Abstract. We present an efficient and provably good partitioning and load balancing algorithm for parallel adaptive N-body simulation. The main ingredient of our method is a novel geometric characterization of a class of communication graphs that can be used to support hierarchical N-body methods such as the fast multipole method (FMM) and the Barnes-Hut method (BH). We show that communication graphs of these methods have a good partition that can be found efficiently sequentially and in parallel. In particular, we show that an N-body communication graph (either for BH or for FMM) can be partitioned into two subgraphs with equal computation load by removing only O( √ n log n) and O(n 2/3 (log n) 1/3 ) number of nodes, respectively, for two and three dimensions. These bounds on node-partition imply bounds on edge-partition of O( √ n(log n) 3/2 ) and O(n 2/3 (log n) 4/3 ), respectively, for two and three dimensions. To the best of our knowledge, this is the first theoretical result on the quality of partitioning N-body communication graphs for nonuniformly distributed particles. Our results imply that parallel adaptive N-body simulation can be made as scalable as computation on regular grids and as efficient as parallel N-body simulation on uniformly distributed particles.
In theoretical work on load balancing hierarchical N-body applications, Teng partitions the communication graph REF and proves certain sub-types of communication graphs can be partitioned.
Provably Good Partitioning and Load Balancing Algorithms for Parallel Adaptive N-Body Simulation
SIAM J. Scientific Computing
SIAM J. Scientific Computing
Mathematics Computer Science