Performance evaluation of a parallel algorithm for simultaneous untangling and smoothing of tetrahedral meshes

Performance Evaluation of a Parallel Algorithm for Simultaneous Untangling and Smoothing of Tetrahedral Meshes Domingo Benítez1,2, Eduardo Rodríguez1,2, José María Escobar2 and Rafael Montenegro2 1 Departamento de Informática y Sistemas, University of Las Palmas de Gran Canaria, Spain 2 University Institute for Intelligent Systems and Numerical Applications in Engineering, SIANI, University of Las Palmas de Gran Canaria, Spain {dbenitez,erodriguez,jmescobar,rmontenegro}@siani.es, http://www.dca.iusiani.ulpgc.es/proyecto2012-2014 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. 1 Introduction It is well known that the mesh and its quality can greatly impact the accuracy of simulations, as well as solver efficiency [1]. Frequently, the automatic mesh generation tools produce meshes with inverted or poorly shaped elements. To obtain high-quality meshes, often scientists must untangle and improve the quality of meshes before or during the numerical analysis [23]. We proposed a mesh optimization method that simultaneous untangle and smooth tetrahedral meshes [12,13]. When this method is applied using conventional non-parallel programs to large and/or tangled meshes, the wall-clock time may be extremely high. Our optimization method can be applied if higher performance could be achieved such as scientific and engineering applications that use 3D discretization methods to numerically solve partial differential equations [15,16]. In this paper, we propose a new parallel algorithm for simultaneously untangling and smoothing tetrahedral meshes. Its goal is to reduce execution time effi- ciently. In addition, a performance evaluation of the proposed parallel algorithm on many-core computers is described. It includes the analysis of the scalability, parallel efficiency, load balancing, performance bottlenecks, and influence of graph coloring algorithms on the performance of our new parallel algorithm. Given that meshes which are used for PDE simulations are becoming larger all of the time, it is becoming necessary to have parallel algorithms for mesh generation and optimization. To the author’s knowledge, there are currently no parallel mesh untangling algorithms or parallel simultaneous mesh untangling and smoothing techniques in the literature. Previous studies on parallel algorithms for mesh smoothing problems include the work of Jiao and Alexander [21] that is applied to triangulated surfaces. Their algorithm was implemented on distributed-memory computers with up to 128 processors and it was shown 43% of maximum parallel efficiency. Yeo et al [34] also proposed an algorithm for smoothing quad meshes that fits well into parallel streams and was mapped to a GPU. They applied their algorithm to real-time processing of surface models and showed a performance comparison with other GPU algorithms. Freitag et al [15] relied on theoretical shared-memory models without a real implementation on shared-memory multicore systems, although they presented results on distributed-memory computers. Shontz and Nistor have published another similar study [32], which provides performance results for mesh simplification algorithms on GPUs. However, they do not mention if a graph coloring algorithm was used to find mesh vertices that have not computational dependency. Several mesh optimization algorithms are implemented in parallel routines of the petascale meshing software tools provided by the ITAPS project [19]. These tools are used in distributed-memory computers. The rest of the paper is organized as follows. Section 2 summarizes the mathematical foundation of the 3D simultaneous untangling and smoothing algorithm. Section 3 describes the new parallel algorithm of this optimization method. The experimental methodology that we used to evaluate the performance of the parallel algorithm is explained in Section 4. Section 5 analyzes the performance scalability. Section 6 describes the influence of three previously published graph coloring algorithms on the parallel performance. Load unbalancing and other performance bottlenecks are studied in Section 7 and 8, respectively. Finally, the main conclusions and future work are discussed in Section 9. 2 Our approach for simultaneous untangling and smoothing of tetrahedral meshes Let us consider M to be a tetrahedral mesh. Usual techniques to improve the quality of a valid mesh, that is, one that does not contain inverted tetrahedra, are based upon local smoothing [10]. In short, these techniques consist of finding the new position that each inner mesh node v must hold, in such a way that they optimize an objective function (boundary vertices are fixed during all the mesh optimization process). Such a function is based on a certain measurement of the quality of the local submesh Nv ⊂M that is formed by the set of tetrahedra connected to the free node v. As it is a local optimization process, we cannot guarantee that the final mesh is globally optimal. Nevertheless, after repeating this process several times for all the nodes of the mesh M, quite satisfactory results can be achieved. The algebraic quality metrics proposed by Knupp [24] provide us an appropriate framework to define objective functions. Specifically, the one used in this paper has the generic form, (1) where n is the number of elements in Nv, p is usually chosen as 1 or 2 and η i = 1 / qi is the distortion of the i-th tetrahedron of Nv and qi is the chosen corresponding algebraic element quality measure. In particular, we have implemented the mean ratio quality measure of a tetrahedron given by q = 3 σ2/3 / |S|2, where |S| is the Frobenius norm of matrix S associated to the affine map from the ideal element (usually an equilateral tetrahedron) to the physical one, and σ = det(S). Specifically, the weighted Jacobian matrix S is defined as S =AW -1, being A = (x1-x0, x2-x0, x3-x0) the Jacobian matrix and xk, k = 0,1,2,3 the coordinates of the vertices of the tetrahedron. The constant matrix W is derived from the ideal element (see [12]). Objective functions like (1) are appropriate to improve the quality of a valid mesh and avoid a valid mesh to be inverted, but they do not work properly when there are inverted elements ( σ < 0). This is because they present singularities (barriers) when any tetrahedron of Nv changes the sign of its Jacobian matrix. In [12] we proposed a suitable modification of the objective function such that it is regular all over R3. It consists of substituting the term σ in the quality metrics by the positive and increasing function . When a feasible region exists (subset of R3 where v could be placed, being Nv a valid submesh), the minima of the original and modified objective functions are very close and, when this region does not exist, the minimum of the modified objective function is located in such a way that it tends to untangle Nv. In this way, we can use any standard and efficient unconstrained optimization method to find the minimum of the modified objective function [2]. In this paper, we have used the Newton unconstrained optimization method that is implemented with UNCMIN++ library [9,33]. 3 A novel parallel algorithm In Algorithm 1, a sequential algorithm called SUS for our simultaneous untangling and smoothing of tetrahedral meshes can be seen. The inputs of the sequential algorithm are the followings: M is a tangled tetrahedral mesh, maxIter is the maximum number of untangling and smoothing iterations, Nv is the set of tetrahedra connected to the free node v, is the initial position of the free node, is its position after optimization, which is implemented with the procedure OptimizeNode, Q measures the lowest quality of a tetrahedron of M when the above mentioned q tetrahedron quality function is used, and quality is a function that provides the minimum quality of mesh M (it is 0 if any tetrahedral is tangled). The output of the algorithm is an untangled and smoothed mesh M, whose minimum quality must be larger than a user-specified threshold λ . This algorithm iterates over all the mesh vertices in some order and adjusts at each step the coordinates of the free node v. A code for this algorithm can be downloaded at [13]. In Algorithm 2, a novel parallel algorithm for our mathematical method for simultaneous untangling and smoothing of tetrahedral meshes is shown. The main procedure is called pSUS. Its inputs M, maxIter, Nv, , OptimizeNode, , Q, λ , quality have the same meanings as described for Algorithm 1. Algorithm 1. Sequential algorithm (SUS) for the simultaneous untangling and smoothing of a tetrahedral mesh M. 1: function OptimizeNode( ,Nv) 2: Optimize objective function ( ) 3: end function 4: procedure SUS 5: Q ← 0 6: k ← 0 7: while Q < λ and k < maxIter do 8: for each vertex v ∈ M do 9: ← OptimizeNode( ,Nv) 10: end do 11: Q ← quality(M) 12: k ← k+1 13: end do 14: end procedure The parallel algorithm has to prevent two adjacent vertices from being simultaneously untangled and smoothed on different processors. On the contrary, new inverted mesh elements may be created [15]. Thus, when the sequential Algorithm 1 is parallelized, a computational dependency appears between adjacent vertices because one vertex needs to be optimized after the other. This justifies the use in our parallel algorithm of a graph coloring algorithm to find vertices of a tetrahedral mesh M that have not computational dependency. Graph coloring is implemented with procedure Coloring, which is expressed as follows. Let G=(V,E) be the graph associated to the tetrahedral mesh M, where V is the set of vertices of the mesh (without information of vertex spatial coordinates) and E is the set of their edges, then Coloring is a procedure that is used to color the graph G such that two adjacent vertices do not have the same color. Then, an independent set, or color, Ii is a set of non-adjacent vertices (i.e., they do not share a common edge). That is, v ∈ Ii => v ∉ adj(Ii,G=(V,E)), where adj(Ii,G=(V,E)) is the set of vertices that are adjacent to all vertex j ∈ Ii being j ≠ v. In this way the graph G of a tetrahedral mesh M is colored and partitioned in a disjoint sequence of independent sets, I={I1,I2,…}. We implemented three different and previously published graph coloring methods called “C1”, “C2”, and “C3”. C1 is a vertex coloring method that has been used for parallel mesh smoothing [15]. It requires the use of the asynchronous coloring heuristic proposed by Jones and Plassmann [22]. In particular, we used its serial version for C1. This heuristic is based on Luby’s Monte Carlo algorithm for determining the maximal independent set [26]. C2 is a parallel version of C1 that was also proposed by Jones and Plassmann [22] for distributed-memory computers. We additionally adapted C2 to multithread/multicore computers. C3 is an iterative parallel greedy coloring algorithm that was proposed by Bozdag et al [3]. Section 6 compares the impact of these graph coloring algorithms on the performance of our parallel optimization method. Algorithm 2. Parallel algorithm (pSUS) for the simultaneous untangling and smoothing of a tetrahedral mesh M. 1: procedure Coloring(G=(V,E)) 2: G is partitioned into independent sets I using C1, C2 or C3 coloring algorithm 3: end procedure 4: function OptimizeNode( ,Nv) 5: Optimize objective function K( ) 6: end function 7: procedure pSUS 8: I ← Coloring(G=(V,E)) 9: k ← 0 10: Q ← 0 11: while Q < λ and k < maxIter do 12: for each independent set Ii ∈ I do 13: for each vertex v ∈ Ii in parallel do 14: ← OptimizeNode( ,Nv) 15: end do 16: end do 17: Q ← quality(M) 18: k ← k+1 19: end do 20: end procedure Our simultaneous untangling and smoothing algorithm optimizes in parallel the vertices of an independent set. The vertex set with the same color (Ii) is partitioned among the available processors. Each processor optimizes its assigned set of vertices in a sequential fashion. At each sequential step, a processor applies the OptimizeNode function to a single vertex v. This optimization function implements the method described above in Section 2 to adjust the new position of each free vertex v in its own submesh Nv. The new vertex spatial position is available to other processors by writing to shared memory. Each subsequent parallel phase optimizes another independent set of vertices. There are as many parallel phases as number of independent sets. As in the serial algorithm, after all vertices have been optimized, the mesh quality Q is measured. The mesh is successively untangled and smoothed until the mesh is completely untangled and successive iterations increase the minimum mesh quality less than 5%. The algorithm also stops when the number of untangling and smoothing iterations is larger than maxIter. Finally, if the mesh optimization procedure stops before maxIter is reached, the output of our parallel algorithm is a tetrahedral mesh M with a minimum quality greater than λ . 4 Experimental methodology Our experiments were conducted on two different many-core high-performance computers. One of them is a HP Integrity Superdome node that contains 128 Itanium2 Montvale cores with 1.6 GHz clock speed, multithreading disabled, and 1024 GB NUMA (Non-Uniform Memory Access) shared memory. It is a node of the Finis Terrae supercomputer [14]. The other parallel computer is called Manycore Testing Lab, which has been set up by Intel to work with 40 Westmere 2.27 GHz cores and 252 GB NUMA shared memory [18]. Both computers use Linux systems with kernels 2.6.16.53-0.8-smp and 2.6.18-194.11.4.el5-smp respectively. The sequential and parallel versions of our 3D untangling and smoothing method were applied on six different tangled benchmark meshes. Their descriptions can be seen in Table 1. The minimum mesh quality of all meshes is 0 because at least one tetrahedron is inverted. The average mesh quality is obtained by summing the quality of all valid tetrahedra and dividing the sum by the number of valid and inverted tetrahedra. All these tetrahedral meshes were constructed with a tool that applies an automatic strategy for adaptive tetrahedral mesh generation based on the meccano method [6,7,28,29]. Some of them were generated using, as input data, the surface triangulations obtained from different Internet repositories [30]. Note that as the meccano method uses Kossaczky’s algorithm [25], the maximum vertex degree (node valence) coincides in all the benchmark meshes. Table 1. Description of the tangled benchmark tetrahedral meshes. The respective minimum mesh qualities are 0. Name Number of vertices (m) Number of tetrahedra Average mesh quality Number of inverted tetrahedra Maximum vertex degree Object “m=6358” 6358 26446 0.2618 2215 26 Bunny “m=9176” 9176 35920 0.1707 13706 26 Tube “m=11525” 11525 47824 0.2660 1924 26 Bone “m=39617” 39617 168834 0.1302 83417 26 Screwdriver “m=201530” 201530 840800 0.2409 322255 26 Toroid “m=520128” 520128 2201104 0.0657 1147390 26 HR toroid To compile our programs, we used the same Intel C++ compiler version 11.1 on both parallel computers, but targeted to the respective processor architecture. This compiler generates more efficient programs for our algorithms than GNU GCC compiler, which is usually included in Linux distributions. The source code of the parallel version of our new algorithm includes OpenMP directives, which were disabled when the sequential version was compiled. After some test runs, we decided to use the dynamic OpenMP thread scheduling method [8] because it provides the best performance results for our parallel algorithm. In all cases, the compiler optimization flag “-O3” was enforced. All versions were run with additional software optimization based on hardware binding: processor and memory. For each benchmark mesh we run the parallel version multiple times using a given maximum number of active threads between 1 and 128 when the Itanium2-based computer is used and between 1 and 40 when the Westmere-based computer is used. Since our algorithms are CPU-bound, there is little sense in us- ing more threads than available cores. Thus, we activate the same number of cores as the number of threads. No operating system code was executed during our experiments and the processors were not shared among other user level workloads. The sequential and parallel versions of our source code were profiled with the Performance Application Programming Interface API [4], which uses performance counter hardware of processors. The information provided from these performance counters was used to calculate the following quantitative performance metrics: wall-clock time, parallel overhead time, true speed-up, parallel efficiency, and load balancing. Each metric is averaged over more than 30 independent runs. Each run is divided into two phases. The first of them completely untangles a mesh. This phase loops over all the mesh vertices repetitively. During this phase, untangled tetrahedra are smoothed too. The number of untangling iterations depends on the mesh. The second phase is focused on smoothing the mesh until successive smoothing iterations increase the minimum mesh quality less than 5%. Each run is characterized by the number of untangling and smoothing iterations, which is represented by “U&S”. The results of the experimental setup, described in this section, are discussed in the following four sections. 5 Performance scalability The qualitative metric called performance scalability informs about the improvement of an algorithm when the amount of processors increases. It is usually based on the quantitative metric SNc called speed-up, which is defined as the ratio of the sequential execution time tS to the parallel execution time tNc when Nc processors are used: SNc = tS / tNc. When the execution time of the main mesh optimization procedure alone is profiled in both versions of our algorithms, line 9 of serial Algorithm 1 vs. line 14 of parallel Algorithm 2, we obtain values for speed-up as illustrated in Fig. 1(b) (black bars labeled INSIDE). Each bar represents to speed-up for a given number of available threads/cores. The results shown in Fig. 1(c) were obtained when the “m=39617” mesh was optimized with our sequential and parallel algorithms using C3 coloring algorithm and the parallel computer with 128 Itanium2 processors. Due to paper limitations, we can present detailed performance results for only one benchmark mesh and one graph coloring algorithm. As it can be seen in Fig. 1(b), the speed-up of the inside part of the mesh optimization procedure linearly increases as the number of cores increases. In order to measure how well this linear increase of speed-up encompasses the increase of cores, the quantitative performance metric called parallel efficiency (ENc) is used: ENc =100% × SNc / NC, where NC is the number of cores. If speed-up (SNc) is not superlinear, maximum value of ENc is 100% [8]. The utilization of the processors and speed-up scalability will be better as long as parallel efficiency is higher. Figures 1(b) and 1(e) also show the parallel efficiency of the main mesh optimization procedure of Algorithm 2 (dotted line labeled INSIDE). Note that up to NC = 128 cores, the parallel efficiency is always above 76% when up to 128 processors are used. These results indicate that the main computation of our parallel algorithm is highly scalable. This scalability is caused by the parallel processing of an independent set of vertices in each iteration of the Algorithm 2 (lines 13-15). (a) (b) (c) (d) (e) (f) Fig. 1. “m=39617”: (a) Tangled (up) and untangled (down) mesh. (b) Speed-up and parallel efficiency of the line 14 of Algorithm 2 (label: INSIDE) and the complete Algorithm 2 (label: OUTSIDE) on the Itanium2 computer. (c) Execution time of the line 14 (label: INSIDE) and the complete parallel algorithm (label: OUTSIDE) when 40 Westmere and 128 Itanium2 cores are respectively used. (e), (f) show the respective results for the “m=520128” mesh (d). C3 coloring algorithm and dynamic thread scheduling were used. When the execution times of the complete sequential (procedure SUS of Algorithm 1) and parallel (procedure pSUS of Algorithm 2) algorithms are profiled, we obtained values for speed-up as illustrated in Fig. 1(b) and 1(e) (grey bars labeled OUTSIDE). Note that in this case, the speed-up of the complete algorithm does not increase linearly as when the main mesh optimization procedures of algorithms are profiled, and the parallel efficiency is above 50% when up to 128 processors are used. We observe that as the number of threads/cores is larger, the OpenMP loopscheduling overhead increases the number of executed instructions to synchronize and manage parallel threads. These additional instructions are not involved in the main computation of our parallel algorithm. As Amdahl’s law describes [5], speed-up and parallel efficiency deteriorate as the number of threads increases because they tend to be dominated by this parallel overhead. This scalability deterioration of our parallel algorithm is mainly due to the parallel loop-scheduling overhead that is incurred when the threads are scheduled and launched during runtime. After some experiments, we observed that the best OpenMP directive for line 29 of Algorithm 2 uses dynamic thread scheduling with 1 mesh vertex per chunk: #pragma omp parallel for schedule (dynamic, 1). The small chunk size that achieves the best load balancing is justified by the fact that the time to optimize each vertex varies significantly. Using data collected from some of the hardware counters of processors during runtime, we observe that as the number of threads/cores is larger, the above mentioned OpenMP directive makes the number of executed instructions to schedule and launch parallel threads to be larger. These additional instructions are not involved in the main computation of our parallel algorithm. As Amdahl’s law describes [5], speed-up and parallel efficiency deteriorate as the number of threads increases because they tend to be dominated by this parallel overhead. Thus, the main performance overhead is due to the implementation tool that is used in developing our parallel programs. Computer performance comparisons are frequently done using wall-clock time metric. Thus, Fig. 1(c) and 1(f) show the runtime of our parallel algorithm when the “m=39617” and “m=520128” meshes are respectively used. In both cases, C3 coloring algorithm and two many-core computers are used. First of all, note that when the number of cores is smaller than 32, the differences in runtime between the inner loop of the parallel algorithm (data labeled INSIDE) and the complete parallel algorithm (data labeled OUTSIDE) are inappreciable. As the number of cores is larger, the runtime performance of the complete parallel algorithm decreases, but not as much as the runtime of the inner loop. However, the larger the number of vertices, the lower the parallel overhead tends to be. These conclusions are valid for the two computers used in the experiments. Additionally, we observe in most of cases that for the complete parallel Algorithm 2, the Westmere-based computer provides higher performance than Itanium2-based computer although more Itanium2 cores are used than Westmere cores: 128 vs. 40, respectively. This is mainly due to three causes: the low parallel efficiency of Algorithm 2 when Itanium2 processors are used, the lower clock speed of Itanium2 processors, and the inefficiency of compiler in exploiting the instruction level parallelism of the very-long-instruction-word of Itanium2 instructions. However, when the inner loop of the parallel algorithm is studied, the Itanium2-based computer provides lower execution time than the other parallel com- Level-1 data cache memory. All the above mentioned cache memory issues are not affected by the vertex ordering provided by the selected coloring algorithm. Using the Itanium2 performance counter called NOPS_RETIRED [17], another performance bottleneck was identified in the machine code that is generated for our serial and parallel algorithms by the Intel compiler for Itanium2 processors. On average, 40% of executed instructions are no-operation instructions. This is caused by the Itanium2 instruction-set, which determines that up to three explicit instructions should be included in a very long instruction word instruction (VLIW). When the compiler analyzes dependencies of our OpenMP programs and cannot schedule a bundle of at least three explicit instructions, no-operation instructions are automatically generated to fill some instruction slots of the respective VLIW instruction. 9 Conclusions and future work We have proposed a new parallel algorithm for simultaneous untangling and smoothing of tetrahedral meshes. It is based on a successive set of mesh optimization iterations. In each of them, all the vertex coordinates are recalculated in parallel. The performance evaluation of this algorithm on two many-core sharedmemory computers using six benchmark meshes with a wide range of sizes shows that it is a scalable and efficient parallel algorithm. For most of the processed meshes, we have observed that the parallelization of the body of the inner loop of our mesh optimization algorithm allows a reduction of about 1/110 of runtime related to the sequential implementation when 128 cores are used. We additionally have analyzed the causes of parallel performance deterioration when OpenMP is used to implement the optimization loop of our algorithm. Using real data collected with some performance counters, we can conclude that the performance overhead of our parallel algorithm is mainly due to loop-scheduling overhead of the OpenMP programming methodology. Moreover, the results indicate that mesh size positively influences on parallel performance, but the number of optimization iterations deteriorates performance more severely. We also investigated the influence of three graph coloring algorithms on the performance of our parallel untangling and smoothing algorithm. They have low impact on the total execution time. However, the total execution time of our parallel algorithm depends on the selected coloring algorithm. In this paper, we have shown that there is not a unique coloring algorithm for our parallel algorithm that achieves the highest parallel performance. When parallel load balancing is analyzed, we observed that load unbalancing is mainly caused by OpenMP loop-scheduling overhead. Thus, its negative impact increases for larger numbers of available parallel threads. When analyzing hardware usage, we observe that our parallel algorithm is processor-bound because it uses CPU and cache memory during 99% of runtime. Our parallel algorithm is CPU bound and its demonstrated scalability potential for many-core architectures encourages us to extend our work to achieve higher performance improvements from GPUs. The main problem will be to reduce the negative impact of global memory random accesses when the non-consecutive mesh vertices are optimized by the same streaming multiprocessor. Many parallel applications using meshes such as finite-element methods use a domain decomposition approach on distributed-memory computers. Our parallel algorithm needs to be adapted for a partitioned mesh on this type of computers. A distributed-memory strategy may sweep the partitioned mesh in three successive steps. First of all, the inner nodes of a mesh partition are sent to the same computing node. The domain boundary nodes are sent to the computing nodes where the inner nodes of the respective domains were sent. In a second step, each multi-core node colors and optimizes the inner mesh nodes of its assigned domain. Nonoptimized domain boundary nodes and their optimized submeshes are sent in the third step to a single multi-core node where boundary nodes are optimized. Acknowledgments This work has been supported by the Spanish Government, Secretaría de Estado de Universidades e Investigación, Ministerio de Economía y Competitividad, and FEDER, grant contract: CGL2011-29396-C03-01. It has been also supported by Fondo Sectorial CONACYT SENER Hidrocarburos, grant contract: 163723, CESGA ICTS projects (ICTS198, ICTS216), and Intel. We thank to anonymous reviewers for their valuable comments and suggestions on this manuscript. References 1. Batdorf, M., Freitag, L.A., Ollivier-Gooch, C. (1997) Computational study of the effect of unstructured mesh quality on solution efficiency. Presented at the 13th Annual AIAA Computational Fluid Dynamics Conference, AIAA 2. Bazaraa, M., Sherali, H., Shetty, C.M. (1993) Nonlinear Programming. Theory and Algorithms. Wiley 3. Bozdag, D., Gebremedhin, A., Manne, F., Boman, E., Catalyurek, U. (2008) A framework for scalable greedy coloring on distributed memory parallel computers. Journal of Parallel and Distributed Computing, 68(4):515-535 4. Browne, S., Dongarra J., Garner N., London K., Mucci, P. (2000) A scalable crossplatform infrastructure for application performance tuning using hardware counters. In: Proc. 2000 ACM/IEEE Conference on Supercomputing. IEEE Computer Society 5. Bronevetsky, G., Gyllenhaal, J.C., Supinski, B.R. (2009) Clomp: Accurately characterizing OpenMP application overheads. Int. J. Parallel Programming, 37(3):250-265 6. Cascón, J.M., Montenegro, R., Escobar, J.M., Rodríguez, E., Montero, G. (2007) A new meccano technique for adaptive 3-D triangulation. In: Proc. of the 16th International Meshing Roundtable, Springer, Berlin, pp. 103–120 7. Cascón, J.M., Montenegro, R., Escobar, J.M., Rodríguez, E., Montero, G. (2009) The meccano method for automatic tetrahedral mesh generation of complex genus-zero solids. In: Proc. 18th International Meshing Roundtable, Springer, Berlin, pp. 463–480 8. Chapman, B., Jost, G., van der Pas, R. (2007) Using OpenMP: Portable Shared Memory Parallel Programming. The MIT Press 9. Dennis, J.E., Schnabel, R.B. (1996) Numerical methods for unconstrained optimization and nonlinear equations. Society for Industrial and Applied Mathematics (SIAM) 10. Dompierre, J., Labbé, P., Guibault, F., Camarero, R. (1998) Proposal of benchmarks for 3D unstructured tetrahedral mesh optimization. In: Proc. of the 7th International Meshing Roundtable, Dearborn, MI. Sandia National Laboratories, pp 459-478 11. Ekman, P. (2003) Studying program performance on the Itanium 2 with pfmon: www.pdc.kth.se/~pek/ia64-profiling.txt 12. Escobar, J.M., Rodríguez, E., Montenegro, R., Montero, G., González-Yuste, J.M. (2003) Simultaneous untangling and smoothing of tetrahedral meshes. Comp. Meth. Appl. Mech. Eng. 192:2775-2787 13. Escobar, J.M., Rodríguez, E., Montenegro, R., Montero, G., González-Yuste, J.M. (2010) SUS Code - Simultaneous Mesh Untangling and Smoothing Code, http://www.dca.iusiani.ulpgc.es/proyecto2012-2014/html/Software.html 14. FINIS TERRAE Supercomputer: http://archivo.cesga.es/content/view/917/115/lang,en 15. Freitag, L., Jones, M.T., Plassmann, P.E. (1999) A parallel algorithm for mesh smoothing. SIAM J. Sci. Comput. 20(6):2023-2040 16. Frey, P.J., George, P.L. (2010) Mesh Generation: Application to Finite Elements, Second Edition. ISTE, London, UK 17. Intel (2004) Intel® Itanium® 2 Processor Reference Manual. For software development and optimization. Intel, Order Number: 251110-003 18. Intel Manycore Testing Laboratory: http://software.intel.com/en-us/intel-manycoretesting-lab 19. Interoperable Technologies for Advanced Petascale Simulations; http://www.itaps.org/ 20. Jarp, S. (2002) A Methodology for using the Itanium 2 Performance Counters for Bottleneck Analysis. Tech-Report HP Labs 21. Jiao, X., Alexander, P.J. (2005) Parallel feature-preserving mesh smoothing, Proc. of the 2005 International Conference on Computational Science and its Applications (ICCSA 2005), 3483: 1180-1189 22. Jones, M.T., Plassmann, P.E. (1993) A parallel graph coloring heuristic. SIAM J. Sci. Comput. 14(3):654-669 23. Kim, J., Panitanarak, T., Shontz, S.M. (2013) A multiobjective mesh optimization framework for mesh quality improvement and mesh untangling, International Journal of Numerical Methods in Engineering, 94(1):20-42 24. Knupp, P.M. (2001) Algebraic mesh quality metrics. SIAM J. Sci. Comput. 23(1):193–218 25. Kossaczky, I. (1994) A recursive approach to local mesh refinement in two and three dimensions. J. Comput. Appl. Math. 55:275-288 26. Luby, M. (1986) A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing, 4, pp. 1036-1053 27. Madden, P.H. (2012) Dispelling the myths of parallel computing. IEEE Design & Test of Computers. IEEE Computer Society Digital Library. IEEE Computer Society 28. Montenegro, R., Cascón, J.M., Escobar, J.M., Rodríguez, E., Montero, G. (2009) An automatic strategy for adaptive tetrahedral mesh generation. Appl. Num. Math. 59(9):2203-2217 29. Montenegro, R., Cascón, J.M., Rodríguez, E., Escobar, J.M., Montero, G. (2010) The meccano method for automatic three-dimensional triangulation and volume parametrization of complex solids. In: Developments and Applications in Engineering Computational Technology, Saxe-Coburg Publications, Stirling, pp. 19–48 30. Shape benchmark repositories: Cyberware (www.cyberware.com), The Stanford 3D Scanning Repository (http://graphics.stanford.edu/data/3Dscanrep), GAMMA (wwwroc.inria.fr/gamma/gamma/download/download.php) 31. Shontz, S.M., Knupp, P. (2008) The effect of vertex reordering on 2D local mesh optimization efficiency. In: 17th International Meshing Roundtable, pp. 107-124 32. Shontz, S.M., Nistor, D.M. (2012) CPU-GPU algorithms for triangular surface mesh simplification. In: Proc. of the 21st International Meshing Roundtable, pp 475-492 33. Uncmin++ library; http://www.smallwaters.com/software/cpp/uncmin.html 34. Yeo, Y.I., Ni, T., Myles, A., Goel, V., Peters, J. (2009), Parallel smoothing of quad meshes, Vis. Comput., 25(8):757-769