基于高阶访问依赖的高效非定常流场可视化 (Efficient Unsteady Flow Visualization with High-Order Access Dependencies)

在流场可视化中,场线追踪是一种很基础的技术,很多应用包括流面计算、FTLE计算以及源汇分析等都需要追踪大量的场线。然而,由于巨大的I/O和内存需求,场线的计算是非常昂贵的。特别是I/O开销,往往能占据整个计算时间的90%。解决I/O负担的一个方法是将数据访问模式结合到场线计算中。数据访问模式由流场数据的特征隐式地决定,其记录了场线轨迹的数据访问情况。我们可以将其提取出来,并在之后的场线应用中预测数据访问。在已有的方法中,马尔可夫链被用来对数据访问模式进行建模,其思想是通过当前的数据访问预测下一个可能的数据访问。这种访问模式也被称为数据块之间的一阶访问依赖。不过,由于每个数据块可能与多个其他的数据块有访问依赖关系,因此很难得到比较准确和可靠的访问预测。

实际上,除了这种简单的一阶访问模式,在场线追踪中还存在着更为复杂的高阶访问依赖。不同之处就在于高阶访问依赖将历史的数据访问信息也考虑进去了,使之可以得到更为精确的数据访问预测。图1给出了一个例子。在图1(a)的一阶访问依赖中,数据块0与其三个邻结块1,2,3都有访问依赖关系。因此,对于一个从数据块0出发的粒子, 其下一个要经过的块有三种可能性。而在图1(b)的二阶访问依赖中,根据不同的历史访问,下一步要访问的数据块的可能性减小为两个,并且概率更集中。基于此,我们提出了一种新颖的基于高阶访问依赖的模型,以高效地计算场线,特别是非定常流场中的迹线。我们的方法包含两部分,首先通过迹线追踪计算出高阶访问依赖,然后将它们应用到一个并行粒子追踪框架,以证明高阶访问依赖的有效性。这篇文章将发表在今年的IEEE PacificVis会议上。

使用图模型展示的(a)一阶和(b)二阶访问依赖的比较。

图1 使用图模型展示的(a)一阶和(b)二阶访问依赖的比较。

与一阶访问依赖相比,在高阶访问依赖模型中,对下一个可能访问的数据块的预测不仅依赖于当前的数据访问,还建立在若干历史数据访问序列上。对于一个m阶访问依赖,我们有如下定义:

m阶访问依赖的定义

m阶访问依赖的定义

为了生成高阶访问依赖,我们首先需要在数据全域内追踪迹线。整个数据被均匀划分为若干数据块,每个块都包含了各个维度上相等大小的范围,并且使用均匀撒种的方式在不同位置放置粒子。每个粒子从起始位置开始同时正向和反向进行追踪。对应生成的迹线分别叫做正向迹线和反向迹线。为了减小预处理开销,我们对于正向迹线只追踪它从起始块跑到下一个数据块,而对于反向迹线,其所经过的数据块的数量不能大于指定的阶数。实际上,始于同一个位置的正向和反向迹线可以合并成一条完整的同时包含历史和下一步访问信息的迹线。对这些合并的迹线,除去起始块,对应的反向迹线所访问的数据块可看成是历史访问信息,而对应的正向迹线访问的数据块则是即将可能的访问信息。

对于指定m (m>1)阶的访问依赖,我们考虑历史访问的数据块序列长度为m−1的所有合并迹线。因为这些迹线的历史访问信息可能仍有不同,因此我们将它们进一步分组。每组迹线的历史访问信息是相同的,但是下个数据访问可能是不同的。假设下一个访问的数据块共有n种可能性,在我们的方法中,每个关联相同访问历史Bp (序列Bpm−1, Bpm−2, …, Bp1的简写)和当前访问Bc的下一个可能的数据块Bfi都会对应一个高阶访问依赖。其对应的访问转移概率pi定义为下一个访问该数据块的所有迹线数量与访问所有可能数据块的迹线总数的比值。该过程示意图如图2所示。为了充分利用所生成的迹线, 我们计算所有阶数低于该指定值的访问依赖。这样只要一轮预处理计算,就可以满足使用不同阶访问依赖的迹线实际应用。在本章剩下的部分,除非特别指出,我们所说的某高阶访问依赖都是这种“累积”的访问依赖。

高阶访问依赖的计算示意图

图2 高阶访问依赖的计算示意图

我们进一步将得到的高阶访问依赖应用到一个任务并行粒子追踪的框架中。数据块和其关联的高阶访问依赖是以数据项的形式进行存储。每个数据项包含三个部分:<key, value, dependencies>,分别表示数据块的时空索引、实际数据以及高阶访问依赖。在dependencies部分,对于具有相同历史访问信息的访问依赖,我们将它们重新组织,将其中下一步可能访问的数据块的key按照访问转移概率降序排列,这样dependencies里面可以看成是很多个键值对,方便之后的检索。

在运行时迹线计算过程中,我们使用了高阶数据预取来提高I/O效率。也就是说,当载入一个不在缓存中的数据项时,我们通过匹配粒子真实的历史数据访问信息和该数据项中高阶访问依赖的历史访问信息部分,得到具有最高转移概率的数据块并将其一并载入,以满足之后可能的数据访问需求。实际上,我们也可以通过设置预取深度来递归地预取多个深度的数据块,而在每个预取深度,也可以将多个高概率的数据块同时预取进来。图3展示了一个递归的预取过程。图中每个预取深度只取概率最大的数据块,原因会在下面讲到。

图3 一次性递归地预取多个数据项。在这个例子中,预取深度设置为4,并且在每个预取深度 只预取概率最大的那个数据块。当请求块(0, 0)时,块(0, 1),(1, 1),(2, 1)和(2, 2)一个接一个地被预 测出来并被预取进内存。在每个预取深度,历史访问信息都会随之更新。

图3 一次性递归地预取多个数据项。此处预取深度设置为4,且在每个预取深度只预取概率最大的数据块。

我们使用两个数据来测试我们的方法,分别是isabel飓风数据和GEOS-5全球气候模拟数据。我们生成了不同阶数的访问依赖,数据和预处理性能如图4所示。对于运行时性能,我们在这两个数据上分别测试了全局分析(全局均匀撒种)和局部分析(选定局部范围撒种),采用一阶方法和不带数据预取的方法作为对比。

图4 数据和预处理性能

图4 数据和预处理性能

对于全局分析,不同阶数的方法所得到的预取数据使用率和运行时间如图5所示。可以看到,阶数越高,预取数据的使用率越高,迹线计算的时间也越少,这也证明高阶方法提高了计算效率。当然,迹线计算的效率并不会随着阶数的增加也一直增大,而是一定阶数后逐渐变得平稳,因为到最后很少有粒子能有如此长的历史访问信息与阶数匹配。此外,对于GEOS-5数据,我们看到从一阶到高阶方法其性能的提升幅度没有Isabel数据的那么显著,原因是GEOS-5数据的迹线表现得比较平直,没有Isabel数据的那么分散,因此所生成的高阶访问依赖数量也远小于Isabel数据。这也表明不同的数据我们的方法效果也不同。我们还测试了在每个预取深度预取不同数量的数据块,其结果如图6所示。可以看到其最佳值是1。原因也很好理解,因为在每个预取深度预取的数据块中实际上最多只有一个能命中,一次性载入太多块反而会带来大量的I/O请求,造成预取数据使用率的降低。对于局部分析,如图7所示,我们也得到了类似于全局分析的结果,值得注意的是,由于局部分析中粒子在一个相对比较集中的区域内活动,一般来说其性能的提升没有全局分析那么明显。

图5 全局分析中不同阶数的方法所得到的预取数据使用率和运行时间

图5 全局分析中不同阶数的方法所得到的预取数据使用率和运行时间

图6 全局分析中每个预取深度预取不同数量的数据块的结果

图6 全局分析中每个预取深度预取不同数量的数据块的结果

图7 局部分析的测试结果

图7 局部分析的测试结果

实际上,我们的方法还是具有一定的局限性的。首先是预处理开销,主要集中在迹线计算上,尽管采取了一定的策略,其代价仍然比较高,特别是对于大规模数据。因此,我们需要考虑更好的撒种策略。另外,合适参数的选择也是一个比较困难的问题,包括预取深度和数据块大小的设置等,虽然我们在该工作中都是经验指定的,但是各个参数和它们之间的联系仍然值得我们进一步地探究。

[1] Jiang Zhang, Hanqi Guo, Xiaoru Yuan. Efficient Unsteady Flow Visualization with High-Order Access Dependencies. In Proceedings of IEEE Pacific Visualization Symposium (PacificVis 2016), pages 80-87, Taipei, Apr. 19-22, 2016.

评论关闭。