Description

GitHub Invitation Link

Accept the GitHub invitation, wait until you get an email saying the import is complete, and then clone the git repository to your local machine.

The goal of this project is to gain experience with writing, tuning, and measuring performance of a concurrent algorithm, in this case a sorting algorithm.

Write a standard (sequential) templated quicksort algorithm as a functor that can operate on a standard C++ container supporting random access (e.g. std::vector), passed by reference. Then write a concurrent version using std::async with the ability to use at most N threads, where N is set at run-time when the functor is constructed, and adapting to the size of the list to be sorted. The functor templates should work for any type supporting comparison. Take care to choose a good pivot. Write both versions from scratch, that is do not use std::sort or qsort(3).

Your implementation of quick sort algorithm should be in cqsort.hpp or cqsort.tpp. It is okay to change the starter code in cqsort.hpp but you should make sure not to break test_cqsort.cpp, which will be overwritten at grading.

Write tests for both versions to ensure they work properly for both built in numeric types and a type that overloads comparisons.

Next, write a program to run the sequential and concurrent sort for inputs ranging in size from 1 to 10^6 increasing by powers of 10, randomly generated with 10 repeats. Use std::chrono to time each sort call. Print out your results to a text file in the following format.

Your implementation of benchmarking should be in cqbench.cpp. The compiled binary, cqbench, does not take any command line arguments.

List Size   Sequential Sort Time (s)   Concurrent Sort Time (s)
             min     max    average     min     max    average
---------   -----   -----   -------    -----   -----   -------
1
10
100
1000
...

Tune the limiting value of N for your machine that gives the best performance relative to the sequential implementation. Compare this empirically optimal N to the value of std::thread::hardware_concurrency() for your machine.

In a plain text file name README.md explain how you tuned your concurrent algorithm and the results of your timing tests. This should be around 6-10 paragraphs and include the output of your final run.

Design Specification

Your design must:

• use a functor for both the sequential and concurrent sorts
• implement a recursive quick-sort and use a non-trivial pivot
• adapt the number of threads used based on the list size and a maximum number set in the functor constructor.

Testing

You should have unit tests using Catch for each sort that covers. Basic tests are included in the file test_cqsort.cpp, which is supposed not to modify. Add your additional test to unittests.cpp. These tests, as well as your timing program, should be able to run in the reference VM (although it has a single virtual CPU and will be much slower).

Submission

Your submission must consist of a git repository containing only the source code and any supporting test and configuration files (Vangrantfile, CMakeLists.txt, tests directory and other files provided in the starter repository).

To submit your assignment, either the beta or final versions:

1. Tag the git commit that you wish to be considered for grading as “final”.

   git tag <tagname>
   

   If you want to have multiple versions of the tags, name them sequentially, i.e. final, final2, final3, etc. We will consider the last one present in the repository when it is pulled for grading.

2. Push this change to GitHub

   git push origin <tagname>
   

Be sure you have committed all the changes you intend to by the respective due dates. Failure to complete these steps by the due date will result in no credit being assigned.