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
Your implementation of quick sort algorithm should be in
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.
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.
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).
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:
- 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.
- 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.
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: firstname.lastname@example.org 微信号:vipnxx