P oceedings o he 16 h In e na ional Con e ence
on Compu a ional and Ma hema ical Me hods
in Science and Enginee ing, CMMSE 2016
4–8 July, 2016.
C i ical Sec ions and So wa e T ansac ional Memo y
Compa ison in he Con ex o a TLS Run ime Lib a y
Se gio Aldea1, Diego R. Llanos1and A u o Gonzalez-Esc ibano1
1Depa amen o de In o m´a ica, Uni e sidad de Valladolid
emails: [email p o ec ed],[email p o ec ed],[email p o ec ed]
Abs ac
T ansac ional Memo y (TM) is a echnique ha aims o mi iga e he pe o mance
losses ha a e inhe en o he se ializa ion o accesses in c i ical sec ions. Some s ud-
ies ha e shown ha he use o TM may lead o pe o mance imp o emen s, despi e
he exis ence o managemen o e heads. Howe e , he ela i e pe o mance o TM,
wi h espec o classical c i ical sec ions managemen depends g ea ly on he ac ual
pe cen age o imes ha he same da a is handled simul aneously by wo ansac ions.
In his pape , we compa e he ela i e pe o mance o he c i ical sec ions p o ided
by OpenMP wi h espec o wo So wa e T ansac ional Memo y (STM) implemen a-
ions. These h ee me hods a e used o manage concu en da a accesses in ATLaS, a
so wa e-based, Th ead-Le el Specula ion (TLS) sys em. The complexi y o his appli-
ca ion makes i ex emely di icul o p edic whe he wo ansac ions may con lic o
no , and how many imes he ansac ions will be execu ed. Ou expe imen al esul s
show ha he STM solu ions only deli e a pe o mance compa able o OpenMP when
he e a e almos no con lic s. In any o he case, hei pe o mance losses make OpenMP
he bes al e na i e o manage c i ical sec ions.
Key wo ds: So wa e T ansac ional Memo y, STM, Th ead-Le el Specula ion, TLS,
OpenMP, ATLaS
1 In oduc ion
Cu en mul ico e p ocesso s o e an oppo uni y o speed up he compu a ion o sequen ial
applica ions. To exploi hese pa allel echnologies, he so wa e needs o be pa allelized,
ha is, ans o med in o de o co ec ly dis ibu e he wo k among di e en h eads.
This p ocess usually in ol es synch onizing he accesses o ce ain memo y a eas ha a e
c
CMMSE ISBN: 978-84-608-6082-2
C i ical Sec ions and STM Compa ison in he Con ex o a TLS Run ime Lib a y
sha ed by he concu en h eads, wi h he aim o a oiding po en ial da a aces. This
synch oniza ion is usually pe o med by using c i ical sec ions ha p o ec sha ed memo y
s uc u es.
To simpli y his p ocess, pa allel p og amming models such as OpenMP [1] o e com-
pile di ec i es, no only o pa allelize he code, bu also o synch onize accesses and de ine
and manage c i ical sec ions. Despi e hei simplici y, hese solu ions p esen a p oblem:
C i ical sec ions in oduce pe o mance losses, no only because hey se ialize he code, bu
also because o he cos associa ed o locking managemen .
So wa e T ansac ional Memo y (STM) [2] a ises as a possible solu ion o he i s
p oblem, allowing p og amme s o ans o m c i ical sec ions in ansac ions ha a e con-
cu en ly and a omically execu ed. This is based on he op imis ic assump ion ha he
code inside he ansac ion will access o di e en loca ions o he sha ed memo y being
p o ec ed. In hese cases, accesses a e ca ied ou concu en ly. I his is no he case,
con lic i e ansac ions should be olled back and execu ed one a a ime.
Wo ks such as [3] ha e shown ha STM can ou pe o m OpenMP c i ical sec ions,
despi e he ela i ely high o e heads o STM. Howe e , he ela i e pe o mance o STM
e sus OpenMP c i ical sec ions is highly dependen on he unning p o ile o each pa icula
applica ion. Di e en pa e ns o accesses o he same c i ical sec ion may lead o di e en
pe o mance igu es.
This pape compa es he OpenMP c i ical sec ions app oach wi h wo STM lib a ies,
using hem o handle he c i ical sec ions ha appea s in he un ime lib a y o ATLaS [4],
a s a e-o - he-a , so wa e-based Th ead Le el Specula ion (TLS) sys em. Ou goal is o
s udy he ela i e pe o mance o bo h app oaches when managing concu en accesses in
such a complex piece o code.
The es o his pape is s uc u ed as ollows: Sec ion 2 b ie ly desc ibes he undamen-
als o so wa e TLS. Sec ion 3 de ails how ou TLS un ime lib a y handles he specula i e
execu ion o a sou ce code, and how c i ical da a s uc u es a e p o ec ed o ensu e co -
ec ness. Sec ion 4 desc ibes how his p o ec ion can be ensu ed using OpenMP and wo
di e en STM lib a ies. Sec ion 5 shows he pe o mance esul s ob ained by each OpenMP
and he STM lib a ies conside ed. Finally, Sec . 6 concludes his pape .
2 Th ead-Le el Specula ion in a Nu shell
Specula i e pa alleliza ion (SP), also called Th ead-Le el Specula ion (TLS) o Op imis ic
Pa alleliza ion [5, 6, 7, 8, 9, 10, 11], is a echnique ha allows he pa allel execu ion o ag-
men s o code ( ypically blocks o i e a ions o a loop) wi hou he need o a compile- ime
analysis, which gua an ees ha he agmen s do no p esen da a dependences be ween
hem. Ins ead, TLS solu ions assume ha he loop can be op imis ically execu ed in pa -
allel, and ely on a un ime moni o o ensu e ha no dependence iola ions appea . TLS
c
CMMSE ISBN: 978-84-608-6082-2
Se gio Aldea, Diego R. Llanos, and A u o Gonzalez-Esc ibano
solu ions can be implemen ed in so wa e o ha dwa e. F om he e on, we will ocus on
so wa e-based TLS.
A dependence iola ion appea s when a gi en h ead gene a es a da um ha has al eady
been consumed by a h ead execu ing a subsequen se o i e a ions wi h espec o he
o iginal sequen ial o de . In his case, he esul s calcula ed so a by he successo (called
he o ending h ead) a e no alid and should be disca ded. Ea ly p oposals [5, 6] s op he
pa allel execu ion and es a he loop se ially. O he p oposals s op he o ending h ead
and all i s successo s, e-execu ing hem in pa allel [7, 8, 9, 10].
Figu e 1 shows an example o h ead-le el specula ion. The igu e ep esen s ou
h eads execu ing one ou o ou consecu i e i e a ions, and he sequence o e en s ha
occu s when he loop is execu ed in pa allel. All h eads access ce ain da a elemen s
om he SV ec o . I he alues o xa e no known a compile ime, he compile is
no able o ensu e ha accesses o he SV s uc u e do no lead o dependence iola ions
when execu ing hem in pa allel. Howe e , he indexes o he da a elemen s being accessed
a e known a un ime, so dependence iola ions can be de ec ed and co ec ed while he
p og am is unning.
Specula i e pa alleliza ion wo ks as ollows. I he p og amme labels he SV ec o as
specula i e, he code should be ins umen ed a compile ime o moni o a un ime ha
all uses o SV ollow sequen ial seman ics. A un ime, each h ead main ains a e sion copy
o he elemen s o he SV ec o being accessed. All ead ope a ions o SV a e eplaced by a
unc ion ha pe o ms a specula i e load. This unc ion ob ains he mos up- o-da e alue
o he elemen being accessed. This ope a ion is called o wa ding. I a p edecesso ( ha is,
a h ead execu ing an ea lie i e a ion) has al eady ead o w i en ha elemen hen he
alue is o wa ded (as Th ead 2 does in Fig. 1). I no , hen he unc ion ob ains he alue
om he main copy o he specula i e da a s uc u e (as Th ead 3 does in he igu e).
Rega ding modi ica ions o he specula i e da a s uc u e, all w i e ope a ions a e e-
placed a compile ime by a specula i e s o e unc ion. This unc ion w i es he da um in he
e sion copy o he cu en p ocesso , and ensu es ha no h ead execu ing a subsequen
i e a ion has al eady consumed an ou da ed alue o his s uc u e elemen , a si ua ion
called “dependence iola ion”. I such a iola ion is de ec ed, he o ending h ead and i s
successo s a e s opped and es a ed, in a so-called squash ope a ion.
I no dependence iola ion a ises o a gi en h ead, i should commi all he da a s o ed
in i s e sion copy o he main copy o he specula i e s uc u e. No e ha commi s should
be done in o de , o ensu e ha he mos up- o-da e alues a e s o ed. A e pe o ming
he commi ope a ion, a h ead can assign i sel a new i e a ion o block o i e a ions o
con inue he pa allel wo k.
c
CMMSE ISBN: 978-84-608-6082-2
C i ical Sec ions and STM Compa ison in he Con ex o a TLS Run ime Lib a y
5
8
10
LocalVa 1 = SV[x]
SV[x] = LocalVa 2
6
7
9
LocalVa 1 = SV[x]
SV[x] = LocalVa 2
2
4
6
LocalVa 1 = SV[x]
SV[x] = LocalVa 2
(c) In−o de commi o da a om success ully− inished h eads
0
1
3 SV[x] = LocalVa 2
Time
LocalVa 1 = SV[x]
Th ead 1 (non spec)
(i e a ion 1, x = 1) (i e a ion 2, x = 1)
Th ead 2
(i e a ion 3, x = 2)
Th ead 3 Th ead 4 (mos −spec)
(i e a ion 4, x = 2)
Re e ence
copy o
s [2]
(Time 4: Th ead 2 o wa ds upda ed alue o s [1] om h ead 1)
(Time 3: h ead 1 de ec s no dependence iola ions)
(Time 8: Th ead 3 o wa ds alue o s [2] om e e ence copy)
(Time 7: Th ead 4 o wa ds alue o s [2] om e e ence copy)
(Time 10: Th ead 3 de ec s iola ion: h ead 4 squashed)
(b) Specula i e loads wi h mos − ecen alue o wa ding
(a) Specula i e s o es plus de ec ion o dependence iola ions
(Time 6: h ead 2 de ec s no dependence iola ions)
Figu e 1: Example o specula i e execu ion o a loop and summa y o ope a ions ca ied
ou by a un ime TLS lib a y.
3 The ATLaS amewo k and un ime lib a y
We ha e de eloped an ex ension o OpenMP ha inco po a es Th ead-Le el Specula ion
suppo . The ATLaS amewo k [4] allows any loop o be execu ed in pa allel wi hou he
need o a p io dependence analysis. This is done by de ining a new OpenMP a iable
classi ica ion clause, namely specula i e. I he use is unsu e abou whe he he access in
pa allel o a a iable o s uc u e inside a gi en loop may lead o a dependence iola ion,
he/she may simply classi y i as specula i e, ins ead o labeling i as p i a e o sha ed. In his
case, he sou ce code is ins umen ed a compile ime o add TLS execu ion suppo . This
is done wi h he help o a GCC compile plugin [12] ha ans o ms he code, inse ing
calls o he ATLaS TLS un ime lib a y. When unning in pa allel, he un ime lib a y
ensu es ha all he accesses o all da a elemen s classi ied as specula i e ollows sequen ial
seman ics.
The ATLaS un ime lib a y [13] suppo s all he ope a ions desc ibed in he p e ious
sec ion. I ollows he design p inciples o he specula i e pa alleliza ion lib a y de eloped
by Cin a and Llanos [7], wi h se e al imp o emen s ha allow, o example, he specula i e
pa alleliza ion o loops ha use poin e a i hme ic o complex da a s uc u es.
One o he key ad an ages o his lib a y o e p e ious designs is ha he ATLaS
un ime lib a y is almos ee o c i ical sec ions. The only c i ical sec ion needed is he
one ha manages he da a s uc u e ha main ains he assignmen o chunks o i e a ions
c
CMMSE ISBN: 978-84-608-6082-2
Se gio Aldea, Diego R. Llanos, and A u o Gonzalez-Esc ibano
Sliding window
S a e
Poin e o he e sion copy
Ve sion copy da a s uc u es
Th ead C
I e : [0,9]
Th ead B
I e : [10,19]
Th ead A
I e : [20,29]
Non-spec
window slo
1
Mos -spec
window slo
3
F ee RunningRunning
Non-spec
window slo
2
Mos -spec
window slo
4
Th ead C
finishes, and
commi s i s copy
Th ead B
I e : [10,19]
Th ead A
I e : [20,29]
Th ead C
I e : [30,39]
Ve sion copy da a s uc u es
Running Running Running Running
F ee
Chunk exec. de ails
Figu e 2: Upda ing he sliding window ha handles he pa allel, specula i e execu ion. A
a gi en momen (le ), he h ead C wo king in slo 1 is unning. When Th ead C inishes,
i ees i s slo and ge s a new one, upda ing non-spec and mos -spec poin e s ( igh ).
o each h ead. ATLaS handles he pa allel execu ion o each chunk o i e a ions h ough a
sliding window mechanism, which is implemen ed by a ma ix wi h Wcolumns ep esen ing
Wwindow slo s. Figu e 2 depic s a simpli ied e sion o he sliding window implemen a ion
(see [4, 13] o mo e de ails). The igu e ep esen s a sliding window wi h ou slo s, hos ing
he execu ion o h ee pa allel specula i e h eads.
The h ead execu ing he ea lies chunk o i e a ions (Th ead C in ou example) is
called non-specula i e, since i has no p edecesso s ha may squash i . Con e sely, he
h ead execu ing he la es chunk is called he mos -specula i e h ead. As can be seen
in Fig. 2, wo poin e s indica e he slo s whe e he non-specula i e and mos -specula i e
h eads a e being execu ed. The pa o he window being used is always he one om he
non-spec poin e o he igh , up o he mos -spec poin e .
The only c i ical sec ion in he ATLaS un ime lib a y is he one ha p o ec s his
sliding window. I wo o mo e h eads inish a he same ime, hey could be assigned o he
same F ee slo , esul ing in an inco ec execu ion. The e o e, in o de o ensu e he co ec
ope a ion o he ATLaS un ime lib a y, i is necessa y o p o ec he accesses o hese sha ed
s uc u es, including he ma ix ha implemen s he sliding window mechanism, and he
a iables ha poin o he non- and mos -specula i e slo s.
Figu e 2 shows wha happens when a non-specula i e h ead success ully inishes i s
execu ion. Suppose ha Th ead C, he one execu ing he non-specula i e h ead, inishes
i s execu ion and commi s i s da a ( he commi ope a ion is no shown in he igu e). A e
his, i en e s he c i ical sec ion o pe o m se e al ac ions. I ma ks slo 1 as F ee; i
ad ances he non-specula i e poin e o slo 2; a e checking ha he slo pas he mos -
specula i e one is F ee, i assigns i o i sel , se ing he mos -specula i e poin e o 4 and
c
CMMSE ISBN: 978-84-608-6082-2

C i ical Sec ions and STM Compa ison in he Con ex o a TLS Run ime Lib a y
changing i s s a e o Running; and inally, a e ge ing he ollowing chunk o i e a ions o
be execu ed (i e a ions 30 o 39 in ou example), i exi s he c i ical sec ion. No e ha he
implemen a ion o he sliding window wo ks in a ci cula way: When Th ead B e en ually
inishes, i will assign i sel he slo ha ollows he one used by Th ead C, in ou case he
le mos slo .
The sliding window is modi ied in h ee di e en loca ions wi hin he ATLaS un ime
lib a y. The e o e, he same lock is used in h ee di e en pa s o he code o p o ec
he access o hese da a s uc u es. As will be seen, he place om whe e he access is
pe o med has a no iceable impac in he pe o mance o he p o ec ing sys em being used.
These places a e he ollowing:
•(A) Each ime a dependence iola ion is de ec ed. In he case o a w i e o a
specula i e a iable, he h ead in cha ge should upda e i s e sion copy, and check
whe he a successo has consumed an ou da ed alue o his a iable. I his is he
case, a dependence iola ion has happened, so he o ending h ead should be es a ed
in o de o consume an upda ed e sion o he a iable. This is done in se e al s eps.
Fi s , he h ead ha has de ec ed he si ua ion should en e he c i ical sec ion o
change he s a e o he o ending h ead, om Running o Squashed, and he mos -
specula i e poin e should be mo ed backwa ds o he las Running h ead. A e
hese changes, he h ead exi s he c i ical sec ion and esumes i s no mal ope a ion.
The o ending squashed h ead will e en ually disco e i s new s a e and will en e
he c i ical sec ion (see below).
•(B) Each ime a h ead inishes i s wo k, ei he because he chunk has been suc-
cess ully execu ed o because he h ead disco e s ha i has been squashed. In bo h
cases, he h ead en e s he c i ical sec ion o change i s own s a e om Running ( esp.
Squashed) o F ee. A e his ope a ion, i he slo ollowing he mos -specula i e one
is F ee, he h ead assigns i o i sel , and ad ances he mos -specula i e poin e by
one. O he wise, i means ha he ollowing slo is occupied ei he by a Running h ead
( his means ha he window is ull) o by ano he Squashed h ead. In bo h cases ou
h ead should exi he c i ical sec ion and a emp o e-en e again, in o de o gi e
he h ead ha is using he slo he oppo uni y o ee i 1(see below).
•(C) Each ime a h ead should wai o a ee slo . I a h ead is no able o
ge a ee window slo o wo k, because he ollowing slo is no F ee ye , i should ge
ou and y o gain access again o he c i ical sec ion o assign i sel he ollowing
slo and o ad ance he mos -specula i e poin e .
1Ou h ead canno simply wai inside he c i ical sec ion, because i should ge ou in o de o le he
h ead using ha slo o ge in and change i s own s a e.
c
CMMSE ISBN: 978-84-608-6082-2
Se gio Aldea, Diego R. Llanos, and A u o Gonzalez-Esc ibano
4 P o ec ing da a accesses wi h OpenMP and STM
The o iginal TLS un ime lib a y uses he OpenMP c i ical di ec i e o gua an ee exclusi e
access o he h eads o he h ee pa s o he code men ioned abo e. Because he same
da a s uc u es a e accessed om h ee di e en places, he same lock is used o p o ec
hem in all cases. Recall ha a block o code ma ked wi h an OpenMP c i ical di ec i e
is only execu ed by one h ead a a ime, whils he es o he h eads ha ha e eached
he same poin in he code ha e o wai . This p ocedu e ensu es ha he sliding window
is always in a consis en s a e, hus a oiding mul iple h eads concu en ly upda ing his
s uc u e wi h he po en ial loss o consis ency.
I is easy o see ha he se ializa ion o ope a ions desc ibed abo e should imply a
no iceable o e head in he pe o mance o he specula i e un ime lib a y. A possible way
o educe his pe o mance penal y would be o eplace he s ic , OpenMP c i ical cons uc
wi h he mo e op imis ic cons uc s ha o e he T ansac ional Memo y pa adigm. The
goal o STM is p ecisely o help in explici pa allel p og amming by educing he cos s o he
locks equi ed o a oid ace condi ions in c i ical sec ions [14, 15]. While OpenMP c i ical
cons uc s only allow one single h ead a a ime inside he c i ical sec ion, a ansac ional-
based implemen a ion allows se e al h eads inside i , pe mi ing hei concu en execu ion
as long as consis ency is no comp omised.
Howe e , he op imism o STM, as well as ha o TLS, comes a he cos o some
o e heads, because o he ex a ins umen a ion needed o handle he ansac ions, as well
as he cos associa ed o he ex a uns o pa icula ansac ions when a con lic appea s.
As can be seen, bo h OpenMP and STM app oaches o p o ec da a in eg i y ha e iden-
i ied o e heads. I is ex emely di icul o p edic which app oach will be be e o a
pa icula p oblem, since i depends on he applica ion, i s unning p o ile, and how o en
he benchma k accesses he po en ially con lic i e sha ed a iables, among o he ac o s.
Rega ding he p og ammabili y, OpenMP has been designed o simpli y, o a g ea
ex en , he p ocess o pa alleliza ion, while he di ec use o STM lib a ies in ol es a non-
i ial ins umen a ion o he sou ce code, om he de ini ion o he ansac ional egion o
moni o ing each access o specula i e a iables. This e o is mi iga ed by he exis ence o
STM solu ions ha ely on he compile o eplace STM cons uc s wi h calls o he STM
lib a y. Some STM app oaches p opose language ex ensions o new cons uc s o decla e
ansac ional code egions ha comp ises s a emen s ha mus be execu ed a omically.
Then, ei he an ad-hoc compile , o an exis ing compile modi ied o his pu pose, pa ses
hese new cons uc s, and gene a es all he ins umen a ion, in he same way as compile s
p ocess OpenMP cons uc s.
As we said abo e, OpenMP allows he use o delimi he c i ical sec ions wi h he
cons uc omp c i ical. To decla e a ansac ional egion, STM lib a ies ely on di e en
al e na i es, such as new cons uc s (e.g. GCC-TM’s ansac ion_a omic{} [16], he
In el’s m_a omic{} [17], o he mo e gene ic ansac ion{}), new compile di ec i es (such
c
CMMSE ISBN: 978-84-608-6082-2
C i ical Sec ions and STM Compa ison in he Con ex o a TLS Run ime Lib a y
Applica ion % Max. speedup % o i e a ions # o po en ially Size o C i ical
a ge P = 64 ha p esen specula i e chunks Sec ions
loop (Amhdahl) dep. iola ions scala a iables issued accessed
FAST 100 64 0.001% 2 25 A, B
TREE 95.17 15.84 0% 259 100 B
2D-MEC 43.75 1.76 0.009% 10 1 800 A, B
2D-Hull, Kuzmin 100 64 0.0008% 1 206 11 000 A, B, C
2D-Hull, Squa e 100 64 0.0032% 3 906 3 000 A, B, C
2D-Hull, Disc 100 64 0.0219% 26 406 1 250 A, B, C
Delaunay 97.60 25.47 0.5% 12 030 060 2 A, B, C
Table 1: Pe cen ages o po en ially pa allelism o he benchma ks and loops conside ed,
oge he wi h some benchma ks’ cha ac e is ics. Chunk sizes we e selec ed o ob ain max-
imum speedups.
as IBM’s [18] m_a omic{}), o e en new OpenMP p agmas, such as omp ansac ion,
de ined by OpenTM [19]. Un o una ely, In el STM compile and OpenTM a e no cu en ly
a ailable, while he IBM compile ’s ansac ional buil -in memo y unc ions a e only alid
o Powe 8 a chi ec u e and Blue Gene/Q.
In his wo k, we ha e used OpenMP, he GCC-TM, and he TinySTM lib a ies [20, 21]
o p o ec he accesses o he sliding window desc ibed p e iously. These h ee app oaches
simpli y he pa alleliza ion p ocess wi h he men ioned cons uc s and di ec i es. Mo eo e ,
GCC-TM de ines a speci ica ion o ansac ional language cons uc s ha o he STM li-
b a ies can le e age, and hence, changing he unde lying STM lib a y is jus a p ocess o
p ope linking. In ac , TinySTM is compa ible wi h GCC-TM, allowing p og amme s o
use he same in e ace and sa e some p og amming e o .
Handling he c i ical sec ions wi h OpenMP is s aigh o wa d: The p og amme should
simply delimi he egion by using he de ined omp c i ical di ec i e. This p ocess is
simila when using he GCC-TM speci ica ion. Howe e , o ensu e ha he ansac ion is
a omically execu ed, he e may be ce ain unc ions inside he ansac ion ha mus no be
execu ed. Since he compile is no able o de ec his issue o he unc ions called wi hin
a ansac ion, i is also necessa y o anno a e hei decla a ion and speci y whe he hey
a e sa e o be called, wi h he ansac ion_sa e a ibu e.
The ollowing sec ion desc ibes he pe o mance esul s ob ained by ATLaS when using
hese h ee solu ions o execu e a se o eal-wo ld and syn he ic benchma ks.
5 Expe imen a ion
Expe imen s we e ca ied ou on a 64-p ocesso se e , equipped wi h ou 16-co e AMD
Op e on 6376 p ocesso s a 2.3GHz and 256GB o RAM, which uns Ubun u 12.04.3 LTS. All
h eads had exclusi e access o he p ocesso s du ing he execu ion o he expe imen s, and
we used wall-clock imes in ou measu emen s. We ha e used he OpenMP implemen a ion
c
CMMSE ISBN: 978-84-608-6082-2
Se gio Aldea, Diego R. Llanos, and A u o Gonzalez-Esc ibano
om GCC 4.8.2, and he ansac ional lib a ies om GCC-TM 4.8.2, and TinySTM 1.0.5.
To pe o m he expe imen s, we used bo h eal-wo ld and syn he ic benchma ks. The
eal-wo ld applica ions include he 2-dimensional Minimum Enclosing Ci cle (2D-MEC)
p oblem [22], he 2-dimensional Con ex Hull p oblem (2D-Hull) [23], he Delaunay T i-
angula ion p oblem [24, 25], and a C implemen a ion o he TREE benchma k [26]. We
ha e also used a syn he ic benchma k called Fas [4], which p esen s almos no dependences
be ween i e a ions, and which was designed o es he o e heads o he ATLaS un ime
lib a y.
Table 1 summa izes he cha ac e is ics o each benchma k, including he pe cen age
o execu ion ime consumed by each a ge loop, an es ima ion o he maximum speedup
a ainable (applying Amhdahls Law), he pe cen age o i e a ions o he a ge loop ha lead
o un ime dependence iola ions, he numbe o specula i e a iables wi hin he loop, and
he size o he chunk o consecu i e i e a ions specula i ely execu ed. I/O ime consumed by
he benchma ks we e no aken in o accoun . We also gi e an indica ion o which accesses
o he sliding window p o ec ed by he c i ical sec ion a e mo e equen in he benchma k
(bold le e s indica e ha he co esponding call is mo e equen ). The pe o mance esul s
ob ained by each benchma k and lib a y used a e summa ized in Fig. 3.
The Fas benchma k was designed o es he e iciency o he specula i e scheduling
mechanism, wi h ew i e a ions leading o a dependence iola ion, al hough hey a e enough
o p e en a compile om pa allelizing he loop. This benchma k has e y ew dependence
iola ions, so he c i ical sec ion is p ima ily accessed o ge he ollowing chunk o i e a ions
o be execu ed (access o ype B in ou lib a y). As can be seen in he co esponding
pe o mance plo , OpenMP and he STM lib a ies handle he c i ical sec ions equally well,
deli e ing almos iden ical pe o mances, wi h a speedup o up o 37×wi h 64 p ocesso s.
Unlike he es o he benchma ks, TREE does no su e om dependence iola ions,
bu i is s ill no pa allelizable a compile ime because he compile is no able o ensu e ha
he e a e no da a dependencies. Since i does no p esen dependence iola ions, he code
ha accesses he c i ical sec ion is p ima ily B. Again, OpenMP and STM solu ions deli e
he same pe o mance, wi h a peak speedup o 6×when unning his benchma k wi h a
4096-poin inpu se . As can be seen in he igu e, he o e heads o he TLS un ime lib a y
lead o a pe o mance loss when using 48 h eads o mo e, ega dless o he implemen a ion
chosen o handle c i ical sec ions.
The 2D-MEC benchma k is a icky code which has only 10 specula i e a iables ha
a e equen ly accessed. This benchma k calls he specula i e loop many imes wi h a e y
di e en numbe o i e a ions each ime, making h eads access he sliding window sys em
equen ly o ge he ollowing chunk. As long as i p esen s some dependence iola ions,
he c i ical sec ions a e accessed by codes A, bu mos ly B (C is a ely accessed in his
benchma k). Fo his benchma k, he use o he OpenMP c i ical sec ions leads o he bes
pe o mance, while he STM lib a ies leading o much poo e esul s. OpenMP ge s a peak
c
CMMSE ISBN: 978-84-608-6082-2