Assignment 2

The objective of this assignment is for you to gain experience in the following parallel programming languages/models:

Complete the following programming questions.  For each design efficient well comment codes and evaluate them carefully.

1) Create an MPI-based program that implements sample sort as described in "Parallel Sorting by Regular Sampling" by Hanmao Shi and Jonathan Schaeffer. Journal of Parallel and Distributed Computing, vol. 14, no. 4, pp. 361-372, 1992. You should design your sort to work with records that contain a key and data field..  You do not need to fully balance the resulting sorted output over the machine.  Your code may either read the input and generated the output to files distributed over your parallel machine or start and end with the data on PE 0, whichever you find easier. I have created an outline of a simple sample sort to aid you.

2) Write a sequential C program that implements Counting sort.

The pseudocode Counting Sort algorithm is as follows:

      countingsort(A[], B[], k)
	for i = 1 to k do
	   C[i] = 0
	   
	for j = 1 to length(A) do
	   C[A[j]] = C[A[j]] + 1
	   
	for 2 = 1 to k do
	   C[i] = C[i] + C[i-1]

	for j = 1 to length(A) do
	   B[C[A[j]]] = A[j]
	   C[A[j]] = C[A[j]] - 1

Although this may look complicated, it is actually a very simple and clever algorithm.
Array A[ ] stores the initial data to be sorted.
Array C[ ] is used to count the occurrences of the data values
Array B[ ] is used to store the final, sorted, list.
See "Introduction to Algorithms" by Cormen, Leiserson, Revest, (Stien) for details.

Using OpenMP create and evaluate an efficient parallel versions of this code.

Note: For each program you will be asked to evaluate its performance carefully. More details on the expected analysis and performance evaluation will follow in class. Please see parallel_trap.c as an example of how to time your application.