Параллельная обработка данных В.А. Фисун 14.12.2000 Параллельные процессы СОДЕРЖАНИЕ 1. Классификация машин по Флинну: 1.1. Архитектура МКМД. 2. Синхронизация параллельных процессов 3. Семафоры 4. Проблема тупиков 5. Семафоры в Фортран программировании 6. Параллельное программирование для SIMD архитектуры 6.1. Конструктивный алгоритм реализации метода координат. 7. Метод гиперплоскостей 8. Метод параллелепипедов 1. Классификация машин по Флинну: Характеризует архитектуры по структуре потоков команд (Instruction) и данных (Data). - ОКОД одиночный поток команд, одиночный поток данных, - ОКМД одиночный поток команд, множественный поток данных, - МКОД множественный поток команд, одиночный поток данных, - МКМД множественный поток команд, множественный поток данных. Схематически можно эту классификацию изобразить: + -> ОКОД -> a+b + -> -> a+b а,b -> a,b -> ОКМД -> c+d c,d -> + -> -> a+b + -> -> a+b - -> МКОД -> a-b - -> МКМД -> c-d a,b -> a,b -> c,d -> Single Data Stream Mult. Data Stream ----------------------------------- Single In. Stream SISD SIMD фон Нейманн распаралл. данных ----------------------------------- Multiple In. Stream MISD MIMD конвейер функциональн.паралл. ----------------------------------- 1.1. Архитектура МКМД. Архитектура МКМД обеспечивает наибольший параллелизм работы: нес- колько процессоров работают асинхронно и обладают средствами взаимо- действия. В архитектуре МКМД различаются два варианта: - платформы с общей памятью, когда каждый процессорный элемент (ПЭ) имеет доступ не только к своей оперативной памяти (ОП), но и к памяти других ПЭ; - платформы с локальной памятью, когда каждый процессорный элемент имеет свою локальную память, доступ к которой из других ПЭ возможен только через процессор. Общая память Локальная память - 2 - ОП1 ОП2 ..... ОПn ------------------- ------------------- шина шина ------------------- ------------------- ПЭ1 ПЭ2 ..... ПЭn ПЭ1 ПЭ2 ..... ПЭn ОП1 ОП2 ..... ОПn Так как элементы архитектура МКМД есть в любой платформе, даже од- нопроцессорной ( устройства ввода-вывода обычно работают асинхронно), проблемы организации параллельной вычислительной работы затрагивают широкий круг проблем. Например: - на уровне прикладного пользователя, - на сетевом уровне,UNIX - на уровне оболочек, - на уровне ОС. 2. Синхронизация параллельных процессов "Процесс - группа ячеек памяти, содержимое которых меняется по определенным правилам. Эти правила описываются программой, которую ин- терпретирует процессор." /Цикритзис Д./. Процессы, работающие на равных правах (не вызовы процедур и не процессы, связанные понятиями "главная-подчиненная"), иногда называе- мые сопроцессами, могут выполняться параллельно и при этом общаться друг с другом - не часто (слабо связанные процессы). Процессы для своей работы могут использовать логические и физи- ческие ресурсы вычислительной системы и ее окружения, причем ресурсы могут быть: поделены между процессами и закреплены постоянно (на все время работы процесса) или использованы всеми или некоторыми процесса- ми по-очереди. Некоторые ресурсы могут быть общими и допускать парал- лельное обслуживание процессов. Ресурс, который допускает обслуживание только одного процесса в текущее время, называется критическим ресурсом. Участки программы процесса, в которых происходит обращение к кри- тическим ресурсам, называются критическими участками. Такие участки должны быть выполнены в режиме "взаимного исключения", т.е. в каждый момент времени не более чем один процесс может быть занят выполнением своего, критического относительно некоторого ресурса, участка. Пробле- ма критического участка - программирование работы критических участков в режиме взаимного исключения. - 3 - Нотация: Операторы Si в блоке: parbein S1;S2;S3,...Sn parend;SS могут вы- полняться параллельно, причем, выполнение оператора SS, следующего за блоком, начнется только после окончания работы всех Si. Цикл do while (true) S enddo предписывает выполнение тела цикла - S бесконечное чис- ло раз. СSi_i обозначает оператор (последовательность операторов) - критический участок относительно ресурса С. Постановка задачи: Два процесса : t1 и t2 в критических участках используют общий ресурс C. parbegin t1: do while (true) S1; CS2; Sn; enddo; t2: do while (true) S2_1; CS2_2; S2_n; enddo; parend Решения: блокировка памяти, операция "проверка-установка", семафоры. Блокировка памяти (тривиальное, но некорректное решение) begin boolean P1,P2; P1:=P2:= false; parbegin task1: do while (true) L1: do while (P2) enddo; P1:=true; CS1_1; P1:=false; S1; enddo; task2: do while (true) L2: do while (P1) enddo; P2:=true; CS2_2; P2:=false; S2; enddo; parend end Почему данное решение некорректно? Данное решение некорректное, так как, например,если второй про- - 4 - цесс работает быстрее первого, то первый определив, что Р2 - ложь и, начав работать, может не успеть скорректировать Р1 и второй процесс также может войти в критический участок. Или, если процессы начнут работать одновременно и с одинаковой скоростью, то для них условия, проверяемые циклами Li, будут одинаковы- ми, что приведет к некорректности. Алгоритм Деккера - Холта решает проблему корректно. begin integer P1,P2,Q; P1:=P2:=0; Q:=1; parbegin task1: begin P1:=1; do while (P2=1) IF Q=2 then begin P1:=0; do while (Q=2) enddo; P1:=1; end; enddo; CS1_1; P1:=0; Q:=2; S1_2; end; task2: begin P2:=1; do while (P1=1) IF Q=1 then begin P2:=0; do while (Q=1) enddo; P2:=1; end; enddo; CS2_1; P2:=0; Q:=1; S2_2; end; parend end При входе в do while (P2=1) какое может быть значение Q ? Зачем делается Р1=0 в условном операторе ? Взаимное исключение реализуются аппаратно, сделав опера- ции над памятью неделимыми, т.е. при засылке данного в одну и - 5 - ту же ячейку из разных процессов аппаратура заканчивает одну из операций и только затем обрабатывает другие запросы. Команда "проверка и установка" (test end set) Команда "проверка и установка" TS(L,Q), выполняется как неде- лимая операция: L=Q;Q=1; begin integer P1,P2,Q; Q=0; parbegin task1: do while (true) P1:=1; do while (P1=1); TS(Р1,Q); enddo; CS1i; Q:=0; S1k; enddo; task2: do while (true) P2:=1; do while (P2=1); TS(Р2,Q); enddo; CS2i; Q:=0; S2k; enddo; parend end Команду "test end set" можно записать в виде процедуры, выполня- емой как неделимая: Boolean procedure TS(X); Для защиты критической секции CS Boolean X; процедура TS : begin L:if TS(S) then go to L; TS:=X; CS; S:=false; X:=true end Предложите другие варианты аппаратной реализации проблемы крити- ческих участков. Например,TSB(X,L) -> if X then go to L else X:=true; Здесь, Q=1 означает, какой-то процесс находится в своем критичес- ком участке. - 6 - Недостатки данной схемы Прием (блокировка памяти) очень не-эффективен, из за активного ожидания - "жужжанием" на циклах вида: do while (P1=1) .... enddo;.Ал- горитм усложняется при увеличении числа процессов. Для ожидания работы в "спящем" состоянии предпочтительнее семафоры и механизмы управления пассивации и активизации процессов. 3. Семафоры Семафоры - переменные, изменять которые могут только Р и V опера- ции, выполняемые "неделимо". Общие семафоры Общий семафор - это целочисленная переменная, над которой разре- шены только две неделимые операции P и V. Аргументом у этих операций является семафор. Определять семантику этих операций можно только для семафоров - положительных чисел, или включать и отрицательный диапа- зон. Операции могут быть определены так: P(S) - декремент и анализ семафора S := S-1 IF (S < 0) THEN <блокировка текущего процесса> ENDIF - 7 - V(S) - инкремент семафора S := S+1 IF S <= 0 THEN <запустить блокированный процесс> ENDIF P и V операции неделимы: в каждый момент только один процесс мо- жет выполнять Р или V операцию над данным семафором. Если семафор используется как счетчик ресурсов, то: S >= 1 - есть некоторое количество (S) доступных ресурсов, S = 0 - нет доступного ресурса, S < 0 - один или несколько (S) процессов находятся в очереди к ресурсу. Вводится, текже, операция инициализации семафора (присвоение на- чального значения). Семафор, максимальное значение которого равно единице, называ- ются,иногда, двоичными (чистый двоичный принимает значения 0,1 или true,false) с максимальным значением, равным единице: 1,0,-1. Тогда, для двух процессов: 1 - ни один процесс не находится в своем критичес- ком участке, 0 - один процесс работает, -1 - один работает в критичес- ком участке и один находится в очереди. /Д. Цикриезис/ Действия двоичного семафора в терминах TS P(S) -> L: if TS(S) then go to L; V(S) -> S:=false; Общий семафор - избыточный, т.к. его можно реализовать через дво- ичные самафоры. Задание: Определить семантику P,V операций для семафора, принима- ющего только положительные знасения. Семафоры позволяют: - синхронизировать работу процессов, - управлять распределением ресурсом (использованием положительно- го диапазона значений семафора как счетчика ресурсов) , - организовывать очередь блокированных процессов (отрицательные значения семафора показывают число блокированных процессов). В системах программирования вводится специальный тип данных, оп- ределяющий структуру семафора, например, SEMAPHOR,SIGNAL,GETA. В Windows NT принята сдедующая иерархия семафоров: А. Критические секции, используемые только для синхронизации за- дач в рамках одного процесса. В. Объекты Mutex - семафоры, допускающие синхронизацию задач, созданные разными процессами. С. Объекты-семафоры обеспечивают доступ к ресурсу для заранее ог- раниченного количества задач. Семафоры типа А и В допускают 'рекурсивное использование', то есть внутри критической секции можно вызвать повторно Р операцию. Она не оказывает никакого влияния на совместную работу процессов, но при ос- вобождении ресурса следует вызвать соответствующее число V операций. Использование семафоров - 8 - begin integer S; S:=1; parbegin task1: begin do while (true) P(S); <критический участок 1>; V(S); <обычный участок>; enddo end; task2: begin do while (true) P(S); <критический участок 2>; V(S); <обычный участок>; enddo end parend end Задача: "поставщик - потребитель". Поставщик производит порцию,например, - образ ПК, например, и размеща- ет ее на буфере, а потребитель - берет ее из буфера и обрабатывает - перфорирует. К - число порций в буфере. begin integer K; K:=0; parbegin поставщик: begin L1:<производство новой порции>; <добавление порции к буферу>; * разбудить L2 V(K); goto L1; end; потребитель: begin * ждать сигнала от L1 L2: P(K); <взятие порции из буфера>; <обработка взятой порции>; goto L2 end; - 9 - parend end Для выполнения в режиме "взаимного исключения" операций: "добав- ления порции к буферу" и "взятию порции с буфера" - вариант:КК - новый семафор - работа с буфером, = 0, если идет работа с буфером и КК =1, если нет работы. begin integer K,КК;КК:=1; K:=0; parbegin производитель: begin L1:<производство новой порции>; Р(КК); <добавление порции к буферу>; V(KK); V(K); goto L1; end; потребитель: begin L2: P(K); P(KK); <взятие порции из буфера>; V(KK); <обработка взятой порции>; goto L2; end; parend end Существенен ли порядок двух V операций в производителе ? (нет) Существенен ли порядок двух Р операций в потребителе ? (да), так как потребитель должен убедиться проверкой Р(К), что есть хотя бы одна порция на буфере, прежде чем начинать ее обработ- ку.Модифицировать программу для двух производителей. 4. Проблема тупиков (The Deadly Embrace) При использовании семафоров порядок P и V операций существенен, так как могут быть тупиковые ситуации при выполнении. Пусть S1,S2 двоичные семафоры с начальными значениями = 1. И если в двух параллельных процессах будут выполняться: P1: P(S1);P(S2); P2: P(S2);P(S1); то процессы будут ждать друг друга неопределенно долго -тупик. Алгоритм предотвращения тупиковых ситуаций - 10 - Пусть процессы А,В,С заявили максимальное потребность в ресурсах (например,лентопротяжек), а их всего в системе 10, и запрашивают их динамически. Тогда возможны ситуации: Имя Мах процесса потребность Выделено Остаток ------------------------------------------------------------------- А 4 2 2 Безопасное В 6 3 3 состояние С 8 2 6 -------------------------------------------------------------------- А 4 2 2 Опасное состояние, В 6 3 3 после того, как С С 8 4 4 запросило еще 2 -------------------------------------------------------------------- "Алгоритм банкира" для проверки корректности запроса. СВОБ_УСТР:= ОБЩ_УСТР; for i:= 1 step 1 until N do begin СВОБ_УСТР:= СВОБ_УСТР - ВЫДЕЛ_УСТР[i]; МОЖЕТ_НЕ_КОНЧИТЬ[i]:= true; ОСТАТОК[i]:= МАКС[i] - ВЫДЕЛ_УСТР[i]; end; ПРИЗНАК := true; do while (ПРИЗНАК) ПРИЗНАК:= false; for i:= 1 step 1 until N do begin if МОЖЕТ_НЕ_КОНЧИТЬ[i] and ОСТАТОК[i]<=СВОБ_УСТР then begin МОЖЕТ_НЕ_КОНЧИТЬ[i]:= false; СВОБ_УСТР:=СВОБ_УСТР + ВЫДЕЛ_УСТР[i]; ПРИЗНАК:=true; end end end do for; end do while; if СВОБ_УСТР = ОБЩ_УСТР then состояние системы безопасное else состояние системы опасное; - 11 - Постановка задачи в банковской терминологии. Банкир обладает известным капиталом и выдает заем клиентам на слежующих условиях: 1. Клиент делает заем (возможно постепенно), который будет непре- менно возвращен со временем. 2. Клиент задает максимальную потребность во флоринах, в рамках которой он может увеличивать или уменьшать свой заем. 3. Клиент согласен на отказ в получении очередного заема (даже при наличии у него лимита по максимальонй потребности) в момент запро- са с тем, чтобы получить удовлентворение позже. Проблемы банкира: 1. На каких условиях можно заключить контракт с новым клиентом ? 2. При каких условиях банкир может удовлетворить очередной запрос клиента ? 5. Семафоры в Фортран программировании Иногда, почти полностью распараллеливающийся по данным, алгоритм имеет единственную зависимость данных, которая на векторных машинах может потребовать расщепления цикла, чтобы изолировать зависимость. Например: DO I = 1,N A(I) = EXP(SIN(B(I))) * EXP(COS(B(I))) C(I) = (D(I) + E(I)) / F(I) * A(I) X(I) = S * X(I-1) + C(I) Z(I) = X(I) * Y(I) + EXP(Z(I)) ENDDO Оператор присваивания X(I) включает рекурсию, что запрещает век- торизацию. Обычно либо компилятор, либо программист выделит этот опе- ратор в отдельный скалярный цикл, чтобы позволить другим трем операто- рам присваивания выполняться в параллельном режиме. Это не всегда необходимо делать при распараллеливании. Если име- ется достаточно работы выше и/или ниже оператора присваивания X(I) и N достаточно велико, можно достичь эффективного параллельного выполнения цикла путем помещения оператора присваивания X(I) в упорядоченную кри- тическую секцию. Она будет обеспечивать доступ только одной нити в один и тот же момент явным или неявным замковым (lock) механизмом. В данном случае требуется выполнять итерации в таком порядке, чтобы - 12 - удовлетворить требования рекурcии для вычисления X. Реальный система синхронизации для SEQ CALL SETSEQ (SEQ,0) * инициализация, установка SEQ=0 С$DIR DO_PARALLEL (ORDRED) DO I = 1,N A(I) = EXP(SIN(B(I))) * EXP(COS(B(I))) C(I) = (D(I) + E(I)) / F(I) * A(I) CALL WAITSEQ (SEQ,I-1) * ждать, пока SEQ будет равно I-1 X(I) = S * X(I-1) + C(I) CALL POSTSEQ (SEQ,I) * установить SEQ в I Z(I) = X(I) * Y(I) + EXP(Z(I)) ENDDO Семантика (для случая четырех процессоров): * Инициализируются вычисления первых четырех итераций в заданном порядке на четырех параллельных процессорах. * Все четыре процессора вычисляют свои A(I),C(I) одновре- менно. * Первый процессор выполнит для I=1 присваивание X(1), в то время как другие ждут. * Первый процессор для I=1 вычисляет Z(1), в то время как X(2) вычисляется вторым процессором для I=2. * Первый процессор начинает вычислять новую итерацию для I=5, в то время как другие три процессора проходят сквозь кри- тическую секцию также упорядочено. Теперь, если работа по выполнению цикла хорошо сбалансирова- на,первый процессор для I=5 достигает точки WAITSEQ как раз тогда, когда четвертый процессор для I=4 закончит POSTSEQ. С этой точки все процессоры работают без простоя, пока они не достигнут последние четы- ре итерации цикла. Библиотеки синхронизации системы программирования поддерживают критические секции, замки, события и последовательности. 6. Параллельное программирование для SIMD архитектуры Одним из методов распараллеливания программ является метод коор- - 13 - динат, обеспечивающий векторизацию циклов для синхронных ЭВМ (ОКМД - SIMD архитектуры). Семантика синхронных циклов следующая: для каждой итерации цикла назначается процессор; вычисления должны производиться всеми процессорами (процессорными элементами) параллельно и синхронно. Операторы тела цикла выполняются по очереди, но каждый оператор выпол- няется всеми процессорами одновременно. При выполнении оператора прис- ваивания сначала вычисляется правая часть, затем одновременно выполня- ется операция присваивания для всех элементов массива левой части. Теоретическое обоснование классического метода координат предло- жено Лэмпортом. Метод применим для канонических ("чистых") циклов, те- ла которых состоят только из операторов присваивания, причем управляю- щая переменная заголовка цикла (параметр цикла) должна входить в ин- дексные выражения операторов тела цикла линейно. Метод предназначен для синхронной векторизации одномерных циклов (многомерные циклы можно рассматривать по каждому параметру отдельно). Идея данного метода сос- тоит в том, что для индексов, содержащих параметры цикла, рассматрива- ется порядок следования, который и определяет очередность выборки/за- писи соответствующего элемента массива. Так как рассматриваются только линейные индексные выражения, порядок следования определяется значени- ями соответствующих алгебраических выражений. Строится граф характе- ристических множеств всех индексов, и при отсутствии в графе петель делается заключение о возможности векторизации всего цикла. В некоторых случаях (устранимая векторная зависимость) векториза- ция возможна лишь в случае переупорядочивания - перестановки операто- ров цикла или путем введения временной переменной (массива), куда бу- дут копироваться элементы вектора для защиты перед их изменением для последующего использования в исходном виде. Итак, метод координат: - позволяет определить возможность выполнения цикла в синхронном режиме; - содержит алгоритмы преобразования тела цикла к синхронному ви- ду. Например, по Лэмпорту, цикл: DO 24 I=2,M DO 24 J=2,N 21 A(I,J) = B(I,J)+C(I) 22 C(I) = B(I-1,J) 23 B(I,J) = A(I+1,J) ** 2 24 CONTINUE преобразуется в цикл: - 14 - DO 24 J=2,N DO 24 SIM FOR ALL I {i:2<=i<=M} C SIM - SI Multeneusly (одновременно) TEMP(I) = A(I+1,J) 21 A(I,J) = B(I,J)+C(I) 23 B(I,J) = TEMP(I) ** 2 22 C(I) = B(I-1,J) 24 CONTINUE 6.1. Конструктивный алгоритм реализации метода координат. Пусть, цикл одномерный, все операторы тела - операторы приваива- ния, в левых частях которых - переменные с индексом - параметром цик- ла. Индексы линейные, т.е. имеют вид i+/-b,где b - константа. Опреде- ляются отношения следования для всех пар одноименных переменных с ин- дексами: генерируемых переменных (переменные в левой части операторов присваивания -f) и используемых переменных (входящих в формулы правых частей - q). Отношение следования для одной пары зависит от порядка обращения к одному и тому же элементу массива при выполнении цикла. Так, для A(I) = A(I+1) отношение можно кодировать: f, <) в позиции соответствующего индекса, которая определяется порядком индексов в гнезде цикла. В при- мере Лемпорта (исходном) для А вектор имеет вид: (<,=). Для тела цикла, состоящего из одного оператора, отношения, и со- ответственно, семантика выполнения, могут быть: < > = и их сочетание. Например, тело цикла: A(I) = (А(I)+A(I+1))/2 допускает векторное вы- полнение; оно невозможно при наличии в операторе хотя бы одного соот- ношения: f>q. Для тела цикла: A(I) = A(I+C))/2 при С>0 возможно синх- ронное выполнение, при С=0 кроме синхронного, возможно параллельное асинхронное; а при С<0 параллельное выполнение невозможно. Для многомерных (тесногнездовых) циклов такое исследование может проводиться для каждого параметра, а для распараллеливания выбираться наиболее оптимальный вариант. Для самого внутреннего цикла определение следования можно проводить, считая его одномерным. Для любого другого цикла, исследование можно проводить по такой же схеме, если семантика цикла допускает перестановку его на позицию самого внутреннего. Перес- тановка допустима, если для всех новых направляющих векторов крайне левый, отличный от = , элемент сохранил направление. Например, для - 15 - двумерного цикла, наличие вектора (<,>) делает перестановку некоррект- ной. Так для цикла: DO 99 J=2,M DO 99 K=2,M 99 U(J,K) = (U(J+1,K)+U(J,K+1)+U(J-1,K)+U(J,K-1)) .25 направляющие вектора: 1 = (<,=) 2 = (=,<) 3 = (>,=) 2 = (=,>) Отсюда: - операторы циклов по I и J можно менять местами, - часть оператора, включающая вхождения из векторов 1 и 2, можно вынести в отдельный оператор, который векторизуется как по I так и по J. Для двух операторов тела цикла отношения следования переменных с индексами можно систематизировать и кодировать так (qi в общем случае, список - информационные поля q и f) : А - независимые отношения В - (qi>qj) , C - (qi - порядок анализа отношений *--------------------------------------------------------------------- * . O2 -> I1 . * . A . B . K . C . G . H . * . HEЗАВ. . O > I . O = I . O < I . O <=>I * . * I2 -> O1 . . . . . . . *---------------------------------------------------------------------- * . . . . . . . * A HEЗАВ. . P . R . S . M . R(K,C). T . *______________________________________________________________________ * . . . . . . . * B I > O . R . R . M(B) . M(B) . R(K,C). T . - 16 - *______________________________________________________________________ * . . . . . . . * K I = O . S . T . S . M . T . T . *______________________________________________________________________ * . . . . . . . * C I < O . M . T . M . M . T . T . *______________________________________________________________________ * . . . . . . . * G I <=> O. M(B) . T . M(B) . M(B) . T . T . *______________________________________________________________________ * . . . . . . . * H * . T . T . T . T . T . T . *______________________________________________________________________ * Кодировка отношений следования * А - независимые отношения * В - (qi>qj) , C - (qi, 1998.-240 с. Воеводин В.В. Математические модели и методы в параллельных процес- сах.-М.: Наука. 1986.-296 с. Э, А. Трахтенгерц. Введение в теорию анализа и распараллеливания прог- рамм ЭВМ в процессе трансляции. -М.: Наука,1981.-254с. Распараллеливание алгоритмов обработки информации. Том 1. -Киев: На- ук.думка, 1985.-280 с. Доклады В.В. Воеводина, Вл.В. Воеводина, А.В. Забродина на Всесоюзной молодежной школе "Суперкомпьютерные вычислительно-информационные тех- нологии в физических и химических исследованиях" 1999 г. Черноголовка - http://parallel.ru:81/info/education/chg99.html 1. В.В. Корнеев. Параллельные вычилительные системы.-М. <Нолидж>, 1999.-320с. 2. Б.А.Головкин. Вычислительные системы с большим числом процессо- ров.-М.: Радио и связь, 1995.-320с. 3. М. Амамия, Ю.Танака. Архитектура ЭВМ и искусственный интеллект: Пер. с японск. - Мир, 1993. 400с. 4. Языки и параллельные ЭВМ. Сб.>Алгоритмы и алгоритмические языки>, М.: Наука, 1990. 5. Р.Хокни, К.Джасхоуп. Параллельные ЭВМ. М.: Радио и связь. 1986. 6. http://parallel.ru:81