![[Force]](./Force.png)
![[bins]](./bins.png)
| Date | Description |
| 8-Feb-13 | Original posting |
| 12-Feb-13 | Mini extra credit |
Your assignment is to implement a fast variant of the particle simulation, discussed in class, and to use multiple cores with multithreading. You've been provided with serial code, written in C++. As in the last assignment, the parallelization you'll perform is specified via OpenMP annotations. Use the OpenMP variant to determine performance goals but use C++11 threads to parallelize the code.
You'll implement static block partitioning and dynamic scheduling with a chunk size. In this case the blocks will be two dimensional. As in the last assignment, there is also an option to generate an imbalanced workload, which you'll use to to demonstrate the capability of your dynamic loop scheduler.
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 A3 Moodle forum.
The assignment includes a brief report, and the requirements for your report are described at the end of this writeup.
The algorithm used in this assignment takes advantage of knowledge about the underlying physical problem. In particular, the force induced on a particle drops off rapidly with distance (see plot below), and we ignore forces that drop below a certain value, which is called the cutoff. The value of the cutoff is 0.01 in our simulations.
We sort the particles, based on their coordinates, into the 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. Force(x) = C*(dx) where C = (0.01/r2 - 1/ r3), r = max( dx, 10-3)) and dx = distance (in x) between the two particles. |
Each bin of the mesh is a list of particles holding the particles contained 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(N2) in the worst case, we have reduced the number of computations significantly since we only search in nearest neighbor boxes. As a result of the algorithm's improved running time, we have increased the default value of the -n parameter to 8192 particles.
The code allows you to input the shape of the binning mesh via the -x parameter. You will vary the -x parameter to optimize the running time, subject to the constraint that the bin size is not allowed to drop below the cutoff 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. However, your dynamic scheduler will work differently. Chunks may consist of a portion of a row of the mesh, that is, if the chunk size is smaller than the linear dimension of the mesh.
You have been provided with starter code that implements the serial algorithm. This code has been installed on the "bang" cluster as $PUB/HW/A3, 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 five (5) files:
Bins.cpp Bins.h Box.cpp Box.h nbody.cpp
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
As in the previous assignment, you'll 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.
As with the previous assignment, OpenMP pragmas are used to express parallelism, e.g.
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.
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:
OpenMP pragmas
#pragmas omp .....
make omp=1
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. 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 (recall the dbg=1 Make command line flag). Don't forget to comment this line out when collecting your timings our your code will run more slowly with optimization turned off.
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 -c 32 -b -p 10 -s 1352723313
will run a problem of size 16384 particles for 1000 timesteps on 8 threads, using dynamic scheduling and a chunk size of 32. The particles will be organized in a 40 × 40 mesh binning structure. 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.
Note that you may 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.
Use the batch queues on Bang to collect timings. 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, 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.
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. Verify that results are independent of the number of threads.
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, properly filled in as explained in the previous assignment:
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.
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.
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.
[Fri Feb 8 20:12:40 PST 2013]