Abstract
Mesh adaptation is a powerful way to minimise the computational cost of mesh based computation. It is particularly successful for multi-scale problems where the required mesh resolution can vary by orders of magnitude across the domain. The end result is local control over solution accuracy and reduced time to solution.
In the case of large scale simulations, where the time to solution is unacceptable or the memory requirements exceeds available RAM, mesh based computation is typically parallelised using domain decomposition methods using the Message Passing Interface (MPI). This allows a simulation to run in parallel on a distributed memory computer. While this has been a high successful strategy up until now, the drive towards low power multi- and many-core architectures means that an even higher degree of parallelism is required and the memory hierarchy exploited to maximise memory bandwidth.
For this reason application codes are increasingly adopting a hybrid parallel approach whereby decomposition methods, implemented using the Message Passing Interface (MPI), are applied for inter-node parallelisation, while a threaded programming model is used for intra-node parallelisation. Mesh adaptivity has been successfully parallelised using MPI by a number of groups, and can be implemented efficiently with few modifications to the serial code. However, thread-level parallelism is significantly more challenging because each thread modifies the mesh data and therefore must be carefully marshalled to avoid data races while still ensuring enough parallelism is exposed to achieve good parallel efficiency.
Here we describe a new thread-parallel algorithm for anisotropic mesh adaptation algorithms. For each mesh optimisation phase (refinement, coarsening, swapping and smoothing) we describe how independent sets of tasks are defined. We show how a deferred updates strategy can be used to update the mesh data structures in parallel and without data contention. We show that despite the complex nature of mesh adaptation and inherent load imbalances in the mesh adaptivity, good parallel efficiency can be achieved.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Agouzal, A., Lipnikov, K., Vassilevski, Y.: Adaptive generation of quasi-optimal tetrahedral meshes. East West J. Numer. Math. 7(4), 223–244 (1999)
Alauzet, F.: Size gradation control of anisotropic meshes. Finite Elem. Anal. Des. 46(1), 181–202 (2010)
Alauzet, F., Li, X., Seol, E.S., Shephard, M.S.: Parallel anisotropic 3D mesh adaptation by mesh modification. Eng. Comput. 21(3), 247–258 (2006)
Blelloch, G.E.: Prefix sums and their applications. Technical Report CMU-CS-90-190, School of Computer Science, Carnegie Mellon University (1990)
Buscaglia, G.C., Dari, E.A.: Anisotropic mesh optimization and its application in adaptivity. Int. J. Numer. Methods Eng. 40(22), 4119–4136 (1997)
Chen, L., Sun, P., Xu, J.: Optimal anisotropic meshes for minimizing interpolation errors in L p-norm. Math. Comput. 76(257), 179–204 (2007)
Coupez, T., Digonnet, H., Ducloux, R.: Parallel meshing and remeshing. Appl. Math. Model. 25(2), 153–175 (2000)
De Cougny, H., Shephard, M.S.: Parallel refinement and coarsening of tetrahedral meshes. Int. J. Numer. Methods Eng. 46(7), 1101–1125 (1999)
Dongarra, J.: What you can expect from exascale computing. In: International Supercomputing Conference (ISC’11), Hamburg (2011)
Field, D.A.: Laplacian smoothing and Delaunay triangulations. Commun. Appl. Numer. Methods 4, 709—712 (1988)
Freitag, L., Ollivier-Gooch, C.: A comparison of tetrahedral mesh improvement techniques. In: Fifth International Meshing Roundtable (1996)
Freitag, L., Jones, M., Plassmann, P.: An efficient parallel algorithm for mesh smoothing. In: Proceedings of the 4th International Meshing Roundtable, Sandia National Laboratories, Citeseer, pp. 47–58 (1995)
Freitag, L.F., Jones, M.T., Plassmann, P.E.: The scalability of mesh improvement algorithms. In: Improvement Algorithms. IMA Volumes in Mathematics and Its Applications, pp. 185–212. Springer, New York (1998)
Frey, P.J., Alauzet, F.: Anisotropic mesh adaptation for cfd computations. Comput. Methods Appl. Mech. Eng. 194(48), 5068–5082 (2005)
Gebremedhin, A.H., Manne, F.: Scalable parallel graph coloring algorithms. Concurrency Pract. Experience 12(12),1131–1146 (2000)
Gorman, G., Southern, J., Farrell, P., Piggott, M., Rokos, G., Kelly, P.: Hybrid OpenMP/MPI anisotropic mesh smoothing. In: Proceedings of the International Conference on Computational Science. Procedia Computer Science, vol. 9, pp. 1513–1522 (2012)
Li, X., Shephard, M., Beall, M.: 3D anisotropic mesh adaptation by mesh modification. Comput. Methods Appl. Mech. Eng. 194(48-49), 4915–4950 (2005)
Pain, C.C., Umpleby, A.P., de Oliveira, C.R.E., Goddard, A.J.H.: Tetrahedral mesh optimisation and adaptivity for steady-state and transient finite element calculations. Comput. Methods Appl. Mech. Eng. 190(29-30), 3771–3796 (2001)
Rabenseifner, R., Hager G, Jost, G.: Hybrid MPI/OpenMP parallel programming on clusters of multi-core SMP nodes. In: 17th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, 2009, pp. 427–436. IEEE (2009)
Rokos, G., Gorman, G., Kelly, P.H.J.: Accelerating anisotropic mesh adaptivity on nVIDIA’s CUDA using texture interpolation. In: Proceedings of the 17th International Conference on Parallel Processing - Volume Part II, Euro-Par’11, pp. 387–398. Springer, Berlin (2011). http://dl.acm.org/citation.cfm?id=2033408.2033453
Tam, A., Ait-Ali-Yahia, D., Robichaud, M., Moore, M., Kozel, V., Habashi, W.: Anisotropic mesh adaptation for 3D flows on structured and unstructured grids. Comput. Methods Appl. Mech. Eng. 189(4), 1205–1230 (2000)
Vasilevskii, Y., Lipnikov, K.: An adaptive algorithm for quasioptimal mesh generation. Comput. Math. Math. Phys. 39(9), 1468–1486 (1999)
Acknowledgements
The authors would like to thank Fujitsu Laboratories of Europe Ltd. and EPSRC grants EP/I00677X/1 and EP/L000407/1 for supporting this work.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Gorman, G.J., Rokos, G., Southern, J., Kelly, P.H.J. (2015). Thread-Parallel Anisotropic Mesh Adaptation. In: Perotto, S., Formaggia, L. (eds) New Challenges in Grid Generation and Adaptivity for Scientific Computing. SEMA SIMAI Springer Series, vol 5. Springer, Cham. https://doi.org/10.1007/978-3-319-06053-8_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-06053-8_6
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06052-1
Online ISBN: 978-3-319-06053-8
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)