2022/03/16 by Alexander Brandt, Brandt, Alexander
Computer Science · Decision Sciences · #Computational Engineering #Distributed #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #Finance #Mathematical Software (cs.MS) #Parallel #Parallel Computing and Optimization Techniques #Simulation Techniques and Applications #and Cluster Computing (cs.DC) #and Science (cs.CE) #cs.CE #cs.DC #cs.MS
paper · pdf · doi:10.48550/arxiv.2203.08966
41 pages, 10 figures
arxiv created 2022/03/16 · openalex publication_date 2022/03/16 · arxiv updated 2022/03/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The N-body problem is a classic problem involving a system of N discrete bodies mutually interacting in a dynamical system. At any moment in time there are N*(N - 1)/2 such interactions occurring. This scaling as N2 leads to computational difficulties where simulations range from tens of thousands of bodies to many millions. Approximation algorithms, such as the famous Barnes-Hut algorithm, simplify the number of interactions to scale as N(log N). Even still, this improvement in complexity is insufficient to achieve the desired performance for very large simulations on computing clusters with many nodes and many cores. In this work we explore a variety of algorithmic techniques for distributed and parallel variations on the Barnes-Hut algorithm to improve parallelism and reduce inter-process communication requirements. Explicit algorithms and details are provided for reproducibility. Our MPI implementation of distributed gravitational N-body simulation, freely available on GitHub, is evaluated on a cluster of 10 nodes, each with two 6-core CPUs, to test the effectiveness and scalability of the aforementioned techniques.