Scalable parallel formulations of the Barnes-Hut method for n-body simulations
Scalable parallel formulations of the Barnes-Hut method for n-body simulations
复制标题
用于 n 体模拟的 Barnes-Hut 方法的可扩展并行公式
DOI：
10.1109/superc.1994.344307
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
A. Sameh
中科院分区：
文献类型：
--
作者：
A. Grama;Vipin Kumar;A. Sameh
我们给出了Barnes-Hut方法的两个新的并行公式。这些并行公式特别适合于具有不规则粒子密度的模拟。我们首先提出了一种并行公式，它使用域的静态划分和子域的分配给处理器。我们证明了该方案提供了可接受的负载均衡，并结合两次集体通信操作，产生了良好的性能。我们提出了第二个并行公式，它结合了域的静态分解和基于Morton排序的子域到处理器的分配。这缓解了第一个方案中固有的负载不平衡。第二个并行公式的灵感来自于目前最著名的Barnes-Hut方法的两个并行算法。我们在一台256处理器的nCUBE2并行计算机上对这些方案进行了实验评估，以进行天体物理模拟。
We present two new parallel formulations of the Barnes-Hut method. These parallel formulations are especially suited for simulations with irregular particle densities. We first present a parallel formulation that uses a static partitioning of the domain and assignment of subdomains to processors. We demonstrate that this scheme delivers acceptable load balance, and coupled with two collective communication operations, it yields good performance. We present a second parallel formulation which combines static decomposition of the domain with an assignment of subdomains to processors based on Morton ordering. This alleviates the load imbalance inherent in the first scheme. The second parallel formulation is inspired by two currently best known parallel algorithms for the Barnes-Hut method. We present an experimental evaluation of these schemes on a 256 processor nCUBE2 parallel computer for an astrophysical simulation.<<ETX>>