并行粒子追踪中基于数据重划分的动态负载平衡方法 (Dynamic Data Repartitioning for Load-Balanced Parallel Particle Tracing)

在流场可视化中,粒子追踪是一种非常基础的技术。通过在流场区域追踪大规模的粒子,研究者可以进行各种各样的流场应用,例如生成流线和迹线去分析复杂流场内部结构等。但是,在应用粒子追踪时,我们往往需要处理大规模数据,其计算代价也非常高,因而需要更具可扩展性的并行算法。目前,最常见的并行粒子追踪算法是数据并行,如图1所示,即在初始时将数据划分为数据块并将这些块分配给不同的进程,之后的粒子追踪过程中,粒子在每个数据块中进行追踪计算并在数据块间进行交换,直至所有粒子追踪完成(即达到最大追踪步数,或者提前穿出了流场边界)。但是,这些数据块的负载很可能会非常不均衡。例如,某些数据块中可能存在漩涡等流场特征,导致附近的粒子会“陷入”其中。尽管存在一些静态负载平衡方法,试图在初始化阶段就将数据块进行负载均衡的划分和分配,但它们都需要进行比较复杂的预处理。因此,我们提出了一种基于数据重划分的动态负载平衡方法,使用一般的初始数据划分和分配策略,在运行时周期性地对数据块负载进行评估并据此进行重划分,从而重新平衡每个进程的负载。相关工作[1]已被IEEE PacificVis 2018接收,并在近日由实验室张江同学在IEEE PacificVis 2018会议上进行了报告。

图1 数据并行中数据块负载的不均匀分布

图2是我们的并行粒子追踪计算流程图,主要包括初始化阶段和多轮追踪计算阶段。我们的方法可以同时处理定常流场和非定常流场。在初始化阶段,对于定常流场,我们将其划分为空间数据块并进行分配,所有数据块会被一次性载入处理。对于非定常流场,我们首先将其划分为多个时间段,并将每个时间段内的数据按照空间维度进行划分。非定常流场数据会被按照划分的时间段顺序连续载入处理。由于非定常流场可以看成是多个时间段下的定常流场,我们将定常流场中的粒子追踪作为一般情况来介绍我们的方法。

图2 我们方法提出的并行粒子追踪计算流程图

在我们的方法中,运行时的并行粒子追踪被管理为一个多轮的计算过程。在每一轮中,每个进程独立地追踪其分配到的数据块中的粒子。粒子在每一轮最多可以经过指定数目的数据块,我们定义该数目为追踪深度(tracing depth),用字母N表示。当所有粒子从开始数据块出发,都经过了N个数据块,或者在这之前就穿出了当前进程的数据块或者已经完成了计算,我们定义该轮追踪完成。当一轮粒子追踪计算完成后,如果还有未完成粒子存在,我们会将数据进行重划分。

图3 基于访问依赖图的数据块负载评估示意图

为了对数据进行重划分,我们首先需要评估下一轮中每个数据块的负载。我们提出了一种动态负载评估的方法,可以对每个数据块中未完成粒子的负载进行预测。这种预测方法假定负载与粒子的数量和数据块的历史负载直接相关。其基本思想是,通过前面轮次的追踪可以计算得到在任何一个数据块中追踪过的每个粒子的平均负载,将其乘以下一轮要在该数据块中追踪的粒子的数量,即可得到该数据块在下一轮的预估负载。当追踪深度为1时,可以直接通过该方法计算得到每个数据块的预估负载,但是,当追踪深度大于1时,粒子可以运动到除初始数据块以外的其他数据块。为了对一个数据块中未完成粒子在下一轮的负载进行全面的评估,我们需要知道这些粒子在设定的追踪深度下全部可能访问的数据块。因此,我们动态地根据历史追踪结果建立了一种访问依赖图(access dependency graph)。该访问依赖图记录了从每个数据块到其相邻数据块的访问转移概率,在之前的工作中主要用于数据预取。如图3所示,在我们的工作中,基于该图我们可以预测一个数据块中的粒子可能会访问哪些数据块,以及粒子在这些可能访问的数据块中的分布数量。据此,我们可以用前面提到的评估计算方法预测粒子在这些数据块中的负载,然后将这些负载累加,得到粒子在下一轮的完整的负载。通过这种方法,我们可以评估下一轮中每个数据块的负载。

图4 使用RCB算法的数据重划分示意图

在对每个数据块的负载进行评估后,我们使用递归坐标二分(recursive coordinate bisection, RCB)算法对数据块进行重新划分,其示意图如图4所示。RCB算法将数据块的坐标作为输入,数据块的评估负载作为对应坐标的权重。重划分算法会递归地将数据块坐标划分为平衡的两部分,同时最大化新旧划分之间的重叠。重划分后,每个进程会被重新分配到总评估负载相近的数据块组合。值得注意的是,由于我们在预测每个数据块的负载时,同时计算了未完成粒子运动到其他数据块中的负载(追踪深度大于1),因此在重划分后这些数据块也会被复制到相应的进程中。

图5 对Nek5000数据使用Gantt图和折线图分析负载随时间的变化

图6 对Isabel数据的可扩展性测试结果

我们对所提出的方法进行了一个性能研究。用于比较的基线方法是基本的数据并行粒子追踪方法,其在每一轮计算完成后只对未完成粒子按照初始数据块的分配进行交换。我们使用了两个数据,分别追踪在全局范围内撒种的粒子。我们首先在Nek5000热工水力学模拟数据计算大规模流线。如图5所示,在这个案例中,我们利用Gantt图展示每个进程的运行情况,利用折线图展示负载平衡随时间的变化,其中负载平衡指示线(Max/Avg Workload)越接近于1表示负载越均衡。可以看到,在每一次经过数据重划分后,我们的方法相比于基线方法都可以获得更平衡的负载。在基线方法中,总有一两个进程处于繁忙阶段而其他进程却相对比较空闲,这种不平衡的现象在我们的方法结果中明显减轻。我们还使用飓风Isabel模拟数据计算大规模迹线。如图6所示,我们展示了总运行时间、粒子追踪计算时间,以及总体负载平衡指示线的变化。与流线计算的案例相似,我们同样可以看到,我们的方法提升了负载均衡性和可扩展性,并且在追踪深度越大的情况下表现更好。此外,我们还和其他针对并行粒子追踪的负载平衡方法进行了比较。与这些方法相比,我们的方法不需要任何预处理和流场特征分析,不需要专门的进程进行调度。与我们之前使用带有约束的k-d树分解方法[2]相比,该方法可以有效地对不均衡的粒子分布情况进行均衡的划分,从而进一步提高了负载均衡性。

Reference

[1] Jiang Zhang, Hanqi Guo, Xiaoru Yuan, and Tom Peterka. Dynamic Data Repartitioning for Load-Balanced Parallel Particle Tracing. In Proceedings of IEEE Pacific Visualization Symposium (PacificVis 2018), Kobe, Japan, Apr. 10-13, 2018.

[2] 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.

评论关闭。