Ryan Avery

Multithreaded Sort


In this project, which was created for my CS-453 Operating Systems class, I took a normal, single threaded mergesort algorithm and made it multithreaded. I did this with the use of C's pthread.h library and the use of threads and mutexs. I was able to achieve a much, much faster sorting time on large amounts of data using my multithreaded version than was possible in the single threaded version of the sorting algorithm.

The program has two arguments; the size of the array of random numbers that is to be sorted and the number of levels deep that the user wants the program to use multithreading on. On the first iteration of mergesort, the algorithm of course splits the array that needs to be sorted in half, and this goes on recursively until the size of the chunk to be sorted either reaches some size limit or contains only 1 item.

Thelarge project picture second argument is the number of levels which will invoke the parallel version of mergesort. If max levels was 3, for instance, this would mean that the first 3 levels of recursive calls to mergesort would be in their own threads. Each call to mergesort has the potential to make two additional calls to mergesort, assuming there is enough items left that need sorting. This means that—assuming a large value for input size—a total of 14 (which comes from 2^1 + 2^2 + 2^3) threads would be created, and all other recursive calls to mergesort would then use the serial version. To test the program using no additional threads (i.e. to test the program in serial mode) use a value of 0 for this second argument.

After having completed the project, I ran a number of tests on the solution using different values for the second argument to test the possible speed improvements when using differing numbers of threads. Below is a table showing the results of these tests, all of which were done on the Boise State University Onyx Cluster which had 32 CPUs at its disposal.

| Mergesort Type | Items Sorted    | Depth Level | Time (s) |
| single-threaded | 100,000,000     | 0                   | 13.65     |
| multi-threaded  | 100,000,000     | 1                   | 7.76       |
| multi-threaded  | 100,000,000     | 2                   | 5.33       |
| multi-threaded  | 100,000,000     | 3                   | 3.27       |
| multi-threaded  | 100,000,000     | 4                   | 3.21       |
| multi-threaded  | 100,000,000     | 5                   | 3.14       |