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

решетки виртуальных процессоров.

6.2.5. Асинхронная спецификация независимых ссылок типа SHADOW

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

·  запуск обмена,

·  ожидание значений.

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

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

Определение группы.

shadow-group-directive

is SHADOW_GROUP shadow-group-name ( renewee-list )

Запуск обновления теневых граней.

shadow-start-directive

is SHADOW_START shadow-group-name

Ожидание значений теневых граней.

shadow-wait-directive

is SHADOW_WAIT shadow-group-name

Директива SHADOW_START должна выполняться после директивы SHADOW_GROUP. После выполнения директивы SHADOW_GROUP директивы SHADOW_START и SHADOW_WAIT могут выполняться многократно. Новые значения в теневых гранях могут использоваться только после выполнения директивы SHADOW_WAIT.

Особым вариантом является использование директив SHADOW_START и SHADOW_WAIT в спецификации shadow-renew-clause параллельного цикла.

Синтаксис спецификации shadow-renew-clause расширен следующим образом:

shadow-renew-clause	is. . .
	or shadow-start-directive
	or shadow-wait-directive

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

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

Пример 6.8. Совмещение счета и обновления теневых граней.

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

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

CDVM$ DISTRIBUTE ( BLOCK, BLOCK ) :: C

. . .

CDVM$ SHADOW_GROUP AB ( A, B )

. . .

CDVM$ SHADOW_START AB

. . .

CDVM$ PARALLEL ( I, J ) ON C ( I, J ), SHADOW_WAIT AB

DO 10 I = 2, 99

DO 10 J = 2, 99

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

D(I, J) = (B(I-1,J) + B(I+1,J) + B(I, J-1) + B(I, J+1) ) / 4

10 CONTINUE

Распределенные массивы по умолчанию имеют теневые грани в 1 элемент по каждому измерению. Т. к. в спецификации параллельного цикла указана директива SHADOW_WAIT, то изменяется порядок выполнения витков цикла. Сначала будут выполняться вычисления на внутренней области каждой локальной секции массива, затем выполнится директива ожидания новых значений теневых граней. Выполнение цикла завершается вычислением значений пересылаемых в теневые грани.

6.3. Удаленные ссылки типа REMOTE

6.3.1. Директива REMOTE_ACCESS

Удаленные ссылки типа REMOTE специфицируются директивой REMOTE_ACCESS.

remote-access-directive	is REMOTE_ACCESS ( [ remote-group-name : ] regular-reference-list )
regular-reference	is dist-array-name [( regular-subscript-list )]
regular-subscript	is int-expr
	or do-variable-use
	or :
remote-access-clause	is remote-access-directive

Директива REMOTE_ACCESS может быть отдельной директивой (область действия - следующий оператор) или дополнительной спецификацией в директиве PARALLEL (область действия – тело параллельного цикла).

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

Рассмотрим удаленную ссылку на многомерный распределенный массив

A( ind1, ind2,…,indk )

Пусть indj – индексное выражение по j-ому измерению.

В директиве REMOTE_ACCESS индексное выражение указывается без изменений, если

·  j-ое измерение является распределенным измерением,

·  indj = a * i + b, где a и b не изменяются в процессе выполнения цикла (инварианты).

Во всех остальных случаях в директиве REMOTE_ACCESS вместо indj указывается “:” (все измерение).

6.3.2. Синхронная спецификация удаленных ссылок типа REMOTE

Если в директиве REMOTE_ACCESS не указано имя группы (remote-group-name), то выполнение такой директивы происходит в синхронном режиме. В пределах нижестоящего оператора или параллельного цикла компилятор заменяет все вхождения удаленной ссылки ссылкой на буфер. Пересылка удаленных данных производится перед выполнением оператора или цикла.

Пример 6.9. Синхронная спецификация удаленных ссылок типа REMOTE.

DIMENSION A(100,100), B(100,100)

CDVM$ DISTRIBUTE (*,BLOCK) :: A

CDVM$ ALIGN B( I, J ) WITH A( I, J )

. . .

CDVM$ REMOTE_ACCESS ( A(50,50) )

С замена ссылки A(50,50) ссылкой на буфер

С рассылка значения A(50,50) по всем процессорам

1 X = A(50,50)

. . .

CDVM$ REMOTE_ACCESS ( B(100,100) )

С пересылка значения В(100,100) в буфер процессора own(A(1,1)

2 A(1,1) = B(100,100)

. . .

CDVM$ PARALLEL (I, J) ON A(I, J) , REMOTE_ACCESS ( B(:,N) )

С рассылка значений B(:,N) по процессорам own(A(:,J))

3 DO 10 I = 1, 100

DO 10 J = 1, 100

10 A(I, J) = B(I, J) + B(I, N)

Первые две директивы REMOTE_ACCESS специфицируют удаленные ссылки для отдельных операторов. REMOTE_ACCESS в параллельном цикле специфицирует удаленные данные (столбец матрицы) для всех процессоров, на которые распределен массив А.

6.3.3. Асинхронная спецификация удаленных ссылок типа REMOTE

Если в директиве REMOTE_ACCESS указано имя группы (remote-group-name), то выполнение директивы происходит в асинхронном режиме. Для спецификации этого режима необходимы следующие дополнительные директивы.

Описание имени группы.

remote-group-directive

is REMOTE_GROUP remote-group-name-list

Идентификатор, определенный этой директивой, может использоваться только в директивах REMOTE_ACCESS, PREFETCH и RESET. Группа remote-group представляет собой глобальный объект, областью действия которого является вся программа.

prefetch-directive	is PREFETCH remote-group-name
reset-directive	is RESET remote-group-name

Рассмотрим следующую типовую последовательность асинхронной спецификации удаленных ссылок типа REMOTE.

CDVM$ REMOTE_GROUP RS

10 . . .

CDVM$ PREFETCH RS

. . .

C вычисления, в которых не участвуют удаленные ссылки r1 , …,rn

. . .

CDVM$ PARALLEL . . . , REMOTE_ACCESS (RS : r1)

. . .

CDVM$ REMOTE_ACCESS (RS : ri)

. . .

CDVM$ PARALLEL . . . , REMOTE_ACCESS (RS : rn)

. . .

IF( P ) GO TO 10

При первом прохождении указанной последовательности операторов директива PREFETCH не выполняется. Директивы REMOTE_ACCESS выполняется в обычном синхронном режиме. При этом происходит накопление ссылок в переменной RS. После выполнения всей последовательности директив REMOTE_ACCESS значение переменной RS равно объединению подгрупп удаленных ссылок ri È ...È rn.

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

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

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

·  Директиву PREFETCH можно выполнять для нескольких циклов (нескольких директив REMOTE_ACCESS), если между этими циклами не существует зависимости по данным для распределенных массивов, указанных в директивах REMOTE_ACCESS .

Если характеристики группы удаленных ссылок изменились, то необходимо присвоить неопределенное значение группе удаленных ссылок с помощью директивы RESET, после чего будет происходить новое накопление группы удаленных ссылок.

Рассмотрим следующий фрагмент многообластной задачи. Область моделирования разделена на 3 подобласти, как показано на рис.6.6.

	M
N1	A1
				D
N2	A2	A3
	M1	M2

Рис.6.6. Разделение области моделирования.

Пример 6.10. Использование группы регулярных удаленных ссылок.

REAL A1(M, N1+1), A2(M1+1,N2+1), A3(M2+1,N2+1)

CDVM$ DISTRIBUTE ( BLOCK, BLOCK) :: A1, A2, A3

CDVM$ REMOTE_GROUP RS

DO 1 ITER = 1, MIT

. . .

C обмен границами по линии раздела D

CDVM$ PREFETCH RS

. . .

CDVM$ PARALLEL ( I ) ON A1 ( I, N1+1 ), REMOTE_ACCESS ( RS: A2(I,2))

DO 10 I = 1, M1

10 A1(I, N1+1) = A2(I,2)

CDVM$ PARALLEL ( I ) ON A1 ( I, N1+1 ), REMOTE_ACCESS ( RS: A3(I-M1,2))

DO 20 I = M1+1, M

20 A1(I, N1+1) = A3(I-M1,2)

CDVM$ PARALLEL ( I ) ON A2 ( I, 1 ), REMOTE_ACCESS ( RS: A1(I, N1))

DO 30 I = 1, M1

30 A2(I,1) = A1(I, N1)

CDVM$ PARALLEL ( I ) ON A3 ( I, 1 ), REMOTE_ACCESS ( RS: A1(I+M1,N1))

DO 40 I = 1, M2

40 A3(I,1) = A1(I+M1,N1)

. . .

IF (NOBLN) THEN

C перераспределение массивов с целью балансировки загрузки

. . .

CDVM$ RESET RS

END IF

. . .

1 CONTINUE

6.3.4. Асинхронное копирование по ссылкам типа REMOTE

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

6.3.4.1. Цикл и операторы копирования

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

DO 10 I1 = L1,H1,S1

. . .

DO 10 In = Ln, Hn, Sn

10 A(f1,…,fk) = B (g1,…,gm)

где A, B - идентификаторы разных распределенных массивов.

Li, Hi, Si – инварианты цикла

fi = ai *Ii + bi

gj = cj *Ij + dj

ai, bi, cj, dj – целые выражения, инварианты цикла (выражения, значения которых не изменяются в процессе выполнения цикла).

Каждая переменная цикла Il может быть использована не более чем в одном выражении fi и не более чем в одном выражении gj.

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

Цикл копирования может быть описан одним или несколькими операторами копирования (copy-statement) следующего вида

A(a1,…,ak) = B(b1,…,bm)

где

ai = li : hi : si

bj = lj : hj : sj

ai, bj - являются триплетами языка Фортран 90.

Оператор копирования является аналогом оператора присваивания секций массивов Фортран 90.

Для триплетов существуют правила сокращенной записи. Определим эти правила на примере триплета ai.

1)  Если в копировании участвует все измерение массива, то

ai = :

2)  Если si = 1, то

ai = li : hi

3)  Если Li = hi, то

ai = li

Для цикла копирования 10 выражения триплетов определяются следующим образом

Для ai Для bj

li = ai *Li + bi lj = cj *Lj + dj

hi = ai *Hi + bi hj = cj *Hj + dj

si = ai *Si sj = cj *Sj

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

REAL A(N1,N2,N3), B(N1,N3)

DO 10 I1 = 1, N1

DO 10 I2 = 2, N3-1

10 A(I1, 5, I2+1) = B(I1, I2-1)

Этому циклу соответствует следующий оператор копирования

A( :, 5, 3:N3 ) = B( :, 1:N3-2 )

6.3.4.2. Директивы асинхронного копирования

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

Асинхронное копирование определяется комбинацией директивы начала копирования (ASYNCHRONOUS ID) и директивой ожидания окончания копирования (ASYNCWAIT ID). Соответствие директив определяется одним идентификатором ID.

6.3.4.2.1. Директива ASYNCID

Директива ASYNCID описывает отдельный идентификатор для каждой пары директив асинхронного копирования.

Синтаксис директивы:

asyncid-directive	is ASYNCID async-name-list

6.3.4.2.2. Директива F90

Директива F90 является префиксом для каждого оператора копирования.

Синтаксис.

f90-directive	is F90 copy-statement
copy-statement	is array-section = array-section
array-section	is array-name [( section-subscript-list )]
section-subscript	is subscript
	or subscript-triplet
subscript-triplet	is [ subscript ] : [ subscript ] [ : stride]
subscript	is int-expr
stride	is int-expr

6.3.4.2.3. Директивы ASYNCHRONOUS и END ASYNCHRONOUS

Директивы ASYNCHRONOUS и END ASYNCHRONOUS задают блочную конструкцию.

Синтаксис.

asynchronous-construct	is asynchronous-directive
	f90-directive [ f90-directive ] … copy-loop [ copy-loop ] …
	end-asynchronous-directive
asynchronous-directive	is ASYNCHRONOUS async-name
end-asynchronous-directive	is END ASYNCHRONOUS

Все операторы присваивания в циклах копирования (copy-loop) должны быть описаны директивами F90 с соответствующим оператором копирования.

6.3.4.2.4. Директива ASYNCWAIT

Синтаксис.

asyncwait-directive

is ASYNCWAIT async-name

Пример из раздела 6.3.4.1 можно специфицировать как асинхронное копирование следующим образом.

CDVM$ ASYNCID TR

REAL A(N1,N2,N3), B(N1,N3)

. . .

CDVM$ ASYNCHRONOUS TR

CDVM$ F90 A( :, 5, 3:N3 ) = B( :, 1:N3-2 )

DO 10 I1 = 1, N1

DO 10 I2 = 2, N3-1

10 A(I1, 5, I2+1) = B(I1, I2-1)

CDVM$ END ASYNCHRONOUS

. . .

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

которая выполняется на фоне передачи данных

. . .

CDVM$ ASYNCWAIT TR

6.4. Удаленные ссылки типа REDUCTION

6.4.1. Синхронная спецификация удаленных ссылок типа REDUCTION

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

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

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

6.4.2. Асинхронная спецификация удаленных ссылок типа REDUCTION

Асинхронная спецификация позволяет:

·  объединять в одну группу редукционные переменные, вычисляемые в разных циклах;

·  совмещать выполнение глобальной групповой редукции с другими вычислениями.

Для асинхронной спецификации, кроме директивы REDUCTION (с именем группы), необходимы следующие дополнительные директивы.

reduction-group-directive

is REDUCTION_GROUP reduction-group-name-list

reduction-start-directive

is REDUCTION_START reduction-group-name

reduction-wait-directive

is REDUCTION_WAIT reduction-group-name

Типовая последовательность директив асинхронной спецификации типа REDUCTION выглядит следующим образом.

CDVM$ REDUCTION_GROUP RD

. . .

CDVM$ PARALLEL . . . , REDUCTION (RD : d1)

C локальная редукция d1

. . .

CDVM$ PARALLEL . . . , REDUCTION (RD : dn)

C локальная редукция dn

. . .

CDVM$ REDUCTION_START RD

C начало глобальной редукции di È ...È dn

. . .

CDVM$ REDUCTION_WAIT RD

C конец глобальной редукции di È ...È dn

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

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

·  Директива REDUCTION_START и REDUCTION_WAIT должны выполняться после окончания цикла (циклов), где вычислялись локальные значения редукционных переменных. Между этими операторами могут выполняться только те операторы, в которых не используются значения редукционных переменных.

·  Директива REDUCTION_WAIT уничтожает группу редукционных операций.

Пример 6.11. Асинхронная спецификация типа REDUCTION.

CDVM$ DISTRIBUTE A ( BLOCK )

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

CDVM$ REDUCTION_GROUP RD

. . .

S = 0.

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

CDVM$* REDUCTION ( RD : SUM(S))

DO 10 I = 1, N

10 S = S + A(I)

X = 0.

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

CDVM$* REDUCTION ( RD : MAX(X))

DO 20 I = 1, N

20 X = MAX(X, ABS( B(I) ) )

CDVM$ REDUCTION_START RD

C начало глобальной редукции SUM(S) и MAX(X)

CDVM$ PARALLEL ( I ) ON A( I )

DO 30 I = 1, N

30 A(I) = A(I) + B(I)

CDVM$ REDUCTION_WAIT RD

C конец глобальной редукции

PRINT *, S, X

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

7. Параллелизм задач

Модель параллелизма DVM объединяет параллелизм по данным и параллелизм задач.

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

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

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

Отдельная группа задач определяется следующими директивами:

1)  Описание массива задач (директива TASK).

2)  Отображение массива задач на секции массива процессоров (директива MAP).

3)  Распределение массивов по задачам (директива REDISTRIBUTE).

4)  Распределение вычислений (блоков операторов или витков параллельного цикла) по задачам (конструкция TASK_REGION).

В процедуре может быть описано несколько массивов задач. Вложенность задач не разрешается.

7.1. Описание массива задач

Массив задач описывается следующей директивой:

task-directive	is TASK task-list
task	is task-name ( max-task )

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