Friday, March 25, 10pm
See Assignment 8 on Canvas for the Github Classroom link.
This is a pair assignment, but you can work alone, if you so choose.
Submit the contents of your repository via Gradescope. See Deliverables below for what to submit. If you are working with a partner, do not forget to include their name with the submission.
There will be no autograder for this assignment ahead of the deadline. Read the requirements and run tests locally.
In this assignment, we will turn a single-threaded naive implementation of merge sort into a multi-threaded one.
The starter code contains an implementation of merge sort in the file
msort.c. The implementation is based directly on the
top-down example from the above mentioned Wikipedia article.
Your first task is to make sure you understand how this algorithm works.
Do ask questions if you feel you are missing something. Note that the
implementation works with two arrays: the input array and a “target” or
“helper” array. The target array will contain the resulting sorted
array. However, this implementation also modifies the original
msort program takes a single argument which is the
number of long integers to be read from standard input. Once it reads in
the given number of elements and/or the standard input is closed, the
array is sorted and the result is printed to standard output.
Your main task is to use the POSIX
threads (pthread) library routines to turn the provided merge sort
implementation into a concurrent one that improves on the performance of
the single-threaded version. The Wikipedia article contains a hint to
get you started. It’s shouldn’t take too much effort. Implement your
tmsort.c, which initially contains the same
The concurrent implementation is parametrized in the number of
threads it should use. This parameter is taken from the environment
MSORT_THREADS, which is read in by the starter
code (take a look!). Your implementation should not use more than the
given number of threads, but should use exactly that number on a large
enough input. E.g., when
MSORT_THREADS=10 and the input
array has 1, 000 elements, the
implementation should use exactly 10
threads (including the main thread). You can set environmental variables
globally for the current shell using
export (see How
to Set and List Environment Variables in Linux, or you can just take
a look how we do it in the Examples below.
Your second task is to perform a few experiments on at least two machines that are capable of compiling and running pthread-based code. These include:
experiments.md, write a brief summary of your
experiments with large enough inputs. Use the provided file as a
template. Write for each machine:
Specs (CPU including the number of cores, memory, disk capacity, OS)
Input data size and how you created it (see Hints & Tips). Use a large enough number of elements, so that the single-threaded implementation takes at least 10 seconds to sort them.
The approximate number of processes running before you start each
experiment (obtainable by running
ps aux | wc -l)
Run experiments for different thread counts (1, 2, number
of cores, double the number of cores, …), one after another. For each
thread count, run the sort at least 4 times with the same arguments/data
set. Note how much time the sorting portion took (look for the line
"Sorting completed in N seconds.").
Keep increasing the thread count and figure out at which point adding new threads does not translate to (significantly) improved performance. How does this number relate the number of cores on the machine you run the experiments on?
tmsort.c. Include any additional
.hfiles your implementation relies on. However, you shouldn’t need to implement many additional functions and/or data structures that would imply separate compilation.
Commit the code and the experiments to your repository. Do not
include any executables,
.o files, or other binary,
temporary, or hidden files.
Once you are done, remember to submit your solution to Gradescope and do not forget to include your partner.
manis your friend. Check out
nproccommand to get the number of cores available on your machine. On Linux, reading the file
/proc/cpuinfowill give you detailed information about the processor on your system.
pthread_createonly takes a single
void *argument. To pass custom arguments, create a “helper” struct and pass a pointer to it. Depending on where you are waiting for the thread to join, you might need to allocate it on the heap.
pthread_mutex_unlockto ensure consistency.
shuf -i1-Nparameter to generate
Nrandom numbers between 1 and
shuf -i1-1000 > thousand.txtgenerates 1, 000 random numbers and writes them to
tmsortconsistently returns the same result as
msorton the same input. You can check that by running
diff <(./msort 1000 < thousand.txt) <(./tmsort 1000 < thousand.txt).
make diff-N, where
Nis the size of input. Example:
tmsortis consistent with
msort, you might want to redirect
/dev/nullto avoid printing the result when doing timing experiments:
./tmsort < input.txt > /dev/null. Timings are printed to
stderrso they will still be visible.
assertto check that your assumptions about state are valid.
asserts to check expected results. Use our tests for queue/vector from Assignment 4 as an example.
elseor a multi-case
switchshould be the only reason to go beyond 40-50 lines per function. Even so, the body of each branch/case should be at most 3-5 lines long.
Here are some examples of running our implementation of
Basic usage, input from terminal.
$ ./tmsort 5 Running with 1 thread(s). Reading input. Enter 5 elements, separated by whitespace 5 4 3 2 1 Array read in 4.505015 seconds, beginning sort. Sorting completed in 0.000069 seconds. 1 2 3 4 5 Array printed in 0.000024 seconds.
Using pre-generated input.
$ shuf -i1-10 > ten.txt $ ./tmsort 10 < ten.txt Running with 1 thread(s). Reading input. Array read in 0.000034 seconds, beginning sort. Sorting completed in 0.000006 seconds. 1 2 3 4 5 6 7 8 9 10 Array printed in 0.000040 seconds.
Varying the number of threads.
$ shuf -i1-100000000 > hundred-million.txt $ MSORT_THREADS=1 ./tmsort 100000000 < hundred-million.txt > /dev/null Running with 1 thread(s). Reading input. Array read in 12.193864 seconds, beginning sort. Sorting completed in 19.202604 seconds. Array printed in 10.442048 seconds. $ MSORT_THREADS=2 ./tmsort 100000000 < hundred-million.txt > /dev/null Running with 2 thread(s). Reading input. Array read in 12.093944 seconds, beginning sort. Sorting completed in 10.288052 seconds. Array printed in 10.403824 seconds. $ MSORT_THREADS=4 ./tmsort 100000000 < hundred-million.txt > /dev/null Running with 4 thread(s). Reading input. Array read in 12.199927 seconds, beginning sort. Sorting completed in 6.118842 seconds. Array printed in 10.817068 seconds.
The QEMU script we provide only uses
a single core. You can increase the number of cores by modifying the
-smp option passed to QEMU on startup by the script. Reach
out if you need help with this.↩︎