Our NBody simulator will extends the above gravity equation to calcuate positions, accelerations, and velocities in the x, y, and z directions of N bodies in a system. For the sake of simplicity in implementation, the following assumptions were made:
All particles are point masses
Gravitational constant G=1
We use a softening factor (sf2=1000) in gravity equations to avoid errors when two point masses are at exactly same co-ordinates.
The timestep constant ts=1
The N-Body Simulator will implement the following gravity equations.
Given inital positions and velocities x y z vx vy vz
at timestep t
, we can calculate the new positions x y z
of the next timestep t+1
:
To calculate the acceleration in the x, y, and z directions of any particle i
(accxi accyi acczi
), you must sum the acceleration caused by all other particles in the system (particles j
):
When you have your accelerations, calculate the new velocities in the x, y, and z directions:
Using these gravity equations, you can calculate your particles’ new positions and velocities x y z vx vy vz
at timestep t+1
and repeat the calculations for the next timestep after. If there are a large number of particles in the system and/or you are simulating for a large number of timesteps, you will quickly see the compute intensive nature of this problem. This algorithm has a computational complexity of O(N2) due to the iterative nature of the process. This is a great opportunity for implementing an accelerator in hardware.
In Module_01-Python Simulations on x86, you can try the nbody.py
to see how slow the particle simulation runs in software only. The particle simulation will run much faster with accelerators implemented in hardware (AI Engine).
This algorithm can be vectorized, hence reducing the complexity to O(N). In our AI Engine design, we will breakdown our workload to parallelize the computation on 100 AI Engine compute units.
Source: GRAPE-6: Massively-Parallel Special-Purpose Computer for Astrophysical Particle Simulations