Three-dimensional delaunay refinement for multi-core processors

ABSTRACT

We develop the first ever fully functional three-dimensional guaranteed quality parallel graded Delaunay mesh generator. First, we prove a criterion and a sufficient condition of Delaunay-independence of Steiner points in three dimensions. Based on these results, we decompose the iteration space of the sequential Delaunay refinement algorithm by selecting independent subsets from the set of the candidate Steiner points without resorting to rollbacks. We use an octree which overlaps the mesh for a coarse-grained decomposition of the set of candidate Steiner points based on their location. We partition the worklist containing poor quality tetrahedra into independent lists associated with specific separated leaves of the octree. Finally, we describe an example parallel implementation using a publicly available state-of-the art sequential Delaunay library (Tetgen). This work provides a case study for the design of abstractions and parallel frameworks for the use of complex labor intensive sequential codes on multicore architectures.

REFERENCES

• 1: http://www.distene.com/en/build/index.html. Accessed on Jan. 13, 2008.
• 2: Christos D. Antonopoulos , Xiaoning Ding , Andrey Chernikov , Filip Blagojevic , Dimitrios S. Nikolopoulos , Nikos Chrisochoides, Multigrain parallel Delaunay Mesh generation: challenges and opportunities for multithreaded architectures, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088198]
• 3: G. E. Blelloch, J. Hardwick, G. L. Miller, and D. Talmor. Design and implementation of a practical parallel Delaunay algorithm. Algorithmica, 24:243--269, 1999.
• 4: A. Bowyer. Computing Dirichlet tesselations. Computer Journal, 24:162--166, 1981.
• 5: Paul B. Callahan , S. Rao Kosaraju, A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields, Journal of the ACM (JACM), v.42 n.1, p.67-90, Jan. 1995 [doi>10.1145/200836.200853]
• 6: S.-W. Cheng, T. K. Dey, and T. Ray. Weighted Delaunay refinement for polyhedra with small angles. In Proceedings of the 14th International Meshing Roundtable, pages 325--342, San Diego, CA, Sept. 2005. Springer.
• 7: A. N. Chernikov and N. P. Chrisochoides. Generalized Delaunay mesh refinement: From scalar to parallel. In Proceedings of the 15th International Meshing Roundtable, pages 563--580, Birmingham, AL, Sept. 2006. Springer.
• 8: Andrey N. Chernikov , Nikos P. Chrisochoides, Parallel Guaranteed Quality Delaunay Uniform Mesh Refinement, SIAM Journal on Scientific Computing, v.28 n.5, p.1907-1926, September 2006 [doi>10.1137/050625886]
• 9: A. N. Chernikov and N. P. Chrisochoides. Three-dimensional semi-generalized point placement method for Delaunay mesh refinement. In Proceedings of the 16th International Meshing Roundtable, pages 25--44, Seattle, WA, Oct. 2007. Springer.
• 10: L. Paul Chew, Guaranteed-quality mesh generation for curved surfaces, Proceedings of the ninth annual symposium on Computational geometry, p.274-280, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161150]
• 11: L. Paul Chew, Guaranteed-quality Delaunay meshing in 3D (short version), Proceedings of the thirteenth annual symposium on Computational geometry, p.391-393, June 04-06, 1997, Nice, France [doi>10.1145/262839.263018]
• 12: H. L. de Cougny, M. S. Shephard, and C. Ozturan. Parallel three-dimensional mesh generation. Computing Systems in Engineering, 5:311--323, 1994.
• 13: B. N. Delaunay. Sur la sphere vide. Izvestia Akademia Nauk SSSR, VII Seria, Otdelenie Mataematicheskii i Estestvennyka Nauk, 7:793--800, 1934.
• 14: W. H. Frey. Selective refinement: A new strategy for automatic node placement in graded triangular meshes. International Journal for Numerical Methods in Engineering, 24(11):2183--2200, 1987.
• 15: P.-L. George and H. Borouchaki. Delaunay Triangulation and Meshing. Application to Finite Elements. HERMES, 1998.
• 16: Milind Kulkarni , Keshav Pingali , Bruce Walter , Ganesh Ramanarayanan , Kavita Bala , L. Paul Chew, Optimistic parallelism requires abstractions, ACM SIGPLAN Notices, v.42 n.6, June 2007
• 17: Xiang-Yang Li, Generating well-shaped d-dimensional Delaunay meshes, Theoretical Computer Science, v.296 n.1, p.145-165, 4 March 2003 [doi>10.1016/S0304-3975(02)00437-1]
• 18: Leonidas Linardakis , Nikos Chrisochoides, Algorithm 870: A static geometric Medial Axis domain decomposition in 2D Euclidean space, ACM Transactions on Mathematical Software (TOMS), v.34 n.1, p.1-28, January 2008 [doi>10.1145/1322436.1322440]
• 19: R. Lohner and J. R. Cebral. Parallel advancing front grid generation. In Proceedings of the 8th International Meshing Roundtable, pages 67--74, South Lake Tahoe, CA, 1999.
• 20: Gary L. Miller , Dafna Talmor , Shang-Hua Teng , Noel Walkington, A Delaunay based numerical method for three dimensions: generation, formulation, and partition, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.683-692, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225286]
• 21: Démian Nave , Nikos Chrisochoides , L. Paul Chew, Guaranteed: quality parallel delaunay refinement for restricted polyhedral domains, Proceedings of the eighteenth annual symposium on Computational geometry, p.135-144, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513418]
• 22: Leonid Oliker , Rupak Biswas, Parallelization of a dynamic unstructured application using three leading paradigms, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.39-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331571]
• 23: I. Pivkin, E. Hueso, R. Weinstein, D. Laidlaw, S. Swartz, and G. Karniadakis. Simulation and visualization of air flow around bat wings during flight. In Proceedings of the International Conference on Computational Science, pages 689--694, Atlanta, GA, 2005.
• 24: Kleanthis Psarris , Konstantinos Kyriakopoulos, The impact of data dependence analysis on compilation and program parallelization, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782843]
• 25: Jonathan Richard Shewchuk, Tetrahedral mesh generation by Delaunay refinement, Proceedings of the fourteenth annual symposium on Computational geometry, p.86-95, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276894]
• 26: H. Si. Tetgen version 1.4.1. http://tetgen.berlios.de/. Accessed on Aug. 3, 2006.
• 27: H. Sutter. The free lunch is over: A fundamental turn toward concurrency in software. Dr. Dobb's Journal, 30(3), Mar. 2005.
• 28: Robert A. Van Engelen , Kyle A. Gallivan, The gSOAP Toolkit for Web Services and Peer-to-Peer Computing Networks, Proceedings of the 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid, p.128, May 21-24, 2002
• 29: D. F. Watson. Computing the n-dimensional Delaunay tesselation with application to Voronoi polytopes. Computer Journal, 24:167--172, 1981.
• 30: C. Wen and K. Yelick. Compiling sequential programs for speculative parallelism. In Proceedings of the International Conference on Parallel and Distributed Systems, Taiwan, Dec. 1993.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
cots software, delaunay triangulation, mesh generation, multicore architectures, parallel scientific computing