logo EDITE Sujets de doctorat

Analyse Topologique de Données In-Situ

Sujet proposé par
Directeur de thèse:
Doctorant: Charles GUEUNET
Unité de recherche UMR 7606 Laboratoire d'informatique de Paris 6

Domaine: Sciences et technologies de l'information et de la communication

Projet

La simulation numérique 3D s'est imposée ces dernières années dans de nombreux domaines comme un outil indispensable pour la découverte scientifique. Le calcul de simulations numériques 3D requiert souvent l'utilisation de super-calculateurs. Le résultat de ce type de calcul est typiquement représenté par une géométrie 3D (maillage tétraédrique, grille régulière, etc.) sur laquelle sont définies des fonctions scalaires représentant des grandeurs calculées par la simulation (température, pression, etc.). Ensuite, ces résultats sont traditionnellement transférés sur la station de travail de l'utilisateur pour leur post-traitement: visualisation et analyse géométrique.

Cette méthodologie globale s'avère cependant incompatible avec les caractéristiques de la nouvelle génération de super-calculateurs à venir (2018), devant attendre des performances de l'ordre de $10^18$ opérations par seconde (ExaScale). Les prévisions actuelles [19] font état de déséquilibres croissants entre l'accroissement de ces puissances de calcul et l'amélioration des débits de transferts ou de sauvegarde sur support permanent (disque dur). Ainsi, les super-calculateurs ExaScale produiront des résultats de simulations à des rythmes plusieurs ordres de grandeurs supérieurs à ceux de leur transfert réseau ou même de leur sauvegarde sur disque dur.

Dans ce scénario, le post-traitement traditionnel off-line (sur une station de travail distante) n'est plus envisageable, étant donné ce goulot d'étranglement majeur. Il est donc nécessaire de déplacer les algorithmes de post-traitement (visualisation et analyse géométrique) au plus près de la simulation de manière à contourner ce goulot d'étranglement. En particulier, pour minimiser le recours à la sauvegarde et au transfert réseau, il devient nécessaire d'exécuter les algorithmes de post-traitement (dont les données de sortie sont de faible taille) sur les mêmes infrastructures de calcul que la simulation, pendant que celle-ci s'exécute. On parle alors de *Visualisation In-Situ* [33].

Kitware Inc. [1], société développant les environnements de visualisation open-source Visualization ToolKit [2] et ParaView [3], et dont Kitware SAS est la filiale européenne, s'est rapidement positionnée sur ce segment en développant la bibliothèque Catalyst [4]. Cet outil permet d'exécuter un pipeline complet de visualisation et d'analyse depuis un code de simulation, et ce avec un minimum d'intrusion. Cette bibliothèque est aujourd'hui utilisée par de nombreux clients de Kitware (EDF, CEA et grands comptes internationaux).

Pour qu'un algorithme de visualisation soit utilisable de manière optimale dans un contexte in-situ, il faut que celui-ci présente les caractéristiques suivantes:

- Exécution parallèle (multi-coeurs) et distribuée (multi-noeuds) pour profiter au maximum du potentiel de calcul des super-alculateurs;

- Exécution interruptible pour permettre un contrôle de l'ordonnancement et de la répartition des ressources de calcul entre simulation et analyse.

Cependant, tous les algorithmes de visualisation ne présentent pas ces caractéristiques. En particulier, les algorithmes d'analyse topologique [24] (outils fondamentaux en visualisation et analyse de données) sont difficilement parallélisables et non-interruptibles. L'objet de cette thèse CIFRE est donc de re-penser intégralement ce type d'algorithmes pour les rendre compatibles avec une utilisation In-Situ et de les mettre en oeuvre dans le cadre de l'outil ParaView/Catalyst de Kitware, augmentant ainsi substantiellement ses fonctionnalités.

Enjeux

L'analyse topologique de données [24] est une méthodologie fondamentale pour la visualisation et l'analyse de données scalaires, notamment issues de simulations numériques. Étant donnée une fonction scalaire linéaire par morceaux F, ce type d'approche consiste à générer des abstractions topologiques de F, permettant de segmenter la géométrie en zones homogènes, où F est homogène d'un point de vue topologique. Par exemple, l'arbre de contour [12, 13] (et sa variante plus générale le graphe de Reeb [25, 23, 29, 21] segmente la géométrie en régions où le nombre de composantes connexes d'ensembles de niveau est égal à 1, pour toute valeur prise par les points de cette région. Le diagramme de persistence [14] (qui représente la distribution des paires de points critiques de F en fonction de leur importance) et le complexe de Morse-Smale [17, 26] (qui segmente la géométrie en régions où l'intégration avant et arrière du gradient se termine sur les mêmes paires de points critiques) sont d'autres exemples d'abstractions topologiques.

Ces structures de données jouent un rôle fondamental en visualisation pour l'accélération de traitements géométriques [31], la simplification d'isosurfaces [13, 29], l'analyse de symétrie [28], le rendu volumique [32], le suivi de structures d'intérêts au cours du temps [11], la segmentation de données [18, 16], la simplification de champs scalaires [30], etc. L'utilité de ce type d'analyse est renforcée par sa généricité (avec des applications en mécaniques des fluides, combustion, chimie, thermodynamiques, cosmologie, etc.) et son aspect multi-résolution, permettant d'extraire des structures d'intérêt à plusieurs niveaux de détail.

Malgré leur intérêt pour l'analyse de données et la visualisation, les algorithmes d'analyse topologique ne sont pourtant pas directement adaptés pour une utilisation in-situ:

1) Exécution parallèle et distribuée: Ces algorithmes reposent tous sur une passe globale sur les données de manière ordonnée et sont donc intrinsèquement séquentiels. Plusieurs tentatives ont été effectuées pour paralléliser l'algorithme de calcul d'arbre de contour en mémoire partagée [22, 10] ou le complexe de Morse-Smale [27] mais ces approches ne fournissent pas encore un gain en temps linéaire avec le nombre de coeurs. Concernant une exécution distribuée, seul l'arbre de jointure (une version simplifiée de l'arbre de contour) a été étudié [20]. Il est donc nécessaire de revoir en profondeur ces approches pour dériver des algorithmes parallèles (en mémoire partagée et distribuée) performants et passant linéairement à l'échelle, pour les abstractions topologiques les plus populaires: arbre de contour, graphe de Reeb, complexe de Morse-Smale, diagramme de persistence, espace de Reeb [15], etc.

2) Exécution interruptible: Dans un contexte in-situ, les résultats d'une simulation devant être analysés n'ont plus forcément vocation à être sauvegardés sur disque dur. Par conséquent, l'analyse doit avoir lieu tant que ces résultats sont disponibles dans la mémoire du code de simulation. Pour ce faire, il est nécessaire de concevoir des algorithmes d'analyse topologique capable d'être interrompus (lorsque le résultat de simulation est supprimé de la mémoire) et de fournir un résultat approché de l'abstraction topologique. Pour ce faire, une piste prometteuse serait de définir des algorithmes coarse-to-fine, capables de raffiner progressivement une abstraction topologique. Il s'agit là d'une difficulté théorique majeure pour l'analyse topologique, étant donné que tous ses algorithmes ont été définis jusqu'à présent dans un schéma fine-to-coarse (calcul de l'abstraction, puis simplification par persistence). Pour atteindre cet objectif, il est donc nécessaire de revoir en profondeur tous ces algorithmes.

L'objectif de cette thèse est donc de lever les verrous scientifiques suivants:

- Algorithmes d'analyse topologique parallèles, passant linéairement à l'échelle en mémoire partagée;

- Algorithmes d'analyse topologique parallèles, passant linéairement à l'échelle en mémoire distribuée;

- Algorithmes d'analyse topologique progressifs (exécution interruptible).

La thèse se déroulera en 3 parties:

1) 1ère année, Création d'algorithmes parallèles efficaces en mémoire partagée, puis distribuée;

2) 2ème année, Création d'algorithmes parallèles progressifs;

3) 3ème année, Intégration dans la plateforme VTK/ParaView/Catalyst de Kitware.

Les deux premières années de la thèse se dérouleront au LIP6 (avec des visites régulières à Kitware SAS à Lyon) et la dernière année (dédiée à l'expérimentation de l'intégration) se déroulera à Lyon dans les locaux de Kitware SAS.

Remarques additionnelles

Référénces:

[1] http://en.wikipedia.org/wiki/Kitware.

[2] http://en.wikipedia.org/wiki/VTK.

[3] http://en.wikipedia.org/wiki/ParaView.

[4] http://www.kitware.com/source/home/post/122.

[5] http://en.wikipedia.org/wiki/Code_Saturne.

[6] http://en.wikipedia.org/wiki/Gerris_(software).

[7] http://www.vtk.org/doc/nightly/html/classvtkReebGraph.html.

[8] http://visu2012.imag.fr/.

[9] http://www.sciencesmaths-paris.fr/fr/horizon-maths-2014-636.htm.

[10] A. Acharya and V. Natarajan. A parallel and memory efficient algorithm for constructing the contour tree. In Proc. of PacificVis, 2015.

[11] 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. on Vis. and Comp. Graph., 2011.

[12] H. Carr, J. Snoeyink, and A. Ulrike. Computing contour trees in all dimensions. In Proc. of Symposium on Discrete Algorithms, pp. 918–926, 2000.

[13] H. Carr, J. Snoeyink, and M. van de Panne. Simplifying flexible isosurfaces using local geometric measures. In Proc. of IEEE VIS, pp. 497–504, 2004.

[14] H. Edelsbrunner and J. Harer. Computational Topology. An Introduction. Amer. Math. Society, Jan. 2010.

[15] H. Edelsbrunner, J. Harer, and A. K. Patel. Reeb spaces of piecewise linear mappings. In Proc. of ACM Symp. on Comp. Geom., 2008.

[16] D. Gunther, R. Alvarez-Boto, J. Contreras-Garcia, J. Piquemal, and J. Tierny. Characterizing molecular interactions in chemical systems. IEEE Trans. on Vis. and Comp. Graph. (Proc. of IEEE VIS), 2014.

[17] A. Gyulassy, P.-T. Bremer, B. Hamann, and P. Pascucci. A practical approach to Morse-Smale complex computation: scalabity and generality. IEEE Trans. on Vis. and Comp. Graph. (Proc. of IEEE VIS), pp. 1619–1626, 2008.

[18] A. Gyulassy, D. Gunther, J. Levine, J. Tierny, and V. Pascucci. Conforming morse-smale complexes. IEEE Trans. on Vis. and Comp. Graph. (Proc. of IEEE VIS), 2014.

[19] W. Harrod. A journey to exascale computing. In SuperComputing, 2012.

[20] D. Morozov and G. Weber. Distributed merge trees. In Proc. of ACM Symposium on Principles and Practice of Parallel Programming, 2013.

[21] S. Parsa. A deterministic o(m log m) time algorithm for the reeb graph. In Proc. of ACM Symp. on Comp. Geom., 2012.

[22] V. Pascucci and K. Cole-McLaughlin. Parallel computation of the topology of level sets. Algorithmica, 2003.

[23] V. Pascucci, G. Scorzelli, P. T. Bremer, and A. Mascarenhas. Robust on-line computation of Reeb graphs: simplicity and speed. ACM Trans. on Graph. (Proc. of ACM SIGGRAPH), 2007.

[24] V. Pascucci, X. Tricoche, H. Hagen, and J. Tierny. Topological Data Analysis and Visualization: Theory, Algorithms and Applications. Springer, 2010.

[25] G. Reeb. Sur les points singuliers d’une forme de Pfaff complètement intégrable ou d’une fonction numérique. Comptes-rend. de l’Acad. des Scien., 222:847–849, 1946.

[26] V. Robins, P. Wood, and A. Sheppart. Theory and algorithms for constructing discrete morse complexes from grayscale digital images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011.

[27] N. Shivashankar and V. Natarajan. Parallel computation of 3d morse-smale complexes. Comp. Graph. Forum (Proc. of EuroVis), 2012.

[28] D. M. Thomas and V. Natarajan. Multiscale symmetry detection in scalar fields by clustering contours. IEEE Trans. on Vis. and Comp. Graph. (Proc. of IEEE VIS), 2014.

[29] J. Tierny, A. Gyulassy, E. Simon, and V. Pascucci. Loop surgery for volumetric meshes: Reeb graphs reduced to contour trees. IEEE Trans. on Vis. and Comp. Graph. (Proc. of IEEE VIS), 15:1177–1184, 2009.

[30] J. Tierny and V. Pascucci. Generalized topological simplification of scalar fields on surfaces. IEEE Trans. on Vis. and Comp. Graph. (Proc. of IEEE VIS), 2012.

[31] M. van Kreveld, R. van Oostrum, B. C. L., V. Pascucci, and D. Schikore. Contour trees and small seed sets for isosurface traversal. In Proc. of ACM Symp. on Comp. Geom., 1997.

[32] G. Weber, S. Dillard, H. Carr, V. Pascucci, and B. Hamann. Topology-controlled volume rendering. IEEE Trans. on Vis. and Comp. Graph., 2007.

[33] H. Yu, C. Wang, R. Grout, J. Chen, and K. Ma. In situ visualization for large scale combustion simulations. IEEE Computer Graphics and Applications, 2010.