Unordered Task-Parallel Augmented Merge Tree Construction



Kilian Werner, Christoph Garth

 External link (DOI) 

 View presentation:2021-10-28T13:30:00ZGMT-0600Change your timezone on the schedule page
2021-10-28T13:30:00Z

Exemplar figure, described by caption below — The Join Tree is constructed by growing regions of exclusively monotone reachable vertices from minima and identifying inner nodes as the smallest valued boundary vertices around these regions. The image shows leaf edges embedded in the domain with their augmentation colored accordingly. High order nodes are currently treated like minima to crawl up the tree.

Fast forward

Direct link to video on YouTube: https://youtu.be/SFS-OVu206M

Keywords

I.3.1.d Parallel processing I.3.2.a Distributed/network graphics I.6.9 Visualization Topological Analysis

Abstract

Contemporary scientific data sets require fast and scalable topological analysis to enable visualization, simplification and interaction. Within this field, parallel merge tree construction has seen abundant recent contributions, with a trend of decentralized, task-parallel or SMP-oriented algorithms dominating in terms of total runtime. However, none of these recent approaches computed complete merge trees on distributed systems, leaving this field to traditional divide and conquer approaches. This paper introduces a scalable, parallel and distributed algorithm for merge tree construction outperforming the previously fastest distributed solution by a factor of around three. This is achieved by a task-parallel identification of individual merge tree arcs by growing regions around critical points in the data, without any need for ordered progression or global data structures, based on a novel insight introducing a sufficient local boundary for region growth.