| Date | Description |
| 25-Jan-13 | Original posting |
| 30-Jan-13 | Clarification about parallelization |
| 2-Feb-13 | Change to restriction on signature modifidication. |
| 7-Feb-13 | If you are attempting the extra credit options. |
Your assignment is to implement the particle simulation, discussed in class, to use multiple cores with multithreading. You'll use C++11 threads, rather than pthreads, to parallelize the code. You've been provided with serial code, written in C++, that may also be compiled to run for multithreaded execution under OpenMP. Use the OpenMP variant to determine performance goals.
You'll implement static block partitioning and dynamic scheduling with a chunk size. The code generates a random distribution of particles with random velocities. Under these conditions, the particles will continue to be distributed randomly. Thus, static block partitioning will enable good scalability. However, there is also an option to generate an imbalanced workload (see discussion of options below) and you'll use this option to demonstrate the capability of your dynamic loop scheduler.
Using your implementation, you'll conduct experiments, on the Bang cluster, to assess scalability and load balancing tradeoffs. In the spirit of friendly competition, post your performance results to the A2 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.
You have been provided with starter code that implements the serial algorithm.
This code has been installed
on the "bang" cluster as $PUB/HW/A2, where $PUB
is defined as /share/class/public/cse160-wi13.
The command line parser in cmdLine.cpp explains the options needed to run the code.
Familiarize yourself with the various modules. Your changes will be made to one file: particles.cpp. This file contains three routines that you'll modify:
SimulateParticles( )
apply_forces( )
move_particles( )
The first controls the overall simulation, and invokes the other two routines. You'll modify it to spawn and join threads, in which the former will invoke a callback thread function that you'll also write. 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 functions defined in particles.h as provided code makes callbacks to them.
When glancing at the code, you'll notice some lines that begin with the text
#pragmas omp .....
These pragmas are interpreted by the compiler to generate multithreaded code, provided you enable OpenMP compilation by specifying "omp=1" on the make command line, e.g.
make omp=1
This capability will enable you to set performance goals for your code. This option specifies static BLOCK partitioning. To enable dynamic scheduling under OpenMP, with an optional chunk size use the following command lines; the omp=1 clause isn't required as the makefile will specify OpenMP compilation:
make dyn=1 chunk=20
Note that these options should not be used in the code you write, as they would conflict with C++ threads. They are to be used in the provided serial code only. See comments below, under Command line options
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. The Makefile produces a target called nbody. 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 compile for debugging with gdb, specify the argument
dbg=1
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
./nbody -n 1024 -t 1000 -nt 8 -c 32 -b -p 10 -s 1352723313
will run a problem of size 1024 particles for 1000 timesteps on 8 threads, using dynamic scheduling and a chunk size of 32. The computation will use an imbalanced workload (-b). The results will be plotted via gnuplot and output every 10 timesteps. Lastly, a random number seed is specified via the -s flag. See below in the discussion of Testing your code.
Your code should control dynamic scheduling with the -c flag. If the flag is not specified, your code should employ static (BLOCK) scheduling.
Note that the make command line flags omp, chunk, and dyn are to be used only when building the provided code for execution under OpenMP. They should not be used in the threaded code you write for the assignment. Rather, dynamic scheduling is to be controlled at run time, and should not be compiled into your code as with the provided code. Be sure not to specify omp=1 on the make command line. If you wish, remove the all the openmp pragmas from the file particles.cpp.
Conversely, since the -c option controls dynamic scheduling at run time, it doesn't have any effect on the provided code that you will run under OpenMP, which handles chunking at compile time. Each time you want to use a different chunking factor for the OpenMP code, you must recompile but this will not be the case for the code you write.
The plotting capability, controlled via the -p flag, uses gnuplot, and may be useful in debugging. It runs on the main thread only and is not multithreaded. The plotter (Plotting.cpp) interfaces with gnuplot, which is free-ware.
Remote visual display can be slow if you are off campus. If a display window does not appear on your screen, then your ssh display settings are not set correctly. If you are connecting to the remote machine from a Linux platform using ssh, use the -X option:
% ssh -X yourlogin@ccom-bang-login.ucsd.edu
If you are connecting from a Windows platform, and are using a 'secure shell client' AND 'exceed' (or xwin32, or cygwin) to log into a remote machine you must ensure that 'X11 tunneling' is set. To do this, you must have installed Cygwin /X with X11.
Use the batch queues on Bang to collect timings. You may run interactively (see instructions provided in the Bang document). But you may find it more convenient to collect your measurements by running non-interactively.
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.
Do not enable plotting (-p) when you are measuring running times for your performance studies, nor output the result to a file using the -o option as doing so could affect your observations.
Your code will report 2 accuracy measures that you can use to determine if your code is correct. Compare the two reported values against the single threaded run:
(u,vMax) = ( 1.90291303e+00, 2.17501010e+00 ) (u,vL2 ) = ( 5.82275320e-01, 5.94707046e-01 )
As discussed in class, these values should agree to within about 5 decimal places of the single threaded reference. You should expect some (smaller than 10-5) differences; the computations are sensitive to roundoff errors, and multithreading will cause some computations to be reordered.
Since the initial particle distribution is random, each run will use a different particle distribution, making it impossible to test for correctness unless we have a way of generating the same random number sequence at will. We can accomplish this with 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.
You also use the graphical output to debug some errors, though it is useful in ascertaining gross errors only.
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. 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 -t and -c command line parameters. You need not handle the case where the number of threads doesn't divide the -n parameter and similarly with the chunk size option -c.
You can catch obvious errors using the graphical output, but use the -s option to compare results exactly. Only an exact test can be guaranteed to verify correctness; the human eye is subjective, and the visual output may not have sufficient resolution to resolve subtle errors. Verify that results are independent of the number of threads.
First try out the provided code. From within your home directory, copy over the provided assignment code, build it.
cp -p -r $PUB/HW/A2 . cd A2 make
Next, 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.
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.
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.
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.
Your electronic turnin must include a Makefile so that we can build and test your code. We will run your code to test it and will check correctness using the residual measurement.
Your turnin must also include three important documents:
These documents are required as the turnin process will 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.
If you are attempting any of the 3 extra credit options include a section at the beginning of your writeup called What we attempted for extra credit and then discuss each attempt in detail later in the report.
If you are attemping cyclic decomposition, use the -c flag to indicate the chunking factor, taking the followign convention. Since -c -1 is reserved for static block decomposition, let's take the convention that, for c<100, c=-100-k indicates cyclic decomposition with a chunking factor of k.
Since the turnin script will try to compile your project before letting you submit your assignment, it's important that you turn in all the files you have, including a Makefile. However, when grading your assignment, we will substitute all the files that we asked you not to modify (as noted above) with the original copies of the version we provided you. This is why it is important that you do not change those files in your own turnin, as they will be lost. The turnin script will have an option to do some basic testing, and we strongly suggest you avail yourself of this option.
Don't wait until the last minute to attempt a turnin for the first time. The turnin program will ask you various questions, and it will check for the presence of certain required files, as well as your source code. It will also build the source code if you like, to catch any obvious build errors. 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. The turnin procedure will be available about a week before the deadline.
Your grade will depend on 3 factors: performance attained by your code, correctness and well-displayed results.
Copyright © 2013 Scott B. Baden [Fri Jan 25 19:59:36 PST 2013]