讲解：C++ CS6771 Assignment Five 2017C/C++

Introduction需要提交的文件为：BucketSort.h BucketSort.cpp主要思路就是不断将区间二分，同时创建子线程，然后各个子线程分别使用bucket sort然后再由父线程归并CS6771 Assignment Five 2017Parallel Bucket SortDue Date: 11:59pm Sunday 29 October 2017Worth: 10%Aims:To learn how to write multithreaded programs in C++To learn how to use mutex locks to avoid race conditions in multiplethreadsTo learn about potential performance bottlenecks and performanceevaluation of parallel programsYour task is to take a slow single threaded sort algorithm andredesign it into a parallel radix sort algorithm that sorts a vectorof numbers as quickly as possible.The sorting algorithm takes a vector of unsigned ints and sorts themby using a MSD (Most Significant Digit) radix sort, which useslexicographic order.For example, given a vector [ 32, 53, 3, 134, 643, 3, 5, 12, 52,501, 98 ], the sorted output would be [ 12, 134, 3, 3, 32, 5, 501,52, 53, 643, 98 ] (as if a shorter number were conceptually left-justified and padded on the right with “-1” to make it as long asthe longest number for the purposes of determining sorted order).A MSD radix sort can be done easily through a parallel bucket sort.A bucket sort takes the most significant digit of each number andgroups the list of numbers with the same digit into one bucket. Forexample, the vector given above may be split into the followingbuckets according their most significant digits:Bucket 1: [ 134, 12 ]Bucket 3: [ 32, 3, 3 ]Bucket 5: [ 53, 5, 52, 501]Bucket 6: [ 643 ]Bucket 9: [ 98 ]Afterwards, each bucket is sorted recursively, starting with thenext most significant digit:Bucket 1: [ 12, 134 ]Bucket 3: [ 3, 3, 32 ]Bucket 5: [ 5, 501, 52, 53]Bucket 6: [ 643 ]Bucket 9: [ 98 ]Finally, all the buckets are concatenated together in order: [ 12,134, 3, 3, 32, 5, 501, 52, 53, 643, 98 ]Requirements:In this assignment, you will need to create two files:BucketSort.cpp and BucketSort.h. These files can contain as manyclasses, functions and structs as you require. However, because thisassignment is about speed, there is no requirement that anystructure must strictly adhere to object oriented design principles(e.g., structure member fields do not need to be private). For anysingle-threaded solution without using multiple threads, a mark of 0will be awarded.BucketSort.h must contain the following struct (which can be addedto):#ifndef BUCKET_SORT_H#define BUCKET_SORT_H#include struct BucketSort {// vector of numbersstd::vector numbersToSort;void sort(unsigned int numCores);};#endif / BUCKET_SORT_H /The member field numbersToSort will be modified by user code to addnumbers to be sorted to a BucketSort object. The same member fieldwill then be read from after the sort method has been called toconfirm that the numbers have been sorted correctly. Your main taskis to write a multithreaded definition of the sort member functionin your BucketSort.cpp file.The sort method will be passed an unsigned int containing the numberof CPU cores that are available to be used. You do not need toadhere to this number when creating threads, however, it can beuseful as it is not sensible to create more threads than there areCPU cores available. Secondly, in some test cases, the number ofcores available may be less than the true number of CPU coresavailable. This is to ensure that the system running the applicationis able to keep other operating system tasks running. If at anypoint during execution the number of threads your application isusing exceeds the numCores limit for a given test case (used inpbs.sort(numCores)) you program may be terminated by the markingsystem and you will score 0 for that test case.Single Threaded Starter CodeThe following definition of the sort member function is thereference solution for the correct sort output. Your multithreadedimplementation should produce the same output as this function, andshould be much faster.#include “BucketSort.h”#include #include bool aLessB(const unsigned int x, const unsigned int y, unsignedint pow) {if (x == y) return false; // if the two numbers are the samethen one is not less than the otherunsigned int a = x;unsigned int b = y;// work out the digit we are currently comparing on.if (pow == 0) {while (a / 10 > 0) {a = a / 10;}while (b / 10 > 0) {b = b / 10;}} else {while (a / 10 >= (unsigned int)std::round(std::pow(10,pow))) {a = a / 10;}while (b / 10 >= (unsigned int)std::round(std::pow(10,pow))) {b = b / 10;}}if (a == b)return aLessB(x,y,pow + 1); // recurse if thisdigit is the sameelsereturn a }// TODO: replace this with a parallel version.void BucketSort::sort(unsigned int numCores) {std::sort(numbersToSort.begin(),numbersToSort.end(), [](const unsigned int x, const unsigned int y){return aLessB(x,y,0);} );}Sample User CodeTest cases for this assignment will involve user code creating largevectors of random numbers and calling the sort method. Your codewill be limited by time and memory with tests increasing indifficultly through decreasing time and memory limits and increasingvector sizes.The following sample test case shows how this is done. For the givensingle threaded code, this sort takes around abouC++代写 CS6771 Assignment Five 2017代写C/C++实验作业t 23 seconds to runon the CSE server williams (with 8 cores). In comparison the modelmultithreaded solution runs for about 6 seconds (without anyoptimisation being applied).#include #include #include #include “BucketSort.h”int main() {unsigned int totalNumbers = 500000;unsigned int printIndex = 259000;// use totalNumbers required as the seed for the random// number generator.std::mt19937 mt(totalNumbers);std::uniform_int_distribution dist(1,std::numeric_limits::max());// create a sort objectBucketSort pbs;// insert random numbers into the sort objectfor (unsigned int i=0; i pbs.numbersToSort.push_back(dist(mt));}// call sort giving the number of cores available.const unsigned int numCores =std::thread::hardware_concurrency();pbs.sort(numCores);std::cout std::endl;// print certain values from the bucketsstd::cout with 1 come first” std::cout pbs.numbersToSort[printIndex - 10000]pbs.numbersToSort[pbs.numbersToSort.size() - 1]}Tips:Consider carefully when you need shared and local memory.Consider carefully when you need to use mutexes around sharedmemory.Consider carefully when you need to use multithreaded code and whenyou need to use single threaded code.You may need to split the sort into multiple sections where threadsare created, destroyed and later additional threads are created.You shouldn’t need to use condition variables, futures or threadpools in this assignment, but you can use these if they help you.You shouldn’t need any pointers or dynamic memory to complete thisassignment.The lecture slides and tutorials have many code snippets that youmay find helpful.You shouldn’t need to create any additional classes or structs (butyou may if you like).The reference solution is 220 lines including comments.Do not use other libraries (e.g., boost).The textbook: Wilkinson, B. and Allen, M., Parallel Programming, 2ndEdition (2005), Pearson Prentice Hall., provides further details andideas on how to implement the parallel bucket sort.A six page pdf photocopied extract covering the relevant section isavailable here. Figure 4.10 is the best diagram of what you shouldbe working your code towards.TestingPlace all your code in a files called BucketSort.h andBucketSort.cppEnsure it compiles on the CSE machines using the following samplemakefileall: sortTestersortTester : sortTester.o BucketSort.og++ -std=c++14 -Wall -Werror -O2 -pthread -o sortTestersortTester.o BucketSort.osortTester.o: sortTester.cpp BucketSort.hg++ -std=c++14 -Wall -Werror -O2 -pthread -c sortTester.cppBucketSort.o : BucketSort.h BucketSort.cppg++ -std=c++14 -Wall -Werror -O2 -pthread -c BucketSort.cppclean:rm *.o sortTesterTo compile your code type:makeTo run your code type:./sortTesterYou should create your own test cases to check the fullfunctionality of your code against the specifications.If you like, you may use the benchmarking suite provided to compareperformance with your previous result, or with other students(though if comparing with other students, run it on wagner)MarkingYour submission will be given a mark out of 100 with 80% anautomarked performance component for output correctness and 20%manually marked component for code style. and quality.As this is a third-year course we expect that your code will be wellformatted, documented and structured. We also expect that you willuse standard formatting and naming conventions.A number of test cases will be used to mark your solution. To pass atest case, your solution must produce exactly the same output as thereference solution. The results from both will be compared by usingthe linux tool diff.In a number of test cases, your solution will be tested under a timelimit, which is set according to the reference solution that wasquickly written with no optimisations being applied.Submission InstructionsCopy your code to your CSE account and make sure it compiles withoutany errors or warnings. Then run your test cases. If all is wellthen submit using the command:give cs6771 ass5 BucketSort.h BucketSort.cppIf you submit and later decide to submit an even better version, goahead and submit a second (or third, or seventh) time; we’ll onlymark the last one. Be sure to give yourself more than enough timebefore the deadline to submit.Late submissions will be penalised unless you have legitimatereasons for an extension which is arranged before the due date. Anysubmission after the due date will attract a reduction of 20% perday to your individual mark. A day is defined as a 24-hour day andincludes weekends and holidays. No submissions will be accepted morethan three days after the due date.Plagiarism constitutes serious academic misconduct and will not betolerated.Further details about lateness and plagiarism can be found in theCourse Introduction.AcknowledgementInspiration for this assignment is based on a 2009 Massey Universityassignment written by Dr Martin Johnson.name to class representative before October 29 23:59:59.转自：http://ass.3daixie.com/2019030313745401.html