Speeding up N-body simulations

N body simulations are fundamental in many areas of research. For example, if we want to predict how galaxies evolve or how molecules interact with each other you have to compute the Gravitational or Coulomb interactions.

Computational complexity

The first problem with these N-body simulations is that the naive approach has O(n²) complexity as it considers every pair of particles. To solve this we can use the Fast Multipole Method, bringing the complexity down to O(n). The algorithm exploits the fact that these interactions decrease rapidly with the distance among particles.

Another important feature is that its keeps the error bounded, and given the peculiarities of floating-point arithmetic it can even get more accurate results than the naive approach in some specific situations.

Exploiting supercomputer’s hardware

Once we have a good FMM implementation the next step is to parallelize it using constructs such as threads, tasks to be executed independently or even accelerators such as GPUs. This works great and has given good results concerning efficiency and speedup, but it has a big problem: you can’t scale! Scaling is important because we want to simulate increasingly complex scenarios, so we have to figure something out.

We can solve this issue with MPI, but doing so requires very hard work because we have to explicitly distribute the workload between nodes while keeping the number of communications to the minimum.

It is definitely a challenge but we’ll do our best! I hope you enjoyed the post and thank you for reading.