inria-00409051, version 1
Parallel Geometric Algorithms for Multi-Core Computers
Vicente H. F. Batista
1David L. Millman
a, 2Sylvain Pion
3Johannes Singler
b, 4
ACM Symposium on Computational Geometry (2009) 217-226
Résumé : 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 d-dimensional algorithms we describe are (a) spatial sorting of points, as is typically used for preprocessing before using incremental algorithms, (b) kd-tree construction, (c) axis-aligned box intersection computation, and finally (d) bulk insertion of points in Delaunay triangulations for mesh generation algorithms or simply computing Delaunay triangulations. We show experimental results for these algorithms in 3D, using our implementations based on the Computational Geometry Algorithms Library (CGAL, http://www.cgal.org/). 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.
- a – University of North Crolina at Chapel Hill
- b – Universitaet Karlsruhe
- 1 : COPPE - Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia (COPPE-UFRJ)
- Federal University of Rio de Janeiro
- 2 : University of North Carolina at Chapel Hill
- North Carolina State University
- 3 : GEOMETRICA (INRIA Sophia Antipolis / INRIA Saclay - Ile de France)
- INRIA
- 4 : University of Karlsruhe (TH)
- University of Karlsruhe – Universität of Karlsruhe
- Domaine : Informatique/Géométrie algorithmique
Informatique/Calcul parallèle, distribué et partagé
- inria-00409051, version 1
- http://hal.inria.fr/inria-00409051
- oai:hal.inria.fr:inria-00409051
- Contributeur : Sylvain Pion
- Soumis le : Mercredi 5 Août 2009, 11:13:41
- Dernière modification le : Mercredi 9 Septembre 2009, 11:28:12






Documents associés
Exporter