Параллельная обработка данных: параллельные процессы

Параллельная обработка данных
В.А. Фисун 14.12.2000

Параллельные процессы
СОДЕРЖАНИЕ


1. Классификация  машин  по Флинну

   1.1. Архитектура МКМД.

2. Синхронизация параллельных процессов

3. Семафоры

4. Проблема тупиков

5. Семафоры в Фортран программировании

6. Параллельное программирование для SIMD архитектуры

  6.1. Конструктивный алгоритм реализации метода координат.

7. Метод гиперплоскостей

8. Метод параллелепипедов

1. Классификация машин по Флинну
Характеризует архитектуры по структуре потоков команд (Instruction) и данных (Data).

ОКОД одиночный поток команд, одиночный поток данных
ОКМД одиночный поток команд, множественный поток данных
МКОД множественный поток команд, одиночный поток данных
МКМД множественный поток команд, множественный поток данных

Схематически можно эту классификацию изобразить:

+ -> а,b ->	ОКОД	-> a+b		+ -> a,b -> c,d ->	ОКМД	-> a+b -> c+d
+ -> - -> a,b ->	МКОД	-> a+b -> a-b		+ -> - -> a,b -> c,d ->	МКМД	-> a+b	-> c-d

	Single Data Stream	Multiple Data Stream
Single Instruction Stream	SISD фон Нейман	SIMD распараллел. по данным
Multiple Instruction Stream	MISD конвейер	MIMD функциональный параллелизм

1.1. Архитектура МКМД.
Архитектура МКМД обеспечивает наибольший параллелизм работы: несколько процессоров работают асинхронно и обладают средствами взаимодействия. В архитектуре МКМД различаются два варианта:

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

Общая память

Локальная память

ОП₁	ОП₂	.....	ОП_n
шина
ПЭ₁	ПЭ₂	.....	ПЭ_n

шина
ПЭ₁ ОП₁	ПЭ₂ ОП₂	..... .....	ПЭ_n ОП_n

Так как элементы архитектура МКМД есть в любой платформе, даже однопроцессорной ( устройства ввода-вывода обычно работают асинхронно), проблемы организации параллельной вычислительной работы затрагивают широкий круг проблем. Например:

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

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

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

Команда "проверка и установка" (test and 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 and 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 означает, какой-то процесс находится в своем критическом участке.
Недостатки данной схемы
Прием (блокировка памяти) очень не-эффективен, из за активного ожидания - "жужжанием" на циклах вида: do while (P1=1) .... enddo;. Алгоритм усложняется при увеличении числа процессов. Для ожидания работы в "спящем" состоянии предпочтительнее семафоры и механизмы управления пассивации и активизации процессов.

3. Семафоры
Семафоры - переменные, изменять которые могут только Р и V операции, выполняемые "неделимо".

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

P(S) - декремент и анализ семафора
S := S-1
IF (S < 0) THEN <блокировка текущего процесса>
ENDIF
V(S) - инкремент семафора S := S+1
IF S <= 0 THEN <запустить блокированный процесс>
ENDIF

P и V операции неделимы: в каждый момент только один процесс может выполнять Р или V операцию над данным семафором.
Если семафор используется как счетчик ресурсов, то:

S >= 1 - есть некоторое количество (S) доступных ресурсов,
S = 0 - нет доступного ресурса,
S < 0 - один или несколько (S) процессов находятся в очереди к ресурсу.

Вводится, тaкже, операция инициализации семафора (присвоение начального значения).
Семафор, максимальное значение которого равно единице, называются,иногда, двоичными (чистый двоичный принимает значения 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 операций.
Использование семафоров

     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;

     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, и запрашивают их динамически.
Тогда возможны ситуации:

Имя процесса	Мах потребность	Выделено	Остаток

А	4	2	2	Безопасное состояние
В	6	3	3
С	8	2	6

А	4	2	2	Опасное состояние, после того, как С запросило еще 2
В	6	3	3
С	8	4	4

"Алгоритм банкира" для проверки корректности запроса.

     СВОБ_УСТР:= ОБЩ_УСТР;
     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 состояние системы опасное;

Постановка задачи в банковской терминологии.
Банкир обладает известным капиталом и выдает заем клиентам на следующих условиях:

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

Проблемы банкира:

На каких условиях можно заключить контракт с новым клиентом ?
При каких условиях банкир может удовлетворить очередной запрос клиента ?

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

преобразуется в цикл:

      DO 24 J=2,N
      DO 24  SIM FOR ALL I {i:2<=i<=M}
C  SIM - SIMulteneusly (одновременно)
      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<q . Для многомерных циклов для всех пар (f,q) определяются направляющие вектора, элементы которых состоят из символов (=, >, <) в позиции соответствующего индекса, которая определяется порядком индексов в гнезде цикла. В примере Лампорта (исходном) для А вектор имеет вид: (<,=).
Для тела цикла, состоящего из одного оператора, отношения, и соответственно, семантика выполнения, могут быть: < > = и их сочетание. Например, тело цикла: A(I) = (А(I)+A(I+1))/2 допускает векторное выполнение; оно невозможно при наличии в операторе хотя бы одного соотношения: f>q. Для тела цикла: A(I) = A(I+C))/2 при С>0 возможно синхронное выполнение, при С=0 кроме синхронного, возможно параллельное асинхронное; а при С<0 параллельное выполнение невозможно.
Для многомерных (тесногнездовых) циклов такое исследование может проводиться для каждого параметра, а для распараллеливания выбираться наиболее оптимальный вариант. Для самого внутреннего цикла определение следования можно проводить, считая его одномерным. Для любого другого цикла, исследование можно проводить по такой же схеме, если семантика цикла допускает перестановку его на позицию самого внутреннего. Перестановка допустима, если для всех новых направляющих векторов крайне левый, отличный от = , элемент сохранил направление. Например, для двумерного цикла, наличие вектора (<,>) делает перестановку некорректной. Так для цикла:

     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

направляющие вектора:

<U(J,K),U(J+1,K)> = (<,=)
<U(J,K),U(J,K+1)> = (=,<)
<U(J,K),U(J-1,K)> = (>,=)
<U(J,K),U(J,K-1)> = (=,>)

Отсюда:

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

Для двух операторов тела цикла отношения следования переменных с индексами можно систематизировать и кодировать так (qi в общем случае, список - информационные поля q и f) : А - независимые отношения В - (qi>qj) , C - (qi<qj) , K - (qi=qj) G - B+K,B+C,B+K+C , Н - неоднозначные отношения. Тогда по координатам приводимой ниже таблице можно определить типы связей и метод выполнения цикла для этих операторов. Если объединить информационные поля двух операторов , то таблицу можно использовать для анализа третьего оператора и т.д.
Таблица решений для метода координат
Оператор 1 O1 = I1 O_i,I_i - список переменных с индексами
Оператор 2 O2 = I2 -> - порядок анализа отношений

I2 -> O1	O2 -> I1
I2 -> O1	A HEЗАВ.	B O > I	K O = I	C O < I	G O <=>I	H *
A HEЗАВ.	P	R	S	M	R(K,C)	T
B I > O	R	R	M(B)	M(B)	R(K,C)	T
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<qj) , K - (qi=qj)
G - B+K,B+C,B+K+C
Н - неоднозначные отношения

TИПЫ CBЯЗEЙ

P - независимые операторы
M - SIMD , M(EA) - SIMD с защитой EA
R - SIMD с реверсом, R(EA) - и с защитой EA
S - PAR (асинхронная параллельность)
T - запрет векторизации

Защита ЕА - копирование массивов ЕА перед ???
В общем случае, алгоритм векторизации методом координат с использования данной таблицы следующий.
Обработка тела цикла начинается с анализа на возможность векторного выполнения каждого оператора тела в отдельности. Затем к первому оператору добавляется второй и проводится анализ на возможную их векторизацию. Пара получает тип, определяющий возможность векторизации ее компонент, информационные поля операторов сливаются, и на следующем шаге применения процедуры векторизации пара рассматривается как единый супероператор. Таким образом из всех операторов тела цикла образуется один супероператор и, если его тип есть Т, то векторизация тела цикла невозможна. Для всех других типов производится обратный анализ полученного графа (супероператора). Если при этом связки имели тип R или R(EA),M(EA), то хотя они и допускают асинхронное параллельное выполнение, но необходимы преобразование тела цикла. Связки типа Т дают операторы, векторизация которых невозможна. Интерпретация остальных типов связок очевидна. В процессе формирования супероператоров к связкам типа Т могут применяться процедуры поиска минимальных границ области типа Т и чистки области Т.

Примеры векторизации
Исходные тела циклов	Преобразованные тела циклов
A(I) = B(I) C(I) = A(I+1)	C(I) = A(I+1) A(I) = B(I)
A(I) = B(I) C(I) = A(I) + A(I+1)	D(I) = A(I) A(I) = B(I) C(I) = A(I) + D(I+1)
A(I) = B(I) + B(I+1) B(I) = A(I+1)	D(I) = B(I) B(I) = A(I+1) A(I) = D(I) + B(I+1)
A(I) = B(I) + B(I-1) B(I) = A(I)	Векторизация невозможна

7. Метод гиперплоскостей
Метод гиперплоскостей применим только к многомерным циклам. В пространстве итераций ищется прямая (плоскость), на которой возможно параллельное асинхронное выполнение тела цикла, причем в отличие от метода координат, эта прямая (плоскость) может иметь наклон по отношению к осям координат. Цикл вида:

              DO 5  I = 2,N
              DO 5  J = 2,M
           5  A(I,J) = ( A(I-1,J) + A(I,J-1) ) * 0.5

методом координат не векторизуется. Действительно, при фиксированном значении переменной I (I = i) значение, вычисленное в точке (i,j) пространства итераций, зависит от результата вычислений в предыдущей точке (i,j-1), так что параллельное выполнение тела цикла по переменной J невозможно. Аналогично нельзя проводить параллельные вычисления по переменной I.
Однако можно заметить, что результат будет также правильным, если вычисления проводить в следующем порядке:
на 1-м шаге - в точке (2,2),
на 2-м шаге - в точках (3,2) и (2,3),
на 3-м шаге - в точках (4,2), (3,3) и (2,4),
на 4-м шаге - в точках (5,2), (4,3), (3,4) и (2,5)
и т.д.
Вычисления в указанных точках для каждого шага, начиная со второго, можно проводить параллельно и асинхронно. Перечисленные кортежи точек лежат на параллельных прямых вида I+J=K, а именно: на первом шаге - на прямой I+J=4, на втором - I+J=5, на третьем шаге - I+J=6 и т.д., на последнем ((N-2)+(M-2)+1) - ом шаге - на прямой I+J=M+N.
В общем случае для n-мерного тесногнездового цикла ищется семейство параллельных гиперплоскостей в n-мерном пространстве итераций, таких что во всех точках каждой из этих гиперплоскостей возможно параллельное выполнение тела цикла.
Для приведенного примера множество точек, в которых возможно параллельное выполнение, является однопараметрическим (прямая) и определяется из решения уравнения I+J=K.
Цикл (5) может быть преобразован к виду:

	   DO 5  K = 4,M+N
              Tн = MMAX(2,K-N)
              Tк = MMIN(M,K-2)
              DO 5  T = Tн,Tк : PAR
              I = T
              J = K - T
           5  A(I,J) = ( A(I-1,J) + A(I,J-1) ) * 0.5

Функция MMAX(X,Y) выбирает ближайшее целое, большее или равное максимуму из чисел X и Y, а функция MMIN(X,Y) - ближайшее целое, меньшее или равное минимуму из X и Y.
Внутренний цикл по переменной T может выполняться параллельно для всех значений T. Границы изменения переменной цикла T меняются при переходе с одной прямой (гиперплоскости) на другую, поэтому их необходимо перевычислять во внешнем цикле. Число итераций внутреннего цикла, то есть потенциальная длина векторной операции, меняется с изменением K. Для приведенного примера диапазон изменения T сначала возрастает, а потом убывает, причем для начального и конечного значения K он равен единице. В некоторых случаях для отдельных значений K накладные расходы на организацию векторного вычисления могут превысить эффект ускорения от векторного выполнения.
Вопрос оценки целесообразности проведения векторизации данным методом должен рассматриваться для каждого конкретного случая отдельно.

8. Метод параллелепипедов
Идея метода заключается в выявлении зависимых итераций цикла и объединении их в последовательности - ветви, которые могут быть выполнены независимо друг от друга. При этом в пространстве итераций определяются области (параллелепипеды), все точки которых принадлежат разным ветвям. Задача максимального распараллеливания заключается в поиске параллелепипеда наибольшего объема; тогда исходный цикл выполняется наибольшим числом параллельных ветвей, каждая из которых представляет собой исходный цикл, но с другим шагом изменения индекса. Для исходного цикла:

              DO 7  I = 1,7
              DO 7  J = 1,3
           7  X(I,J)  = X(I-2,J-1)

параллельное представление в виде:

              DO 7  (K,L) = (1,1) (P1,P2)  : PAR
              DO 7  I = K,7,P1
              DO 7  J = L,3,P2
           7  X(I,J)  = X(I-2,J-1)

допускается для различных разбиений пространства итераций: пара (P1,P2) может иметь, например, значения (2,1), (2,3) или (7,1). Таким образом, исходный цикл (7) преобразуется в последовательность параллельных ветвей, имеющих циклический вид.
В общем виде задача, рассматриваемая методом параллелепипедов, для одномерных циклов состоит в определении возможности представления цикла:

           DO L  I = 1,r
           L  T(I)

(где T(i) - тело цикла) в виде следующей языковой конструкции:

              DO L  K = 1,p  : PAR
              DO L  I = K,r,p
           L  T(I)

Литература:

Parallel Virtual Machine, Users Guide, Release 3.1, May 21, 1993

Дийкстра Э. Взаимодействие последовательных процессов.Сб. Языки программирования. Пер. с анг. Москва, Мир, 1972, 405 с.

Цикритзис Д., Бернстайн Ф. Операционные системы. Москва,Мир, 1977, 333 с.

Хоар Ч. Взаимодействующие последовательные процессы.Москва, Мир,1989

Шоу А. Логическое проектирование операционных систем. М.:Мир,1981.-360 с.

В.В. Корнеев, А.В. Киселев. Современные микропроцессоры.-М. <Нолидж>, 1998.-240 с.

Воеводин В.В. Математические модели и методы в параллельных процессах.-М.: Наука. 1986.-296 с.

Э. А. Трахтенгерц. Введение в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции. -М.: Наука,1981.-254с.

Распараллеливание алгоритмов обработки информации. Том 1. -Киев: Наук.думка, 1985.-280 с.

Доклады В.В. Воеводина, Вл.В. Воеводина, А.В. Забродина на Всесоюзной молодежной школе "Суперкомпьютерные вычислительно-информационные технологии в физических и химических исследованиях" 1999 г. Черноголовка

http://parallel.ru:81/info/education/chg99.html
В.В. Корнеев. Параллельные вычислительные системы.-М. <Нолидж>, 1999.-320с.
Б.А.Головкин. Вычислительные системы с большим числом процессоров.-М.: Радио и связь, 1995.-320с.
М. Амамия, Ю.Танака. Архитектура ЭВМ и искусственный интеллект: Пер. с японск. - Мир, 1993. 400с.
Языки и параллельные ЭВМ. Сб."Алгоритмы и алгоритмические языки", М.: Наука, 1990.
Р.Хокни, К.Джасхоуп. Параллельные ЭВМ. М.: Радио и связь. 1986.
http://parallel.ru:81