| Date | Description |
| 02-Oct-13 | Original posting |
| 07-Oct-13 | Clarification about function signatures |
| 08-Oct-13 | Corrected path name for assigning $PUB on Bang |
| 11-Oct-13 | Clarification about # threads being a power of two |
| 11-Oct-13 | Constraint on -g parameter to avoid some corner cases |
| 12-Oct-13 | Documentation for -w and -r options |
Your assignment is to implement the merge sort algorithm, discussed in class, to run on multiple cores with multithreading. You'll use C++11 threads to parallelize the code. You've been provided with serial code, written in C++, and an executable reference implementation to assess performance goals. (There are two, one for each course platform. Code compiled on Bang won't run on Ieng6, and vice verse).
Using your implementation, you'll conduct experiments, on the Bang cluster, to assess scalability and load balancing tradeoffs. Do your development on Ieng6 if Bang becomes too heavily loaded. In the spirit of friendly competition, post your performance results to the A1 Moodle forum.
The assignment includes a brief report, and the requirements for your report are described at the end of this writeup.
Instructions for setting up your environment on Bang and for submitting jobs are described HERE.
We've provided you with starter code that implements the serial algorithm. We've also provided a reference binary that supports multithreading so you can assess performance. This code has been installed in an SVN repository that resides on Bang.
To use the svn repository, take the following 3 steps.
svn co --username your_AD svn://ccom-bang-login.ucsd.edu/SVN/A1/Provided
svn co --username your_AD svn://localhost/SVN/A1/Provided
svn co svn://ccom-bang-login.ucsd.edu/SVN/A1/Turnin/YOUR_GROUP_ID Turnin
cp Provided/* Turnin cd ./Turnin svn add * svn commit -m "import the provided code"
So you don't have inconsistent copies different machines, make sure that you keep your repository up to date before you log out or interrupt a login session. You can check on the status of your files with the svn status command. Commit any file with the 'M' tag (modified but not committed).
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() to any of the functions 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 included "arch" file located in $(PUB)/Arch/arch.gnu-4.7_c++11. PUB is should be defined in ~/.bash_profile on ieng6 as
export PUB= /home/linux/ieng6/cs160f/public
and on Bang as
export PUB=/share/class/public/cse160-fa13
The Makefile produces a target called msort.
Important: Do not change the name of this target. You may add additional source files if you wish, but don't change the names of the any of the provided files.
You may override certain settings, such as compiler optimization, by redefining macros in your Makefile. Within the Makefile, we have provided a commented out line that, if uncommented, will redefine the optimization level. This may come in handy if you want to debug your code using gdb. But don't forget to comment this line out when collecting your timings our your code will run more slowly with optimization turned off.
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
The other options are self-explanatory. Don't forget to do a make clean before rebuilding the code. Otherwise, you may get anomalous behavior.
The code has various capabilities, which are controlled via command line flags explained in cmdLine.cpp. For example the following invocation
./msort -n 67108864 -s 1380501542 -g 262144 -s 1380501542
will run a problem of size 67108864 (64 Meg) keys on 2 threads. It will terminate the recursion when the input size drops below 262144 keys (256K). Lastly, a random number seed is specified via the -s flag. See below in the discussion of Testing your code.
The inputs provided with randomly distributed inputs (the default) are large numbers, and can be hard to distinguish from one another when debugging. To this end, there are two options, -r and -w to specify best case and worst case inputs, respectively. These options play no role in how we grade your assignment and are intended to help you with testing, as the keys start from 0 and are generally much smaller than the keys specified with random distribution (the default).
Use the batch queues on Bang to collect timings. This is explained in the document Getting Started with Bang, which references the document Running jobs on the Bang Cluster.
Do NOT run interactively on Bang's front end as a class of over 100 students will overload the machine (see instructions provided in the Bang document). But you may find it more convenient to collect your measurements by running non-interactively.
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. Shut off any debugging output when you collect timings results. as doing so could affect your observations.
The code will verify that the list has been sorted. 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 invalidate performance comparisons on different numbers of processors, unless we have a way of generating the same random number sequence when required will. 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.
We will grade your assignment on bang. Be sure to do your final testing on that machine, to avoid any surprises at turnin time.
We will test your code's correctness and performance. 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.
Request an interactive compute node via the qlogin command. Once you've been granted your node, you'll see the following output, though your job number and assigned node number will differ:
Your job 239 ("QLOGIN") has been submitted
waiting for interactive job to be scheduled ...
Your interactive job 239 has been successfully scheduled.
Establishing builtin session to host compute-0-26.local ...
You are now running in a shell and have exclusive access, for 30 minutes, to a compute node with 8 cores. Since Bang has 32 nodes, at most 32 users can be accommodated. If there are no more available nodes, move to ieng6.
Wait until you receive a command prompt. You will now be running in a new shell, within your $HOME directory. You may run commands on the compute node, edit and compile code, but you won't be able to submit non-interactive jobs. Since SVN won't work on the compute nodes, when tuning the performance of your code, it will be convenient if you have 2 windows: one on the front end for editing and compiling, the other for running the code.
As a courtesy to other users, exit the interactive session when no longer needed.
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.
Take care in how you plot your data, only plotting 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. Tabular data may be included electronically (in your turnin) as a spreadsheet or other document called, e.g. Data.xlsx, Data.txt.
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.
In addition to source code files, your electronic turnin must include a Makefile so that we can build and test your code.
Your turnin must also include the following important documents. These documents are required as the grading process which not complete without them. Empty forms, or forms not properly filled out, will result in a 10% penalty being assessed, in addition to holding up the grading process.
| Don't wait until the last minute to complete the assignment. The batch queue can become full, the machine unresponsive, so be sure to get results early on. Be sure you are familiar with svn, and commit code frequently. |
We will use a script to measure your code's performance and test for correctness. We will also look at code since some correctness errors cannot be tested automatically. Except for MergeSort.cpp, our tester will use fresh copies of all code files, so only changes to the MergeSort file will affect your grade. Any changes you have made to other files will not affect your grade.
Your grade will based on results obtained from your code, and documentation. Documentation includes the report, comments in the code, and svn log entries. The grade for the code will depend on two factors: performance and correctness. The grade for your documentation will be based on clear explanations, and in the case of the report, insight into the results and presentation of experimental data. Remember: the report is brief so you need not go into long explanations. Focus on what's important. When you commit files with svn, be sure to add brief, but descriptive comments, suitable for understanding your development process. If you aren't sure, be sure to ask us.
To get full credit on the programming portion of the assignment, your code must
Copyright © 2013 Scott B. Baden [Wed Oct 2 10:43:03 PDT 2013]