Fast N-body Simulations on GPUs

Rio Yokota, Lorena A. BarbaarXiv 2011 · arXiv · OpenReview

Abstract

With the current hybridization of treecodes and FMMs, combined with auto-tuning capabilities on heterogeneous architectures, the flexibility of fast N-body methods has been greatly enhanced. These features are a requirement to developing a black-box software library for fast N-body algorithms on heterogeneous systems, which is our immediate goal.

Introduction

The "N-body problem"—calculating the interactions between $N$ particles—is a fundamental challenge in computational physics, essential for fields ranging from astrophysics to molecular biology. While brute-force calculations scale at $O(N^2)$, approximation algorithms like treecodes ($O(N \log N)$) and the Fast Multipole Method (FMM, $O(N)$) have made large-scale simulations feasible. However, these algorithms are highly sensitive to hardware architecture. An implementation optimized for a CPU may perform poorly on a GPU, and optimal parameters often depend on the specific hardware and required accuracy. This paper addresses these challenges by presenting a hybrid, auto-tuning N-body algorithm designed for massive scalability on GPU clusters.

Methodology: Hybrid Treecode-FMM with Auto-Tuning

The core of the proposed approach is a hybrid algorithm that merges the strengths of treecodes and FMM, enhanced by an automated tuning mechanism.

Dual Tree Traversal

Unlike traditional methods with rigid interaction lists, this algorithm employs a stack-based dual tree traversal. It simultaneously traverses a "target" tree and a "source" tree, allowing for adaptive interactions between cells of varying sizes. This flexibility is crucial for handling non-uniform particle distributions efficiently.

Dual tree traversal mechanism for hybrid N-body interactions

Auto-Tuning and Kernel Selection

The algorithm can dynamically select between cell-cell, cell-particle, and particle-particle interaction kernels. The auto-tuner performs a "pre-calculation" phase at runtime, executing small tests with synthetic data to measure kernel performance on the specific hardware. It then selects the fastest combination of kernels for the actual simulation, effectively removing the need for manual parameter tweaking.

Experimental Setup

The algorithm's performance was evaluated using various synthetic particle distributions:

  • Cube Distribution: Randomly placed particles in a 3D cube (up to $10^7$ particles).
  • Spherical Shell: Particles on a sphere's surface to test performance with highly non-uniform distributions.

Benchmarks were conducted on the TSUBAME 2.0 supercomputer, utilizing up to 2,048 NVIDIA M2050 GPUs.

Discussion: The Roofline Advantage and GPU Trade-offs

N-body algorithms possess high operational intensity—performing many floating-point operations per byte of data moved. This characteristic makes them ideal for GPUs, which offer high arithmetic throughput but are often limited by memory bandwidth.

Interestingly, the auto-tuner reveals significant differences between CPU and GPU optimization. While FMM is typically faster on CPUs, the massive parallel processing power of GPUs often makes "brute force" particle-particle interactions more efficient. The auto-tuner frequently opts for more direct calculations to avoid the overhead associated with complex tree logic, effectively adapting the algorithm to the many-core architecture.

Performance Results

The hybrid algorithm demonstrated exceptional scalability and throughput. On 2,048 GPUs, it achieved a sustained performance of 0.5 petaflop/s, with peak performance reaching 2.4 petaflop/s.

Execution time breakdown across increasing GPU counts

As shown in the performance breakdown, the system maintains high parallel efficiency (approximately 72% in weak scaling tests) as the number of GPUs increases. For a single-GPU simulation with $10^7$ particles, the code completes potential and force calculations in roughly 23 seconds.

Conclusion and Future Work

The authors have successfully developed a scalable, "black-box" N-body library (exafmm) that leverages auto-tuning to achieve high performance on heterogeneous systems. Future work will focus on expanding expansion types (e.g., Cartesian expansions for lower accuracy needs) and developing more sophisticated load-balancing strategies to fully utilize both CPUs and GPUs in truly heterogeneous environments.

Summary updated

Abstract

With the current hybridization of treecodes and FMMs, combined with auto-tuning capabilities on heterogeneous architectures, the flexibility of fast N-body methods has been greatly enhanced. These features are a requirement to developing a black-box software library for fast N-body algorithms on heterogeneous systems, which is our immediate goal.
BibTeX
@misc{yokota2011fast,
  author = {Rio Yokota and Lorena A. Barba},
  title = {{Fast N-body Simulations on GPUs}},
  year = {2011},
  eprint = {1108.5815},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1108.5815},
}
Figure