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. You will need millions of data items per processor to see speedup.

2) The goal of this question is to give you some experience using OpenMP to speed-up an existing C++ code. Start by reading carefully the following links

• Introduction to Particle Swarm Optimization - http://mnemstudio.org/particle-swarm-introduction.htm
• Particle Swarm Optimization C++ Code with example problem- http://mnemstudio.org/particle-swarm-example-1.htm

Particle Swarm Optimization (PSO) is a derivitive free optimization method (like Genetic Algorithms or Simulated Alealing) that uses a population of "solutions" to home in on a final answer to a provided search problem. Proceed as follows:

1. Get the sequential code working and running on a single core.
2. Instrurment the code so you can collect timings. What are the code phases you want to divide time into? Cretae a script which can run all the tests and generate output that is easily read into a graphing program (Excel?) for analysis.
3. Carefully run your the sequential code on the 6 examples provided and generate a base line set of timings (to be included in your report).
4. Analyze your timing results and the options for parallelism in the code. Create a plan for parallelization. This plan and the rationalization for it needs to go in your report. Make the best plan you can but relize things may take a different direction once you get into the "Analyze, Optimize, Time it" loop.
5. Using OpenMP create and evaluate efficient parallel versions of this code. Seek to do at least 3 things to improve the performance of the code. For each present the idea, the code changes, and the performance results. For each change you should have a seperate directory with the code and timing results in your final submission
6. Finally, for your best version (which likely combines a variety of optimizations) analyse the results. How do the timings and the example input parameters interact? Given the randomness of the search process how many times do you need to run each experiment in order to manage the timing varience?

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.