Distributed merge trees
Distributed merge trees
复制标题
分布式合并树
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
G. Weber
中科院分区：
文献类型：
--
作者：
D. Morozov;G. Weber
改进的模拟和传感器正在产生数据集，其日益复杂的程度耗尽了我们直接可视化和理解它们的能力。为了解决这个问题，我们可以检测和提取数据中的重要特征，并将它们作为后续分析的基础。在这种情况下，拓扑方法很有价值，因为它们提供了健壮和通用的特征定义。
随着串行计算能力的增长停滞不前，数据分析变得越来越依赖大规模并行机。为了满足复杂数据集产生的计算需求，算法需要有效地利用这些计算机体系结构。拓扑方法的主要优点是强调全局信息，这在并行化过程中成为了障碍。
我们提出了两种方法来缓解这个问题。我们开发了合并树的分布式表示，避免了在单个处理器上计算全局树，并允许我们并行化后续查询。为了应对每个处理器不断增加的核心数量，我们开发了一种新的数据结构，允许我们利用多个共享内存核心来并行处理单个节点上的工作。最后，我们提供了一些实验，这些实验说明了我们方法的优势，并帮助确定了未来的挑战。
Improved simulations and sensors are producing datasets whose increasing complexity exhausts our ability to visualize and comprehend them directly. To cope with this problem, we can detect and extract significant features in the data and use them as the basis for subsequent analysis. Topological methods are valuable in this context because they provide robust and general feature definitions.
As the growth of serial computational power has stalled, data analysis is becoming increasingly dependent on massively parallel machines. To satisfy the computational demand created by complex datasets, algorithms need to effectively utilize these computer architectures. The main strength of topological methods, their emphasis on global information, turns into an obstacle during parallelization.
We present two approaches to alleviate this problem. We develop a distributed representation of the merge tree that avoids computing the global tree on a single processor and lets us parallelize subsequent queries. To account for the increasing number of cores per processor, we develop a new data structure that lets us take advantage of multiple shared-memory cores to parallelize the work on a single node. Finally, we present experiments that illustrate the strengths of our approach as well as help identify future challenges.