Programming Assignment #2

Parallel Merge Sort

Changelog

Date Description
16-Apr-15 Original posting

Contents

The Assignment

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 Thursday 4/30/15 @ 9PM

‣ ‣ ‣ Required solution file: MergeSort.cpp

This means that the file that contains your solution to the assignment must be turned in by the deadline. The turnin procedure is described below in the section "Turning in your assignment".

You may develop your code anywhere. But, we'll test your code on Bang, so you must ensure that it runs runs correctly on Bang.

In doing this assignment, it's your responsibility to understand the course rules for integrity of scholarship.

Part 1. The provided MergeSort starter code

1.1. Accessing the code.

Follow these steps to get the starter code and set up your repository.

Refer to the link below for instructions on how to obtain the starter code to get started on your assignment 

A2 Git Instructions

1.2 The MergeSort starter code

We've provided you with starter code that implements the serial algorithm along with a multithreaded reference binary to enable you to assess performance. This code has been installed as $PUB/HW/A2/msort. (There are two versions, one for each course platform. Code compiled on Bang won't run on Ieng6, and vice verse).

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 use one file: MergeSort.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.

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. To assist you in your code development, we've set up the Makefile to enable you to build the code in various ways. For example, if you want 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).

The other options are self-explanatory. Don't forget to do a make clean before rebuilding the code. Otherwise, you may get anomalous behavior.

1.3 Command line options

The code has various command line options, set in cmdLine.cpp: 

-g Minimum N that is subject to merge sort, smaller N invoke a fast local sort.
-n Number of input keys.
-p Use a parallel merge algorithm [Default: serial] 
-r Number of repetitions (used for small problems)
-s Random number seed. Valid for random input only.
-t Number of threads
-b Best  case input of perfectly sorted data
-w Worst case input of reverse sorted data
For example the following invocation 

./msort -n 67108864 -s 1380501542 -g 262144 -t 2 -p

will run with input size N=67108864 keys (64 Meg) on 2 threads and use a parallel merge. It will terminate the recursion when a subproblem size drops below 262144 keys (256K). Lastly, the random number seed is specified as 1380501542. To learn how and to use the -s flag, see the Testing your code below.

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 for using shorter keys. To do this, set the input size N to a small number like 16 or 32. Then, use of of the two options -r or -w to specify best case and worst case inputs, respectively. The resultant input will be much easier to inspect than the default input.

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 only.

Part 2. Experimentation

2.1 Testing your code

To test your code, use the capability provided by the code to verify that the list has been sorted. (Note that 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'll need to implement a more ambitious test, which is also more costly, as you'll have to ensure that each input key is found in the output.) Make sure that the code runs correctly for all timing tests you perform. Since the input keys are distributed randomly, each run will use a different input, which can complicate performance comparisons on different numbers of cores. We need a way of reproducing the same random number sequence over several runs. The provided code enables you to can meet this requirement using the -s flag. This flag starts the random number sequence from a known place so that you can reproduce the input from run to run. The code always outputs the random seed, so the first time you run, note the seed so that you can then specify it in subsequent runs when needed.

2.2 Taking timings

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.

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, and also add your email address if you want to be notified when your job completes. Take timings with the provided timer code (it uses gettimeofday()). Take at least 3 timings for each combination of parameters, and report the minimum timing. (Included is the random seed setting via the -s flag). Shut off any debugging output when you collect timings results. as doing so could affect your observations.

You'll notice that at the end of the run, you'll get a line of output like one of 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. 

        N     NT    T_P            G      Reps In  ||?  V
@> 134217728   8     5.059      262144      1   R   N   P

2.3 Coding and Assignment Checklist

  1. Implement DC_MergeSort (within MergeSort.cpp) a multithreaded version of the serial Merge Sort divide and conquer algorithm. Don't change the signature of this function, as our tester will rely on the interface specified in the provided code.
    1. First parallelize the recursive calls to merge.
    2. Once you have the basic mergeSort working, implement the parallel merge algorithm discussed in class. Take care when passing reference arguments to the thread function, since you'll need to use the ref() specifier to pass the arguments correctly.
  2. Conduct a strong scaling study, using the default parameters defined in the provided code.
    1. Vary the number of threads from 1 to 8, in powers of two. Be sure to use the same random seed with the help of -s option (as explained previously) so that you are taking multiple sample timings from identical input lists. If you have time, let the program pick the random seed for each run and report, for each value of the number of threads (NT), the average timer over ten runs. Plot the speedup in your strong scaling study
    2. Do a strong scaling study as previously, but with the -p option asserted. Note any performance change and plot the performance increase compared to the results without parallel merge. Don't report the parallel speedup, but rather how much faster (or slower) your code ran with parallel merging available. If faster, than the numbers will be greater than 1, if slower, less than 1.
  3. You’ll note that performance may be only slightly sensitive to the -g value. However, when g=n on more than 1 thread, the code suddenly slows down. Why is this the case? Try to pick a -g value that minimizes the running time; you may need a different value of -g for each value of the number of threads -t. Behavior may or may not change with parallel merging turned on.
  4. Report and comment on performance. Be sure that all data is in tabular form as well as in a plot, or place a label above each point showing the value of the performance metric you are measuring.

Part 3. Turning in your assignment

3.1 Submission via GitLab

When you have completed the assignment, you must submit it. You will do this by pushing your changes to GitLab. Follow these steps:

  1. Run a ’git status’ to see what files have been changed.
  2. Use ’git add <files>’ to stage certain files for a commit, use ’git add .’ to add all files in the working directory to the commit (hopefully you will not be doing this at this late stage—all files should already be in your repository!)
  3. Use ’git commit -m "FINAL SUBMISSION"’ to commit the changes to your repository and indicate that you are done and this is your final submission.
  4. To push your changes onto your repository on GitLab run ’git push origin master’ Don’t forget this push! You must do this to get credit.
  5. As an added safety check, you should log on to GitLab on the web and verify that your push went through.

Some of the finer points about this process:

  1. Watch out for (and resolve) merge conflicts before your final push!!
    If you have been developing on multiple computers and not syncing with GitLab between switching computers, you will likely get merge conflicts. This happens because your code from one repo is out of sync with your code from another and GitLab doesn't know how to merge the files. You will get these conflicts "at the last minute," because git must sync the code in the repo you're trying to push with the code in the repo you're trying to push to. MERGE CONFLICTS WILL PREVENT YOUR CODE FROM COMPILING. So, even if your code was working perfectly just before you attempted your final push, conflicts will break your code.

    It is your responsibility to recognize when you have conflicts (it's not hard--you get a big warning), and to fix them. Please leave yourself enough time to do this.

  2. If you are submitting with a partner, just push to the joint repository on behalf of both partners. That’s your joint submission.

  3. Use the commit message FINAL SUBMISSION for your final submission in only one of your individual and partner repositories. You shouldn't be using both anyway, but if you happen to have pushed changes to both, just make sure only one contains the FINAL SUBMISSION commit message.

  4. If you decide you want to resubmit your assignment before the deadline, just do another commit with the message FINAL SUBMISSION (and don’t forget to push to GitLab!!). We will grade the last commit before the deadline that is tagged as the FINAL SUBMISSION.

  5. If you submit the assignment within 24 hours after the deadline (i.e. if there is a commit tagged "FINAL SUBMISSION") you will be charged a 10% lateness penalty. . If it is more than 24 but within 48 hours, you will be charged a 20% penalty. After 48 hours, we’ll roll back to the last commit tagged as "FINAL SUBMISSION" that was submitted before the deadline.

3.2 Required files in the submission

  1. A PDF document that presents all requested performance data. This file must have the following format. The stem part of the file name (before the .pdf) should begin with "A2-report" and end with you repository name, e.g. A2-report-baden-powell.pdf or, if working alone: A2-report-baden.pdf.

    You may provide data in tabular form only. 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 plot or table 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. You must also include any plotted data in tabular form.

    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!

    Cite any written works or software as appropriate in the text of the report. Citations should include any software you used that was written by someone else, or that was written by you for purposes other than this class.

  2. Source code. Even though we will be substituting fresh copies of all but one source module, include all code files your worked with, in case we need to unravel a problem with your turnin. For this reason, also include your Makefile.

  3. 2 Required text documents

    Your turnin must also fill in two important documents, which accompany the provided code.

    1. A completed self-evaluation discussing your work; if in a team this form address the division of labor and other aspects of how you worked together as a team.
    2. A file named DECLARATION, that states that the work was your own, and that you did not violate the Academic Integrity policies in effect for the course. Modify the DECLARATION by filling in your correct login ID(s) and the date only. Don't change anything else.

    These documents are required and we will not report a grade for your assignment without them. A 10% penalty will be assessed in cases of missing forms, empty forms, or forms not properly filled out.


☛ Important.

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 10 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.

Grading

There are 10 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

  1. Run not less than 10% slower than the provided reference, for each combination of input size and number of threads.
  2. Employ parallelism in the Merge phase under control of the -p flag.

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 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, our tester will use the original copies of all provided code files, except for the MergeSort.cpp file; only changes to the MergeSort file will affect your grade. Any changes you have made to other files will not affect your grade.

References to C++11 and to C++11 threading

Scott B. Baden   [Thu Apr 16 19:54:52 PDT 2015]