Параллельное программирование на основе MPI

6.2.1.3. Передача сообщений

Для передачи сообщения процесс-отправитель должен выполнить функцию:

int MPI_Send(void *buf, int count, MPI_Datatype type, int dest,
  int tag, MPI_Comm comm),

где

Для указания типа пересылаемых данных в MPI имеется ряд базовых типов, полный список которых приведен в табл. 6.1.

Следует отметить:

( buf, count, type )

Сразу же после завершения функции MPI_Send процесс-отправитель может начать повторно использовать буфер памяти, в котором располагалось отправляемое сообщение. Вместе с этим, следует понимать, что в момент завершения функции MPI_Send состояние самого пересылаемого сообщения может быть совершенно различным - сообщение может располагаться в процессе-отправителе, может находиться в процессе передачи, может храниться в процессе-получателе или же может быть принято процессом-получателем при помощи функции MPI_Recv. Тем самым, завершение функции MPI_Send означает лишь, что операция передачи начала выполняться и пересылка сообщения будет рано или поздно будет выполнена.

Пример использования функции будет представлен после описания функции MPI_Recv.

6.2.1.4. Прием сообщений

Для приема сообщения процесс-получатель должен выполнить функцию:

int MPI_Recv(void *buf, int count, MPI_Datatype type, int source,
  int tag, MPI_Comm comm, MPI_Status *status),

где

Следует отметить:

Функция

MPI_Get_count(MPI_Status *status, MPI_Datatype type, int *count)

возвращает в переменной count количество элементов типа type в принятом сообщении.

Вызов функции MPI_Recv не должен согласовываться со временем вызова соответствующей функции передачи сообщения MPI_Send - прием сообщения может быть инициирован до момента, в момент или после момента начала отправки сообщения.

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

6.2.1.5. Первая параллельная программа с использованием MPI

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

#include <stdio.h>
  #include "mpi.h"
  int main(int argc, char* argv[]){
    int ProcNum, ProcRank, RecvRank;
    MPI_Status Status;
    MPI_Init(argc, argv);
    MPI_Comm_size(MPI_COMM_WORLD, ProcNum);
    MPI_Comm_rank(MPI_COMM_WORLD, ProcRank);
    if ( ProcRank == 0 ){
      // Действия, выполняемые только процессом с рангом 0
      printf ("\n Hello from process %3d", ProcRank);
      for ( int i=1; i<ProcNum; i++ ) {
        MPI_Recv(RecvRank, 1, MPI_INT, MPI_ANY_SOURCE, 
          MPI_ANY_TAG, MPI_COMM_WORLD, Status);
        printf("\n Hello from process %3d", RecvRank);
      }
    } 
    else // Сообщение, отправляемое всеми процессами, 
         // кроме процесса с рангом 0
      MPI_Send(ProcRank,1,MPI_INT,0,0,MPI_COMM_WORLD);
    MPI_Finalize();
    return 0;
  }

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

Hello from process 0
   Hello from process 2
   Hello from process 1
   Hello from process 3

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

MPI_Recv(RecvRank, 1, MPI_INT, i, MPI_ANY_TAG, MPI_COMM_WORLD, Status).

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

Следует отметить еще один важный момент - разрабатываемая с использованием MPI программа как в данном частном варианте, так и в самом общем случае используется для порождения всех процессов параллельной программы и, как результат, должна определять вычисления, выполняемые во всех этих процессах. Можно сказать, что MPI-программа является некоторым " макро-кодом ", различные части которого используются разными процессами. Так, например, в приведенном примере программы выделенные двойной рамкой участки программного кода не выполняются одновременно ни в одном процессе. Первый выделенный участок с функцией приема MPI_Send исполняется только процессом с рангом 0, второй участок с функцией приема MPI_Recv используется всеми процессами, за исключением нулевого процесса.

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

MPI_Comm_rank(MPI_COMM_WORLD, ProcRank);
    if ( ProcRank == 0 ) DoProcess0();
    else if ( ProcRank == 1 ) DoProcess1();
    else if ( ProcRank == 2 ) DoProcess2();

Во многих случаях, как и в рассмотренном примере, выполняемые действия являются отличающимися только для процесса с рангом 0. В этом случае общая схема MPI программы принимает более простой вид:

MPI_Comm_rank(MPI_COMM_WORLD, ProcRank);
    if ( ProcRank == 0 ) DoManagerProcess();
    else DoWorkerProcesses();

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

и др. - полный список констант для проверки кода завершения содержится в файле mpi.h.

6.2.2. Определение времени выполнение MPI-программы

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

Получение времени текущего момента выполнения программы обеспечивается при помощи функции:

double MPI_Wtime(void),

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

double t1, t2, dt;
    t1 = MPI_Wtime();
    …
    t2 = MPI_Wtime();
    dt = t2 - t1;

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

double MPI_Wtick(void),

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

6.2.3. Начальное знакомство с коллективными операциями передачи данных

Функции MPI_Send и MPI_Recv, рассмотренные в п. 6.2.1, обеспечивают возможность выполнения парных операций передачи данных между двумя процессами параллельной программы. Для выполнения коммуникационных коллективных операций, в которых принимают участие все процессы коммуникатора, в MPI предусмотрен специальный набор функций. В данном подразделе будут рассмотрены три такие функции, широко используемые даже при разработке сравнительно простых параллельных программ; полное же представление коллективных операций будет дано в подразделе 6.

Для демонстрации примеров применения рассматриваемых функций MPI будет использоваться учебная задача суммирования элементов вектора x (см. подраздел 2.5):

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

6.2.3.1. Передача данных от одного процесса всем процессам программы

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

MPI_Comm_size(MPI_COMM_WORLD,ProcNum);
for (i=1; i<ProcNum; i++)
  MPI_Send(x,n,MPI_DOUBLE,i,0,MPI_COMM_WORLD);

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

Достижение эффективного выполнения операции передачи данных от одного процесса всем процессам программы ( широковещательная рассылка данных) может быть обеспечено при помощи функции MPI

int MPI_Bcast(void *buf,int count,MPI_Datatype type,int root,MPI_Comm comm),

где

Функция MPI_Bcast осуществляет рассылку данных из буфера buf, содержащего count элементов типа type с процесса, имеющего номер root, всем процессам, входящим в коммуникатор comm (см. рис. 6.1).

Следует отметить:

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

#include <math.h> 
#include <stdio.h>
#include <stdlib.h>
#include "mpi.h"
int main(int argc, char* argv[]){
  double x[100], TotalSum, ProcSum = 0.0;
  int  ProcRank, ProcNum, N=100;
  MPI_Status Status;

  // инициализация
  MPI_Init(argc,argv); 
  MPI_Comm_size(MPI_COMM_WORLD,ProcNum); 
  MPI_Comm_rank(MPI_COMM_WORLD,ProcRank);

  // подготовка данных
  if ( ProcRank == 0 ) DataInitialization(x,N);

// рассылка данных на все процессы
  MPI_Bcast(x, N, MPI_DOUBLE, 0, MPI_COMM_WORLD);

  // вычисление частичной суммы на каждом из процессов
  // на каждом процессе суммируются элементы вектора x от i1 до i2
  int k = N / ProcNum;
  int i1 = k *   ProcRank;
  int i2 = k * ( ProcRank + 1 );
  if ( ProcRank == ProcNum-1 ) i2 = N;
  for ( int i = i1; i < i2; i++ )
    ProcSum  = ProcSum + x[i];

  // сборка частичных сумм на процессе с рангом 0
  if ( ProcRank == 0 ) {
    TotalSum = ProcSum;
    for ( int i=1; i < ProcNum; i++ ) {
      MPI_Recv(ProcSum, 1, MPI_DOUBLE, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD,
 Status);
      TotalSum = TotalSum + ProcSum;
    }
  } 
  else // все процессы отсылают свои частичные суммы
    MPI_Send(ProcSum, 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD);

  // вывод результата
  if ( ProcRank == 0 ) 
    printf("\nTotal Sum = %10.2f",TotalSum);
  MPI_Finalize();
}

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

6.2.3.2. Передача данных от всех процессов одному процессу. Операции редукции

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

int MPI_Reduce(void *sendbuf, void *recvbuf,int count,MPI_Datatype type,
MPI_Op op,int root,MPI_Comm comm),

где

В качестве операций редукции данных могут быть использованы предопределенные в MPI операции - см. табл. 6.2.

Помимо данного стандартного набора операций могут быть определены и новые дополнительные операции непосредственно самим пользователем библиотеки MPI - см., например, Немнюгин и Стесик (2002), Group, et al. (1994), Pacheco (1996).

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

где $$\otimes$$ есть операция, задаваемая при вызове функции MPI_Reduce (для пояснения на рис. 6.3. показан пример выполнения операции редукции данных).

Следует отметить:

Применим полученные знания для переработки ранее рассмотренной программы суммирования - как можно увидеть, весть программный код, выделенный двойной рамкой, может быть теперь заменен на вызов одной лишь функции MPI_Reduce:

// сборка частичных сумм на процессе с рангом 0
MPI_Reduce(ProcSum,TotalSum, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);

6.2.3.3. Синхронизация вычислений

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

Синхронизация процессов, т.е. одновременное достижение процессами тех или иных точек процесса вычислений, обеспечивается при помощи функции MPI:

int MPI_Barrier(MPI_Comm comm);

Функция MPI_Barrier определяет коллективную операции и, тем самым, при использовании должна вызываться всеми процессами используемого коммуникатора. При вызове функции MPI_Barrier выполнение процесса блокируется, продолжение вычислений процесса произойдет только после вызова функции MPI_Barrier всеми процессами коммуникатора.

6.3. Операции передачи данных между двумя процессами

Продолжим начатое в п. 6.2.1 изучение функций MPI для выполнения операций передачи данных между процессами параллельной программы.

6.3.1. Режимы передачи данных

Рассмотренная ранее функция MPI_Send обеспечивает так называемый стандартный ( Standard ) режим отправки сообщений, при котором (см. также п. 6.2.1.3):

Кроме стандартного режима в MPI предусматриваются следующие дополнительные режимы передачи сообщений:

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

Список параметров всех перечисленных функций совпадает с составом параметров функции MPI_Send.

Для использования буферизованного режима передачи должны быть создан и передан MPI буфер памяти для буферизации сообщений - используемая для этого функция имеет вид:

int MPI_Buffer_attach(void *buf, int size),

где

После завершения работы с буфером он должен быть отключен от MPI при помощи функции:

int MPI_Buffer_detach(void *buf, int *size).

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

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

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

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

MPI обеспечивает возможность неблокированного выполнения операций передачи данных между двумя процессами. Наименование неблокирующих аналогов образуется из названий соответствующих функций путем добавления префикса I ( Immediate ). Список параметров неблокирующих функций содержит весь набор параметров исходных функций и один дополнительный параметр request с типом MPI_Request (в функции MPI_Irecv отсутствует также параметр status ):

int MPI_Isend(void *buf, int count, MPI_Datatype type, int dest,
  int tag, MPI_Comm comm, MPI_Request *request)
int MPI_Issend(void *buf, int count, MPI_Datatype type, int dest,
  int tag, MPI_Comm comm, MPI_Request *request)
int MPI_Ibsend(void *buf, int count, MPI_Datatype type, int dest,
  int tag, MPI_Comm comm, MPI_Request *request)
int MPI_Irsend(void *buf, int count, MPI_Datatype type, int dest,
  int tag, MPI_Comm comm, MPI_Request *request)
int MPI_Irecv(void *buf, int count, MPI_Datatype type, int source,
  int tag, MPI_Comm comm, MPI_Request *request)

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

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

int MPI_Test( MPI_Request *request, int *flag, MPI_status *status),

где

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

MPI_Isend(buf,count,type,dest,tag,comm,request);
…
do {
  …
  MPI_Test(request,flag,status)
} while ( !flag );

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

int MPI_Wait( MPI_Request *request, MPI_status *status).

Кроме рассмотренных, MPI содержит ряд дополнительных функций проверки и ожидания неблокирующих операций обмена:

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

6.3.3. Одновременное выполнение передачи и приема

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

Достижение эффективного и гарантированного одновременного выполнения операций передачи и приема данных может быть обеспечено при помощи функции MPI:

int MPI_Sendrecv(void *sbuf,int scount,MPI_Datatype stype,int dest, int  stag, 
                 void *rbuf,int rcount,MPI_Datatype rtype,int source,int rtag, 
                 MPI_Comm comm, MPI_Status *status),

где

Как следует из описания, функция MPI_Sendrecv передает сообщение, описываемое параметрами ( sbuf, scount, stype, dest, stag ), процессу с рангом dest и принимает сообщение в буфер, определяемый параметрами ( rbuf, rcount, rtype, source, rtag ), от процесса с рангом source.

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

int MPI_Sendrecv_replace (void *buf, int count, MPI_Datatype type, int dest,
int stag, int source, int rtag, MPI_Comm comm, MPI_Status* status).

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

6.4. Коллективные операции передачи данных

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

Рассмотрим далее оставшиеся базовые коллективные операции передачи данных.

6.4.1. Обобщенная передача данных от одного процесса всем процессам

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

int MPI_Scatter(void *sbuf,int scount,MPI_Datatype stype,
                void *rbuf,int rcount,MPI_Datatype rtype,
                int root, MPI_Comm comm),

где

При вызове этой функции процесс с рангом root произведет передачу данных всем другим процессам в коммуникаторе. Каждому процессу будет отправлено scount элементов. Процесс с рангом 0 получит блок данных из sbuf из элементов с индексами от 0 до scount-1, процессу с рангом 1 будет отправлен блок из элементов с индексами от scount до 2* scount-1 и т.д. Тем самым, общий размер отправляемого сообщения должен быть равен scount * p элементов, где p есть количество процессов в коммуникаторе comm.

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

Отметим также, что функция MPI_Scatter передает всем процессам сообщения одинакового размера. Выполнение более общего варианта операции распределения данных, когда размеры сообщений для процессов могут быть разного размера, обеспечивается при помощи функции MPI_Scatterv.

Пример использования функции MPI_Scatter рассматривается в разделе 7 при разработке параллельных программ умножения матрицы на вектор.

6.4.2. Обобщенная передача данных от всех процессов одному процессу

Операция обобщенной передачи данных от всех процессоров одному процессу ( сбор данных ) является обратной к процедуре распределения данных (см. рис. 6.5). Для выполнения этой операции в MPI предназначена функция:

int MPI_Gather(void *sbuf,int scount,MPI_Datatype stype,
               void *rbuf,int rcount,MPI_Datatype rtype,
                int root, MPI_Comm comm),

где

При выполнении функции MPI_Gather каждый процесс в коммуникаторе передает данные из буфера sbuf на процесс с рангом root. Процесс с рангом root собирает все получаемые данные в буфере rbuf (размещение данных в буфере осуществляется в соответствии с рангами процессов-отправителей сообщений). Для того, чтобы разместить все поступающие данные, размер буфера rbuf должен быть равен scount * p элементов, где p есть количество процессов в коммуникаторе comm.

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

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

int MPI_Allgather(void *sbuf, int scount, MPI_Datatype stype,
               void *rbuf, int rcount, MPI_Datatype rtype, MPI_Comm comm).

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

Пример использования функции MPI_Gather рассматривается в разделе 7 при разработке параллельных программ умножения матрицы на вектор.

6.4.3. Общая передача данных от всех процессов всем процессам

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

int MPI_Alltoall(void *sbuf,int scount,MPI_Datatype stype,
                 void *rbuf,int rcount,MPI_Datatype rtype,MPI_Comm comm),

где

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

Вызов функции MPI_Alltoall при выполнении операции общего обмена данными должен быть выполнен в каждом процессе коммуникатора.

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

Пример использования функции MPI_Alltoall рассматривается в разделе 7 при разработке параллельных программ умножения матрицы на вектор как задание для самостоятельного выполнения.

6.4.4. Дополнительные операции редукции данных

Рассмотренная в п. 6.2.3.2 функция MPI_Reduce обеспечивает получение результатов редукции данных только на одном процессе. Для получения результатов редукции данных на каждом из процессов коммуникатора необходимо использовать функцию редукции и рассылки:

int MPI_Allreduce(void *sendbuf, void *recvbuf,int count,MPI_Datatype type,
MPI_Op op,MPI_Comm comm).

Функция MPI_AllReduce выполняет рассылку между процессами всех результатов операции редукции. Возможность управления распределением этих данных между процессами предоставляется функций MPI_Reduce_scatter.

И еще один вариант операции сбора и обработки данных, при котором обеспечивается получение и всех частичных результатов редуцирования, может быть получен при помощи функции:

int MPI_Scan(void *sendbuf, void *recvbuf,int count,MPI_Datatype type,
MPI_Op op,MPI_Comm comm).

Общая схема выполнения функции MPI_Scan показана на рис. 6.7. Элементы получаемых сообщений представляют собой результаты обработки соответствующих элементов передаваемых процессами сообщений, при этом для получения результатов на процессе с рангом i, 0 i<n,используются данные от процессов, ранг которых меньше или равен i,т.е.

где $$\otimes$$ есть операция, задаваемая при вызове функции MPI_Scan.

6.4.5. Сводный перечень коллективных операций данных

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

6.5. Производные типы данных в MPI

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

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

6.5.1. Понятие производного типа данных

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

TypeMap = {(type0,disp0),… , (typen-1,dispn-1)}.

Часть карты типа с указанием только типов значений именуется в MPI сигнатурой типа:

TypeSignature = {type0,… , typen-1}

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

Поясним рассмотренные понятия на следующем примере. Пусть в сообщение должны входить значения переменных:

double a; /* адрес 24 */
double b; /* адрес 40 */
int    n; /* адрес 48 */

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

{(MPI_DOUBLE,0),
 (MPI_DOUBLE,16),
 (MPI_INT,24)
}

Дополнительно для производных типов данных в MPI используется следующий ряд новых понятий:

Согласно определению нижняя граница есть смещение для первого байта значений рассматриваемого типа данных. Соответственно верхняя граница представляет собой смещение для байта, располагающегося вслед за последним элементом рассматриваемого типа данных. При этом величина смещения для верхней границы может быть округлена вверх с учетом требований выравнивания адресов. Так, одно из самых общих требований, которые налагают реализации языков C и Fortran, состоит в том, чтобы адрес элемента был кратен длине этого элемента в байтах. Например, если тип int занимает четыре байта, то адрес на элемент типа int должен нацело делиться на четыре. Именно это требование и отражается в определении верхней границы типа данных MPI. Поясним данный момент на ранее рассмотренном примере набора переменных a,b и n, для которого нижняя граница равна 0, а верхняя граница принимает значение 32 (величина округления 6 или 4 в зависимости от размера типа int ). Здесь следует отметить, что требуемое выравнивание определяется по типу первого элемента данных в карте типа.

Следует также указать на различие понятий протяженности и размера типа. Протяженность - это размер памяти в байтах, который нужно отводить для одного элемента производного типа. Размер типа данных - это число байтов, которые занимают данные (разность между адресами последнего и первого байтов данных). Различие в значениях протяженности и размера опять же в величине округления для выравнивания адресов. Так, в рассматриваемом примере размер типа равен 28, а протяженность - 32 (предполагается, что тип int занимает четыре байта).

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

int MPI_Type_extent ( MPI_Datatype type, MPI_Aint *extent ),
int MPI_Type_size   ( MPI_Datatype type, MPI_Aint *size ).

Определение нижней и верхней границ типа может быть выполнено при помощи функций:

int MPI_Type_lb ( MPI_Datatype type, MPI_Aint *disp ),
int MPI_Type_ub ( MPI_Datatype type, MPI_Aint *disp ).

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

int MPI_Address ( void *location, MPI_Aint *address )

(следует отметить, что данная функция является переносимым вариантом средств получения адресов в алгоритмических языках C и Fortran).

6.5.2. Способы конструирования производных типов данных

Для снижения сложности в MPI предусмотрено несколько различных способов конструирования производных типов:

Далее перечисленные способы конструирования производных типов данных будут рассмотрены более подробно.

6.5.2.1. Непрерывный способ конструирования

При непрерывном способе конструирования производного типа данных в MPI используется функция:

int MPI_Type_contiguous(int count,MPI_Data_type oldtype,MPI_Datatype *newtype).

Как следует из описания, новый тип newtype создается как count элементов исходного типа oldtype. Например, если исходный тип данных имеет карту типа

{ (MPI_INT,0),(MPI_DOUBLE,8) },

то вызов функции MPI_Type_contiguous с параметрами

MPI_Type_contiguous (2, oldtype, newtype);

приведет к созданию типа данных с картой типа

{ (MPI_INT,0),(MPI_DOUBLE,8),(MPI_INT,16),(MPI_DOUBLE,24) }.

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

6.5.2.2. Векторный способ конструирования

При векторном способе конструирования производного типа данных в MPI используются функции

int MPI_Type_vector ( int count, int blocklen, int stride, 
  MPI_Data_type oldtype, MPI_Datatype *newtype ),

где

int MPI_Type_hvector ( int count, int blocklen, MPI_Aint stride, 
  MPI_Data_type oldtype, MPI_Datatype *newtype ).

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

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

MPI_Type_vector ( n/2, n, 2*n, StripRowType, ElemType ),

MPI_Type_vector ( n, 1, n, ColumnType, ElemType ),

MPI_Type_vector ( n, 1, n+1, DiagonalType, ElemType ).

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

int MPI_Type_create_subarray ( int ndims, int *sizes, int *subsizes, 
  int *starts, int order, MPI_Data_type oldtype, MPI_Datatype *newtype ),

где

6.5.2.3. Индексный способ конструирования

При индексном способе конструирования производного типа данных в MPI используются функции:

int MPI_Type_indexed ( int count, int blocklens[], int indices[], 
  MPI_Data_type oldtype, MPI_Datatype *newtype ),

где

int MPI_Type_hindexed ( int count, int blocklens[], MPI_Aint indices[], 
  MPI_Data_type oldtype, MPI_Datatype *newtype )

Как следует из описания, при индексном способе новый производный тип создается как набор блоков разного размера из элементов исходного типа, при этом между блоками могут иметься разные промежутки по памяти. Для пояснения данного способа можно привести пример конструирования типа для описания верхней треугольной матрицы размером n x n:

// конструирование типа для описания верхней треугольной матрицы
	for ( i=0, i<n; i++ ) {
	  blocklens[i] = n - i;
	  indices[i]   = i * n + i;
	}
	MPI_Type_indexed ( n, blocklens, indices, UTMatrixType, ElemType ).

Как и ранее, способ конструирования, определяемый функцией MPI_Type_hindexed, отличается тем, что элементы indices для определения интервалов между блоками задаются в байтах, а не в элементах исходного типа данных.

Следует отметить, что существует еще одна дополнительная функция MPI_Type_create_indexed_block индексного способа конструирования для определения типов с блоками одинакового размера (данная функция предусматривается стандартом MPI-2).

6.5.2.4. Структурный способ конструирования

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

int MPI_Type_struct ( int count, int blocklens[], MPI_Aint indices[], 
  MPI_Data_type oldtypes[], MPI_Datatype *newtype ),

где

Как следует из описания, структурный способ дополнительно к индексному методу позволяет указывать типы элементов для каждого блока в отдельности.

6.5.3. Объявление производных типов и их удаление

Рассмотренные в предыдущем пункте функции конструирования позволяют определить производный тип данных. Дополнительно перед использованием созданный тип должен быть объявлен при помощи функции:

int MPI_Type_commit (MPI_Datatype *type ).

При завершении использования производный тип должен быть аннулирован при помощи функции:

int MPI_Type_free (MPI_Datatype *type ).

6.5.4. Формирование сообщений при помощи упаковки и распаковки данных

Наряду с рассмотренными в п. 4.5.2 методами конструирования производных типов в MPI предусмотрен и явный способ сборки и разборки сообщений, содержащих значения разных типов и располагаемых в разных областях памяти.

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

int MPI_Pack ( void *data, int count, MPI_Datatype type, 
  void *buf, int bufsize, int *bufpos, MPI_Comm comm),

где

Функция MPI_Pack упаковывает count элементов из буфера data в буфер упаковки buf, начиная с позиции bufpos. Общая схема процедуры упаковки показана на рис. 6.8а.

Начальное значение переменной bufpos должно быть сформировано до начала упаковки и далее устанавливается функцией MPI_Pack. Вызов функции MPI_Pack осуществляется последовательно для упаковки всех необходимых данных. Так, для ранее рассмотренного примера набора переменных a,b и n, для их упаковки необходимо выполнить:

bufpos = 0;
	MPI_Pack(a,1,MPI_DOUBLE,buf,buflen,bufpos,comm);
	MPI_Pack(b,1,MPI_DOUBLE,buf,buflen,bufpos,comm);
	MPI_Pack(n,1,MPI_INT,buf,buflen,bufpos,comm);

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

int MPI_Pack_size (int count, MPI_Datatype type, MPI_Comm comm, int *size),

которая в параметре size указывает необходимый размер буфера для упаковки count элементов типа type.

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

После получения сообщения с типом MPI_PACKED данные могут быть распакованы при помощи функции:

int MPI_Unpack (void *buf, int bufsize, int *bufpos, 
  void *data, int count, MPI_Datatype type, MPI_Comm comm),

где

Функция MPI_Unpack распаковывает начиная с позиции bufpos очередную порцию данных из буфера buf и помещает распакованные данные в буфер data. Общая схема процедуры распаковки показана на рис. 6.8б.

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

bufpos = 0;
MPI_Pack(buf,buflen,bufpos,a,1,MPI_DOUBLE,comm);
MPI_Pack(buf,buflen,bufpos,b,1,MPI_DOUBLE,comm);
MPI_Pack(buf,buflen,bufpos,n,1,MPI_INT,comm);

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

6.6. Управление группами процессов и коммуникаторами

Рассмотрим теперь возможности MPI по управлению группами процессов и коммуникаторами.

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

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

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

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

При необходимости передачи данных между процессами из разных групп необходимо создавать глобальный коммуникатор ( intercommunicator ). Взаимодействие между процессами разных групп оказывается необходимым в достаточно редких ситуациях, в данном учебном материале не рассматривается и может служить темой для самостоятельно изучения - см., например, Немнюгин и Стесик (2002), Group, et al. (1994), Pacheco (1996).

6.6.1. Управление группами

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

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

int MPI_Comm_group ( MPI_Comm comm, MPI_Group *group ).

Далее, на основе существующих групп, могут быть созданы новые группы:

int MPI_Group_incl(MPI_Group oldgroup,int n, int *ranks,MPI_Group *newgroup),

int MPI_Group_excl(MPI_Group oldgroup,int n, int *ranks,MPI_Group *newgroup).

int MPI_Group_union(MPI_Group group1, MPI_Group group2, MPI_Group *newgroup);

int MPI_Group_intersection ( MPI_Group group1, MPI_Group group2,
  MPI_Group *newgroup ),

int MPI_Group_difference ( MPI_Group group1, MPI_Group group2, 
  MPI_Group *newgroup ).

int MPI_Group_size ( MPI_Group group, int *size ),

int MPI_Group_rank ( MPI_Group group, int *rank ).

int MPI_Group_free ( MPI_Group *group )

6.6.2. Управление коммуникаторами

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

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

int MPI_Comm_dup ( MPI_Comm oldcom, MPI_comm *newcomm ),

int MPI_comm_create (MPI_Comm oldcom, MPI_Group group, MPI_Comm *newcomm).

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

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

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

MPI_Group WorldGroup, WorkerGroup;
MPI_Comm Workers;
int ranks[1];
ranks[0] = 0;
// получение группы процессов в MPI_COMM_WORLD
MPI_Comm_group(MPI_COMM_WORLD, WorldGroup);
// создание группы без процесса с рангом 0
MPI_Group_excl(WorldGroup, 1, ranks, WorkerGroup);
// Создание коммуникатора по группе
MPI_Comm_create(MPI_COMM_WORLD,WorkerGroup,Workers);
...
MPI_Group_free(WorkerGroup);
MPI_Comm_free(Workers);

Быстрый и полезный способ одновременного создания нескольких коммуникаторов обеспечивает функция:

int MPI_Comm_split ( MPI_Comm oldcomm, int split, int key, 
  MPI_Comm *newcomm ),

где

Создание коммуникаторов относится к коллективным операциям и, тем самым, вызов функции MPI_Comm_split должен быть выполнен в каждом процессе коммуникатора oldcomm. В результате выполнения функции процессы разделяются на непересекающиеся группы с одинаковыми значениями параметра split. На основе сформированных групп создается набор коммуникаторов. При создании коммуникаторов для рангов процессов выбирается такой порядок нумерации, чтобы он соответствовал порядку значений параметров key (процесс с большим значением параметра key должен иметь больший ранг).

В качестве примера можно рассмотреть задачу представления набора процессов в виде двумерной решетки. Пусть p=q*q есть общее количество процессов, следующий далее фрагмент программы обеспечивает получение коммуникаторов для каждой строки создаваемой топологии:

MPI_Comm comm;
int rank, row;
MPI_Comm_rank(MPI_COMM_WORLD,rank);
row = rank/q;
MPI_Comm_split(MPI_COMM_WORLD,row,rank,comm);

При выполнении данного примера, например, при p=9, процессы с рангами (0,1,2) образуют первый коммуникатор, процессы с рангами (3,4,5) - второй и т.д.

После завершения использования коммуникатор должен быть удален:

int MPI_Comm_free ( MPI_Comm *comm ).

6.7. Виртуальные топологии

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

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

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

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

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

6.7.1. Декартовы топологии (решетки)

Декартовы топологии, в которых множество процессов представляется в виде прямоугольной решетки (см. п. 1.4.1 и рис. 6.7), а для указания процессов используется декартова система координат, широко применяются во многих задачах для описания структуры имеющихся информационных зависимостей. В числе примеров таких задач - матричные алгоритмы (см. разделы 7 и 8) и сеточные методы решения дифференциальных уравнений в частных производных (см. раздел 12).

Для создания декартовой топологии (решетки) в MPI предназначена функция:

int MPI_Cart_create(MPI_Comm oldcomm, int ndims, int *dims, int *periods, 
  int reorder, MPI_Comm *cartcomm),

где:

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

Для пояснения назначения параметров функции MPI_Cart_create рассмотрим пример создания двухмерной решетки 4x4, в которой строки и столбцы имеют кольцевую структуру (за последним процессом следует первый процесс):

// создание двухмерной решетки 4x4
MPI_Comm GridComm;
int dims[2], periods[2], reorder = 1;
dims[0]    = dims[1]    = 4;
periods[0] = periods[1] = 1;
MPI_Cart_create(MPI_COMM_WORLD, 2, dims, periods, reoreder, GridComm);

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

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

int MPI_Card_coords(MPI_Comm comm,int rank,int ndims,int *coords),

где:

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

int MPI_Cart_rank(MPI_Comm comm, int *coords, int *rank),

где

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

int MPI_Card_sub(MPI_Comm comm, int *subdims, MPI_Comm *newcomm),

где:

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

Для пояснения функции MPI_Cart_sub дополним ранее рассмотренный пример создания двухмерной решетки и определим коммуникаторы с декартовой топологией для каждой строки и столбца решетки в отдельности:

// создание коммуникаторов для каждой строки и столбца решетки
MPI_Comm RowComm, ColComm;
int subdims[2];
// создание коммуникаторов для строк
subdims[0] = 0;  // фиксации измерения
subdims[1] = 1;  // наличие данного измерения в подрешетке
MPI_Cart_sub(GridComm, subdims, RowComm);
// создание коммуникаторов для столбцов
subdims[0] = 1;
subdims[1] = 0;
MPI_Cart_sub(GridComm, subdims, ColComm);

В приведенном примере для решетки размером 4х4 создаются 8 коммуникаторов, по одному для каждой строки и столбца решетки. Для каждого процесса определяемые коммуникаторы RowComm и ColComm соответствуют строке и столбцу процессов, к которым данный процесс принадлежит.

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

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

int MPI_Card_shift(MPI_Comm comm, int dir, int disp,
  int *source, int *dst),

где:

Следует отметить, что функция MPI_Cart_shift только определяет ранги процессов, между которыми должен быть выполнен обмен данными в ходе операции сдвига. Непосредственная передачами данных, может быть выполнена, например, при помощи функции MPI_Sendrecv.

6.7.2. Топологии графа

Сведения по функциям MPI для работы с виртуальными топологиями типа граф будут рассмотрены более кратко - дополнительная информация может быть получена, например, Немнюгин и Стесик (2002), Group, et al. (1994), Pacheco (1996).

Для создания коммуникатора с топологией типа граф в MPI предназначена функция:

int MPI_Graph_create(MPI_Comm oldcomm, int nnodes, int *index, int *edges, 
  int reorder, MPI_Comm *graphcomm),

где:

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

Для примера создадим топологию графа со структурой, представленной на рис. 6.9. В этом случае количество процессов равно 5, порядки вершин (количества исходящих дуг) принимают значения (4,1,1,1,1), а матрица инцидентности (номера вершин, для которых дуги являются входящими) имеет вид:

Процессы   Линии связи
	  0        1, 2, 3, 4
	  1           0
	  2           0
	  3           0
	  4           0

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

// создание топологии типа звезда
	int index[] = { 4,1,1,1,1 };
	int edges[] = { 1,2,3,4,0,0,0,0 };
	MPI_Comm StarComm;
	MPI_Graph_create(MPI_COMM_WORLD, 5, index, edges, 1, StarComm);

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

int MPI_Graph_neighbors_count(MPI_Comm comm,int rank, int *nneighbors).

Получение рангов соседних вершин обеспечивается функцией:

int MPI_Graph_neighbors(MPI_Comm comm,int rank,int mneighbors, int *neighbors),

где mneighbors есть размер массива neighbors.

6.8. Дополнительные сведения о MPI

6.8.1. Разработка параллельных программ с использованием MPI на алгоритмическом языке Fortran

При разработке параллельных программ с использованием MPI на алгоритмическом языке Fortran существует не так много особенностей по сравнению с применением алгоритмического языка C:

В качестве принятых соглашений при разработке программ на языке Fortran рекомендуется записывать имена подпрограмм с использованием прописных символов.

В качестве примера приведем вариант программы из п. 4.2.1.5 на алгоритмическом языке Fortran.

PROGRAM MAIN
  include 'mpi.h'
  INTEGER PROCNUM, PROCRANK, RECVRANK, IERR
  INTEGER STATUS(MPI_STATUS_SIZE)
  CALL MPI_Init(IERR)
  CALL MPI_Comm_size(MPI_COMM_WORLD, PROCNUM, IERR)
  CALL MPI_Comm_rank(MPI_COMM_WORLD, PROCRANK IERR)
  IF ( PROCRANK.EQ.0 )THEN
    ! Действия, выполняемые только процессом с рангом 0
    PRINT *,"Hello from process ", PROCRANK
    DO i = 1, PROCNUM-1
      CALL MPI_RECV(RECVRANK, 1, MPI_INT, MPI_ANY_SOURCE, 
        MPI_ANY_TAG, MPI_COMM_WORLD, STATUS, IERR)
      PRINT *,"Hello from process ", RECVRANK
    END DO
  ELSE ! Сообщение, отправляемое всеми процессами, 
       ! кроме процесса с рангом 0
    CALL MPI_SEND(PROCRANK,1,MPI_INT,0,0,MPI_COMM_WORLD,IERR)
  END IF
  MPI_FINALIZE(IERR);
  STOP
END

6.8.2. Общая характеристика среды выполнения MPI-программ

Для проведения параллельных вычислений в вычислительной системе должна быть установлена среда выполнения MPI-программ, которая бы обеспечивала разработку, компиляцию, компоновку и выполнение параллельных программ. Для выполнения первой части перечисленных действий - разработки, компиляции, компоновки - как правило, достаточно обычных средств разработки программ (таких, например, как Microsoft Visual Studio), необходимо лишь наличие той или иной библиотеки MPI. Для выполнения же параллельных программ от среды выполнения требуется ряд дополнительных возможностей, среди которых наличие средств указания используемых процессоров, операций удаленного запуска программ и т.п. Крайне желательно также наличие в среде выполнения средств профилирования, трассировки и отладки параллельных программ.

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

Запуск MPI-программы также зависит от среды выполнения, но в большинстве случаев данное действие выполняется при помощи команды mpirun. В числе возможных параметров этой команды:

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

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

6.8.3. Дополнительные возможности стандарта MPI-2

Как уже отмечалось, стандарт MPI-2 был принят в 1997 г. Несмотря на достаточно большой период времени, прошедший с тех пор, использование данного варианта стандарта все еще ограничено. Среди основных причин такой ситуации можно назвать обычный консерватизм разработчиков программного обеспечения, сложность реализации нового стандарта и т.п. Важный момент состоит также в том, что возможностей MPI-1 оказывается достаточным для реализации многих параллельных алгоритмов, а сфера применимости дополнительных возможностей MPI-2 оказывается не столь широкой.

Для знакомства со стандартом MPI-2 может быть рекомендован информационный ресурс http://www.mpiforum.org, а также работа Group, et al. (1999b). Здесь же дадим краткую характеристику дополнительных возможностей стандарта MPI-2:

6.9. Краткий обзор раздела

Данный раздел посвящен рассмотрению методов параллельного программирования для вычислительных систем с распределенной памятью с использованием MPI.

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

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

В подразделе 6.2 проводится быстрое и простое введение в разработку параллельных программ с использованием MPI. Излагаемого в подразделе материала достаточно для начала разработки параллельных программ разного уровня сложности.

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

В подразделе 6.4 рассматриваются коллективные операции передачи данных. Изложение материала соответствует последовательности изучения коммуникационных операций, использованной в разделе 3. Основной результат данного подраздела состоит в том, что MPI обеспечивает поддержку практически всех основных операций информационных обменов между процессами.

В подразделе 6.5 излагается материал, связанный с использованием в MPI производных типов данных. В подразделе представлены все основные способы конструирования производных типов - непрерывный, векторный, индексный и структурный. Обсуждается также возможность явного формирования сложных сообщений при помощи упаковки и распаковки данных.

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

В подразделе 6.7 рассматриваются возможности MPI по использованию виртуальных топологий. В подразделе представлены топологии, поддерживаемые MPI - прямоугольная решетка произвольной размерности ( декартова топология ) и топология графа любого необходимого вида.

В подразделе 6.8 приводятся дополнительные сведения о MPI. В их числе обсуждаются вопросы разработки параллельных программ с использованием MPI на алгоритмическом языке Fortran, дается краткая характеристика сред выполнения MPI-программ и приводится обзор дополнительных возможностей стандарта MPI-2.

6.10. Обзор литературы

Имеется ряд источников, в которых может быть получена информация о MPI. Прежде всего, это информационный ресурс Интернет с описанием стандарта MPI: http://www.mpiforum.org. Одна из наиболее распространенных реализаций MPI - библиотека MPICH представлена на http://www-unix.mcs.anl.gov/mpi/mpich (библиотека MPICH2 с реализацией стандарта MPI-2 содержится на http://www-unix.mcs.anl.gov/mpi/mpich2). Русскоязычные материалы о MPI имеются на сайте http://www.parallel.ru.

Среди опубликованных изданий могут быть рекомендованы работы Group, et al. (1994), Pacheco (1996), Snir, et al. (1996), Group, et al. (1999a). Описание стандарта MPI-2 может быть получено в Group, et al. (1999b). Среди русскоязычных изданий могут быть рекомендованы работы Воеводин В.В. и Воеводин Вл.В. (2002), Немнюгина и Стесик (2002), Корнеева (2003).

Следует отметить также работу Quinn (2003), в которой изучение MPI проводится на примере ряда типовых задач параллельного программирования - матричных вычислений, сортировки, обработки графов и др.

6.11. Контрольные вопросы

6.12. Задачи и упражнения

Подраздел 6.2.