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

Презентацию к данной лекции Вы можете скачать здесь.

Пользовательские типы

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

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

В MPI-программе для решения этой проблемы придется создать производный тип данных.

Пример:

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

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

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

Можно различные элементы данных пересылать по отдельности. Это медленный и неудобный способ обмена.

Более эффективным решением является использование производных типов данных.

Производные типы данных создаются во время выполнения программы (а не во время ее трансляции), как правило, перед их использованием.

Создание типа - двухступенчатый процесс, который состоит из двух шагов:

конструирование типа.

регистрация типа.

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

Коммуникаторы, группы, типы данных, определённые пользователем операции, атрибуты коммуникаторов, обработчики ошибок - все это примеры объектов, которые (если они были созданы в процессе работы программы) должны удаляться.

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

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

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

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

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

Конструкторы производных типов

Подпрограмма MPI_Type_struct является наиболее общим конструктором типа в MPI - программист может использовать полное описание каждого элемента типа.

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

MPI_Type_сontiguous - создает производный тип, элементы которого являются непрерывно расположенными элементами массива.

MPI_Type_vector - создает тип, элементы которого расположены на одинаковых расстояниях друг от друга.

MPI_Type_indexed - создает тип, содержащий произвольные элементы.

Векторный тип создается конструктором MPI_Type_vector:

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

Входные параметры:

count - количество блоков (неотрицательное целое значение);

blocklen - длина каждого блока (количество элементов, неотрицательное целое);

stride - количество элементов, расположенных между началом предыдущего и началом следующего блока ("гребенка");

oldtype - базовый тип.

Выходной параметр - идентификатор нового типа newtype. Этот идентификатор назначается программистом. Исходные данные здесь однотипные.

Схема расположения данных в новом типе

Пример:

count = 2;

stride = 4;

blocklen = 3;

oldtype = double;

карта нового типа:

{(double, 0), (double, 1), (double, 2), (double, 4), (double, 5), (double, 6)}

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

  int MPI_Type_struct(int count, int blocklengths[], MPI_Aint indices[], MPI_Datatype oldtypes[], 
  MPI_Datatype *newtype)
  MPI_Type_struct(count, blocklengths, indices, oldtypes, newtype, ierr)
 

Ее входные параметры:

count - задает количество элементов в производном типе, а также длину массивов oldtypes, indices и blocklengths;

blocklengths - количество элементов в каждом блоке (массив);

indices - смещение каждого блока в байтах (массив);

oldtypes - тип элементов в каждом блоке (массив).

Выходной параметр - идентификатор производного типа newtype.

Схема расположения данных в структурном типе

Пример создания структурного производного типа:

 blen[0] = 1;
 indices[0] = 0;
 oldtypes[0] = MPI_INT;
 blen[1] = 1;
 indices[1] = data.b — data;
 oldtypes[1] = MPI_CHAR;
 blen[2] = 1;
 indices[2] = sizeof(data);
 oldtypes[2] = MPI_FLOAT;
 MPI_Type_struct(3, blen, indices, oldtypes, newtype);

Регистрация и удаление производных типов

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

  int MPI_Type_commit(MPI_Datatype *datatype)
      MPI_Type_commit(datatype, ierr)
        

Аннулировать производный тип datatype можно с помощью вызова подпрограммы

  MPI_Type_free:
    int MPI_Type_free(MPI_Datatype *datatype)
      MPI_Type_free(datatype, ierr
        

Предопределенные (базовые) типы данных не могут быть аннулированы.

Пример – создание структурного типа

  #include "mpi.h"
  #include <stdio.h>
  struct newtype {
  float a;
  float b;
  int n;
  };
  int main(int argc,char *argv[])
  {
  int myrank;
  MPI_Datatype NEW_MESSAGE_TYPE;
  int block_lengths[3];
  MPI_Aint displacements[3];
  MPI_Aint addresses[4];
  MPI_Datatype typelist[3];
  int blocks_number;
  struct newtype indata;
  int tag = 0;
  MPI_Status status;
  

  MPI_Init(argc, argv);
  MPI_Comm_rank(MPI_COMM_WORLD, myrank);
  typelist[0] = MPI_FLOAT;
  typelist[1] = MPI_FLOAT;
  typelist[2] = MPI_INT;
  block_lengths[0] = block_lengths[1] = block_lengths[2] = 1;
  MPI_Address(indata, addresses[0]);
  MPI_Address((indata.a), addresses[1]);
  MPI_Address((indata.b), addresses[2]);
  MPI_Address((indata.n), addresses[3]);
  displacements[0] = addresses[1] — addresses[0];
  displacements[1] = addresses[2] — addresses[0];
  displacements[2] = addresses[3] — addresses[0];
  blocks_number = 3;
  MPI_Type_struct(blocks_number, block_lengths, displacements, typelist, NEW_MESSAGE_TYPE);
  MPI_Type_commit(NEW_MESSAGE_TYPE);
  

  if (myrank == 0)
  {
  indata.a = 3.14159;
  indata.b = 2.71828;
  indata.n = 2010;
  MPI_Send(indata, 1,NEW_MESSAGE_TYPE, 1, tag, MPI_COMM_WORLD);
  printf("Process %i send: %f %f %i\n", myrank, indata.a, indata.b, indata.n);
  }
  else
  {
  MPI_Recv(indata, 1, NEW_MESSAGE_TYPE, 0, tag, MPI_COMM_WORLD, status);
  printf("Process %i received: %f %f %i, status %s\n", myrank, indata.a, indata.b, indata.n, status.MPI_ERROR);
  }
  MPI_Type_free(NEW_MESSAGE_TYPE);
  MPI_Finalize();
  return 0;
  }
  

Как работает эта программа

Задаются типы членов производного типа.

Задаётся количество элементов каждого типа.

Вычисляются адреса элементов типа indata и определяются смещения трех членов производного типа относительно адреса первого, для которого смещение равно 0. Располагая этой информацией, можно определить производный тип, что и делается с помощью подпрограмм MPI_Type_struct и MPI_Type_commit .

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

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

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

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

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

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

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

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

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

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

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

размерность решетки (значение 2, например, соответствует плоской решетке);

размер решетки вдоль каждого измерения (размеры {10, 5}, например, соответствуют прямоугольной плоской решетке, протяженность которой вдоль оси x составляет 10 узлов-процессов, а вдоль оси y - 5 узлов);

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

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

Декартова топология

Познакомимся с операциями создания и преобразования декартовых топологий обмена. Подпрограмма MPI_Cart_create создает новый коммуникатор comm_cart, наделяя декартовой топологией исходный коммуникатор comm_old:

  int MPI_Cart_create(MPI_Comm comm_old, int ndims, int *dims, int *periods, int reorder, MPI_Comm *comm_cart)

MPI_Cart_create(comm_old, ndims, dims, periods, reorder, comm_cart, ierr)

Входные параметры:

comm_old - исходный коммуникатор;

ndims - размерность декартовой решетки;

dims - целочисленный массив, состоящий из ndims элементов, задающий количество процессов в каждом измерении;

periods - логический массив из ndims элементов, который определяет, является ли решетка периодической (значение true) вдоль каждого измерения;

reorder - при значении этого параметра "истина", системе разрешено менять порядок нумерации процессов.

Информация о структуре декартовой топологии содержится в параметрах ndims, dims и periods.

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

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

  int MPI_Cart_coords(MPI_Comm comm, int rank, int maxdims, int *coords)

MPI_Cart_coords(comm, rank, maxdims, coords, ierr)

Входные параметры:

comm - коммуникатор, наделенный декартовой топологией;

rank - ранг процесса в comm;

maxdims - длина вектора coords в вызывающей программе.

Выходным параметром этой подпрограммы является одномерный целочисленный массив coords (его размер равен ndims), содержащий декартовы координаты процесса.

Обратным действием обладает подпрограмма MPI_Cart_rank. С ее помощью можно определить ранг процесса (rank) по его декартовым координатам в коммуникаторе comm:

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

MPI_Cart_rank(comm, coords, rank, ierr)

Входной параметр coords - целочисленный массив размера ndims, задающий декартовы координаты процесса.

Пример

  #include "mpi.h";
  #include <stdio.h>;
  int main(int argc,char *argv[])
  {
  MPI_Comm grid_comm;
  int dims[2];
  int periodic[2];
  int reorder = 1, q = 5, ndims = 2, maxdims = 2;
  int coordinates[2];
  int my_grid_rank;
  int coords[2];
  MPI_Comm row_comm;
   dims[0] = dims[1] = q;
  periodic[0] = periodic[1] = 1;
  coords[0] = 0; coords[1] = 1;
  MPI_Init(argc, argv);
  MPI_Cart_create(MPI_COMM_WORLD, ndims, dims, periodic, reorder, grid_comm);
  MPI_Comm_rank(grid_comm, my_grid_rank);
  MPI_Cart_coords(grid_comm, my_grid_rank, maxdims, coordinates);
  printf("Process rank %i has coordinates %i %i\n", my_grid_rank, coordinates[0], coordinates[1]);
  MPI_Finalize();
  return 0;
  }

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

int MPI_Cart_get(MPI_Comm comm, int maxdims, int *dims, int *periods, int *coords)

MPI_Cart_get(comm, maxdims, dims, periods, coords, ierr)

Входной параметр maxdims задает длину массивов dims, periods и vectors в вызывающей программе, а выходные параметры:

dims - целочисленный массив, задающий количество процессов для каждого измерения;

periods - массив логических значений, задающих периодичность (true, если решетка периодическая) для каждого измерения;

coords - целочисленный массив, задающий декартовы координаты вызывающего подпрограмму процесса.

Топология графа

Подпрограмма MPI_Graph_create создает новый коммуникатор comm_graph, наделенный топологией графа:

int MPI_Graph_create(MPI_Comm comm, int nnodes, int *index, int *edges, int reorder, MPI_Comm *comm_graph)

MPI_Graph_create(comm, nnodes, index, edges, reorder, comm_graph, ierr)

Входные параметры:

comm - исходный коммуникатор, не наделенный топологией;

nnodes - количество вершин графа;

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

edges - целочисленный одномерный массив, описывающий ребра графа;

reorder - значение "истина" разрешает изменение порядка нумерации процессов.

Получить информацию о топологии графа, связанной с коммуникатором comm, можно с помощью подпрограммы MPI_Graph_get:

int MPI_Graph_get(MPI_Comm comm, int maxindex, int maxedges, int *index, int *edges)

MPI_Graph_get(comm, maxindex, maxedges, index, edges, ierr)

Входные параметры:

comm - коммуникатор;

maxindex - длина массива index в вызывающей программе;

maxedges - длина массива edges в вызывающей программе.

Выходные параметры:

index - целочисленный массив, содержащий структуру графа;

edges - целочисленный массив, содержащий сведения о ребрах графа.

Подпрограмма MPI_Graphdims_get позволяет получить информацию о топологии графа, связанной с коммуникатором comm:

  int MPI_Graphdims_get(MPI_Comm comm, int *nnodes, int *nedges)

MPI_Graphdims_get(comm, nnodes, nedges, ierr)

Выходными параметрами этой подпрограммы являются:

nnodes - количество вершин графа;

nedges - количество ребер графа.

Определить тип топологии (toptype), связанной с коммуникатором comm, можно с помощью подпрограммы:

int MPI_Topo_test(MPI_Comm comm, int *toptype)

MPI_TOPO_TEST(COMM, TOPTYPE, IERR)

Выходным параметром является тип топологии toptype (значения MPI_CART для декартовой топологии и MPI_GRAPH для топологии графа).