| Оглавление | Часть 1 | C-DVM - часть 2 | Часть 3 |
Параллельная программа разрабатывается для многопроцессорной системы с распределенной памятью (МПС), которую программист представляет в виде прямоугольной многомерной решетки процессоров. Такое представление позволяет ему компактно и наглядно описывать распределение данных и вычислений. При запуске программы пользователь задает размерность (количество измерений) МПС и количество процессоров в каждом измерении. При этом заданная размерность не может быть меньше той, из которой исходил программист при описании распределения данных и вычислений. Указания о количестве процессоров влияют на эффективность выполнения программы, но не могут повлиять на результаты выполнения правильно написанной программы.
В модели C-DVM данные могут быть нераспределенными (т.е. размноженными по одному экземпляру на каждом процессоре), а могут быть распределены по одной секции массива на каждом процессоре с помощью указания DISTRIBUTE или ALIGN (см.4.1). Эти указания используются как префиксы к описаниям массивов.
Скалярные переменные всегда являются размноженными переменными.
Указание DISTRIBUTE может применяться как к статическим, так и к динамическим массивам следующим образом:
DVM (DISTRIBUTE rd1. . . rdN) описания-массивов ;
Для каждого измерения массива указывается тип распределения измерения:
Замечание1. Если ни одно измерение массива не указано как распределенное, то массив будет размножен при создании, но может быть впоследствии распределен с помощью директивы REDISTRIBUTE (см. 6.2).
Замечание2. Поскольку размер памяти, требуемой для размещения распределенного массива зависит от количества процессоров, на которые он отображается, то выделение памяти осуществляется только при выполнении программы, когда становится известным количество выделенных для нее процессоров. Поэтому статические распределенные массивы превращаются компилятором в динамические массивы, создание которых осуществляется при входе в функцию main(). Все статические распределенные массивы должны быть описаны как глобальные в том же файле, в котором находится функция main().
Примеры описаний:
float A[100]; /* обычный нераспределенный статический массив */
DVM (DISTRIBUTE[ ][ ]) float B[20][30]; /*двумерный статический массив, распределенный с размножением */
DVM (DISTRIBUTE [BLOCK] [] [BLOCK]) float D[100][10][100]; /*трехмерный статический распределенный массив: 1-е измерение массива распределяется по 1-му измерению МПС, 2-е измерение массива не распределяется, 3-е измерение массива распределяется по 2-му измерению МПС*/
В языке C-DVM расширены возможности использования динамических массивов - можно создавать многомерные массивы, размеры которых по любым измерениям могут вычисляться при выполнении программы (в языке Си это разрешено только для одного первого измерения). Кроме того, многомерные массивы разных размеров (и, в некоторых случаях, даже разной размерности) могут передаваться в процедуру в качестве ее фактического параметра. Существуют два различных способа работы с многомерными динамическими массивами. Первый базируется на использовании многомерных массивов языка Си, а второй - на моделировании многомерных массивов с помощью одномерных.
Для обеспечения возможности создания многомерных массивов с вычисляемыми размерами (и сохранения возможности выполнять и отлаживать программы на рабочих станциях с использованием обычных компиляторов и средств отладки) определена следующая дисциплина описания, создания, использования и уничтожения динамических массивов языка Си.
1) n-мерный массив
описывается как указатель на
(n-1)-мерный массив, т.е.
<elem_type> (*arrid)[dim2]...[dimn];
В частности, одномерный
массив описывается как указатель
на скаляры
<elem_type> *arrid;
2) Инициализация
указателя и запрос памяти под
n-мерный массив осуществляется
динамически оператором
arrid = malloc(dim1 * dim2 *... *
elem_size);
Здесь
| elem_type | - тип элемента, |
| elem_size | - размер элемента в байтах, |
| arrid | - имя (идентификатор) массива, |
| indi | - i-ый индекс массива. |
| dimi | - размер i-го измерения массива. |
Замечание. При использовании обычного компилятора Си размеры массива во всех измерениях, кроме первого, должны быть заданы константами. Для этого необходимо временно переопределить имена переменных, описав их как константы (см. пример программы RED-BLACK в приложении 1). Компилятор C-DVM такие переопределения проигнорирует.
3) Уничтожение массива производится оператором free (arrid);
4) Обращение к элементу массива в тексте программы записывается как arrid[ind1]...[indn]
Пример описания:
DVM (DISTRIBUTE [BLOCK] [BLOCK]) float *C[N]; /*двумерный распределенный динамический массив */
При необходимости использования многомерных массивов с вычисляемыми размерами в программах на языке Си программисты применяют следующий прием. Вместо многомерного массива создается одномерный массив требуемого размера. Доступ к элементам моделируемого многомерного массива осуществляется путем введения для них обозначений вида arrid(ind1,...,indN), идентичных по виду обозначениям элементов массивов в Фортране. С помощью макросредств препроцессора Си эти обозначения интерпретируются как обращения к соответствующим элементам одномерного массива.
При использовании компилятора C-DVM такие обозначения рассматриваются как обозначения элементов многомерного массива, если указанный одномерный массив специфицирован с помощью указаний DISTRIBUTE или ALIGN как многомерный распределенный массив. Макрокоманда, обеспечивающая доступ к элементам моделируемого массива, в этом случае игнорируется.
Пример описания динамического массива (одномерного при последовательном выполнении и двумерного при параллельном) и обращения к его элементам:
DVM (DISTRIBUTE [BLOCK] [ ]) float *C; C(i,j) = (C(i,j-1) + C(i,j+1))/2;
Моделью выполнения C-DVM программы, как и программ на других языках с параллелизмом по данным, является модель ОПМД (одна программа - множество потоков данных). На все процессоры загружается одна и та же программа, но каждый процессор в соответствии с правилом собственных вычислений выполняет только те операторы присваивания, которые изменяют значения переменных, размещенных на этом процессоре (собственных переменных).
Таким образом, вычисления распределяются в соответствии с размещением данных (параллелизм по данным). В случае размноженной переменной оператор присваивания выполняется на всех процессорах, а в случае распределенного массива - только на процессоре (или процессорах), где размещен соответствующий элемент массива.
Определение “своих” операторов и пропуск “чужих” операторов может вызывать значительные накладные расходы при выполнении программы. Чтобы избежать их, на C-DVM программу накладываются следующие ограничения:
Таким образом, ответственность за согласованное распределение вычислений и данных полностью возлагается на программиста.
С целью дальнейшего снижения накладных расходов отображение витков параллельного цикла осуществляется блочно - на каждый процессор отображается сразу несколько соседних витков цикла. Кроме того, если имеется гнездо тесно вложенных циклов, между заголовками которых нет других операторов, то оно может быть специфицировано как единый многомерный параллельный цикл.
Для спецификации параллельного цикла служит DVM-описание
DVM (PARALLEL [j1]...[jN] ON имя-массива [v1]...[vN])
которое задает отображение витков цикла косвенно - посредством задания соответствия между витками и элементами базового распределенного массива (виток цикла с индексами [j1]...[jN] отображается на тот процессор, на котором расположен элемент базового массива с индексом [v1]...[vN] ). При этом индексные выражения vi должны быть линейными выражениями вида vi =ai* ji + bi , где ai и bi - выражения, значения которых будут вычислены при входе в цикл.
Параллельный цикл должен удовлетворять следующим требованиям.
1) Цикл может быть объявлен параллельным только в том случае, если его витки могут выполняться в произвольном порядке. Например, если при выполнении любого витка цикла не изменяются данные, используемые другими витками, то такой цикл может выполняться параллельно.
2) Заголовки цикла должны быть записаны с помощью макрокоманд DO или FOR:
#define DO(v,l,h,s) for(v=(l); v<=(h); v+=(s)) #define FOR(v,h) for(v=0; v<(h); v++)
3) Параметры
l, h, s не должны изменяться при
выполнении параллельного цикла
(прямоугольное индексное
пространство цикла).
Замечание. В виде исключения
из этого правила в настоящей версии
языка предусмотрена возможность
описания параллельного цикла для
двумерного красно-черного (red-black)
разбиения (см. Приложение 1).
DO(i,li,hi,si) DO(j,lj+(i+v)%2,hj,2)
4) Для каждого витка цикла элементы массивов в левых частях операторов присваивания тела цикла должны размещаться на том же процессоре, что и элемент базового массива с индексами [v1]...[vN].
5) В левых частях операторов присваивания запрещены размноженные переменные, кроме редукционных переменных (см. 3.3.) и переменных, описанных в теле цикла.
6) При выполнении параллельного цикла не должны встречаться какие-либо другие параллельно выполняющиеся операторы (вложенные параллельные циклы, операторы обмена распределенных массивов с файлами, и т.п.).
Пример:
DVM(PARALLEL [i][j] ON A[i][j])
DO (i,1,10,1)
FOR (j,10)
{ A[i][j] = . . . ;
. . .
B[i][j] = . . . ; }
Очень часто в программе встречаются циклы, в которых выполняются редукционные операции - в некоторой переменной суммируются элементы массива или находится их максимальное или минимальное значение. Эти циклы тоже можно выполнять параллельно, если в префиксах этих циклов указать их редукционные операции и переменные.
Редукционными переменными будем называть переменные, которые вычисляются и используются в цикле в операторах определенного типа - редукционных операторах.
Введем обозначения.
rv - редукционная переменная, которая может быть только размноженной переменной, er - выражение, не содержащее редукционную переменную, ro - одна из 4-х коммутативных операций языка Си (+,*,||,&&).
Редукционными операторами будут операторы в теле цикла следующего вида
1) rv = rv ro er; rv = er ro rv;
2) rv = max(rv,er); rv = max(er,rv);
3) rv = min(rv,er); rv = min(er,rv);
4) if(rv<er) { rv = er;} if(er>rv) { rv = er;}
5) if(rv>er) { rv = er;} if(er<rv) { rv = er;}
6) if(rv<er) { rv = er; I1 = e1;...; In = en;}
7) if(er>rv) { rv = er; I1 = e1;...; In = en;}
8) if(rv>er) { rv = er; I1 = e1;...; In = en;}
9) if(er<rv) { rv = er; I1 = e1;...; In = en;}
Указание для спецификации редукционных операций и переменных помещается в префиксе параллельного цикла после указания PARALLEL и имеет следующий вид
REDUCTION имя-редукции
где имя-редукции задается следующей таблицей
| Вид редукционного оператора | Операция языка С | Имя редукции |
| 1 | + | SUM(rv) |
| 1 | * | PRODUCT(rv) |
| 1 | // | OR(rv) |
| 1 | && | AND(rv) |
| 2, 4 | MAX(rv) | |
| 3, 5 | MIN(rv) | |
| 6, 7 | MAXLOC(rv,I1,...,In) | |
| 8, 9 | MINLOC(rv,I1,...,In) |
Пример спецификации редукций:
DVM(DISTRIBUTE[BLOCK]) float A[1000];
imax = 0;
amax = FLT_MIN; /* минимальное число с плавающей точкой */
s = 0;
DVM(PARALLEL [i] ON A[i]; REDUCTION SUM(s);
REDUCTION MAXLOC(amax, imax))
FOR(i,1000)
{ s = s+A[i];
if (amax < A[i])
{ amax = A[i]; imax = i;
}
}
После спецификаций распределения данных и витков циклов программа готова к параллельному выполнению при условии, что все данные, необходимые процессору, размещены на этом процессоре. Для большинства программ это условие не выполняется. В этой главе описываются средства, позволяющие использовать удаленные данные.
Импортируемыми данными процессора будем называть используемые им удаленные (расположенные на других процессорах) данные. Основной способ “оптимизации” доступа к удаленным данным - уменьшение количества импортируемых данных. Это достигается совместным распределением нескольких массивов (выравнивание массивов).
Рассмотрим следующий пример.
DVM(DISTRIBUTE[BLOCK]) float A[16], float B[32]; DVM(PARALLEL [i] ON B[i]) DO (i,1,15,1) B[i] = A[i];
Если мы имеем в качестве МПС линейку из 4-х процессоров, то массивы будут распределены по процессорам следующим образом.
Процессоры |
P[0] | P[1] | P[2] | P[3] |
Массив A |
(0:3) | (4:7) | (8:11) | (12:15) |
Массив B |
(0:7) | (8:15) | (16:23) | (24:31) |
В операторе присваивания используется одинаковый индекс в левой и правой частях оператора, тем не менее присваивание B[6] = A[6] потребует удаленного доступа. Оператор будет выполняться на процессоре P[0], а A[6] размещено на процессоре P[1].
Это произошло потому, что распределение измерений массивов с разным числом элементов на одно измерение МПС не гарантирует размещение элементов с одинаковыми номерами на одном процессоре. Для этого необходимо их совместное распределение - выравнивание, идея которого заключается в установлении соответствия между элементами двух массивов, которое обязывает располагать такие (соответствующие друг другу) элементы на одном процессоре. При выравнивании массивов возможны следующие виды соответствия и их комбинации:
Выравнивание массивов осуществляется с помощью указания
DVM (ALIGN [sd1]... [sdN] WITH base_array [ard1]. . . [ardm]) descr_array;
| descr_array | - описание выравниваемого массива (статического или динамического) |
| base_array | - базовый массив выравнивания (на который оно производится) |
| sdi | - идентификатор i-го измерения выравниваемого массива |
| ardj | - правило выравнивания на j-ое измерение базового массива |
Возможно задание следующих правил выравнивания:
1) Измерение массива может быть выровнено на одно и только одно измерение базового массива линейной функцией типа aj * sdi + bj где aj и bj - целочисленные константы, sdi - идентификатор измерения массива.
2) Если идентификатор измерения массива не задан, то это измерение массива сжимается (расположение элементов массива не зависит от их индексов в этом измерении - такое измерение будет называться нераспределенным).
3) Избыточные измерения базового массива помечаются либо константой, что означает выравнивание на секцию базового массива, либо [], что означает размножение массива по этому измерению базового массива.
Примеры.
DVM (DISTRIBUTE [BLOCK] [BLOCK]) float B[10][10]; DVM (DISTRIBUTE [BLOCK] ) float D[20]; DVM(ALIGN [i] WITH B[1][i]) float A[10]; /* выравнивание вектора на первую строку B */ DVM(ALIGN [i] WITH B[][i]) float A[10]; /* размножение вектора - выравнивание его на каждую строку B */ DVM(ALIGN [][i] WITH D[i]) float C[20][20]; /* сжатие матрицы - столбец матрицы соответствует элементу вектора */ DVM(ALIGN [i] WITH D[2*i]) float A[10]; /* выравнивание вектора A на вектор D с раздвижкой */ DVM(ALIGN [i] WITH D[-i+19]) float A[20]; /* выравнивание вектора A на вектор D с реверсом */ DVM(ALIGN [i][j] WITH B[j][i]) float C[10][10]; /* выравнивание матрицы C на матрицу B с поворотом */
Теперь рассмотрим следующий пример:
DVM(DISTRIBUTE[BLOCK]) float A[100],B[100],C[100];
DVM(PARALLEL [i] ON A[i])
DO (i,1,98,1)
A[i] = C[i-1] + B[i+1];
Здесь массивы A, B, C распределены одинаково. Но на процессоре, который выполняет i-ый виток цикла (в котором вычисляется A[i]), не всегда размещены элементы C[i-1] и B[i+1]. Чтобы в данном фрагменте не было доступа к удаленным данным необходимо распределить массивы A, B, C так, чтобы для индекса i элементы массивов A[i], B[i+1], C[i-1] были размещены на одном процессоре. Здесь невозможно использовать один массив для выравнивания других массивов, т.к. в этом случае произойдет выход за пределы его индексного пространства. В таких случаях с помощью описания TEMPLATE определяют фиктивный массив - шаблон выравнивания. На шаблон выравниваются другие массивы, а элементы шаблона распределяется между процессорами не требуя никакой памяти для своего размещения. Приведенный выше пример без доступа к удаленным данным может быть специфицирован следующим образом:
DVM(DISTRIBUTE[BLOCK];TEMPLATE [102]) void *TABC;
DVM(ALIGN [i] WITH TABC[i]) float B[100];
DVM(ALIGN [i] WITH TABC[i+1]) float A[100];
DVM(ALIGN [i] WITH TABC[i+2]) float C[100];
DVM(PARALLEL [i] ON A[i])
DO (i,1,98,1)
A[i] = C[i-1] + B[i+1];
Первое предложение описывает имя шаблона и его индексное пространство, а также задает распределение элементов шаблона между процессорами.
В результате применения этих директив мы получим следующую картину отображения:
Витки цикла |
PARALLEL |
A,B,C |
ALIGN |
TABC |
DISTRIBUTE |
P |
(1:24) |
--> |
A( 0:24) |
--> |
(0:25) |
--> |
[0] |
(25:50) |
--> |
A(25:50) |
--> |
(26:51) |
--> |
[1] |
(51:75) |
--> |
A(51:75) |
--> |
(52:76) |
--> |
[2] |
(76:97) |
--> |
A(76:99) |
--> |
(77:101) |
--> |
[3] |
Выравниванием массивов не всегда удается избавиться от доступа к удаленным данным. Рассмотрим следующий пример:
DVM(DISTRIBUTE[BLOCK]) float A[100],B[100];
DVM(PARALLEL [i] ON A[i])
DO (i,2,96,1)
A[i]= (B[i-2]+B[i-1]+ B[i]+B[i+1]+B[i+2]+B[i+3])/6;
Получаем следующую картину отображения витков цикла и элементов массива B на четырех процессорах:
P[0] |
P[1] |
P[2] |
P[3] |
витки(2:24) |
витки(25:49) |
витки(50:74) |
витки(75:97) |
B( 0:24) |
B(25:49) |
B(50:74) |
B(75:99) |
Рассмотрим выполнение некоторых витков цикла на процессоре P[1]:
номер витка |
импортируемые данные |
25 |
B[23], B[24] |
26 |
B[24] |
. . . |
. . . |
47 |
B[50] |
48 |
B[50], B[49] |
49 |
B[50], B[49], B[48] |
Как мы видим, импортируемые данные на левом фланге составляют отрезок B(23:24) длиной 2, на правом фланге - B(48:50) длиной 3. Для многомерных массивов это будут грани импортируемых данных.
Каждая грань имеет ширину грани. Грани импортируемых данных располагаются на соседних (слева и справа) процессорах. Увеличим память локальной секции массива слева и справа на ширину граней импортируемых данных и будем называть эту память теневыми гранями секции массива. Ширина теневой грани секции равна ширине грани импортируемых данных. Картина размещения секций с теневыми гранями будет следующая
P[0] |
P[1] |
P[2] |
P[3] |
B( 0:27) |
B(23:52) |
B(48:77) |
B(73:99) |
Такое распределение массива называется распределением с теневыми гранями. Если перед выполнением цикла скопировать грани импортируемых данных в соответствующие теневые грани, то цикл можно выполнять без доступа к удаленным данным. Максимальная ширина теневых граней задается в указании SHADOW. По умолчанию максимальная ширина теневых граней по каждому измерению равна 1.
Перепись в теневые грани (обновление) осуществляется перед параллельным циклом, если в его префиксе содержится указание SHADOW_RENEW. Указанный выше пример можно переписать следующим образом:
DVM(DISTRIBUTE[BLOCK]; SHADOW[2:3]) float B[100];
DVM(DISTRIBUTE[BLOCK]) float A[100];
DVM(PARALLEL [i] ON A[i]; SHADOW_RENEW B)
DO (i,2,96,1)
A[i]=(B[i-2]+B[i-1]+B[i]+B[i+1]+B[i+2]+B[i+3])/6;
Конструкция [2:3] определяет максимальные размеры теневых граней массива В - слева шириной 2 и справа шириной 3.
В указании SHADOW_RENEW можно уточнить размеры теневых граней (задать меньше, чем было задано при первоначальном описании массива в спецификации SHADOW), а также указать спецификатор CORNER. Этот необязательный спецификатор указывает, что при обновлении теневых граней многомерных массивов необходимо пересылать и угловые элементы (в программе Jacobi из раздела 2 угловые элементы были не нужны).
Пример.
DVM(DISTRIBUTE [BLOCK] [BLOCK]) float (*A)[N],(*B)[N]; A = malloc( N*N*sizeof(float)); B = malloc( N*N*sizeof(float)); DVM(PARALLEL[i][j] ON B[i][j]); SHADOW_RENEW A[1:0][1:0] CORNER) DO (i,1,N-2,1) DO (j,1,N-2,1) B[i][j]=(A[i][j]+A[i-1][j]+A[i][j-1]+A[i-1][j-1])/4;
В правой части оператора присваивания присутствует ссылка на “угловую” удаленную переменную A[i-1][j-1], поэтому в указании обновления теневых граней указан спецификатор CORNER.
Если импортируемые переменные не являются “соседними” и для доступа к ним нельзя использовать теневые грани, то их буферизация осуществляется через отдельный буферный массив. В указании удаленного доступа REMOTE_ACCESS задается, какая часть массива должна быть буферизована на каждом процессоре. Размер этой части определяет размер буфера.
Такое указание может специфицировать как циклы (DO, FOR), так и отдельные операторы, не расположенные в теле параллельного цикла.
Пример.
DVM(DISTRIBUTE [BLOCK] []) float (*A)[N];
A = malloc( N*N*sizeof(float));
for (i=0; i<=N-1; i++)
DVM(PARALLEL [j][k] ON A[j][k]; REMOTE_ACCESS A[i][k]))
FOR (j,N-1)
FOR (k,N-1) {
A[j][k]=A[j][k]-A[j][i]*A[i][k]);
}
Ссылка A[i][k] будет заменена ссылкой на одномерный буферный массив, размер которого на каждом процессоре определяется индексами витков цикла, выполняемых на этом процессоре. Перед выполнением цикла в этот массив на каждом процессоре будут переписаны все требуемые ему для выполнения цикла элементы A[i][k].
Пример программы метода исключения Гаусса, использующей удаленный доступ, приведен в приложении 1.
Обновление значений теневых граней выполняется каждым процессором следующим образом:
На фоне этого ожидания можно выполнять вычисления по внутренним элементам секции массива, если эти два этапа операции обновления теневых граней задавать с помощью отдельных директив (запуск операции и ожидание ее окончания).
Если перед циклом необходимо обновление теневых граней нескольких массивов, то эти операции можно объединить в одну групповую операцию обновления, что также может уменьшить накладные расходы.
Для организации группового асинхронного обновления теневых граней существуют 4 указания:
Описание группы операций:
DVM(SHADOW_GROUP) void *AR;
Директива задания состава группы:
DVM(CREATE_SHADOW_GROUP AR: A B C);
Переменная AR будет содержать ссылку на группу операций обновления граней массивов A, B и C. В этой директиве для каждого массива можно уточнить размеры теневых граней и указать спецификатор CORNER.
Директива запуска обновления теневых граней, т.е. выдача операций посылки и приема экспортируемых данных массивов A, B и C:
DVM(SHADOW_START AR);
Директива ожидания завершения обновления теневых граней:
DVM(SHADOW_WAIT AR);
Ограничения:
Если задать в префиксе параллельного цикла указания SHADOW_START или SHADOW_WAIT , то изменяется порядок выполнения витков цикла на каждом процессоре.
Возможны две схемы изменения порядка выполнения витков параллельного цикла для совмещения вычислений и ожидания теневых граней:
1) Опережающее вычисление экспортируемых данных и рассылка их в теневые грани соседних процессоров.
В префиксе параллельного цикла необходимо задать указание SHADOW_STARTбудет выполняться на каждом процессоре по . В этом случае цикл следующему алгоритму:
- вычисление экспортируемых элементов массивов;
- запуск обновления теневых граней;
- вычисление внутренних (не экспортируемых) элементов локальной секции.
2) Отложенное использование импортируемых данных.
В префиксе параллельного цикла необходимо задать указание SHADOW_WAIT . В этом случае цикл будет выполняться на каждом процессоре по следующему алгоритму:
- выполнение витков, не требующих импортируемых элементов;
- ожидание завершения обновления теневых граней;
- выполнение витков, требующих импортируемых элементов.
Если в префиксе параллельного цикла задано указание REDUCTION, то значение редукционной переменной вычисляется следующим образом:
1) Вычисление локального значения редукционной переменной на каждом процессоре.
2) После окончания цикла выполняется редукционная операция над локальными значениями и исходным значением переменной. Каждый процессор выполняет свою часть работы и ждет получения окончательного результата.
Это ожидание можно совмещать с другими вычислениями. Для реализации такого совмещения определено понятие асинхронной редукции.
Если в цикле (циклах) вычисляются несколько редукций, то их можно объединить в одну групповую асинхронную редукцию.
Для организации групповой асинхронной редукции существуют 4 указания:
Описание групповой редукции:
DVM(REDUCTION_GROUP) void *MAXMIN;
Директива задания состава групповой редукции:
DVM(CREATE_REDUCTION_GROUP MAXMIN: MAX(eps1) MIN(eps2));
Переменная MAXMIN будет содержать ссылку на группу редукций MAX(eps1) и MIN(eps2).
Директива запуска выполнения редукции, когда каждый процессор начинает выполнять свою часть работы по интеграции локальных значений:
DVM(REDUCTION_START MAXMIN);
Директива ожидания результатов групповой редукции каждым процессором:
DVM(REDUCTION_WAIT MAXMIN);
Ограничения:
С использованием асинхронных операций программа метода Якоби, приведенная в главе 2, будет выглядеть следующим образом.
Пример. Программа Jacobi2.
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#define DVM(dvmdir)
#define DO(v,l,u,s) for(v=l; v<=u; v+=s)
#define L 8
#define ITMAX 20
int i,j,it,k;
double eps;
double MAXEPS = 0.5;
FILE *f;
/* описание группы операций обновления теневых элементов */
DVM(SHADOW_GROUP) void *grshad;
/* описание группы редукционных операций */
DVM(REDUCTION_GROUP)void *emax;
/* двумерные массивы, блочно распределенные по 2-м измерениям */
DVM(DISTRIBUTE [BLOCK][BLOCK])
double A[L][L], B[L][L];
main()
{
/* Двумерный параллельный цикл с базовым массивом А */
DVM(PARALLEL [i][j] ON A[i][j])
DO(i,0,L-1,1)
DO(j,0,L-1,1)
{A[i][j]=0.;
B[i][j]=1.+i+j;}
/* Задание состава группы операций обновления теневых граней */
DVM(CREATE_SHADOW_GROUP grshad: A);
/************ итерационный цикл *************************/
DO(it,1,ITMAX,1)
{
eps= 0.;
/* Задание состава групповой редукции */
DVM(CREATE_REDUCTION_GROUP emax : MAX(eps));
/* Параллельный цикл с базовым массивом A: */
/* сначала вычисляем и рассылаем элементы массива A, */
/* экспортируемые соседним процессорам; */
/* затем вычисляем внутренние элементы массива А */
DVM(PARALLEL [i][j] ON A[i][j]; SHADOW_START grshad)
DO(i,1,L-2,1)
DO(j,1,L-2,1)
{eps = max(fabs(B[i][j]-A[i][j]),eps);
A[i][j] = B[i][j];
}
/* Запускаем асинхронное вычисление максимума */
DVM(REDUCTION_START emax);
/* Параллельный цикл с базовым массивом B: */
/* сначала вычисляем внутренние элементы массива B, затем */
/* дожидаемся завершения обновления теневых граней массива A */
/* и выполняем оставшиеся витки цикла, которым требовались */
/* теневые элементы массива A */
DVM(PARALLEL [i][j] ON B[i][j]; SHADOW_WAIT grshad)
DO(i,1,L-2,1)
DO(j,1,L-2,1)
B[i][j] = (A[i-1][j]+A[i+1][j]+
A[i][j-1]+A[i][j+1])/4;
/* Дожидаемся окончания редукции */
DVM(REDUCTION_WAIT emax);
printf( "it=%4i eps=%3.3E\n", it,eps);
if (eps < MAXEPS) break;
}/*DO it*/
f=fopen("jacobi.dat","wb");
fwrite(B,sizeof(double),L*L,f);
return 0;
}
Распределение массивов в одной части программы может быть не эффективным для другой части программы. Согласование распределения фактических и формальных параметров также может потребовать перераспределения массивов.
Синтаксис директивы динамического выравнивания массивов:
DVM (REALIGN array [sd1]... [sdN] WITH base_array [ard1]. . . [ardm] {NEW});
Синтаксис и семантика параметоров sdi и ardj такие же как в директиве ALIGN. В выражении выравнивания aj * sdi + bj коэффициенты aj и bj могут быть любыми целочисленными выражениями.
Особенности применения директивы REALIGN:
Синтаксис директивы динамического распределения:
DVM(REDISTRIBUTE имя-распределенного-объекта rd1 . .. rdn { NEW });
Синтаксис и семантика последовательности-распределений-измерений такие же как и в директиве DISTRIBUTE.
Особенности применения директивы REDISTRIBUTE:
Формальный параметр процедуры, которому может соответствовать фактический параметр - распределенный массив, должен быть специфицирован следующим образом:
а) если фактический параметр - произвольный распределенный массив заданной размерности, то
DVM(*DISTRIBUTE [*]...[*]) описание-формального-параметра
б) если фактический параметр - распределенный массив с известными правилами распределения, то
DVM(*DISTRIBUTE rd1. . . rdN ) описание-формального-параметра
в) если фактический параметр - произвольный распределенный массив или обычный массив языка Си, то
DVM(*) описание-формального-параметра
Такие формальные параметры можно использовать только в операциях бесформатного ввода-вывода массива целиком.
Замечание. Аналогично должны быть специфицированы заголовки функций, значениями которых является распределенные массивы, а также указатели на массивы, значения которых задается не при создании массива, а посредством присваивания значений других указателей.
Вызов процедуры осуществляется на том процессоре, где был распределен виток цикла. Поэтому все условия параллельного цикла распространяются на операторы вызова процедур.
Это приводит к следующим ограничениям:
В CDVM-программе для размноженных данных допускаются следующие операторы ввода-вывода:
fopen, fclose, feof, fprintf, prinf, fscanf, scanf, fputc, putc, fputs, puts, fgetc, getc, fgets, gets, fflush, fseek, ftell, ferror, clearerr, perror, а также fread, fwrite.
Эти операторы выполняются на одном процессоре, специально выделяемым для этой цели системой поддержки выполнения программы. Выводимые значения берутся с данного процессора, а вводимые значения вводятся на данном процессоре и рассылаются на остальные.
Для распределенных массивов допускается только бесформатный ввод-вывод массива целиком (в стандартном порядке элементов). В исходной программе он должен быть записан как оператор fread (fwrite) c идентификатором массива в качестве указателя на область памяти и длиной области.
Указанные операторы (за исключением операторов печати) не могут использоваться в параллельном цикле.
Замечание. .Использование операторов печати в параллельном цикле может привести к нарушению порядка следования и формата распечатываемой информации.
Язык C-DVM был использован для программирования нескольких тестов, включая TOMCATV из Spec92 и Spec95. Кроме того, с использованием языка C-DVM был переписан модуль расчета нейтронных полей в диффузионном приближении в трехмерной X-Y-Z геометрии, входящий в состав пакета прикладных программ РЕАКТОР [Arz91]. При выполнении на МВС-100 были получены следующие временные характеристики C-DVM программ: Yakobi, TOMCATV и решения главной спектральной задачи для английской критсборки ZEBRA [ChS94].
Yakobi (2 массива 900*900)
N |
1 |
2*1 |
4*1 |
4*2 |
4*4 |
4*6 |
4*8 |
E |
100% |
98% |
96% |
90% |
77% |
64% |
51% |
TOMCATV (7 массивов 257*257)
N |
1 |
2*1 |
4*1 |
8*1 |
16*1 |
24*1 |
32*1 |
E |
100% |
99% |
93% |
79% |
53% |
34% |
23% |
ZEBRA (28 массивов 16*31*61)
N |
1 |
2*1 |
4*1 |
8*1 |
2*8 |
2*16 |
E |
100% |
98% |
95% |
88% |
80% |
73% |
ZEBRA (28 массивов 16*31*61)
N |
16*2 |
1*32 |
8*4 |
4*8 |
2*16 |
E |
60% |
65% |
70% |
70% |
73% |
N
- количество процессоров (топология
- двумерная решетка)
E - коэффициент
эффективности распараллеливания.
Первый опыт использования языка C-DVM показал, что эффективность выполнения полученных программ не ниже эффективности выполнения тех программ, которые написаны на языках, базирующихся на модели передачи сообщений.
Кроме того, стало ясно, что важным достоинством программ на языке C-DVM является их способность динамически (без перетрансляции) настраиваться на исходные данные задачи (количество и размеры массивов) и конфигурацию параллельной машины. Это существенно упрощает использование и сопровождение параллельной программы.
KKM94 N.A.Konovalov, V.A.Krukov, S.N.Mihailov and A.A.Pogrebtsov, “Fortran-DVM language for portable parallel programs development”, Proceedings of Software For Multiprocessors & Supercomputers: Theory, Practice, Experience (SMS-TPE 94),Inst. for System Programming RAS, Moscow, Sept. 1994.
Wal94 David W. Walker, “The design of a standard message-passing interface for distributed memory concurrent computers”, Parallel Computing”, v. 20, n 4, April 1994, 657-673.
GBD93 A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, V. Sunderam, “PVM 3 User’s Guide and Reference Manual”, Technical report, Oak Ridge National Laboratory ORNL/TM-12187 (1993).
KPZ93 V.A.Krukov, L.A.Pozdnjakov and I.B.Zadykhailo, ‘’RAMPA - CASE for portable parallel programs development’’, Proc. of the International Conference on Parallel Computing Technologies, Obninck, Russia, Aug30-Sept 4, 1993.
ZLK95 A.V.Zabrodin, V.K.Levin, V.V.Korneev. The Massively Parallel Computer System МВС-100. Third International Conference PaCT-95. Parallel Computing Technologies. Springer 964, 1995. p.341-356.
ЛаЛ94 Лацис А.О., Луцкий А.Е. Численное решение задач сверхзвукового обтекания на многопроцессорной вычислительной системе. Вестник российского общества информатики и вычислительной техники. 1994, N3, Москва, ВИМИ, стр.19-24.
Arz91 V.I.Arzhanov. REACTOR - Program system for Neutron Physical Calculation. Advances in Mathematics, Computations and Reactor Physics. Pittsburg, PA, USA, 1991.
ChS94 A.N.Chebesko, E.P.Sychugova. Low reactivity sosodium-void benchmark study in annular heterogeneous assembly. Proceedings International Topical Meeting on Fast Reactor Safety, IPPE, 1994, Obninsk.
| Оглавление | Часть 1 | C-DVM - часть 2 | Часть 3 |