| Date | Description |
| 24-Jan-16 | Original posting |
| 01-Feb-16 | Clarification of the meaning of -g |
In this assignment you'll implement the merge sort algorithm discussed in class with C++11 threads. Using your implementation, you'll conduct experiments on the Bang cluster to assess performance. The assignment includes a brief report, and the requirements for your report are described at the end of this writeup.
☞ Due Friday2/5/16 @ 9PM‣ ‣ ‣ Required solution files: MergeSort.cpp Merge.cpp
This means that these files, containing your solution to the assignment, must be turned in by the deadline.
You may develop your code anywhere, but you must ensure that it compiles and runs correctly on Bang, because that’s where we’ll be testing it.
In doing this assignment, it's your responsibility to understand the course rules for integrity of scholarship.
All assignments will be turned in using UCSD's GitLab. The turnin procedure is described below in the section "Turning in your assignment". You must follow these steps to get the starter code and to get set up to do assignment 2.
Refer to the link below for instructions on how to obtain the starter code to get started on your assignment
A2 Git Instructions
We've provided you with starter code that implements the serial algorithm. We've also provided multithreaded reference binary to enable you to assess performance, in $PUB/HW/msort.
Look over the code to familiarize yourself with the various modules. For example, the command line parser in cmdLine.cpp explains the options needed to run the code. You will be making changes to just two files: MergeSort.cpp and Merge.cpp. To ensure that your program is correctly graded, do not rely on any changes you have made to any other provided source code files; we will substitute fresh copies when we grade your assignment. Also, don't change the signature of the function DC_MergeSort() defined in MergeSort.cpp as our tester code is designed to use the signature in the provided code. (We've defined this signature in mergeSort.h so if you do change the signature the compiler will complain about there being two signatures for the same function)To build your code, use the provided Makefile, which sets up the appropriate flags for the compiler via an "arch" file as used in the last assignment. The Makefile produces a target called msort. Do not change the name of this target.
The "arch" file provides various options to assist you in developing your code. For example, to compile for the gdb debugger, specify "gdb=1" on the make command line, e.g.
make gdb=1
This option will shut off optimization (-O0). Don't forget to do a make clean before building the code after adding or changing a Makefile command line argument. Otherwise, you may get anomalous or unexpected behavior, i.e. some modules are compiled with optimization and others are not.
The code has various command line options, set in cmdLine.cpp:
-n Number of input keys
-t Number of threads
-p Use the parallel merge algorithm [Default: serial]
-g Value of N where we stop the recursion, using fast local sort (applies to all values smaller than N as well)
-s Random number seed. Valid for random input only.
-r Number of repetitions (used for timing small problems)
-b Best case input of perfectly sorted data
-w Worst case input of reverse sorted data
-o Output file
-v Verify against an output file
For example the following invocation
./msort -n 67108864 -t 2 -p -g 262144 -o out.67 -s 1380501542
will run with input size N=67108864 random keys (64 Megawords) on 2 threads with
parallel merge.
Mergesort will terminate the recursion when a subproblem size drops below reaches 262144 keys (256K).
A binary output file, out.67, will be written when the program completes.
You can use this to compare your output against a trusted output that you know is correct.
The random number seed is 1380501542.
To learn how and to use
the -s flag,
see Timing your code in the next section.
By default, the program will generate a list of random keys in the range -231-1 to 231. Since the keys can be long and difficult to compare when testing, we've provided options to simplify testing with smaller keys. But don't consider your program correct and complete until you can correctly handle larger inputs sizes with random keys.
To test with smaller keys, set the input size N to a small number like 8, 16 or 32. Then, use one of the two options -b or -w to specify best case and worst case inputs, respectively. The resultant input will be much easier to inspect than the default input as the numbers are short and aren't random.The best case input is a sorted list of numbers that starts at 0 and progresses to N-1 in steps of 1. The worst case input is the reverse sorted counterpart of this list. The two options play no role in how we grade your assignment and are intended to help you with testing.
To help you test larger inputs, we've added the -o flag to generate a binary file of your Merge Sort programs output, and the -v flag to enable you to compare a sorted list with a previously generated output file. These will be explained in the next section Testing your Code.
For a correctly written mergesort program, the output should agree exactly with the provided (serial) code's output. In addition, the output should be independent of the number of threads specified in the -t flag as well as the -g flag.
To enable you to validate your code with respect to these requirements, the provided code has the capability to verify your program output in various ways, depending on the input options. It will verify any best case or worst case inputs. These are trivial to test, as they consist of the integers 0 to N-1 only.For random input (i.e., neither -b or -w is asserted), the program will serially sort the input using the C++ stdlib's built in sort function. Since a serial sort will be slow for large inputs, we only allow this option to be used if the input is not larger than 8K (You may increase this value if you wish but be careful about long running times). For larger inputs there are two choices. One is a weak test, which runs very quickly. This simple test only checks that the output is a sorted list, but doesn't guarantee that the list is the correct one, that is, it corresponds to the input. You will see this warning when you run the code without the -v option (and neither b or -w):
*** Using a weak verification, result NOT guaranteed to be correct Sorted result PASSED verification test.You can use this quick mode if helpful, but a more certain way to verify that your program is correct is to use the -v option, that allows you to compare against trusted output. To this end, we have provided you with 1 output file, called out.67 in the same directory as the binary reference: $PUB/HW/A2/out.67 It was generated with the following command:
./msort -n 67108864 -t 1 -p -g 262144 -o out.67 -s 1380501542
You can then compare the output of your multithreaded program against this file: ./msort -n 67108864 -t 2 -p -g 262144 -v out.67 -s 1380501542
If successful, you'll get the following output:Comparing with reference result in file out.67 Sorted result PASSED verification test.
When using -v, make sure you trust the source. You can assume that the provided code (as well as the provided reference binary) can be trusted. We gave you the out.67 file because it is 256MB in size. If all teams create this one file, more than 15GB of storage will be required, for just 1 test.
Since the input keys are distributed randomly, each run will use a different input, which can complicate performance comparisons on different numbers of cores or even runs with the same numbers of cores. The -s flag enables you to run with a given random seed which starts the random number sequence from a known place. This way you can reproduce random input from run to run. The provided code outputs the random seed, so the first time you run, note the seed so that you can then specify it in subsequent runs.
Take timings with the provided timer code, Timer.cpp, which uses gettimeofday(). Take at least 3 timings for each combination of parameters, and report the minimum timing. Be sure to use the same random seed for each run, with the help of the -s flag. Shut off any debugging output when you collect timings results. as doing so could affect your observations. Use the timer in the provided code, which takes timings using gettimeofday().
You may run interactively via qlogin, but may find it more convenient to collect your measurements by non-interactively via batch. To use batch, follow these instructions. As a courtesy to other users, exit an interactive session when you longer need it. Do NOT run interactively on Bang's front end as there is a risk of overloading the machine
We've provided you with a batch script that provides the appropriate commands for running batch jobs. You need only change the commands you wish to run. If you want to be notified when your job completes, then add your email address on the qsub command line:
qsub batch-job.sh -M youremail@ucsd.edu
You'll notice that at the end of the run, you'll get a line of output like the following, which lists the input size (128 Meg keys), # threads (8), parallel running time (5.059 seconds), the list size that terminates the recursion MergeSort (256K), # of repetitions (1), type type of input (Random, Worst case, Best case), whether or not a parallel merge was used and whether or not the solution verified correctly. The line begins with the '@' symbol so you can quickly search for it in a batch output file containing several runs.
N NT T_P G Reps In ||? V
@ 134217728 8 5.059 262144 1 R N P
For large inputs when you did not use the -v option, the P will include an asterisk (P*) to signify that the verification was weak.
This procedure is the same as the previous assignment and is reproduced here:
Git Lab Submission
A2-report-baden-powell.pdf.
You need only provide data in tabular form. If you like, make a plot; if you provide a plot, you must still provide the tabular data as sometimes plots can be hard to read. Be sure to provide a caption for each table or plot that describes the experiment you conducted, e.g. "strong scaling." Plot your data carefully, plotting only what's necessary to get your points across, and choosing log and linear plots carefully.
Negative results are also valid and especially valued if you can document them, with the underlying causes, or best guesses if the causes are not clear. So if results weren't as you expected, let us know why and we may be able to give you some partial credit. Include this discussion on the PDF containing your results.
Your repository must also contain one important document, which accompanies the provided code: teameval.txt. This document must be filled in completely. If you don't turn in it in, your assignment will be considered late. (Minimum 10% lateness penalty). We no longer require the DECLARATION document.
Don't wait until the last minute to attempt a turnin for the first time. Try out the turnin process early on so you are sure that you you are familiar with the process, and that all the required additional files are present.
You will receive 0 points for this assignment if your code does not compile, including cases of non-compilation due to merge conflicts. If you developed your code on another machine you are responsible for properly testing on bang, else you may lose significant credit, possibly all 25 points depending on the circumstances. As mentioned previously, you must ensure that you resolve all of your merge conflicts and that your code compiles and runs correctly IMMEDIATELY BEFORE you push to GitLab.
For this assignment staff will attempt intervene manually to fix problems. However, the policy for such manual intervention is as follows. If any manual intervention is required by staff you will lose at least 2 points. Included are: incorrectly naming your GitLab repository, or misspelling the words FINAL SUBMISSION in the commit message. Lastly, the only files you should be pushing to GitLab are text files: source code and ASCII test files. Do not push large binaries such as the executables or media files, as doing so could lead to problems such as losing the ability to push to GitLab. Staff will not intervene under these circumstances and you you may be unable to complete your assignment by the deadline. If you commit binaries, you are doing so at your own risk.
There are 25 possible points on the assignment and your grade will depend on 4 factors: performance attained by your code, correctness, appropriately-displayed results and comments.
To get full credit for the performance component, your code must
Note that, in the interest of avoiding some messy corner cases for uninteresting values of the -g parameter, we won’t for values of the -g parameter that are smaller than 4. We will test against the public input described here, plus other inputs that will not be made public. Be sure to test against various combinations of the -n, -t, and -g parameters. However, use care in choosing these parameters so that no runs lasts for more than 10 or 20 seconds. To save time, we suggest that you start with the default values for the -n and -g command line parameters and vary by a factor of four--up and down. Your code need only handle the case where the -n and -t parameters are integer powers of two.
You must not only put comments inside your code, but every time you commit to your repository. GitLab comments may be brief, but they must enable us to understand (and re-trace) your development process. If you aren't sure, be sure to ask us.
We will grade your code (on bang) using our own Makefile. Be sure to do your final testing on that machine, to avoid any surprises at turnin time. Our Makefile will compile your code using g++ and then link it with a test driver. We will use the same compilation flags as in the provided starter code. Our test driver expects your DC_MergeSort() function to satisfy the interface specifications specified in the starter code. Except for MergeSort.cpp and Merge.cpp, our tester will use the original copies of all provided code files.
[Sun Jan 31 08:00:09 PST 2016]