Abstract
A new parallel algorithm for simultaneous untangling and smoothing of tetrahedral meshes is proposed in this paper. We provide a detailed analysis of its performance on shared-memory many-core computer architectures. This performance analysis includes the evaluation of execution time, parallel scalability, load balancing, and parallelism bottlenecks. Additionally, we compare the impact of three previously published graph coloring procedures on the performance of our parallel algorithm. We use six benchmark meshes with a wide range of sizes. Using these experimental data sets, we describe the behavior of the parallel algorithm for different data sizes. We demonstrate that this algorithm is highly scalable when it runs on two different high-performance many-core computers with up to 128 processors. However, some parallel deterioration is observed. Here, we analyze the main causes of this parallel deterioration.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Batdorf, M., Freitag, L.A., Ollivier-Gooch, C.: Computational study of the effect of unstructured mesh quality on solution efficiency. Presented at the 13th Annual AIAA Computational Fluid Dynamics Conference, AIAA (1997)
Bazaraa, M., Sherali, H., Shetty, C.M.: Nonlinear Programming. Theory and Algorithms. Wiley (1993)
Bozdag, D., Gebremedhin, A., Manne, F., Boman, E., Catalyurek, U.: A framework for scalable greedy coloring on distributed memory parallel computers. Journal of Parallel and Distributed Computing 68(4), 515–535 (2008)
Bronevetsky, G., Gyllenhaal, J.C., Supinski, B.R.: Clomp: Accurately characterizing OpenMP application overheads. Int. J. Parallel Programming 37(3), 250–265 (2009)
Browne, S., Dongarra, J., Garner, N., London, K., Mucci, P.: A scalable cross-platform infrastructure for application performance tuning using hardware counters. In: Proc. 2000 ACM/IEEE Conference on Supercomputing. IEEE Computer Society (2000)
Cascón, J.M., Montenegro, R., Escobar, J.M., Rodríguez, E., Montero, G.: A new meccano technique for adaptive 3-D triangulation. In: Proc. of the 16th International Meshing Roundtable, pp. 103–120. Springer, Berlin (2007)
Cascón, J.M., Montenegro, R., Escobar, J.M., Rodríguez, E., Montero, G.: The meccano method for automatic tetrahedral mesh generation of complex genus-zero solids. In: Proc. 18th International Meshing Roundtable, pp. 463–480. Springer, Berlin (2009)
Chapman, B., Jost, G., van der Pas, R.: Using OpenMP: Portable Shared Memory Parallel Programming. The MIT Press (2007)
Dennis, J.E., Schnabel, R.B.: Numerical methods for unconstrained optimization and nonlinear equations. Society for Industrial and Applied Mathematics, SIAM (1996)
Dompierre, J., Labbé, P., Guibault, F., Camarero, R.: Proposal of benchmarks for 3D unstructured tetrahedral mesh optimization. In: Proc. of the 7th International Meshing Roundtable, pp. 459–478. Sandia National Laboratories, Dearborn (1998)
Ekman, P.: Studying program performance on the Itanium 2 with pfmon (2003), www.pdc.kth.se/~pek/ia64-profiling.txt
Escobar, J.M., Rodríguez, E., Montenegro, R., Montero, G., González-Yuste, J.M.: Simultaneous untangling and smoothing of tetrahedral meshes. Comp. Meth. Appl. Mech. Eng. 192, 2775–2787 (2003)
Escobar, J.M., Rodríguez, E., Montenegro, R., Montero, G., González-Yuste, J.M.: SUS Code - Simultaneous Mesh Untangling and Smoothing Code (2010), http://www.dca.iusiani.ulpgc.es/proyecto2012-2014/html/Software.html
FINIS TERRAE Supercomputer, http://archivo.cesga.es/content/view/917/115/lang,en
Freitag, L., Jones, M.T., Plassmann, P.E.: A parallel algorithm for mesh smoothing. SIAM J. Sci. Comput. 20(6), 2023–2040 (1999)
Frey, P.J., George, P.L.: Mesh Generation: Application to Finite Elements, 2nd edn. ISTE, London (2010)
Intel, Intel® Itanium® 2 Processor Reference Manual. For software development and optimization. Intel, Order Number: 251110-003 (2004)
Intel Manycore Testing Laboratory, http://software.intel.com/en-us/intel-manycore-testing-lab
Interoperable Technologies for Advanced Petascale Simulations, http://www.itaps.org/
Jarp, S.: A Methodology for using the Itanium 2 Performance Counters for Bottleneck Analysis. Tech-Report HP Labs (2002)
Jiao, X., Alexander, P.J.: Parallel feature-preserving mesh smoothing. In: Gervasi, O., Gavrilova, M.L., Kumar, V., Laganá, A., Lee, H.P., Mun, Y., Taniar, D., Tan, C.J.K. (eds.) ICCSA 2005. LNCS, vol. 3483, pp. 1180–1189. Springer, Heidelberg (2005)
Jones, M.T., Plassmann, P.E.: A parallel graph coloring heuristic. SIAM J. Sci. Comput. 14(3), 654–669 (1993)
Kim, J., Panitanarak, T., Shontz, S.M.: A multiobjective mesh optimization framework for mesh quality improvement and mesh untangling. International Journal of Numerical Methods in Engineering 94(1), 20–42 (2013)
Knupp, P.M.: Algebraic mesh quality metrics. SIAM J. Sci. Comput. 23(1), 193–218 (2001)
Kossaczky, I.: A recursive approach to local mesh refinement in two and three dimensions. J. Comput. Appl. Math. 55, 275–288 (1994)
Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing 4, 1036–1053 (1986)
Madden, P.H.: Dispelling the myths of parallel computing. IEEE Design & Test of Computers. IEEE Computer Society Digital Library. IEEE Computer Society (2012)
Montenegro, R., Cascón, J.M., Escobar, J.M., Rodríguez, E., Montero, G.: An automatic strategy for adaptive tetrahedral mesh generation. Appl. Num. Math. 59(9), 2203–2217 (2009)
Montenegro, R., Cascón, J.M., Rodríguez, E., Escobar, J.M., Montero, G.: The meccano method for automatic three-dimensional triangulation and volume parametrization of complex solids. In: Developments and Applications in Engineering Computational Technology, pp. 19–48. Saxe-Coburg Publications, Stirling (2010)
Shape benchmark repositories: Cyberware ( www.cyberware.com ), The Stanford 3D Scanning Repository ( http://graphics.stanford.edu/data/3Dscanrep ), GAMMA ( www-roc.inria.fr/gamma/gamma/download/download.php )
Shontz, S.M., Knupp, P.: The effect of vertex reordering on 2D local mesh optimization efficiency. In: 17th International Meshing Roundtable, pp. 107–124 (2008)
Shontz, S.M., Nistor, D.M.: CPU-GPU algorithms for triangular surface mesh simplification. In: Jiao, X., Weill, J.-C. (eds.) Proceedings of the 21st International Meshing Roundtable, vol. 123, pp. 475–492. Springer, Heidelberg (2013)
Uncmin++ library, http://www.smallwaters.com/software/cpp/uncmin.html
Yeo, Y.I., Ni, T., Myles, A., Goel, V., Peters, J.: Parallel smoothing of quad meshes. Vis. Comput. 25(8), 757–769 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Benítez, D., Rodríguez, E., Escobar, J.M., Montenegro, R. (2014). Performance Evaluation of a Parallel Algorithm for Simultaneous Untangling and Smoothing of Tetrahedral Meshes. In: Sarrate, J., Staten, M. (eds) Proceedings of the 22nd International Meshing Roundtable. Springer, Cham. https://doi.org/10.1007/978-3-319-02335-9_32
Download citation
DOI: https://doi.org/10.1007/978-3-319-02335-9_32
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-02334-2
Online ISBN: 978-3-319-02335-9
eBook Packages: EngineeringEngineering (R0)