What is the communication pattern of the following MPI program? int main(int argc, char** argv) { int* arr = NULL; int chunk_size, own_chunk_size; int* chunk; double start_time, run_time; MPI_Status status; if (!(argc >= 2)) { printf("Number of array elements was not provided as first argument to program\n"); } int n = atoi(argv[1]); int p, rank; int rc = MPI_Init(&argc, &argv); if (rc != MPI_SUCCESS) { printf("Error in creating MPI " "program.\n " "Terminating......\n"); MPI_Abort(MPI_COMM_WORLD, rc); } MPI_Comm_size(MPI_COMM_WORLD, &p); MPI_Comm_rank(MPI_COMM_WORLD, &rank); if (rank == 0) { printf("Number of Elements is %d \n", n); if ((n % p) != 0) { printf("ERROR: number of elements must be evenly divisible by number of processors\n"); exit(-1); } // Compute chunk size chunk_size = (n % p == 0) ? (n / p) : (n / (p - 1)); arr = (int*)malloc(p * chunk_size * sizeof(int)); // Read in the elements from the input file for (int i = 0; i < n; i++) { arr[i] = (rand() % 99999) + 1; } // Pad the data with zeroes if not enough elements are provided to fill the array for (int i = n; i < p * chunk_size; i++) { arr[i] = 0; } // Print the unsorted array printf("Elements in the unsorted array: \n"); printArray(arr, n); printf("\n"); } // Block all processes until this point is reached by all MPI_Barrier(MPI_COMM_WORLD); // Start Timer start_time = MPI_Wtime(); // BroadCast the Size from root to all the processes MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD); // Compute chunk_size chunk_size = (n % p == 0) ? (n / p) : (n / (p - 1)); // Calculate total chunk size according to bits chunk = (int*)malloc(chunk_size * sizeof(int)); // Scatter the chunk size data to all process MPI_Scatter(arr, chunk_size, MPI_INT, chunk, chunk_size, MPI_INT, 0, MPI_COMM_WORLD); free(arr); arr = NULL; // Compute size of each local chunk and then sort them with quicksort own_chunk_size = (n >= chunk_size * (rank + 1)) ? chunk_size : (n - chunk_size * rank); // Sort the array with quicksort for every chunk as called by process quicksort(chunk, 0, own_chunk_size); for (int step = 1; step < p; step = 2 * step) { if (rank % (2 * step) != 0) { MPI_Send(chunk, own_chunk_size, MPI_INT, rank - step, 0, MPI_COMM_WORLD); break; } if (rank + step < p) { int received_chunk_size = (n >= chunk_size * (rank + 2 * step)) ? (chunk_size * step) : (n - chunk_size * (rank + step)); int* chunk_received; chunk_received = (int*)malloc(received_chunk_size * sizeof(int)); MPI_Recv(chunk_received, received_chunk_size, MPI_INT, rank + step, 0, MPI_COMM_WORLD, &status); arr = merge(chunk, own_chunk_size, chunk_received, received_chunk_size); free(chunk); free(chunk_received); chunk = arr; own_chunk_size = own_chunk_size + received_chunk_size; } } // Stop timer run_time = MPI_Wtime() - start_time; // Open the other file as taken from input and write it to the output file if (rank == 0) { // Print the results of quicksort printf("Total number of Elements given as input : " "%d\n", n); printf("Sorted array is: \n"); printArray(chunk, n); printf( "\n\nQuicksort %d ints on %d procs: %f secs\n", n, p, run_time); } MPI_Finalize(); return 0; } a) One-to-all broadcast b) All-to-one reduction c) All-to-all broadcast and reduction d) All-reduce & prefix sum e) Scatter and Gather f) All-to-All Personalized
What is the communication pattern of the following MPI
int main(int argc, char** argv)
{
int* arr = NULL;
int chunk_size, own_chunk_size;
int* chunk;
double start_time, run_time;
MPI_Status status;
if (!(argc >= 2)) {
printf("Number of array elements was not provided as first argument to program\n");
}
int n = atoi(argv[1]);
int p, rank;
int rc = MPI_Init(&argc, &argv);
if (rc != MPI_SUCCESS) {
printf("Error in creating MPI "
"program.\n "
"Terminating......\n");
MPI_Abort(MPI_COMM_WORLD, rc);
}
MPI_Comm_size(MPI_COMM_WORLD, &p);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
if (rank == 0) {
printf("Number of Elements is %d \n",
n);
if ((n % p) != 0) {
printf("ERROR: number of elements must be evenly divisible by number of processors\n");
exit(-1);
}
// Compute chunk size
chunk_size = (n % p == 0) ? (n / p) : (n / (p - 1));
arr = (int*)malloc(p * chunk_size * sizeof(int));
// Read in the elements from the input file
for (int i = 0; i < n; i++) {
arr[i] = (rand() % 99999) + 1;
}
// Pad the data with zeroes if not enough elements are provided to fill the array
for (int i = n; i < p * chunk_size; i++) {
arr[i] = 0;
}
// Print the unsorted array
printf("Elements in the unsorted array: \n");
printArray(arr, n);
printf("\n");
}
// Block all processes until this point is reached by all
MPI_Barrier(MPI_COMM_WORLD);
// Start Timer
start_time = MPI_Wtime();
// BroadCast the Size from root to all the processes
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
// Compute chunk_size
chunk_size = (n % p == 0) ? (n / p)
: (n / (p - 1));
// Calculate total chunk size according to bits
chunk = (int*)malloc(chunk_size * sizeof(int));
// Scatter the chunk size data to all process
MPI_Scatter(arr, chunk_size, MPI_INT, chunk, chunk_size, MPI_INT, 0, MPI_COMM_WORLD);
free(arr);
arr = NULL;
// Compute size of each local chunk and then sort them with quicksort
own_chunk_size = (n >= chunk_size * (rank + 1)) ? chunk_size
: (n - chunk_size * rank);
// Sort the array with quicksort for every chunk as called by process
quicksort(chunk, 0, own_chunk_size);
for (int step = 1; step < p; step = 2 * step)
{
if (rank % (2 * step) != 0) {
MPI_Send(chunk, own_chunk_size, MPI_INT,
rank - step, 0,
MPI_COMM_WORLD);
break;
}
if (rank + step < p) {
int received_chunk_size = (n >= chunk_size * (rank + 2 * step)) ? (chunk_size * step)
: (n - chunk_size * (rank + step));
int* chunk_received;
chunk_received = (int*)malloc(received_chunk_size * sizeof(int));
MPI_Recv(chunk_received, received_chunk_size, MPI_INT, rank + step, 0, MPI_COMM_WORLD, &status);
arr = merge(chunk, own_chunk_size, chunk_received, received_chunk_size);
free(chunk);
free(chunk_received);
chunk = arr;
own_chunk_size = own_chunk_size + received_chunk_size;
}
}
// Stop timer
run_time = MPI_Wtime() - start_time;
// Open the other file as taken from input and write it to the output file
if (rank == 0)
{
// Print the results of quicksort
printf("Total number of Elements given as input : "
"%d\n",
n);
printf("Sorted array is: \n");
printArray(chunk, n);
printf(
"\n\nQuicksort %d ints on %d procs: %f secs\n",
n, p,
run_time);
}
MPI_Finalize();
return 0;
}
a) One-to-all broadcast
b) All-to-one reduction
c) All-to-all broadcast and reduction
d) All-reduce & prefix sum
e) Scatter and Gather
f) All-to-All Personalized
Step by step
Solved in 2 steps
