BOOST-Hut: Microarchitectually optimized N-body simulation

High‑performance, microarchitecturally optimized, strictly single-threaded Barnes–Hut N-body simulation written in C/C++.
Result of our ETH Zurich fastcode project, and playground for algorithmic tuning and micro‑architectural performance studies.

---

Repository layout

Path	Purpose
src/	All C/C++ sources + Makefile for building.
src/implementations	Different optimization stages and experiments.
plotting/	Helper scripts to create roof‑line, speed‑up and per‑step trace plots.
tests/	Reference input files and their expected outputs for quick self-consistency checks.
figures/	Performance and speedup plots pre-created by the plotting scripts.
21_report.pdf	Report outlining all performed optimizations and evaluations.

---

Building

cd src
make                # builds every target below
make <target>       # build one specific artefact
make clean          # remove the entire build/ directory

Supported targets

Make target	Output binary	What it’s for
release	build/bin/barnes_hut_<arch>_<os>	Fastest build—vectorisation, read from input file, -O3, no instrumentation.
measure	build/bin/barnes_hut_measure_<arch>_<os>	Counts cycles, L1+L2 misses, uops, ... . Generates random particle sets.
flop_count	build/bin/barnes_hut_fc_<arch>_<os>	Inserts hooks to count every floating‑point operation.
asan	build/bin/barnes_hut_asan_<arch>_<os>	Address‑Sanitizer build for chasing leaks & out‑of‑bounds accesses (slow).
sim	build/bin/barnes_hut_sim_<arch>_<os>	Release version, but with a step-by-step particle log (slow).

---

Running the main binary

./build/bin/barnes_hut_<arch>_<os> <input-file>

The output is a plain‑text dump of the final particle state—use the scripts in plotting/ if you want richer visualisations.

---

Input‑file format

All parameters are SI units.

theta:       <float>      # Barnes‑Hut opening angle
steps:       <integer>    # Simulation steps to run
gravity:     <float>      # Gravitational constant (normally 6.67430e‑11)
particles                 # Start of particle list
<mass>, <x>, <y>, <z>, <vx>, <vy>, <vz>
<... one line per particle …>

Example (tests/solar_system.txt):

theta: 0.5
steps: 31536000                  # 1 year
gravity: 6.67430e-11
particles
1.989e30,            0, 0, 0, 0,     0, 0        # Sun
3.285e23,  57.9e9,    0, 0, 0, 47360, 0          # Mercury
4.867e24, 108.2e9,    0, 0, 0, 35020, 0          # Venus
5.972e24, 149.6e9,    0, 0, 0, 29780, 0          # Earth

---

Manual performance experiments

All parameters for the measure and flop_count builds live in

• src/measure.c
• src/perf_measure/measure_config.h

Tweak the particle count, steps, measured functions - then make measure / make flop_count.

---

Plotting utilities

The Python tool measure_and_plot.py performs an end-to-end performance and speedup benchmark. It emits the plots as PDFs under figures/, and the raw data under measure_results

All other plotting tools come without warranty ;)

---

Happy simulating 🚀