When I started CS380P at UT Austin, I expected a tough parallel computing assignment from my Parallel Computing course. What I did not expect was to get genuinely obsessed with a physics simulation.
The problem was deceptively simple: implement a parallel N-body gravitational simulator using the Barnes–Hut algorithm with MPI. I built a correct sequential Barnes–Hut tree code first, then parallelized it with MPI, then kept going until I had an interactive web demo that lets you see the quadtree evolve in real time.
This post is a guided walkthrough of what I built, how Barnes–Hut turns an impossible looking problem into something tractable, what MPI does to a tree-based algorithm, and what the accuracy versus speed knob (θ) really means when you can watch it.
