An FMM Based on Dual Tree Traversal for Many-Core Architectures

Rio Yokota

This paper, published in 2012, presents a highly optimized Fast Multipole Method (FMM) library called exaFMM, designed specifically to exploit the architecture of modern many-core CPUs. By combining algorithmic flexibility from "treecodes" with the computational efficiency of FMM and low-level SIMD optimizations, the author demonstrates performance that significantly outpaces existing state-of-the-art N-body solvers.

TL;DR

The paper introduces an FMM implementation that uses dual tree traversal and task-based parallelism to achieve massive speedups on many-core CPUs. By prioritizing "compute-bound" kernels and low-level SIMD (AVX) optimizations, the author creates a library that is both an order of magnitude faster and significantly smaller than its predecessors.

What Problem Does This Paper Address?

The central challenge is the widening "memory wall" in computer architecture: the ratio of memory bandwidth to computational power (Byte/flop) is plummeting. Modern processors can perform arithmetic much faster than they can move data from memory.

Traditional algorithms like the Fast Fourier Transform (FFT) or sparse linear solvers are often memory-bound, meaning they spend most of their time waiting for data. The Fast Multipole Method (FMM) is a promising alternative because it is "compute-bound"—it performs many operations on a small amount of data. However, standard FMM implementations often lack the flexibility to handle highly non-uniform particle distributions efficiently or fail to fully utilize the SIMD (Single Instruction, Multiple Data) units on modern CPUs.

Methods

The author integrates several high-performance computing (HPC) techniques into a unified framework:

  • Dual Tree Traversal (DTT): Unlike standard FMM which uses rigid arrays and Morton keys, DTT traverses target and source trees simultaneously. This inherits the flexibility of "treecodes" (allowing for rectangular cells and adjustable opening angles) while maintaining the $O(N)$ complexity of FMM.
  • Cartesian Taylor Expansions: While spherical harmonics are mathematically more elegant for high accuracy, the author argues that Cartesian Taylor expansions are better for low-accuracy optimizations on modern hardware because they are more arithmetic-intensive and map better to SIMD units.
  • Task-Based Threading: To maximize parallelism on many-core chips, the code moves away from simple "for" loops. It uses a task-based model (via Intel TBB or OpenMP 3.0) to dynamically balance the load across cores, which is essential for the irregular workloads generated by tree traversals.
  • Low-Level SIMD Optimization: The inner kernels are manually optimized using AVX and SSE intrinsics, including the use of rsqrt_ps for fast reciprocal square root calculations.

Datasets

The primary evaluation uses:

  • Synthetic Benchmarks: Randomly distributed particles in a cube, with $N$ ranging from $10^4$ to $10^6$.
  • Comparative Datasets: The paper references six different datasets with varying levels of non-uniformity (from previous studies) to validate the algorithm's robustness across different physical distributions.

Key Insights and Ideas

  • The "Off-Balance" Architecture: The author highlights that as Byte/flop ratios fall below 0.2, we must rethink our algorithms. FMM is "future-proof" because its high arithmetic intensity thrives where memory-bound algorithms fail.
  • Complexity vs. Constant: A major "aha" moment is the comparison between Cartesian Taylor and spherical harmonics. Even though Cartesian expansions have higher theoretical complexity ($O(p^6)$ vs $O(p^3)$), for low accuracy (small $p$), the Cartesian version is actually faster because it avoids the complex pre-computations and irregular memory access of spherical harmonics.
  • Hybridization is Key: By treating the "treecode" and "FMM" communities as independent efforts that need integration, the author shows that the flexibility of tree-based logic combined with the $O(N)$ scaling of FMM provides the best of both worlds.

Key Results

  • SIMD Speedup: The use of AVX intrinsics provided a $6.59\times$ speedup over non-SIMD code on a Sandy Bridge processor.
  • Peak Performance: The Laplace P2P kernel achieved 321 Gflop/s on a single CPU socket, nearing the theoretical peak of the hardware.
  • State-of-the-Art Comparison: In a benchmark against four other major codes (KIFMM, falcON, ufmmlap, and PEPC), exaFMM was consistently the fastest, often by an order of magnitude, especially at the 3-digit accuracy level required for use as a preconditioner.
  • Code Efficiency: The author notes that exaFMM is not only faster but also "an order of magnitude smaller in terms of lines of code" compared to the other benchmarked libraries.

Limitations and Future Work

  • Accuracy Range: The optimizations heavily favor low-to-medium accuracy (around 3-5 digits). Applications requiring extremely high precision might still find spherical harmonics or other expansions more efficient.
  • Single-Node Focus: While MPI support is mentioned, the bulk of the paper focuses on single-node, many-core optimization. The author notes that load-balancing adaptive global trees across multiple nodes remains a significant challenge for future work.
  • Expansion Comparison: The author acknowledges that Figure 1 (comparing expansion times) is incomplete and plans to include more expansion types in future publications to provide a more exhaustive guide for the community.

Summary updated

Abstract

The present work attempts to integrate the independent efforts in the fast N-body community to create the fastest N-body library for many-core and heterogenous architectures. Focus is placed on low accuracy optimizations, in response to the recent interest to use FMM as a preconditioner for sparse linear solvers. A direct comparison with other state-of-the-art fast N-body codes demonstrates that orders of magnitude increase in performance can be achieved by careful selection of the optimal algorithm and low-level optimization of the code. The current N-body solver uses a fast multipole method with an efficient strategy for finding the list of cell-cell interactions by a dual tree traversal. A task-based threading model is used to maximize thread-level parallelism and intra-node load-balancing. In order to extract the full potential of the SIMD units on the latest CPUs, the inner kernels are optimized using AVX instructions.
BibTeX
@article{yokota2013fmm,
  author = {Rio Yokota},
  title = {{An FMM Based on Dual Tree Traversal for Many-Core Architectures}},
  journal = {Journal of Algorithms \& Computational Technology},
  year = {2013},
  doi = {10.1260/1748-3018.7.3.301},
}

Loading related content...

Figure