Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <mpi.h>
- #include <stdio.h>
- #include <string.h>
- #include <stdlib.h>
- /**
- * @author cristian.chilipirea
- * Run: mpirun -np 12 ./a.out
- */
- int graph[][2] = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 11}, {11, 5}, {5, 6}, {6, 7}, {7, 8}, {8, 9}, {9, 10}, {10, 9}, {9, 8}, {8, 7}, {7, 6}, {6, 5}, {5, 11}, {11, 4}, {4, 3}, {3, 2}, {2, 1}, {1, 0}, {9, 5}, {5, 9}, {5, 3}, {3, 5}, {0, 2}, {2, 0}, {9, 7}, {7, 9}};
- int *getNeighbors(int myRank)
- {
- int *neigh = malloc(sizeof(int) * 100);
- int i;
- int j = 1;
- for (i = 0; i < 30; i++)
- {
- if (graph[i][0] == myRank)
- {
- neigh[j] = graph[i][1];
- j++;
- }
- }
- neigh[0] = j;
- return neigh;
- }
- int *getLocalTopology(int myRank, int *neigh)
- {
- int *topology = malloc(sizeof(int) * 100);
- int i;
- int j = 1;
- for (i = 1; i < neigh[0]; i++)
- {
- topology[2 * j] = myRank;
- topology[2 * j + 1] = neigh[i];
- j++;
- }
- topology[0] = j;
- return topology;
- }
- int IsSame(int *vec1, int *vec2)
- {
- if (vec1[0] == vec2[0] && vec1[1] == vec2[1])
- {
- return 1;
- }
- else if (vec1[1] == vec2[0] && vec1[0] == vec2[1])
- {
- return 1;
- }
- return 0;
- }
- void Concat(int *Top1, int *Top2)
- {
- int count = Top1[0];
- int bool;
- for (int i = 1; i < Top2[0]; i++)
- {
- bool = 0;
- for (int j = 1; j < Top1[0]; j++)
- {
- if (IsSame(Top2 + (2 * i), Top1 + (2 * j)))
- {
- bool = 1;
- }
- }
- if (bool == 0)
- {
- Top1[2 * count] = Top2[2 * i];
- Top1[2 * count + 1] = Top2[2 * i + 1];
- count++;
- }
- }
- Top1[0] = count;
- }
- int main(int argc, char *argv[])
- {
- int rank;
- int nProcesses;
- MPI_Init(&argc, &argv);
- MPI_Status status;
- MPI_Request request;
- MPI_Comm_rank(MPI_COMM_WORLD, &rank);
- MPI_Comm_size(MPI_COMM_WORLD, &nProcesses);
- printf("Hello from %i/%i\n", rank, nProcesses);
- int *neigh = getNeighbors(rank);
- int i;
- char aux[1000];
- aux[0] = 0;
- sprintf(aux + strlen(aux), "Rank %i vecinii: ", rank);
- for (i = 1; i < neigh[0]; i++)
- {
- sprintf(aux + strlen(aux), " %i,", neigh[i]);
- }
- sprintf(aux + strlen(aux) - 1, "\n");
- printf("%s", aux);
- // YOU ARE ONLY ALLOWED TO COMMUNICATE WITH NEIGHBOR PROCESSES
- // The goal of the first exercise is to pretend you don't have graph and rebuild it in a distributed manner
- // The goal of the second exercise is to build routing tables. Routing tables are a list of destination + next hope.
- // Routing table for 5 is:
- // 0 -> 3 ; 1 -> 3 ; 2 -> 3 ; 3 -> 3 ; 4 -> 3 ; 5 -> 5 ; 6 -> 6 ; 7 -> 6 ; 8 -> 9 ; 9 -> 9 ; 10 -> 9 ; 11 -> 11
- int *LocTop = getLocalTopology(rank, neigh);
- for (int i = 0; i < 100; i++)
- {
- for (int j = 1; j < neigh[0]; j++)
- {
- MPI_Send(LocTop, 100, MPI_INT, neigh[j], 0, MPI_COMM_WORLD);
- }
- for (int j = 1; j < neigh[0]; j++)
- {
- int *NewTop = (int *)malloc(100 * sizeof(int));
- MPI_Recv(NewTop, 100, MPI_INT, neigh[j], 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
- Concat(LocTop, NewTop);
- }
- }
- printf("Bye from %i/%i\n", rank, nProcesses);
- if (rank == 0)
- {
- for (i = 1; i < LocTop[0]; i++)
- {
- printf("%d -> %d\n", LocTop[2 * i], LocTop[2 * i + 1]);
- }
- }
- int Parent[12] = {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
- int *Q = malloc(12 * sizeof(int));
- Q[0] = 0;
- int T = 1;
- int H = 0;
- while (H < T)
- {
- int *neigh = getNeighbors(Q[H]);
- for (int i = 1; i < neigh[0]; i++)
- {
- if (Parent[neigh[i]] == -1)
- {
- Parent[neigh[i]] = Q[H];
- Q[T] = neigh[i];
- T++;
- }
- }
- H++;
- }
- int *Parent2 = malloc(12 * sizeof(int));
- for (int i = 0; i < 12; i++)
- {
- Parent2[i] = -1;
- }
- int num;
- if (rank == 0)
- {
- for (int i = 0; i < 12; i++)
- {
- printf("%d ", Parent[i]);
- }
- printf("\n");
- num = 22;
- int find = 10;
- while (find != 0)
- {
- Parent2[find] = Parent[find];
- find = Parent[find];
- }
- for (int i = 0; i < 12; i++)
- {
- printf("%d ", Parent2[i]);
- }
- printf("\n");
- }
- MPI_Bcast(Parent2, 12, MPI_INT, 0, MPI_COMM_WORLD);
- if (rank == 0)
- {
- int index;
- for (int i = 0; i < 12; i++)
- {
- if (Parent2[i] == 0)
- {
- index = i;
- }
- }
- printf("I'm %d and I send to %d\n", rank, index);
- MPI_Send(&num, 1, MPI_INT, index, 0, MPI_COMM_WORLD);
- }
- if (Parent2[rank] != -1)
- {
- int index;
- for (int i = 0; i < 12; i++)
- {
- if (Parent2[i] == rank)
- {
- index = i;
- }
- }
- //printf("I'm %d and I received from %d\n", rank, Parent2[rank]);
- MPI_Recv(&num, 1, MPI_INT, Parent2[rank], 0, MPI_COMM_WORLD, NULL);
- if (rank != 10)
- {
- printf("I'm %d and I send to %d\n", rank, index);
- MPI_Send(&num, 1, MPI_INT, index, 0, MPI_COMM_WORLD);
- }
- }
- if (rank == 10)
- {
- printf("%d: %d\n", rank, num);
- }
- MPI_Finalize();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement