An Efficient Program for Many-Body Simulation

Andrew W. AppelSIAM Journal on Scientific and Statistical Computing 1985 · DOI

TL;DR

Andrew Appel demonstrates how a multi-layered optimization strategy—combining a tree-based $O(N \log N)$ algorithm with low-level code tuning and hardware acceleration—can reduce the runtime of cosmological simulations by a factor of 400. This approach transformed a prohibitively expensive 8,000-hour task into a manageable 20-hour run on 1980s-era hardware.

What Problem Does This Paper Address?

In astrophysics, simulating the gravitational interaction of $N$ particles (like galaxies) is a fundamental but computationally brutal task. Because gravity is a long-range force, every particle attracts every other particle, leading to a "naive" computational complexity of $O(N^2)$. For a simulation of 10,000 galaxies, this means 100 million interactions per time step.

Beyond the sheer number of calculations, these simulations suffer from "stiffness." When two particles pass very close to each other, their high velocities and the inverse-square nature of gravity require extremely tiny time steps to maintain accuracy. In a standard simulator, these few "tight" pairs force the entire global simulation to slow down to a crawl, making large-scale cosmological studies nearly impossible on mid-range computers like the VAX-11/780.

Methods

Appel’s solution is a "divide-and-conquer" strategy centered on three main pillars:

  1. The Monopole Approximation: Instead of calculating the force between every individual star in two distant galaxies, the algorithm treats distant "clumps" of particles as single point masses located at their centers of mass. This reduces the interaction complexity from $O(N^2)$ to $O(N \log N)$. The monopole approximation treats a cluster of masses as a single point source for distant observers.

  2. Hierarchical Tree Structure: The particles are organized into a binary tree (a variant of a k-d tree). Leaves represent individual particles, while internal nodes represent clumps. The algorithm recursively traverses the tree: if two nodes are far enough apart relative to their size, it computes a single interaction; if they are too close, it "breaks" the clumps and recurses deeper. Two clumps of bodies can be treated as single interactions if the distance $r$ is large enough.

  3. Dynamic Reorganization (The "Grab" Algorithm): As particles move, the tree structure becomes distorted. Appel introduced a local rearrangement heuristic called "Grab" that identifies particles that have moved closer to external neighbors than to their own siblings, keeping the tree efficient over time.

FIG. 4.1. The monopole approximation.
FIG. 4.2. Two clumps to which the approximation can be applied.

Datasets

The paper does not use external datasets. Instead, it evaluates the algorithm using a self-generated initial configuration of 10,000 galaxies with a uniform random distribution. This was used to test the "bottom-up" theory of galaxy formation, which posits that local fluctuations in a random distribution lead to the clustering we see in the universe today.

Key Insights and Ideas

  • Multiplicative Speedups: The most important takeaway is that optimizations at different levels of the "conceptual hierarchy"—from high-level physics insights down to assembly-level register management—multiply together.
  • Relative Coordinates for Precision: By storing particle positions relative to their parent clump rather than in absolute coordinates, Appel reduced round-off errors. This allowed the use of 32-bit single-precision floats (which are faster) instead of 64-bit double-precision, without losing physical accuracy.
  • Handling "Indivisible" Clumps: The algorithm identifies tightly bound systems (like binary stars) that are "indivisible" to the rest of the universe. These can be iterated internally or solved using closed-form equations, preventing them from bottlenecking the global time step.

Key Results

The combined "attacks" on the problem yielded a staggering 400-fold reduction in execution time for a 10,000-body simulation:

  • Algorithmic Change: Moving from $O(N^2)$ to $O(N \log N)$ provided a 12x speedup.
  • Implementation & Tuning: Hand-coding the inner loop in assembly and using single-precision floats provided a 5x boost.
  • Hardware: Using a Floating Point Accelerator (FPA) doubled the speed (2x).
  • Physics Insights: Efficiently handling clustering and variable time steps provided another 4x gain.

The resulting simulation successfully modeled the expansion of the universe and the formation of galaxy clusters, providing evidence for the "bottom-up" cosmological model. Initial random configuration (a) vs. clustered result after expansion (b).

Initial random configuration (a) vs. clustered result after expansion (b).

Limitations and Future Work

  • Complexity Proof: While the algorithm is empirically $O(N \log N)$, the paper notes that a formal proof of this complexity for the specific tree-traversal method was not yet established.
  • The "Grab" Heuristic: The reorganization algorithm is effective but difficult to analyze theoretically. Its performance depends on the accuracy parameter $\delta$.
  • Generalization: Appel suggests that these reorganized trees could be applied to other fields, such as computer vision (grouping point sets from camera data) or more general nearest-neighbor search problems.

Summary updated

Abstract

The simulation of N particles interacting in a gravitational force field is useful in astrophysics, but such simulations become costly for large N. Representing the universe as a tree structure with the particles at the leaves and internal nodes labeled with the centers of mass of their descendants allows several simultaneous attacks on the computation time required by the problem. These approaches range from algorithmic changes (replacing an $O(N^2 )$ algorithm with an algorithm whose time-complexity is believed to be $O(N\log N)$) to data structure modifications, code-tuning, and hardware modifications. The changes reduced the running time of a large problem $(N = 10,000)$ by a factor of four hundred. This paper describes both the particular program and the methodology underlying such speedups.
BibTeX
@article{appel1985efficient,
  author = {Andrew W. Appel},
  title = {{An Efficient Program for Many-Body Simulation}},
  journal = {SIAM Journal on Scientific and Statistical Computing},
  year = {1985},
  doi = {10.1137/0906008},
}
Figure