Petascale turbulence simulation using a highly parallel fast multipole method

Rio Yokota, Tetsu Narumi, Lorena A. Barba, Kenji YasuokaarXiv 2011 · arXiv · OpenReview

TL;DR

This paper presents a groundbreaking petascale simulation of turbulent fluid dynamics, achieving 1.08 petaflops on GPUs using a Fast Multipole Method (FMM) with a vortex particle approach. This method demonstrates significantly better scalability than traditional spectral methods on modern supercomputing architectures, paving the way for larger and more detailed simulations of complex fluid phenomena.

What Problem Does This Paper Address?

Simulating turbulent fluid dynamics at high resolutions (Direct Numerical Simulation or DNS) is crucial for understanding phenomena ranging from weather patterns to blood flow. Historically, the dominant approach for this has been the pseudo-spectral method, which relies on the Fast Fourier Transform (FFT) algorithm. While effective, the FFT's inherent all-to-all communication pattern severely limits its scalability on modern supercomputers, which feature an ever-increasing number of processing cores. This bottleneck prevents researchers from fully leveraging the power of these machines for DNS. The authors aim to demonstrate that an alternative approach, using a Fast Multipole Method (FMM) with a vortex particle solver, can overcome this scalability limitation and achieve petascale performance.

Methods

The core of this work lies in the combination of two key techniques:

  • Vortex Particle Method: Instead of discretizing space onto a grid (as in spectral methods), this approach represents the fluid's vorticity using discrete particles. The Navier-Stokes equations are then solved by tracking the interactions between these particles. This method is particularly well-suited for capturing the complex, localized interactions characteristic of turbulence.
  • Fast Multipole Method (FMM): The vortex particle method, when solved directly, leads to an N-body problem with O(N²) complexity. The FMM is a hierarchical algorithm that reduces this complexity to O(N) by efficiently approximating the interactions between distant particles using multipole expansions. This is crucial for handling the massive number of particles (up to 69 billion in this study).

The authors developed a highly parallel FMM library called exaFMM specifically for GPUs. They also employed advanced parallelization strategies like orthogonal recursive bisection (ORB) for domain partitioning and a dual tree traversal to manage cell-cell interactions efficiently, even with non-cubic cells. For periodic boundary conditions, they extended the FMM by including periodic images of the domain.

Datasets

The paper does not introduce new benchmark datasets. Instead, it uses a standard initial condition for homogeneous isotropic turbulence, generated by the hit3d spectral code developed at Stanford University. The validation of the vortex method's accuracy was performed by comparing its results against this trusted spectral code.

Key Insights and Ideas

  • GPU Acceleration is Key for FMM Scalability: While FMM has been around for a while, its true potential for large-scale simulations is unlocked by GPU acceleration. The high arithmetic intensity of FMM kernels, combined with the massive parallelism of GPUs, makes it a strong contender for exascale computing.
  • FMM's Scalability Advantage Over FFT: The paper starkly contrasts the weak scaling performance of their FMM-based vortex method with a traditional FFT-based spectral method. The FMM achieved a remarkable 74% parallel efficiency on 4096 GPUs, while the spectral method only reached 14% on the same number of CPU cores. This highlights the critical bottleneck of FFT's communication patterns on modern hardware.
  • Petascale Turbulence Simulation is Achieved: The work successfully demonstrates a sustained performance of 1.08 petaflops, marking a significant milestone in simulating turbulent fluid dynamics at unprecedented scales.
  • Vortex Method Validation: The authors provide strong evidence that their FMM-based vortex method accurately reproduces turbulence statistics, matching the kinetic energy spectrum of a well-established spectral code. This addresses a historical concern about the reliability of vortex methods for DNS.

Key Results

  • Performance: Achieved a sustained performance of 1.08 petaflops (single precision) on 4096 GPUs.
  • Scale: Simulated homogeneous isotropic turbulence with up to 69 billion particles, an order of magnitude larger than previous vortex-method calculations.
  • Scalability: Demonstrated 74% parallel efficiency for the FMM-based vortex method when scaling from 1 to 4096 processes (GPUs). In contrast, the spectral method achieved only 14% parallel efficiency on CPUs.
  • Time Step: A single time step took 108 seconds for the vortex method and 154 seconds for the spectral method at the largest scale.
  • Accuracy: The kinetic energy spectrum from the FMM-based vortex method quantitatively matched that of a trusted spectral method.
  • Mesh Size: Matched the current record for mesh size in isotropic turbulence DNS (4096³ points).

Limitations and Future Work

  • Single Precision: The FMM kernels were run in single precision on the GPU. While the authors describe techniques to maintain double-precision accuracy, this is a potential area for further investigation.
  • Vortex Method Inefficiency for Turbulence: The authors acknowledge that vortex methods may still be comparatively inefficient for simulating fluid turbulence compared to spectral methods, though they emphasize that this does not detract from the FMM's efficiency.
  • Future Work: The authors plan to explore using FMM as a Poisson solver or preconditioner for more standard finite difference/volume/element methods. They also aim to investigate the FMM's advantages over multigrid methods in terms of synchronization patterns and its potential for reducing communication overhead in exascale computing.

Summary updated

Abstract

This paper reports large-scale direct numerical simulations of homogeneous-isotropic fluid turbulence, achieving sustained performance of 1.08 petaflop/s on gpu hardware using single precision. The simulations use a vortex particle method to solve the Navier-Stokes equations, with a highly parallel fast multipole method (FMM) as numerical engine, and match the current record in mesh size for this application, a cube of 4096^3 computational points solved with a spectral method. The standard numerical approach used in this field is the pseudo-spectral method, relying on the FFT algorithm as numerical engine. The particle-based simulations presented in this paper quantitatively match the kinetic energy spectrum obtained with a pseudo-spectral method, using a trusted code. In terms of parallel performance, weak scaling results show the fmm-based vortex method achieving 74% parallel efficiency on 4096 processes (one gpu per mpi process, 3 gpus per node of the TSUBAME-2.0 system). The FFT-based spectral method is able to achieve just 14% parallel efficiency on the same number of mpi processes (using only cpu cores), due to the all-to-all communication pattern of the FFT algorithm. The calculation time for one time step was 108 seconds for the vortex method and 154 seconds for the spectral method, under these conditions. Computing with 69 billion particles, this work exceeds by an order of magnitude the largest vortex method calculations to date.
BibTeX
@misc{yokota2011petascale,
  author = {Rio Yokota and Tetsu Narumi and Lorena A. Barba and Kenji Yasuoka},
  title = {{Petascale turbulence simulation using a highly parallel fast multipole method}},
  year = {2011},
  eprint = {1106.5273},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1106.5273},
}
Figure