Performance comparison and workload analysis of mesh untangling and smoothing algorithms.

*(English)*Zbl 07216464
Roca, Xevi (ed.) et al., Proceedings of the 27th International Meshing Roundtable (IMR), Albuquerque, NM, USA, October 1–5, 2018. Cham: Springer (ISBN 978-3-030-13991-9/hbk; 978-3-030-13994-0/pbk; 978-3-030-13992-6/ebook). Lecture Notes in Computational Science and Engineering 127, 385-404 (2019).

Summary: This paper compares methods for simultaneous mesh untangling and quality improvement that are based on repositioning the vertices. The execution times of these algorithms vary widely, usually with a trade-off between different parameters. Thus, computer performance and workloads are used to make comparisons. A range of algorithms in terms of quality metric, approach and formulation of the objective function, and optimization solver are considered. Among them, two new objective function formulations are proposed. Triangle and tetrahedral meshes and three processors architectures are also used in this study. We found that the execution time of vertex repositioning algorithms is more directly proportional to a new workload measure called mesh element evaluations than other workload measures such as mesh size or objective function evaluations. The comparisons are employed to propose a performance model for sequential algorithms. Using this model, the workload required by each mesh vertex is studied. Finally, the effects of processor architecture on performance are also analyzed.

For the entire collection see [Zbl 1417.65007].

For the entire collection see [Zbl 1417.65007].

##### MSC:

65M50 | Mesh generation, refinement, and adaptive methods for the numerical solution of initial value and initial-boundary value problems involving PDEs |

65N50 | Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs |

65Y10 | Numerical algorithms for specific classes of architectures |

PDF
BibTeX
XML
Cite

\textit{D. Benitez} et al., Lect. Notes Comput. Sci. Eng. 127, 385--404 (2019; Zbl 07216464)

Full Text:
DOI

##### References:

[1] | K. Barker, N. Chrisochoides, Practical performance model for optimizing dynamic load balancing of adaptive applications, in Proceedings of19^thIPDPS, pp. 28.a-28.b (2005) |

[2] | D. Benítez, J.M. Escobar, R. Montenegro, E. Rodríguez, Parallel performance model for vertex repositioning algorithms and application to mesh partitioning, in Proceedings of27^thInternational Meshing Roundtable (2018) |

[3] | M. Brewer, L. Diachin, P. Knupp, T. Leurent, D. Melander, The mesquite mesh quality improvement toolkit, in Proceedings of12^thInternational Meshing Roundtable, pp. 239-250 (2003) |

[4] | S. Browne, J. Dongarra, N. Garner, K. London, P. Mucci, A scalable cross-platform infrastructure for application performance tuning using hardware counters, in Proceedings of Supercomputing, Article 42 (IEEE Computer Society, Washington, 2000) |

[5] | Y. Che, L. Zhang, C. Xu, Y. Wang, W. Liu, Z. Wang, Optimization of a parallel CFD code and its performance evaluation on Tianhe1A. Comput. Inform. 33(6), 1377-1399 (2015) · Zbl 1413.65500 |

[6] | L. Diachin, P. Knupp, T. Munson, S. Shontz, A comparison of inexact newton and coordinate descent mesh optimization techniques, in Proceedings of13^thInternational Meshing Roundtable, pp. 243-254 (2004) |

[7] | J.M. Escobar, E. Rodríguez, R. Montenegro, G. Montero, J.M. González-Yuste, Simultaneous untangling and smoothing of tetrahedral meshes. Comput. Methods Appl. Mech. Eng. 192, 2775-2787 (2003) · Zbl 1037.65126 |

[8] | C. Geuzaine, J.F. Remacle, GMSH: a three-dimensional finite element mesh generator with built-in pre- and post-processing facilities. Int. J. Numer. Methods Eng. 79(11), 1309-1331 (2009) · Zbl 1176.74181 |

[9] | P. Knupp, Updating meshes on deforming domains: an application of the target-matrix paradigm. Commun. Numer. Methods Eng. 24, 467-476 (2007) · Zbl 1145.65105 |

[10] | D. Levinthal, Performance Analysis Guide for Intel Core i7 Processor and Intel Xeon 5500 Processors (Intel, Santa Clara, 2014) |

[11] | M. Livesu, A. Sheffer, N. Vining, M. Tarini, Practical hex-mesh optimization via edge-cone rectification. ACM Trans. Graph. 34(4), Article 141 (2015) |

[12] | R. Montenegro, J.M. Cascón, J.M. Escobar, E. Rodríguez, G. Montero, An automatic strategy for adaptive tetrahedral mesh generation. Appl. Numer. Math. 59(9), 2203-2217 (2009) · Zbl 1167.65456 |

[13] | D.A. Patterson, J.L. Hennessy, Computer Organization and Design: The Hardware/Software Interface, ARM edn. (Morgan Kaufmann Publishers Inc., Burlington, 2017) |

[14] | E. Ruiz-Girones, X. Roca, J. Sarrate, R. Montenegro, J.M. Escobar, Simultaneous untangling and smoothing of quadrilateral and hexahedral meshes using an object-oriented framework. Adv. Eng. Softw. 80, 12-24 (2015) |

[15] | S.P. Sastry, S.M. Shontz, Performance characterization of nonlinear optimization methods for mesh quality improvement. Eng. Comput. 28, 269-286 (2012) |

[16] | S.P. Sastry, S.M. Shontz, A parallel log-barrier method for mesh quality improvement and untangling. Eng. Comput. 30(4), 503-515 (2014) |

[17] | S.P. Sastry, S.M. Shontz, S.A. Vavasis, A log-barrier method for mesh quality improvement and untangling. Eng. Comput. 30(3), 315-329 (2014) |

[18] | R.B. Schnabel, Concurrent function evaluations in local and global optimization. CU-CS-345-86. Computer Science Technical Reports, 332 (University of Colorado, Boulder, 1986) · Zbl 0608.49019 |

[19] | D. Terpstra, H. Jagode, H. You, J. Dongarra, Collecting performance data with PAPI-C, in Tools for High Performance Computing 2009, pp. 157-173 (Springer, Berlin, 2010) |

[20] | C.S. Verman, |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.