Scalable Contour Tree Computation by Data Parallel Peak Pruning.
Scalable Contour Tree Computation by Data Parallel Peak Pruning.
复制标题
通过数据并行峰值修剪进行可扩展等高线树计算。
DOI：
10.1109/tvcg.2019.2948616
复制
发表时间：
2021
影响因子：
5.2
通讯作者：
Carr HA
中科院分区：
文献类型：
--
作者：
Carr HA
随着数据集增长到亿级，自动化数据分析和可视化变得越来越重要，以便通过现场分析实现人类的中间理解并减少对磁盘存储的需求。高性能计算系统的体系结构趋势要求分析算法有效地利用大规模多核和分布式系统的组合。主要的分析工具之一是等高线树，它分析等高线之间的关系，以确定比局部更重要的特征。不幸的是，计算轮廓树的主要算法是显式串联的，并且建立在连续隐喻的基础上，这限制了这种分析形式的可扩展性。虽然在分布式轮廓树计算和GPU-CPU混合计算方面有一些工作，但还没有有效的算法在性能和快速实用性能上有很强的形式化保证。本文报道了第一个用于全并行轮廓树计算的共享SMP算法，对于具有V个样本和t个轮廓树超节点的数据，形式上保证O(Lg V LGT)并行步长和O(V Lg V)工作，并且在使用TBB和使用推力的GPU上实现的并行加速都超过30倍，与串行扫描合并算法相比提高了70倍。
As data sets grow to exascale, automated data analysis and visualization are increasingly important, to intermediate human understanding and to reduce demands on disk storage via in situ analysis. Trends in architecture of high performance computing systems necessitate analysis algorithms to make effective use of combinations of massively multicore and distributed systems. One of the principal analytic tools is the contour tree, which analyses relationships between contours to identify features of more than local importance. Unfortunately, the predominant algorithms for computing the contour tree are explicitly serial, and founded on serial metaphors, which has limited the scalability of this form of analysis. While there is some work on distributed contour tree computation, and separately on hybrid GPU-CPU computation, there is no efficient algorithm with strong formal guarantees on performance allied with fast practical performance. We report the first shared SMP algorithm for fully parallel contour tree computation, with formal guarantees of O(lg V lgt) parallel steps and O(V lg V) work for data with V samples and t contour tree supernodes, and implementations with more than 30× parallel speed up on both CPU using TBB and GPU using Thrust and up 70× speed up compared to the serial sweep and merge algorithm.