Modeling and Simulation Using Parallel Computing Assignment

1. Write a C program using MPI to implement parallel odd-even sort for the given total values of elements and cores. Your code will support 2m elements to sort, that is, the number of elements to sort is even. The number of cores p will be chosen such that 2m/p is even. That is, each core will have an even number of elements (this ensures that phase 1 requires no inter-process communication). The total number of cores p wont necessarily be even, but you are guaranteed that 2m/p is even. Each core will be assigned 2m/p elements. You can either use one large array (of size 2m) that each core will have a copy of, or define arrays of size 2m/p for each core. In phase 1, each core will do a compare-exchange on elements that are assigned to it. For example if there are 4 elements per core (stored in an array A), then core 0 will compareexchange A[0] and A[1], then A[2] and A[3] and so on for the other cores. In phase 2, each core will do a compare-exchange on the its own elements but also a compareexchange between the next core. For example if there are 4 elements per core (stored in array A) then core 0 will compare-exchange A[1] and A[2], then A[3] and A[4]. Note that A[4] is assigned to core 1 in this case. If there are 12 elements in total and 3 cores, then in phase 2: core 0 will compare-exchange its A[3] with core 1s A[4], core 1 will compare-exchange A[7] with A[8] in core 2. You need to generalize this for the scenario where there is an even number of elements and each core has an even number of elements assigned to it. Make sure you start with unsorted arrays. After m rounds of phase 1 and phase 2 i.e. 2m phases in total, the elements should be sorted. After this is complete, have each core send their current values to core 0 (in order), and have core 0 print the values in sorted order (see Hello2.c example in slides). Use a for loop to receive values from each core and print as you receive them, this ensures they will be printed in order of rank. Note: if ntasks >=20 then make sure tasks per node is fixed at 20 in your script when you experiment.

2. Generalize your code in part 1 to take into account an odd number of elements, and possibly an odd number of elements per core.

3. Generalize your code from part 2 to take into account when the number of elements is not divisible by the number of cores i.e. there may be a remainder. For example your code should handle when there are 15 elements and 4 cores.

Please submit your source code and scripts via Blackboard as a ZIP ARCHIVE.