Parallel peak pruning for scalable SMP contour tree computation
Parallel peak pruning for scalable SMP contour tree computation
复制标题
用于可扩展 SMP 轮廓树计算的并行峰值修剪
DOI：
10.1109/ldav.2016.7874312
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Carr H
中科院分区：
文献类型：
--
作者：
Carr H
随着数据集增长到百万亿级，自动化数据分析和可视化越来越重要，以中介人类的理解，并通过现场分析减少对磁盘存储的需求。高性能计算系统架构的趋势需要分析算法来有效地利用大规模多核和分布式系统的组合。其中一个主要的分析工具是等高线树，它分析等高线之间的关系，以确定超过本地重要性的功能。不幸的是，用于计算轮廓树的主要算法是显式串行的，并且建立在串行隐喻的基础上，这限制了这种分析形式的可扩展性。虽然有一些分布式轮廓树计算的工作，并分别在混合GPU-CPU计算，有没有有效的算法与强大的正式保证的性能与快速的实际性能结盟。我们报告了第一个共享SMP算法，用于完全并行的轮廓树计算，具有O（lgnlgt）并行步骤和O（n lgn）工作的形式保证，并在OpenMP中实现了高达10倍的并行速度，在NVIDIA Thrust中实现了高达50倍的速度。
As data sets grow to exascale, automated data analysis and visualisation 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, withfor-mal guarantees of O(lgnlgt) parallel steps and O(n lgn) work, and implementations with up to 10x parallel speed up in OpenMP and up to 50x speed up in NVIDIA Thrust.
登录
查看更多内容
分布式合并树
DOI：
--
发表时间：
2013
期刊：
ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming
影响因子：
--
作者：
D. Morozov;G. Weber
通讯作者：
G. Weber
分布式轮廓树
DOI：
--
发表时间：
2014
期刊：
Topological Methods in Data Analysis and Visualization
影响因子：
--
作者：
D. Morozov;G. Weber
通讯作者：
G. Weber
DOI：
10.1007/978-3-540-88606-8_5
发表时间：
2009
期刊：
SC14: International Conference for High Performance Computing, Networking, Storage and Analysis
影响因子：
--
作者：
Hamish A. Carr;J. Snoeyink
通讯作者：
J. Snoeyink
TOPORRERY：多分辨率拓扑的计算和呈现
影响因子：
5.2
作者：
Valerio Pascucci;K. Cole;G. Scorzelli
通讯作者：
G. Scorzelli
使用单调路径简单且优化输出敏感的轮廓树构造
DOI：
--
发表时间：
2005
期刊：
Computational geometry
影响因子：
--
作者：
Yi;Tobias Lenz;Xiang Lu;G. Rote
通讯作者：
G. Rote