CS 336: Homework

Implementing an Odd/Even Interchange Sort with MPI (due Thurs. Nov. 6)

In this homework, you will be implementing the odd/even interchange sort with MPI. I am providing a code skeleton odd_even_sort.c that also contains the sequential version of the sort. Briefly, this means that we repeat a 2-phase operation until the entire list is sorted. The first phase is the odd/even phase, in which each pair of array items array[i] and array[i+1] (where i is odd and i+1 is even) is compared. If array[i] > array[i+1], then the values are swapped. The second phase is the even/odd phase, in which each pair of array items array[i] and array[i+1] (where i is even and i+1 is odd) are compared and swapped as necessary. The two phases are repeated until no swaps are necessary. To implement this sort in parallel, we simply assign each processor a segment of the array. The odd/even interchange sort is performed on each segment, and boundary values are sent to and received from neighboring processors. To make the algorithm simpler to implement, I guarantee that each processor has an even number of items. This means that during the odd/even phase of each iteration, inter-processor communication is necessary, but that during the even/odd phase all data is available locally.

What to Do

  1. Create a directory hw6 which contains the directories src and bin.
  2. Download odd_even_sort.c, Makefile, and mpi.sh into hw6/src.
  3. Compile the code by typing make odd_even_sort and run it by typing ./mpi.sh odd_even_sort 8. If you get the error message -bash: ./mpi.sh: Permission denied, then mpi.sh is not executable. Make it executable by typing chmod +x mpi.sh (this changes the permissions on the file to make it executable for the owner, group, and world - for more information see man chmod). Let me know if there is a problem. Remember that on NSCC, you should expect to see warning messages like this one:
    --------------------------------------------------------------------------
    [0,1,3]: uDAPL on host nscc was unable to find any NICs.
    Another transport will be used instead, although this may result in
    lower performance.
    --------------------------------------------------------------------------
    and that the output explicitly generated by odd_even_sort is redirected to a file named outfile.
  4. Familiarize yourself with the sequential version of the sort and with the skeleton code. In particular, note that create_random_int_array() uses a pseudo-random number generator. The seed (set by srand() determines which sequence of numbers will be produced. As the code is currently written, the generator is seeded with the number 1, which means that every time the code is run (on the same computer with the same rand library), the same sequence will be used. This is great for debugging, but not so great for testing code on different data sets. To create different data sets, replace the call srand(1) with srand(time(NULL)).
  5. Add support for the parallel version by following the instructions in the comments of the main function. Your general approach should be to loop while there is still at least one process that hasn't completely sorted its data. In each iteration through the loop, you will need to handle the communication of boundary values (using MPI_Send and MPI_Recv) and of the flag indicating whether or not each process has fully sorted its segment (I suggest you use MPI_Reduceall with MPI_SUM as the operation).
  6. Thoroughly test your code.

What to Turn In

Turn in your code by emailing me. There is no need to collect runtimes for this assignmenet. Put "CS336" in your subject line so that my mail filters will catch it and I will notice it right away.

Expectations

Back to Homework Page