Multicore Computing - N-Body Simulation:


Following is the description of assignment:

N-body simulation [1] is the simulation of particles under the influence of gravity. E.g. planets, stars in a solar system. In this assignment, you will work in a 2D world and ignore collisions.

A straightforward O(n^2) algorithm can calculate the movement of each object using Newton’s laws and leapfrog finite difference approximation scheme. In this scheme, you take discrete time jumps of a given time interval and at each jump calculate the new force, new acceleration (assuming constant force during the time interval), new velocity (assuming constant acceleration during the time interval), and new position (assuming constant velocity during the time interval) of each particle. A small time interval gives a more accurate simulation.

Barnes-Hut algorithm [2] is an O(n log n) algorithm that approximates the effect of a set of distant objects. You need a Quad-tree (Each node has four children) for this algorithm. This algorithm takes an additional parameter of the error threshold. Read the detailed description from this link.

There are five part of this assignment having equal marks.

Part 1: Implement the N^2 algorithm (C++)
Part 2: Parallelize the N^2 algorithm (Cilk/OpenMP/Intel TBB) and report scalability with at least 4 cores on different simulation sizes.
Part 3: Implement Quad-tree + N-log-N algorithm (C++)
Part 4: Parallelize the N-log-N algorithm with reader-writer locks on Quad-tree (C++ Threads or Pthreads) and report scalability with at least 4 cores on different simulation sizes.
Part 5: Repeat Part 4 but without any locks and using transactions instead (C++) [4]

Input should contain the time interval (dt), iterations to simulate, error threshold, the number of objects to simulate, their initial velocities and positions in double format. For testing you can generate random velocities and positions. If you are interested, you can also get actual initial parameters of planets in our solar system [3]. Test it on up to at least a 1000 objects.

Output should contain the final x,y position of each of the objects on a separate line. Needless to say the output of the first two parts should be the same for a particular input and the output of the last three parts should be the same.

I have implemented all the parts of this assignment using C++. You can download the project from https://goo.gl/RQsVBe