Homework 11

Details

Work alone or in pairs on this assignment.

Complete your parallel implementation of Quicksort. Your goal is to make it as fast as possible. Use the test files largeTests.txt and reallyLargeTests.txt as you are optimizing your code. When you are satisfied with your implementation, run runSorts on the file hugeTests.txt and put the results in a file called hugeTestResults.txt.

You should already have the base code, but if not it is here: QuickSortProject.zip

Note: There is an OpenMP version of some notes we will be studying later in the semester linked below (we will go through the Java version). They may or may not help you with this assignment, but just in case, you can find them here: SPAC_CPP.pdf.

Zip up the directory with all of your files and use Webhandin 385-HW11. to submit it.

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. Your output from running hugeTests.txt. Add a final column that gives the speedup versus the first trial (pQuickP1).
3. A chart showing its performance against the serial version on the hugeTests.txt file with 2, 4, 8, 12, 16, 24, and 32 threads. Plot the numbers from the average column using Excel or a similar program so you can see the trend.
4. Discuss how the running time scales with the number or processors. Is it what you would expect? Try to explain why or why not.
5. 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.
6. Discuss any limitations of your parallel algorithm. What is the limiting factor of how much you can parallelize it? Could it be made faster? If so, explain.
7. Grade yourself out of 20 points, providing a clear justification.

For purposes of comparison, here is my output for hugeTests.txt:

             In Order  Reversed Random         Repeated  Clumped  Average
pQuickP1     No Data   No Data  19743513 (7)   No Data   No Data  19743513 (7)
pQuickP2     No Data   No Data  14265134 (7)   No Data   No Data  14265134 (7)
pQuickP4     No Data   No Data  10995513 (7)   No Data   No Data  10995513 (7)
pQuickP8     No Data   No Data   5709799 (7)   No Data   No Data   5709799 (7)
pQuickP16    No Data   No Data   4191602 (7)   No Data   No Data   4191602 (7)
pQuickP24    No Data   No Data   3482685 (7)   No Data   No Data   3482685 (7)
pQuickP32    No Data   No Data   3175726 (7)   No Data   No Data   3175726 (7)