Communication Reducing Algorithms for Distributed Hierarchical N-Body Problems with Boundary Distributions

Abstract

Reduction of communication and efficient partitioning are key issues for achieving scalability in hierarchical $N$-Body algorithms like FMM. In the present work, we propose four independent strategies to improve partitioning and reduce communication. First of all, we show that the conventional wisdom of using space-filling curve partitioning may not work well for boundary integral problems, which constitute about 50% of FMM's application user base. We propose an alternative method which modifies orthogonal recursive bisection to solve the cell-partition misalignment that has kept it from scaling previously. Secondly, we optimize the granularity of communication to find the optimal balance between a bulk-synchronous collective communication of the local essential tree and an RDMA per task per cell. Finally, we take the dynamic sparse data exchange proposed by Hoefler et al. and extend it to a hierarchical sparse data exchange, which is demonstrated at scale to be faster than the MPI library's MPI_Alltoallv that is commonly used.

arXiv commentarXiv admin note: text overlap with arXiv:1405.7487

References in corpus (7)

• An energy-conserving formalism for adaptive gravitational force softening in SPH and N-body codes
• A sparse octree gravitational N-body code that runs entirely on the GPU processor
• A Parallel Tree Code
• Biomolecular electrostatics using a fast multipole BEM on up to 512 GPUs and a billion unknowns
• 24.77 Pflops on a Gravitational Tree-Code to Simulate the Milky Way Galaxy with 18600 GPUs
• An inventory of three-dimensional Hilbert space-filling curves
• Asynchronous Execution of the Fast Multipole Method Using Charm++

Cited by in corpus (2)

• Stop talking to me -- a communication-avoiding ADER-DG realisation
• Extreme Scale FMM-Accelerated Boundary Integral Equation Solver for Wave Scattering