Группы, контексты, коммуникаторы и топологии

 

Группы

 

Группа представляет собой упорядоченное множество идентификаторов процессов (далее процессов). У каждого процесса в группе есть ранг — уникальное целое число в диапазоне от 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

 

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