Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции - Параллельное программирование - файл лекции.doc


Лекции - Параллельное программирование
скачать (42.3 kb.)

Доступные файлы (1):

лекции.doc228kb.16.11.2006 11:25скачать

содержание
Загрузка...

лекции.doc

Реклама MarketGid:
Загрузка...
Параллельное программирование.


1. Немнюгин С.А., Стесик О.Л. Параллельное программирование для многопроцессорных вычислительных систем. – СПб.: БХВ-Петербург, 2002.

2. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб: БХВ-Петербугр, 2002.

3. Богачев К.Ю. Основы параллельного программирования. – М.:Бином, 2003.

4. Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования. – М.:Вильямс, 2003.


Основы пар. Прогр.


Пар. Программа содержит несколько процессов (последовательностей команд), работающих совместно. Процессы взаимодействуют друг с другом. Есть две схемы взаимодействия – используя общие ресурсы, например, общую память или обмен сообщениями. Первый используется в рамках одной вычислительной системы (одно или многопроцессорной), второй – для распределенных вычислений.

В любом случае необходима взаимная синхронизация. Также есть два основных вида синхронизации.

Взаимное исключение требует, чтобы критические секции процессов не выполнялись одновременно. Условная синхронизация задерживает процесс, пока не выполнится некоторое условие. Например один процесс запиывает данные в буфер ОЗУ, а другой – читает их оттуда. Пока первый не выполнил запись, второй не может выполнить чтение.

ПП возникло в 60-е гг 20 в в сфере операционных систем. Контрллеры устройств работали независимо от ЦП и взаимодействовали с помощью прерываний. Затем появились многопроцессорные машины

Архитектуру МП рассмотрим в следующий раз, а пока выделим основные классы ПП.

  1. Многопоточные системы. – выполняется несколько потоков на одном процессоре по очереди, разделяя время процессора, ОП, другие ресурсы. Пример – современные ОС.

  2. Распределенные вычисления - компоненты выполняются на выч. Системах, связанных сетью с пом. Обмена сообщениями. Пример – архитектура Клиент-Сервер.

  3. Синхронные параллельные вычисления – научные вычисления, моделирование для суперкомпьютеров,


Модель вычислений может быть синхронной – все процессы выполняют одни и те жже действия с собственными данными или асинхронной – различные процессы решают разные задачи.


Основные модели (методы) ПП или парадигмы.


  1. Итеративный параллелизм – параллельное выполнение итеративных программ, работающих вместе над одной задачей. Часто встречается в научных вычислениях

Пример – умножение матриц

For i:=1 to n do

For j:=1 to n do

Begin

C[I,j]:=0;

For k:=1 to N do C[I,j]:=c[I,j]+a[I,k]*b[k,j]

End;

Некоторые операции могут выполняться параллельно. Какие? Независимые. Определим множество чтения операции – множество необходимых данных, множество записи – переменные, которые изменяет программа. Две операции независимы, если их множества записи не пересекаются. Вычисления внутренних произведений – независимые операции.

Их можно делать параллельно. Либо строки, либо столбцы, либо и то и другое.

Можно ли параллельно выполнять внутрениий цикл? Нет.



  1. Рекурсивный параллелизм – параллельно выполняются независимые рекурсивные процедуры. Для решения комбинаторных проблем – сортировки, поиска, перебора и др.

Процедуры буду независимы, если их множества значений не пересекаются. Это будет, если они не пишут в глобальные переменные, аргументы и результаты – различные переменные.

Пример. Вычисление интеграла.

Можно разделить на отрезки и вычислить по формуле трапеций. В этом случае постоянно идет обращение к переменной area и распараллелить нельзя.

Можно разбить пополам, посчитать интеграл для левой и правой половинки и сравнить с трапеций в целом. Если их разность > epsilon, то площади левой и правой половинки вычисляются рекурсивно. 5 параметров – концы отрезка, значения функции в концах, площадь трапеции.

  1. Производители и потребители. Организуются в конвейер. Каждый процесс получает на вход данные, обрабатывает и передает следующему процессу в цепочке. Пример: фильтры в Unix (more). Используют стандартные файлы stdin, stdout. Фильтры выполняются параллельно. Производитель ожидает освобождения буфера, затем добавляет в него новую строку. Потребитель ожидает новой строки, затем забирает ее.

  2. Клиенты и серверы – обычно в распределенных системах. Клиент запрашивает сервис и ждет ответа. Сервер ожидает запросов и обрабатывает их. Фактически Кл-сервер – обобщение процедур и их вызовов. В распределенных системах используется специальная техника вызова процедур – удаленный вызов процедуры или рандеву. Примеры – файловая система на сервере. При изменении ресурсов нужны блокировки. WWW

  3. Взаимодействующие равные. Научные вычисления. Несколько процессов в распределенных вычислениях обмениваются информацией.

Как сделать умножение матриц с помощью передачи сообщений? Параллелизм по строкам – каждый процесс получает строку а и всю матрицу в от отдельного управляющего процесса. Затем он отдает строку результата в управляющий процесс.

Чтобы сделать процессы равными, дадим каждому процессу по одному столбцу. После вычисления элемента процесс отдает столбец следующему процессу и забирает новый столбец от предыдущего.


^ Аппаратное обеспечение. Многопроцессорные архитектуры.


Однопроцессорные архитектуры


ЦПУ – кэш1 – кэш2 – память


Параллелизм внутри обычного процессора

1. Конвейеризация. Процессор принимает новую инструкцию каждый цикл, даже если предыдущие не завершены. В результате выполнение нескольких инструкций перекрывается и в процессоре находятся сразу несколько инструкций в разной степени готовности. Они образуют конвейер инструкций

Стадии исполнения: выборка, декодирование, исполнение, запись результатов.

ВДИЗ ВДИЗ ВДИЗ

Процессор без конвейера

ВДИЗ

ВДИЗ

ВДИЗ

Процессор с конвейером.

Поток инструкций могут нарушить переходы и прерывания. Поэтому используется предсказание переходов.

Внутри конвейера могут быть взаимозависимые инструкции. Команда может читать результат, который пишет предыдущая. Поэтому оптимизирующие компиляторы переупорядочивают команды, чтобы избежать зависимостей. Также используется динамическое переименование регистров.


  1. Суперскалярность. Исполнение нескольких инструкций одновременно. Требует наличие нескольких независимых устройств: целочисленных, для работы с плавающей точкой, управления памятью, мультимедийных команд и т.д.В суперскалярном процессоре несколько конвейеров инструкций.

  2. Многоядерность. Фактически несколько процессоров с разделяемой памятью



Многопроцессорные архитектуры

  1. Сильно связанные процессоры (SMP- симметричные мультипроцессорные системы).

Общая шина, общая память Задачи могут переходить от одного процессора к другому. Синхронизация кэшей. Пример – мат. плата с двумя Pentium 4.

  1. Слабо связанные процессоры. Разделяемая память, но невозможен переход задачи.


Память память

----------------------------- сеть

ЦПУ ЦПУ

Пример – промышленные компьютеры –стойки с процессорными платами и платами с памятью.

3. Распределенные процессоры. Распределенная память.

----------------------------- сеть

память память

ЦПУ ЦПУ

Кластеры.

Возможны гибридные схемы. Например модули сильно связанных процессоров с общейц памятью соединяются через шину.


Поддержка параллелизма системой команд процессора.

Доступ к объектам синхронизации (например семафорам). Процесс читает значение семафора. Если оно = 1, то процесс его обнуляет, занимая семафор. Изменение семафора состоит из трех стадий: чтение, изменение, запись. Если на стадии чтения произойдет переключение на другой процесс, то он также может занять семафор, что приведет к одновременной попытке обратиться к разным ресурсам, то есть к ошибке.

Для решения этой проблемы процессоры имеют инструкцию выполняющую неделимый цикл чтение-изменение-запись.


^ Процессы, задачи (потоки) и синхронизация.


Процесс – код программы в процессе выполнения.

Имеет собственную память под код и данные, отображение виртуальной памяти на реальную, а также стек.

^ Задача (поток, нить) – одна из ветвей выполнения процесса. Разделяет с процессом память под код и данные, отображение виртуальной памяти на реальную. Имеет собственный стек, то есть свои локальные переменные.

Взаимодействие задач легче, поскольку у них есть общая разделяемая память. Для процессов приходится организовывать обмен сообщениями.

Состояние параллельной программы состоит из значений переменных в некоторый момент времени. Программа начинает выполнение в некотором начальном состоянии. Процессы (потоки) выполняются параллельно и каждый изменяет состояние программы. Каждый оператор процесса изменяет состояние неделимым образом. Выполнение пар. программы можно рассматривать как последовательность состояний, которая называется история s0->s1->…->sn. Число возможных историй программы огромно.

Цель синхронизации процессов – исключить нежелательные истории.

Взаимное исключение состоит в выделении в процессах критических секций, которые не прерываются другими процессами, использующими те же переменные. Условная синхронизация состоит в приостановке процесса до выполнения некоторого условия.

<await (B) S;>

Параллельная программа должна обладать некоторыми свойствами:

– безопасность (программа не переходит в нежелательное состояние)

– живучесть (программа обязательно оказывается в желательном состоянии)

Пример.

Поиск образца в файле

{открыть файл}

readln(f,s);

while not (eof(f)) do

begin

if search(p,s) then Writeln(s);

readln(f,s);

end;


Две строки в теле цикла можно попытаться выполнить параллельно. Однако они не являются независимыми. Нужно, чтобы чтение производилось не в ту строку, где происходит поиск.


{открыть файл}

readln(f,s1);

while not (eof(f)) do

begin

if search(p,s1) then Writeln(s1); //*

readln(f,s2); //*

s1:=s2

end;


Программа правильна, но неэффективна, поскольку надо потоки создавать внутри цикла и копировать строки. Нужно сделать два цикла в разных потоках. Используем схему производитель-потребитель. Один поток будет читать из файла в буфер. Другой – искать строку в буфере.

Взаимодействуют потоки через разделяемую переменную buffer.


Var buffer:string;

Const done:Boolean=false;


//процесс 1

var s1:string;

….

While true do

begin

//ожидать заполнения буфера или значения true

if done then break;

s1:=buffer

//сигнализировать, что буфер пуст

if search(p,s1) then Writeln(s1);

end;


//процесс 2

var s2:string;

….

While true do

Begin

Readln(f,s2);

If eof(f) then

Begin

Done:=true;

Break

End;

//ожидать опустошения буфера

buffer:=s2;

//сигнализировать о заполнении буфера

end;


Пример. Поиск максимального элемента в массиве.


^ Критические секции.


Критические секции – исторически первый способ обеспечения синхронизации. Предложены Эдсгером Дейкстрой в 1965 году. Критическая секция – последовательность операторов внутри процесса, содержащая протоколы входа и выхода, удовлетворяющая нескольким условиям:

  1. Взаимное исключение В любой момент только один процесс может выполнять свою критическую секцию.

  2. Отсутствие взаимной блокировки. Если несколько процессов пытаются войти в свои критические секции, хотя бы один сделает это

  3. Если процесс пытается войти в критич. секцию, а другие выполняют некритические секции, то ему разрешается вход

  4. Процесс, который пытается войти в крит. секцию когда-нибудь это сделает.

1-3 – свойства безопасности, 4 – живучести.

Критическая секция может быть реализована методом активной блокировки с помощью разделяемой логической переменной lock. Начальное значение – false


// вход

While lock do;

lock:=true;

//Крит. Секция

//выход

lock:=false;


Как добиться неделимости действий? В процессорах есть операция проверить и установить (test and set). Ее логика описывается следующим кодом

Function TS(var lock:Boolean):Boolean;

Var n:Boolean;

Begin

N:=lock; lock:=true; TS:=N;

End;


Тогда вход опишется так

While TS(Lock);


Если обозначить вход в Крит. cекцию CSEnter, а выход – CSExit, то задача взаимной блокировки решается следующим кодом

CSEnter;

S;

CSExit;


Задача условной синхронизации – <await (B) S;>

CSEnter;

While not(B) do

Begin

CSExit;

Delay; // задержка на случайное время

CSEnter;

End;

S;

CSExit;

Такая условная синхронизация применяется в сети Ethernet. Чтобы передать сообщение контроллер отправляет его в сеть и следит, не возникла ли коллизия. Если была коллизия, делается пауза случайной длины и повторяется передача. Интервал для длины паузы удваивается, если коллизии повторяются.

Решение с активной блокировкой не является справедливой стратегией: одни потоки могут часто входить в секцию, другие – никогда не попасть в нее. Дело в том, что порядок входа не определен.

Существуют решения задачи критической секции со справедливой стратегией планирования: алгоритм разрыва узла, алгоритм билета, алгоритм поликлиники.


Алгоритм разрыва узла (алгоритм Питерсона) обеспечивает поочередный вход двух процессов в критическую секцию. Заводятся две логические переменные in1, in2 – значение true, если соответствующий поток находится в критической секции. Также заводится переменная Last , которая показывает какой поток пытается последним зайти в критическую секцию. Если оба процесса пытаются войти в Крит. Секцию, то выполнение последнего потока приостанавливается.


var in1, in2: boolean;

Last: integer;

//процесс 1

While true do

Begin

Last:=1; in1:=true;

While in2 and (last = 1) do;

//кр. Секция

in1:=false;

//некр. Секция

end;


//процесс 2

While true do

Begin

Last:=2; in2:=true;

While in1 and (last = 2) do;

//кр. Секция

in2:=false;

//некр. Секция

end;


Для n процессов алгоритм разрыва узла достаточно сложен.


Алгоритм билета основан на том, что каждый процесс, который пытается войти в кс получает номер, который больше номера любого из ранее вошедших. Процесс ждет, пока не будут выполнены кс процессов, имеющих меньшие номера.


Логика


Const number:integer =1; next:integer=1;

Var turn: array[1..n] of integer;


// процесс i

While true do

Begin

<turn[i]:=number; inc(number); >

//Здесь можно использовать обычный алгоритм CS (блокировка)

while turn[i]<>next do;

кр секция

inc(next)

некр секция

end;


Недостаток критических секций с активным ожиданием – сложность, отсутствие грани между переменными синхронизации и другими переменными, неэффективность (ожидающие процессы постоянно проверяют переменные, что занимает время процессора).


Гораздо лучше, если критические секции реализуются на уровне ОС. В Windows 32 такая реализация имеется.


Для работы с критическими разделами используются следующие функции:

VOID InitializeCriticalSection(LPCRITICAL_SECTION lpCriticalSection) - инициализация синхронизатора типа критический раздел.

lpCriticalSection - указатель на переменную типа CRITICAL_SECTION. Тип данных CRITICAL_SECTION является структурой, ее поля используются только Windows.

VOID EnterCriticalSection(LPCRITICAL_SECTION lpCriticalSection) - запрос на вход в критический раздел с ожиданием.

BOOL TryCriticalSection(LPCRITICAL_SECTION lpCriticalSection) - запрос на вход в критический раздел без ожидания (с возвратом логического значения – вошли или нет).

VOID LeaveCriticalSection (LPCRITICAL_SECTION lpCriticalSection) - выход из критического раздела.

VOID DeleteCriticalSection(LPCRITICAL_SECTION lpCriticalSection) - удаление критического раздела (обычно при выходе из программы).

В DELPHI критические секции описаны в модуле Windows. Для описания переменной типа критическая секция нужно использовать тип TRTLCriticalSection

Итак, для создания критического раздела необходимо инициализировать структуру CRITICAL_SECTION. Создав объект CRITICAL_SECTION, мы можем работать с ним, т.е. можем обозначить код, доступ к которому для одновременно выполняющихся задач требуется синхронизировать. Если один поток вошел в критический раздел, то следующий поток, вызывая функцию EnterCriticalSection с тем же самым объектом типа CRITICAL_SECTION, будет задержан внутри функции. Возврат произойдет только после того, как первый поток покинет критический раздел, вызвав функцию LeaveCriticalSection. В этот момент второй поток, задержанный в функции EnterCriticalSection, станет владельцем критического раздела, и его выполнение будет возобновлено.

К
76
огда объект критический раздел больше не нужен программе, его можно удалить с помощью функции DeleteCriticalSection. Это приведет к освобождению всех ресурсов системы, задействованных для поддержки объекта критический раздел.

Заметим, что возможно определение нескольких объектов типа критический раздел. Если в программе имеется четыре потока, и два из них разделяют одни данные, а два других - другие, то потребуется два объекта типа критический раздел.

Рассмотрим такой пример. Мы хотим записывать и считывать значения из некоего глобального массива mas. Причем запись и считывание должны производиться двумя разными потоками. Вполне естественно, что лучше, если эти действия не будут выполняться одновременно. Поэтому введем ограничение на доступ к массиву.


Листинг 1. Ограничение доступа к массиву с использованием критических разделов


// Массив значений.

Var mas: array [1..1000] of integer;

// Критическая секция, регулирующая доступ к массиву

Var CritSec: TRTLCriticalSection;



// Инициализируем критический раздел

InitializeCriticalSection(CritSect);

// Запускаем потоки

Thread1.Resume;

Thread2.Resume;

DeleteCriticalSection(CritSec);


// Первый поток: запись в массив данных

procedure Thread1.Execute;

Var i: integer;

Begin // Запись значения в массив

 // Запрос на вход в критический раздел

EnterCriticalSection(CritSec);

 // Выполнение кода в критическом разделе

 for i:= 1 to 1000 do mas[i] := i;

// Выход из критического раздела:

// освобождаем критический раздел для доступа

// к нему других задач

LeaveCriticalSection(CritSec);

End;

// Второй поток: считывание данных из массива

procedure Thread2.Execute;

Var i: integer;

Begin // Считывание значений из массива

 // Запрос на вход в критический раздел

EnterCriticalSection(CritSec);

 // Выполнение кода в критическом разделе

 for i:= 1 to 1000 do j:=mas[i];

// Выход из критического раздела:

// освобождаем критический раздел для доступа

// к нему других задач

LeaveCriticalSection(CritSec);

End;

И хотя приведенный нами пример подобного ограничения (см. листинг 1) чрезвычайно упрощен, он хорошо иллюстрирует работу синхронизатора типа критический раздел: пока один поток "владеет" массивом, другой доступа к нему не имеет.

Вход в критическую секцию уже занявшим его потоком возможен любое количество раз (столько же раз необходимо выполнить операцию выхода).


Для упрощения работы с критическими секциями в DELPHI и C++Builder есть специальный класс TCriticalSection.

У него имеется конструктор Create без параметров, методы Acquire и Enter для входа в секцию, методы Release и Leave для выхода из секции. Для удаления объекта используется Free. Перепишем наш пример.


^

4.2. Исключающий семафор (mutex)


Еще один вид синхронизаторов - исключающий семафор (мьютекс – mutual exclusion). Основное его отличие от критического раздела заключается в том, что последний можно использовать только в пределах одного процесса (одного запущенного приложения), а исключающими семафорами могут пользоваться разные процессы. Другими словами, критические разделы - это локальные объекты, которые доступны в рамках только одной программы, а исключающие семафоры могут быть глобальными объектами, позволяющими синхронизировать работу программ (т. е. разные запущенные приложения могут разделять одни и те же данные).

Р
78
ассмотрим основные функции для работы с объектами mutex.


1. Создание объекта mutex:

HANDLE CreateMutex(LPSECURITY_ATTRIBUTES lpMutexAttributes, BOOL bInitialOwner, LPCTSTR lpName );

Параметры:

lpMutexAttributes - указатель на структуру SECURITY_ATTRIBUTES (в Windows 95 данный параметр игнорируется);

bInitialOwner - указывает первоначальное состояние созданного объекта (TRUE - объект сразу становится занятым, FALSE - объект свободен);

lpName - указывает на строку, содержащую имя объекта. Имя необходимо для доступа к объекту других процессов, в этом случае объект становится глобальным и им могут оперировать разные программы. Если вам не нужен именованный объект, то укажите NULL. Функция возвращает указатель на объект mutex. В дальнейшем этот указатель используется для управления исключающим семафором.

2. HANDLE OpenMutex( DWORD dwDesiredAccess, // access flag

BOOL bInheritHandle, // inherit flag

LPCTSTR lpName // pointer to mutex-object name );

Позволяет получить указатель на мьютекс, открытый в другом разделе.

3. Закрытие (уничтожение) объекта mutex :

BOOL CloseHandle(HANDLE hObject )

3. Универсальная функция запроса доступа:

DWORD WaitForSingleObject(HANDLE hHandle, DWORD dwMilliseconds) - универсальная функция, предназначенная для запроса доступа к синхронизирующему объекту (в данном случае к объекту mutex).

Параметры:

hHandle - указатель на синхронизирующий объект (в данном случае передается значение, возвращенное функцией CreateMutex);

dwMilliseconds - время (в миллисекундах), в течение которого происходит ожидание освобождения объекта mutex. Если передать значение INFINITE (бесконечность), то функция будет ждать бесконечно долго.

Данная функция может возвращать следующие значения:

WAIT_OBJECT_0 - объект освободился;

WAIT_TIMEOUT - время ожидания освобождения прошло, а объект не освободился;

WAIT_ABANDON - произошел отказ от объекта (т. е. процесс, владеющий данным объектом, завершился, не освободив объект). В этом случае система (а не "процесс-владелец") переводит объект в свободное состояние. Такое освобождение объекта не предполагает гарантий защищенности данных;

WAIT_FAILED - произошла ошибка.

4. Освобождение объекта mutex:

BOOL ReleaseMutex(HANDLE hMutex) - освобождает объект mutex, переводя его из занятого в свободное состояние.

Посмотрим, как выглядит наш пример c критическими разделами, если переписать его, используя исключающие семафоры.

Листинг 2. Ограничение доступа к массиву с использованием исключающих семафоров


// Массив значений.

int mas[1000]; 

// Объект, регулирующий доступ к разделяемому коду.

HANDLE CritMutex; 

{

...

// Инициализируем семафор разделяемого кода.

CritMutex = CreateMutex(NULL,FALSE,NULL);

... //  Текст программы.

// Закрываем объект доступа к разделяемому коду.

CloseHandle(CritMutex);

}

// Первый поток: запись в массив данных.

DWORD WINAPI thread1(LPVOID par)

{ // Запись значений в массив.

 // Запрос на вход в защищенный раздел.

 DWORD dw = WaitForSingleObject(CritMutex,INFINITE);

if(dw == WAIT_OBJECT_0) 

{ // Если объект освобожден корректно, то

 // выполнение кода в защищенном разделе.

  for(int i = 0;i<1000;i++)

  {

    mas[i] = i;

 
80
}  


// Выход из защищенного раздела:

// освобождаем объект для доступа

//  к защищенному разделу других задач.

 ReleaseMutex(CritMutex);

 }

return 0;

}


// Второй поток: считывание данных из массива.

DWORD WINAPI thread2(LPVOID par)

{ // Считывание значений из массива.

 int j;

 // Запрос на вход в защищенный раздел.

 DWORD dw = WaitForSingleObject(CritMutex,INFINITE);

if(dw == WAIT_OBJECT_0) 

{ // Если объект освобожден корректно, то

 // выполнение кода в защищенном разделе.

  for(int i = 0;i<1000;i++)

  {

    j = mas[i];

  }  


// Выход из защищенного раздела:

// освобождаем объект для доступа

//  к защищенному разделу других задач.

 ReleaseMutex(CritMutex);

}

return 0;

}

Исключающий семафор может быть занят неограниченное количество раз одним и тем же потоком.


http://mbo88.narod.ru/Ch9.html


Семафоры.


Семафор – реализуемая ядром операционной системы специальная переменная, которая доступна параллельным процессам для выполнения двух операций – закрытия и открытия (P и V операции). Операции неделимы и взаимно исключают друг друга. Терминология железнодорожная. Процесс устанавливает семафор на время критической секции. Другие процессы в это время приостановлены и ждут освобождения семафора.

Значение семафора – неотрицательное целое число.

Операция V(s) : <s = s +1> увеличивает значение семафора.

Операция P(s) <await (s>0) s = s – 1>. Проверяет значение s и ждет, пока оно не станет положительным, после чего уменьшает его на 1. Ожидание является пассивным, то есть процесс приостанавливается. Операция V переводит один из ожидающих процессов в состояние работы.

Обычный семафор может принимать любые значения. Двоичный – только 0 и 1.

Операционная система при работе с семафорами применяет справедливую стратегию, то есть возобновляет работу процессов в том порядке, в котором они приостанавливались, что обеспечивает для каждого процесса возможность продолжить работу.

Применение семафоров.

  1. Критические секции. Можно использовать двоичный семафор.

sem s = 1

….

P(s)

//критическая секция

V(s)

….

  1. Барьерная синхронизация. – синхронизация по времени окончания опреаций в разных процессах.

Требования – ни один из процессов не должен перейти барьер, пока к нему не подошли все процессы. Например для двух процессов


Sem arrive1 = 0 ; arrive 2 = 1;


//1 процесс

….

V(arrive1); //сигнал о прибытии

P(arrive2); // ожидание другого процесса




//2 процесс

….

V(arrive2);

P(arrive1);


Для n процессов нужен массив семафоров. Каждый процесс выполняет операцию V для своего элемента массива, а затем выполняет P для всех остальных семафоров.


  1. Задача о производителе и потребителе. Производитель производит данные, помещая их в кольцевой буфер из n записей. Потребитель их обрабатывает, выбирая из буфера. Если буфер заполняется, то производитель должен подождать. Если буфер пуст, то ждет потребитель



Var Buf: array [ 0..N-1] of Type;

Var head, tail: integer;

empty, full: sem;


head:=0; tail:=0; empty:=n; full =0 ;


//производитель

While true do

Begin

//создать data

P(empty);

Buf[tail]:=data; tail:=(tail+1) mod n;

V(full);

End


//потребитель

While true do

Begin

P(full);

Result:=Buf[head]; head:=(head+1) mod n;

V(empty);

End


Семафоры играю роль счетчиков ресурсов. Empty считает количество пустых ячеек, Full – заполненных.

Если несколько производителей и потребителей, то нужно добавить двоичные семафоры для взаимного исключения при добавлении и чтении.


  1. Задача об обедающих философах.

Пять философов сидят за круглым столом. Между ними по вилке. Каждый ест двумя вилками. Каждый некоторе время думает, затем пытается поесть. Нужно смоделировать их поведение. Программа должна избегать ситуации, когда все голодны, но каждый взял по вилке – сл-но ни один не может взять обе вилки.

Цикл будет такой

While True do

Begin

// думаем

sleep(random(1000));

//берем вилки

// едим

sleep(random(1000));

//отдаем вилки

end;


Каждая вилка – семафор (или критическая секция).можно завести массив семафоров. Чтобы не было взаимной блокировки, нужно чтобы были философы которые сначала берут правую вилку и были, которые берут левую. Например, четные и нечетные.


  1. Задача о читателях и писателях. Есть БД. Есть процессы читатели , которые могут одновременно читать данные. Есть писатели, которые имеют искл. доступ к данным. Читатели конкурируют с писателями, писатели – между собой.

Есть два способа решения этой задачи. Первый – как задачи взаимного исключения.

Для этого заведем переменные nr – число читателей, семафоры rw – для исключения доступа к БД читателей и писателей, m – для блокировки доступа читателей к nr.


// Writer



P(rw);

//пишем

V(rw)




//reader

P(m)

nr: = nr +1;

if nr =1 then P(rw); //первый читатель – блокировать доступ

V(m)

Читать

P(m);

Nr:=nr-1;

if nr = 0 then V(rw); // последний читатель – снять доступ.

V(m)


Преимущество будет у читателей. Пока они читают, писатели не смогут писать. Новый читатель получает преимущество перед писателем. Это несправедливо.


Рассмотрим решение с помощью условной синхронизации.

Будем подсчитывать число писателей nw и читателей nr. Множество хороших состояний параллельной программы будет описываться следующим условием

((nr = 0) or (nw =0)) and (nw<=1)

Отсюда получается код для читателей и писателей

//reader

<await (nw=0) nr:=nr+1>

чтение

< nr:=nr-1>

//writer

<await (nw=0 and nr=0) nw:=nw+1>

чтение

< nw:=nw-1>


Для реализации await используем метод передачи эстафеты. Этот метод позволяет реализовать любую условную синхронизацию.

С каждым условием свяжем семафор и счетчик с нулевыми нач значениями. Семафор будем использовать для приостановки процесса пока условие защиты не станет истинным. Счетчик будет хранить число приостановленных процессов. Для нашей задачи нужно два семафора r и w, а также два счетчика dr и dw – количество ожидающих писателей и читателей. Семафор е используется для входа в неделимые блоки (кр.секции).

Для выход используется следующий код (Signal). Он сбрасывает один из трех семафоров – если нет писателей, но есть ожидающий читатель – семафор r, если нет писателей и читателей – w, иначе – e.


If (nw=0) and (dr >0)

Begin dec(dr); V(r) end

Else

If (nr=0) and (nw=0) and (dw >0)

Begin dec(dw); V(w) end

Else

V(e)


//reader

p(e);

if (nw>0)

begin

dr:=dr+1;

v(e);

p(r)

End;

Nr=Nr+1;

Signal;

//читаем

P(e);

Nr:=Nr-1;

Signal;


//writer

p(e);

if (nr>0 or nw>0)

begin

dw:=dw+1;

v(e);

p(w)

End;

Nw=Nw+1;

V(e);

//пишем

P(e);

Nw:=Nw-1;

Signal;


Из трех семафоров в листинге только один может иметь значение 1. Каждый код начинается с P и заканчивается V - сл-но код выполняется со взаимным исключением.

Метод называется метод передачи эстафеты из-за способа выработки сигнала семафорами. Процесс внутри кр секции получил эстафету. При выходе из кр секции он передает эстафету следующему ожидающему процессу. Если ни один из процессов не ожидает, то эстафету получает следующий процесс, взывавший P(e).


Сигнальный код можно упростить, учитывая неравенства для dr,dw,nr,nw в каждом месте программы. Получим код


//reader

p(e);

if (nw>0) // or (dw>0)

begin

dr:=dr+1;

v(e);

p(r)

End;

Nr=Nr+1;

if dr>0 then begin dr = dr-1; V(r) end

else v(e);

//читаем

P(e);

Nr:=Nr-1;

If (nr=0) and (dw >0)

Begin dec(dw); V(w) end

Else V(e)


//writer

p(e);

if (nr>0 or nw>0)

begin

dw:=dw+1;

v(e);

p(w)

End;

Nw=Nw+1;

V(e);

//пишем

P(e);

Nw:=Nw-1;

If (dr >0)

Begin dec(dr); V(r) end

Else

If (dw >0)

Begin dec(dw); V(w) end

Else

V(e)


Для того, чтобы писатели получили преимущество можно изменить программу. Метод передачи эстафеты позволяет реализовать любую условную синхронизацию и гибко управлять стратегией программы.

^

4.4. Механизм семафоров


В Win32 реализован также механизм классических семафоров. Для работы с классическими семафорами используются следующие функции.

Функция создания объекта типа семафор:

HANDLE CreateSemaphore( LPSECURITY_ATTRIBUTES lpSemaphoreAttributes, LONG lInitialCount, LONG lMaximumCount, LPCTSTR lpName );

Параметры:

lpSemaphoreAttributes - указатель на структуру SECURITY_ATTRIBUTES , который определяет, может ли возвращаемый дескриптор наследоваться порожденными процессами. Если NULL, то дескриптор не может наследоваться.

lInitialCount - определяет начальное значение семафора, которое должно быть не меньше нуля и не больше lMaximumCount. Семафор установлен, если его значение больше нуля, и не установлен, если его значение равно нулю. Счетчик семафора увеличивается при вызове функции ReleaseSemaphore.

lMaximumCount - определяет максимальное значение семафора;

lpName - указывает на строку, определяющую имя семафора, если NULL, то семафор открывается без имени.

Функция возврата дескриптора существующего именованного семафора:

HANDLE OpenSemaphore(

DWORD dwDesiredAccess, // access flag

BOOL bInheritHandle, // inherit flag

LPCTSTR lpName // pointer to semaphore-object name

);

Функция увеличения счетчика семафора на заданное число:

BOOL ReleaseSemaphore( HANDLE hSemaphore, LONG lReleaseCount,LPLONG lpPreviousCount );

Параметры:

hSemaphore - дескриптор семафора;

lReleaseCount - определяет, на сколько увеличивать счетчик семафора;

lpPreviousCount - указатель на 32-битную переменную с предыдущим значением счетчика (NULL, если предыдущее значение не требуется).

Функция WaitForSingleObject определяет, свободен ли семафор, и если он свободен, то уменьшает значение счетчика семафора на 1, в противном случае поток будет приостановлен, пока семафор не освободится.

Посмотрим, как выглядит пример c критическими разделами, если переписать его, используя классические семафоры (см. листинг 3).

Листинг 3. Ограничение доступа к массиву с использованием классических семафоров

// Массив значений.

int mas[1000]; 

// Семафор, регулирующий доступ к критическому разделу.

HANDLE Semaph;  

{

...

// Создаем семафор;

Semaph = CreateSemaphore(NULL, 1, 1, NULL);

// Запускаем потоки

CreateThread(NULL,0,thread1,NULL,0,NULL);

CreateThread(NULL,0,thread2,NULL,0,NULL);

... // Текст программы.

// Удаляем семафор

CloseHandle(Semaph);

}

// Первый поток: запись в массив данных.

DWORD WINAPI thread1(LPVOID par)

{ // Запись значения в массив.

 // Запрос на вход в критический раздел.

WaitForSingleObject(Semaph, INFINITE);

 // Выполнение кода в критическом разделе.

 for(int i = 0;i<1000;i++)

{

  mas[i] = i;

}  

// Выход из критического раздела:

// освобождаем семафор для доступа

// других задач к критическому разделу

ReleaseSemaphore(Semaph, 1, NULL);

// завершаем поток

return 0;

}

// Второй поток: считывание данных из массива.

DWORD WINAPI thread2(LPVOID par)

{ // Считывание значений из массива.

 int j;

 // Запрос на вход в критический раздел.

WaitForSingleObject(Semaph, INFINITE);

 // Выполнение кода в критическом разделе.

 for(int i = 0;i<1000;i++)

{

  j = mas[i];

}  

// Выход из критического раздела:

// освобождаем семафор для доступа

// других задач к критическому разделу

ReleaseSemaphore(Semaph, 1, NULL);

// завершаем поток

return 0;

}


Реализация многозадачности и многопоточности в UNIX.

Средства управления процессами

Функция fork – клонирует текущий процесс. Возвращает идентификатор потомка в род. процессе и ноль – в дочернем процессе.

Функции execl,execv позволяют заменить текущий процесс новым.

Функция waitpid позволяет ожидать окончания порожденного процесса

Функция kill посылает сигнал процессу

Функция signal позволяет указать функцию, выполняющуся при получении сигнала.

Процессы могут использовать специальным образом создаваемую разделяемую память, семафоры, очереди сообщений.

Для реализации многопоточности используется библиотека PTHREAD.

Она содержит функции для создания потока с указанием выполняющейся в потоке функции, ожидания окончания потока, объекты синхронизации (мьютексы).


Для условной синхронизации в библиотеке PTHREAD имеются условные переменные (condvar). С условной переменной связана очередь потоков, ожидающих ее освобождения. Поток может проверить, пуста ли очередт (empty), встать в очередь (wait), запустить первый поток из очереди (signal).

Использование условных переменных позволяет упростить сложное взаимодействие потоков, реализовать различные стратегии планирования.


Параллельные алгоритмы.


Для обычных алгоритмов важное понятие – выч. Сложность. Для пар. Алгоритмов вводится понятие коэффициент ускорения (насколько ПА быстрее оптимвльного обычного). Например для сорт О(nlogn). Если пар алгоритм имеет сложность O(n) то КУ будет O(log n).

Другое понятие – стоимость пар алгоритма – произведение количества процессоров на сложность алгоритма. Если сортировка имеет сложность O(n) и требует столько процессоров, сколько исх данных, то стоимость будет O(n^2).

Еще одно понятие – расщепляемость задачи (на сколько процессоров ее можно разбить). Нас будут интересовать алгоритмы, в которых число процессоров значительно менше объема входных данных и не требует увеличения при росте их объема.


Макконелл. Основы современных алгоритмов.


Распределенные вычисления.

Используется, если отсутствует разделяемая память – кластеры, компьютерные сети, гибридные архитектуры. В этом случае процессы не могут взаимодействовать с помощью разделяемых переменных. Вместо этого они должны обмениваться сообщениями.

Как правило, программирование для сетевых кластеров отличается от привычной модели программирования для многозадачных систем, построенных на базе одного или множества процессоров. Часто в таких системах необходимо обеспечить только синхронизацию процессов, и нет нужды задумываться об особых способах обмена информацией между ними, т.к. данные обычно располагаются в общей разделяемой памяти. В сети реализация такого механизма затруднительно из-за высоких накладных расходов, связанных с необходимостью предоставлять каждому процессу копию одной и той же разделяемой памяти для работы. Поэтому, обычно, при программировании для сетевых кластеров используется SPMD-технология [8] (Single Program – Multiple Data, одна программа – множественные данные). Идея SPMD в том, чтобы поделить большой массив информации между одинаковыми процессами, которые будут вести обработку своей части данных (рис. 1).



Рис. 1. Схема взаимодействия частей SPMD-программы.

В случае SPMD-подхода достаточно рассылать время от времени процессам блоки данных, которые требуют трудоемкой обработки, а затем собирать результаты их работы. Если время обработки блока данных одной машиной значительно больше, чем время пересылки этого блока по сети, то сетевая кластерная система становится очень эффективной.


Передача сообщений должна обеспечивать синхронизацию процессов. Для этого вводится понятие канала. Каждый канал обеспечивает путь взаимодействия процессов.

Разработано несколько механизмов распределенного программирования. Они отличаются способами использования каналов и синхронизации взаимодействия. Каналы бывают однонаправленными и двунаправленными, обеспечивают асинхронную (неблокирующую) и синхронную передачу сообщений. Более высокоуровневые механизмы – удаленный вызов процедур и рандеву.

Простейший способ взаимодействия процессов в распределенных системах – асинхронная передача сообщений.

Канал – очередь сообщений, которые уже отправлены, но еще не получены.

Допустима операция send channel (x), ставящая x в очередь на отправку в канал channel. Очередь теоретически не ограничена, поэтому операция send не вызывает задержку и является неблокирующей.

Для получения сообщения используется операция receive channel (x). Процесс приостанавливается и ожидает, пока в очереди канала не появится сообщение.

Поскольку канал является очередью FIFO, то сообщения принимаются в порядке передачи.

Каналы глобальны относительно процессов и могут использоваться в любом процессе.

Пример использования каналов – сортировка с помощью алгоритма сеть слияния. Сеть слияния использует процессы для слияния упорядоченных последовательностей

Процесс Merge циклически сравнивает числа, полученные из потоков in1 и in2 и отправляет в out меньшее из них.


Procedure Merge

begin

receive(in1, v1);

receive(in2, v2);

while (v1<> eof) and (v2<>eof) do

if v1<= v2 then begin send(out, v1); receive(in1, v1); end

else begin send(out, v2); receive(in2, v2); end;

if (v1 = eof)

while (v2<> eof) do begin send(out, v2); receive(in2, v2); end

else begin send(out, v1); receive(in1, v1); end

send(out,eof)


n-1 процессов слияния соединяются так, чтобы образовывать дерево.


V1 \ Merge\

V2 / \

\

Merge

/

Vn-1\ Merge/

Vn /


Синхронная передача сообщений блокирует процесс, отправляющий сообщение, пока получатель его не получит.

Недостаток синхронного обмена сообщениями – высокая вероятность взаимных блокировок.

Для реализации взаимодействия клиент-сервер требуется двусторонний поток данных, то есть нужно использовать два канала.

Более удобно использовать механизмы взаимодействия – удаленный вызов процедуры и рандеву.

Клиент вызывает удаленную процедуру на сервере и ждет, пока она не вернет результаты.

RPC и рандеву отличаются способом обслуживания вызовов операций. RPC для каждой операции требует объявления процедуры и для обработки вызова создает новый процесс. Рандеву обеспечивает взаимодействие с уже существующим процессом. Процесс-сервер ждет вызова с помощью операции приема, обрабатывает вызов и возвращает результаты.

Пример RPC – технология COM. COM- объекты содержат методы, которые удаленно вызываются.

Недостаток RPC – отсутствует непосредственное взаимодействие процессов. Для его реализации нужно использовать семафорные механизмы синхронизации.

При использовании рандеву можно синхронизировать процессы, используя операторы вызова и приема.


Рассмотрим некоторые системы и языки для параллельных и распределенных вычислений


Интерфейс MPI (Message Parsing Interface) – фактически стандарт распределенного программирования. MPI – библиотека функций, реализованных для разных языков программирования (С/С++, Fortran, Delphi,…)

Имена функций начинаются с MPI_ и описаны в mpi.h.

В MPI всегда есть основной процесс, который производит распределение данных по другим машинам, а после окончания вычислений собирает результаты и показывает их пользователю. Обычно процесс-мастер после распределения данных также выполняет обработку их части, чтобы использовать ресурсы системы наиболее эффективно.

Как уже было сказано выше, MPI является стандартом обмена сообщениями. Он обеспечивает низкоуровневые коммуникации и синхронизацию процессов в сетевом кластере.

По сути дела, каждое сообщение представляет собой пакет типизированных данных, который один процесс может отправить другому процессу или группе процессов. Все сообщения обладают идентификатором (не обязательно уникальным), который задается программистом и служит для идентификации типа сообщения на принимающей стороне.

MPI поставляется в виде библиотеки, подключаемой к среде программирования. Самыми распространенными являются библиотеки для языков Си и Fortran. Также частью MPI является резидент, который запускается на каждой машине кластера и, отвечая на запросы процессов, позволяет им взаимодействовать в сети, а также осуществляет начальный запуск всех процессов, участвующих в расчете и составляющих SPMD-программу, на указанных в файле конфигурации задачи машинах кластера.

Каждый MPI-процесс в пределах SPMD-программы уникально идентифицируется своим номером. Допускается объединять процессы в группы, которые могут быть вложенными. Внутри каждой группы все процессы перенумерованы, начиная с нуля. С каждой группой ассоциирован свой коммуникатор (уникальный идентификатор). Поэтому при осуществлении пересылки данных необходимо указать наряду с номером процесса и идентификатор группы, внутри которой производится эта пересылка. Все процессы изначально содержатся в группе с предопределенным идентификатором MPI_COMM_WORLD, который заводится для каждой запускаемой SPMD-программы (рис. 2). Разные SPMD-программы не знаю о существовании друг друга и обмен данными между ними невозможен.



Рис 2. Нумерация процессов и коммуникаторы в MPI

Рассмотрим основные функции библиотеки. Все они возвращают целое значение, которое либо равно константе MPI_SUCCESS, либо содержит код произошедшей ошибки.

Перед тем, как программа сможет работать с функциями библиотеки необходимо инициализировать MPI с помощью функции:

int MPI_Init(int *argc, char ***argv)

В качестве аргументов этой функции передаются параметры командной строки, поступающие в функцию main().

Если процессу MPI необходимо узнать свой порядковый номер в группе, то используется функция:

int MPI_Comm_rank (MPI_Comm, int *rank)

Ее второй параметр будет выходным, содержащим номер процесса в указанной в первом параметре группе.

Чтобы узнать размер группы (количество процессов в ней) необходимо применить функцию:

int MPI_Comm_size (MPI_Comm, int *ranksize)

Для окончания работы с MPI необходимо использовать функцию:

int MPI_Finalize()

Перед тем, как начать рассмотрение функций передачи/приема сообщений, отметим, какие основные типы данных поддерживает MPI (таблица 1).

Таблица 1. Соответствие типов в MPI и языке Cи

Тип MPI

Тип Cи

MPI_CHAR

char

MPI_BYTE

unsigned char

MPI_SHORT

short

MPI_INT

int

MPI_LONG

long

MPI_FLOAT

float

MPI_DOUBLE

double

MPI_UNSIGNED_CHAR

unsigned char

MPI_UNSIGNED_SHORT

unsigned short

MPI_UNSIGNED

unsigned int

MPI_UNSIGNED_LONG

unsigned long

MPI_LONG_DOUBLE

long double


Для передачи сообщений в MPI используется ряд функций, которые работают синхронно и асинхронно. В первом случае функция не возвращает управления, пока не завершит свою работу, во втором – сразу возвращает управление, инициировав соответствующую операцию, затем с помощью специальных вызовов есть возможность проконтролировать ход выполнения асинхронной посылки или приема данных.

Рассмотрим эти функции подробнее.

int MPI_Send(void* buf, int count,
MPI_Datatype datatype, int dest,
int msgtag, MPI_Comm comm)


Функция выполняет блокирующую посылку сообщения с идентификатором msgtag (идентификатор выбирается самостоятельно программистом!), состоящего из count элементов типа datatype, процессу с номером dest и коммуникатором comm. Все элементы сообщения расположены подряд в буфере buf. Тип передаваемых элементов datatype должен указываться с помощью предопределенных констант типа (таблица 1). Разрешается передавать сообщение самому себе.

Блокировка гарантирует корректность повторного использования всех параметров после возврата из подпрограммы. Следует специально отметить, что возврат из подпрограммы MPI_Send не означает ни того, что сообщение уже передано процессу dest, ни того, что сообщение покинуло процессорный элемент, на котором выполняется процесс, выполнивший MPI_Send. В MPI имеется ряд специальных функций посылки сообщения, устраняющих подобную неопределенность, их рассмотрение выходит за рамки данного руководства.

int MPI_Recv(void* buf, int count,
MPI_Datatype datatype, int source,
int msgtag, MPI_Comm comm,
MPI_Status *status)


Прием сообщения с идентификатором msgtag от процесса source с блокировкой. Число элементов в принимаемом сообщении не должно превосходить значения count. Если число принятых элементов меньше значения count, то гарантируется, что в буфере buf изменятся только элементы, соответствующие элементам принятого сообщения.

Блокировка гарантирует, что после возврата из подпрограммы все элементы сообщения приняты и расположены в буфере buf.

В качестве номера процесса-отправителя можно указать предопределенную константу MPI_ANY_SOURCE - признак того, что подходит сообщение от любого процесса. В качестве идентификатора принимаемого сообщения можно указать константу MPI_ANY_TAG - признак того, что подходит сообщение с любым идентификатором.

Если процесс посылает два сообщения другому процессу, и оба эти сообщения соответствуют одному и тому же вызову MPI_Recv, то первым будет принято то сообщение, которое было отправлено раньше.

Параметр status содержит служебную информацию о ходе приема, которая может быть использована в программе. status является структурой и содержит поля: MPI_SOURCE, MPI_TAG и MPI_ERROR (источник сообщения, идентификатор сообщения и возникшая ошибка, соответственно).

int MPI_Isend(void *buf, int count,
MPI_Datatype datatype, int dest,
int msgtag, MPI_Comm comm,
MPI_Request *request)


Передача сообщения, аналогичная MPI_Send, однако, возврат из подпрограммы происходит сразу после инициализации процесса передачи без ожидания обработки всего сообщения, находящегося в буфере buf. Это означает, что нельзя повторно использовать данный буфер для других целей без получения дополнительной информации о завершении данной посылки. Окончание процесса передачи (т.е. тот момент, когда можно вновь использовать буфер buf без опасения испортить передаваемое сообщение) можно определить с помощью параметра request (идентификатор асинхронной операции определенного в MPI типа MPI_Request) и процедур MPI_Wait и MPI_Test, которые будут рассмотрены ниже.

Сообщение, отправленное любой из процедур MPI_Send и MPI_Isend, может быть принято как функцией MPI_Recv, так и MPI_Irecv.

int MPI_Irecv(void *buf, int count,
MPI_Datatype datatype, int source,
int msgtag, MPI_Comm comm,
MPI_Request *request)


Прием сообщения, аналогичный MPI_Recv, однако возврат из подпрограммы происходит сразу после инициализации процесса приема без ожидания получения сообщения в буфере buf. Окончание процесса приема можно определить с помощью параметра request и процедур MPI_Wait и MPI_Test.

int MPI_Wait(MPI_Request *request, MPI_Status *status)

С помощью этой функции производится ожидание завершения асинхронных процедур MPI_Isend или MPI_Irecv, ассоциированных с идентификатором request. В случае приема, параметры сообщения оказываются в status.

int MPI_Test(MPI_Request *request, int *flag,
MPI_Status *status)


Проверка завершенности асинхронных процедур MPI_Isend или MPI_Irecv, ассоциированных с идентификатором request. В параметре flag возвращает значение 1, если соответствующая операция завершена, и значение 0 в противном случае. Если завершена процедура приема, параметры сообщения оказываются в status. MPI_Test не блокирует программу до окончания соответствующих операций приема/передачи, чем и отличается от MPI_Wait.

MPI позволяет работать с некоторыми операциями коллективного взаимодействия. В операциях коллективного взаимодействия процессов участвуют все процессы коммуникатора. Соответствующая процедура должна быть вызвана каждым процессом, быть может, со своим набором параметров. Возврат из процедуры коллективного взаимодействия может произойти в тот момент, когда участие процесса в данной операции уже закончено. Как и для блокирующих процедур, возврат означает то, что разрешен свободный доступ к буферу приема или посылки, но не означает ни того, что операция завершена другими процессами, ни даже того, что она ими начата (если это возможно по смыслу операции).

int MPI_Bcast(void *buf, int count,
MPI_Datatype datatype, int source,
MPI_Comm comm)


Рассылка сообщения от процесса source всем процессам, включая рассылающий процесс. При возврате из процедуры содержимое буфера buf процесса source будет скопировано в локальный буфер процесса. Значения параметров count, datatype и source должны быть одинаковыми у всех процессов.

int MPI_Gather(void *sbuf, int scount,
MPI_Datatype stype, void *rbuf,
int rcount, MPI_Datatype rtype,
int dest, MPI_Comm comm)


Сборка данных со всех процессов в буфере rbuf процесса dest. Каждый процесс, включая dest, посылает содержимое своего буфера sbuf процессу dest. Собирающий процесс сохраняет данные в буфере rbuf, располагая их в порядке возрастания номеров процессов. Параметр rbuf имеет значение только на собирающем процессе и на остальных игнорируется, значения параметров count, datatype и dest должны быть одинаковыми у всех процессов.

int MPI_Scatter(void *sbuf, int scount,
MPI_Datatype stype, void *rbuf,
int rcount, MPI_Datatype rtype,
int source, MPI_Comm comm)


Обратная к MPI_Gather функция. Процесс source рассылает порции данных из массива sbuf всем процессам группы, на которую указывает коммуникатор comm. Можно считать, что массив sbuf делится на n равных частей, состоящих из scount элементов типа stype, после чего i-я часть посылается i-му процессу. На процессе source существенным являются значений всех параметров, а на остальных процессах – только значения параметров rbuf, rcount, rtype, source и comm. Значения параметров source и comm должны быть одинаковыми у всех процессов.

Синхронизация MPI-процессов может быть выполнена с использованием блокирующих процедур приема/посылки сообщений или посредством функции, реализующей барьерную синхронизацию:

int MPI_Barrier(MPI_Comm comm)

MPI_Barrier блокирует работу процессов, вызвавших данную процедуру, до тех пор, пока все оставшиеся процессы группы comm также не выполнят эту процедуру.


Кратко рассмотрим некоторые языки, поддерживающие параллельноеь и распределенное программирование.

Язык Occam. Разработан в середине 80-х годов для программирования транспьютеров – многопроцессорных систем, образующих двумерную решетку (каждый процессор связан с четырьмя другими).

Базовые операции языка –

  • Присваивание пер := выражение

  • ввод (запросить) канал ? переменная

  • вывод (выдать) канал ! выражение



В программе также используются декларации – описания переменных, а также конструкторы.

Конструктор SEQ применяется для последовательного выполнения и PAR для параллельного. Есть конструкторы IF, CASE, WHILE.


INT x,y:

^ SEQ //PAR

x:=x+1

y:=y+1


CHANN OF BYTE comm. :

PAR

WHILE TRUE

BYTE ch :

SEQ

keyboard ? ch

comm ! ch

WHILE TRUE

BYTE ch :

SEQ

comm ? ch

display ! ch


Существует механизм условной блокировки ALT


Язык Java (Sun 1995 г). Java поддерживает потоки (класс Thread), разделяемые переменные, синхронизированные методы (выполняющиеся со взаимным исключением)

Библиотека Java поддерживает обмен сообщениями с помощью сокетов. Java поддерживает удаленный вызов методов RMI


Язык ADA. Разработан по заказу министерства обороны США в конце 70-х годов.

В языке есть понятие задача – независимый процесс внутри одной программы.

Для синхронизации используется механизм рандеву. Из одной задачи вызывается точка входа в другой задаче call T.E (аргументы)

Задача T обслуживает вызовы точки Е с помощью оператора accept

accept E(параметры) do

операторы

end;


Скачать файл (42.3 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации