TTK is Getting MPI-Ready
Authors: 
Eve Le Guillou, Michael Will, Pierre Guillou, Jonas Lukasczyk, Pierre Fortin, Christoph Garth, Julien TiernyAuthors Info & Claims
Pages 5875 - 5892
Abstract
This system paper documents the technical foundations for the extension of the <italic>Topology ToolKit</italic> (TTK) to distributed-memory parallelism with the <italic>Message Passing Interface</italic> (MPI). While several recent papers introduced topology-based approaches for distributed-memory environments, these were reporting experiments obtained with tailored, mono-algorithm implementations. In contrast, we describe in this paper a versatile approach (supporting both triangulated domains and regular grids) for the support of topological analysis <italic>pipelines</italic>, i.e., a sequence of topological algorithms interacting together, possibly on distinct numbers of processes. While developing this extension, we faced several algorithmic and software engineering challenges, which we document in this paper. Specifically, we describe an MPI extension of TTK’s data structure for triangulation representation and traversal, a central component to the global performance and generality of TTK’s topological implementations. We also introduce an intermediate interface between TTK and MPI, both at the global pipeline level, and at the fine-grain algorithmic level. We provide a taxonomy for the distributed-memory topological algorithms supported by TTK, depending on their communication needs and provide examples of hybrid MPI+thread parallelizations. Detailed performance analyses show that parallel efficiencies range from 20% to 80% (depending on the algorithms), and that the MPI-specific preconditioning introduced by our framework induces a negligible computation time overhead. We illustrate the new distributed-memory capabilities of TTK with an example of advanced analysis pipeline, combining multiple algorithms, run on the largest publicly available dataset we have found (120 billion vertices) on a standard cluster with 64 nodes (for a total of 1536 cores). Finally, we provide a roadmap for the completion of TTK’s MPI extension, along with generic recommendations for each algorithm communication category.
References
[1]
A. Acharya and V. Natarajan, “A parallel and memory efficient algorithm for constructing the contour tree,” in Proc. IEEE Pacific Visual. Symp., 2015, pp. 271–278.
[2]
J. Ahrens, B. Geveci, and C. Law, “36 - ParaView: An end-user tool for large-data visualization,” in Visualization Handbook, C. D. Hansen, and C. R. Johnson, Eds., Burlington, NJ, USA: Butterworth-Heinemannloc>, 2005, pp. 717–731.
[3]
S. Bachthaler and D. Weiskopf, “Continuous scatterplots,” IEEE Trans. Vis. Comput. Graph., vol. 14, no. 6, pp. 1428–1435, Nov./Dec. 2008.
[4]
T. F. Banchoff, “Critical points and curvature for embedded polyhedral surfaces,” Amer. Math. Monthly, vol. 77, pp. 475–485, 1970.
[5]
U. Bauer, M. Kerber, and J. Reininghaus, “Distributed computation of persistent homology,” in Proc. 16th Workshop Algorithm Eng. Experiments, 2014, pp. 31–38.
[6]
U. Bauer, M. Kerber, J. Reininghaus, and H. Wagner, “Phat - persistent homology algorithms toolbox,” J. Symbolic Comput., vol. 78, pp. 76–90, 2017.
[7]
H. Bhatia, A. G. Gyulassy, V. Lordi, J. E. Pask, V. Pascucci, and P.-T. Bremer, “TopoMS: Comprehensive topological exploration for molecular and condensed-matter systems,” J. Comput. Chem., vol. 39, pp. 936–952, 2018.
[8]
T. B. Masood et al., “An overview of the topology toolKit,” in Proc. Topological Methods Data Anal. Visual., 2019, pp. 327–342.
[9]
A. Bock, H. Doraiswamy, A. Summers, and C. T. Silva, “TopoAngler: Interactive topology-based extraction of fishes,” IEEE Trans. Vis. Comput. Graph., vol. 24, no. 1, pp. 812–821, Jan. 2018.
[10]
P. Bremer, G. Weber, J. Tierny, V. Pascucci, M. Day, and J. Bell, “Interactive exploration and analysis of large scale simulations using topology-based data segmentation,” IEEE Trans. Vis. Comput. Graph., vol. 17, no. 9, pp. 1307–1324, Sep. 2011.
[11]
H. Carr, O. Ruebel, and G. Weber, “Distributed hierarchical contour trees,” in IEEE 12th Symp. Large Data Anal. Visual., 2022, pp. 1–10.
[12]
H. Carr, J. Snoeyink, and M. van de Panne, “Simplifying flexible isosurfaces using local geometric measures,” in Proc. IEEE Visual., 2004, pp. 497–504.
[13]
H. A. Carr, G. H. Weber, C. M. Sewell, O. Rübel, P. K. Fasel, and J. P. Ahrens, “Scalable contour tree computation by data parallel peak pruning,” IEEE Trans. Vis. Comput. Graph., vol. 27, no. 4, pp. 2437–2454, Apr. 2021.
[14]
F. Chazal, L. J. Guibas, S. Y. Oudot, and P. Skraba, “Persistence-based clustering in Riemannian manifolds,” J. ACM, vol. 60, 2013, Art. no.
[15]
H. Doraiswamy, J. Tierny, P. J. S. Silva, L. G. Nonato, and C. T. Silva, “TopoMap: A 0-dimensional homology preserving projection of high-dimensional data,” IEEE Trans. Vis. Comput. Graph., vol. 27, no. 2, pp. 561–571, Feb. 2021.
[16]
H. Edelsbrunner and J. Harer, Jacobi Sets of Multiple Morse Functions. Cambridge, MA, USA: Cambridge Books Online, 2004.
[17]
H. Edelsbrunner and J. Harer, Computational Topology: An Introduction. Providence, RI, USA: Amer. Math. Soc., 2009.
[18]
H. Edelsbrunner, D. Letscher, and A. Zomorodian, “Topological persistence and simplification,” Discrete Comput. Geometry, vol. 28, pp. 511–533, 2002.
[19]
H. C. Edwards, A. B. Williams, G. D. Sjaardema, D. G. Baur, and W. K. Cochran, “SIERRA toolkit computational mesh conceptual model,” Sandia Nat. Lab., Albuquerque, NM, USA, Tech. Rep. SAND--2010-1192, 2010.
[20]
G. Favelier, C. Gueunet, and J. Tierny, “Visualizing ensembles of viscous fingers,” in Proc. IEEE SciVis Contest, 2016.
[21]
R. Forman, “A user’s guide to discrete morse theory,” Sém. Lothar. Combin., vol. 48, Dec. 2001.
[22]
D. Guenther, R. Alvarez-Boto, J. Contreras-Garcia, J.-P. Piquemal, and J. Tierny, “Characterizing molecular interactions in chemical systems,” IEEE Trans. Vis. Comput. Graph., vol. 20, no. 12, pp. 2476–2485, Dec. 2014.
[23]
C. Gueunet, P. Fortin, J. Jomier, and J. Tierny, “Contour forests: Fast multi-threaded augmented contour trees,” in Proc. IEEE 12th Symp. Large Data Anal. Visual., 2016, pp. 85–92.
[24]
C. Gueunet, P. Fortin, J. Jomier, and J. Tierny, “Task-based augmented contour trees with fibonacci heaps,” IEEE Trans. Parallel Distrib. Syst., vol. 30, no. 8, pp. 1889–1905, Aug. 2019.
[25]
C. Gueunet, P. Fortin, J. Jomier, and J. Tierny, “Task-based augmented Reeb graphs with dynamic ST-Trees,” in Proc. Eurographics Symp. Parallel Graph. Visual., 2019, pp. 27–37.
[26]
P. Guillou, J. Vidal, and J. Tierny, “Discrete morse sandwich: Fast computation of persistence diagrams for scalar data–an algorithm and a benchmark,” IEEE Trans. Vis. Comput. Graph., vol. 30, no. 4, pp. 1897–1915, Apr. 2024.
[27]
A. Gyulassy, P. Bremer, R. Grout, H. Kolla, J. Chen, and V. Pascucci, “Stability of dissipation elements: A case study in combustion,” Comput. Graph. Forum, vol. 33, pp. 51–60, 2014.
[28]
A. Gyulassy, P. Bremer, and V. Pascucci, “Shared-memory parallel computation of morse-smale complexes with improved accuracy,” IEEE Trans. Vis. Comput. Graph., vol. 25, no. 1, pp. 1183–1192, Jan. 2019.
[29]
A. Gyulassy et al., “Interstitial and interlayer ion diffusion geometry extraction in graphitic nanosphere battery materials,” IEEE Trans. Vis. Comput. Graph., vol. 22, no. 1, pp. 916–925, Jan. 2016.
[30]
H. Freudenthal, “Simplizialzerlegungen von Beschrankter Flachheit,” Ann. Math., vol. 43, pp. 580–582, 1942.
[31]
C. Heine et al., “A survey of topology-based methods in visualization,” Comput. Graph. Forum, vol. 35, pp. 643–667, 2016.
[32]
X. Huang, P. Klacansky, S. Petruzza, A. Gyulassy, P. Bremer, and V. Pascucci, “Distributed merge forest: A new fast and scalable approach for topological analysis at scale,” in Proc. ACM Int. Conf. Supercomputing, 2021, pp. 367–377.
[33]
H. W. Kuhn, “Some combinatorial lemmas in topology,” IBM J. Res. Dev., vol. 45, pp. 518–524, 1960.
[34]
D. Ibanez, E. S. Seol, C. W. Smith, and M. S. Shephard, “PUMI: Parallel unstructured mesh infrastructure,” ACM Trans. Math. Softw., vol. 42, pp. 1–28, 2016.
[35]
J. Kasten, J. Reininghaus, I. Hotz, and H. C. Hege, “Two-dimensional time-dependent vortex regions based on the acceleration magnitude,” IEEE Trans. Vis. Comput. Graph., vol. 17, no. 12, pp. 2080–2087, Dec. 2011.
[36]
P. Klacansky, “Open scientific visualization data sets,” 2020. [Online]. Available: https://klacansky.com/open-scivis-datasets/
[37]
P. Klacansky, J. Tierny, H. A. Carr, and Z. Geng, “Fast and exact fiber surfaces for tetrahedral meshes,” IEEE Trans. Vis. Comput. Graph., vol. 23, no. 7, pp. 1782–1795, Jul. 2017.
[38]
D. Laney, P. Bremer, A. Mascarenhas, P. Miller, and V. Pascucci, “Understanding the structure of the turbulent mixing layer in hydrodynamic instabilities,” IEEE Trans. Vis. Comput. Graph., vol. 12, no. 5, pp. 1053–1060, Sep./Oct. 2006.
[39]
G. Liu and F. Iuricich, “A task-parallel approach for localized topological data structures,” IEEE Trans. Vis. Comput. Graph., vol. 30, no. 1, pp. 1271–1281, Jan. 2024.
[40]
J. Lukasczyk, C. Garth, R. Maciejewski, and J. Tierny, “Localized topological simplification of scalar data,” IEEE Trans. Vis. Comput. Graph., vol. 27, no. 2, pp. 572–582, Feb. 2021.
[41]
R. G. C. Maack, J. Lukasczyk, J. Tierny, H. Hagen, R. Maciejewski, and C. Garth, “Parallel computation of piecewise linear morse-smale segmentations,” IEEE Trans. Vis. Comput. Graph., vol. 30, no. 4, pp. 1942–1955, Apr. 2024.
[42]
S. Maadasamy, H. Doraiswamy, and V. Natarajan, “A hybrid parallel algorithm for computing and tracking level set topology,” in Proc. IEEE 19th Int. Conf. High Perform. Comput., 2012, pp. 1–10.
[43]
D. Maljovec et al., “Topology-inspired partition-based sensitivity analysis and visualization of nuclear simulations,” in Proc. IEEE Pacific Visual. Symp., 2016, pp. 64–71.
[44]
Message Passing Interface Forum, “MPI: A message-passing interface standard, version 4.0,” Jun. 9, 2021. [Online]. Available: https://www.mpi-forum.org/docs/mpi-4.0/mpi40-report.pdf
[45]
D. Morozov and T. Peterka, “Block-parallel data analysis with DIY2,” in Proc. IEEE 12th Symp. Large Data Anal. Visual., 2016, pp. 29–36.
[46]
D. Morozov and G. H. Weber, “Distributed merge trees,” in Proc. ACM SIGPLAN Symp. Princ. Pract. Parallel Program., 2013, pp. 93–102.
[47]
D. Morozov and G. H. Weber, “Distributed contour trees,” in Proc. Topological Methods Data Anal. Vis. III, P.-T. Bremer, I. Hotz, V. Pascucci, and R. Peikert, Eds. 2014, pp. 89–102.
[48]
F. Nauleau, F. Vivodtzev, T. Bridel-Bertomeu, H. Beaugendre, and J. Tierny, “Topological Analysis of Ensembles of Hydrodynamic Turbulent Flows–An Experimental Study,” in Proc. IEEE 12th Symp. Large Data Anal. Visual., 2022, pp. 1–11.
[49]
A. Nigmetov and D. Morozov, “Local-global merge tree computation with local exchanges,” in Proc. Int. Conf. High Perform. Comput., Netw., Storage Anal., 2019, pp. 1–13.
[50]
A. Nigmetov and D. Morozov, “Reeber: A. library for shared- and distributed-memory parallel computation of merge trees,” 2020. [Online]. Available: https://github.com/mrzv/reeber
[51]
M. Olejniczak, A. S. P. Gomes, and J. Tierny, “A topological data analysis perspective on non-covalent interactions in relativistic calculations,” Int. J. Quantum Chem., vol. 120, 2019, Art. no.
[52]
M. Olejniczak and J. Tierny, “Topological data analysis of vortices in the magnetically-induced current density in LiH molecule,” Phys. Chem. Chem. Phys., vol. 25, pp. 5942–5947, 2023.
[53]
OpenMP Architecture Review Board, “OpenMP application program interface version 5.1,” 2020. [Online]. Available: https://www.openmp.org/specifications/
[54]
V. Pascucci and K. Cole-McLaughlin, “Parallel computation of the topology of level sets,” Algorithmica, vol. 38, pp. 249–268, 2004.
[55]
V. Robins, P. J. Wood, and A. P. Sheppard, “Theory and algorithms for constructing discrete morse complexes from grayscale digital images,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 33, no. 8, pp. 1646–1658, Aug. 2011.
[56]
N. Shivashankar and V. Natarajan, “Parallel computation of 3D morse-smale complexes,” Comput. Graph. Forum, vol. 31, pp. 965–974, 2012.
[57]
N. Shivashankar, P. Pranav, V. Natarajan, R. van de Weygaert, E. P. Bos, and S. Rieder, “Felix: A topology based framework for visual exploration of cosmic filaments,” IEEE Trans. Vis. Comput. Graph., vol. 22, no. 6, pp. 1745–1759, Jun. 2016.
[58]
D. Smirnov and D. Morozov, “Triplet merge trees,” in Proc. Topological Methods Data Anal. Vis. V, H. Carr, I. Fujishiro, F. Sadlo, and S. Takahashi, Eds. 2020, pp. 19–36.
[59]
M. Soler, M. Petitfrere, G. Darche, M. Plainchault, B. Conche, and J. Tierny, “Ranking viscous finger simulations to an acquired ground truth with topology-aware matchings,” in Proc. IEEE 9th Symp. Large Data Anal. Visual., 2019, pp. 62–72.
[60]
T. Sousbie, “The persistent cosmic web and its filamentary structure: Theory and implementations,” Monthly Notices Roy. Astronomical Soc., vol. 414, pp. 350–383, 2011.
[61]
J. Tierny and H. A. Carr, “Jacobi fiber surfaces for bivariate reeb space computation,” IEEE Trans. Vis. Comput. Graph., vol. 23, no. 1, pp. 960–969, Jan. 2017.
[62]
J. Tierny, G. Favelier, J. A. Levine, C. Gueunet, and M. Michaux, “The topology toolkit,” 2017. [Online]. Available: https://topology-tool-kit.github.io/
[63]
J. Tierny and V. Pascucci, “Generalized topological simplification of scalar fields on surfaces,” IEEE Trans. Vis. Comput. Graph., vol. 18, no. 12, pp. 2005–2013, Dec. 2012.
[64]
TTK Contributors, “TTK Data,” 2020. [Online]. Available: https://github.com/topology-tool-kit/ttk-data/tree/dev
[65]
TTK Contributors, “TTK online example database,” 2022. [Online]. Available: https://topology-tool-kit.github.io/examples/
[66]
K. Werner and C. Garth, “Unordered task-parallel augmented merge tree construction,” IEEE Trans. Vis. Comput. Graph., vol. 27, no. 8, pp. 3585–3596, Aug. 2021.
[67]
W. Zhang et al., “AMReX: A framework for block-structured adaptive mesh refinement,” J. Open Source Softw., vol. 4, 2019, Art. no.
Recommendations
MPI + MPI: a new hybrid approach to parallel programming with MPI plus shared memory
Hybrid parallel programming with the message passing interface (MPI) for internode communication in conjunction with a shared-memory programming model to manage intranode parallelism has become a dominant approach to scalable parallel programming. While ...
MPI-StarT: delivering network performance to numerical applications
SC '98: Proceedings of the 1998 ACM/IEEE conference on SupercomputingWe describe an MPI implementation for a cluster of SMPs interconnected by a high-performance interconnect. This work is a collaboration between a numerical applications programmer and a cluster interconnect architect. The collaboration started with the ...
Performance Evaluation of MPI Implementations and MPI-Based Parallel ELLPACK Solvers
MPIDC '96: Proceedings of the Second MPI Developers ConferenceAbstract: We are concerned with the parallelization of finite element mesh generation and its decomposition, and the parallel solution of sparse algebraic equations which are obtained from the parallel discretization of second order elliptic partial ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
1077-2626 © 2024 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Educational Activities Department
United States
Publication History
Published: 17 April 2024
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Dec 2024