Вторая версия (1158279), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

CDVM$ SHADOW B( d1:d2 )

В каждом параллельном цикле, где используются удаленные данные типа SHADOW массива B необходимо указать дополнительную спецификацию в директиве PARALLEL ON:

CDVM$ PARALLEL ( I ) ON A ( I ), SHADOW_RENEW ( B )

3.5.3Удаленные данные типа ACROSS

A(I)= A(I-d1) + A(I+d2)

Как в предыдущем разделе необходимо описать размер удаленных данных директивой:

CDVM$ SHADOW A( d1:d2 )

Но в директиве PARALLEL ON добавляется спецификация ACROSS:

CDVM$ PARALLEL ( I ) ON A ( I ), ACROSS ( A(d1:d2) )

Отличие данных типа ACROSS от данных типа SHADOW заключается в следующем: невозможно независимое выполнение витков цикла, т.к. прежде чем вычислить A(I), необходимо вычислить A(I-d1). В спецификации ACROSS перечисляются все распределенные массивы, по которым существует регулярная зависимость по данным.

3.5.4Удаленные данные типа REMOTE

A(I)= C(5) + C(I+N)

где C - распределенный массив.

В этом случае в директиве PARALLEL ON необходимо указать следующую спецификацию REMOTE_ACCESS:

CDVM$ PARALLEL ( I ) ON A ( I ), REMOTE_ACCESS ( C( 5 ), C( I+N ) )

3.5.5Удаленные данные типа REDUCTION

A(I) = B(I) + C(I)

S=S+A(I)

Для первого оператора необходимо локализовать данные как и в разделе 3.5.1. Для второго оператора необходимо указать в директиве PARALLEL ON спецификацию REDUCTION:

CDVM$ PARALLEL ( I ) ON A ( I ) , REDUCTION (SUM(S))

где SUM – имя редукционной операции суммирования,

S – редукционная переменная.

К редукционным операциям относятся: SUM, PRODUCT, AND, OR, MAX, MIN.

3.6Распределение вычислений внутри узла.

3.6.1Параллельная область

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

OpenMP-директива PARALLEL определяет параллельную область.

!$OMP PARALLEL

A(I) = B(I) + C(I)

D(I) = B(I) + C(I)

!$OMP END PARALLEL

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

3.6.2Размноженные по узлам данные

Как уже говорилось, в модели Fortran OpenMP/DVM все переменные можно разделить на два основных класса:

• распределенные, которые отображены по узлам, при помощи высокоуровневых директив распределения данных, и

• размноженные по узлам, которые отображаются по одному экземпляру на каждый узел.

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

В свою очередь размноженные по узлам данные внутри параллельной области можно разделить на:

• общие - под именем A все нити видят одну переменную и

• приватные - под именем A каждая нить видит свою переменную.

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

Общие переменные описываются при помощи спецификации SHARED:

!$OMP PARALLEL SHARED (B, C)

A = B + C

D = B + B

!$OMP END PARALLEL

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

Приватные переменные описываются при помощи спецификации PRIVATE:

!$OMP PARALLEL SHARED (B, C) PRIVATE (A, D)

A = B + C

D = B + B

!$OMP END PARALLEL

3.6.3Распределение витков цикла между нитями внутри узла. Директивы DO и PARALLEL DO

Если в параллельной области (определяемой парой директив PARALLEL/END PARALLEL) встретился оператор цикла, то, согласно общему правилу, он будет выполнен всеми нитями, т.е. каждая нить выполнит все итерации данного цикла. Для распределения итераций цикла между различными нитями используется директива DO:

REAL A(N, M), B(N, M+1), C(N, M), D(N, M)

!$OMP PARALLEL SHARED (A, B, D, C)

! . . .

!$OMP DO PRIVATE (I,J)

DO 10 I = 1, N

DO 10 J = 1, M-1

A(I,J) = D(I,J) + C(I,J)

B(I,J+1) = D(I,J) - C(I,J)

1. CONTINUE

По окончании выполнения витков цикла осуществляется барьерная синхронизация нитей, если не указана спецификация NOWAIT.

Если параллельная область состоит только из одного цикла, то такой цикл можно описать при помощи следующей директивы PARALLEL DO:

REAL A(N, M), B(N, M+1), C(N, M), D(N, M)

! . . .

!$OMP PARALLEL DO PRIVATE (I,J) SHARED (A, B, C, D)

DO 10 I = 1, N

DO 10 J = 1, M-1

A(I,J) = D(I,J) + C(I,J)

B(I,J+1) = D(I,J) - C(I,J)

10 CONTINUE

3.6.4Распределение витков распределенного параллельного цикла между нитями.

Витки распределенного параллельного цикла, специфицированного при помощи директивы PARALLEL ON, можно распределить между нитями, при помощи директив DO или PARALLEL DO.

REAL A(N, M), B(N, M+1), C(N, M), D(N, M)

CDVM$ ALIGN ( I, J ) WITH B( I, J+1 ) :: A, C, D

CDVM$ DISTRIBUTE B ( BLOCK , BLOCK )

. . .

CDVM$ PARALLEL ( I, J ) ON B( I, J+1 )

!$OMP DO

DO I = 1, N

DO J = 1, M-1

A(I,J) = D(I,J) + C(I,J)

B(I,J+1) = D(I,J) - C(I,J)

ENDDO

ENDDO

!$OMP ENDDO

В данном случае, витки тесно-гнездового цикла будут распределены между узлами, в соответствии с распределением массива B; и те витки цикла по I, которые будут выполняться на узле, будут распределены между нитями на этом узле.

Ограничения:

• В разделе 2 определен порядок вложенности уровней параллелизма в Fortran OpenMP/DVM программе. Согласно этого порядка, распределенные параллельные циклы не могут использоваться внутри OpenMP конструкций разделения работы. Поэтому, например, такая ситуация некорректна:

REAL A(N, N)

CDVM$ DISTRIBUTE B ( BLOCK , *)

. . .

!$OMP PARALLEL DO PRIVATE ( I, J ) SHARED ( A )

DO J = 1, N

CDVM$ PARALLEL ( I ) ON B( I, * )

DO I = 1, N

B(I,J) = 1.0

ENDDO

ENDDO

Ошибка - нарушен порядок вложенности уровней параллелизма.

3.6.5Работа с удаленными данными типа ACROSS внутри узла

Рассмотрим следующий цикл

DO J = 2, N-1

DO I = 2, N-1

A(I,J) = (A(I,J-1) + A(I,J+1) + A(I-1,J) + A(I+1,J)) / 4

ENDDO

ENDDO

Между витками цикла с индексами i1 и i2 ( i1<i2 ) существует зависимость по данным (информационная связь) массива A, если оба эти витка осуществляют обращение к одному элементу массива по схеме запись‑чтение или чтение‑запись.

Если виток i1 записывает значение, а виток i2 читает это значение, то между этими витками существует потоковая зависимость или просто зависимость i1 i2.

Если виток i1 читает “старое” значение, а виток i2 записывает “новое” значение, то между этими витками существует обратная зависимость i1 i2.

В обоих случаях виток i2 может выполняться только после витка i1.

Значение i2 - i1 называется диапазоном или длиной зависимости. Если для любого витка i существует зависимый виток i + d (d - константа), тогда зависимость называется регулярной или зависимостью с постоянной длиной.

Если массив A не распределен между узлами, тогда такой цикл с регулярными вычислениями можно распараллелить, используя средства OpenMP:

!$OMP PARALLEL, PRIVATE ( IAM, J, I, J1)

!$ IAM = OMP_GET_THREAD_NUM ( )

С IAM - номер нити

!$ OMP_GET_NUM_THREADS ( ) – количество нитей

DO J1 = 2, N-1 + OMP_GET_NUM_THREADS ( ) - 1

!$ J = J1 – IAM

!$OMP DO SCHEDULE (STATIC)

DO I = 2, N-1

!$ IF (J .LT. 2 .OR J .GT. N - 1) THEN

!$ CYCLE

!$ ENDIF

A( I, J ) = (A( I, J-1 ) + A( I, J+1 ) + A( I-1, J ) + A( I+1, J ))/4

ENDDO

!$OMP ENDDO

ENDDO

!$OMP END PARALLEL

Рассмотрим более подробно, как работает данный алгоритм. Все витки цикла по J выполняются всеми нитями, а витки цикла по I распределяются между ними при помощи OpenMP-директивы DO. В начальный момент времени начинает работать нить с номером 0 (нить0). Для нее значение J равно 2 и условие внутри цикла не выполняется. Нить0 вычисляет свою часть витков цикла по I. Все остальные нити (для них условие выполнено) дожидаются, пока нить0 посчитает свою часть массива A для J=2. Далее работают нить0 и нить1: нить0 вычисляет свою порцию витков цикла по I для J = 3, а нить1 - для J = 2. И так далее, последняя нить включится в работу через OMP_GET_NUM_THREADS ( ) - 1 шагов.

Пусть теперь массив A является распределенным между узлами. Тогда помимо синхронизации между нитями внутри узла, необходимо организовать выполнение витков данного цикла на узлах таким образом, чтобы для витков цикла с индексами i1 и i2 (i1<i2) виток i2 выполнялся бы только после витка i1 (витки i2 и i1 могут выполняться на разных узлах). Такой цикл с регулярными вычислениями, в котором существуют регулярные зависимости по распределенным массивам, можно распределять, указав спецификацию ACROSS после директивы PARALLEL ON.

!$OMP PARALLEL, PRIVATE ( IAM, NUMT, J, I, J1)

!$ IAM = OMP_GET_THREAD_NUM ( )

С IAM - номер нити

CDVM$ PARALLEL ( J1, I ) ON A( I, J1 - IAM ) , ACROSS ( A( 1:1, 1:1 ))

DO J1 = 2, N-1 + OMP_GET_NUM_THREADS () - 1

!$ J = J1 - IAM

!$OMP DO SCHEDULE (STATIC)

DO I = 2, N-1

!$ IF (J .LT. 2 .OR J .GT. N - 1) THEN

!$ CYCLE

!$ ENDIF

A( I, J ) = (A( I, J-1 ) + A( I, J+1 ) + A( I-1, J ) + A( I+1, J ))/4

ENDDO

!$OMP ENDDO

ENDDO

!$OMP END PARALLEL

По каждому измерению массива А существует прямая и обратная зависимость длиной 1.

3.6.6Работа с данными типа REDUCTION внутри узла

При использовании внутри параллельного цикла данных типа REDUCTION, необходимо описать их при помощи OpenMP-спецификаци REDUCTION:

S = 0

X = -1.

CDVM$ PARALLEL ( I ) ON A( I ), REDUCTION (SUM(S)), REDUCTION (MAX(X))

C$OMP DO REDUCTION (+:S) REDUCTION (MAX:X)

DO 10 I = 1, N

S = S + A(I)

X = MAX(X, A(I))

10 CONTINUE

В данном примере спецификация REDUCTION используется и в DVM, и в OpenMP-спецификации параллелизма. Информация о редукционных переменных дублируется, но это дает возможность скомпилировать эту программу и как OpenMP, и как DVM. Если опустить какую-то одну спецификацию REDUCTION, то программа станет работать неверно.

Вычисление значения редукционной операции, происходит в два этапа:

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

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

3.7Копирование секций массивов

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

Цикл копирования

Для того, чтобы DVM-программа могла компилироваться и выполняться как обычная последовательная программа, копирование массивов (секций) записывается как обычный многомерный цикл.

Характеристики

Список файлов книги