Homework 4
cs599 Parallel Programming and Algorithms
5 points
Due Friday, Mar. 20, 2015 at 11:59:59pm

1. Ensure that the MPI version of quicksort provided on the class examples page evenly balances the number of items assigned to each process by using the MPI_Scan function.

2. Manually perform a bitonic sort on the following sequence:

[7, 441, 89, 343, 99, 27, 65, -67]

3. Write an MPI version of sample sort that will work well with a uniformly distributed random sequence of 5,000,000 elements. Your program must generate n/p elements in each process where p is the number of processes. Samples from each process representing 1% of the process’s data must be sent to a “master” process. You could use process rank 0 to represent the “master”. The master process must sort the samples, and send to each process in ascending order of rank, the ranges of values that process and every other process must collect. After each process receives these ranges, each process must send values in the appropriate range to the corresponding process. Said processes must also receive values within their ranges. Once all data has been received, it must be sorted locally using quicksort. You must time your program with MPI_Wtime().

4. Using the Stampede Supercomputer, run parallel, MPI-based Odd-Even Sort, Quicksort, and Sample Sort on 1,000,000, 2,000,000, 4,000,000, 8,000,000, and 16,000,000 integer elements using 16 and 32 processes. Create a graph and plot the runtimes for each data point. You must include axis labels, a title, and a legend in your graph.