Homework 9

Details

Complete your parallel implementation of either Mergesort or Quicksort. Your goal is to make it as fast as possible. Zip up your files and submit them using Web handin.

In case you missed it, you need to add -fopenmp to the CFLAGS in the Makefile. If you don't add this none of your code will actually be compiled using OpenMP.

Note: I just discovered a version of the notes we are starting this week written for OpenMP instead of Java. They may or may not help you with this assignment, but just in case, you can find them here: SPAC_CPP.pdf.

Submit a hard-copy of a write-up that includes the following. (Please take the write-up seriously and don't just throw it together at the last minute.)

1. A brief description of your algorithm. Focus on how you parallelized it.
2. A chart showing its performance against the serial version (The runSorts program should help with this). Run the parallel version with 2, 4, and 8 threads (Note: The lab machines technically only have 4 cores and use hyperthreading to make it seem like 4. Therefore your results for 4 and 8 cores will likely be close to the same.) and create a chart showing the results of the runSorts program for each of these along with the serial version. If you have access to a machine with more cores, run in on that as well.
3. Discuss how the running time scales with the number or processors. Is it what you would expect? Clearly explain, referring to Amdahl's law.
4. Give a tight bound on the expected running time of your parallel algorithm assuming you had k cores. Make sure you justify your analysis. Hint: It may not be exactly what you expect it to be. Think about the merge process.
5. Discuss any limitations of your parallel algorithm. Could it be made faster? If so, explain.
6. Grade yourself out of 20 points, providing a clear justification.