Lecture_DVM_2 (1158299), страница 2

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

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

Пример.

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 - индекс цикла;

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

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

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

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

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

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

FOR(i, N)

{

A[i] = expr;

}

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

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

2.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 определяет некоторое индексное пространство, которое является посредником между массивом данных и массивом виртуальных процессоров. Элементы шаблона не имеют физического представления в памяти. Они указывают процессоры, на которые должны быть распределены соответствующие элементы массивов данных.

2.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)

2.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 перечисляются все распределенные массивы, по которым существует регулярная зависимость по данным.

2.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])

2.5.5. Удаленные данные типа REDUCTION

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

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

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

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

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

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

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

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

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

Для того, чтобы C-DVM программа могла компилироваться и выполняться как обычная последовательная программа, копирование массивов (секций) записывается как обычный многомерный цикл. Тело цикла должно состоять из единственного оператора присваивания. Заголовки цикла должны быть записаны макрокомандами DO(v,first,last,step) или FOR(v,times). Все переменные цикла должны использоваться в индексных выражениях правой и левой части оператора присваивания, причем в одном и том же порядке. Каждое индексное выражение может содержать только одну переменную цикла и должно зависеть от нее линейно.

Для асинхронного копирования нужно:

• объявить директивой COPY_FLAG переменную -- флаг завершения операции копирования;

• перед циклом указать директиву COPY_START с адресом переменной-флага;

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

Пример . Асинхронное копирование.

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

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

. . .

DVM(COPY_FLAG) void * flag;

. . .

DVM(COPY_START &flag)

FOR(i,N)

FOR(j,N)

B[i][j]=A[i][j];

. . .

DVM(COPY_WAIT &flag);

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

Пример .Синхронное копирование.

DVM(COPY)

FOR(i,N)

FOR(j,N)

B[i][j]=A[i][j];

2.7. Многомерные массивы

При локализации данных с помощью директивы ALIGN для многомерных массивов необходимо указывать индексы выравниваемых элементов массивов по всем измерениям.

На предмет наличия удаленных данных достаточно анализировать только распределенные измерения массивов. Локальные измерения полностью распределены на каждом процессоре и по этим измерениям не существует удаленных данных. Каждое распределенное измерение, по которому существуют удаленные данные, должно быть учтено при спецификации удаленных данных в соответствии с разделами 2.5.2 - 2.5.4.

2.8. Процедуры

Вызов процедуры из параллельного цикла

Процедура, вызываемая из параллельного цикла, не должна иметь побочных эффектов и содержать обменов между процессорами (прозрачная процедура). Как следствие этого, прозрачная процедура не содержит операторов ввода-вывода и DVM‑директив.

Вызов процедуры вне параллельного цикла

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

Формальные параметры

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

• Если распределение фактического параметра известно, то директивой
  DVM(*DISTRIBUTE f₁…f_k);

• Если известна только размерность, но не конкретное распределение, то директивой DVM(*DISTRIBUTE[*]...[*]);

• Если фактический параметр может быть произвольным (распределенным или нераспределенным) массивом, то директивой DVM(*). Такой параметр может использоваться только в функциях fread/fwrite.

Локальные массивы.

Локальные массивы могут распределяться в процедуре директивами DISTRIBUTE и ALIGN. Локальный массив может быть выровнен на формальный аргумент. Директива DISTRIBUTE распределяет локальный массив на ту подсистему процессоров, на которой была вызвана процедура (текущая подсистема).

2.9. Ввод/вывод

В C-DVM, разрешены следующие операции ввода/вывода для размноженных данных:

fopen, fclose, feof, fprintf, printf, fscanf, fputc, putc, fputs, puts, fgetc, getc, fgets, gets, fflush, fseek, ftell, ferror, clearerr, perror, as well as fread, fwrite.

Эти операторы выполняются на выделенном процессоре (процессоре ввода/вывода). Выводимые значения берутся на этом процессоре, а вводимые – вводятся на нем и рассылаются на остальные процессоры.

Для распределенных данных обеспечивается только бесформатный ввод/вывод массива целиком функциями fread/fwrite.

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

2.10. Ограничения на использование языка СИ

C-DVM предназначен для распараллеливания вычислительных программ, написанных в "фортрано-подобном" стиле. При этом на использование средств языка СИ накладываются некоторые ограничения. В первую очередь эти ограничения касаются использования указателей на распределенные массивы и их элементы. C‑DVM не запрещает использовать указатели, но некоторые операции с ними могут стать некорректными после конвертирования программы. Например:

• идентификатор массива (или указателя на массив) становится идентификатором массива целых чисел (так называемого хендлера массива);

• процессор содержит только локальную часть массива, поэтому относительный доступ к его элементам с помощью адресной арифметики невозможен;

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

Второе ограничение касается типов данных: элементы распределенных массивов могут быть только скалярных типов int, long, float и double.

Некоторые описания для распараллеливания требуют выполнения определенных действий. Так, например:

• описания процессорных секций;

• описание распределенных массивов или шаблонов с константными размерностями ("статических");

• инициализация переменных (требуется их регистрация для отладчика).

Такого рода неявные действия для глобальных объектов выполняются в начале функции main сразу после инициализации системы поддержки. Поэтому в момент генерации main все такие объекты должны быть известны, т.е. не могут находиться в отдельно транслируемом файле или следовать за описанием функции main. Для объектов, локальных в функции или блоке, эти действия выполняются перед первым оператором блока. Кроме того, заметим, что неявные действия выполняются в порядке описаний, и это накладывает определенные семантические ограничения на порядок описаний: база ALIGN должна быть описана до выравниваемого массива и т.п.

И наконец, использование препроцессора, выходящее за пределы файлов заголовков, требует осторожности по нескольким причинам. Во-первых, C-DVM компилятор работает до препроцессора. Поэтому, например, пара определений

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

Список файлов лекций