Low-Cost Parallel Algorithms for 2:1 Octree Balance
Low-Cost Parallel Algorithms for 2:1 Octree Balance
复制标题
2:1 八叉树平衡的低成本并行算法
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
O. Ghattas
中科院分区：
文献类型：
--
作者：
T. Isaac;Carsten Burstedde;O. Ghattas
八叉树森林的逻辑结构可用于创建并行自适应网格细化（AMR）的可扩展算法，该算法最近已在几个千兆级应用程序中得到验证。在各种经常使用的基于八叉树的网格操作（包括细化、粗化、分区和枚举节点）中，确保相邻元素之间2:1的大小平衡在CPU时间和通信量方面是最昂贵的。因此，2:1平衡操作是优化的主要目标。并行平衡算法的一个重要组成部分是确定任意两个给定的八分位数是否具有一致的距离/大小关系的能力。基于新的逻辑概念，我们提出了快速算法，用于在2D和3D中为所有类型的2:1平衡条件做出此决策。由于我们无需在树中构造任何需要排序和通信的父节点就可以实现这一点，因此我们可以显著减少所需的内存和通信量。此外，我们提出了一种轻量级的集体算法来逆转由非局部八分域相互作用引起的不对称通信模式。我们已经将我们的改进作为开源“p4est”软件的一部分实现了。将此代码与合成和模拟驱动的自适应网格进行基准测试，我们能够展示大大减少的运行时间以及出色的弱和强可伸缩性。在我们最大的5.13 × 1011八分位数的基准测试问题上，新的2:1平衡算法在捷豹Cray XT5超级计算机的112,128个CPU内核上执行不到8秒。
The logical structure of a forest of octrees can be used to create scalable algorithms for parallel adaptive mesh refinement (AMR), which has recently been demonstrated for several petascale applications. Among various frequently used octree-based mesh operations, including refinement, coarsening, partitioning, and enumerating nodes, ensuring a 2:1 size balance between neighboring elements has historically been the most expensive in terms of CPU time and communication volume. The 2:1 balance operation is thus a primary target to optimize. One important component of a parallel balance algorithm is the ability to determine whether any two given octants have a consistent distance/size relation. Based on new logical concepts we propose fast algorithms for making this decision for all types of 2:1 balance conditions in 2D and 3D. Since we are able to achieve this without constructing any parent nodes in the tree that would otherwise need to be sorted and communicated, we can significantly reduce the required memory and communication volume. In addition, we propose a lightweight collective algorithm for reversing the asymmetric communication pattern induced by non-local octant interactions. We have implemented our improvements as part of the opensource “p4est” software. Benchmarking this code with both synthetic and simulation-driven adapted meshes we are able to demonstrate much reduced runtime and excellent weak and strong scalability. On our largest benchmark problem with 5.13 × 1011 octants the new 2:1 balance algorithm executes in less than 8 seconds on 112,128 CPU cores of the Jaguar Cray XT5 supercomputer.