Parallel Constrained Delaunay Mesh Generation

Summary	Delaunay refinement is a widely used method for the construction of guaranteed quality triangular and tetrahedral meshes. We present an algorithm and a software for the parallel constrained Delaunay mesh generation in two dimensions. Our approach is based on the decomposition of the original mesh generation problem into N smaller subproblems which are meshed in parallel. The parallel algorithm is asynchronous with small messages which can be aggregated and exhibits low communication costs. On a heterogeneous cluster of more than 100 processors our implementation can generate over one billion triangles in less than 3 minutes, while the single-node performance is comparable to that of the fastest to our knowledge sequential guaranteed quality Delaunay meshing library (Triangle). The Chesapeake bay model decomposed into 1024 subdomains, which are mapped onto 8 processes. The assignment of subdomains to processes is shown with different colors. The scaled speedup measurements. The number of triangles is approximately 10P, i.e., for 2 processors 20M, and for 144 processors about 1.4B.
Download	pcdm-1.0.tgz meDDec Triangle Exact Arithmetic And Robust Geometric Predicates Metis
Related papers:	Algorithm 872: Parallel 2D Constrained Delaunay Mesh Generation. Andrey Chernikov and Nikos Chrisochoides. ACM Transactions on Mathematical Software (Vol. 34, No. 1, pp. 6-25), January 2008. Multigrain Parallel Delaunay Mesh Generation: Challenges and Opportunities for Multithreaded Architectures. Christos Antonopoulos, Xiaoning Ding, Andrey Chernikov, Filip Blagojevic, Dimitris Nikolopoulos, and Nikos Chrisochoides. 19th ACM International Conference on Supercomputing, pp. 367-376. Cambridge, MA, June 2005. A Load Balancing Framework for Adaptive and Asynchronous Applications. Kevin Barker, Andrey Chernikov, Nikos Chrisochoides, and Keshav Pingali. IEEE Transactions on Parallel and Distributed Systems (Vol. 15, No. 2, pp. 183-192), February 2004. A Multigrain Delaunay Mesh Generation Method for Multicore SMT-based Architectures. Christos Antonopoulos, Filip Blagojevic, Andrey Chernikov, Nikos Chrisochoides, and Dimitris Nikolopoulos. Journal on Parallel and Distributed Computing (Vol. 69, No. 7, pp. 589-600), 2009. Algorithm, Software, and Hardware Optimizations for Delaunay Mesh Generation on Simultaneous Multithreaded Architectures. Christos Antonopoulos, Filip Blagojevic, Andrey Chernikov, Nikos Chrisochoides, and Dimitris Nikolopoulos. Journal on Parallel and Distributed Computing (Vol. 69, No. 7, pp. 601-612), 2009. Experience with Memory Allocators for Parallel Mesh Generation on Multicore Architectures. Andrey Chernikov, Christos Antonopoulos, Nikos Chrisochoides, Scott Schneider, and Dimitris Nikolopoulos. 10th International Conference on Numerical Grid Generation in Computational Field Simulations, Published on CD-ROM. Forth, Crete, Greece, September 2007. Parallel Out-of-Core Constrained Delaunay Mesh Generation. Andriy Kot, Andrey Chernikov, and Nikos Chrisochoides. 3rd IEEE International Workshop on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications, pp. 183-190. Sofia, Bulgaria, September 2005.