Теория и практика параллельных вычислений



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


Сведения по функциям MPI для работы с виртуальными топологиями типа граф будут рассмотрены более кратко – дополнительная информация может быть получена, например, в [[4], [40]

– [42], [57]].

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

int MPI_Graph_create(MPI_Comm oldcom, int nnodes, int *index, int *edges, int reorder, MPI_Comm *graphcom),

где

  • oldcom — исходный коммуникатор;
  • nnodes — количество вершин графа;
  • index — количество исходящих дуг для каждой вершины;
  • edges — последовательный список дуг графа;
  • reorder — параметр допустимости изменения нумерации процессов;
  • graphcom – создаваемый коммуникатор с топологией типа граф.

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


Рис. 5.9.  Пример графа для топологии типа звезда

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

ПроцессыЛинии связи
01, 2, 3, 4
10
20
30
40

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

/* Создание топологии типа звезда */ 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),

где

  • comm — коммуникатор с топологией типа граф;
  • rank — ранг процесса в коммуникаторе;
  • nneighbors — количество соседних процессов.

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

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

где

  • comm — коммуникатор с топологией типа граф;
  • rank — ранг процесса в коммуникаторе;
  • mneighbors — размер массива neighbors;
  • neighbors — ранги соседних в графе процессов.




Содержание  Назад  Вперед