Homework 13

Details

You may work in teams of 2 on this project if you wish. In fact you really should work with a partner on this one! It contains several challenges.

Implement either Mergesort or Quicksort (recommended) 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 8 (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.

Start by implementing packP and testing it (Change which test it runs by commenting/uncommenting at the end of the file, and compile using make parCode) and running it (./parCode). Then implement and test partitionP, making sure to change which test method gets called.

Here are some resources you might find helpful

1. SPAC_CPP.pdf A version of the Parallelism and Concurrency written for OpenMP instead of Java.
2. QuickSortProject The starting files which you should already have from a previous assignment. 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 parallel 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.)

1. 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.
2. 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.
3. Grade yourself out of 20 points, providing a clear justification.

Hand in your code using Webhandin 385-HW13.

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 (If you only implement partition so it works on a full array, it will need to be modified to work in Quicksork so it can work on just part of an array). 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 2023):

           In Order    Reversed   Random      Repeated  Clumped    Average
Quick2       No Data   No Data  20030716 (7)   No Data   No Data  20030716 (7)
pQuickP1     No Data   No Data  20217046 (7)   No Data   No Data  20217046 (7)
pQuickP2     No Data   No Data  12910157 (7)   No Data   No Data  12910157 (7)
pQuickP4     No Data   No Data   8132749 (7)   No Data   No Data   8132749 (7)
pQuickP8     No Data   No Data   5249098 (7)   No Data   No Data   5249098 (7)
pQuickP16    No Data   No Data   3657280 (7)   No Data   No Data   3657280 (7)
pQuickP24    No Data   No Data   3037894 (7)   No Data   No Data   3037894 (7)
pQuickP32    No Data   No Data   2726988 (7)   No Data   No Data   2726988 (7)
fQuickP1     No Data   No Data  28325679 (7)   No Data   No Data  28325679 (7)
fQuickP2     No Data   No Data  26838886 (7)   No Data   No Data  26838886 (7)
fQuickP4     No Data   No Data  23836322 (7)   No Data   No Data  23836322 (7)
fQuickP8     No Data   No Data  15874206 (7)   No Data   No Data  15874206 (7)
fQuickP16    No Data   No Data   5462368 (7)   No Data   No Data   5462368 (7)
fQuickP24    No Data   No Data   3619784 (7)   No Data   No Data   3619784 (7)
fQuickP32    No Data   No Data   2948947 (7)   No Data   No Data   2948947 (7)

           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)