
Write a program in C that does Old-Even sort with MPI (i.e., cluster computing)
- 5th Jun, 2019
- 17:21 PM
Question
Write a program in C that does Old-Even sort with MPI (i.e., cluster computing)
Answer
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <mpi.h>
#define N 400
void swap(int* x, int* y)
{
int swp = *x;
*x = *y;
*y = swp;
}
void print_array(int *array, int n)
{
// print array's content 10 elements per row
for (int i = 0; i < n; i++)
{
if (i % 10 == 0)
printf("\n");
printf("%d, ", array[i]);
}
printf("\n");
}
// serial selection sort
void sort(int *array, int n)
{
for (int i = 0; i < n - 1; i++)
{
int k = i;
for (int j = i + 1; j < n; j++)
if (array[k] > array[j])
k = j;
swap(&array[i], &array[k]);
}
}
int main(int argc, char **argv)
{
// Initialize the MPI environment
MPI_Init(&argc, &argv);
// Get the number of processes
int world_size;
MPI_Comm_size(MPI_COMM_WORLD, &world_size);
// Get the rank of the process
int world_rank;
MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
// a pointer to the array to be sorted
int *array = NULL;
if (world_rank == 0) // root process
{
srand(42); // seed random number generator
array = malloc(sizeof(int) * N);
// populate array with random numbers in -100 .. 100 range
for (int i = 0; i < N; i++)
{
array[i] = rand() % 200 - 100;
}
printf("\n\nBefore sorting: ");
print_array(array, N);
}
// the number of array elements per process
int chunk_size = N / world_size;
// allocate memory for 2 arrays: one to hold a local
// copy of the array chunk and
// another for a neighbor's local copy
int *local_array = malloc(sizeof(int) * chunk_size);
int *other_array = malloc(sizeof(int) * chunk_size);
// distribute array chunks between processes
MPI_Scatter(array, chunk_size, MPI_INT, local_array, chunk_size, MPI_INT, 0, MPI_COMM_WORLD);
for (int k = 0; k < world_size; k++)
{
// sort local array
sort(local_array, chunk_size);
// find the neighbor process for current (k-th) phase
int other_rank = (k % 2 == world_rank % 2) ? world_rank + 1 : world_rank - 1;
// skipping invalid neighbor rank
if (other_rank < 0 || other_rank >= world_size)
continue;
// exchange local array data with neighbor (even process sends first)
if (world_rank % 2 == 0)
{
MPI_Send(local_array, chunk_size, MPI_INT, other_rank, 0, MPI_COMM_WORLD);
MPI_Recv(other_array, chunk_size, MPI_INT, other_rank, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
}
else
{
MPI_Recv(other_array, chunk_size, MPI_INT, other_rank, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
MPI_Send(local_array, chunk_size, MPI_INT, other_rank, 0, MPI_COMM_WORLD);
}
// order local and other arrays based on the relative order of their processes' ranks
int *smaller_array = world_rank < other_rank ? local_array : other_array;
int *larger_array = world_rank < other_rank ? other_array : local_array;
// keep smaller elements in smaller_array and
// larger elements in larger_array
// larger array is iterated from the beginning
// and smaller array is iterated from the end
for (int i = 0; i < chunk_size; i++)
{
int j = chunk_size - 1 - i;
if (smaller_array[j] <= larger_array[i])
break;
swap(&smaller_array[j], &larger_array[i]);
}
}
// send ordered and sorted local_arrays to the root process
MPI_Gather(local_array, chunk_size, MPI_INT, array, chunk_size, MPI_INT, 0, MPI_COMM_WORLD);
// deallocate memory
free(other_array);
free(local_array);
if (world_rank == 0)
{
printf("\n\nAfter sorting: ");
print_array(array, N);
free(array); // deallocate memory
}
// Finalize the MPI environment.
MPI_Finalize();
return 0;
}