时变流场的并行粒子平移和FTLE计算 (Parallel Particle Advection and FTLE Computation for Time-Varying Flow Fields)

流场是一种很重要的科学模拟的产物,对流场进行可视化的一种很常见的方法是粒子平移(particle advection),追踪粒子在流场中的运行路线。我们可以利用粒子踪迹计算得到一种非常强大的分析工具:Finite-Time Lyapunov Exponent field (FTLE域)。在时变流场中,给定一个空间位置和时间点,它的FTLE值表示以接近于该位置为种子(seed)位置的粒子在有限时间步后的偏离情况,该偏离情况可以使用雅克比流图(Jacobian of the flow map)来度量。从相同的时变数据集中可以计算出多个FTLE值,用来分析流场特征随时间如何演变。多个FTLE值的计算需要在时间和空间上密集分布的迹线(pathline),这也导致产生了性能的瓶颈问题。因此,Boonthanome等人在2012年SC上的文章[1]中,提出了一种并行的时变粒子追踪技术,特别是针对于在大规模矢量场中计算多个FTLE值(需要在时间和空间上分布的很大数量的粒子)的需求。

overview

文章提出的并行FTLE计算框架如上图所示。该框架可以分成三个主要部分:初始化,粒子平移,FTLE计算。初始化阶段将时变矢量场数据的整个时间范围分解为多个不同的时间窗口,对每个时间窗口,将空间域划分为多个块。某个时间窗口中的所有块称作一个时间间隔(time interval)。在划分完空间区域后,使用round-robin方法,这些块会被分配给进程。接着,根据FTLE的计算参数,种子位置会被计算并放置到正确的块中。

所有进程被平均分为若干个进程组,每个进程组分配到了连续的时间间隔。进程组处理自己当前的时间间隔,处理完毕后载入下一个时间间隔。在该处理过程中,进程组负责粒子的平移,直至在该时间间隔中没有可用的粒子。当粒子完成平移后,它们会被送回到起源进程(originating process)。

一旦所有粒子都被送回到起源进程,接下来便需要进行FTLE的计算。每个单独的FTLE域会被分配给一个进程组,每个FTLE会被分解到进程组中所有进程的块中。为了进行雅克比计算,每个FTLE块还需要一个ghost cell层,流图计算出来后,ghost值会在所有进程中进行交换,然后FTLE值就可以并行地计算出来,最终产生的FTLE域会被写入到磁盘。

important

为了最大限度利用进程资源,文章采用了一种并发处理多个时间间隔的流水线方法。如上图所示,所有进程组被分配到一定数量的时间间隔。在粒子平移的开始阶段,所有进程组会载入其第一个时间间隔并开始粒子的平移。当粒子到达块边界时,它会被送到包含该块的进程中继续平移。当所有可能的粒子超出了该时间间隔范围后,对应的进程组会载入下一个时间间隔,直至所有的时间间隔都被载入。

粒子根据其是否完成平移分为两类:活跃(active)和不活跃(inactive)。当粒子仍然在矢量场中进行平移时,它属于活跃的,反之不活跃。活跃的粒子会被排入到一个ActiveList表中,不活跃的粒子在一个ReturnList表中。为了判断某个时间间隔的停止与否,文章使用了一个“根”进程来收集所有进程送来的信息。当时间间隔需要计算的活跃粒子的总数(Ptotal)与完成粒子的数量(Pdone)达到一致时,该时间间隔宣告完成。Ptotal由两类粒子组成,一类是在该时间间隔新种的粒子(Pseed),另一类是在前一个时间间隔活跃并且传到当前时间间隔的粒子(Pnext)。为了达到负载平衡以及良好的扩展性,文章使用了一个二叉树通信模型,如下图所示。图中在阶段1,当0号进程组完成后,每个进程结点将其Pnext值传到其下一个进程组的表兄弟结点。在阶段2,当P6从其先前的表兄弟结点和子结点获得Pnext值后,总的Pnext值会被送到其父亲结点。在阶段3,当根结点P5从先前的表兄弟结点和两个子结点接收到Pnext值后,Ptotal的正确值会被计算出来,进而用来判断该时间间隔是否结束。

illustration

总的来说,这篇文章使用了一种流水线的工作流结构方式对大规模时变的粒子平移进行并行地计算,在时间和空间上都做到了并行,而且,对多个时间间隔进行流水线式的并发处理也是文章的亮点所在。该工作还可以与其他一些近期做过的并行工作进行比较,以后我们也会一一进行的分析。

[1] Nouanesengsy, B.; Teng-Yok Lee; Kewei Lu; Han-Wei Shen; Peterka, T., “Parallel particle advection and FTLE computation for time-varying flow fields,” High Performance Computing, Networking, Storage and Analysis (SC), 2012 International Conference for, pp. 1-11, 10-16 Nov. 2012

评论关闭。