Unordered Task-Parallel Augmented Merge Tree Construction.

Area of Science:

• Topological Data Analysis
• High-Performance Computing
• Scientific Visualization

Background:

• Contemporary scientific datasets demand efficient topological analysis for visualization and interaction.
• Existing parallel merge tree algorithms primarily focus on task-parallel or SMP architectures, not fully distributed systems.
• Traditional divide and conquer methods remain the standard for distributed merge tree construction.

Purpose of the Study:

• To develop a scalable, parallel, and distributed algorithm for complete merge tree construction.
• To outperform existing distributed merge tree algorithms in terms of total runtime.
• To enable faster topological analysis of large-scale scientific data.

Main Methods:

• Introduced a novel task-parallel algorithm for merge tree construction.
• Employs region growing around critical points for arc identification.
• Avoids the need for ordered progression or global data structures.
• Leverages a novel local boundary condition for region growth.

Main Results:

• The developed algorithm achieves a performance improvement of approximately three times over the previous fastest distributed solution.
• Demonstrates scalability for parallel and distributed environments.
• Successfully computes complete merge trees on distributed systems.

Conclusions:

• The new algorithm offers a significant advancement in distributed merge tree construction.
• Enables faster and more scalable topological analysis for large scientific datasets.
• Provides a viable alternative to traditional divide and conquer approaches for distributed settings.