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

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

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

DVM( ALIGN a₁… a_n WITH B b₁… b_m ) <описание-массива-A-на-языке-Си>

где a_i - параметр i–го измерения выравниваемого массива А

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 и семантика.

DVM(ALIGN [i] WITH B[2*i+1] ) float A[N];

Распределить элемент A[ i ] и B[2*i+1] на один процессор.

DVM(ALIGN [i][j] WITH B[j][i]) float A[N][N];

Распределить элемент A[ i ] [ j ] и B[ j ] [ i ] на один процессор.

DVM(ALIGN [i] WITH B[][i]) float A[N];

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

DVM(ALIGN [i] [ ] WITH B[i]) float A[N][N];

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

Изменить параметры выравнивания и/или базовый массив можно с помощью директивы

DVM( REALIGN a₁… a_n WITH C c₁… c_k ) <описание-массива-A-на-языке-Си>

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

Заголовки параллельных циклов описываются макросами DO( ) или FOR( ):

#define DO(v,f,u,s) for(v=f; v<=u; v+=s)

#define FOR(v,h) for(v=0; v<=h-1; v+=1)

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

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

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

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

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

DVM( PARALLEL [ I₁ ]… [ I_n ] ON A e₁… 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. Отличием является то, что вместо выравниваемого массива данных используется массив витков параллельного цикла.

Пример.

DVM(PARALLEL [i]]j] ON A[i][j] )

FOR(i, N)

FOR(j, N)

{

A[i][j] = …;

B[i][j] = …;

}

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

DVM( ALIGN [i] [j] WITH A[i][j] ) float B[N][N];

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

Пример.

FOR(i, N)

{

D[2*i] = …;

D[2*i+1] = …;

}

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

DVM(PARALLEL [i] ON D[2*i])

FOR(i, N)

{

D[2*i] = …;

}

DVM(PARALLEL [i] ON D[2*i+1])

FOR(i, N)

{

D[2*i+1] = …;

}

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

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

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

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

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

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

DVM(DISTRIBUTE [BLOCK]) float A[N];

DVM(PARALLEL [i] ON A[i])

FOR(i, N)

{

A[i] = expr;

}

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

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

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

Пусть

A[i] = B[i] + C[i]

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

DVM( ALIGN [i] WITH A[i] ) float B[N], C[N];

Рассмотрим следующее выражение:

A[i] = B[i+d1] + C[i-d2]

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

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

DVM(DISTRIBUTE [BLOCK]; TEMPLATE [N+d1+d2]) void *TABC;

DVM( ALIGN [i] WITH TABC[i] ) float B[N];

DVM( ALIGN [i] WITH TABC[i+d2] ) float A[N];

DVM( ALIGN [i] WITH TABC[i+d1+d2] ) float C[N];

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

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

A[i] = B[i-d1] + B[i+d2]

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

DVM( ALIGN [i] WITH A[i] ) float B[N];

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

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

DVM( ALIGN [i] WITH A[i]; SHADOW [d1:d2] ) float B[N];

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

DVM(PARALLEL [i] ON A[i]; SHADOW_RENEW B)

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

A[i] = A[i-d1] + A[i+d2]

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

DVM(DISTRIBUTE [BLOCK]; SHADOW [d1:d2]) float A[N];

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

DVM(PARALLEL [i] ON A[i]; ACROSS A[d1:d2])

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

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

A[i] = C[5] + C[i+n]

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

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

DVM(PARALLEL [i] ON A[i]; REMOTE_ACCESS C[5] C[i+n])

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

A[i] = B[i] + C[i]; S=S+A[i];

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

DVM(PARALLEL [i] ON A[i]; REDUCTION SUM(S))

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

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

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

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

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

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

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

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