McGill University
School of Computer Science

Computer Science 308-767: Parallel Programming

The Big Dance as seen by Barnes and Hutt

As you can guess from the title of the assignment, you are going to implement the Barnes-Hutt algorithm. The emphasis will be on load balancing, since oct-trees are not very good at knowing where the bodies are located. You should use the BSP (Bulk Synchronous Programming) model to implement the algorithm.

In BSP all of the processors do the following:

This approach is easy to implement and the serial code will not wind up looking all that different from the parallel code. The implementation should be on a shared memory machine.

Now to the fun part-load balancing. You can implement one of two load balancing algorithms (1) orthogonal recursive bisection (2) cost-zones. The first scheme is the easier of the two, and only works in 2-D. The second scheme will take more work to implement. You should use shared memory for this load balancing algorithm, as it will be much easier to implement this way.

The choice is yours-if you feel adventurous and have the time, try 2. However it is not required (you will clearly get extra consideration for implementing the second method). There will be no loss of marks if you chose 1.

You should use 4 to 6 processors . Assume that the particles all have the same mass (say 1). You should present results for several (at least 3) different initial configurations, i.e. different load distributions in which you show the results for all of the processors. You should run the algorithm without load balancing for one of the initial configurations in order to show the improvements produced by the algorithm.