FPGA based gravitational multi-particle simulator

Abstract

The Multi-Particle/N-body simulation problem has been pursued by numerous scholars in the last century. Nowadays particle simulators are considered to be highly valuable tools in several fields of Physics, most notably that of Astronomy. The idea behind the n-body problem is to find the most time and resource efficient method to simulate an ‘n’ number of particles in a given space. By simulating it is meant that the next position of each particle is continuously predicted by a combination of the particle’s current vectorial velocity and the forces exerted on that same particle by the other particles. There are various ways to achieve this, with the most basic being the brute-force approach which compares each particle with every other particle in the system for each time-step. An optimised approach towards solving the n-body problem is the barnes-hut algorithm, which was developed in the mid 80s and makes use of a quad-tree data-structure. The multi-particle problem in this dissertation has been tackled from two different perspectives; software and hardware. For the scope of this project the brute-force approach was applied both to the software and hardware implementations, while the barnes-hut was only implemented in software part. The software implementation consisted of a simulator built from scratch in Python, utilising custom packages such as the quad-tree data-structure. The basic brute-force algorithm compares each particle with every other particle while the barnes-hut makes use of the quadtree, to improve computational times at the expense of some degree of accuracy. On the other hand the hardware implementation consists of a brute-force simulator built using an FPGA in VHDL. The idea behind this project was to learn about the difference between the two implementations in terms of computational efficiency. Each implementation was approached using a different mindset. The software implementation required a procedural and structural approach even though object oriented principles were applied, whilst the hardware implementation required a more state driven and concurrent approach. In the software implementation the n-body problem was solved using a rather highly abstracted understanding of the logic with minimal to no particular interest of how it is implemented at a lower level. This is in stark contrast with the hardware implementation where the hardware dictated how the simulator was to be built, so a low level understanding was mandatory and a priority. The results for the software implementation showed that the barnes-hut offers significant improvement over the basic brute-force approach. This is primarily due to the efficient quad-tree data-structure implementation, with fast traversal times. It was also concluded that the FPGA isn’t necessarily the best option, even though it might sound counter intuitive. This is because if parallelisation is not utilised, the problem becomes quadratic and computational times become large in a very short amount of time. In the hardware implementation computation times are dependant on the propagation of the values through the logic and not on the inputs themselves, more specifically the intensiveness of the calculations.