carrier image

A Two-Level Multithreaded Delaunay Kernel

Remacle, Jean-Francois, Vincent Bertranda, Christophe Geuzaine

24th International Meshing Roundtable, Elsevier Ltd., October 12-14 2015


24th International Meshing Roundtable
Austin, TX
October 12-14,2014

Universite catholique de Louvain, Institute of Mechanics, Materials and Civil Engineering (iMMC), Belgium
Universite de Liege, Department of Electrical Engineering and Computer Science, Belgium
Department of Computational and Applied Mathematics, Rice University

This paper presents a fine grain parallel version of the 3D Delaunay Kernel procedure using the OpenMP (Open Multi-Processing) API. A set S = {p1,} 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 point is then divided into M subsets Si, 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.30GHz with 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.

Download Full Paper (PDF Format)

Contact author(s) or publisher for availability and copyright information on above referenced article