Galaxies

Assigned: Tuesday, Mar 8, 2016

Due: Wednesday, Apr 6, 2016 at 10:30pm

Collaboration: Work with your assigned partner for this lab. You may use your classmates and their code as a resource, but please cite them. Sharing of complete or nearly-complete answers is not permitted.

Overview

For this lab, you will extend a naive, single-threaded implementation of a n-body simulation to use the Barnes–Hut Method. An n-body simulation simulates the movement of n massive objects acting on each other gravitationally. The naive approach considers all pairwise interactions, which is quite inefficient for large numbers of objects. The Barnes–Hut method instead divides the simulated space into quadrants, those quadrants into quadrants, and so on, until every object is in its own quadrant. Then, you calculate the force of an entire region on each point, using regions with a single point for nearby objects and larger regions for distant objects.

This implementation method lends itself well to parallelism: subdividing the space into quadrants can be approached using the divide-and-conquer method, then computing forces on each point can be done in parallel for each body.

The starter code, which implements the naive approach, is available at github.com/grinnell-cs/213-galaxy. Follow the usual procedure for forking this repository and adding your partner as a collaborator.

Provided Code

Quite a few of the files in this lab will be familiar from the raytracer lab. Part of the logic for the n-body simulation is in the star class, defined in star.hh. This class tracks the mass, position, velocity, and color of an individual star. You can also use this class to accumulate force vectors on a given star, then update its position and velocity according to that force.

The remainder of the simulation logic is in main.cc, in the updateStars function. This code loops over all stars, computes the force between each pair of stars, merges stars that are close enough to collide, then updates the position of each star once forces have been calculated. The figure to the right shows a simulation after most of the stars have collapsed into a few massive stars.

Build the program with make, then run ./galaxy to start the simulation. Clicking on the screen will create a random “galaxy” of stars moving in a somewhat-random circular pattern. If stars drift out of view, you can use the arrow keys to move the viewport.

Your Task

Your task is to implement a parallel version of the Barnes–Hut method for this program to replace the naive pairwise interactions model. First, you will need to subdivide the space into quadrants recursively until every star is in its own quadrant. This process is inherently parallel, as every quadrant can be subdivided independently. Next, you should compute the forces on each star in parallel using the quad-tree you construct for Barnes–Hut. Once all forces are computed, update the position of each point, doing as much of this in parallel as possible.

All of these tasks offer significantly more parallelism than you will actually want to take advantage of; there is no point in starting 10,000 threads to compute forces if you only have four cores on your system. To get around this issue, you must use the thread pool model for dispatching parallel tasks. Every new parallel task is added to a global work queue, and some number of threads (determined by a single constant) will continuously take tasks off the queue and complete them. Your queue implementation from the data structures lab may be useful when you implement your work queue. Your work queue will need to keep track of the functions each thread should call, which requires function pointers. We used these in the warmup lab to implement every, but C++ also offers a useful function class that cleans up the syntax a bit.

A successful parallel implementation will use synchronization only when necessary. For example, the quad-tree is read-only after it has been created, so there is no need to use locking of any kind when accessing the completed tree. Think carefully about what must be synchronized before jumping into your parallel implementation. This may be easier if you implement the Barnes–Hut method in serial first.

Performance Evaluation

In addition to implementing a more efficient, parallel n-body simulation method, you will also conduct a small performance evaluation of your implementation. Add code to track the number of stars being simulated and the time to run a single frame of the simulation, which you can output to the terminal in CSV format, which you can open in most spreadsheet programs. Collect information for at least 5,000 frames in each of the following configurations:

1. The original program
2. A serial version of the program that uses Barnes–Hut
3. A parallel Barnes–Hut version

Plot the frame calculation time as a function of the number of bodies. How does changing the algorithm change the time it takes to simulate one frame? How does adding parallelism change the time it takes to simulate one frame?

Add your graph to the repository and include your responses in a README.md file in your repository.