Модели параллельного программирования (стр. 4 )

С выравнивание вектора на вектор с реверсом

CDVM$ ALIGN G( I ) WITH D( - I + 21)

С выравнивание матрицы на матрицу с поворотом и раздвижкой

CDVM$ ALIGN H( I, J ) WITH C( 2*J, 2*I )

Несколько массивов (A1, A2,…) можно выровнять одинаковым образом на один и тот же массив B одной директивой вида

CDVM$ ALIGN (d1,…,dn) WITH B(ard1,…,ardm) :: A1, A2, …

При этом массивы A1, A2… должны иметь одинаковое число измерений (n), но необязательно одинаковые размеры измерений.

Пусть задана цепочка выравниваний A f1 B f2 C, где f2 - выравнивание массива В на массив С , а f1 - выравнивание массива А на массив В. По определению массивы А и В считаются выровненными на массив С. Массив В выровнен непосредственно функцией f2, а массив А выровнен опосредовано составной функцией f1(f2). Поэтому применение директивы REALIGN к массиву В не вызовет перераспределения массива А.

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

4.3.2. Директива TEMPLATE

Если значения линейной функции a*I + b выходят за пределы измерения базового массива, то необходимо определить фиктивный массив - шаблон выравнивания следующей директивой:

template-directive

is TEMPLATE template-decl-list

template-decl

is template-name [ ( explicit-shape-spec-list ) ]

Затем необходимо произвести выравнивание обоих массивов на этот шаблон. Шаблон распределяется с помощью директив DISTRIBUTE и REDISTRIBUTE. Элементы шаблона не требуют памяти, они указывают процессор, на который должны быть распределены элементы выровненных массивов.

Рассмотрим следующий пример.

Пример 4.9. Выравнивание по шаблону.

REAL A(100), B(100), C(100)

CDVM$ TEMPLATE TABC (102)

CDVM$ ALIGN B( I ) WITH TABC( I )

CDVM$ ALIGN A( I ) WITH TABC( I + 1 )

CDVM$ ALIGN C( I ) WITH TABC( I + 2 )

CDVM$ DISTRIBUTE TABC ( BLOCK )

. . .

DO 10 I = 2, 98

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

10 CONTINUE

Для того, чтобы не было обмена между процессорами необходимо разместить элементы A(I), C(I-1) и B(I+1) на одном процессоре. Выравнивание массивов С и В на массив А невозможно, т. к. функции выравнивания I-1 и I+1 выводят за пределы индексов измерения А. Поэтому описывается шаблон TABC. На один элемент шаблона TABC выравниваются элементы массивов A, В и С, которые должны быть размещены на одном процессоре.

4.3.3. Выравнивание динамических массивов

Для спецификации выравнивания динамических массивов синтаксис директив ALIGN и REALIGN расширен следующим образом.

alignee	is. . .
	or pointer-name

align-target	is. . .
	or pointer-name

Если в директиве ALIGN в качестве выравниваемого массива (alignee) указана переменная с атрибутом POINTER, то выполнение директивы откладывается до выполнения функции ALLOCATE, которая определяет значение этой переменной. Директива REALIGN может выполняться только после выполнения функции ALLOCATE.

Пример 4.10. Выравнивание динамических массивов.

REAL HEAP(100000)

CDVM$ REAL, POINTER ( :, : ) :: PX, PY

INTEGER PX, PY, DESC(2)

CDVM$ ALIGN PY( I, J ) WITH PX( I, J )

CDVM$ DISTRIBUTE PX ( BLOCK, BLOCK )

. . .

PX = ALLOCATE(DESC, ...)

PY = ALLOCATE(DESC, ...)

. . .

CDVM$ REDISTRIBUTE PX ( BLOCK, * )

Пусть задана цепочка выравниваний директивами ALIGN

P1 f1 P2 f2 . . . fN-1 PN

где fi - функция выравнивания,

Pi - указатель на динамический массив.

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

PN = ALLOCATE(...)

. . .

P2 = ALLOCATE(...)

P1 = ALLOCATE(...)

Если указатель динамического массива является элементом массива указателей, то выравнивание динамического массива можно выполнить только директивой REALIGN. Т. к. директива REALIGN допускает лишь ссылку на имя указателя, то элемент массива указателей необходимо предварительно переслать в скалярную переменную-указатель. Выравнивание массива с указателем PT(I) на массив с указателем PT(J) можно выполнить с помощью следующей последовательности операторов:

P1 = PT( I )

P2 = PT( J )

CDVM$ REALIGN P1( I, J ) WITH P2( I+1, J )

4.4. Директивы DYNAMIC и NEW_VALUE

Массивы, перераспределяемые директивами REDISTRIBUTE и REALIGN, необходимо специфицировать в директиве DYNAMIC.

dynamic-directive	is DYNAMIC alignee-or-distributee-list
alignee-or-distributee	is alignee
	or distributee

Если после выполнения директив REDISTRIBUTE и REALIGN перераспределяемые массивы получают новые значения, то перед этими директивами следует указать дополнительную (оптимизирующую) директиву NEW_VALUE.

new-value-directive

is NEW_VALUE

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

Если массив указан в спецификации DYNAMIC и для него нет спецификации DISTRIBUTE или ALIGN , то его распределение откладывается до первого оператора REDISTRIBUTE или REALIGN. Такая необходимость возникает в двух случаях:

·  распределение (выравнивание) динамического массива с указателем, который является элементом массива указателей;

·  распределение массива на секцию массива процессоров, параметры которой определяются в процессе вычислений.

4.5. Распределение по умолчанию

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

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

5.1. Параллельные циклы

5.1.1. Определение параллельного цикла

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

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

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

·  цикл является тесно-гнездовым циклом с прямоугольным индексным пространством;

·  распределенные измерения массивов индексируются только регулярными выражениями типа a*I + b , где I - индекс цикла;

·  левые части операторов присваивания одного витка цикла размещены на одном процессоре и, следовательно, виток цикла полностью выполняется на этом процессоре;

·  нет зависимости по данным кроме редукционной зависимости и регулярной зависимости по распределенным измерениям;

·  левая часть оператора присваивания является ссылкой на распределенный массив, редукционную переменную, приватную переменную (см. 5.1.3);

·  нет операторов ввода-вывода и dvm-директив в теле цикла.

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

5.1.2. Распределение витков цикла. Директива PARALLEL

Параллельный цикл специфицируется следующей директивой:

parallel-directive

is PARALLEL ( do-variable-list ) ON iteration-align-spec [ , new-clause ] [ , reduction-clause] [ , shadow-renew-clause] [ , shadow-compute-clause] [ , remote-access-clause ] [ , across-clause ]

iteration-align-spec

is align-target ( iteration-align-subscript-list )

iteration-align-subscript	is int-expr
	or do-variable-use
	or *
do-variable-use	is [ primary-expr * ] do-variable [ add-op primary-expr ]

Директива PARALLEL размещается перед заголовком цикла и распределяет витки циклов в соответствии с распределением массива или шаблона. Семантика директивы аналогична семантике директивы ALIGN, где индексное пространство выравниваемого массива заменяется индексным пространством цикла. Индексы циклов в списке do-variable-list перечисляются в том порядке, в котором размещены соответствующие операторы DO в тесно-гнездовом цикле.

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

new-clause раздел 5.1.3

reduction-clause раздел 5.1.4

shadow-renew-clause раздел 6.2.2

shadow-compute-clause раздел 6.2.3

across-clause раздел 6.2.4

remote-access-clause раздел 6.3.1

Пример 5.1. Распределение витков цикла с регулярными вычислениями.

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 )

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

Цикл удовлетворяет всем условиям параллельного цикла. В частности, левые части операторов присваивания одного витка цикла A(I, J) и B(I, J+1) размещаются на одном процессоре через выравнивание массивов А и В.

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

Пример 5.2. Разделение цикла

	CDVM$ PARALLEL ( I ) ON A( 2*I )
DO 10 I = 1, N	DO 10 I = 1, N
DO 10 J = 1, M-1	10 A(2*I) = . . .
A(2*I) = . . .	CDVM$ PARALLEL ( I) ON B( 3*I )
B(3*I) = . . .	DO 11 I = 1, N
10 CONTINUE	11 B(3*I) = . . .

Цикл разделен на 2 цикла, каждый из которых удовлетворяет условию параллельного цикла.

5.1.3. Приватные переменные. Спецификация NEW

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

new-clause

is NEW ( new-variable-list )

new-variable	is array-name
	or scalar-variable-name

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

Пример 5.3. Спецификация приватной переменной.

CDVM$ PARALLEL ( I, J ) ON A( I, J ) , NEW ( X )

DO 10 I = 1, N

DO 10 J = 1, N

X = B(I, J) + C(I, J)

A(I, J) = X

10 CONTINUE

5.1.4. Редукционные операции и переменные. Спецификация REDUCTION

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

reduction-clause

is REDUCTION ( [ reduction-group-name : ] reduction-op-list )

reduction-op	is reduction-op-name ( reduction-variable )
	or reduction-loc-name ( reduction-variable , location-variable, int-expr)

reduction-variable	is array-name
	or scalar-variable-name
location-variable	is array-name

reduction-op-name	is SUM
	or PRODUCT
	or MAX
	or MIN
	or AND
	or OR
	or EQV
	or NEQV

reduction-loc-name	is MAXLOC
	or MINLOC

Редукционными переменными не могут быть распределенные массивы. Редукционные переменные вычисляются и используются только в операторах определенного вида - редукционных операторах.

Введем следующие обозначения

rv	- редукционная переменная
L	- одномерный массив целого типа
n	- число координат минимума или максимума
er	- выражение, не содержащее rv
Ik	- целая переменная
op	- одна из следующих операций языка Фортран: +, -, .OR., .AND., .EQV., .NEQV.
ol	- одна из следующих операций языка Фортран: .GE., .GT., .LE., .LT.
f	- функция max или min

В теле цикла редукционный оператор имеет один из следующих видов:

1) rv = rv op er

rv = er op rv

2) rv = f( rv, er )

rv = f( er, rv )

3) if( rv ol er ) rv = er

if( er ol rv ) rv = er

4) if( rv ol er ) then

rv = er

L( 1 ) = e1

. . .

L( n ) = en

endif

if( er ol rv ) then

rv = er

L( 1 ) = e1

. . .

L( n ) = en

endif

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

Вид оператора	операция Фортран	имя редукции FDVM
1	+	SUM(rv)
1	*	PRODUCT(rv)
1	.AND.	AND(rv)
1	.OR.	OR(rv)
1	.EQV.	EQV(rv)
1	.NEQV.	NEQV(rv)
2,3		MAX(rv)
		MIN(rv)
4		MINLOC(rv, L, n)
		MAXLOC(rv, L, n)

Операция MAXLOC (MINLOC) предполагает вычисление максимального (минимального) значения и определение его координат.

Пример 5.4. Спецификация редукции.

S = 0

Y =1.E10

X = -1.

IMIN(1) = 0

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

CDVM$* REDUCTION(SUM(S), MAX(X), MINLOC(Y, IMIN,1))

DO 10 I = 1, N

S = S + A(I)

X = MAX(X, A(I))

IF(A(I) .LT. Y) THEN

Y = A(I)

IMIN(1) = I

ENDIF

10 CONTINUE

5.2. Вычисления вне параллельного цикла

Вычисления вне параллельного цикла выполняются по правилу собственных вычислений. Пусть оператор

IF p THEN lh = rh

где p – логическое выражение,

lh – левая часть оператора присваивания (ссылка на скаляр или элемент массива),

rh – правая часть оператора присваивания (выражение),

находится вне параллельного цикла.

Тогда этот оператор будет выполняться на процессоре, где распределены данные со ссылкой lh (процессор own( lh )). Все данные в выражениях p и rh должны быть размещены на процессоре own( lh ). Если какие-либо данные из выражений p и rh отсутствуют на процессоре own( lh ), то их необходимо указать в директиве удаленного доступа (см. 6.1.2) перед этим оператором.

Если lh является ссылкой на распределенный массив А и существует зависимость по данным между rh и lh, то распределенный массив необходимо размножить с помощью директивы

REDISTRIBUTE А( *,...,* ) или REALIGN А( *,...,* )

перед выполнением оператора.

Пример 5.5. Оператор собственных вычислений.

PARAMETER (N = 100)

REAL A(N, N+1), X(N)

CDVM$ ALIGN X( I ) WITH A( I, N+1)

CDVM$ DISTRIBUTE ( BLOCK, * ) :: A

. . .

C обратная подстановка алгоритма Гаусса

C собственные вычисления вне циклов

С

С оператор собственных вычислений

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

X(N) = A(N, N+1) / A(N, N)

DO 10 J = N-1, 1, -1

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

DO 20 I = 1, J

A(I, N+1) = A(I, N+1) - A(I, J+1) * X(J+1)

20 CONTINUE

C собственные вычисления в последовательном цикле,

С охватывающем параллельный цикл

X(J) = A(J, N+1) / A(J, J)

10 CONTINUE

Отметим, что A(J, N+1) и A(J, J) локализованы на том процессоре, где размещается X(J).

6. Cпецификация удаленных данных

6.1. Определение удаленных ссылок

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

IF (…A(inda)…) B(indb) = …C(indc)…

где A, B, C - распределенные массивы,

inda, indb, indc - индексные выражения.

В модели DVM этот оператор будет выполняться на процессоре own(B(indb)), т. е. на том процессоре, где размещен элемент B(indb). Ссылка A(inda) и C(indc) не являются удаленными ссылками, если соответствующие им элементы массивов A и C размещены на процессоре own(B(indb)). Единственной гарантией этого является выравнивание A(inda), B(indb) и C(indc) в одну точку шаблона выравнивания. Если выравнивание невозможно или невыполнено, то ссылки A(inda) и/или C(indc) необходимо специфицировать как удаленные ссылки. В случае многомерных массивов данное правило применяется к каждому распределенному измерению.

По степени эффективности обработки удаленные ссылки разделены на два типа: SHADOW и REMOTE.

Если массивы B и C выровнены и

inda = indc ± d ( d – положительная целочисленная константа),

то удаленная ссылка C(indc) принадлежит типу SHADOW. Удаленная ссылка на многомерный массив принадлежит типу SHADOW, если распределяемые измерения удовлетворяют определению типа SHADOW.

Удаленные ссылки, не принадлежащие типу SHADOW, составляют множество ссылок типа REMOTE.

Особым множеством удаленных ссылок являются ссылки на редукционные переменные (см. 5.2.4), которые принадлежат типу REDUCTION. Эти ссылки могут использоваться только в параллельном цикле.

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

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

6.2. Удаленные ссылки типа SHADOW

6.2.1. Спецификация массива с теневыми гранями

Удаленная ссылка типа SHADOW означает, что обработка удаленных данных будет происходить через “теневые” грани. Теневая грань представляет собой буфер, который является непрерывным продолжением локальной секции массива в памяти процессора (см. рис.6.1.).Рассмотрим оператор