Task-based Augmented Contour Trees with ...
Type de document :
Compte-rendu et recension critique d'ouvrage
Titre :
Task-based Augmented Contour Trees with Fibonacci Heaps
Auteur(s) :
Gueunet, Charles [Auteur]
Kitware SAS
Performance et Qualité des Algorithmes Numériques [PEQUAN]
Fortin, Pierre [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Performance et Qualité des Algorithmes Numériques [PEQUAN]
Jomier, Julien [Auteur]
Kitware SAS
Tierny, Julien [Auteur]
Algorithmes, Programmes et Résolution [APR]
Kitware SAS
Performance et Qualité des Algorithmes Numériques [PEQUAN]
Fortin, Pierre [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Performance et Qualité des Algorithmes Numériques [PEQUAN]
Jomier, Julien [Auteur]
Kitware SAS
Tierny, Julien [Auteur]
Algorithmes, Programmes et Résolution [APR]
Titre de la revue :
IEEE Transactions on Parallel and Distributed Systems
Pagination :
1889-1905
Éditeur :
Institute of Electrical and Electronics Engineers
Date de publication :
2019
ISSN :
1045-9219
Mot(s)-clé(s) en anglais :
Scientific Visualization
Task Parallelism
Multi-core Architecture
Topological Data Analysis
Task Parallelism
Multi-core Architecture
Topological Data Analysis
Discipline(s) HAL :
Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
Informatique [cs]/Algorithme et structure de données [cs.DS]
Informatique [cs]/Traitement des images [eess.IV]
Informatique [cs]/Géométrie algorithmique [cs.CG]
Informatique [cs]/Mathématique discrète [cs.DM]
Informatique [cs]/Synthèse d'image et réalité virtuelle [cs.GR]
Informatique [cs]/Imagerie médicale
Informatique [cs]/Logiciel mathématique [cs.MS]
Informatique [cs]/Algorithme et structure de données [cs.DS]
Informatique [cs]/Traitement des images [eess.IV]
Informatique [cs]/Géométrie algorithmique [cs.CG]
Informatique [cs]/Mathématique discrète [cs.DM]
Informatique [cs]/Synthèse d'image et réalité virtuelle [cs.GR]
Informatique [cs]/Imagerie médicale
Informatique [cs]/Logiciel mathématique [cs.MS]
Résumé en anglais : [en]
This paper presents a new algorithm for the fast, shared memory, multi-core computation of augmented contour trees on triangulations. In contrast to most existing parallel algorithms our technique computes augmented trees, ...
Lire la suite >This paper presents a new algorithm for the fast, shared memory, multi-core computation of augmented contour trees on triangulations. In contrast to most existing parallel algorithms our technique computes augmented trees, enabling the full extent of contour tree based applications including data segmentation. Our approach completely revisits the traditional, sequential contour tree algorithm to re-formulate all the steps of the computation as a set of independent local tasks. This includes a new computation procedure based on Fibonacci heaps for the join and split trees, two intermediate data structures used to compute the contour tree, whose constructions are efficiently carried out concurrently thanks to the dynamic scheduling of task parallelism. We also introduce a new parallel algorithm for the combination of these two trees into the output global contour tree. Overall, this results in superior time performance in practice, both in sequential and in parallel thanks to the OpenMP task runtime. We report performance numbers that compare our approach to reference sequential and multi-threaded implementations for the computation of augmented merge and contour trees. These experiments demonstrate the run-time efficiency of our approach and its scalability on common workstations. We demonstrate the utility of our approach in data segmentation applications.Lire moins >
Lire la suite >This paper presents a new algorithm for the fast, shared memory, multi-core computation of augmented contour trees on triangulations. In contrast to most existing parallel algorithms our technique computes augmented trees, enabling the full extent of contour tree based applications including data segmentation. Our approach completely revisits the traditional, sequential contour tree algorithm to re-formulate all the steps of the computation as a set of independent local tasks. This includes a new computation procedure based on Fibonacci heaps for the join and split trees, two intermediate data structures used to compute the contour tree, whose constructions are efficiently carried out concurrently thanks to the dynamic scheduling of task parallelism. We also introduce a new parallel algorithm for the combination of these two trees into the output global contour tree. Overall, this results in superior time performance in practice, both in sequential and in parallel thanks to the OpenMP task runtime. We report performance numbers that compare our approach to reference sequential and multi-threaded implementations for the computation of augmented merge and contour trees. These experiments demonstrate the run-time efficiency of our approach and its scalability on common workstations. We demonstrate the utility of our approach in data segmentation applications.Lire moins >
Langue :
Anglais
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-02010580/document
- Accès libre
- Accéder au document
- http://arxiv.org/pdf/1902.04805
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02010580/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02010580/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- hal.pdf
- Accès libre
- Accéder au document
- 1902.04805
- Accès libre
- Accéder au document