Using A Set of Thread To Sort A Given Array
For this homework, you will use a set of threads to sort a given array. For the input you will read in two integers: an integer to denote the list of the list which we will denote as list Size and the number of threads we wish to use which we will denote as numThreads. You will re-prompt for input if the numbers read in are either nonpositive, not a numerical type, or if the number of threads reads in exceeds the number of threads your system can handle. You can assume both the listSize and numThreads values will both be powers of 2, just to make life a lot easier.
ThreadSort Algorithm Requirements
1. Allocate a vector of listSize number of items and assign a random number into each element between 1 and listSize, declaring this vector as a global vector, to make things simple
2. Create exactly numThreads amount of threads and each thread will run insertion sort on each listSize / numThreadssublist, you will need to pass in the correct left and right indices (endpoints) into each thread function such that each thread is assigned its own list without overlapping the other threads, the insertion sort prototype can be seen below
void i n s e r t i o n S o r t ( int left, int right );
3. After step 2, we now have exactly numThreads amount of sorted sublists each of size listSize / numThreads, we must now perform the steps to merge these sublists to form larger sublists using the following function that will be assigned to a thread
void m e r g e L i s t s ( int leftLeft , intleftRight , intrightLeft , intRightRight);
4. You will now need to merge each adjacent pair of listSize / numThreads size sorted sublists, thus you will need to spawn numThreads / 2 amount of threads (you will need to compute the 4 endpoints for each thread to tell it which two sublists it needs to merge)
5. After step 4, you perform the same task except you will spawn half as many threads each time which will sort two larger pair of adjacent sublists (each sublist will double in size each time), and you continue this process until you have one thread that merges two adjacent pair of sublists which are both listSize / 2 in size
6. Once the list is sorted and all threads are done, output the list unless the listSize is too large, anything larger than 512 elements would be too large
So for example, if we have a vector of 65536 and have 8 threads, we will spawn 8 threads and each thread will sort 8912 elements (since 65536 / 8 = 8912), and then we will spawn 4 threads and each thread will merge two adjacent lists of size 8912 into arrays of 16384 (there will be 4 of these). Then we will spawn 2 threads to merge the 4 sorted lists into 2 sorted lists, and then we will spawn 1 thread that merges two lists of size 32768, and then you will have one sorted array of size 65536.
The di cult part will be computing the new ranges for each thread each time such that no two threads overlap, i.e. will not have multiple threads accessing the same element in the vector and for spawning the correct amount of threads each time. Your code must be scale-able to the number of threads you have and the size of the list. You may use a global vector to store the numbers list, do not use reference parameters with threads since thread functions do not like that.
Write Up
• Tabulate the runtimes (in real-time) for various amounts for list sizes (all powers of 2) along with the various amounts of threads
• Using the same list sizes from the above portion, tabulate the runtimes (in real-time) for a sequential sort (you can use quicksort or mergesort)
• Conclude which method was faster (sequential or parallel) and explain why you obtained those results
• Hypothetically if we have listSize / 2 amount of threads that could run in parallel, would our parallel sorting algorithm have a better runtime than a sequential sorting algorithm?
Specifications
• Comment your code
• Make sure you never spawn more threads than your system can handle
• You may use a global vector to store your vector, but the parameters passed into each thread function must be determined in main and not be global since the number of threads used is not predetermined
• You can assume list size and number of threads will be a power of 2
C++ Code Solution
#include
#include
#include
#include
#include
#include
#include
using namespace std;
vectorlistSize;
vectororiginalListSize;
// Perform insertion sort for a specific range of indices
voidinsertionSort(int left, int right)
{
for (inti = left + 1; i<= right; i++)
{
int number = listSize[i];
int j = i - 1;
while (j >= left &&listSize[j] > number)
{
listSize[j + 1] = listSize[j];
j--;
}
listSize[j + 1] = number;
}
}
// Merge 2 sub-list it into a sorted bigger list
voidmergeLists(int LL, int LR, int RL, int RR)
{
vector container;
intcurrentLeftHalf = LL;
intcurrentRightHalf = RL;
// Merge them temporarily in a container, maintain sorted order
while (currentLeftHalf<= LR &¤tRightHalf<= RR)
{
if (listSize[currentLeftHalf] <= listSize[currentRightHalf])
{
container.push_back(listSize[currentLeftHalf]);
currentLeftHalf++;
}
else
{
container.push_back(listSize[currentRightHalf]);
currentRightHalf++;
}
}
// Put whatever is left in the left half
while (currentLeftHalf<= LR)
container.push_back(listSize[currentLeftHalf++]);
// Put whatever is left on the right half
while (currentRightHalf<= RR)
container.push_back(listSize[currentRightHalf++]);
// Put the sorted container on the main list
intcurrentIndexToMain = LL;
for (inti = 0; i< (int)container.size(); i++)
listSize[currentIndexToMain++] = container[i];
}
// Display the numbers for the first 512 only
voidprintNumbers()
{
for (inti = 0; i< (int)listSize.size() &&i< 512; i++)
cout<
cout<
if (listSize.size() > 512)
cout<< "" <
}
// Genrate a random number of elements
voidgenerateNumbers(intnumElements)
{
listSize.clear();
for (inti = 0; i
{
int number = rand() % numElements;
listSize.push_back(number);
originalListSize.push_back(number);
}
}
// An abstract class that performs sorting
classSortThread
{
public:
threadmainThread;
intfromIndex;
inttoIndex;
// Nothing to do for constructors/destructors
// just here for formality's sake because of inheritance
SortThread() {};
virtual ~SortThread() {};
// Execute the thread
virtual void run() = 0;
};
// A thread that performs insertion sort
classInsertionSortThread
: publicSortThread
{
public:
// Run the thread and perform insertion sort on the assigned
// indices
void run()
{
mainThread = thread(insertionSort, fromIndex, toIndex);
}
};
// Run and wait for the left and right thread to finish then merge
// the results
voidmergeThreads(SortThread *leftThread, SortThread *rightThread)
{
leftThread->run();
rightThread->run();
leftThread->mainThread.join();
rightThread->mainThread.join();
// Now do merge
mergeLists(leftThread->fromIndex, leftThread->toIndex,
rightThread->fromIndex, rightThread->toIndex);
}
// A thread that performs merging of 2 sub thread's result
classMergeSortThread
: publicSortThread
{
public:
SortThread *leftThread;
SortThread *rightThread;
// Deallocate pointers
~MergeSortThread()
{
deleteleftThread;
deleterightThread;
}
// Run the sub-threads. Wait for them to finish before
// merging the results
void run()
{
// Start the sub threads and wait for them to finish
// before merging
mainThread = thread(mergeThreads, leftThread, rightThread);
}
};
// Check if number is power of two
bool isPowerOf2(int n)
{
if (n == 0)
return false;
while (n != 1)
{
n /= 2;
if (n % 2 != 0 && n != 1)
return false;
}
return true;
}
// Read a number that is power of 2 from the input
int readPositivePowerof2Int()
{
while (true)
{
string line;
getline(cin, line);
stringstreamss(line);
int number;
if (ss>> number && number > 0 && isPowerOf2(number))
return number;
cout<< "Error. Value should be a positive integer and a power of 2." <
cout<< "Try again: ";
}
}
// Helps merging elements using merge sort algorithm
voidmergeSortHelper(int *temp, intleftPos, intrightPos, intrightEnd)
{
intleftEnd = rightPos - 1;
inttmpPos = leftPos;
intnumElements = rightEnd - leftPos + 1;
while (leftPos<= leftEnd&&rightPos<= rightEnd)
{
if (listSize[leftPos] <= listSize[rightPos])
temp[tmpPos++] = listSize[leftPos++];
else
temp[tmpPos++] = listSize[rightPos++];
}
while (leftPos<= leftEnd)
temp[tmpPos++] = listSize[leftPos++];
while (rightPos<= rightEnd)
temp[tmpPos++] = listSize[rightPos++];
for (inti = 0; i
listSize[rightEnd] = temp[rightEnd];
}
// Merge sort on the list
voidmergeSort(int *temp, int size, int left, int right)
{
if (left < right)
{
int center = (left + right) / 2;
mergeSort(temp, size, left, center);
mergeSort(temp, size, center + 1, right);
mergeSortHelper(temp, left, center + 1, right);
}
}
// Entry point of the program
int main()
{
// Configure number of elements and threads
intnumElements = 0;
intnumThreads = 0;
while (true)
{
cout<< "Enter the size of the list (should be a positive and power of 2): ";
numElements = readPositivePowerof2Int();
cout<< "Enter the number of threads (should be a positive and power of 2): ";
numThreads = readPositivePowerof2Int();
if (numElements>= numThreads)
break;
cout<< "The number of threads should lesser than or equal to the size of list." <
}
cout<< "Generating " <
generateNumbers(numElements);
cout<< "Numbers before sorting: " <
printNumbers();
// Identify the number of insertion sort threads to create
// Assumes that the number of elements are a power of 2 and even the number of threads
intnumElementsPerThread = numElements / numThreads;
// Calculate the index for each insertion sort thread
vectorsortThreads;
for (inti = 0; i< (int) listSize.size(); i += numElementsPerThread)
{
InsertionSortThread *sortThread = new InsertionSortThread();
sortThread->fromIndex = i;
sortThread->toIndex = i + numElementsPerThread - 1;
sortThreads.push_back(sortThread);
}
// Debugging each thread if they are assigned correctly
for (inti = 0; i< (int)sortThreads.size(); i++)
{
cout<< "Thread " <
<fromIndex<< " to "
<toIndex<
}
// Prepare the threads that will merge the results of each sub thread
while (sortThreads.size() > 1)
{
MergeSortThread *sortThread = new MergeSortThread();
sortThread->leftThread = sortThreads.front();
sortThreads.erase(sortThreads.begin());
sortThread->rightThread = sortThreads.front();
sortThreads.erase(sortThreads.begin());
sortThread->fromIndex = sortThread->leftThread->fromIndex;
sortThread->toIndex = sortThread->rightThread->toIndex;
sortThreads.push_back(sortThread);
}
// We end up with one single thread that will run all sub-threads
// and each sub-threads having their own sub-threads and do their job
autostartTime = chrono::high_resolution_clock::now();
SortThread *rootThread = sortThreads.front();
rootThread->run();
rootThread->mainThread.join();
autoendTime = chrono::high_resolution_clock::now();
cout<< "Numbers after sorting: " <
printNumbers();
cout<
cout<< "Threaded Insertion Sort Sorting time: " <(endTime - startTime).count() << " ms" <
deleterootThread;
cout<< "Press key to do sort the list using sequential merge sort..." <
string line;
getline(cin, line);
// Now sort again the list but using merge sort
cout<
cout<< "Sorting using regular quick sort algorithm..." <
listSize = originalListSize;
cout<< "Numbers before sorting: " <
printNumbers();
int *temp = new int[numElements];
startTime = chrono::high_resolution_clock::now();
mergeSort(temp, numElements - 1, 0, numElements - 1);
endTime = chrono::high_resolution_clock::now();
cout<
cout<< "Numbers after sorting: " <
printNumbers();
cout<
cout<< "Merge Sort Sorting time: " <(endTime - startTime).count() << " ms" <
delete[] temp;
return 0;
}