论文标题
使用联合获取的混合MPI+线程粒子群查找方法
A Hybrid MPI+Threads Approach to Particle Group Finding Using Union-Find
论文作者
论文摘要
朋友（FOF）算法是一种标准技术，用于识别结构的宇宙学$ n $ body模拟。它的目标是找到最多被截止半径隔开的颗粒（称为组）的簇。 $ n $ body模拟通常使用节点上存在的大多数内存，而FOF算法几乎没有免费的免费运行。我们提出了一种新方法，该方法利用了通用的联合数据结构和混合MPI+线程方法。如果在应用程序的其余部分中使用了此类框架，则该算法也可以在基于任务的形式主义中优雅地表达。我们已经在开源宇宙准则Swift实施了算法。我们的实现在现实问题上表现出了出色的强度和弱尺度行为，并且比$ n $ body社区中常用的其他方法比较（加快18倍）。
The Friends-of-Friends (FoF) algorithm is a standard technique used in cosmological $N$-body simulations to identify structures. Its goal is to find clusters of particles (called groups) that are separated by at most a cut-off radius. $N$-body simulations typically use most of the memory present on a node, leaving very little free for a FoF algorithm to run on-the-fly. We propose a new method that utilises the common Union-Find data structure and a hybrid MPI+threads approach. The algorithm can also be expressed elegantly in a task-based formalism if such a framework is used in the rest of the application. We have implemented our algorithm in the open-source cosmological code, SWIFT. Our implementation displays excellent strong- and weak-scaling behaviour on realistic problems and compares favourably (speed-up of 18x) over other methods commonly used in the $N$-body community.
