1 Введение

Язык C-DVM предназначен для разработки мобильных и эффективных параллельных программ вычислительного характера. Он представляет собой расширение языка Си в соответствии с моделью DVM, разработанной в ИПМ им М.В.Келдыша РАН [1].

Вычислительные программы для последовательных ЭВМ традиционно создавались на языках Фортран 77 и Cи. Для многопроцессорных ЭВМ с распределенной памятью и сетей ЭВМ такие программы в настоящее время, как правило, создаются на языках Фортран 77 и Cи, расширенных библиотеками передачи сообщений (PVM, MPI). Разработка таких параллельных программ требует от прикладного программиста гораздо больших усилий, чем разработка последовательных программ, поскольку ему требуется не только распределить данные и вычисления между разными процессорами, но и организовать взаимодействие процессоров посредством обмена сообщениями. Фактически, параллельная программа представляет собой систему взаимодействующих программ, каждая из которых выполняется на своем процессоре. Программы на разных процессорах могут быть совершенно различными, могут различаться лишь незначительно, а могут являться одной программой, поведение которой зависит от номера процессора. Но даже в этом последнем случае, программист обычно вынужден разрабатывать и сопровождать два различных варианта своей программы -- последовательный и параллельный.

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

Таким образом, язык C-DVM представляет собой стандартный язык Си, дополненный средствами спецификации параллельного выполнения программы:

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

Для создания программ на языке C-DVM служит специальная система автоматизации разработки параллельных программ – DVM-система.

DVM-система предоставляет единый комплекс средств для разработки параллельных программ научно-технических расчетов на языках Си и Фортран 77.

Модель параллелизма DVM. Модель параллелизма DVM базируется на модели параллелизма по данным. Аббревиатура DVM отражает два названия модели: распределенная виртуальная память (Distributed Virtual Memory) и распределенная виртуальная машина (Distributed Virtual Mashine). Эти два названия указывают на адаптацию модели DVM как для систем с общей памятью, так и для систем с распределенной памятью. Высокоуровневая модель DVM позволяет не только снизить трудоемкость разработки параллельных программ, но и определяет единую формализованную базу для систем поддержки выполнения, отладки, оценки и прогноза производительности.

Языки и компиляторы. В отличие от стандарта HPF в системе DVM не ставилась задача полной автоматизации распараллеливания вычислений и синхронизации работы с общими данными. С помощью высокоуровневых спецификаций программист полностью управляет эффективностью выполнения параллельной программы.

Единая модель параллелизма встроена в языки Си и Фортран 77 на базе конструкций, которые “невидимы” для стандартных компиляторов, что позволяет иметь один экземпляр программы для последовательного и параллельного выполнения. Компиляторы с языков C-DVM и Fortran DVM переводят DVM-программу в программу на соответствующем последовательном языке (Си или Фортран 77) с вызовами функций системы поддержки параллельного выполнения (Lib-DVM). Поэтому единственным требованием к параллельной системе является наличие компиляторов с языков Си и Фортран 77.

Технология выполнения и отладки. Единая модель параллелизма позволяет иметь для двух языков единую систему поддержки выполнения и, как следствие, единую систему отладки, анализа и прогноза производительности. Выполнение и отладка DVM-программ может осуществляться в следующих режимах:

• Последовательное выполнение и отладка средствами стандартных компиляторов с языков Си и Фортран 77.
• Псевдо-параллельное выполнение и отладка на рабочей станции (среда WINDOWS и UNIX).
• Параллельное выполнение и отладка на параллельной ЭВМ.

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

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

2 Обзор языка

2.1 Модель программирования и модель параллелизма

Язык C-DVM является расширением ANSI-C специальными аннотациями (DVM-директивами). Директивы записываются как параметры макроса

DVM(<directive>)

который в последовательной программе “расширяется” в пустую строку.

DVM-директивы могут быть условно разбиты на три класса:

• директивы распределения данных (раздел 4);
• директивы распределения вычислений (разделы 5, 7);
• спецификации удаленного доступа (раздел 6).

Модель параллелизма DVM базируется на специальной форме параллелизма по данным: одна программа – множество потоков данных (SPMD). В этой модели одна и та же программа выполняется на каждом процессоре, но каждый процессор выполняет свое подмножество операторов в соответствии с распределением данных.

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

На следующем этапе определяются массивы, которые должны быть распределены между процессорами (распределенные данные). Эти массивы специфицируются директивами отображения данных (раздел 4). Остальные переменные (распределяемые по умолчанию) отображаются по одному экземпляру на каждый процессор (размноженные данные). Размноженная переменная должна иметь одно и то же значение на каждом процессоре за исключением переменных в параллельном цикле (разделы 5.1.3, 5.1.4 и 7.5).

Распределение данных определяет множество локальных или собственных переменных для каждого процессора. Множество собственных переменных определяет правило собственных вычислений: процессор присваивает значения только собственным переменным.

Модель DVM определяет два уровня параллелизма:

• параллелизм по данным;
• параллелизм задач.

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

Параллелизм задач реализуется распределением данных и вычислений на (разные) секции массива процессоров (раздел 7).

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

2.2 Синтаксис директив C-DVM

Синтаксис DVM-директив описывается расширенной БНФ. Используются следующие обозначения:

Синтаксис директив.

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

• Описательные директивы (specification-directive) пишутся перед описаниями Си распределяемых массивов данных или DVM-объектов.
• Выполняемые директивы (executable-directive) пишутся перед операторами Си (или точкой с запятой – т.е. пустым оператором).

3 Массивы виртуальных процессоров. Директива PROCESSORS

Директива PROCESSORS определяет один или несколько массивов виртуальных процессоров на текущем множестве физических процессоров.

Синтаксис:

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

Замечание1. Массив процессоров описывается в Си как массив типа void*.

Замечание2. Чтобы программа компилировалась как последовательная в ней должно присутствовать определение:

#define NUMBER_OF_PROCESSORS()  1

Пример 3.1. Описание массивов виртуальных процессоров.

DVM(PROCESSORS)  void  *P[N];
DVM(PROCESSORS)  void  *Q[NUMBER_OF_PROCESSORS()],
		       *R[2][NUMBER_OF_PROCESSORS()/2];

В этом примере значение N должно быть равно значению функции NUMBER_OF_PROCESSORS ( ) и оба должны быть четными.

4 Распределение данных

C-DVM поддерживает распределение блоками (равными и неравными) и распределение через выравнивание.

4.1 Директивы DISTRIBUTE и REDISTRIBUTE

Синтаксис:

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

• Длина списка dist-format... должна быть равна количеству измерений массива. Т.е. для каждого измерения должен быть задан формат распределения.
• Количество распределяемых измерений массива (формат не ‘[ ]’) не должно превышать количество измерений dist-target. По лишним измерениям dist-target (может быть, даже по всем, когда нет распределяемых измерений массива) данные размножаются.
• Массив block-array-name в спецификации GENBLOCK, должен быть одномерным целочисленным массивом, размер которого равен размеру соответствующего измерения массива процессоров, а сумма значений его элементов равна размеру распределяемого измерения.
• Отсутствие dist-directive-stuff допустимо только в директиве DISTRIBUTE. В этом случае распределяемый массив может использоваться только после выполнения директивы REDISTRIBUTE.
• Спецификация ONTO указывает массив или секцию массива виртуальных процессоров. Если спецификация ONTO не указана, то распределение осуществляется по текущему массиву виртуальных процессоров.
• Спецификация NEW в директиве REDISTRIBUTE означает, что содержимое массива копировать не нужно, оно будет заново вычисляться.

Рассмотрим форматы распределения для одного измерения массива (одномерный массив A[N]) и для одного измерения массива процессоров (одномерный массив R[P]). Многомерные распределения рассматриваются в разделе 4.1.4.

4.1.1 Формат BLOCK

Измерение массива распределяется последовательно блоками по [N/P] элементов. Если размерность не делится нацело, то образуется один частично заполненный и, возможно, несколько пустых блоков.

Пример 4.1. Распределение по формату BLOCK.

4.1.2 Формат GENBLOCK

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

Пусть NB[P] - массив целых чисел. Следующая директива

DVM(DISTRIBUTE [ GENBLOCK(NB) ] ONTO R) float A[N];

разделяет массив A на P блоков. Блок i размера NB[i] распределяется на процессор R[i]. При этом должно выполняться равенство

Пример 4.2. Распределение неравными блоками.

4.1.3 Формат WGTBLOCK

Формат WGTBLOCK определяет распределение блоками по их относительным “весам”.

Пусть задан формат WGTBLOCK(WB, NBL).

WB(i) определяет вес i-го блока для 0 <= i <= NBL-1. Блоки распределяются на P процессоров с балансировкой сумм весов блоков на каждом процессоре. При этом должно выполняться условие P <= NBL.

Определим вес процессора как сумму весов всех блоков, распределенных на него. Измерение массива распределяется пропорционально весам процессоров.

Формат BLOCK является частным случаем формата WGTBLOCK(WB,P), где WB(i) = 1 для 0 <=  i <=  P-1 и NBL = P.

Формат GENBLOCK с некоторой точностью является частным случаем формата WGTBLOCK.

Пример 4.2 можно переписать с использованием формата WGTBLOCK следующим образом.

Пример 4.3. Распределение блоками по весам.

В примере 4.3 P = 4 и распределение идентично примеру 4.2.

В отличие от распределения неравными блоками, распределение по формату WGTBLOCK можно выполнить для любого числа процессоров в диапазоне 1 <=  P <=  NBL. Для данного примера размер массива процессоров R может меняться от 1 до 12.

4.1.4 Формат []

Формат ‘[ ]’ означает, что измерение не распределяется, т.е. присутствует на каждом процессоре целиком.

4.1.5 Многомерные распределения

При многомерных распределениях формат распределения указывается для каждого измерения. Между измерениями распределяемого массива и массива процессоров устанавливается следующее соответствие.

Пусть массив процессоров имеет n измерений. Пронумеруем измерения массива без формата ‘[ ]’ слева направо d₁, ..., d_k.. Тогда измерение d_i будет распределяться на i-ое измерение массива процессоров. При этом должно выполняться условие k<=n.

Пример 4.3. Одномерное распределение.

Пример 4.4. Двумерное распределение.

4.2 Многомерные динамические массивы

4.2.1 Динамические массивы в языке Си

DVM-система имеет расширенные возможности работы с динамическими массивами. Она позволяет создавать многомерные массивы, размеры которых по всем измерениям определяются во время выполнения. (Язык Cи позволяет не определять статически только старшую размерность). Многомерные массивы разных размеров (а иногда и размерностей) можно передавать как параметры. В языке C-DVM предлагаются два способа работы с многомерными динамическими массивами. Первый основан на использовании многомерных массивов Cи. Второй состоит в моделировании многомерных массивов одномерными.

4.2.2 Использование многомерных массивов Си

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

1. n-мерный массив описывается как указатель на (n-1)-мерные массивы:
   elem_type (*arrid)[dim₂]...[dim_n];
   В частности, одномерный массив описывается как указатель (на скаляры):
   elem_type *arrid;
2. Создание массива выполняется оператором:
   arrid = malloc ( dim₁*dim₂...*sizeof ( elem_type ));
   где:

   elem_type	- тип элемента массива,
   arrid	- идентификатор массива,
   dimi	- размер по i-му измерению.

3. Массив уничтожается оператором free( arrid );
4. Ссылка на элемент массива записывается как обычно: arrid [ ind₁]...[ ind_n ].

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

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

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

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, указав для каждого измерения формат [ ]. Но в этом случае доступ к данным будет менее эффективным.