ECEC 353: Systems Programming Parallel Implementation of Counting Sort Prof. Naga Kandasamy ECE Department, Drexel University February 24, 2020 The problem is due March 15, 2020, by 11:59 pm. You may work on this problem in a team of up to two people. One submission per group will suffice. Please submit original work. Sorting is an ubiquitous operation in Computer Science, and significant work has been spent on developing efficient sorting algorithms — for example, Quicksort, Heapsort, and Merge sort that have an average computational complexity of n log n when sorting a list of n elements — as well as in developing parallel implementations of these algorithms. You are asked to develop a parallel implementation of counting sort, which is an efficient non- comparison based algorithm to sort an array of integers in the range 0 to r for some integer r. Given an input array comprising n elements, counting sort runs in O(n) time, and trades the time complexity for space complexity when compared to other sorting algorithms. Let us walk through an example of how this algorithm operates. Consider the following input array with ten randomly generated integers, each in the range between 0 and 10: input_array = 8 5 1 3 7 8 6 5 3 8 The first step is to generate a histogram with 10 + 1 = 11 bins — one for each of the integers that could possibly appear in the input array. This histogram simply counts the number of times an integer occurs in the input array. int bin[11]; /* Bins in the histogram */ /* Count the occurrence frequency of each input element */ for (int i = 0; i < 10; i++) bin[input_array[i]]++; For our input array, the resulting histogram has the following entries: bin[0] bin[1] bin[2] bin[3] bin[4] bin[5] bin[6] bin[7] bin[8] 0 1 0 2 0 2 1 1 3 1 bin[9] bin[10] 0 0 The sorted array is generated as follows. Since bin[0] = 0, nothing is written to the output array; bin[1] = 1 and so the corresponding bin number is written to sorted array[0]; the bin number associated with bin[3] is written twice — to output locations sorted array[1] and sorted array[2]; and so on. At the end of this process, we obtain the sorted array sorted_array = 1 3 3 5 5 6 7 8 8 8 We can parallelize the histogram generation process as follows. • Each thread maintains a local copy of the histogram, strides over elements of the input array, and updates the bin values. This process can be performed completely in parallel without the need for any locks (since threads operate on their individual histogram copies). • Once local histograms have been generated, each thread can accumulate the corresponding bin values into a global histogram data structure. – The granularity of locking can be the entire global histogram. That is, each thread acquires the lock for the global histogram and accumulates the bin values of its local histogram into the corresponding bins of the global histogram. – Speedup may be improved if the locking granularity is reduced. You can develop a solution wherein the final values of bins in the global histogram can be calculated in parallel as well by the thread pool. Here a lock is associated with each bin and threads can stride over the bins in the global histogram. – You may try both techniques and choose the best-performing one in terms of speedup. The code provided to you takes the number of elements to be sorted and number of threads as command-line parameters. Edit the compute using pthreads() function to complete the multi- threaded version of counting sort. You may add additional functions and data structures as needed. Submit the files needed to run your code as a single zip file via BBLearn. Also, provide a short report describing how you designed your multi-threaded code, using code or pseudocode if that helps the discussion, and the amount of speedup obtained over the serial version for 106 and 108 integers in the input array, for 4, 8, and 16 threads. Do not change the default range of [0, ]1023] specified in the code for elements of the input array. 2
