Группы, контексты, коммуникаторы и топологии
Группы
Группа представляет собой упорядоченное множество идентификаторов процессов (далее процессов). У каждого процесса в группе есть ранг — уникальное целое число в диапазоне от 0 до размера группы. Группы представлены непрозрачными объектами и, таким образом, не могут непосредственно передаваться от одного процесса другому. Группа используется внутри коммуникатора для описания процессов коммуникатора и присвоения им рангов. Существуют специальные предопределенные группы: MPI_GROUP_EMPTY в которой ничего нет, и MPI_GROUP_NULL, которая соответствует ошибочному объекту группы.
Контексты
Контекст — это свойство коммуникатора(определено далее), которое позволяет разделить коммуникационное пространство. Сообщение, отправленное в рамках одного контекста, не может быть получено в рамках другого. Контексты не являются явными MPI объектами, они представляют собой часть реализации коммуникаторов.
Коммуникаторы
Существуют два вида коммуникаторов: intra-communicators и inter-communicators. Intra-communicators, далее коммуникаторы, объединяют концепции групп и контекстов. Для поддержки реализационно-зависимых оптимизаций и топологий коммуникаторы могут кэшировать дополнительную информацию. Коммуникационные операции используют коммуникаторы для определения множества процессов, среди которых происходит коммуникация. Каждый коммуникатор содержит группу процессов, эта группа всегда включает локальный процесс. Отправитель и адресат сообщения определяются рангом в этой группе. Для коллективных коммуникаций коммуникатор определяет множество процессов, участвующих в коммуникации, и их порядок в тех случаях, когда это важно. Таким образом, коммуникатор ограничивает «пространственные» границы коммуникации и обеспечивает машинно-независимый механизм адресации процессов.
Существуют следующие предопределенные коммуникаторы, которые создаются один раз после вызова MPI_Init: MPI_COMM_WORLD,состоящий из всех процессов, с которыми может обмениваться данными локальный процесс (включая сам этот процесс), и MPI_COMM_SELF, содержащий только локальный процесс. Константа MPI_COMM_NULL используется для обозначения ошибочного значения коммуникатора.
В модели статических процессов, все процессы параллельной программы доступны после инициализации MPI. В этом случае MPI_COMM_WORLD содержит все процессы программы и является одним и тем же для всех процессов. В тех реализациях MPI, где допускается динамическое присоединение процессов к исполняющейся программе, возможен случай, когда процесс начинает работу, не имея доступа ко все остальным процессам. В таких случаях, MPI_COMM_WORLD объединяет те процессы, с которыми этот процесс может обмениваться данными. Таким образом, в различных процессах MPI_COMM_WORLD может быть различным. Все реализации MPI должны обеспечивать коммуникатор MPI_COMM_WORLD. Этот коммуникатор не может быть освобожден во время работы процесса. Группе, соотвествующей этому коммуникатору, не соответствует никакая предопределенная константа, но эта группа может быть получена MPI_Comm_group.
Функции работы с группами
Получение свойств группы
int MPI_Group_size(MPI_Group group, int *size)
— по адресу size записывается число процессов в группе
int MPI_Group_rank(MPI_Group group, int *rank)
— по адресу rank записывается ранг вызвавшего процесса в группе group
int MPI_Group_translate_ranks (MPI_Group group1, int n, int *ranks1, MPI_Group group2, int *ranks2)
— Вычисляет ранги процессов в группе group2 на основании их рангов в группе group1.
Если какой-то процесс из группы group1 отсутствует в группе group2, его ранг в group2 будет MPI_UNDEFINED.
int MPI_Group_compare(MPI_Group group1,MPI_Group group2, int *result)
— Если группы group1 и group2 содержат одни и те же процессы, у которых одинаковые ранги в обеих группах,
по адресу result записыватеся MPI_IDENT. Если же группы состоят из одних и тех же процессов, но процессы имеют
различные ранги в каждой группе, то по адресу result записывается MPI_SIMILAR. Иначе по адресу result записывается
значение MPI_UNEQUAL.
Создание группы
int MPI_Comm_group(MPI_Comm comm, MPI_Group *group)
— по адресу group создается группа, в которую входят все процессы коммуникатора comm
int MPI_Group_union(MPI_Group group1, MPI_Group group2, MPI_Group *newgroup)
— по адресу newgroup создается новая группа, состоящая из объединения процессов групп group1 и group2
int MPI_Group_intersection(MPI_Group group1, MPI_Group group2, MPI_Group *newgroup)
— по адресу newgroup создается новая группа, состоящая из пересечения процессов групп group1 и group2
int MPI_Group_difference(MPI_Group group1, MPI_Group group2, MPI_Group *newgroup)
— по адресу newgroup создается новая группа, состоящая из симметричной разности
(элементов, принадлежащих только одному из двух множеств) процессов групп group1 и group2
int MPI_Group_incl(MPI_Group group, int n, int *ranks, MPI_Group *newgroup)
— В группу newgroup попадают те и только те процессы группы group, ранги которых перечислены в массиве ranks
int MPI_Group_excl(MPI_Group group, int n, int *ranks, MPI_Group *newgroup)
— В группу newgroup попадают все процессы группы group, кроме тех, ранги которых перечислены в массиве ranks
int MPI_Group_range_incl(MPI_Group group, int n, int ranges[][3], MPI_Group *newgroup)
— В группу newgroup попадают те и только те процессы группы group,
которые попадают в один из диапазонов, перечисленных в массиве ranges. Каждый элемент ranges
представляет собой тройку (старый ранг, новый ранг, число процессов, начиная с ранга «старый ранг» )
int MPI_Group_range_excl(MPI_Group group, int n, int ranges[][3], MPI_Group *newgroup)
— В группу newgroup попадают все процессы группы group, кроме тех, которые попадают в один из диапазонов,
перечисленных в массиве ranges. Каждый элемент ranges представляет собой тройку
(старый ранг, новый ранг, число процессов, начиная с ранга «старый ранг» )
Деструктор группы
int MPI_Group_free(MPI_Group *group);
Функции работы с коммуникаторами
Получение свойств коммуникатора
int MPI_Comm_size(MPI_Comm comm, int *size)
— по адресу size записывается число процессов в коммуникаторе comm
int MPI_Comm_rank(MPI_Comm comm, int *rank)
— по адресу rank записывается ранг вызвавшего процесса в коммуникаторе comm
int MPI_Comm_compare(MPI_Comm comm1,MPI_Comm comm2, int *result)
— по адресу result записывается результат сравнения коммуникаторов comm1 и comm2. Результат сравнения равен
MPI_IDENT тогда и только тогда, когда comm1 и comm2 являются одним и тем же объектом
(если совпадают группы и контекст).
MPI_CONGRUENT, в случае, если группы совпадают, а контекст нет.
MPI_SIMILAR, в случае если группы коммуникаторов состоят из одних и тех же процессов,
имеющих различные ранги в каждой из групп
MPI_UNEQUAL — иначе
Создание коммуникатора
The following are collective functions that are invoked by all processes in the group associated with comm.
int MPI_Comm_dup(MPI_Comm comm, MPI_Comm *newcomm)
— по адресу newcomm создается новый коммуникатор, MPI_CONGRUENT коммуникатору comm
int MPI_Comm_create(MPI_Comm comm, MPI_Group group, MPI_Comm *newcomm)
— по адресу newcomm создается новый коммуникатор, состоящий из процессов группы group
int MPI_Comm_split(MPI_Comm comm, int color, int key, MPI_Comm *newcomm)
— по адресу newcomm создается новый коммуникатор, в который попадают все те процессы,
у которых одно и то же значение color.
Ранги процесса в новом коммуникаторе определяется параметром key
Деструктор коммуникатора
int MPI_Comm_free(MPI_Comm *comm)
Топологии
Как говорилось ранее, группа процессов в MPI это линейно упорядоченное множество процессов. Во многих случаях такое упорядочение не в полной мере отражает логическую схему взаимодействий процессов (обычно такая схема определяется геометрией решаемой задачи и свойствами реализуемого алгоритма). Часто используются декартовы топологии (решетки) различной размерности. Наиболее общим случаем топологии является граф, описывающий связи между процессами.
Необходимо различать виртуальные топологии (о них и пойдет речь) и топологию оборудования. Виртуальная топология может опираться на физическую для повышения производительности. Отображение виртуальной топологии на физическую реализуется вне стандарта MPI. Виртуальные топологии зависят только от приложения и не зависят от конкретного оборудования.
Создание декартовых топологий
int MPI_Cart_create(MPI_Comm comm_old, int ndims, int *dims, int *periods, int reorder, MPI_Comm *comm_cart)
— Создание коммуникатора comm_cart с декартовой топологией.
comm_old — исходный коммуникатор;
ndims — размерность создаваемой топологии;
dims — массив количеств процессов по каждому из измерений создаваемой топологии;
periods — массив флагов, указывающих необходимости «закольцовывать» топологию по соответствующему измерению;
reorder — флаг, указывающий, нужно ли перенумеровывать процессы;
comm_cart — Указатель на новый коммуникатор с декартовой топологией
int MPI_Dims_create(int nnodes, int ndims, int *dims)
—
int MPI_Cart_sub(MPI_Comm comm, int *remain_dims, MPI_Comm *newcomm)
— Разделяет декартову топологию коммуникатора comm на подтопологии. (Подробное описание здесь появится позже.)
Пример:
#include<mpi.h>
#include <stdio.h>
#include<stdlib.h>
int main(int argc, char** argv)
{
int periods[2],remains[2];
int*dims;
int newsize;
int rank,size,i,j;
MPI_Comm comm2D,comm1D[2],comm;
MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD,&rank);
if(argc <3)
{
if(!rank)
fprintf(stderr,"usage: cart ndims dim1...dimn\n");
MPI_Finalize();
exit(1);
}
dims=(int*)malloc(sizeof(int)*(argc-2));
for(int i=0;i <argc-2;i++)
{
dims[i]=atoi(argv[i+2]);
printf("[%d]: dims[%d]=%d\n",rank,i,dims[i]);
}
MPI_Comm_dup(MPI_COMM_WORLD,&comm);
periods[0]=0;
periods[1]=0;
MPI_Cart_create(comm,2,dims,periods,0,&comm2D);
for(i=0;i <2;i++)
{ for(j=0;j<2;j++)
remains[j]=(i==j);
MPI_Cart_sub(comm2D,remains,comm1D+i);
}
for(i=0;i <2;i++)
{
MPI_Comm_size(comm1D[i],&newsize);
printf("[%d]: New size is %d\n",rank,newsize);
}
for(i=0;i<2;i++)
MPI_Comm_free(comm1D+i);
MPI_Comm_free(&comm2D);
free(dims);
MPI_Finalize();
return 0;
}
Создание графовых топологий
int MPI_Graph_create(MPI_Comm comm_old, int nnodes, int *index, int *edges, int reorder, MPI_Comm *comm_graph)
comm_old — коммуникатор, содержащий процессы, из которых конструируется граф.
nnodes - число процессов — вершин графа
index — массив степеней вершин графа (далее будет подробное описание)
edges — массив дуг графа (далее будет подробное описание)
reorder — флаг, указывающий, нужно ли перенумеровывать процессы в новом коммуникаторе
comm_graph —адреc, по которому создается новый коммуникатор со сконструированой графовой топологией
Рассмотрим следующий граф, состоящий из 4х вершин: Вершина Соседи
0 1,3
1 0
2 3
3 0,2
Для того, чтобы создать топологию, соответствующую этому графу, необходимо передать в MPI_Graph_create следующие параметры:
nnodes=4
index={2,3,4,6}
edges={1,3,0,3,0,2}
index[i] содержит сумму степеней всех вершин с номерами <= i
Получение свойств топологий
int MPI_Topo_test(MPI_Comm comm, int *status)
— По адресу status записывается тип топологии: MPI_GRAPH в случае графовой топологии,
MPI_CART в случае декартовой топологии, MPI_UNDEFINED иначе.
К примеру, MPI_COMM_WORLD не имеет связанной с ним топологии, и результат будет MPI_UNDEFINED
int MPI_Graphdims_get(MPI_Comm comm, int *nnodes, int *nedges)
Возвращает число вершин и число дуг в графовой топологии коммуникатора comm;
Если топология не MPI_GRAPH, программа аварийно завершится или сработает перехватчик ошибок.
int MPI_Graph_get(MPI_Comm comm, int maxindex, int maxedges, int *index, int *edges)
— Получает представление графа, такое же, как использовалось при его создании.
Предполагается, что значения maxindex и maxedges получаются в результате вызова предыдущей функции.
int MPI_Cartdim_get(MPI_Comm comm, int *ndims)
— По адресу ndims записывает размерность декартовой топологии коммуникатора comm.
int MPI_Cart_get(MPI_Comm comm, int maxdims, int *dims, int *periods, int *coords)
— Получает параметры декартовой топологии коммуникатора comm;
int MPI_Cart_rank(MPI_Comm comm, int *coords, int *rank)
— По координатам процесса в декартовой топологии вычисляет его ранг.
int MPI_Cart_coords(MPI_Comm comm, int rank, int maxdims, int *coords)
— По рангу процесса в декартовой топологии вычисляет его координаты.
int MPI_Graph_neighbors_count(MPI_Comm comm, int rank, int *nneighbors)
— По адресу nneighbors записывается число соседей процесса с рангом rank в графовой топологии коммуникатора comm.
int MPI_Graph_neighbors(MPI_Comm comm, int rank, int maxneighbors, int *neighbors)
— В массив neighbors записываются ранги процессов — соседей процесса с рангом rank
в графовой топологии коммуникатора comm.
int MPI_Cart_shift(MPI_Comm comm, int direction, int disp, int *rank_source, int *rank_dest)
Пример работы с графовыми топологиями
#include <mpi.h>
#include<stdio.h>
#include<stdlib.h>
#define DBG(a) if(rank==(a))
int main(int argc, char** argv)
{
int rank,size;
int* neighbours, n;
int *nodes,*edges;
int nnodes,nedges,nprev=0;
MPI_Comm newcomm;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD,&size);
MPI_Comm_rank(MPI_COMM_WORLD,&rank);
nnodes=size;
nedges=0;
nodes=(int*)malloc(sizeof(int)*nnodes);
for(int i=0;i<nnodes;i++)
{
nodes[i]=2*(i+1);
nedges+=2;
}
edges=(int*)malloc(nedges*sizeof(int));
for(int i=0;i<nnodes;i++)
{
edges[nprev]=(i+1)%nnodes;
edges[nprev+1]=(i-1+nnodes)%nnodes;
nprev+=2;
}
DBG(0) printf("Before graph create\n");
nprev=0;
DBG(0)
{
for(int i=0;i<nedges;i++)
{
printf("%d: ",edges[i]);
}
printf("\n");
}
MPI_Graph_create ( MPI_COMM_WORLD, nnodes, nodes, edges, 0, &newcomm);
MPI_Graph_neighbors_count(newcomm,rank,&n);
neighbours=(int*)malloc(sizeof(int)*n);
MPI_Graph_neighbors(newcomm,rank,n,neighbours);
{
printf("[%d] My %d neighbours are: ",rank,n);
for(int k=0;k<n;k++)
printf("%d ",neighbours[k]);
printf("\n");
}
free(nodes);
free(neighbours);
free(edges);
MPI_Comm_free(&newcomm);
MPI_Finalize();
return 0;
}
Низкоуровневые функции создания топологий
int MPI_Cart_map(MPI_Comm comm, int ndims, int *dims, int *periods, int *newrank)
int MPI_Graph_map(MPI_Comm comm, int nnodes, int *index, int *edges, int *newrank)
Задание
Определение: Вершина v2 достижима из вершины v2 в графе G=(V,E), если существуют такие v1=u1,...,ui,...,un=v2, что дуги (ui,ui+1) принадлежат E.
Определение: граф G2 = (V,E2)является транзитивным замыканием графа G1 = (V,E1), если для любых v1, v2 из V, дуга (v1,v2) принадлежит E2 тогда и только тогда, когда v2 достижима из v1 в G1.
Задание 5
Написать функцию void ShowComm(MPI_Comm comm), которая:
Выводит тип топологии
Если топология !=MPI_UNDEFINED, то каждый процесс выводит число и ранги своих соседей
Если топология ==MPI_UNDEFINED, то функция выводит:«No topology associated with communicator, now exiting» и прекращает свою работу.
Написать функцию void ModifyComm(MPI_Comm comm, MPI_Comm* newcomm), которая принимает на вход коммуникатор, выводит его тип и:
В случае, если тип comm MPI_Graph, по адресу commnew записывает новый коммуникатор, представляющий собой транзитивное замыкание топологии коммуникатора comm;
В случае, если тип comm MPI_Cart, по адресу commnew записывает новый коммуникатор, представляющий собой срез декартовой топологии коммуникатора comm по последней размерности. (массив remains имеет вид {1,...,1,0})
Если топология ==MPI_UNDEFINED, то функция выводит:«No topology associated with communicator, now exiting» и прекращает свою работу.
Интеркоммуникаторы
В сложных модульных приложениях различные группы процессов исполняют различные части программы. В таких приложениях наиболее естественным образом определения адресата по группе и его рангу в ней. В приложениях, содержащих серверы пользовательского уровня, каждый сервер может являться группой процессов, в то время как клиенты, тоже являясь группами процессов, обращаются к одному или нескольким серверам. Интеркоммуникаторы предназначены для организации взаимодействия процессов, принадлежащих различным группам. Далее коммуникации «точка-точка» между процессами различных групп будут обозначены «интеркоммуникации» Группа, содержащая процесс, инициирующий интеркоммуникацию (отправитель в send или получатель в recv), назовем локальной группой. Группу же, содержащую другого участника коммуникации (получателя в send и отправителя в recv), далее назовем удаленной группой. Как и в обычных коммуникаторах, процесс определяется парой (коммуникатор, ранг), отличие заключается в том, что ранг указывается в удаленной группе, а не в локальной. Все конструкторы интеркоммуникаторов являются блокирующими. Кроме того, для избежания дедлоков необходимо, чтобы локальная и удаленная группа не пересекались. Далее следует summary свойств интеркоммуникаторов и интеркоммуникаций
Синтаксис обмена сообщениями такой же, как и в обычных коммуникаторах
Процесс идентифицируется рангом в группе
Интеркоммуникации не конфликтуют с коммуникациями
В интеркоммуникаторах не допускаются групповые коммуникации
Вид коммуникатора можно узнать, используя функцию MPI_Comm_test_inter
Получение свойств интеркоммуникатора
int MPI_Comm_test_inter(MPI_Comm comm, int *flag)
int MPI_Comm_size(MPI_Comm comm, int* size)
int MPI_Comm_rank(MPI_Comm comm, int* rank)
int MPI_Comm_group(MPI_Comm comm, MPI_Group* group)
int MPI_Comm_remote_size(MPI_Comm comm, int* size)
int MPI_Comm_remote_group(MPI_Comm comm, MPI_Group* group)
Создание интеркоммуникатора
int MPI_Intercomm_create(MPI_Comm local_comm, int local_leader, MPI_Comm peer_comm,
int remote_leader, int tag, MPI_Comm *newintercomm)
local_comm — один из двух коммуникаторов, из которых конструируется интеркоммуникатор,
local_leader — ранг лидера локальной группы в локальной группе
peer_comm — Коммуникатор, в котором происходят обмены сообщений между лидерами групп
(значим только в лидере локальной группы).
remote_leader — ранг лидера удаленной группы в коммуникаторе peer_comm
(значим только в лидере локальной группы)
tag — Тэг сообщений, используемых при коммуникаций между лидерами.
newintercomm — адрес, по которому создается новый интеркоммуникатор.
Из двух различных коммуникаторов конструируется новый интеркоммуникатор по адресу newintercomm (в каждом процессе значение localcomm — свое). При этом в локальной и удаленной группах должно существовать по одному процессу (лидеру группы); должен существовать коммуникатор peer_comm, содержащий оба лидера групп. Для корректной работы программы необходимо, чтобы значения тэга tag не использовались при вызове других функций MPI
int MPI_Intercomm_merge(MPI_Comm intercomm, int high, MPI_Comm *newintracomm)
intercomm — Исходный интеркоммуникатор;
high — логический флаг, определяющий нумерацию процессов в newintracomm.
Если в одной из групп high==0, а в другой high==1,
то процессы первой группы будут иметь ранги, меньшие рангов процессов второй группы.
newintracomm — адрес, по которому создается коммуникатор.
Уничтожение интеркоммуникатора
int MPI_Comm_free(MPI_Comm* comm)
Задание 6
Создать коммуникаторы, в которые входят процессы с четными и нечетными рангами, соответственно, и создать интеркоммуникатор между ними. Продемонстрировать их работу на каком-либо простом примере.