Aflarea topologiei unei retele distribuite (avand ca reprezentare un graf aciclic)

O astfel de retea este de fapt un arbore. Fiecare nod isi cunoaste doar vecinii, iar radacina fiind procesul initiator trebuie sa cunoasca intreaga topologie.

Initial, radacina ca oricare nod isi cunoaste doar propriii fii. Isi creeaza propria matrice de adiacenta pe care o trimite fiilor, care la randul lor o completeaza cu informatiile cunoscute de ei referitoare la fii. Cand matricea ajunge intr-un nod frunza, se incepe trimiterea in sens invers catre radacina a matricei. Daca procesul nu este frunza, odata ce a primit de sub el isi completeaza matricea proprie cu informatiile adunate de la fii, si o trimite mai departe pana cand se ajunge la radacina si se afiseaza topologia.

#include "mpi.h"

#include "stdio.h"

int main(argc,argv)

int argc;

char *argv[]; {

// un arbore cu n=7 noduri

int m[7][7],i,j;

for(i=0; i<=6 ;i++)

for(j=0; j<=6 ; j++)

m[i][j] = 0;

m[0][1] = m[1][0] = 1;

m[0][2] = m[2][0] = 1;

m[1][3] = m[3][1] = 1;

m[4][1] = m[1][4] = 1;

m[5][2] = m[2][5] = 1;

m[5][6] = m[6][5] = 1;

int numtasks, rank, dest, source, rc, count, tag=1;

MPI_Status Stat;

MPI_Request req;

MPI_Init(&argc,&argv);

MPI_Comm_size(MPI_COMM_WORLD, &numtasks);

MPI_Comm_rank(MPI_COMM_WORLD, &rank);

if (rank == 0) {

int newm[7][7],j; //matricea de la care porneste

for(i=0; i<=6 ;i++)

for(j=0; j<=6 ; j++) {

if(j==rank) {

newm[rank][i] = m[rank][i];

newm[i][rank] = newm[rank][i];

}

else {

newm[j][i] = 0;

newm[i][j] = 0;

}

}

int nr_copii = 0;

for(i=1; i<=6 ; i++)

if(m[0][i]==1) {

nr_copii++;

rc = MPI_Send(newm, 7*7, MPI_INT, i, tag, MPI_COMM_WORLD);

}

int rec[7][7];

for(i=0; i<=nr_copii-1; i++) {

rc = MPI_Recv(&rec, 7*7, MPI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, &Stat);

int k;

for(j=0; j<=6 ; j++)

for(k=0; k<=6 ; k++)

if(rec[j][k] == 1)

newm[j][k] = 1;

}

int k;

for(j=0; j<=6; j++) {

for(k=0; k<=6 ; k++)

printf("%d ", newm[j][k]);

printf("\n");

}

}

else {

int newm[7][7],j; //matricea de la care porneste

for(i=0; i<=6 ;i++)

for(j=0; j<=6 ; j++) {

if(j==rank) {

newm[rank][i] = m[rank][i];

newm[i][rank] = newm[rank][i];

}

else {

newm[j][i] = 0;

newm[i][j] = 0;

}

}

MPI_Status src;

int recv[7][7];

rc = MPI_Recv(&recv, 7*7, MPI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, &src);

for(i=0; i<=6 ; i++)

for(j=0; j<=6 ; j++)

if(recv[i][j]==1)

newm[i][j] = 1;

int nr_copii = 0;

for(i=0; i<=6 ; i++)

if(m[rank][i]==1 && i!=src.MPI_SOURCE) {

nr_copii++;

rc = MPI_Send(newm, 7*7, MPI_INT, i, tag, MPI_COMM_WORLD);

}

if(nr_copii==0) { //frunza, trimite in sus

rc = MPI_Send(&newm, 7*7, MPI_INT, src.MPI_SOURCE, tag, MPI_COMM_WORLD); }

else { // primeste de jos

for(i=0; i<=nr_copii-1; i++) {

rc = MPI_Recv(&recv, 7*7, MPI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, &Stat);

for(i=0; i<=6; i++)

for(j=0; j<=6 ; j++)

if(recv[i][j]==1)

newm[i][j] = 1;

}

rc = MPI_Send(&newm, 7*7, MPI_INT, src.MPI_SOURCE, tag, MPI_COMM_WORLD);

}

}

MPI_Finalize();

}