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

Pe o mance E alua ion o a Pa allel Algo i hm o Simul aneous Un angling and Smoo hing o Te ahed al Meshes Domingo Bení ez1,2, Edua do Rod íguez1,2, José Ma ía Escoba 2 and Ra ael Mon eneg o2 1 Depa amen o de In o má ica y Sis emas, Uni e si y o Las Palmas de G an Cana ia, Spain 2 Uni e si y Ins i u e o In elligen Sys ems and Nume ical Applica ions in Enginee ing, SIANI, Uni e si y o Las Palmas de G an Cana ia, Spain {dbeni ez,e od iguez,jmescoba , mon eneg o}@siani.es, h p://www.dca.iusiani.ulpgc.es/p oyec o2012-2014 Abs ac . A new pa allel algo i hm o simul aneous un angling and smoo hing o e ahed al meshes is p oposed in his pape . We p o ide a de ailed analysis o i s pe o mance on sha ed-memo y many-co e compu e a chi ec u es. This pe - o mance analysis includes he e alua ion o execu ion ime, pa allel scalabili y, load balancing, and pa allelism bo lenecks. Addi ionally, we compa e he impac o h ee p e iously published g aph colo ing p ocedu es on he pe o mance o ou pa allel algo i hm. We use six benchma k meshes wi h a wide ange o sizes. Us- ing hese expe imen al da a se s, we desc ibe he beha io o he pa allel algo i hm o di e en da a sizes. We demons a e ha his algo i hm is highly scalable when i uns on wo di e en high-pe o mance many-co e compu e s wi h up o 128 p ocesso s. Howe e , some pa allel de e io a ion is obse ed. He e, we ana- lyze he main causes o his pa allel de e io a ion. 1 In oduc ion I is well known ha he mesh and i s quali y can g ea ly impac he accu acy o simula ions, as well as sol e e iciency [1]. F equen ly, he au oma ic mesh gen- e a ion ools p oduce meshes wi h in e ed o poo ly shaped elemen s. To ob ain high-quali y meshes, o en scien is s mus un angle and imp o e he quali y o meshes be o e o du ing he nume ical analysis [23]. We p oposed a mesh op imi- za ion me hod ha simul aneous un angle and smoo h e ahed al meshes [12,13]. When his me hod is applied using con en ional non-pa allel p og ams o la ge and/o angled meshes, he wall-clock ime may be ex emely high. Ou op imiza- ion me hod can be applied i highe pe o mance could be achie ed such as scien- i ic and enginee ing applica ions ha use 3D disc e iza ion me hods o nume ical- ly sol e pa ial di e en ial equa ions [15,16]. In his pape , we p opose a new pa allel algo i hm o simul aneously un an- gling and smoo hing e ahed al meshes. I s goal is o educe execu ion ime e i- cien ly. In addi ion, a pe o mance e alua ion o he p oposed pa allel algo i hm on many-co e compu e s is desc ibed. I includes he analysis o he scalabili y, pa allel e iciency, load balancing, pe o mance bo lenecks, and in luence o g aph colo ing algo i hms on he pe o mance o ou new pa allel algo i hm. Gi en ha meshes which a e used o PDE simula ions a e becoming la ge all o he ime, i is becoming necessa y o ha e pa allel algo i hms o mesh gene a- ion and op imiza ion. To he au ho ’s knowledge, he e a e cu en ly no pa allel mesh un angling algo i hms o pa allel simul aneous mesh un angling and smoo h- ing echniques in he li e a u e. P e ious s udies on pa allel algo i hms o mesh smoo hing p oblems include he wo k o Jiao and Alexande [21] ha is applied o iangula ed su aces. Thei algo i hm was implemen ed on dis ibu ed-memo y compu e s wi h up o 128 p ocesso s and i was shown 43% o maximum pa allel e iciency. Yeo e al [34] also p oposed an algo i hm o smoo hing quad meshes ha i s well in o pa allel s eams and was mapped o a GPU. They applied hei algo i hm o eal- ime p ocessing o su ace models and showed a pe o mance compa ison wi h o he GPU algo i hms. F ei ag e al [15] elied on heo e ical sha ed-memo y models wi hou a eal implemen a ion on sha ed-memo y mul i- co e sys ems, al hough hey p esen ed esul s on dis ibu ed-memo y compu e s. Shon z and Nis o ha e published ano he simila s udy [32], which p o ides pe - o mance esul s o mesh simpli ica ion algo i hms on GPUs. Howe e , hey do no men ion i a g aph colo ing algo i hm was used o ind mesh e ices ha ha e no compu a ional dependency. Se e al mesh op imiza ion algo i hms a e imple- men ed in pa allel ou ines o he pe ascale meshing so wa e ools p o ided by he ITAPS p ojec [19]. These ools a e used in dis ibu ed-memo y compu e s. The es o he pape is o ganized as ollows. Sec ion 2 summa izes he ma he- ma ical ounda ion o he 3D simul aneous un angling and smoo hing algo i hm. Sec ion 3 desc ibes he new pa allel algo i hm o his op imiza ion me hod. The expe imen al me hodology ha we used o e alua e he pe o mance o he pa al- lel algo i hm is explained in Sec ion 4. Sec ion 5 analyzes he pe o mance scala- bili y. Sec ion 6 desc ibes he in luence o h ee p e iously published g aph colo - ing algo i hms on he pa allel pe o mance. Load unbalancing and o he pe o mance bo lenecks a e s udied in Sec ion 7 and 8, espec i ely. Finally, he main conclusions and u u e wo k a e discussed in Sec ion 9. 2 Ou app oach o simul aneous un angling and smoo hing o e ahed al meshes Le us conside M o be a e ahed al mesh. Usual echniques o imp o e he quali- y o a alid mesh, ha is, one ha does no con ain in e ed e ahed a, a e based upon local smoo hing [10]. In sho , hese echniques consis o inding he new posi ion ha each inne mesh node mus hold, in such a way ha hey op i- mize an objec i e unc ion (bounda y e ices a e ixed du ing all he mesh op i- miza ion p ocess). Such a unc ion is based on a ce ain measu emen o he quali- y o he local submesh N ⊂M ha is o med by he se o e ahed a connec ed o he ee node . As i is a local op imiza ion p ocess, we canno gua an ee ha he inal mesh is globally op imal. Ne e heless, a e epea ing his p ocess se e al imes o all he nodes o he mesh M, qui e sa is ac o y esul s can be achie ed. The algeb aic quali y me ics p oposed by Knupp [24] p o ide us an app op i- a e amewo k o de ine objec i e unc ions. Speci ically, he one used in his pa- pe has he gene ic o m, (1) whe e n is he numbe o elemen s in N , p is usually chosen as 1 o 2 and η i = 1 / qi is he dis o ion o he i- h e ahed on o N and qi is he chosen co esponding algeb aic elemen quali y measu e. In pa icula , we ha e implemen ed he mean a io quali y measu e o a e ahed on gi en by q = 3 σ2/3 / |S|2, whe e |S| is he F obenius no m o ma ix S associa ed o he a ine map om he ideal elemen (usually an equila e al e ahed on) o he physical one, and σ = de (S). Speci ical- ly, he weigh ed Jacobian ma ix S is de ined as S =AW -1, being A = (x1-x0, x2-x0, x3-x0) he Jacobian ma ix and xk, k = 0,1,2,3 he coo dina es o he e ices o he e ahed on. The cons an ma ix W is de i ed om he ideal elemen (see [12]). Objec i e unc ions like (1) a e app op ia e o imp o e he quali y o a alid mesh and a oid a alid mesh o be in e ed, bu hey do no wo k p ope ly when he e a e in e ed elemen s ( σ < 0). This is because hey p esen singula i ies (ba - ie s) when any e ahed on o N changes he sign o i s Jacobian ma ix. In [12] we p oposed a sui able modi ica ion o he objec i e unc ion such ha i is egu- la all o e R3. I consis s o subs i u ing he e m σ in he quali y me ics by he posi i e and inc easing unc ion . When a easible e- gion exis s (subse o R3 whe e could be placed, being N a alid submesh), he minima o he o iginal and modi ied objec i e unc ions a e e y close and, when his egion does no exis , he minimum o he modi ied objec i e unc ion is lo- ca ed in such a way ha i ends o un angle N . In his way, we can use any s and- a d and e icien uncons ained op imiza ion me hod o ind he minimum o he modi ied objec i e unc ion [2]. In his pape , we ha e used he New on uncon- s ained op imiza ion me hod ha is implemen ed wi h UNCMIN++ lib a y [9,33]. 3 A no el pa allel algo i hm In Algo i hm 1, a sequen ial algo i hm called SUS o ou simul aneous un angling and smoo hing o e ahed al meshes can be seen. The inpu s o he sequen ial al- go i hm a e he ollowings: M is a angled e ahed al mesh, maxI e is he max- imum numbe o un angling and smoo hing i e a ions, N is he se o e ahed a connec ed o he ee node , is he ini ial posi ion o he ee node, is i s po- si ion a e op imiza ion, which is implemen ed wi h he p ocedu e Op i- mizeNode, Q measu es he lowes quali y o a e ahed on o M when he abo e men ioned q e ahed on quali y unc ion is used, and quali y is a unc ion ha p o ides he minimum quali y o mesh M (i is 0 i any e ahed al is angled). The ou pu o he algo i hm is an un angled and smoo hed mesh M, whose min- imum quali y mus be la ge han a use -speci ied h eshold λ . This algo i hm i e - a es o e all he mesh e ices in some o de and adjus s a each s ep he coo di- na es o he ee node . A code o his algo i hm can be downloaded a [13]. In Algo i hm 2, a no el pa allel algo i hm o ou ma hema ical me hod o simul aneous un angling and smoo hing o e ahed al meshes is shown. The main p ocedu e is called pSUS. I s inpu s M, maxI e , N , , Op imizeNode, , Q, λ , quali y ha e he same meanings as desc ibed o Algo i hm 1. Algo i hm 1. Sequen ial algo i hm (SUS) o he simul aneous un angling and smoo hing o a e ahed al mesh M. 1: unc ion Op imizeNode( ,N ) 2: Op imize objec i e unc ion ( ) 3: end unc ion 4: p ocedu e SUS 5: Q ← 0 6: k ← 0 7: while Q < λ and k < maxI e do 8: o each e ex ∈ M do 9: ← Op imizeNode( ,N ) 10: end do 11: Q ← quali y(M) 12: k ← k+1 13: end do 14: end p ocedu e The pa allel algo i hm has o p e en wo adjacen e ices om being simul a- neously un angled and smoo hed on di e en p ocesso s. On he con a y, new in- e ed mesh elemen s may be c ea ed [15]. Thus, when he sequen ial Algo i hm 1 is pa allelized, a compu a ional dependency appea s be ween adjacen e ices be- cause one e ex needs o be op imized a e he o he . This jus i ies he use in ou pa allel algo i hm o a g aph colo ing algo i hm o ind e ices o a e ahed al mesh M ha ha e no compu a ional dependency. G aph colo ing is implemen ed wi h p ocedu e Colo ing, which is exp essed as ollows. Le G=(V,E) be he g aph associa ed o he e ahed al mesh M, whe e V is he se o e ices o he mesh (wi hou in o ma ion o e ex spa ial coo di- na es) and E is he se o hei edges, hen Colo ing is a p ocedu e ha is used o colo he g aph G such ha wo adjacen e ices do no ha e he same colo . Then, an independen se , o colo , Ii is a se o non-adjacen e ices (i.e., hey do no sha e a common edge). Tha is, ∈ Ii => ∉ adj(Ii,G=(V,E)), whe e adj(Ii,G=(V,E)) is he se o e ices ha a e adjacen o all e ex j ∈ Ii being j ≠ . In his way he g aph G o a e ahed al mesh M is colo ed and pa i ioned in a dis- join sequence o independen se s, I={I1,I2,…}. We implemen ed h ee di e en and p e iously published g aph colo ing me h- ods called “C1”, “C2”, and “C3”. C1 is a e ex colo ing me hod ha has been used o pa allel mesh smoo hing [15]. I equi es he use o he asynch onous colo ing heu is ic p oposed by Jones and Plassmann [22]. In pa icula , we used i s se ial e sion o C1. This heu is ic is based on Luby’s Mon e Ca lo algo i hm o de- e mining he maximal independen se [26]. C2 is a pa allel e sion o C1 ha was also p oposed by Jones and Plassmann [22] o dis ibu ed-memo y compu e s. We addi ionally adap ed C2 o mul i h ead/mul ico e compu e s. C3 is an i e a i e pa allel g eedy colo ing algo i hm ha was p oposed by Bozdag e al [3]. Sec ion 6 compa es he impac o hese g aph colo ing algo i hms on he pe o mance o ou pa allel op imiza ion me hod. Algo i hm 2. Pa allel algo i hm (pSUS) o he simul aneous un angling and smoo hing o a e ahed al mesh M. 1: p ocedu e Colo ing(G=(V,E)) 2: G is pa i ioned in o independen se s I using C1, C2 o C3 colo ing algo i hm 3: end p ocedu e 4: unc ion Op imizeNode( ,N ) 5: Op imize objec i e unc ion K( ) 6: end unc ion 7: p ocedu e pSUS 8: I ← Colo ing(G=(V,E)) 9: k ← 0 10: Q ← 0 11: while Q < λ and k < maxI e do 12: o each independen se Ii ∈ I do 13: o each e ex ∈ Ii in pa allel do 14: ← Op imizeNode( ,N ) 15: end do 16: end do 17: Q ← quali y(M) 18: k ← k+1 19: end do 20: end p ocedu e Ou simul aneous un angling and smoo hing algo i hm op imizes in pa allel he e ices o an independen se . The e ex se wi h he same colo (Ii) is pa i ioned among he a ailable p ocesso s. Each p ocesso op imizes i s assigned se o e i- ces in a sequen ial ashion. A each sequen ial s ep, a p ocesso applies he Op i- mizeNode unc ion o a single e ex . This op imiza ion unc ion implemen s he me hod desc ibed abo e in Sec ion 2 o adjus he new posi ion o each ee e ex in i s own submesh N . The new e ex spa ial posi ion is a ailable o o he p ocesso s by w i ing o sha ed memo y. Each subsequen pa allel phase op imizes ano he independen se o e ices. The e a e as many pa allel phases as numbe o independen se s. As in he se ial algo i hm, a e all e ices ha e been op imized, he mesh quali y Q is measu ed. The mesh is successi ely un angled and smoo hed un il he mesh is comple ely un angled and successi e i e a ions inc ease he minimum mesh quali y less han 5%. The algo i hm also s ops when he numbe o un angling and smoo hing i e a- ions is la ge han maxI e . Finally, i he mesh op imiza ion p ocedu e s ops be o e maxI e is eached, he ou pu o ou pa allel algo i hm is a e ahed al mesh M wi h a minimum quali y g ea e han λ . 4 Expe imen al me hodology Ou expe imen s we e conduc ed on wo di e en many-co e high-pe o mance compu e s. One o hem is a HP In eg i y Supe dome node ha con ains 128 I ani- um2 Mon ale co es wi h 1.6 GHz clock speed, mul i h eading disabled, and 1024 GB NUMA (Non-Uni o m Memo y Access) sha ed memo y. I is a node o he Finis Te ae supe compu e [14]. The o he pa allel compu e is called Manyco e Tes ing Lab, which has been se up by In el o wo k wi h 40 Wes me e 2.27 GHz co es and 252 GB NUMA sha ed memo y [18]. Bo h compu e s use Linux sys- ems wi h ke nels 2.6.16.53-0.8-smp and 2.6.18-194.11.4.el5-smp espec i ely. The sequen ial and pa allel e sions o ou 3D un angling and smoo hing me h- od we e applied on six di e en angled benchma k meshes. Thei desc ip ions can be seen in Table 1. The minimum mesh quali y o all meshes is 0 because a leas one e ahed on is in e ed. The a e age mesh quali y is ob ained by sum- ming he quali y o all alid e ahed a and di iding he sum by he numbe o al- id and in e ed e ahed a. All hese e ahed al meshes we e cons uc ed wi h a ool ha applies an au oma ic s a egy o adap i e e ahed al mesh gene a ion based on he meccano me hod [6,7,28,29]. Some o hem we e gene a ed using, as inpu da a, he su ace iangula ions ob ained om di e en In e ne eposi o ies [30]. No e ha as he meccano me hod uses Kossaczky’s algo i hm [25], he max- imum e ex deg ee (node alence) coincides in all he benchma k meshes. Table 1. Desc ip ion o he angled benchma k e ahed al meshes. The espec i e mini- mum mesh quali ies a e 0. Name Numbe o e i- ces (m) Numbe o e ahed a A e age mesh quali y Numbe o in e ed e ahed a Maximum e ex deg ee Objec “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 Sc ewd i e “m=201530” 201530 840800 0.2409 322255 26 To oid “m=520128” 520128 2201104 0.0657 1147390 26 HR o oid To compile ou p og ams, we used he same In el C++ compile e sion 11.1 on bo h pa allel compu e s, bu a ge ed o he espec i e p ocesso a chi ec u e. This compile gene a es mo e e icien p og ams o ou algo i hms han GNU GCC compile , which is usually included in Linux dis ibu ions. The sou ce code o he pa allel e sion o ou new algo i hm includes OpenMP di ec i es, which we e disabled when he sequen ial e sion was compiled. A e some es uns, we decided o use he dynamic OpenMP h ead scheduling me hod [8] because i p o ides he bes pe o mance esul s o ou pa allel algo i hm. In all cases, he compile op imiza ion lag “-O3” was en o ced. All e sions we e un wi h addi ional so wa e op imiza ion based on ha dwa e binding: p ocesso and memo y. Fo each benchma k mesh we un he pa allel e sion mul iple imes using a gi en maximum numbe o ac i e h eads be ween 1 and 128 when he I anium2-based compu e is used and be ween 1 and 40 when he Wes me e-based compu e is used. Since ou algo i hms a e CPU-bound, he e is li le sense in us- ing mo e h eads han a ailable co es. Thus, we ac i a e he same numbe o co es as he numbe o h eads. No ope a ing sys em code was execu ed du ing ou ex- pe imen s and he p ocesso s we e no sha ed among o he use le el wo kloads. The sequen ial and pa allel e sions o ou sou ce code we e p o iled wi h he Pe o mance Applica ion P og amming In e ace API [4], which uses pe o mance coun e ha dwa e o p ocesso s. The in o ma ion p o ided om hese pe o mance coun e s was used o calcula e he ollowing quan i a i e pe o mance me ics: wall-clock ime, pa allel o e head ime, ue speed-up, pa allel e iciency, and load balancing. Each me ic is a e aged o e mo e han 30 independen uns. Each un is di ided in o wo phases. The i s o hem comple ely un angles a mesh. This phase loops o e all he mesh e ices epe i i ely. Du ing his phase, un angled e ahed a a e smoo hed oo. The numbe o un angling i e a ions de- pends on he mesh. The second phase is ocused on smoo hing he mesh un il suc- cessi e smoo hing i e a ions inc ease he minimum mesh quali y less han 5%. Each un is cha ac e ized by he numbe o un angling and smoo hing i e a- ions, which is ep esen ed by “U&S”. The esul s o he expe imen al se up, de- sc ibed in his sec ion, a e discussed in he ollowing ou sec ions. 5 Pe o mance scalabili y The quali a i e me ic called pe o mance scalabili y in o ms abou he imp o e- men o an algo i hm when he amoun o p ocesso s inc eases. I is usually based on he quan i a i e me ic SNc called speed-up, which is de ined as he a io o he sequen ial execu ion ime S o he pa allel execu ion ime Nc when Nc p ocesso s a e used: SNc = S / Nc. When he execu ion ime o he main mesh op imiza ion p ocedu e alone is p o- iled in bo h e sions o ou algo i hms, line 9 o se ial Algo i hm 1 s. line 14 o pa allel Algo i hm 2, we ob ain alues o speed-up as illus a ed in Fig. 1(b) (black ba s labeled INSIDE). Each ba ep esen s o speed-up o a gi en numbe o a ailable h eads/co es. The esul s shown in Fig. 1(c) we e ob ained when he “m=39617” mesh was op imized wi h ou sequen ial and pa allel algo i hms using C3 colo ing algo i hm and he pa allel compu e wi h 128 I anium2 p ocesso s. Due o pape limi a ions, we can p esen de ailed pe o mance esul s o only one benchma k mesh and one g aph colo ing algo i hm. As i can be seen in Fig. 1(b), he speed-up o he inside pa o he mesh op i- miza ion p ocedu e linea ly inc eases as he numbe o co es inc eases. In o de o measu e how well his linea inc ease o speed-up encompasses he inc ease o co es, he quan i a i e pe o mance me ic called pa allel e iciency (ENc) is used: ENc =100% × SNc / NC, whe e NC is he numbe o co es. I speed-up (SNc) is no supe linea , maximum alue o ENc is 100% [8]. The u iliza ion o he p ocesso s and speed-up scalabili y will be be e as long as pa allel e iciency is highe . Figu es 1(b) and 1(e) also show he pa allel e iciency o he main mesh op i- miza ion p ocedu e o Algo i hm 2 (do ed line labeled INSIDE). No e ha up o NC = 128 co es, he pa allel e iciency is always abo e 76% when up o 128 p o- cesso s a e used. These esul s indica e ha he main compu a ion o ou pa allel algo i hm is highly scalable. This scalabili y is caused by he pa allel p ocessing o an independen se o e ices in each i e a ion o he Algo i hm 2 (lines 13-15). (a) (b) (c) (d) (e) ( ) Fig. 1. “m=39617”: (a) Tangled (up) and un angled (down) mesh. (b) Speed-up and pa allel e iciency o he line 14 o Algo i hm 2 (label: INSIDE) and he comple e Algo i hm 2 (la- bel: OUTSIDE) on he I anium2 compu e . (c) Execu ion ime o he line 14 (label: INSIDE) and he comple e pa allel algo i hm (label: OUTSIDE) when 40 Wes me e and 128 I anium2 co es a e espec i ely used. (e), ( ) show he espec i e esul s o he “m=520128” mesh (d). C3 colo ing algo i hm and dynamic h ead scheduling we e used. When he execu ion imes o he comple e sequen ial (p ocedu e SUS o Algo- i hm 1) and pa allel (p ocedu e pSUS o Algo i hm 2) algo i hms a e p o iled, we ob ained alues o speed-up as illus a ed in Fig. 1(b) and 1(e) (g ey ba s labeled OUTSIDE). No e ha in his case, he speed-up o he comple e algo i hm does no inc ease linea ly as when he main mesh op imiza ion p ocedu es o algo- i hms a e p o iled, and he pa allel e iciency is abo e 50% when up o 128 p o- cesso s a e used. We obse e ha as he numbe o h eads/co es is la ge , he OpenMP loop- scheduling o e head inc eases he numbe o execu ed ins uc ions o synch onize and manage pa allel h eads. These addi ional ins uc ions a e no in ol ed in he main compu a ion o ou pa allel algo i hm. As Amdahl’s law desc ibes [5], speed-up and pa allel e iciency de e io a e as he numbe o h eads inc eases be- cause hey end o be domina ed by his pa allel o e head. This scalabili y de e io a ion o ou pa allel algo i hm is mainly due o he pa - allel loop-scheduling o e head ha is incu ed when he h eads a e scheduled and launched du ing un ime. A e some expe imen s, we obse ed ha he bes OpenMP di ec i e o line 29 o Algo i hm 2 uses dynamic h ead scheduling wi h 1 mesh e ex pe chunk: #p agma omp pa allel o schedule (dynamic, 1). The small chunk size ha achie es he bes load balancing is jus i ied by he ac ha he ime o op imize each e ex a ies signi ican ly. Using da a collec ed om some o he ha dwa e coun e s o p ocesso s du ing un ime, we obse e ha as he numbe o h eads/co es is la ge , he abo e men- ioned OpenMP di ec i e makes he numbe o execu ed ins uc ions o schedule and launch pa allel h eads o be la ge . These addi ional ins uc ions a e no in- ol ed in he main compu a ion o ou pa allel algo i hm. As Amdahl’s law de- sc ibes [5], speed-up and pa allel e iciency de e io a e as he numbe o h eads inc eases because hey end o be domina ed by his pa allel o e head. Thus, he main pe o mance o e head is due o he implemen a ion ool ha is used in de- eloping ou pa allel p og ams. Compu e pe o mance compa isons a e equen ly done using wall-clock ime me ic. Thus, Fig. 1(c) and 1( ) show he un ime o ou pa allel algo i hm when he “m=39617” and “m=520128” meshes a e espec i ely used. In bo h cases, C3 colo ing algo i hm and wo many-co e compu e s a e used. Fi s o all, no e ha when he numbe o co es is smalle han 32, he di e ences in un ime be ween he inne loop o he pa allel algo i hm (da a labeled INSIDE) and he comple e pa allel algo i hm (da a labeled OUTSIDE) a e inapp eciable. As he numbe o co es is la ge , he un ime pe o mance o he comple e pa allel algo i hm de- c eases, bu no as much as he un ime o he inne loop. Howe e , he la ge he numbe o e ices, he lowe he pa allel o e head ends o be. These conclusions a e alid o he wo compu e s used in he expe imen s. Addi ionally, we obse e in mos o cases ha o he comple e pa allel Algo- i hm 2, he Wes me e-based compu e p o ides highe pe o mance han I ani- um2-based compu e al hough mo e I anium2 co es a e used han Wes me e co es: 128 s. 40, espec i ely. This is mainly due o h ee causes: he low pa allel e i- ciency o Algo i hm 2 when I anium2 p ocesso s a e used, he lowe clock speed o I anium2 p ocesso s, and he ine iciency o compile in exploi ing he ins uc- ion le el pa allelism o he e y-long-ins uc ion-wo d o I anium2 ins uc ions. Howe e , when he inne loop o he pa allel algo i hm is s udied, he I ani- um2-based compu e p o ides lowe execu ion ime han he o he pa allel com- Le el-1 da a cache memo y. All he abo e men ioned cache memo y issues a e no a ec ed by he e ex o de ing p o ided by he selec ed colo ing algo i hm. Using he I anium2 pe o mance coun e called NOPS_RETIRED [17], ano he pe o mance bo leneck was iden i ied in he machine code ha is gene a ed o ou se ial and pa allel algo i hms by he In el compile o I anium2 p ocesso s. On a e age, 40% o execu ed ins uc ions a e no-ope a ion ins uc ions. This is caused by he I anium2 ins uc ion-se , which de e mines ha up o h ee explici ins uc ions should be included in a e y long ins uc ion wo d ins uc ion (VLIW). When he compile analyzes dependencies o ou OpenMP p og ams and canno schedule a bundle o a leas h ee explici ins uc ions, no-ope a ion in- s uc ions a e au oma ically gene a ed o ill some ins uc ion slo s o he espec- i e VLIW ins uc ion. 9 Conclusions and u u e wo k We ha e p oposed a new pa allel algo i hm o simul aneous un angling and smoo hing o e ahed al meshes. I is based on a successi e se o mesh op imiza- ion i e a ions. In each o hem, all he e ex coo dina es a e ecalcula ed in pa al- lel. The pe o mance e alua ion o his algo i hm on wo many-co e sha ed- memo y compu e s using six benchma k meshes wi h a wide ange o sizes shows ha i is a scalable and e icien pa allel algo i hm. Fo mos o he p ocessed meshes, we ha e obse ed ha he pa alleliza ion o he body o he inne loop o ou mesh op imiza ion algo i hm allows a educ ion o abou 1/110 o un ime e- la ed o he sequen ial implemen a ion when 128 co es a e used. We addi ionally ha e analyzed he causes o pa allel pe o mance de e io a ion when OpenMP is used o implemen he op imiza ion loop o ou algo i hm. Using eal da a collec ed wi h some pe o mance coun e s, we can conclude ha he pe - o mance o e head o ou pa allel algo i hm is mainly due o loop-scheduling o e head o he OpenMP p og amming me hodology. Mo eo e , he esul s indi- ca e ha mesh size posi i ely in luences on pa allel pe o mance, bu he numbe o op imiza ion i e a ions de e io a es pe o mance mo e se e ely. We also in es iga ed he in luence o h ee g aph colo ing algo i hms on he pe o mance o ou pa allel un angling and smoo hing algo i hm. They ha e low impac on he o al execu ion ime. Howe e , he o al execu ion ime o ou pa al- lel algo i hm depends on he selec ed colo ing algo i hm. In his pape , we ha e shown ha he e is no a unique colo ing algo i hm o ou pa allel algo i hm ha achie es he highes pa allel pe o mance. When pa allel load balancing is analyzed, we obse ed ha load unbalancing is mainly caused by OpenMP loop-scheduling o e head. Thus, i s nega i e impac inc eases o la ge numbe s o a ailable pa allel h eads. When analyzing ha d- wa e usage, we obse e ha ou pa allel algo i hm is p ocesso -bound because i uses CPU and cache memo y du ing 99% o un ime. Ou pa allel algo i hm is CPU bound and i s demons a ed scalabili y po en ial o many-co e a chi ec u es encou ages us o ex end ou wo k o achie e highe pe o mance imp o emen s om GPUs. The main p oblem will be o educe he nega i e impac o global memo y andom accesses when he non-consecu i e mesh e ices a e op imized by he same s eaming mul ip ocesso . Many pa allel applica ions using meshes such as ini e-elemen me hods use a domain decomposi ion app oach on dis ibu ed-memo y compu e s. Ou pa allel algo i hm needs o be adap ed o a pa i ioned mesh on his ype o compu e s. A dis ibu ed-memo y s a egy may sweep he pa i ioned mesh in h ee successi e s eps. Fi s o all, he inne nodes o a mesh pa i ion a e sen o he same compu- ing node. The domain bounda y nodes a e sen o he compu ing nodes whe e he inne nodes o he espec i e domains we e sen . In a second s ep, each mul i-co e node colo s and op imizes he inne mesh nodes o i s assigned domain. Non- op imized domain bounda y nodes and hei op imized submeshes a e sen in he hi d s ep o a single mul i-co e node whe e bounda y nodes a e op imized. Acknowledgmen s This wo k has been suppo ed by he Spanish Go e nmen , Sec e a ía de Es ado de Uni e - sidades e In es igación, Minis e io de Economía y Compe i i idad, and FEDER, g an con- ac : CGL2011-29396-C03-01. I has been also suppo ed by Fondo Sec o ial CONACYT SENER Hid oca bu os, g an con ac : 163723, CESGA ICTS p ojec s (ICTS198, ICTS216), and In el. We hank o anonymous e iewe s o hei aluable commen s and sugges ions on his manusc ip . Re e ences 1. Ba do , M., F ei ag, L.A., Olli ie -Gooch, C. (1997) Compu a ional s udy o he e - ec o uns uc u ed mesh quali y on solu ion e iciency. P esen ed a he 13 h Annual AIAA Compu a ional Fluid Dynamics Con e ence, AIAA 2. Baza aa, M., She ali, H., She y, C.M. (1993) Nonlinea P og amming. Theo y and Algo i hms. Wiley 3. Bozdag, D., Geb emedhin, A., Manne, F., Boman, E., Ca alyu ek, U. (2008) A ame- wo k o scalable g eedy colo ing on dis ibu ed memo y pa allel compu e s. Jou nal o Pa allel and Dis ibu ed Compu ing, 68(4):515-535 4. B owne, S., Donga a J., Ga ne N., London K., Mucci, P. (2000) A scalable c oss- pla o m in as uc u e o applica ion pe o mance uning using ha dwa e coun e s. In: P oc. 2000 ACM/IEEE Con e ence on Supe compu ing. IEEE Compu e Socie y 5. B one e sky, G., Gyllenhaal, J.C., Supinski, B.R. (2009) Clomp: Accu a ely cha ac e - izing OpenMP applica ion o e heads. In . J. Pa allel P og amming, 37(3):250-265 6. Cascón, J.M., Mon eneg o, R., Escoba , J.M., Rod íguez, E., Mon e o, G. (2007) A new meccano echnique o adap i e 3-D iangula ion. In: P oc. o he 16 h In e na- ional Meshing Round able, Sp inge , Be lin, pp. 103–120 7. Cascón, J.M., Mon eneg o, R., Escoba , J.M., Rod íguez, E., Mon e o, G. (2009) The meccano me hod o au oma ic e ahed al mesh gene a ion o complex genus-ze o solids. In: P oc. 18 h In e na ional Meshing Round able, Sp inge , Be lin, pp. 463–480 8. Chapman, B., Jos , G., an de Pas, R. (2007) Using OpenMP: Po able Sha ed Memo y Pa allel P og amming. The MIT P ess 9. Dennis, J.E., Schnabel, R.B. (1996) Nume ical me hods o uncons ained op imiza- ion and nonlinea equa ions. Socie y o Indus ial and Applied Ma hema ics (SIAM) 10. Dompie e, J., Labbé, P., Guibaul , F., Cama e o, R. (1998) P oposal o benchma ks o 3D uns uc u ed e ahed al mesh op imiza ion. In: P oc. o he 7 h In e na ional Meshing Round able, Dea bo n, MI. Sandia Na ional Labo a o ies, pp 459-478 11. Ekman, P. (2003) S udying p og am pe o mance on he I anium 2 wi h p mon: www.pdc.k h.se/~pek/ia64-p o iling. x 12. Escoba , J.M., Rod íguez, E., Mon eneg o, R., Mon e o, G., González-Yus e, J.M. (2003) Simul aneous un angling and smoo hing o e ahed al meshes. Comp. Me h. Appl. Mech. Eng. 192:2775-2787 13. Escoba , J.M., Rod íguez, E., Mon eneg o, R., Mon e o, G., González-Yus e, J.M. (2010) SUS Code - Simul aneous Mesh Un angling and Smoo hing Code, h p://www.dca.iusiani.ulpgc.es/p oyec o2012-2014/h ml/So wa e.h ml 14. FINIS TERRAE Supe compu e : h p://a chi o.cesga.es/con en / iew/917/115/lang,en 15. F ei ag, L., Jones, M.T., Plassmann, P.E. (1999) A pa allel algo i hm o mesh smoo hing. SIAM J. Sci. Compu . 20(6):2023-2040 16. F ey, P.J., Geo ge, P.L. (2010) Mesh Gene a ion: Applica ion o Fini e Elemen s, Se- cond Edi ion. ISTE, London, UK 17. In el (2004) In el® I anium® 2 P ocesso Re e ence Manual. Fo so wa e de elopmen and op imiza ion. In el, O de Numbe : 251110-003 18. In el Manyco e Tes ing Labo a o y: h p://so wa e.in el.com/en-us/in el-manyco e- es ing-lab 19. In e ope able Technologies o Ad anced Pe ascale Simula ions; h p://www.i aps.o g/ 20. Ja p, S. (2002) A Me hodology o using he I anium 2 Pe o mance Coun e s o Bo - leneck Analysis. Tech-Repo HP Labs 21. Jiao, X., Alexande , P.J. (2005) Pa allel ea u e-p ese ing mesh smoo hing, P oc. o he 2005 In e na ional Con e ence on Compu a ional Science and i s Applica ions (ICCSA 2005), 3483: 1180-1189 22. Jones, M.T., Plassmann, P.E. (1993) A pa allel g aph colo ing heu is ic. SIAM J. Sci. Compu . 14(3):654-669 23. Kim, J., Pani ana ak, T., Shon z, S.M. (2013) A mul iobjec i e mesh op imiza ion amewo k o mesh quali y imp o emen and mesh un angling, In e na ional Jou nal o Nume ical Me hods in Enginee ing, 94(1):20-42 24. Knupp, P.M. (2001) Algeb aic mesh quali y me ics. SIAM J. Sci. Compu . 23(1):193–218 25. Kossaczky, I. (1994) A ecu si e app oach o local mesh e inemen in wo and h ee dimensions. J. Compu . Appl. Ma h. 55:275-288 26. Luby, M. (1986) A simple pa allel algo i hm o he maximal independen se p ob- lem. SIAM Jou nal on Compu ing, 4, pp. 1036-1053 27. Madden, P.H. (2012) Dispelling he my hs o pa allel compu ing. IEEE Design & Tes o Compu e s. IEEE Compu e Socie y Digi al Lib a y. IEEE Compu e Socie y 28. Mon eneg o, R., Cascón, J.M., Escoba , J.M., Rod íguez, E., Mon e o, G. (2009) An au oma ic s a egy o adap i e e ahed al mesh gene a ion. Appl. Num. Ma h. 59(9):2203-2217 29. Mon eneg o, R., Cascón, J.M., Rod íguez, E., Escoba , J.M., Mon e o, G. (2010) The meccano me hod o au oma ic h ee-dimensional iangula ion and olume pa ame i- za ion o complex solids. In: De elopmen s and Applica ions in Enginee ing Compu- a ional Technology, Saxe-Cobu g Publica ions, S i ling, pp. 19–48 30. Shape benchma k eposi o ies: Cybe wa e (www.cybe wa e.com), The S an o d 3D Scanning Reposi o y (h p://g aphics.s an o d.edu/da a/3Dscan ep), GAMMA (www- oc.in ia. /gamma/gamma/download/download.php) 31. Shon z, S.M., Knupp, P. (2008) The e ec o e ex eo de ing on 2D local mesh op- imiza ion e iciency. In: 17 h In e na ional Meshing Round able, pp. 107-124 32. Shon z, S.M., Nis o , D.M. (2012) CPU-GPU algo i hms o iangula su ace mesh simpli ica ion. In: P oc. o he 21s In e na ional Meshing Round able, pp 475-492 33. Uncmin++ lib a y; h p://www.smallwa e s.com/so wa e/cpp/uncmin.h ml 34. Yeo, Y.I., Ni, T., Myles, A., Goel, V., Pe e s, J. (2009), Pa allel smoo hing o quad meshes, Vis. Compu ., 25(8):757-769