Abstract
General purpose computing on Graphics Processor Units (GPGPU) can significantly reduce computational cost by performing massively parallel computing. The benefits of GPGPU have been exploited in mesh generation and mesh optimization. Mesh smoothing is one of the most popular approaches that are capable of improving mesh quality by repositioning nodes in meshes without altering the topology of meshes. In this paper, specifically aiming at Laplacian-based mesh smoothing, a generic paradigm for exploiting the power of GPU-acceleration is developed to improve the computational efficiency. The data layouts for representing mesh data structures on the GPU are first discussed; and then a practical solution to dealing with the data dependencies in the iterative smoothing procedure is introduced. Two forms of iteration in Laplacian smoothing (LS) are also analyzed, including the form that needs to swap intermediate nodal coordinates and the other form that does not swap data. In addition, the standard LS is implemented to demonstrate the effectiveness of the presented paradigm. Experimental results show that: on single and double precision, the GPU implementations developed using the data structures represented by aligned array-of-structures layout achieve the best efficiency. It is also demonstrated that the form that needs to swap intermediate nodal coordinates is always slower than the one that does not swap data.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Crespo, A.C.; Dominguez, J.M.; Barreiro, A.; Gomez-Gesteira, M.; Rogers, B.D.: GPUs, a new tool of acceleration in CFD: efficiency and reliability on smoothed particle hydrodynamics methods. PLoS One 6(6), e20685 (2011)
Giles M.B., Mudalige G.R., Spencer B., Bertolli C., Reguly I.: Designing OP2 for GPU architectures. J. Parallel Distrib. Comput. 73(11), 1451–1460 (2013)
Qi M., Cao T.T., Tan T.S.: Computing 2D constrained Delaunay triangulation using the GPU. IEEE T. Vis. Comput. Graph. 19(5), 736–748 (2013)
Shuai L., Guo X.H., Jin M.: GPU-based computation of discrete periodic centroidal Voronoi tessellation in hyperbolic space. Comput. Aided Des. 45(2), 463–472 (2013)
D’Amato J.P., Venere M.: A CPU–GPU framework for optimizing the quality of large meshes. J. Parallel Distrib. Comput. 73(8), 1127–1134 (2013)
Zegard T., Paulino G.H.: Toward GPU accelerated topology optimization on unstructured meshes. Struct. Multidiscip. Optim. 48(3), 473–485 (2013)
NVIDIA: CUDA C Programming Guide v5.5. http://docs.nvidia.com/cuda/cuda-c-programming-guide/ (2013)
Munshi, A.: The OpenCL Specification, v2.0. https://www.khronos.org/registry/cl/specs/opencl-2.0.pdf (2013)
Abal Abas Z., Salleh S., Manan Z.: Extended advancing front technique for the initial triangular mesh construction on a single coil for radiative heat transfer. Arab. J. Sci. Eng. 38(9), 2245–2262 (2013)
Freitag L., Ollivier-Gooch C.: A cost/benefit analysis of simplicial mesh improvement techniques as measured by solution efficiency. Int. J. Comput. Geom. Appl. 10(04), 361–382 (2000)
Shewchuk, J.R.: What is a good linear finite element? Interpolation, conditioning, anisotropy, and quality measures (preprint). University of California at Berkeley (2002)
Owen, S.J.: A survey of unstructured mesh generation technology. In: Proceedings of the 7th International Meshing Roundtable, vol. 3, pp. 239–267 (1998)
Freitag L., Jones M., Plassmann P.: A parallel algorithm for mesh smoothing. SIAM J. Sci. Comput. 20(6), 2023–2040 (1999)
Jiao, X.; Alexander, P.: Parallel Feature-Preserving Mesh Smoothing, Lecture Notes in Computer Science, vol. 3483, chap. 123, pp. 1180–1189. Springer, Berlin (2005)
Gorman G.J., Southern J., Farrell P.E., Piggott M.D., Rokos G., Kelly P.H.J.: Hybrid openmp/mpi anisotropic mesh smoothing. Procedia Comput. Sci. 9, 1513–1522 (2012)
Benłtez, D.; Rodrłguez, E.; Escobar, J.; Montenegro, R.: Performance Evaluation of a Parallel Algorithm for Simultaneous Untangling and Smoothing of Tetrahedral Meshes, chap. 32, pp. 579–598. Springer International Publishing (2014)
Sastry, S.; Shontz, S.: A parallel log-barrier method for mesh quality improvement and untangling. Eng. Comput. 30(4), 503–515 (2014)
D’Amato J.P., Lotito P.: Mesh optimization with volume preservation using GPU. Lat. Am. Appl. Res. 41(3), 291–297 (2011)
Heuveline, V.; Lukarski, D.; Trost, N.; Weiss, J.P.: Parallel Smoothers for Matrix-Based Geometric Multigrid Methods on Locally Refined Meshes Using Multicore CPUs and GPUs, Lecture Notes in Computer Science, vol. 7174, chap. 14, pp. 158–171. Springer, Berlin (2012)
Monch T., Lawonn K., Kubisch C., Westermann R., Preim B.: Interactive mesh smoothing for medical applications. Comput. Graph Forum 32(8), 110–121 (2013)
Herrmann L.R.: Laplacian-isoparametric grid generation scheme. J. Eng. Mech. Div. ASCE 102(5), 749–907 (1976)
Blacker T.D., Stephenson M.B.: Paving: a new approach to automated quadrilateral mesh generation. Int. J. Numer. Methods Eng. 32(4), 811–847 (1991)
Vollmer J., Mencl R., Mller H.: Improved Laplacian smoothing of noisy surface meshes. Comput. Graph Forum 18(3), 131–138 (1999)
Freitag, L.A.: On combining Laplacian and optimization-based mesh smoothing techniques. In: Trends in Unstructured Mesh Generation, pp. 37–43 (1997)
Canann, S.A.; Tristano, J.R.; Staten, M.L.: An approach to combined Laplacian and optimization-based smoothing for triangular, quadrilateral, and quad-dominant meshes. In: Proceedings of 7th International Meshing Roundtable, pp. 479–494 (1998)
Farber, R.: CUDA Application Design and Development. Morgan Kaufmann (2011)
Bell, N.; Hoberock, J.: Thrust: Productivity-Oriented Library for CUDA, chap. 26, pp. 359–371. Morgan Kaufmann (2011)
Govender, N.; Wilke, D.N.; Kok, S.; Els, R.: Development of a convex polyhedral discrete element simulation framework for NVIDIA Kepler based GPUs. J. Comput. Appl. Math. 270, 386–400 (2013)
Mudalige G.R., Giles M.B., Thiyagalingam J., Reguly I.Z., Bertolli C., Kelly P.H.J., Trefethen A.E.: Design and initial performance of a high-level unstructured mesh framework on heterogeneous parallel systems. Parallel Comput. 39(11), 669–692 (2013)
Mistry, P.; Schaa, D.; Jang, B.; Kaeli, D.; Dvornik, A.; Meglan, D.: Data Structures and Transformations for Physically Based Simulation on a GPU, Lecture Notes in Computer Science, vol. 6449, chap. 17, pp. 162–171. Springer, Berlin (2011)
Strzodka, R.: Abstraction for AoS and SoA layout in C++, pp. 429–441. Morgan Kaufmann (2011)
Strzodka R.: Data layout optimization for multi-valued containers in OpenCL. J. Parallel Distrib. Comput. 72(9), 1073–1082 (2012)
Sung, I.J.; Liu, G.D.; Hwu, W.M.W.: DL: A data layout transformation system for heterogeneous computing. In: Innovative Parallel Computing (InPar), pp. 1–11. IEEE (2012)
Shewchuk, J.R.: Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator. In: Selected Papers from the Workshop on Applied Computational Geormetry, Towards Geometric Engineering, FCRC ’96/WACG ’96, pp. 203–222. Springer, London (1996)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mei, G., Tipper, J.C. & Xu, N. A Generic Paradigm for Accelerating Laplacian-Based Mesh Smoothing on the GPU. Arab J Sci Eng 39, 7907–7921 (2014). https://doi.org/10.1007/s13369-014-1406-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13369-014-1406-y