Parallel Geometric Algorithms for Multi-Core Computers - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2008

Parallel Geometric Algorithms for Multi-Core Computers

David L. Millman
  • Fonction : Auteur
  • PersonId : 856291
Sylvain Pion
Johannes Singler
  • Fonction : Auteur
  • PersonId : 856292

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.
Fichier principal
Vignette du fichier
RR-6749.pdf (358.38 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00343804 , version 1 (03-12-2008)

Identifiants

  • HAL Id : inria-00343804 , version 1

Citer

Vicente H. F. Batista, David L. Millman, Sylvain Pion, Johannes Singler. Parallel Geometric Algorithms for Multi-Core Computers. [Research Report] RR-6749, INRIA. 2008, pp.30. ⟨inria-00343804⟩
220 Consultations
451 Téléchargements

Partager

Gmail Facebook X LinkedIn More