Using C Programming Language, Implement a parallelized version of the odd-even t
ID: 3920129 • Letter: U
Question
Using C Programming Language, Implement a parallelized version of the odd-even transposition sort.
You will generate an array of 2048 random numbers of type intto test the parallelized algorithm. The algorithm assumes that the number of data items to be sorted is evenly divisible by the number of processes.
You will test the program under different configurations and measure the timings for each configuration. The different configurations to use for testing are:
1. Eight nodes with one process per node. This assigns 256 data items per process.
2. Eight nodes with two processes per node. This assigns 128 data items per process.
3. Eight nodes with four processes per node. This assigns 64 data items per process.
4. Eight nodes with eight processes per node. This assigns 32 data items per process.
Graph the elapsed time vs comm_sz (processes per node). Clearly show the configuration associated with each graph
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "mpi.h"
#define N 10000
#define MAX_ITEM 3*N
#define ROOT_RANK 0
#define MAX_OUTPUT 20
// Comparison function used by qsort
int compare_ints(const void* arg1, const void* arg2)
{
int a1 = *(int *)arg1;
int a2 = *(int *)arg2;
if (a1 < a2 ) return -1;
else if (a1 == a2 ) return 0;
else return 1;
}
// Wrapper for qsort for integers. This sorts the array
// in place.
void qsort_ints(int *array, int array_len)
{
qsort(array, (size_t)array_len, sizeof(int), compare_ints);
}
// Print out the contents of an array if the array
// is short enough
void print_array(int *array, int array_len)
{
int i;
for (i = 0; i < array_len && i < MAX_OUTPUT; i++)
{
printf("%d ",array[i]);
if ((i+1)%5 == 0)
printf(" ");
}
printf(" ");
}
// Sort the array in place using the odd-even interchange sort.
void sequential_odd_even_sort(int *array, int length)
{
int done = 0, i, tmp;
while (!done)
{
done = 1;
// odd/even pairs
for (i = 1; i < length-2; i+=2)
{
if (array[i] > array[i+1])
{
tmp = array[i];
array[i] = array[i+1];
array[i+1] = tmp;
done = 0;
}
}
// even/odd pairs
for (i = 0; i < length-1; i+=2)
{
if (array[i] > array[i+1])
{
tmp = array[i];
array[i] = array[i+1];
array[i+1] = tmp;
done = 0;
}
}
} // end while !done
} // end sequential_odd_even_sort
// Print a message indicating whether or not the arrays
// are identical.
void compare_arrays(int *a1, int *a2, int len)
{
int i;
if (a1 == NULL || a2 == NULL)
{
printf("One of the arrays is null ");
return;
}
for (i = 0; i < len; i++)
if (a1[i] != a2[i])
{
printf("The arrays don't match! ");
return;
}
printf("The comparison test succeeded ");
} // end compare_arrays
// Allocate space on the heap for an integer array of length len.
// Fill it with integers pseudo-randomly chosen from the range
// 0 to MAX_ITEM-1;
int *create_random_int_array(int len)
{
int i;
int *ret;
ret = (int *)malloc(sizeof(int)*len);
srand(1); // Seed the random number generator with a 1 so that the same
// array will be created every time the program is called.
// To get a different set of values for each run, seed it with
// the clock instead, i.e. srand(time(NULL));
for (i=0; i<len; i++)
ret[i] = rand() % MAX_ITEM;
return ret;
} // create_random_int_array
int main(int argc, char **argv)
{
// Variables Stephanie used to write her parallel version.
// You may or may not need all of them.
const int TAG = 1; // the tag used for MPI_Send and MPI_Recv
MPI_Status status; // the status used for MPI_Recv
int numprocs, rank; // the number of processes, rank of this process
int rc; // error code
int i, tmp; // loop control and swap variables
int *array = NULL; // pointer to full original array (that only root uses)
int *my_array = NULL; // pointer to my section of the array
int *sorted_array = NULL; // pointer to sorted array (that only root uses)
int length; // length of the full array
int length_per_process; // length of each processes part of the array
int local_count = 0; // variable used to indicated whether or not this processes'
// array segment is sorted
int global_count; // variable to keep track of the number or processes whose
// array segments are sorted
int left, right; // variables to store the boundary values sent to use from
// our left (rank-1) and right (rank+1) neighbors
/******* Initialize *******/
rc = MPI_Init(&argc,&argv);
if (rc != MPI_SUCCESS) {
printf ("Error starting MPI program. Terminating. ");
MPI_Abort(MPI_COMM_WORLD, rc);
}
MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
MPI_Comm_rank(MPI_COMM_WORLD,&rank);
// LET'S MAKE THE PROBLEM SIZE SUIT US RATHER THAN
// WRITE LOTS OF CODE TO MAKE SURE WE CAN HANDLE ODD_SIZED DATA.
// THIS IS A MASSIVE HACK!!!!
// Call me Lizzy Borden.
length_per_process = N/numprocs;
// if the number of items per proc is not even, then reduce it
// so it is even
if (length_per_process%2 != 0)
length_per_process--;
// If the number of items is not evenly divisible by the processors,
// the reduce it so that it is.
length = length_per_process*numprocs;
// Assume only the root has access to the input. It needs to send it to the rest
// of the processors. In this case, we mimic input by randomly creating an array.
if (rank == ROOT_RANK)
array = create_random_int_array(length);
// Scatter the data by sending parts of it from the
// root process to each of the other processes. The root
// process does send data to itself, so my_array must be
// a valid address on the root proccess. On non-root processes,
// the first three arguments are ignored.
// YOUR CODE GOES HERE!
// While not all processes have sorted sections, do the odd even sort.
// This means we sort our section, send our boundary values to our
// neighbors (procs rank-1 and rank+1), and receive boundary values
// from our neighbors. If necessary our boundary values were out of
// order with respect to our neighbor's boundary values, then use
// set our boundary values to be those or our neighbor's.
// For each loop through the algorithm, determine whether or not this
// process has a sorted segment of the array. Then, use MPI_Reduceall
// to count the number of processes that have finished. If all have
// finished, then stop looping. Otherwise, continue.
// YOUR CODE GOES HERE!
// Gather the array segments onto the root (in the variable
// sorted_array)
// YOUR CODE GOES HERE!
// Test the result to make sure it is correct.
if (rank == ROOT_RANK)
{
// Use a local odd-even sequential sort as a reference
// If you would prefer to use qsort, then replace
// the call to sequential_odd_even_sort with qsort_ints(array,length);
sequential_odd_even_sort(array,length);
// Compare the array sorted sequentially (array) with the
// array sorted in parallel (sorted_array). They should be
// the same.
compare_arrays(array,sorted_array,length);
}
/******* Finalize *******/
MPI_Finalize();
// free my_array, sorted_array, and array as necessary
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.