An FMM Based on Dual Tree Traversal for Many-core Architectures. 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. Our code -- exaFMM -- is an order of magnitude faster than the current state-of-the-art FMM codes, which are themselves an order of magnitude faster than the average FMM code.
Keywords for this software
References in zbMATH (referenced in 4 articles )
Showing results 1 to 4 of 4.
- Abduljabbar, Mustafa; Farhan, Mohammed Al; Al-Harthi, Noha; Chen, Rui; Yokota, Rio; Bagci, Hakan; Keyes, David: Extreme scale FMM-accelerated boundary integral equation solver for wave scattering (2019)
- Huang, He; Luo, Li-Shi; Li, Rui; Chen, Jie; Zhang, He: Improve the efficiency of the Cartesian tensor based fast multipole method for Coulomb interaction using the traces (2018)
- Ibeid, Huda; Yokota, Rio; Pestana, Jennifer; Keyes, David: Fast multipole preconditioners for sparse matrices arising from elliptic equations (2018)
- Yan, Wen; Shelley, Michael: Flexibly imposing periodicity in kernel independent FMM: a multipole-to-local operator approach (2018)