CS 336: Homework

Implementing a Parallel Bitonic Sort with MPI (due Thurs. Dec. 4)

In this homework, you will be implementing the bitonic sort we went over in class with MPI.

What to Do

  1. Create a directory hw8 which contains the directories src and bin. Download bitonic_sort.c and save it in the src directory. Copy mpi.sh and Makefile into it from your hw6/src directory.
  2. Add support for the parallel version according to the comments in bitonic_sort.c and the pseudocode on the slides from November 6. Notes:
    1. Notice that I implemented the 2 bit-related functions that you need - flipbit and bit.
    2. I also included a function log2i which determines the base 2 logarithm of an integer.
    3. And I updated the print_array function to print everything on the same line, and to use sprintf to get all of the output into a string variable so that there is a single printf in the function. This will ensure that printouts of values in arrays on different processors won't be intermingled.
    4. In the pseudocode, I refer to the merge functions as merge_up and merge_down. They should probably be called bitonic_merge_up and bitonic_merge_down to avoid any confusion. The merge operation we need for the bitonic sort is NOT the same as that used in a sequential merge sort. A bitonic merge iterates through each index in the array and compares the values only at that index (see the pseudocode).
    5. In the pseudocode, I assume their exists a function getPartnerData(prank). I suggest you implement instead a function exchangeDataWithPartner that takes rank, prank, my_array, another array (perhaps their_array?), and length_per_process. It should send my_array to the partner processor and receive data (into their_array) from that processor.
  3. 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