A two-level multithreaded Delaunay kernel. (April 2017)

• Record Type: Journal Article
• Authors: Remacle, Jean-François
• Is Part Of: Computer aided design. Volume 85(2017)
• Page Start: 2
• Page End: 9
• Publication Date: 2017-04
• Subjects: Delaunay triangulation -- Parallel computing -- OpenMP; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2016.07.018
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: This paper presents a fine grain parallel version of the 3D Delaunay Kernel procedure using the OpenMP (Open Multi-Processing) API. A set S = { p 1, …, p n } of n points is taken as input. S is initially sorted along a space-filling curve so that two points that are close in the insertion order are also close geometrically. The sorted set of points is then divided into M subsets S i, 1 ≤ i ≤ M of equal size n / M . The multithreaded version of the Delaunay kernel inserts M points at a time in the triangulation. OpenMP barriers provide the required synchronization that is needed after each multiple insertion in order to avoid data races. This simple approach exhibits two standard problems of parallel computing: load imbalance and parallel overheads. Those two issues are addressed using a two-level version of the multithreaded Delaunay kernel. Tests show that triangulations of about a billion tetrahedra can be generated on a 32 core machine (Intel Xeon E5-4610 v2 @ 2.30 GHz with 128 GB of memory) in less that 3 minutes of wall clock time, with a speedup of 18 compared to the single-threaded implementation. Highlights: A fine grain parallel Delaunay kernel algorithm is proposed. The method that is proposed allows to generate meshes with more than a billion tetrahedra in about two minutes. The implementation uses simple OpenMP constructs.