Parallel Geometric Algorithms for Multi-Core Computers

Abstract : Computers with multiple processor cores using shared memory are now ubiquitous. In this paper, we present several parallel geometric algorithms that specifically target this environment, with the goal of exploiting the additional computing power. The algorithms we describe are (a) 2-/3-dimensional spatial sorting of points, as is typically used for preprocessing before using incremental algorithms, (b) d-dimensional axis-aligned box intersection computation, and finally (c) 3D bulk insertion of points into Delaunay triangulations, which can be used for mesh generation algorithms, or simply for constructing 3D Delaunay triangulations. For the latter, we introduce as a foundational element the design of a container data structure that both provides concurrent addition and removal operations and is compact in memory. This makes it especially well-suited for storing large dynamic graphs such as Delaunay triangulations. We show experimental results for these algorithms, using our implementations based on the Computational Geometry Algorithms Library (CGAL). This work is a step towards what we hope will become a parallel mode for CGAL, where algorithms automatically use the available parallel resources without requiring significant user intervention.
Type de document :
Article dans une revue
Computational Geometry, Elsevier, 2010, Special Issue on the 25th Annual Symposium on Computational Geometry (SoCG'09), 43 (8), pp.663-677. 〈10.1016/j.comgeo.2010.04.008〉
Liste complète des métadonnées

Littérature citée [33 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00488961
Contributeur : Sylvain Pion <>
Soumis le : jeudi 3 juin 2010 - 15:01:29
Dernière modification le : jeudi 11 janvier 2018 - 16:57:00
Document(s) archivé(s) le : vendredi 19 octobre 2012 - 15:31:48

Fichier

parallel_cgal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Vicente Batista, David Millman, Sylvain Pion, Johannes Singler. Parallel Geometric Algorithms for Multi-Core Computers. Computational Geometry, Elsevier, 2010, Special Issue on the 25th Annual Symposium on Computational Geometry (SoCG'09), 43 (8), pp.663-677. 〈10.1016/j.comgeo.2010.04.008〉. 〈inria-00488961〉

Partager

Métriques

Consultations de la notice

334

Téléchargements de fichiers

353