-
13518104 Kevin Austin Stefano authoredd082082b
MST_OpenMPI.c 8.98 KiB
// IF3230 - Sistem Paralel dan Terdistribusi
// Michael Hans / 13518056
// Kevin Austin Stefano / 13518104
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <mpi.h>
#include <stddef.h>
// Edge structure
typedef struct
{
int src;
int dest;
int weight;
} Edge;
// Graph structure
typedef struct
{
int V; // number of vertices
int E; // number of edges
Edge *edge;
} Graph;
//Struct for OpenMPI
void makeStruct(MPI_Datatype *mpi_edge_type)
{
//Inisialisasi
MPI_Datatype types[3] = {MPI_INT, MPI_INT, MPI_INT};
MPI_Aint offset[3];
int block[3] = {1,1,1};
//Fill with our datatype
offset[0] = offsetof(Edge, src);
offset[1] = offsetof(Edge, dest);
offset[2] = offsetof(Edge, weight);
//Connect
MPI_Type_create_struct(3, block, offset, types, &(*mpi_edge_type));
MPI_Type_commit(&(*mpi_edge_type));
}
// Create new Graph based on V vertices and E edges
Graph *CreateGraph(int V, int E)
{
Graph *graph = (Graph *)(malloc(sizeof(Graph)));
graph->V = V;
graph->E = E;
graph->edge = (Edge *)(malloc(E * sizeof(Edge)));
return graph;
}
// Print all graph component to the CLI
void PrintGraph(Graph *graph)
{
printf("Vertices : %d\n", graph->V);
printf("Edges : %d\n", graph->E);
for (int i = 0; i < graph->E; i++)
{
printf("%d -- %d = %d\n", graph->edge[i].src, graph->edge[i].dest, graph->edge[i].weight);
}
}
// Implement the value of 2^x
int pow2(int x){
return 1 << x;
}
// Menuliskan array ke layar
void PrintArray(Edge arr[], int a, int b)
{
for (int i = a; i <= b; i++)
{
printf("%d ", arr[i-1].weight);
}
printf("%d\n", arr[b-1].weight);
}
// Melakukan partisi sembari menukar value dengan pivot ke-i
void Partisi(Edge T[], int i, int j, int *k)
{
Edge pivot = T[i - 1];
int p = i;
int q = j;
while (p <= q)
{
while (T[p - 1].weight < pivot.weight)
{
p++;
}
while (T[q - 1].weight > pivot.weight)
{
q--;
}
if (p < q)
{
Edge temp = T[p - 1];
T[p - 1] = T[q - 1];
T[q - 1] = temp;
p++;
q--;
}
else if (p == q)
{
p++;
}
}
*k = q;
}
// Mengurutkan array dengan menggunakan Quick Sort versi Sequential
void SequentialQuickSort(Edge T[], int i, int j)
{
int k;
if (i < j)
{
Partisi(T, i, j, &k);
SequentialQuickSort(T, i, k);
SequentialQuickSort(T, k + 1, j);
}
}
// Mengurutkan array dengan metode Quick Sort Parallel
void QuickSort(Edge T[], int i, int j, int rank, int max_rank, int rank_index){
MPI_Datatype mpi_edge_type;
makeStruct(&mpi_edge_type);
int distributed_process = rank + pow2(rank_index);
rank_index++;
// If the rank of distributed process is higher than max rank
if (distributed_process >= max_rank) {
SequentialQuickSort(T, i, j);
}
else {
int pivot;
Partisi(T, i, j, &pivot);
// Upper half of array is larger than lower half of array
if (pivot-i+1 > j-pivot){
MPI_Send(&T[pivot], j - pivot, mpi_edge_type, distributed_process, 1, MPI_COMM_WORLD);
QuickSort(T, i, pivot, rank, max_rank, rank_index + 1);
MPI_Recv(&T[pivot], j - pivot, mpi_edge_type, distributed_process, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
} else {
MPI_Send(&T[i-1], pivot - i + 1, mpi_edge_type, distributed_process, 1, MPI_COMM_WORLD);
QuickSort(T, pivot + 1, j, rank, max_rank, rank_index + 1);
MPI_Recv(&T[i-1], pivot - i + 1, mpi_edge_type, distributed_process, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
}
}
}
/// Create graph based from the adjacency matrix in file
Graph *ReadArguments()
{
Graph *graph = (Graph *)(malloc(sizeof(Graph)));
int V, weight;
scanf("%d", &V);
graph->V = V;
graph->edge = (Edge *)(malloc(((V * V - V) / 2) * sizeof(Edge)));
// Read the adjacency matrix
int E = 0;
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
scanf("%d", &weight);
// int r = (rand() % (2 * V)) + 1;
// int weight = (r < 0.3 * V) ? -1: r;
if ((weight != -1) && (i <= j))
{
graph->edge[E].src = i;
graph->edge[E].dest = j;
graph->edge[E].weight = weight;
E += 1;
}
}
}
graph->E = E;
return graph;
}
// Structure to represent a subset for union-find
typedef struct
{
int parent;
int rank;
} Subset;
// Create new subset
Subset *CreateSubset(int V)
{
Subset *subsets = (Subset *)(malloc(V * sizeof(Subset)));
// Create V subsets with single elements
for (int i = 0; i < V; i++)
{
subsets[i].parent = i;
subsets[i].rank = 0;
}
return subsets;
}
int find(Subset subsets[], int i)
{
// find root and make root as parent of i
// (path compression)
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
void Union(Subset subsets[], int x, int y)
{
int xroot = find(subsets, x);
int yroot = find(subsets, y);
// Attach smaller rank tree under root of high
// rank tree (Union by Rank)
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
// If ranks are same, then make one as root and
// increment its rank by one
else
{
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
// Compare two edges according to their weights.
int compare(const void *a, const void *b)
{
Edge *a1 = (Edge *)a;
Edge *b1 = (Edge *)b;
return a1->weight > b1->weight;
}
// Compare two sources according to their number
int compare_src(const void *a, const void *b)
{
Edge *a1 = (Edge *)a;
Edge *b1 = (Edge *)b;
return a1->src > b1->src;
}
// Minimum Spanning Tree using Kruskal's Algorithm
void KruskalMST(Graph *graph, Edge result[], int *e, int size, int rank)
{
int V = graph->V;
int i = 0;
// Step 1: Sort all the edges into correspendent sorted edges
QuickSort(graph->edge, 0, graph->E, rank, size, 0);
// PrintArray(graph->edge, 1, graph->E);
// Step 2: Allocate memory for creating V subsets
Subset *subsets = CreateSubset(V);
while (((*e) < V - 1) && (i < graph->E))
{
// Pick the smallest edge of the graph
Edge next_edge = graph->edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
if (x != y)
{
result[(*e)++] = next_edge;
Union(subsets, x, y);
}
}
// QuickSortSrc(graph->edge, 0, graph->E, size, rank);
// QuickSortSrc(result, 1, (*e));
qsort(result, *e, sizeof(result[0]), compare_src);
return;
}
void printResult(Edge *result, int e)
{
// Get the number of processes
int minimumCost = 0;
for (int i = 0; i < e; i++)
{
minimumCost += result[i].weight;
}
printf("%d\n", minimumCost);
for (int i = 0; i < e; i++)
{
printf("%d-%d\n", result[i].src, result[i].dest);
}
}
// Driver program to test above functions
int main()
{
MPI_Init(NULL, NULL);
// Get the number of processes
int size;
MPI_Comm_size(MPI_COMM_WORLD, &size);
// Get the rank of the process
int rank;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
// For the process with rank 0
if (rank == 0){
Graph *graph= ReadArguments();
Edge result[graph->E];
int e = 0;
double t = MPI_Wtime();
KruskalMST(graph, result, &e, size, rank);
t = MPI_Wtime() - t;
printResult(result, e);
// printf("Waktu Eksekusi: %f ms \n", (t * 1000));
// MPI_Abort(MPI_COMM_WORLD, EXIT_FAILURE);
} else {
MPI_Datatype mpi_edge_type;
makeStruct(&mpi_edge_type);
int idxcnt = 0;
int arrLength;
MPI_Status status;
// Calculate rank
while (rank >= pow2(idxcnt)) {
idxcnt = idxcnt+1;
}
// Get source of the sender
int source = MPI_Probe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
source = MPI_Get_count(&status, mpi_edge_type, &arrLength);
int src = status.MPI_SOURCE;
// Declare the array buffer to receive data from the source process
Edge* temp = (Edge *) malloc (sizeof(Edge) *arrLength);
source = MPI_Recv(temp, arrLength, mpi_edge_type, src, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
// Sort the received buffer with QuickSort
QuickSort(temp, 1, arrLength, rank, size, idxcnt);
// Send the sorted array back to the source process
source = MPI_Send(temp, arrLength, mpi_edge_type, src, 1, MPI_COMM_WORLD);
// printf("Process %d\n", rank);
free(temp);
}
MPI_Finalize();
return 0;
}