Синхронный MST с MPI

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

Я начал неделю назад и все еще пытаюсь создать код C ++ / MPI из псевдокода, описанного в книге. Может кто-нибудь дать мне хорошую ссылку или код, который я могу использовать в качестве руководства?

Я делаю это правильно до сих пор?

#include <mpi.h>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cfloat>

static const int SEARCH_MWOE_TAG    = 1;
static const int EXAMINE_TAG        = 2;
static const int MAX_NODES          = 4;

//used in the graph structure
struct Edge {
int    target;
double weight;

Edge(){
weight = target = 0;
}

Edge(int t, double w) {
target = t;
weight = w;
}
};

//the minimum weight outgoing edge used for messages
struct Mwoe_type {

int leader;
int remot_id;
int local_id;
double weight;

Mwoe_type(){
leader = remot_id = local_id = 0;
weight = DBL_MAX;
}

Mwoe_type(int le, int lo, int re , double we) {
leader   = le;
local_id = lo;
remot_id = re;
weight   = we;
}

bool operator< (const Mwoe_type& other){
return weight < other.weight;
}
};

using adj_list = std::vector< Edge >;/*
Creates a new mpi structure to use for send/receive.
*/
void commit_edge_type(MPI_Datatype *newType);

/*
sends an EXAMINE message along unmarked (i.e., non-tree) edges
to determine if the other end of the edge is in the same component.

Returns the request vector to be used for wait the replys of mwoe.
*/
std::vector< MPI_Request > examine(adj_list &, int &);

/*
broadcast SEARCH_MWOE(leader) along marked edges of tree
*/
void search_mwoe(adj_list &, int &);

//convergecast
void reply_mwoe(Mwoe_type &);void makeUnmarked( int id_process, adj_list &unmarked_edges ){
//a small test graph
switch (id_process) {
case 0:
unmarked_edges.push_back( Edge( 1, 9.0 ) );
unmarked_edges.push_back( Edge( 2, 5.0  ) );
break;

case 1:
unmarked_edges.push_back( Edge( 0, 9.0 ) );
unmarked_edges.push_back( Edge( 2, 2.0  ) );
unmarked_edges.push_back( Edge( 3, 6.0  ) );
break;

case 2:
unmarked_edges.push_back( Edge( 0, 5.0 ) );
unmarked_edges.push_back( Edge( 1, 2.0  ) );
unmarked_edges.push_back( Edge( 3, 3.0  ) );
break;

case 3:
unmarked_edges.push_back( Edge( 1, 6.0 ) );
unmarked_edges.push_back( Edge( 2, 3.0  ) );
break;

default:
break;
}

}

int main(int argc, char** argv) {

MPI_Init( &argc, &argv);
MPI_Request request;
MPI_Status status;

MPI_Datatype MPI_mwoe;
commit_edge_type(&MPI_mwoe);

int id_process;
MPI_Comm_rank( MPI_COMM_WORLD, &id_process );

adj_list marked_edges  ;
adj_list unmarked_edges;

//every node begins with itself on marked edges list
marked_edges.push_back( Edge(id_process, 0.0) );

//a simple example
makeUnmarked( id_process, unmarked_edges );int leader = id_process;

int nodes_on_mst = 1;
//while all nodes arent on the MST
while ( nodes_on_mst != MAX_NODES ) {

//1) [the root always initiate with a broadcast]
if( leader == id_process ) {
search_mwoe( marked_edges , leader);
}

//synchronize and read messages ... how to make this ?
//MPI_Barrier(MPI_COMM_WORLD);
//MPI_Probe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);

//received search message and isn`t a leader ... propagates the broadcast
if( leader != id_process && status.MPI_TAG == SEARCH_MWOE_TAG ){
search_mwoe( marked_edges , leader);
}

//2)
std::vector< MPI_Request > request_vector;
Mwoe_type minimum;
if (status.MPI_TAG == SEARCH_MWOE_TAG) {

//2) A [on receive of a search message broadcast a examine on unmarked edges]
request_vector = examine( unmarked_edges, leader );

//2) B [Pick the minimum outgoing edge]
for (auto &e : unmarked_edges) {
Mwoe_type local( leader, id_process, e.target, e.weight );
if( local < minimum )
minimum = local;
}
}

//3) [Convergecast] to be continued ...
if( status.MPI_TAG == EXAMINE_TAG ) {

if( marked_edges.size() == 1 ) { //leaf node
//faz um send para o no que enviou mensagem de examine com a mwoe
}

else {
//use request_vector to check the answer of each examine TAG sent and continue the convergecast
for ( auto& r: request_vector ) {
MPI_Wait(&r, &status);
}
}

}

//broadcast add mwoe... to be continued
if( id_process == leader ) {
++nodes_on_mst;
}

}MPI_Finalize();
}

//this will be used to send the minimum weight outgoing edge
void commit_edge_type(MPI_Datatype *newType){

int      lengths[2] = { 3, 1 };
MPI_Aint offsset[2];
MPI_Datatype types[2] = { MPI_INT, MPI_DOUBLE };

MPI_Aint adress1,adress2;

Mwoe_type obj;
MPI_Get_address( &obj, &adress1 );

MPI_Get_address( &obj.leader, &adress2 );
offsset[0] = adress2 - adress1;

MPI_Get_address( &obj.weight   , &adress2 );
offsset[1] = adress2 - adress1;

MPI_Type_create_struct( 2, lengths, offsset, types, newType );
MPI_Type_commit(newType);
}

std::vector< MPI_Request > examine(adj_list &unmarked_edges, int &leader){
std::vector< MPI_Request > request_vector;
for (auto &e : unmarked_edges) {
MPI_Request request;
MPI_Isend( &leader, 1, MPI_INT, e.target , EXAMINE_TAG , MPI_COMM_WORLD, &request );
request_vector.push_back(request);
}
return request_vector;
}

void reply_mwoe(Mwoe_type &, int target){
//nothing here for now
}

void search_mwoe(adj_list &marked_edges, int &leader){
MPI_Request request;
for (auto &e : marked_edges) {
MPI_Isend( &leader, 1, MPI_INT, e.target , SEARCH_MWOE_TAG , MPI_COMM_WORLD, &request );
}
}

Вот псевдокод для алгоритма:

1. если лидер = я, то
Трансляция SEARCH_MWOE (лидер) вдоль отмеченных краев дерева (раздел 5.5.5).

2. При получении сообщения SEARCH_MWOE (лидера), которое транслировалось по отмеченным краям:
(a) Каждый процесс i (включая лидера) отправляет сообщение EXAMINE по немаркированным (то есть, не относящимся к дереву) ребрам, чтобы определить, находится ли другой конец ребра в том же компоненте (то есть является ли его лидер тем же).
(b) Из всех инцидентных ребер в i, для которых другой конец принадлежит другому компоненту, процесс i выбирает свой инцидент MWOE (localID, remoteID).

3. Конечные узлы в MST внутри компонента инициируют конвергентность
(Раздел 5.5.5) с использованием REPLY_MWOE, информируя их родителя об их MWOE (localID, remoteID).
Все узлы участвуют в этом сближении.

4. если лидер = я, то
ожидайте конвергентных ответов по отмеченным краям.
Выберите минимальное MWOE (localID, remoteID) из всех ответов.
транслировать ADD_MWOE (localID, remoteID) по отмеченным краям дерева (раздел 5.5.5).
// Просить процесс localID пометить localID remoteID
// ребро, т.е. включаем его в MST компонента.

5. если ребро MWOE помечено обоими компонентами, на которые оно падает, то
(a) Определите new_leader как процесс с большим идентификатором, в котором произошел этот MWOE (то есть процесс, идентификатор которого является максимальным localID remoteID).
(b) new_leader идентифицирует себя как лидера для следующего раунда.
(c) new_leader транслирует NEW_LEADER во вновь сформированном компоненте вдоль отмеченных ребер (раздел 5.5.5), объявляя себя лидером следующего раунда.