论文标题
在分布式重力N体型模拟上
On Distributed Gravitational N-Body Simulations
论文作者
论文摘要
N体问题是一个经典的问题，涉及在动态系统中相互相互作用的N离散物体系统。在任何时候，都会发生n*（n -1）/2这样的相互作用。这种缩放为n^2导致计算困难，其中模拟范围从成千上万的尸体到数百万。近似算法（例如著名的Barnes-HUT算法）简化了相互作用的数量，以扩展为n（log n）。即便如此，这种复杂性的提高不足以实现具有许多节点和许多核心计算簇的非常大的模拟所需的性能。在这项工作中，我们探讨了Barnes-Hut算法的分布式和并行变化的各种算法技术，以改善并行性并减少过程间的通信要求。提供明确的算法和详细信息，以供重复可再现。我们在GITHUB上免费获得的分布式重力N体模拟的MPI实现在10个节点的群集上评估，每个节点具有两个6核CPU，以测试上述技术的有效性和可扩展性。
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 N^2 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.
