1. Введение

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

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

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

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

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

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

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

Для отладки программы на реальной параллельной машине служат средства накопления трассировки. Трассировочная информация для каждого процессора накапливается в его оперативной памяти или записывается в файл. Для МВС-100 [ZLK95] созданы средства 'посмертной' выгрузки трассировочной информации из памяти всех процессоров и определения состояния программы на каждом процессоре (например, 'ждет сообщения', 'деление на ноль', и т.п.).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример. Программа 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;
}