  The N-body problem is a classic problem involving a system of N discrete
bodies mutually interacting in a dynamical system. At any moment in time there
are N*(N - 1)/2 such interactions occurring. This scaling as N^2 leads to
computational difficulties where simulations range from tens of thousands of
bodies to many millions. Approximation algorithms, such as the famous
Barnes-Hut algorithm, simplify the number of interactions to scale as N(log N).
Even still, this improvement in complexity is insufficient to achieve the
desired performance for very large simulations on computing clusters with many
nodes and many cores. In this work we explore a variety of algorithmic
techniques for distributed and parallel variations on the Barnes-Hut algorithm
to improve parallelism and reduce inter-process communication requirements.
Explicit algorithms and details are provided for reproducibility. Our MPI
implementation of distributed gravitational N-body simulation, freely available
on GitHub, is evaluated on a cluster of 10 nodes, each with two 6-core CPUs, to
test the effectiveness and scalability of the aforementioned techniques.
