The effect of parallelization on a tetrahedral mesh optimization method

The effect of parallelization on a tetrahedral mesh optimization method D. Benitez, E. Rodríguez, J.M. Escobar, R. Montenegro SIANI Research Institute University of Las Palmas de Gran Canaria, SPAIN PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 2/36 Motivation •Untangling and smoothing of tetrahedral meshes is an important step in the optimization of meshes in problems with moving boundaries because it provides simulations with elements of good quality •Improving the speed of mesh generation helps users iterate problem setup faster •There are currently no parallel mesh untangling algorithms in existence •There are also no parallel simultaneous mesh untangling and smoothing techniques in the literature PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 3/36 Outline •We propose a new parallel algorithm for simultaneous untangling and smoothing of tetrahedral meshes (it is a tetrahedral mesh optimization method) •We also provide a detailed analysis of its parallelization on a many-core computer: •parallel scalability •load balancing •parallelism bottlenecks •influence of 3 graph coloring algorithms PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 4/36 Summary •Our mathematical approach to tetrahedral mesh optimization •The novel parallel algorithm •Experimental methodology •Performance scalability •Load balancing •Parallelism bottlenecks •Influence of coloring algorithms on parallel performance •Conclusions and future work PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 5/36 Our mathematical approach to tetrahedral mesh optimization Tetrahedral mesh with non-valid tetrahedra (artificially tangled for our experimental tests) Optimized tetrahedral mesh without non-valid tetrahedra Equilateral tetrahedron Example of a valid tetrahedral mesh for a cube Valid Tetrahedron A mesh vertex (node) PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 6/36 Our mathematical approach to tetrahedral mesh optimization TANGLED MESHES UNTANGLED MESHES Bunny Tube Bone Screwdriver Toroid HR toroid PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 7/36 Our mathematical approach to tetrahedral mesh optimization Equilateral tetrahedron Its quality (q) specifies the degree to which regularity is achieved: q=1: equilateral tetrahedron q<1: non-equilateral tetrahedron q < 1 q < 1 q → 1 PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 8/36 Our mathematical approach to tetrahedral mesh optimization •M : a tetrahedral mesh •v: inner mesh node •xv: node position •Nv: the local submesh (set of tetrahedra connected to the node v) •K(xv) : objetive function that measures the quality of the local submesh PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 9/36 Our mathematical approach to tetrahedral mesh optimization •Our untangling and smoothing technique finds the new position xv that each inner mesh node v must hold, in such a way that K(xv) is optimized •This process repeats several times for all the nodes of the mesh M •Mathematical details: J. M. Escobar , E. Rodrıguez , R. Montenegro , G. Montero , J. M. Gonzalez-Yuste (2003) Simultaneous untangling and smoothing of tetrahedral meshes. Computer Methods in Applied Mechanics and Engineering, 192: 2775-2787 PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 16/36 The novel parallel algorithm •Parallel algorithm (pSUS) for the simultaneous untangling and smoothing of a tetrahedral mesh M 1. function OptimizeNode(xv,Nv) 2. Optimize objective function K(xv) 3. end function 4. procedure Coloring(G=(V,E)) 5. G is partitioned into independent sets I={I1, I2, …} using C1, C2or C3 coloring algorithm 6. end procedure 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Iiin parallel do 14. x’v← OptimizeNode(xv,Nv) 15. end do 16. end do 17. Q ← quality(M) 18. k ← k+1 19. end do 20. end procedure We implemented graph coloring with procedure Coloring(), which partitions the mesh in a disjoint sequence of independent sets: I1, I2, … PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 17/36 The novel parallel algorithm •Parallel algorithm (pSUS) for the simultaneous untangling and smoothing of a tetrahedral mesh M 1. function OptimizeNode(xv,Nv) 2. Optimize objective function K(xv) 3. end function 4. procedure Coloring(G=(V,E)) 5. G is partitioned into independent sets I={I1, I2, …} using C1, C2or C3 coloring algorithm 6. end procedure 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Iiin parallel do 14. x’v← OptimizeNode(xv,Nv) 15. end do 16. end do 17. Q ← quality(M) 18. k ← k+1 19. end do 20. end procedure This parallel algorithm optimize in parallel the nodes of each independent set PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 18/36 Experimental methodology •Finis Terrae supercomputer (www.cesga.es), the third largest supercomputer in Spain •1 many-core node HP Integrity Superdome, with 128 cores Itanium Montvale and 1.024 GB (NUMA): shared memory architecture PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 19/36 Experimental methodology •Six different tangled benchmark meshes “m=6358” “m=9176” “m=11525” “m=39617” “m=201530” “m=520128” Bunny Tube Bone Screwdriver Toroid HR toroid PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 20/36 Experimental methodology •Description of the tangled benchmark meshes. The quality of non-valid tetrahedra is considered zero. So, the minimum quality is zero for all meshes 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 PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 21/36 Experimental methodology •Intel C++ compiler 11.1 with “O2” flag •Linux system kernel “2.6.16.53-0.8-smp”. •The source code of the parallel version included OpenMP directives, which were disabled when the sequential version was compiled •Both software versions were profiled with PAPI API, which uses performance counter hardware of Itanium 2 processors •Hardware binding: processor and memory PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 22/36 Experimental methodology •For each benchmark mesh we run the parallel version multiple times using a given maximum number of active threads between 1 and 128 •Each run is divided into two phases •The first of them completely untangles a mesh. This phase loops over all mesh vertices repetitively •The second phase smoothes the mesh until successive iterations increases the minimum mesh quality less than 5% PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 23/36 Performance scalability •True speed-up and parallel efficiency of the body of the main loop 0% 20% 40% 60% 80% 100% 120% 0 20 40 60 80 100 120 1 2 4 8 16 24 32 40 48 56 64 72 80 88 96 104 112 120 128 PARALLELEFFICIENCY(%) SPEED‐UP‐ bodyofthemainloop NUMBEROFTHREADS/CORESUSED Speed‐Up ParallelEfficiency m=6358 C N S t t UpSpeed  C N N S ficiencyParallelEf C  %100 x’v← OptimizeNode(xv,Nv) PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 24/36 Performance scalability •True speed-up and parallel efficiency of the body of the complete parallel Algorithm m=6358 0% 20% 40% 60% 80% 100% 120% 0 20 40 60 80 100 120 1 2 4 8 16 24 32 40 48 56 64 72 80 88 96 104 112 120 128 PARALLELEFFICIENCY(%) SPEED‐UP‐parallelAlgorithm2 NUMBEROFTHREADS/CORESUSED Speed‐Up ParallelEfficiency procedure pSUS … while Q < and k < maxIter do for each independent set IiI do for each vertex vIiin parallel do x’v← OptimizeNode(xv,Nv) PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 25/36 Performance scalability •Best runtime for the complete parallel algorithm (procedure pSUS) Name of tetrahedral mesh Serial runtime (seconds) Best parallel runtime (seconds) Best number of cores Best Speed-Up Best parallel efficiency Best coloring algorith m Number of colors Number of iterations (U&S) Minimum mesh quality Average mesh quality m=6358 17.33 1.49 72 11.7X 16.2% C129 25 0.1319 0.6564 m=9176 37.25 1.17 88 31.9X 36.3% C329 26 0.2580 0.6823 m=11525 33.69 1.13 120 29.7X 24.8% C310 38 0.1109 0.6474 m=39617 87.40 1.59 128 54.9X 42.9% C131 11 0.1698 0.7329 m=201530 2505.37 81.28 128 30.8X 24.1% C221 143 0.2275 0.6687 m=520128 2259.72 41.86 120 54.0X 45.0% C334 36 0.2233 0.6750 PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 32/36 Influence of coloring algorithms on parallel performance •Speed-up achieved by the complete parallel algorithm (pSUS) depends on the mesh coloring algorithm m=39617 PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 33/36 Influence of coloring algorithms on parallel performance •Speed-up achieved by the complete parallel algorithm (pSUS) for all six benchmark meshes when three graph coloring algorithms (C1, C2, and C3) are used and all 128 shared-memory Itanium2 processors are active PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 34/36 Conclusions •We demonstrate that this algorithm is highly scalable when run on a highperformance shared-memory many-core computer with up to 128 Itanium 2 processors. •It is due to the graph coloring algorithm that is used to identify independent sets of vertices without computational dependency PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 35/36 Conclusions •We have analyzed the causes of its parallel deterioration on a 128-core shared-memory high performance computer using six benchmark meshes. •It is mainly due to loop-scheduling overhead of the OpenMP programming methodology. •The graph coloring algorithm has low impact on the total execution time. However, the total execution time of our parallel algorithm depends on the selected coloring algorithm. PPAM13: The effect of parallelization on a tetrahedral mesh optimization method 36/36 Future work •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 massively parallel GPUs. •The main problem will be to reduce the negative impact of global memory random accesses when the nonconsecutive mesh vertices are optimized by the same streaming multiprocessor.