лекции по курсу параллельное прогр

Параллельное программирование.

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;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ВДИЗ ВДИЗ ВДИЗ Процессор без конвейера

ВДИЗ

ВДИЗ

ВДИЗ Процессор с конвейером.

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

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

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

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

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

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

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

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

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

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

Критические секции – исторически первый способ обеспечения синхронизации. Предложены Эдсгером Дейкстрой в 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, станет владельцем критического раздела, и его выполнение будет возобновлено.

Когда объект критический раздел больше не нужен программе, его можно удалить с помощью функции 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). Основное его отличие от критического раздела заключается в том, что последний можно использовать только в пределах одного процесса (одного запущенного приложения), а исключающими семафорами могут пользоваться разные процессы. Другими словами, критические разделы - это локальные объекты, которые доступны в рамках только одной программы, а исключающие семафоры могут быть глобальными объектами, позволяющими синхронизировать работу программ (т. е. разные запущенные приложения могут разделять одни и те же данные).

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

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

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

Параметры:

lpMutexAttributes - указатель на структуру SECURITY_ATTRIBUTES (в Windows 95

данный параметр игнорируется);

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

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

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);

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