A massively parallel, multi-disciplinary Barnes–Hut tree code for extreme-scale N-body simulations

Abstract

The efficient parallelization of fast multipole-based algorithms for the N-body problem is one of the most challenging topics in high performance scientific computing. The emergence of non-local, irregular communication patterns generated by these algorithms can easily create an insurmountable bottleneck on supercomputers with hundreds of thousands of cores. To overcome this obstacle we have developed an innovative parallelization strategy for Barnes–Hut tree codes on present and upcoming HPC multicore architectures. This scheme, based on a combined MPI–Pthreads approach, permits an efficient overlap of computation and data exchange. We highlight the capabilities of this method on the full IBM Blue Gene/P system JUGENE at Jülich Supercomputing Centre and demonstrate scaling across 294,912 cores with up to 2,048,000,000 particles. Applying our implementation pepc to laser–plasma interaction and vortex particle methods close to the continuum limit, we demonstrate its potential for ground-breaking advances in large-scale particle simulations.

Introduction

Despite rapid development in supercomputer performance over the last three decades, the N-body problem still is and will not be solved in a direct way. What makes this problem so challenging – and important as a driver for supercomputing – is the uncompromising nature of a $1/r$ force-law coupled with the need to compute $O(N^2)$ pairwise interactions for a system of N particles. Since hardware acceleration and/or parallelism can postpone, but not remove, the bottleneck implied by such an algorithmic complexity, much attention has been devoted to rapid summation techniques which reduce the computational effort to $O(N)$ or $O(N\log N)$. In molecular dynamics simulations of soft matter and plasmas, the particle–particle/particle–mesh (P3M) method and variations thereof have traditionally been deployed to model periodic systems dominated by Coulomb interactions: most recently the ddcMD code was successfully scaled across the entire 294,912-core BlueGene/P at Jülich Supercomputing Centre (JSC) [1].

While a mesh-based approach is suited to broadly homogeneous systems with periodic boundaries, it is less appropriate for geometrically complex N-body problems exhibiting a high dynamic range in their density distribution, as found, for example in astro- or plasma physics. For these applications, mesh-free multipole techniques based on either the Barnes–Hut (BH) tree algorithm [2] or the Fast Multipole Method (FMM) [3] are preferable. Both of these methods rely on a hierarchical oct-tree data structure to store local multipole expansions of the particle charge or mass distribution. Since this additional information typically consumes more memory than the particles themselves, sharing it among many processors makes parallel scaling of the complete force summation a notoriously difficult task.

In this paper we present a new, highly scalable implementation of the Barnes–Hut tree algorithm: we note in passing that parallel versions of the FMM have also been reported recently, scaling to 64k [4] and 288k [5] cores respectively. An important caveat of these works is that the benchmarks were performed for static systems in which the domain decomposition could be adjusted a priori to ensure load balancing. Despite theoretical work which suggests load balancing can be generally achieved [6], this has yet to be demonstrated in a highly dynamic, inhomogeneous simulation using FMM.

By contrast, several groups including JSC staff have demonstrated load-balanced BH tree codes for electrostatics [7], astrophysics [8], and fluid dynamics applications [9]. Our own persistence with the BH algorithm owes more to the fact that the code can easily be adapted to new problems by exchanging the interaction kernel, a feature which has led to the rapid establishment of a whole family of codes at JSC.

Since the seminal work by Warren and Salmon [10], there have been many efforts made to parallelize the BH tree algorithm with varying degrees of success. A flurry of early attempts [11], [12], [13], [14] reported scaling to at most a few hundred processors, limited mainly by the machine size available during the late ʼ90s. With the explosion in core numbers seen in Petascale machines over the last five years, the demands on tree algorithms in terms of memory footprint and load balance have been stretched to the point where a complete redesign is necessary to scale beyond a few thousand cores.

One way around this bottleneck is to use GPGPU accelerators, as demonstrated to great effect by Hamada et al. [15]. While this approach offers an attractive short-term solution, it still begs the question of whether tree codes are in principle suited to future exascale architectures with millions of cores. The best-scaling BH tree code prior to the present work stands at around 8k cores [7], [8], [16]. Here we present an new load-balanced, hybrid MPI–Pthread algorithm which makes effective use of all 288k cores of JUGENE, and which is also well placed to take advantage of multicore architectures coming online within the next few years.

The paper is organized as follows: in Section 2, the hybrid tree algorithm is described with particular attention to the tree traversal routine, where bottlenecks are typically found in other implementations. Section 3 contains detailed performance and scalability analyses of the communication-intensive parts of the code. Finally, examples of two applications currently being pursued in the Jülich and Lugano groups are discussed in which major qualitative progress can be expected by exploiting the huge improvements in statistical fidelity afforded by our new algorithm.