Homework 11

Details

You may work in teams of 2 on this project if you wish.

Implement either Mergesort or Quicksort using the algorithm given in the SIPC notes. Run tests to compare it with an optimized serial version and your naive parallel version from HW 9 (which you are welcome to improve a bit if you wish). Zip up the directory with all of your files and submit it using Web handin as usual.

Here are some resources you might find helpful

SPAC_CPP.pdf A version of the Parallelism and Concurrency written for OpenMP instead of Java.
QuickSortProject The starting files which you should already have from a previous assignment. However, if you downloaded this too early, your version will not have parallelCode.cpp which you should get. It has my version of parallel sum, parallel-prefix sum, and a start of the pack and partition algorithms. It also has methods that will test paralll sum, parallel-prefix sum, and pack.

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.)

A chart that compares the performance of the various algorithms. At a minimum, both parallel algorithms should be run on 1, 2, 4, 8, 16, 24, and 32 threads.
Discuss how the algorithms compare with each other. Is the new-and-improved algorithm better than your naive one? If not, explain why you think it is the case. Discuss what would happen if you had a lot more processors and/or larger arrays.
Grade yourself out of 20 points, providing a clear justification.

If you are unable to complete the implementation of quicksort, you may receive up to 13/20 points for a proper implementation of pack and up to 16/20 points for a proper implementation of partition (although if you get partition correct, there is no reason that you shouldn't also get quicksort correct). My code (given above) already has a test program for pack. If you get partition correct but not quicksort, include a program that tests your partition algorithm.

Here are my results from HugeTests.txt:

           In Order    Reversed   Random      Repeated  Clumped   Average
pQuickP1     No Data   No Data  20110140 (7)   No Data   No Data  20110140 (7)
pQuickP2     No Data   No Data  11751138 (7)   No Data   No Data  11751138 (7)
pQuickP4     No Data   No Data  10558189 (7)   No Data   No Data  10558189 (7)
pQuickP8     No Data   No Data   6403963 (7)   No Data   No Data   6403963 (7)
pQuickP16    No Data   No Data   4241028 (7)   No Data   No Data   4241028 (7)
pQuickP24    No Data   No Data   3525688 (7)   No Data   No Data   3525688 (7)
pQuickP32    No Data   No Data   3061767 (7)   No Data   No Data   3061767 (7)
fQuickP1     No Data   No Data  39916515 (7)   No Data   No Data  39916515 (7)
fQuickP2     No Data   No Data  39280604 (7)   No Data   No Data  39280604 (7)
fQuickP4     No Data   No Data  33353175 (7)   No Data   No Data  33353175 (7)
fQuickP8     No Data   No Data  18289919 (7)   No Data   No Data  18289919 (7)
fQuickP16    No Data   No Data   7671305 (7)   No Data   No Data   7671305 (7)
fQuickP24    No Data   No Data   9214110 (7)   No Data   No Data   9214110 (7)
fQuickP32    No Data   No Data   7341779 (7)   No Data   No Data   7341779 (7)