Provably Good Partitioning and Load Balancing Algorithms for Parallel Adaptive N-Body Simulation
Shang‐Hua Teng · SIAM Journal on Scientific Computing · 1998
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(\sqrt{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(\sqrt{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.