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.
QUESTION 1:
a) 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 payload 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.
b) Perform a careful and extensive brenchmarking exersize on your code for 1a. Describe how your program works, your experimental setup, your experiments and analysis. Please see parallel_trap.c as an example of how to time your application.
QUESTION 2:
a) Kakro, also known as cross sums, is a recent puzzle craze. You can find Kakro puzzles in both the Guardian and the National Post newspapers. These puzzles look a bit like "math based" crossword puzzle. The numbers, that appear in the black margins, represent the sums of the digits that you will insert into the empty squares. A number above a diagonal line refers to the empty squares to the right of that number, and a number below a diagonal line refers to the squares below that number. No zeros appear in the puzzle, and no digit is repeated in a particular number. An example taken from the Dell Magazine Cross Sum page is given below.
a) Create a sequential C++ program that reads a Kakro puzzle from a text file and using exhustive recursive enumeration finds the unique solution. The key recursive routine might look something like this:
solve(int location)
If location == gridSize // puzzle has been solved
display();
return true;
else
Check each integer v between 1 and 9
if v is OK in location //meaning that row, col and no duplicates conditions are met
set location to v
return solve(nextEmptyLocation(l))
else return false
If you are unsure of how to go about designing a recursive enumeration you might want to look over this sample java Maze_Search program. You might be interested in this sample input formats and a matching output display formats.
b) Now design and implement a parallel shared memory version using OpenMP.
c) Produce a brief report describing and analyzing your solution. Your report should include the following items: