Параллельное программирование на языке Fortran DVM (1158280), страница 2

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

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

b_j - параметр j–го измерения базового массива B

n - количество измерений массива А

m - количество измерений массива В

Эта директива ставит в соответствие каждому элементу массива В некоторое подмножество элементов массива А. Установленное подмножество элементов массива А будет распределено на тот процессор, где будет размещен соответствующий элемент массива В. Параметры выравниваемого массива А и базового массива В могут иметь следующие обозначения

a_i = ID_i b_j = c*ID_j+d

= * = *

где ID_i , ID_j - идентификаторы

c, d - целочисленные константы

Рассмотрим семантику этих обозначений.

Если a_i = * , то i–тое измерение массива А целиком распределяется на каждый процессор, где распределен хотя бы один элемент В (размножение, локальное измерение).

Если b_j = * , то выполнение директивы ALIGN не зависит от j-ого измерения массива В (коллапс, т.е. измерение как бы не существует при установлении соответствия).

Если a_i = ID_i , то обязательно существует одно и только одно b_j = c*ID_j+d , где ID_i=ID_j. Равенство ID_i=ID_j означает, что i–тое измерение массива А ставится в соответствие j-ому измерению массива В. Соответствие элементов устанавливается функцией c*ID_j+d .

Примеры директивы ALIGN и семантика.

CDVM$ ALIGN A( I) WITH B(2*I+1)

Распределить элемент A( I ) и B( 2*I+1) на один процессор

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

Распределить элемент A( I,J ) и B( J,I) на один процессор.

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

Распределить элемент A( I ) на те процессоры, где размещен хотя бы один элемент I-ого столбца B.

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

Распределить I-ую строку A и элемент B( I ) на один процессор, т.е. размножить второе измерение массива А.

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

Параллельный цикл в модели DVM рассматривается как массив витков цикла. Количество измерений такого массива равно количеству заголовков параллельного цикла. Размер каждого измерения определяется параметрами соответствующего заголовка цикла. Чтобы такое представление было правильным, необходимо выполнение следующих условий:

• заголовки параллельного цикла не должны разделяться другими операторами (тесно-гнездовой цикл);

• параметры заголовков параллельного цикла не должны изменяться в процессе выполнения цикла (прямоугольное индексное пространство);

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

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

CDVM$ PARALLEL ( I_{1 ,}… I_n ) ON A ( e_1,… e_m )

где

I_j - переменная (индекс) j–го заголовка параллельного цикла,

n - количество заголовков цикла,

A - идентификатор массива,

m - количество измерений массива,

e_i=a* I_k+b, a, b – целочисленные переменные

I_k - переменная(индекс) k-го заголовка цикла.

Это выражение означает следующее:

• k-ое измерение (заголовок цикла) массива витков цикла ставится в соответствие i–ому измерению массива данных,

• соответствие витка цикла и элемента массива устанавливается линейной функцией a* I_k+b.

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

Пример.

CDVM$ PARALLEL ( I, J ) ON A( 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) = D(I,J) - C(I,J)

1. CONTINUE

Для того, чтобы левые части операторов присваивания одного витка цикла были распределены на одном процессоре необходимо к описанию массива В применить следующую директиву:

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

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

Пример.

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

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

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

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

• нет DVM-директив в теле цикла.

3.5Удаленные данные. Их типы и спецификация

В следующих разделах будем использовать фрагмент программы

CDVM$ DISTRIBUTE A ( BLOCK)

. . .

CDVM$ PARALLEL ( I ) ON A ( I)

DO 10 I =1,N

A(I) = expr

10 CONTINUE

где expr - выражение.

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

3.5.1Локализация данных

Пусть

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

Если A( I ), B( I ) и C( I ) для каждого I распределены на одном процессоре, то для этого оператора не существует удаленных данных. Локализацию данных можно выполнить директивами ALIGN:

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

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

Рассмотрим оператор

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

где d1,d2 – положительные константы.

Полную локализацию данных для этого оператора невозможно выполнить используя массив A, т.к. смещение +d1 и -d2 выводят за пределы индексного пространства массива A. Поэтому необходимо применить шаблон следующим образом.

CDVM$ TEMPLATE TABC ( N )

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

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

CDVM$ ALIGN C( I ) WITH TABC( I + d1+d2)

CDVM$ DISTRIBUTE TABC ( BLOCK )

В этом случае A( I ) , B( I+d1 ) и C( I-d2 ) для каждого I будут распределены на один процессор. Шаблон TABC определяет некоторое индексное пространство, которое является посредником между массивом данных и массивом виртуальных процессоров. Элементы шаблона не имеют физического представления в памяти. Они указывают процессоры, на которые должны быть распределены соответствующие элементы массивов данных.

3.5.2Удаленные данные типа SHADOW

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

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

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

После выполнения этой директивы точно определяется местонахождение удаленных данных. Для вычисления всех A(I) на одном процессоре будут использоваться d1 элементов массива B с левого соседнего процессора и d2 с правого соседнего процессора. Такие данные будем называть удаленными данными типа SHADOW (теневые).

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

CDVM$ SHADOW B( d1:d2 )

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

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 добавляется спецификация 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 необходимо указать следующую спецификацию 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 спецификацию REDUCTION:

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

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

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

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

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

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

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

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

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

DO 10 I₁ = L₁,H₁,S₁

. . .

DO 10 I_n = L_n,H_n,S_n

10 A(f₁,…,f_k) = B (g₁,…,g_m)

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

L_i,H_i,S_i – инварианты цикла

f_i = a_i *I_i + b_i

g_j = c_j *I_j + d_j

a_i, b_i , c_j, d_j – целые выражения, инварианты цикла (выражения, значения которых не изменяются в процессе выполнения цикла).

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

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

Оператор копирования

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

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

A(₁,…,_k) = B(₁,…,_m)

где

_i = l_i : h_i : s_i

_j = l_j : h_j : s_j

_i, _j - являются триплетами языка Фортран 90 (<начало>:<конец>:<шаг> по каждой размерности массива).

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

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

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

_i = :

Если s_i = 1, то

_i = l_i : h_i

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

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