×

Thread-parallel mesh improvement using face and edge swapping and vertex insertion. (English) Zbl 1443.65022

Summary: The purpose of this paper is three-fold. First, we devise a memory model for unstructured mesh data for efficient use of memory on parallel shared memory architectures, with the purpose of lowering the synchronization overhead between threads while avoiding race conditions. Second, we present a new thread-parallel edge and face swapping algorithm for two and three dimensional meshes using OpenMP for shared memory architectures. We show how removing the conflicts from the reconfiguration procedure by applying a vertex locking strategy can result in a near linear speed-up with parallel efficiency of close to one on two threads and 70% with 24 threads on shared-memory processors. Finally, we derive a parallel mesh generation and refinement module for shared memory architectures based on pre-existing serial modules by implementing Chernikov and Chrisochoides’ parallel insertion algorithm along with the two above tools. Experiments show a worst case parallel efficiency of 50% for parallel refinement with 24 threads.

MSC:

65D17 Computer-aided design (modeling of curves and surfaces)
65Y10 Numerical algorithms for specific classes of architectures
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Shewchuk, J. R., Delaunay refinement algorithms for triangular mesh generation, Comput. Geom., 22, 21-74, (2002) · Zbl 1016.68139
[2] Ruppert, J., A new and simple algorithm for quality 2-dimensional mesh generation, (Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms, (1993)), 83-92 · Zbl 0801.68163
[3] Ruppert, J., A Delaunay refinement algorithm for quality 2-dimensional mesh generation, J. Algorithms, 18, 548-585, (1995) · Zbl 0828.68122
[4] Sohler, C., Fast reconstruction of Delaunay triangulations, Comput. Geom., 31, 166-178, (2005) · Zbl 1115.68158
[5] Dyken, C.; Floater, M. S., Preferred directions for resolving the non-uniqueness of Delaunay triangulations, Comput. Geom., 34, 96-101, (2006) · Zbl 1140.52014
[6] Su, P.; Drysdale, R. L.S., A comparison of sequential Delaunay triangulation algorithms, Comput. Geom., 7, 361-385, (1997) · Zbl 1133.68466
[7] Chen, L.; Holst, M., Efficient mesh optimization schemes based on optimal Delaunay triangulation, Comput. Methods Appl. Mech. Eng., 200, 967-984, (2011) · Zbl 1225.65113
[8] Kreveld, M. V.; Loffler, M.; Silveira, R. I., Optimization for first order Delaunay triangulations, Comput. Geom., 43, 377-394, (2010) · Zbl 1186.65025
[9] Rineau, L.; Yvinec, M., A generic software design for Delaunay refinement meshing, Comput. Geom., 38, 100-110, (2007) · Zbl 1114.65310
[10] Shewchuk, J. R., Delaunay refinement mesh generation, (1997), School of Computer Science, Carnegie Mellon University, Ph.D. thesis
[11] Shewchuk, J. R., Triangle: engineering a 2D quality mesh generator and Delaunay triangulator, (Proceedings of the First ACM Workshop on Applied Computational Geometry, Towards Geometric Engineering, Philadelphia, Pennsylvania, (1996)), 124-133
[12] Ollivier-Gooch, C. F., GRUMMP version 0.7.1 User’s guide, (2017), Department of Mechanical Engineering, The University of British Columbia, Technical Report
[13] Chow, A. L., Parallel algorithms for geometric problems, (1980), University of Illinoise Urbana-Champain, USA, Ph.D. thesis
[14] Papadrakakis, M.; Stavroulakis, G.; Karatarakis, A., A new era in scientific computing: domain decomposition methods in hybrid CPU-GPU architectures, Comput. Methods Appl. Mech. Eng., 200, 1490-1508, (2011) · Zbl 1228.74092
[15] Chrisochoides, N. P., A new approach to parallel mesh generation and partitioning problems, Comput. Sci. Math. Softw., 335-359, (2002)
[16] Kadow, C., Adaptive dynamic projection-based partitioning for parallel Delaunay mesh generation algorithms, (SIAM Workshop on Combinatorial Scientific Computing, (2004))
[17] Linardakis, L., Parallel domain decoupling Delaunay method, SIAM J. Sci. Comput., (2004)
[18] Lintermann, A.; Schlimpert, S.; Grimmen, J.; Gunther, C.; Meinke, M.; Schroder, W., Massively parallel grid generation on HPC systems, Comput. Methods Appl. Mech. Eng., 277, 131-153, (2014) · Zbl 1423.76366
[19] Lo, S., Parallel Delaunay triangulation in three dimensions, Comput. Methods Appl. Mech. Eng., 240, 88-106, (2012) · Zbl 1253.65020
[20] Chrisochoides, N. P., A survey of parallel mesh generation methods, (Proceedings of the 14th International Meshing Roundtable, (2005))
[21] Cao, T. T.; Edelsbrunner, H.; Tan, T. S., Triangulations from topologically correct digital Voronoi diagrams, Comput. Geom., 48, 507-519, (2015) · Zbl 1329.65055
[22] Nave, D.; Chrisochoides, N. P.; Chew, L. P., Gauaranteed-quality parallel Delaunay refinement for restricted polyhedral domains, (Proceedings of the Eighteenth Annual Symposium on Computational Geometry, vol. 28, (2004)), 191-215 · Zbl 1059.65022
[23] Kohout, J.; Kolingerova, I.; Zara, J., Parallel Delaunay triangulation in E^{2} and E^{3} for computers with shared memory, Parallel Comput., 31, 491-522, (2005)
[24] Spielman, D. A.; Teng, S. H.; Ungor, A., Parallel Delaunay refinement: algorithms and analyses, Int. J. Comput. Geom. Appl., 17, (2007) · Zbl 1114.65024
[25] Luby, M., A simple parallel algorithm for the maximal independent set problem, SIAM J. Comput., 4, 1036-1053, (1986) · Zbl 0619.68058
[26] Chernikov, A. N.; Chrisochoides, N. P., Parallel guaranteed quality planar Delaunay mesh generation by concurrent point insertion, (14th Annual Fall Workshop on Computational Geometry, (2004))
[27] Chernikov, A. N.; Chrisochoides, N. P., Practical and efficient point insertion scheduling method for parallel guaranteed quality Delaunay refinement, (Proceedings of the 18th ACM Annual International Conference on Supercomputing, (2004))
[28] Chernikov, A. N.; Chrisochoides, N. P., Parallel 2D graded guaranteed quality Delaunay mesh refinement, (Proceedings of the 14th International Meshing Roundtable, (2005)) · Zbl 1125.65018
[29] Chernikov, A. N.; Chrisochoides, N. P., Parallel guaranteed quality Delaunay uniform mesh refinement, SIAM J. Sci. Comput., 28, 1907-1926, (2006) · Zbl 1125.65018
[30] Burstedde, C.; Wilcox, L. C.; Ghattas, O., P4est: scalable algorithms for parallel adaptive mesh refinement on forests of octrees, SIAM J. Sci. Comput., 33, 1103-1133, (2011) · Zbl 1230.65106
[31] Liang, X.; Ebeida, M. S.; Zhang, Y., Guaranteed-quality all-quadrilateral mesh generation with feature preservation, Comput. Methods Appl. Mech. Eng., 199, 2072-2083, (2010) · Zbl 1231.76243
[32] de Cougny, H. L., Parallel volume meshing using face removal and hierarchial repartitioning, Comput. Methods Appl. Mech. Eng., 174, 275-298, (1999) · Zbl 0963.76073
[33] Bowyer, A., Computing Dirichlet tessellation, Comput. J., 24, 167-171, (1981)
[34] Watson, D. F., Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes, Comput. J., 24, 167-172, (1981)
[35] Rokos, G.; Gorman, G. J.; Southern, J.; Kelly, P. H.J., A thread-parallel algorithm for anisotropic mesh adaptation, (2013), Parallel Computing · Zbl 1327.65256
[36] Batista, V. H.F.; Millman, D. L.; Pion, S.; Singler, J., Parallel geometric algorithms for multi-core computers, Comput. Geom., 43, 663-677, (2010) · Zbl 1344.68254
[37] Ollivier-Gooch, C. F., GRUMMP — generation and refinement of unstructured, mixed-element meshes in parallel, (1998-2017)
[38] Freitag, L. A.; Ollivier-Gooch, C. F., Tetrahedral mesh improvement using swapping and smoothing, Int. J. Numer. Methods Eng., 40, 3979-4002, (1997) · Zbl 0897.65075
[39] George, P.-L.; Borouchaki, H., Back to edge flips in three dimensions, (12th International Meshing Roundtable, (2003)), 393-402
[40] Ungor, A., Off-centers: a new type of Steiner points for computing size-optimal quality-guaranteed Delaunay triangulations, Comput. Geom., 42, 109-118, (2009) · Zbl 1155.65020
[41] Chernikov, A. N.; Chrisochoides, N. P., Generalized insertion region guides for Delaunay mesh refinement, SIAM J. Sci. Comput., 34, 1333-1350, (2012) · Zbl 1246.65137
[42] Edelsbrunner, H.; Guoy, D., Sink-insertion for mesh improvement, Int. J. Found. Comput. Sci., 13, 223-242, (2002) · Zbl 1066.65137
[43] Chernikov, A. N.; Chrisochoides, N. P., Three-dimensional Delaunay refinement for multi-core processors, (Proceedings of the 22nd ACM Annual International Conference on Supercomputing, (2008)) · Zbl 1238.65010
[44] Mellor-Crummey, J., Hpctoolkit, (2011)
[45] Si, H., Tetgen version 1.4.1, (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.