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