Computer Systems Sample Code - Sample Sort
This section will demonstrate some sampled code for 3302ENG Computer System Lab which will be discussed below.
Parallel sort assignment
Question 1
Write a program that performs a sample sort on a dataset that you create. The dataset is a space delimited list of integers between 0 and 1000. The program should open a file called dataset.txt which contains the data to be sorted. The number of bins used is your choice. The program should also time the length of time taken to complete the sort.
Hints: The timing functions can easily be found in any slightly advanced C programming textbook or website. Also make sure that you use a large enough dataset to get a meaningful time.
Question 2
Modify Q1 so that it uses threads to perform a parallel sample sort.
Question 3
The aim of part 3 is to determine the effect of increasing the number of threads on the time taken to perform the parallel sort. This will be demonstrated by plotting a graph of the average time for the sort versus the number of threads used.
You should choose the number of threads so that range is 1 <= number of threads <= 10.
Repeat this procedure 3 times and calculate the average taken time for the different number of threads.
Plot the graph of the average time for the sort vs the number of threads used.
Write down the processor type and the number of cores for the computer that you used to perform this question.
Explain the graph.
Analysis of the implemented sample sort
Figure: Average time taken for each # of thread used in the parallel programming of a sample sort used in conjuncture with a Bucket Sort via multithreading.
The increasing of sorting ranges via the addition of another thread to sort a particular range of integers shows that certain thread numbers (using parallel sorting of 2 – 3) could be beneficial with dips in 5 and 7 where the larger of the resources being chewed up by the program from the system is happening around 8 to 10 threads.
The higher peaks happening at thread numbers 4 and 6 could be from a range for one bucket containing a majority of the randomised data, the distribution could be held entirely by accident from a poor sampling algorithm, decreasing the overall time can be achieved by re-evaluating how a random sample of the whole dataset is obtained, post sorting and acquiring splitters from the sorted random sample could help distribute the whole dataset evenly amongst the buckets (threads).
Code
Github link to Generating data to sample C File
The C File will contain the code to generate the needed data for the sampling algorithim.
Github link to Question 1 C File
This C File will contain the code for sample sorting the generated data Txt File - the code itself is different from the next C File which is a combination of Question 1 and Question 2, the main difference within this code is that the sorting algorithim will examine the amount of the pieces of data and resize for an appropriate amount of buckets to be used to sort the amount of data, it’s aim is to stay relatively in the low-middle section of the thread numbers such as (2 - 5).
Github link to Question 1 Question 2 C File
Alternative C File at Github
This C File will contain the code for sample sorting the generated data Txt File - the code itself will sort data at the number of threads that the user chooses. The alternative file is the same code with the removal of the printed to terminal data positions as a measure to examine whether it is working the way it should be.
Issues occurred and possible solution
Problem 1:
An occurrance was during the accessing of critical code, which content of first thread will be mixed by the content of the nth thread.
Possible solutions for problem 1:
Thread locking the critical code and allowing each thread to enter and submit the data at the appropriate position in the array of sorted data, which means keeping track of where it is between shared memory between threads.
Implemented solution for problem 1:
Mutex locking, conditional numbers with mutex condition broadcasting and waiting so that thread 1 will access the critical code sections and will allow the data to be inserted increasing the conditional number up until the nth thread, for this section of the code the parallel programming because serial however it is not destructive.
Problem 2:
The sorting of the random data resulted in one bucket taking most of the load of the data, when each bucket was given a number range.
Possible solutions for problem 2:
Eliminating the use of the number ranged buckets and give each bucket a random number of elements to be sorted with in perspective bucket and allowing a simple mutex lock and let each thread insertion sort each number - it will elminiate overhead of the storage for a slower time.
Implemented solution for problem 2:
A solution has yet to be implemented.
Revision
This is the revision of the code to make it a little more efficient.
