Programming Lab #2 (CSE 160, Fall 2013)
A rapid many body simulation with C++11 threads
Due Weds 10/30/13 at 6PM

Changelog

The Assignment

Your assignment is to parallelize the rapid many body particle simulation, discussed in class, with C++11 threads. As in the previous assignment your starting point is serial code. We’ve also provided a multithreaded executable that will enable you to assess performance.

Conduct experiments on the Bang cluster to assess scalability. If Bang becomes too heavily loaded, do your development on Ieng6. 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.

Getting access to the starter code

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.

1. Check out the provided code from within your home directory on Ieng6. You'll need a password, which will be sent to you after you've filled out the request Google form provided on Moodle. (Only groups that changed need to fill out the form.) your_AD is your active directory password.

   svn co --username your_AD svn://ccom-bang-login.ucsd.edu/SVN/A2/Provided
   

   When working on Bang, you'll check out the code differently:

   svn co --username your_AD svn://localhost/SVN/A2/Provided
   

2. Next, check out your development repository directory (Your group ID will also be mailed to you after you have completed the Google form):

   svn co svn://ccom-bang-login.ucsd.edu/SVN/A2/Turnin/YOUR_GROUP_ID Turnin
   

3. Add the provided code to your development repository. This task will be performed only once and can be done by one team member.

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

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 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 nbody. Do not change the name of this target and do not add additional source files to the Makefile, as we'll be grading your assignment with our own Makefile.

The accelerated algorithm

The algorithm used in this assignment takes advantage of knowledge about the underlying physical problem. In particular, because the force induced on a particle drops off rapidly with distance (see plot below), we may safely ignore forces that drop below a certain value, the cutoff. The value of the cutoff is 0.01 in our simulations.

We sort the particles, based on their coordinates, into a geographic data structure, a 2d array, called a binning mesh. The binning mesh divides the simulation region into a uniform array of boxes, each box containing all the particles residing in the corresponding region of space.

The force between two particles with the same y-coordinate is defined as follows.

Each bin of the mesh contains a list of particles situated in the physical region of space covered by the bin. We organize the computation (apply_force) around this mesh and need only look to boxes whose i and j coordinate differs by at most one. While the algorithm is still O(N²) in the worst case, we have reduced the number of computations significantly since we only search in nearest neighbor boxes. We can solve much larger problems than the slower method that must compute distances between all pairs of particles.

The code allows you to specify the shape of the binning mesh via the -x parameter (binning meshes are square so you specify just one number). You’ll vary the -x parameter to optimize the running time, subject to the constraint that the bin size must not drop below the cutoff value of 0.01 units. If you select a value that doesn't meet this constraint, the code will issue a warning and exit. Note that, as you increase the -n parameter, the size of the computational region, as measured in floating point valued spatial units, grows as sqrt(n). This ensures that the density of particles remains constant as n increases. Thus you will need to increase -x in order to optimize the running time, subject to the above constraint.

In this assignment you'll implement BLOCK partitioning in one dimension. Since the iterator that visits each box of the binning mesh enumerates a 1-dimensional iteration space, you'll split the mesh into horizontal strips.

A quick tour of the starter code

Familiarize yourself with the various modules. The command line parser in cmdLine.cpp explains the options needed to run the code.

The program defines two main classes to store the binning structure. The first classed, called Bins, defines the 2D array. Each element of the array is an object of class Box, containing a vector of particles.

Bins.{cpp,h} defines the Simulate() member function which controls the overall simulation via two other member functions, Bins::move_particles() and Bins::apply_forces, that update the binning structure. In turn, these functions apply identically named member functions (but of class Box) to each bin, i.e. Box::move_particles() and Box::apply_forces.

Your changes will be made to five (5) files:

Bins.cpp
Bins.h
Box.cpp
Box.h
nbody.cpp

To ensure that your program is correctly graded, do not rely on any changes you have made to any of the provided source code files, other than those in the above list. We will substitute fresh copies of the remaining files when we grade your assignment, including the Makefile. Please check that this is correct and that we might find later on that they need to change other files Don't change the signature of functions defined in particles.h as provided code makes callbacks to them.

Command line options

The code has various capabilities, which are controlled via command line flags explained in cmdLine.cpp. For example the following invocation

./nbody -n 16384 -t 1000 -nt 8 -x 40 -p 10 -s 1352723313 -o 16k.out

will run a problem of size 16384 particles for 1000 timesteps on 8 threads. The particles will be organized in a 40 × 40 mesh binning structure. The results will be plotted via gnuplot and output every 10 timesteps. S random number seed is specified via the -s flag. (See below in the discussion of Testing your code.) We also asked to output the positions of the particles to a file called "16.out" You may find the output option handy when debugging your code, in conjunction with summary output mentioned below.

Plotting capability

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.

Assignment Checklist

1. Implement the multithreaded version of the provided code, specifying any synchronization needed to ensure correctness.
   1. Write a loop to spawn the thread callback function and another to join threads. Create your thread callback function, using a mix of existing code, and code you write.
   2. Parallelize the computation loops in the provided code. These loops appear in Bins.cpp and they iterate over the boxes making up the chaining mesh. The actual computation is carried out in class Box, which makes up the chaining mesh. No parallelism is expressed in that class. Thus, if you make any optimizations that improve single core performance, they will generally occur here.
   3. Implement static scheduling, that is BLOCK partitioning. You must correctly handle the case where the number of threads does not evenly divide the mesh size (-x parameter).
      
   4. Use the provided barrier synchronzation code as needed.
      If you have time, implement a logarithmic time barrier for extra credit (see below). To show that your log-time barrier improves performance, reduce the size of the problem enough so that barrier syncrhonization becomes relatively costly and there is a clear improvement in performance.
      
   5. If you determine that you need to support atomic operations, use the C++ atomic template class rather than critical sections, and hence avoid the need for mutex variables whenever possible.
   6. Add code in nbody.cpp that prints out the number of threads used to run your code.
   
   
2. Conduct a strong scaling study using the default parameters defined in the provided code. Be sure to use the same random seed on all your timing runs. If you have time, try different random seeds. In this case, you can let the program pick the random seed and reprot the average time for ten runs for each data point (# threads). Note that you will still need to repeat a run 3 times, with the same random seed, for each of the 10 runs. You'll report the minimum time of each set of 3 runs, and take the average of the 10 times you've obtained.
   1. Vary the number of threads from 1 to 8, in powers of two. Verify that results are independent of the number of threads.
   2. Determine the optimal value of -x on 1 core to within a resolution of 8, i.e. 24, 32, 40 etc. There is no need to explore this parameter at a finer resolution. Once you have established the value of -x on 1 core use it in your strong scaling study. Plot the parallel speedups and explain your results.

      You be able to improve performance by further tuning the -x parameter for each value of the number of threads. However, it is not necessary to conduct a two parameter study of -x and the number of threads over all the values of -x that you tested on one core.

3. Report and comment on performance. This requirement is described below under Document your work in a well-written report.
   
4. Extra credit. Up to 5% extra credit will be awarded for implementing a logarithmic running time barrier.

Taking timings

Take timings with the provided timer code (it uses gettimeofday()) which measures wall clock time. On Bang, use an interactive qlogin node, or a batch queue, to collect timings. Take at least 3 timings for each combination of parameters, and report the minimum timing.

Instructions for submitting jobs via the batch queue are described in

http://cseweb.ucsd.edu/classes/fa13/cse160-a/Bang/runningJobs.html

When you are measuring running times for your performance studies, do not enable plotting (-p) nor output the result to a file using the -o option, as doing so could affect your observations.

Testing your code

Your code will report 2 accuracy measures that you can use to determine if your code is correct. These values reflect information about all the particles in the simulation and hence is a summary error. Compare the two reported values against the single threaded run, obtained with the following command line parameters: ./nbody -x 40 -s 1359856190 -nt 8

(u,v) Max = ( 2.27641850e+00, 2.84668447e+00 )
(u,v) L2 = ( 5.81159812e-01, 5.81967427e-01 )

These values should agree to the full printing precision (9 significant figures) when you vary the number of threads. However, as you grow the -x parameter, you'll note changes in the last 3 digits. Such changes are due to roundoff errors that are a side effect of how the particles are organized in the chaining mesh. We will accept these errors which should never affect the higher order 6 digits. Larger errors indicate an error. Note that, if you run for sufficiently long times (-t option) and/or with more particles, you may note larger errors, even in an otherwise "correct" code. These errors are an artifact of the computation so explore this regime with care.

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. As in the previous assignment, use the -s flag to start the random number sequence from a known place. For each combination of input variables such as -t, -n and so on, run 3 times with the same seed and report the minimum time.

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, -n and -x command line parameters.

Things you should turn in

1. Document your work in a well-written, one to two page report, including plots, which presents your results, analyzes them, and offers insight. Your report should briefly discuss any performance bottlenecks of the implementation. If you improved performance of your code in a sequence of steps, be sure to document this in your svn log, which we'll consider an Appendix to your report. We will be looking at the log, and will deduct points if we can't see your thought processes. If you like, summarize the information in a list or a table in your report. If necessary, provide pseudo code to illustrate the concepts. Do not include full code listings in your writeup as these will be in your turnin.

   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 such cases you must talk with us prior to get our approval.

2. Turnin. Your turnin will consist of two parts.
   1. Hard copy of your report. Hand in a hard copy by the deadline, placing it in Jing or Yashodhan's 's student mailbox on the 2nd floor of EBU3B. The paper and electronic versions of the report should be identical. When there are any questions about turnin time, the latest timestamp of all files in your turnin establishes the turnin time. We won't collect files included in your repository after the deadline.
      
   2. Electronic turnin. Our tester will check out your code from your private Turnin repository, using the latest versions that were created not later than the deadline. Be sure that your svn repository is up to date. If you get stuck at the end, we can always roll back your code when grading it, though this may delay the grading of your assignment and result in a small penalty.

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

      1. A completed team self-evaluation called teameval.txt, that discusses the division of labor and other aspects of how you worked together as a team. A copy of the form is included in the provided code.
      2. A file named DECLARATION, that you sign electronically, stating that the work was your own, and that you did not violate the Academic Integrity policies in effect for the course. The DECLARATION file is also included with the provided code. Make changes to your login ID(s) and the date only. Don't change anything else. Be sure that the date you entered falls in between the dates 10/15/2013-10/28/2013.
         

Grading

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 the code files mentioned above, our tester will use fresh copies of all code files, so any changes you made to those files be lost and therefor 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 portio of the assigment your code must

1. Be correct.
2. Run not less than 10% slower than the provided reference, for each combination, that we test, of input size -n, number of threads -t and binning mesh size -x.
3. Your code must correctly handle the case where the number of threads does not divide the mesh size -x.

Copyright © 2013 Scott B. Baden   [Fri Oct 11 09:59:29 PDT 2013]