粒子追踪是流场可视化中的一种非常基础的技术。很多应用，从最基本的流线，迹线的计算，到源汇分析和FTLE(有限时间李雅普诺夫指数)的计算，都需要追踪大量的粒子。粒子追踪本身计算量大，加之流场数据的规模往往也比较大，我们需要对其并行化处理。但是，无论是数据并行（对数据进行静态划分和分配）还是任务并行（对粒子进行静态分配），由于很难确保每个进程分配到均等的工作负载，并行粒子追踪往往存在着严重的负载不均问题。究其本质，造成这一问题的原因是在追踪过程中粒子的分布随时间变化，并且很可能分布非常不均。以图1(a)为例，粒子在追踪过程中的分布变化非常大，甚至在一段时间后有些进程（或数据）没有粒子。
图1 (a) 基本的数据并行方法 (b) 基于一般的k-d树分解的方法 (c) 基于带有几和约束的k-d树分解方法
针对这一问题，我们提出了一种新颖的方法，通过动态地对粒子进行重新分配来达到负载均衡的目的。我们的基本想法是在粒子追踪的过程中，动态地执行k-d树分解，使得每个进程所拥有的粒子数重新达到平衡，如图1(b)所示。但是，k-d树分解时可以在任何区域进行切分，因此进程可能会被分配到任何区域的粒子。由于粒子追踪的计算需要粒子所在区域的数据，在并行粒子追踪中，这种k-d树分解的实现往往需要每个进程能够访问全部的数据。但是，不论是初始时载入全部数据，或者运行时请求需要的数据，它们的代价往往都很大，甚至是不可行。我们的目标是使用静态的数据划分，使得通过k-d树分解可以达到动态负载平衡。因此，我们重新设计了一种带有约束的k-d树分解的方法用于粒子重分配（图1(c)）。相关工作[1]已被IEEE VIS 2017接收，并在近日由实验室张江同学在IEEE VIS 2017会议上进行了报告。
图2 我们提出的带有约束的k-d树分解的方法
如图2所示，在我们的方法里，首先将数据划分为没有重叠的数据块，数据块的数量与进程数相等。对于每一个数据块，我们通过增加一个ghost层在所有维度上对其进行扩展，使其与相邻的数据块重叠。ghost层的大小由进程的内存所决定，我们期望在内存限制下可以最大化数据块之间的重叠部分。之后，在k-d树分解的每一次迭代过程中，切分面会被严格限制在数据块的重叠区域内，这样可以确保粒子在被尽量均匀切分和分配的同时始终处于对应进程的数据域内。
图3 对Nek5000数据使用Gantt图和折线图分析负载随时间的变化
图4 对GEOS-5数据进行源汇分析的可扩展性测试结果
图5 对Isabel数据进行FTLE计算的可扩展性测试结果
我们对所提出的方法进行了一个全面的性能分析。基线方法使用了基本的数据并行粒子追踪方法，与我们提出的方法的区别在于基线方法直接进行粒子交换而非粒子重分配。我们首先在Nek5000热工水力学模拟数据计算大规模流线，利用Gantt图展示了每个进程的运行情况，利用折线图展示了负载平衡随时间的变化，其中负载平衡指示线（Max/Avg Workload）越接近于1表示负载越均衡。如图3所示，可以看到每次k-d树分解后，我们的方法都可以获得更平衡的负载，因此相比于基线方法花费更少的时间。我们还在不同内存限制下，分别利用GEOS-5全球气候模式模拟和飓风Isabel模拟数据进行源汇分析和FTLE计算，时间花费和总体负载平衡水平结果如图4和5所示。可以很明显看到在这两种应用案例下我们的方法相比于基线方法都很大程度提高了负载平衡性和可扩展性。此外，我们还和其他针对并行粒子追踪的负载平衡方法进行了比较。与这些方法相比，我们的方法不需要任何预处理和流场特效分析，不需要在运行过程中移动数据，不需要专门的进程进行调度。
Reference
[1] Jiang Zhang, Hanqi Guo, Fan Hong, Xiaoru Yuan, and Tom Peterka. Dynamic Load Balancing Based on Constrained K-D Tree Decomposition for Parallel Particle Tracing. IEEE Transactions on Visualization and Computer Graphics (SciVis’17), 24(1): 954-963, 2018.
评论关闭。