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

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

где:

1. Массив уничтожается оператором free( arrid );

2. Ссылка на элемент массива записывается как обычно: arrid [ ind₁]...[ ind_n ].

Компилятор C-DVM преобразует эти конструкции в корректные описания и обращения к системе поддержки. Но чтобы программа могла транслироваться как последовательная обычным Cи компилятором, все размерности dim_i (кроме первой) должны быть константами. Предлагается в точке определения массива временно переопределить их как константы (#define dim_i const …#undef dim_i). Компилятор удаляет эти переопределения, точнее, перемещает их в начало файла. Естественно, что фактические («вычисленные» в переменных) размерности при последовательном выполнении должны совпадать с выбранными константными значениями. (см. пример Красно-черного SOR в Приложении 1).

Пример определения массива.

DVM(DISTRIBUTE [BLOCK][BLOCK]) float (*C)[N];
/* two-dimensional distributed array */

4.2.3Моделирование многомерных массивов одномерными

Для работы с многомерными динамическими массивами в Cи используется и другой метод. Создается (одномерная) область памяти нужного размера, а для доступа к элементам “многомерного массива” используется макрос arrid(ind₁,...,ind_n), который вычисляет позицию элемента с указанными индексами в отведенной массиву области памяти. В этом случае обращения к массивам выглядят так же, как в Фортране.

Такой способ работы тоже поддерживается компилятором C-DVM.

• Массив описывается как указатель (на скаляры),

• создается оператором arrid=malloc(dim₁*dim₂...*sizeof(elem_type)),

• уничтожается оператором free(arrid),

• обращения к элементам массива в форме arrid(ind₁,...,ind_n) распознаются компилятором и заменяются соответствующей конструкцией.

Пример описания массива (одномерный для последовательной программы, но двумерный для параллельного выполнения) и ссылки на его элементы:

int Cdim2; /* The second dimension of array C */

DVM(DISTRIBUTE [BLOCK][]) float *C;

#define C(x,y) C[(x)*Cdim2+(y)]

. . .

C(i,j) = (C(i,j-1)+C(i,j+1))/2;

4.3Распределение выравниванием

Выравнивание массива А на распределенный массив В ставит в соответствие каждому элементу массива А элемент или секцию массива В. Распределение элементов массива В определяет распределение элементов массива А. Если на некоторый процессор распределен элемент В, то на этот же процессор будут распределены элементы массива А, поставленные в соответствие с ним выравниванием.

Метод распределения через выравнивание выполняет следующие две функции.

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

2. На один массив может быть выравнено несколько массивов. Изменение распределения одного массива директивой REDISTRIBUTE вызовет соответствующее изменение распределения группы массивов.

4.3.1Директивы ALIGN и REALIGN

Выравнивание массива описывается следующими директивами:

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

• Длина списка align-source... должна быть равна количеству измерений выравниваемого массива.

• Длина списка align-subscript... должна быть равна количеству измерений базового массива align-target.

• Отсутствие align-directive-stuff допустимо только в директиве ALIGN. В этом случае распределяемый массив может использоваться только после выполнения директивы REALIGN.

Пусть задано выравнивание двух массивов с помощью директивы

DVM(ALIGN [d₁]…[d_n] WITH B[ard₁]…[ard_m]) float A[100]…[100];

где

d_i - спецификация i-го измерения выравниваемого массива А,

ard_j - спецификация j-го измерения базового массива В.

Если d_i задано целочисленной переменной I, то обязательно должно существовать одно и только одно измерение массива В, специфицированное линейной функцией ard_j = a*I + b. Следовательно, количество измерений массива А, специфицированных идентификаторами (align-dummy) должно быть равно количеству измерений массива В, специфицированных линейной функцией.

Пусть i-ое измерение массива А имеет размер A_i, а j-ое измерение массива В, специфицированное линейной функцией a*I + b, имеет размер B_j. Т.к. параметр I определен над множеством значений 0…A_i-1, то должны выполняться следующие условия:

b  0; а*(A_i –1)+ b < B_j

Если d_i пусто, то i-ое измерение массива А будет локальным на каждом процессоре при любом распределении массива В (аналог локального измерения в директиве DISTRIBUTE ).

Если ard_i пусто, то массив А будет размножен по j-му измерению массива В (аналог частичного размножения по массиву процессоров).

Если ard_i = int-expr, то массив А выравнивается на секцию массива В.

Пример 4.7. Выравнивание массивов

DVM(DISTRIBUTE [BLOCK][BLOCK]) float B[10][10];

DVM(DISTRIBUTE [BLOCK]) float D[20];

/* aligning the vector A with the first line of B) */

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

/* replication of the vector aligning it with each line */

DVM(ALIGN [i] WITH B[][i]) float F[10];

/* collaps: each column corresponds to the vector element */

DVM(ALIGN [][i] WITH D[i]) float C[20][20];

/* alignment using stretching */

DVM(ALIGN [i] WITH D[2*i]) float E[10];

/* alignment using rotation and stretching */

DVM(ALIGN [i][j] WITH C[2*j][2*i] ) float H[10,10];

Пусть заданы выравнивания f1 и f2, причем f2 - выравнивает массив В по массиву С, а f1 - выравнивает массив А массиву В. По определению массивы А и В считаются выровненными на массив С. Массив В выровнен непосредственно функцией f2, а массив А выровнен опосредовано составной функцией f1(f2). Поэтому применение директивы REALIGN к массиву В не вызовет перераспределения массива А.

В общем случае множество спецификаций ALIGN образует лес деревьев. При этом корень каждого дерева должен быть распределен директивами DISTRIBUTE или REDISTRIBUTE. При выполнении директивы REDISTRIBUTE перераспределяется все дерево выравниваний.

4.3.2Директивы TEMPLATE и CREATE_TEMPLATE

Если значения линейной функции a*I + b выходят за пределы измерения базового массива, то необходимо определить фиктивный массив - шаблон выравнивания следующей директивой:

Затем необходимо произвести выравнивание обоих массивов на этот шаблон. Шаблон распределяется с помощью директив DISTRIBUTE и REDISTRIBUTE. Элементы шаблона не требуют памяти, они указывают процессор, на который должны быть распределены элементы выровненных массивов.

Рассмотрим следующий пример.

Пример 4.8. Выравнивание по шаблону.

DVM(DISTRIBUTE [BLOCK]; TEMPLATE[102]) void * TABC;

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

DVM(ALIGN A[i] WITH TABC[i+1]) float A[100];

DVM(ALIGN C[i] WITH TABC[i+2]) float C[100];

. . .

DO(i,1, 98,1)

A[i] = C[i-1] + B[i+1];

Если размеры шаблона (и массивов) не известны статически, то следует использовать следующую выполняемую директиву:

Пример 4.9. Выравнивание по динамическому шаблону.

DVM(DISTRIBUTE [BLOCK]; TEMPLATE ) void *TABC;

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

DVM(ALIGN A[i] WITH TABC[i+1]) float *A;

DVM(ALIGN C[i] WITH TABC[i+2]) float *C;

int N;

. . .

N= ... /* вычисляем размер */...;

DVM(CREATE_TEMPLATE TABC[N]);

A=malloc(N*sizeof(float));

B=malloc(N*sizeof(float));

C=malloc(N*sizeof(float));

. . .

DO(i,1, N-2,1)

A[i] = C[i-1] + B[i+1];

4.4Нераспределяемые данные

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

5Распределение вычислений

5.1Параллельные циклы

5.1.1Определение параллельного цикла

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

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

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

• цикл является тесно-гнездовым циклом с прямоугольным индексным пространством; (исключение см. Пример 4 в Приложении 1);

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

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

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

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

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

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

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

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

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

Список файлов учебной работы