标签存档: data repartitioning

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

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

继续阅读 »