MiniAMR一种用于自适应网格的小型应用程序外文翻译资料

MiniAMR - A miniapp for Adaptive Mesh

Re nement

Aparna Sasidharan

University of Illinois at Urbana-Champaign

sasidha2@illinois.edu

Marc Snir

Argonne National LaboratoryChicago,IL

and University of Illinois at Urbana-Champaign

snir@illinois.edu

August 4, 2016

Abstract：We present a new implementation of MiniAMR, a miniapp for adap-tive mesh re nement (AMR) that mimics commonly found workloads and communication patterns in AMR applications. We obtain signi cant per-formance improvements by using new data structures and algorithms. One of our important areas of focus in this work is the use of low-overhead dis-tributed load balancing schemes for octree partitioning. We evaluate this new implementation by comparing its performance to that of the Mini-AMR code in the Mantevo suite of miniapplications for three realistic test cases. In addition, the new code supports re nement in time (sub-cycling).

Introduction

Adaptive Mesh Re nement is a frequently used technique for e ciently solving partial di erential equations (PDEs): A ner mesh is used in regions that require a higher resolution (e.g., because of turbulence), and a coarse mesh is used to cover less sensitive regions. This reduces both computation and storage, compared to a mesh with uniform resolution. Since the regions requiring a ner mesh may vary during the course of a simulation, the mesh is adaptively re ned or coarsened to re ect these changes. This a ects the amount of computation done by each processor; over time, it becomes necessary to re-partition the mesh across processors.

A good partition minimizes the amount of communication between processes and balances their computational load, thus reducing execution time. This has to be balanced against the overhead of computing the partition, migrating data and re-constructing the distributed data structures that are used by the application. Many AMR frameworks use Space lling curves (SFC) for mesh partitioning, as they achieve a good compromise between these con icting goals.

We focus in this paper on octree-based AMR [18, 25, 23, 19, 1, 21, 5]. Our paper makes the following contributions:

We present an improved linearized data structure for representing octrees. We also describe a low-overhead re nement and coarsening algorithm for octree based AMR.

We propose an amortized load balancing scheme that lowers the total execution time by reducing the frequency of re-partitioning.

We provide a low-overhead distributed weighted slicing algorithm for SFC that can be used for load balancing AMR applications which use sub-cycling.

These changes do not a ect the numerical properties of the algorithms in any way, but only change their performance.

We evaluate the improvements by using the miniAMR benchmark in the Mantevo benchmark suite [10]. We compare the performance of the miniAMR-code in Mantevo to our new code, for three realistic test cases, using the same SFC (Morton order) for both. With the improved data structure and algorithms we could reduce the re nement time of MiniAMR by more than half. The com-putation time of the kernel also showed signi cant improvement by almost 1:8X. Amortized load balancing was able to improve the running time of the simu-lation by a maximum of 3X for one of the test cases. We obtained signi cant performance improvements for the test cases with sub-cycling. The weighted slicing algorithm was able to reduce the execution time of the simulation by a maximum of 3X. In addition to performance improvements, our code is more general as it provides support for sub-cycling.

The remainder of the report is organized as follows:

We discuss octree-based AMR in the next section; it also includes a short ex-planation of parallel octree partitioning using Morton order. Section 2 describes the performance model that we used for measuring execution time. Section 3 describes in detail the improvements we made to the Mantevo miniAMR code. Section 4 contains our experimental results. We nish with a short survey of related work in Section 5 and a brief conclusion.

1.1 Adaptive Mesh Re nement (AMR)

While many of our techniques generalize to other mesh-based algorithms, we shall focus in this work on octree-based AMR. Results for other AMR variants will be quantitatively di erent but we expect them to show improvements as well.

The miniAMR mini-app from the Mantevo suite is a compact proxy for octree-based AMR. It exhibits computation and communication patterns that are typical of the application while being shorn of many of the details of a full application. MiniAMR uses 3D meshes with an octree structure: contiguous mesh cells are grouped into cubic blocks, the granularity of which can be decided by the user. Each block has a halo region de ned around its mesh cells, which is used for exchanging boundary information with neighboring blocks. If a block needs to be re ned, then it is split into 8 cubic sub-blocks; if blocks are coarsened, then the 8 adjacent sub-blocks are replaced by the original parent block. The re nement preserves a 2:1 balance condition: The re nement levels of adjacent blocks di er by at most one. The mini-app uses a 7-point stencil so that any two blocks are neighbors if they share a face. Computation typically involves only the leaves of the octree. Our mini-app also models applications which perform sub-cycling.

<t

剩余内容已隐藏，支付完成后下载完整资料</t

MiniAMR一种用于自适应网格的小型应用程序

阿帕纳·萨西达兰 马克

阿贡国家 伊利诺伊大学厄巴纳香槟分校

8月 4日, 2016

摘要：我们介绍了MiniAMR的一个新的实现，它是一种小型应用程序，用于模拟AMR应用程序中常见的工作负载和通信模式。我们得到的信号通过使用新的数据结构和算法来改进。我们在这项工作中重点关注的一个重要领域是使用低开销的dis分配负载平衡方案进行八叉树分区。g.我们评估这一新的实现，通过比较它的性能与Mini-AMR代码在Mantevo套件的微型应用程序的三个现实的测试用例。此外，新代码支持及时更新(分自行车)。

引言

自适应网格重建是一种常用的技术，用于科学地求解部分二次方程(PDE)：在需要较高分辨率的区域(例如，由于Turb)，使用了新网格。可能），和一个粗网格是用来掩盖不敏感地区。与具有均匀分辨率的网格相比，这减少了计算和存储。由于需要NER网格的区域可以VA在模拟过程中，网格被自适应地重新调整或粗化以重新考虑这些变化。这是每个处理器所完成的计算量；随着时间的推移，它变得必要了。在处理器之间重新划分网格。

一个好的分区最小化进程之间的通信量并平衡它们的计算负载，从而减少执行时间。这必须与计算开销相平衡。分区，迁移数据和重构应用程序使用的分布式数据结构。许多AMR框架使用空间lling曲线进行网格划分，因为它们实现了一个很好的折衷方案。在这些目标之间。

1. 我们提出了一个改进的线性化数据结构来表示八叉树。我们还描述了基于八叉树的AMR的低开销接收和粗化算法。

2.我们提出一种分期平衡的负载均衡方案，通过减少重新分区的频率来降低​​总执行时间。

3.我们为SFC提供低开销的分布式加权分片算法，可用于使用子循环的负载均衡AMR应用。

这些更改不会以任何方式影响算法的数字属性，而只会改变其性能。

我们通过在Mantevo基准测试套件中使用miniAMR基准来评估改进[10]。我们将Mantevo中的miniAMR代码的性能与我们的新代码进行比较，对于三个实际的测试用例，两者都使用相同的SFC（Morton顺序）。随着数据结构和算法的改进，我们可以将MiniAMR的运行时间缩短一半以上。核心的计算时间也显示出显着的提高了近1倍：8倍。对于其中一个测试用例，摊销负载平衡可以将模拟的运行时间最多提高3倍。我们获得了次循环测试案例的显着性能改进。加权切片算法能够将模拟的执行时间减少最多3倍。除了性能改进之外，我们的代码更加通用，因为它提供了对次循环的支持。

报告的其余部分安排如下：

我们在下一节讨论基于八叉树的AMR;它还包括使用Morton命令进行并行八叉树分割的简短前期规划。第2节描述了我们用来衡量执行时间的性能模型。第3节详细介绍了我们对Mantevo miniAMR代码的改进。第4节包含我们的实验结果。我们在第5部分对相关工作进行了简短的调查并作了简短的总结。

1.1自适应网格（AMR）

虽然我们的许多技术都推广到其他基于网格的算法，但我们应该将重点放在基于八叉树的AMR上。其他AMR变体的结果将在数量上不同，但我们预计它们也会有所改进。

Mantevo套件中的miniAMR迷你应用程序是基于八叉树的AMR的紧凑代理。它展示了计算和通信模式是典型的应用程序，同时对整个应用程序的许多细节进行了删减。 MiniAMR使用八叉树结构的三维网格：连续的网格单元被分组为立方块，其粒度可以由用户决定。每个块在其网格单元周围都有一个晕圈区域，用于与相邻块交换边界信息。如果一个块需要被重新定义，那么它被分成8个立方的子块;如果块粗化，则8个相邻的子块被原始父块替换。接头保持2：1平衡状态：相邻块的接近程度最多不超过一个。迷你应用程序使用7点模板，以便任何两个块如果共享一张脸就是邻居。计算通常只涉及八叉树的叶子。我们的迷你应用程序还可以模拟执行次循环的应用程序。

图 1

在抽象层次上，网格数据结构是一个动态的八叉树森林，其中森林的根是网格的初始粗块。在我们的讨论中，八叉树节点等同于之前定义的网格块。我们将互换使用这些术语。这个数据结构应该支持以下操作：

继续：创建8个节点作为前一个叶节点的子节点。

粗化：8个兄弟节点被删除，其父节点成为叶节点。

图1a和1b提供了一个自适应网格的例子，该网格满足2：1平衡准则及其2D中的相应四叉树。对于并行计算，八叉树数据结构分布在计算节点中。分配应平衡每个节点执行的计算量，同时减少通信。基于八叉树的AMR的主要通信开销如下：平衡：连接和粗化操作必须保持2：1的平衡状态。节点的更新可能会触发更多改善粗糙的邻居。类似地，一组节点的粗化可能导致邻近组的粗化。两种操作都需要节点与其邻居之间的通信。更新块晕圈区域：在模拟的每个时间步中，阻止与它们的邻居交换边界数据。涉及的通信取决于所使用的有限差分方案的类型。在最简单的情况下，仿真仅在八叉树的叶节点处进行。在这种情况下，只有叶块执行边界交换。如果内核也及时执行修复，则相邻块之间的晕轮交换速率取决于它们的相对修正水平。每种内核类型的开销是不同的。但是所有的变体都没有受到负载均衡且具有良好局部性的八叉树网格的域分解，即相邻块大多存储在同一节点上。

通常情况下，并行八叉树网格框架从跨过程的八叉树节点的初始分区开始，并通过在仿真过程中对树节点进行缩放和粗化来自适应地修改它。这可能导致负载不平衡并且在平衡和光环交换期间通信恶化的分区。因此，八叉树需要定期重新分区。这包括计算新分区，迁移数据和重新建立光环交换所需的信息。空间曲线广泛用于对自适应网格进行分区。 SFC用于创建网格块（树叶）的线性有序列表，然后以负载均衡的方式在参与进程中分布。我们还保持内部块与其子节点存储在同一节点上的不变性。

1.2八叉树分区

SFC可用于划分直线网格：每个网格单元由一个点表示，通常位于其重心处。曲线是使用点的空间坐标生成的。单调映射函数用于将空间坐标转换为唯一键。函数生成的键值应该保持曲线的遍历顺序。然后通过将密钥集划分为p个分段，每个分段包含大致相同的点数，将这些点分割成p个子集，从而确保负载均衡。分区具有良好的局部性，因此，如果计算需要相邻网格单元之间的通信，则它们将具有低通信。离散k维空间填充曲线（SFC）是一种双射映射C：f1：：：Nkg！对于所有0 lt;i lt;Nk，其中d是欧几里德距离[9]，f1：：：Ngk使得d（C（i）; C（i 1））= 1。我们根据要求确定良好的地点即任何k个连续点C（i）; ：：：; SFC上的C（i k 1）包含在维度为O（k1 = m）的超立方体中，其中m是任何非零整数。一些流行的SFC包括Hilbert，Peano和Sierpinski [20]。尽管莫顿order [2]没有纳入上述定义，由于其易于计算而被广泛使用。 Morton阶的映射函数是点的空间坐标的简单比特交织。

在这个讨论中，我们使用莫顿顺序来进行所有的实验。我们目前正在用MiniAMR中具有更好位置的SFC取代Morton订单。对于自适应八叉树网格，我们避免在八叉树被修改或粗化时从头开始重新计算SFC。要做到这一点，当一个带有键`的块被重新定义时，在SFC上由8个带有按照曲线遍历顺序（本例中为Morton顺序）标记的xyz子元素替换。当8个兄弟模块变粗时，粗粒模块（父）替换SFC上的一个子模块，其他子模块将被删除。对于Morton命令，由于8个兄弟姐妹在SFC上是连续的，所以他们有二进制密钥xyz，粗块被重新标记为;键的字典顺序被保留。此外，每个进程可以独立并行执行这些更新，针对它拥有的块。

1.2.1 排序

为了重新分区，我们需要计算SFC上任意点（叶节点）的（加权）索引。当一个节点被修改时，它的子节点被存储在与父节点相同的进程中;当节点粗化时，父节点已经存储在与其中一个子节点相同的进程中。因此，接近和粗化操作保持不变，即存储在过程Pi中的所有节点都具有按照字典顺序严格小于在过程Pi 1处存储的节点的密钥。因此，为了获得全局排序，可以在每个进程的本地对关键字进行排序。

每个进程在本地按照排序顺序编号。然后使用并行预x操作来计算最后一个密钥的全局排序。在此步骤之后，进程可以独立计算其本地节点的全局等级并以负载均衡的方式重新分配它们。

在网格及时更新的情况下，我们将块视为具有与它们的接近程度成比例的权重值（因为块更新频率更高）。然后应该将曲线切成等重量的部分。

2性能指标

在本节中，我们将讨论性能模型和我们用来评估我们迷你应用程序性能的指标。 AMR内核由以下不同频率的非重叠相位组成。内核迭代直到收敛，我们认为每次迭代都是单个时间步。

1.Renement /粗化：内核检查每个ref freq时间步的接收标准，如果有指示，则执行块的接收和粗化。块的添加和/或删除受制于前面讨论的2：1平衡标准。

2.负载均衡：节点的重新分区可以在重新/粗化之后执行。这包括计算新分区，重新分区数据和计算新的通信模式，以便在后续时间步中使用。

3.Computation：在每个时间步，每个叶节点根据邻居值更新其数据点，如模板模式（本讨论中的7点）所定义的。这一步需要跨叶节点的共享面交换数据（称为光晕更新）我们测量每个时间步i和每个过程j，花费在计算上的时间Tcomp（i; j），花费在光环更新中的时间Tcomm（i; j），花费时间Tref（i; j）网格和时间Tlb（i; j）花费负载平衡。让是总时间步数，ref freq = r，并让t1; ：：：; tk是发生负载平衡的时间步。然后，总执行时间Texec可以定义为

Titer(i) = maxj(Tcomp(i; j) Tcomm(i; j));

Tref (i) = maxjTref (i; j); and

Tlb(i) = maxjTlb(i; j):

这里给出的等式是针对没有任何计算 - 通信在内核中重叠的一般情况。 但是，我们的实现在模板代码中使用计算 - 通信重叠。 如果完全重叠，那么Titer的等式变为

Titer（i）= maxj（max（Tcomp（i; j）; Tcomm（i; j）））

我们使用这些公式来计算本报告中所有测试用例的总执行时间。

3MiniAMR

我们开发了一个改进的MiniAMR迷你应用程序的实现，它是Mantevo套件的一部分[10]。此迷你应用程序旨在更好地理解基于八叉树的AMR中的通信开销，并利用这些见

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[23368]，资料为PDF文档或Word文档，PDF文档可免费转换为Word