C-DVM — язык разработки мобильных параллельных программ

 Н.А.Коновалов, В.А.Крюков, Ю.Л.Сазанов

Институт прикладной математики им. М.В.Келдыша
Российской академии наук

125047 Москва, Миусская пл., 4

Аннотация

Язык С-DVM предназначен для разработки мобильных и эффективных параллельных программ вычислительного характера. Он представляет собой расширение языка Си в соответствии с моделью DVM (Distributed Virtual Machine, Distributed Virtual Memory), разработанной в ИПМ им. М.В.Келдыша РАН. В язык включены следующие основные возможности описания параллелизма: распределение элементов массива между процессорами; распределение витков цикла между процессорами; организация эффективного доступа к удаленным (расположенным на других процессорах) данным; организация эффективного выполнения глобальных операций с расположенными на различных процессорах данными (таких, как суммирование элементов распределенных массивов).

Оглавление

1. Введение
2. Краткий обзор модели параллелизма C-DVM
3. Описание параллелизма программы
      3.1. Многопроцессорная система
      3.2. Распределение данных
       3.3. Распределение вычислений
4. Организация доступа к удаленным данным
      4.1. Совместное распределение (выравнивание) массивов
      4.2. Теневые грани локальных секций массива
      4.3. Буферный массив
5. Совмещение счета и обменов данными между процессорами
      5.1. Асинхронное обновление теневых граней
      5.2. Асинхронная редукция
6. Заключение
Список литературы

1. Введение

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

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

Таким образом, язык C-DVM представляет собой стандартный язык Си, дополненный средствами описания правил параллельного выполнения программ (DVM-указаниями).

Компилятор C-DVM работает в среде MS-DOS (или WINDOWS 95) и переводит программу на языке C-DVM в программу на стандартном языке Cи, расширенную функциями библиотеки Lib-DVM (системы поддержки выполнения DVM-программ). На распределенных системах эта программа загружается на все процессоры, выделенные для выполнения параллельной программы. Для организации межпроцессорного взаимодействия библиотека Lib-DVM использует средства коммуникационных библиотек MPI [2], PVM [3], Lib-GNS [4] или Router [6].

Отладка программ осуществляется следующим образом.

Сначала программа отлаживается на рабочей станции как обычная последовательная программа с использованием штатных средств отладки. Затем на той же рабочей станции программа пропускается в специальном режиме проверки DVM-указаний, что позволяет выявить их правильность и полноту. На следующем этапе программа может быть пропущена на параллельной машине (или ее модели, например MPI-машине в среде Windows95 или UNIX) в режиме сравнения ее промежуточных результатов с эталонными, полученными, например, при ее последовательном выполнении.

Для отладки программы на реальной параллельной машине служат средства накопления трассировки. Трассировочная информация для каждого процессора накапливается в его оперативной памяти или записывается в файл. Для МВС-100 [5] созданы средства “посмертной” выгрузки трассировочной информации из памяти всех процессоров и определения состояния программы на каждом процессоре.

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

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

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

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

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

2. Краткий обзор модели параллелизма C-DVM

При распараллеливании программы на системах с распределенной памятью необходимо выполнить следующие действия:

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

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

Распределение данных в языке С-DVM осуществляется путем “разрезания” некоторых массивов на части и размещения этих частей на разных процессорах. Такое “разрезание” осуществляется путем разделения какого-то измерения массива на примерно равные по длине отрезки. При этом многопроцессорная система из N процессоров, на которой будет выполняться параллельная программа, может рассматриваться не только как линейка процессоров, но и как многомерная решетка (или матрица) процессоров, например, как двумерная решетка размера N1 на N2 (N1*N2=N). В этом случае одно из измерений массива может быть разделено на N1 отрезков, а какое-либо другое — на N2 отрезков. В результате массив будет разрезан на N1*N2 частей (секций массива), каждая из которых будет отображена на соответствующий процессор двумерной решетки. Такие массивы называются распределенными массивами. Остальные массивы (как и скаляры) называются размноженными и размещаются на каждом процессоре целиком.

Распределение вычислений должно производиться согласованно с распределением вычисляемых данных. Каждый процессор может вычислять значения только тех переменных, которые на нем размещены. Программист может объявить некоторые циклы в своей программе параллельными и указать для каждого из них его “базовый” массив. В этом случае витки этих циклов будут выполняться на тех процессорах, на которых размещены соответствующие элементы их “базовых” массивов. Операторы, расположенные вне параллельного цикла, выполняются на всех процессорах и, следовательно, могут вычислять только значения размноженных переменных.

Цикл может быть объявлен параллельным только в том случае, когда его витки могут выполняться в произвольном порядке. Например, если при выполнении любого витка цикла не изменяются данные, используемые другими витками, то такой цикл может выполняться параллельно. Однако, очень часто в программе встречаются циклы, в которых выполняются редукционные операции — в некоторой переменной суммируются элементы массива или находится их максимальное или минимальное значение. При объявлении таких циклов параллельными требуется специфицировать выполняемые в них редукционные операции.

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

На рис. 1 приведен пример простейшей параллельной программы (решение уравнения Лапласа методом Якоби), а на рисунке 2 приведена схема отображения ее массивов на процессоры. Для понимания примера и схемы важное значение имеют следующие особенности реализации языка:

• DVM-указания оформляются как параметры специальной макрокоманды DVM(dvmdir), которая в последовательной программе игнорируется (заменяется на пустую последовательность символов). DVM-указания могут использоваться либо как префиксы к конструкциям языка Си, либо как самостоятельные выполняемые операторы. В первом случае они будут называться DVM-описаниями, а во втором — DVM-директивами.
• Макроопределение DO(v,l,u,s) заменяет заголовок цикла for (v = l; v <= u; v += s) и позволяет указать в программе те циклы, которые аналогичны DO-циклам Фортрана (в теле которых индексы, шаг и предельные значения изменяться не могут). Только такие циклы могут быть объявлены в программе параллельными.
• Для упрощения доступа к удаленным данным, находящимся на соседних процессорах, расположенные на каждом процессоре секции распределенного массива расширяются дополнительными (теневыми) элементами — копиями импортируемых элементов массива.

Рис. 1. Программа Jacobi.

#include <math.h>
#include <stdlib.h>
#include <stdio.h>
/* пустая макрокоманда */
/* для обычного компилятора С */
#define DVM(dvmdir)
/* макро для DVM-циклов */
#define DO(v,l,h,s) for(v=l;v<=h;v+=s)
#define  L  8
#define  ITMAX 20
    int i,j,it,k;
    double eps;
    double MAXEPS   = 0.5;
    FILE *f;
/* двумерные массивы, блочно распределенные по 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;}
/********* итерационный цикл  **********/
DO(it,1,ITMAX,1)
  {eps= 0.;
/* Параллельный цикл с базовым массивом A и         */
/* вычислением максимума в переменной eps           */
DVM(PARALLEL [i][j] ON A[i][j];
    REDUCTION MAX(eps))
  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];}
/* Параллельный цикл с базовым массивом B и         */
/* c предварительным обновлением теневых элементов массива A */
DVM(PARALLEL [i][j] ON B[i][j];
    SHADOW_RENEW A)
  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.;
  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;
}

3. Описание параллелизма программы

3.1. Многопроцессорная система

Параллельная программа разрабатывается для многопроцессорной системы с распределенной памятью (МПС), которую программист представляет в виде прямоугольной многомерной решетки процессоров. Такое представление позволяет ему компактно и наглядно описывать распределение данных и вычислений. При запуске программы пользователь задает размерность (количество измерений) МПС и количество процессоров в каждом измерении. При этом заданная размерность не может быть меньше той, из которой исходил программист при описании распределения данных и вычислений. Указания о количестве процессоров влияют на эффективность выполнения программы, но не могут повлиять на результаты выполнения правильно написанной программы.

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

3.2.1. Способы отображения данных

Модель отображения данных является подмножеством модели HPF [13].

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

Скалярные переменные всегда являются размноженными переменными.

Указание DISTRIBUTE может применяться как к статическим, так и к динамическим массивам следующим образом:

DVM (DISTRIBUTE rd₁. . . rd_N) описания-массивов ;

Для каждого измерения массива указывается тип распределения измерения:

• rd_i = [BLOCK] — индексы i-го измерения (распределенного измерения массива) непрерывными интервалами отображаются на процессоры очередного измерения МПС. Количество спецификаций BLOCK (количество распределенных измерений массива) не должно превосходить число измерений МПС;
• rd_i = [ ] — индексы измерения не распределяются между процессорами, а целиком отображаются на каждый процессор (нераспределенное измерение массива).
• описания-массивов — список объявлений распределяемых массивов, указателей на распределяемые массивы или массивов указателей на распределяемые массивы.

3.2.2. Организация работы с динамическими массивами

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

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

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

1. n-мерный массив описывается как указатель на (n-1)-мерный массив, т.е.

<elem_type> (*arrid)[dim₂]…[dim_n];

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

<elem_type> *arrid;

2. Инициализация указателя и запрос памяти под n-мерный массив осуществляется динамически оператором

arrid = malloc(dim₁ * dim₂ *… * elem_size);

Здесь

elem_type —  тип элемента,
elem_size  —  размер элемента в байтах,
arrid            —  имя (идентификатор) массива,
ind_i              —  i-ый индекс массива.
dim_i            —  размер i-го измерения массива.

Моделирование многомерных массивов с помощью одномерных.

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

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

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

3.3.1. Правило собственных вычислений

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

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

Определение “своих” операторов и пропуск “чужих” операторов может вызывать значительные накладные расходы при выполнении программы. Чтобы избежать их, на C-DVM программу накладываются следующие ограничения:

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

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

3.3.2. Отображение витков цикла

С целью дальнейшего снижения накладных расходов отображение витков параллельного цикла осуществляется блочно — на каждый процессор отображается сразу несколько соседних витков цикла. Кроме того, если имеется гнездо тесно вложенных циклов, между заголовками которых нет других операторов, то оно может быть специфицировано как единый многомерный параллельный цикл.

Для спецификации параллельного цикла служит DVM-описание

DVM (PARALLEL [j₁]…[j_N] ON имя-массива [v₁]…[v_N])

которое задает отображение витков цикла косвенно — посредством задания соответствия между витками и элементами базового распределенного массива (виток цикла с индексами [j₁]…[j_N] отображается на тот процессор, на котором расположен элемент базового массива с индексом [v₁]…[v_N]). При этом индексные выражения v_i должны быть линейными выражениями вида v_i =a_i* j_i + b_i, где a_i и b_i — выражения, значения которых будут вычислены при входе в цикл.

3.3.3. Редукционные переменные

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

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

Указание для спецификации редукционных операций и переменных помещается в префиксе параллельного цикла после указания PARALLEL и имеет следующий вид

REDUCTION имя-редукции

где имя-редукции может иметь одно из следующих значений: SUM, PRODUCT, OR, AND, MAX, MIN, MAXLOC, MINLOC.

4. Организация доступа к удаленным данным

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

Импортируемыми данными процессора будем называть используемые им удаленные (расположенные на других процессорах) данные. Основной способ “оптимизации” доступа к удаленным данным — уменьшение количества импортируемых данных. Это достигается совместным распределением нескольких массивов (выравнивание массивов).

4.1.  Совместное распределение (выравнивание) массивов

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

• совмещение двух массивов одинаковой формы (одинаковой размерности и с одинаковыми размерами в каждом измерении)
• совмещение двух массивов одинаковой формы с реверсом (первому элементу одного массива соответствует последний элемент другого)
• совмещение двух массивов с поворотом (j-ое измерение одного массива совмещается с k-ым измерением другого)
• вложение меньшего массива в больший со сдвигом, не приводящим к выходу за пределы большего массива
• вложение меньшего массива в больший с раздвижкой (например, каждому элементу первого массива с индексом i соответствует элемент второго массива с индексом 2*i)
• размножение массива меньшей размерности
• отображение массива меньшей размерности на секцию другого массива, получающуюся путем фиксации индексов в некоторых его измерениях
• сжатие измерения массива большей размерности

4.2. Теневые грани локальных секций массива

Выравниванием массивов не всегда удается избавиться от доступа к удаленным данным. Рассмотрим следующий пример:

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[1]:

Как мы видим, импортируемые данные на левом фланге составляют отрезок B(23:24) длиной 2, на правом фланге — B(48:50) длиной 3. Для многомерных массивов это будут грани импортируемых данных.

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

Такое распределение массива называется распределением с теневыми гранями. Если перед выполнением цикла скопировать грани импортируемых данных в соответствующие теневые грани, то цикл можно выполнять без доступа к удаленным данным. Максимальная ширина теневых граней задается в указании SHADOW. По умолчанию максимальная ширина теневых граней по каждому измерению равна 1.

Перепись в теневые грани (обновление) осуществляется перед параллельным циклом, если в его префиксе содержится указание SHADOW_RENEW. Указанный выше пример можно переписать следующим образом:

DVM(DISTRIBUTE[BLOCK];SHADOW[2:3]) floatB[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.

4.3. Буферный массив

Если импортируемые переменные не являются “соседними” и для доступа к ним нельзя использовать теневые грани, то их буферизация осуществляется через отдельный буферный массив. В указании удаленного доступа 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].

5. Совмещение счета и обменов данными между процессорами

5.1. Асинхронное обновление теневых граней

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

• сначала запускаются операции обмена данными — операции посылки экспортируемых данных локальной секции массива и операции приема значений теневых граней;
• затем ожидается завершение выданных операций.

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

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

Для организации группового асинхронного обновления теневых граней существуют 4 указания:

1.  Описание группы операций:

DVM(SHADOW_GROUP) void *AR;

2.  Директива задания состава группы:

DVM(CREATE_SHADOW_GROUP AR: A B C);

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

3.  Директива запуска обновления теневых граней, т.е. выдача операций посылки и приема экспортируемых данных массивов A, B и C:

DVM(SHADOW_START AR);

4.  Директива ожидания завершения обновления теневых граней:

DVM(SHADOW_WAIT AR);

Если задать в префиксе параллельного цикла указания SHADOW_START или SHADOW_WAIT, то изменяется порядок выполнения витков цикла на каждом процессоре.

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

А) Опережающее вычисление экспортируемых данных и рассылка их в теневые грани соседних процессоров.

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

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

Б) Отложенное использование импортируемых данных.

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

• выполнение витков, не требующих импортируемых элементов;
• ожидание завершения обновления теневых граней;
• выполнение витков, требующих импортируемых элементов.

5.2. Асинхронная редукция

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

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

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

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

Для организации групповой асинхронной редукции существуют 4 указания:

1.  Описание групповой редукции:

DVM(REDUCTION_GROUP) void *MAXMIN;

2.  Директива задания состава групповой редукции:

DVM(CREATE_REDUCTION_GROUP MAXMIN:
MAX(eps1) MIN(eps2));

Переменная MAXMIN будет содержать ссылку на группу редукций MAX(eps1) и MIN(eps2).

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

DVM(REDUCTION_START MAXMIN);

4. Директива ожидания результатов групповой редукции каждым процессором:

DVM(REDUCTION_WAIT MAXMIN);

6. Заключение

Язык C-DVM можно отнести к классу языков с параллелизмом данных, наиболее известными представителями которых являются языки Fortran D [10], Pandore C [11], Vienna Fortran [12], HPF [13].

Исследования языков с параллелизмом данных, которые велись в ИПМ РАН с 1993 года, позволили сделать вывод, что главным недостатком языков с параллелизмом данных является не сложность компиляторов, а отсутствие явной и ясной модели параллельного выполнения программы. Это не позволяет предоставить программисту удобные средства для анализа и повышения эффективности своей программы.

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

Название модели связано с двумя понятиями — Distributed Virtual Memory and Distributed Virtual Machine. Первое отражает наличие глобального адресного пространства (общей виртуальной памяти), а второе — использование промежуточной абстрактной машины (распределенной виртуальной машины) для двухступенчатого отображения параллельной программы на реальный параллельный компьютер. Программист создает абстрактную машину, наиболее подходящую для своей программы (позволяющую учесть весь потенциальный параллелизм программы), затем задает отображение на эту машину своей программы и данных, а также указывает правила отображения этой абстрактной машины на реальный параллельный компьютер. Это отображение абстрактной машины осуществляется во время выполнения программы и не требует ее перекомпиляции.

Язык C-DVM был разработан посредством расширения языка Си в соответствии с DVM-моделью. Главный принцип разработки языка — программист должен иметь возможность полностью специфицировать параллельное выполнение своей программы, хотя интеллектуальный компилятор может и не требовать этого от него.

Фактически, этот принцип определяет направление развития языка — от более сложного языка к более простому, от простого компилятора к более сложному. Направление развития языка HPF — противоположное: от автоматического распараллеливания к HPF1, затем к HPF2. Главным результатом этого различия подходов является то, что пользователь языка C-DVM ценой некоторых дополнительных усилий всегда может добиться той же эффективности своей программы, которую он мог бы обеспечить при программировании на языке с передачей сообщений. При этом переносимость его программы не ухудшается

Язык C-DVM создавался в тесном контакте с разработчиками пакета REACTOR [7]. Результатом совместной работы была значительная доработка DVM-модели, появление нескольких версий языка и двух существенно различающихся экспериментальных версий компилятора.

Язык C-DVM был использован для программирования нескольких тестов, включая TOMCATV из Spec92 и Spec95. Кроме того, с использованием языка C-DVM был переписан модуль расчета нейтронных полей в диффузионном приближении в трехмерной X-Y-Z геометрии, входящий в состав пакета прикладных программ РЕАКТОР [14]. При выполнении на МВС-100 были получены следующие временные характеристики C-DVM программ: Yakobi, TOMCATV и решения главной спектральной задачи для английской критсборки ZEBRA [8].

Yakobi (2 массива 900*900)

TOMCATV (7 массивов 257*257)

ZEBRA (28 массивов 16*31*61)

ZEBRA (28 массивов 16*31*61)

N — количество процессоров (топология — двумерная решетка)
E — коэффициент эффективности распараллеливания.

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

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

Список литературы

1. Konovalov N.A., Krukov V.A., Mihailov S.N. and Pogrebtsov A.A. 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.
2. Walker D.W. The design of a standard message-passing interface for distributed memory concurrent computers // Parallel Computing. — 1994 — Vol. 20(4), pp. 657-673.
3. Geist A., Beguelin A., Dongarra J., Jiang W., Manchek R., Sunderam V. PVM 3 User’s Guide and Reference Manual // Technical report, Oak Ridge National Laboratory ORNL/TM-12187 — 1993.
4. Krukov V.A., Pozdnjakov L.A. and Zadykhailo I.B. RAMPA — CASE for portable parallel programs development // Proc. of the International Conference on Parallel Computing Technologies, Obninck, Russia, Aug30-Sept 4, 1993.
5. Zabrodin A., Levin V., Korneev V. The Massively Parallel Computer System MBC-100. // In Proceedings of PaCT-95 (Parallel Computing Technologies) Int. conference, St.-Petersburg, Russia, 1995. LNCS, Vol. 964, Springer Verlag, pp.341-355.
6. Лацис А.О., Луцкий А.Е. Численное решение задач сверхзвукового обтекания на многопроцессорной вычислительной системе. // Вестник российского общества информатики и вычислительной техники. — 1994. — N3 — Москва, ВИМИ, стр.19-24.
7. Voronkov A.V., Arzhanov V.I. REACTOR – Program System for Neutron-Physical Calculations. // Proceedings of the International Topical Meeting “Advances in Mathematics, Calculation and Reactor Physics”, 5, 30.5 1-1 — 30.5 1-4, ANS, Pittsburgh, USA — 1991.
8. Chebesko A.N., Sychugova E.P. Low reactivity sosodium-void benchmark study in annular heterogeneous assembly. // Proceedings International Topical Meeting on Fast Reactor Safety, IPPE, Obninsk — 1994.
9. Коновалов Н.А., Крюков B.A., Погребцов A.A., Сазанов Ю.Л. C-DVM – язык разработки мобильных параллельных программ. // Препринт ИПМ им. М.В.Келдыша РАН. — 1997. — №86.
10. Fox G., Hiranandani S., Kennedy K., Koelbel K., Kremer U., Tseng C., and Wu M. Fortran D Language specification // Technical Report, TR 90-141, Dept. of Computer Science, Rice University — 1990.
11. Andre F., Pazat J., Thomas H. A system to manage data distribution. // Proceedings of the 1990 ACM International Conference on Supercomputing, Amsterdam, Netherlands — 1990.
12. Chapman B., Mehrotra P., and Zima H. Programming in Vienna Fortran. // Science Programming. — 1992. — Vol.1, pp.31-50.
13. High Performance Fortran Forum. High Performance Fortran Language Specification. // Technical Report, Version 1.0, Rice University — 1993.
14. Arzhanov V.I., Voronkov A.V., Golubev A.S., Konovalov N.A., Krukov V.A., and Sychugova E.P. Development of Portable Program System for Modeling Neutron-Physical Processes in Nuclear Reactor on Parallel Computers. // Proceedings of the Joint International Conference on Mathematical Methods and Supercomputing for Nuclear Applications — Vol. 2, pp.1454-1466 (Saratoga Springs, New York October 5-9, 1997).