代码代写｜ECE3574 Project 4: Concurrent QuickSort

这是一篇美国的并发快速排序代码代写

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.

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:

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:

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.

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.