Task-Based Augmented Contour Trees with Fibonacci Heaps
Task-Based Augmented Contour Trees with Fibonacci Heaps
复制标题
基于任务的斐波那契堆增强轮廓树
DOI：
--
复制
发表时间：
2019
影响因子：
5.3
通讯作者：
Julien Tierny
中科院分区：
文献类型：
--
作者：
Charles Gueunet;P. Fortin;J. Jomier;Julien Tierny
本文提出了一种新的算法，用于快速，共享内存，多核计算的增广轮廓树的三角剖分。与大多数现有的并行算法相比，我们的技术计算增强树，使全范围的轮廓树为基础的应用程序，包括数据分割。我们的方法完全重温传统的，顺序的轮廓树算法重新制定的所有步骤的计算作为一组独立的本地任务。这包括一个新的计算过程，基于斐波那契堆的连接和分裂树，两个中间的数据结构用于计算的轮廓树，其建设是有效地同时进行由于任务并行的动态调度。我们还介绍了一个新的并行算法，这两个树的组合成输出的全球轮廓树。总体而言，得益于OpenMP任务运行时，这在实践中实现了卓越的上级时间性能，无论是在顺序还是并行模式下。我们报告的性能数字，比较我们的方法，以参考顺序和多线程实现的增强合并和轮廓树的计算。这些实验证明了我们的方法的运行时的效率和其在常见的工作站上的可扩展性。我们证明了我们的方法在数据分割应用程序的实用性。
This paper presents a new algorithm for the fast, shared memory, multi-core computation of augmented contour trees on triangulations. In contrast to most existing parallel algorithms our technique computes augmented trees, enabling the full extent of contour tree based applications including data segmentation. Our approach completely revisits the traditional, sequential contour tree algorithm to re-formulate all the steps of the computation as a set of independent local tasks. This includes a new computation procedure based on Fibonacci heaps for the join and split trees, two intermediate data structures used to compute the contour tree, whose constructions are efficiently carried out concurrently thanks to the dynamic scheduling of task parallelism. We also introduce a new parallel algorithm for the combination of these two trees into the output global contour tree. Overall, this results in superior time performance in practice, both in sequential and in parallel thanks to the OpenMP task runtime. We report performance numbers that compare our approach to reference sequential and multi-threaded implementations for the computation of augmented merge and contour trees. These experiments demonstrate the run-time efficiency of our approach and its scalability on common workstations. We demonstrate the utility of our approach in data segmentation applications.
用于可扩展 SMP 轮廓树计算的并行峰值修剪
DOI：
10.1109/ldav.2016.7874312
发表时间：
2016
期刊：
--
影响因子：
--
作者：
Carr H
通讯作者：
Carr H