Efficient clustered n-Body simulation in futhark

This project aims to implement the barnes-hut algorithm which runs in O(n log n) as compared to the naive version, which runs in O(n²).

Fetching and compiling

Assuming you have either Cuda or OpenCL installed, along with the futhark compiler of at least version v0.16.1

1. Clone into this repository
2. Change directory to source
3. Run futhark pkg sync
4. Run make
5. Run ./nbodysim-gui for a working (graphical) demo

To run tests and benchmarks, substitude step 4 to futhark [cuda|opencl] nbodysim.fut -- use either opencl or cuda depending on your choice of backend. Lastly run the binary: ./nbodysim

Result

Should be a comparison between a collection of implementations:

• The existing futhark implementation.
• A naive barnes-hut implementation.
• A flat barnes-hut implementation, ie. Where we apply all flattening and other rules we learned from the Parallel Functional Programming-course

Of the implementations we would compare speed and draw conclusions scaling/implementation wise.

Roadmap (country-roads edition)

• Get Lys working
• Add naive implementation to Lys
• Create benchmarking stuff
• Optimal implementation (Barnes Hut)
  • Copy radix tree
  • Copy morton codes
  • Implement Octree
  • Apply simulation steps on said Octree

Barnes hut sources

• "The barnes hut algorithm", slideshows from Thomas Trost, The Institute for Theoretical Physics, Ruhr University Bochum.
• "An efficient CUDA Implementation of the tree-based Barnes Hut n-Body Algorithm", CUDA implementation paper, M. Burtscher, K. Pingali.
  • slideshow (basically the same thing in a different format)
• Wikipedia
• Octrees Paper from Tero Karras
• Sparse Octree gravitational N-body code Jeroen Bedorf et al.