7 h In e na ional Symposium on
High-Le el Pa allel P og amming and Applica ions (HLPP 2014)
Ams e dam, Ne he lands
July 3-4, 2014
New Da a S uc u es o Handle Specula i e
Pa alleliza ion a Run ime
Al a o Es ebanez ·Diego R. Llanos ·
A u o Gonzalez-Esc ibano
Abs ac So wa e-based, h ead-le el specula ion (TLS) is a so wa e ech-
nique ha op imis ically execu es in pa allel loops whose ully-pa allel seman-
ics can no be gua an eed a compile ime. Mode n TLS lib a ies allow o
handle a bi a y da a s uc u es specula i ely. This desi ed ea u e comes a
he high cos o local s o e and/o emo e eco e y imes: The easie he local
s o e, he ha de he emo e eco e y. Un o una ely, bo h imes a e on he
c i ical pa h o any TLS sys em. In his pape we p opose a solu ion ha
pe o ms local s o e in cons an ime, while eco e alues in a ime ha is
in he o de o T, being T he numbe o h eads. As we will see, his solu-
ion, oge he wi h some addi ional imp o emen s, makes he di e ence be-
ween slowdowns and no iceable speedups in he specula i e pa alleliza ion o
non-syn he ic, poin e -based applica ions on a eal sys em. Ou expe imen al
esul s show a gain o 3.58× o 28×wi h espec o he baseline sys em, and
a ela i e e iciency o up o, on a e age, 65% wi h espec o a TLS imple-
men a ion speci ically ailo ed o he benchma ks used.
Keywo ds h ead-le el specula ion ·specula i e pa allelism ·memo y
imp o emen s
1 In oduc ion
Th ead-Le el Specula ion (TLS) [3,29,30,34], also called Specula i e Pa al-
leliza ion (SP) [8,10,14,37] o Op imis ic Pa allelism [16–21] ies o ex ac
pa allelism o loops ha can no be conside ed ully pa allel a compile ime.
A. Es ebanez ·D.R. Llanos ·A. Gonzalez-Esc ibano
Depa amen o de In o ma ica, Uni e sidad de Valladolid, Valladolid, Spain 47011
E-mail: al [email p o ec ed]a.es
D.R. Llanos
E-mail: [email p o ec ed]a.es
A. Gonzalez-Esc ibano
E-mail: [email p o ec ed]a.es
Es ebanez e al.
TLS op imis ically assumes ha dependence iola ions will no occu , launch-
ing he pa allel execu ion o he loop. A ha dwa e o so wa e moni o ensu es
he co ec ness o ha assump ion. I a dependence iola ion is de ec ed, o -
ending h eads a e s opped and e-s a ed in o de . A e sol ing he issue,
he op imis ic, pa allel execu ion is allowed o p oceed. The a ge o TLS sys-
ems a e usually o loops. O he loops can be conside ed as well, bu as long
as hei numbe o i e a ions can no be so easily p edic ed, he applicabili y
o TLS solu ions is limi ed by scheduling p oblems.
In o de o handle he specula i e pa alleliza ion o a loop, all a iables
ha a e no p i a e no sha ed a e labeled a compile ime as “specula i e”.
All eads o a specula i e a iable a e eplaced a compile ime wi h a unc ion
ha eco e s he mos up- o-da e alue o his a iable. In a simila way, all
w i es o a specula i e a iable a e eplaced wi h a unc ion ha no only
pe o ms he w i e ope a ion, bu also 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 a iable.
The mos common solu ion o main ain specula i e da a is o allow each
h ead o keep a e sion copy o all he specula i e a iables ha ha e been
locally accessed. Once a h ead inishes he execu ion o i s chunk o i e a ions,
all changes in he specula i e da a a e commi ed o main memo y.
The bigges challenge in so wa e-based TLS is how o educe he ime
needed o (a) ge he mos up- o-da e alue when eading specula i e da a,
and (b) o sea ch o a possible dependence iola ion when a h ead w i es on a
specula i e a iable. No e ha bo h ope a ions imply a e sing all he e sion
copies main ained by o he h eads. In he i s case, he sea ch o an up- o-
da e alue implies o a e se all he da a being kep by all p edecesso h eads
( ha is, h eads being execu ing ea lie chunks o i e a ions). In he second
case, he sea ch implies o a e se all he specula i e da a being main ained
by all successo s.
Access o p edecesso and successo copies o he da a a e in he c i ical
pa h o any TLS sys em. The p oblem is e en mo e di icul o sol e i he
TLS lib a y allows o specula e o e dynamic s uc u es and/o poin e -based
e e ences.
Among all so wa e-based TLS app oaches p oposed in he li e a u e, ew
o hem a e capable o specula i ely handling dynamic da a s uc u es [20,
34]. Conside ing he di icul y o he p oblem o sol e, i is no s ange ha
he solu ions p oposed ely on abs ac app oaches ha a e di icul o bo h
unde s and and implemen .
The con ibu ion o his pape is o show a new solu ion o a e se specula-
i e da a in a so wa e-based TLS lib a y. We will desc ibe how o d ama ically
dec ease he numbe o memo y accesses when sea ching o p edecesso and
successo e sions o specula i e da a, while keeping he cos o local da a s o -
age in O(1). Ou expe imen al esul s wi h well-known benchma ks on a eal
sys em show ha hese op imiza ions lead o signi ican educ ions in he num-
be o accesses needed (by a ac o o h ee o de s o magni ude) compa ing
wi h a compe i i e baseline implemen a ion ha lacks his ea u e. We also
p opose addi ional solu ions o u he educe he memo y alloca ion calls,
New Da a S uc u es o Handle Specula i e Pa alleliza ion a Run ime
needed o dynamically add new a iables o he specula i e s uc u es ha
should be managed a un ime. The combined e ec o all hese imp o emen s
is an imp essi e inc emen in he speedups ob ained.
The es o his pape is s uc u ed as ollows: Sec ion 2 pu s his wo k
in pe spec i e wi h he exis en solu ions in his ield. Sec ion 3 desc ibes he
baseline solu ion de eloped in a p e ious esea ch. Sec ion 4 desc ibes bo h he
expe imen al en i onmen and he benchma ks used o e alua e he baseline
solu ion and ou new p oposals. Sec ion 5 e alua es he cos s o specula i e
eads and w i es, om a heo e ical and expe imen al poin s o iew. Sec ion 6
add esses he imp o emen s applied o he lib a y in o de o imp o e i s
pe o mance. Sec ion 7 desc ibes wo addi ional imp o emen s ha leads o an
e e as e specula i e pa allel execu ion. Sec ion 8 shows some expe imen al
esul s in e ms o pe o mance measu ed in a eal sys em. Finally, Sec ion 9
concludes his pape .
2 Rela ed wo k
Memo y managemen is a c i ical ield in he con ex o specula i e pa al-
leliza ion. As we will see in his pape , an adequa e handling o specula i e
a iables makes a huge di e ence in e ms o pe o mance. We will i s e-
iew some e o s in his ield, and la e we will concen a e on he p oblem o
ensu ing as accesses o e sion da a.
2.1 TLS app oaches
Se e al esea ches ha e been cen e ed in he pa alleliza ion o loops wi h c oss-
i e a ion dependences h ough h ead-le el specula ion (TLS) echniques. Some
o hem ha e been implemen ed in ha dwa e [5,7,11,15,24,31,32], h ough he
design o speci ic chips, o he addi ion o some unc ionali ies. Bu he e a e
also se e al so wa e app oaches ha suppo he men ioned pa allelism wi h
no a chi ec u al changes [3,14,16,18,20,23,28,30,34]. One o his so wa e ap-
p oaches is he wo k o Tian, Feng, Naga ajan and Gup a in [34,35], whe e hey
p oposed he Copy-o -Disca d (Co D) execu ion model, in which he execu ion
o pa allel h eads a e sepa a ely managed by he non-specula i e one. Spec-
ula i e h eads ead alues o he non-specula i e h ead and pe o m hei
compu a ion, a e ha , specula i e h eads a e commi ed in o de . A e
ha esul s a e checked by non-specula i e h ead in o de o p ese e seman-
ics o sequen ial o de . Commi ope a ion is pe o med by non-specula i e
h ead h ough he Copy o Disca d mechanism ha checks whe he esul s
a e co ec o be copied o he non-specula i e da a, o disca ded wi h no cos
o he wise. Howe e , Co D app oach did no suppo hose applica ions whose
specula i e a iables we e dynamically alloca ed, so in [33] Tian, Feng and
Gup a de eloped mechanisms ha enable hei solu ion o do i .
Es ebanez e al.
Cin a and Llanos [3,4] con ibu ed ano he scheme mainly based on an
agg essi e sliding window, wi h checks o da a dependence iola ions on spec-
ula i e s o es ha educed synch oniza ion cons ain s, and wi h ine- uned
da a s uc u es.
Kulka ni e al. in he wo k desc ibed in [20,21], in oduced Galois a sys em
o suppo complex poin e -based se s o elemen s in op imis ic pa allelism.
They we e cen e ed on pa allelize applica ions wi h complex s uc u es as
linked lis s, g aphs, ees, e c.
In pa icula , hese app oaches su e ed om some speci ic bo lenecks be-
cause a dynamic s uc u e could change hei size du ing he execu ion, and
usually hey a e bigge han he s a ic s uc u es, so a e se hem could be
e y ine icien .
2.2 The p oblem o a e sing e sion copies
Ea lie so wa e-based TLS lib a ies such as [3] only allowed specula i e ac-
cesses o s a ic da a s uc u es such as ec o s. In his way, i a gi en h ead
wan ed o ge he mos up- o-da e alue o he i- h elemen o a specula i e
ec o , i simply looked o i in he i- h posi ion o he e sion copy o each
p edecesso . W i es we e handled in he same way, looking o he i- h posi ion
o each successo ’s e sion copy o he specula i e da a. I is easy o see ha ,
wi h T h eads, he complexi y o his sea ch is in O(T), an a o dable alue
aking in o accoun ha Tis usually in he o de o en hs o p ocesso s.
Mode n TLS lib a ies allow o specula i ely access no only s a ic ec o s,
bu a bi a y memo y loca ions. Usually, his da a is kep wi h no pa icula
o de , an a ac i e solu ion since he cos o inse ing a new elemen o he
s uc u e is exac ly in O(1). The p oblem wi h his solu ion is ha he sea ch
o a p e ious alue (due o a ead ope a ion) and he sea ch o po en ial
iola ions (due o a w i e) imply a e sing all e sion da a kep by all p e-
decesso s and successo s, espec i ely. I we conside T h eads and Mda a
elemen s in each e sion copy, his lead o a complexi y ha is in O(T×M),
wi h Mpo en ially in he o de o millions o elemen s. The solu ion o s o ing
alues using an o de ed da a s uc u e may seem easonable, bu his comes
a he cos o a highe s o age ime, ha is also undesi able. As we will see,
ou solu ion keeps he s o age cos in O(1) while he a e sing cos is in
O(T×M
H), wi h Han a bi a ily la ge cons an . In p ac ice, his solu ion
leads o a a e sing cos ha is jus in O(T).
Ceze e al. [2] add essed he p oblem o he complexi y o he basics ope -
a ions in ol ed in TLS p ocesses. To do his hey used a kind o hash encode ,
called signa u e, ha manages he add esses accessed by each specula i e
h ead. Each signa u e is a se o add esses and allowed o ea se e al ad-
d esses as i hey we e a single one. They enhanced he a chi ec u e wi h some
ha dwa e mechanism ha could e icien ly ope a e wi h his hashed in o ma-
ion. The main di e ences wi h ou sys em a e ha hei ’s is ha dwa e-based
New Da a S uc u es o Handle Specula i e Pa alleliza ion a Run ime
and he hash is used o pe o m ope a ions o a g oup o add esses ins ead
a e sing hei da a.
Kulka ni e al. [19] in oduced some imp o emen s ha inc eased he e -
iciency o Galois. They implemen ed a me hod o pe o m da a pa i ioning
in he da a in a way ha all elemen s o a se whe e mapped o an abs ac
domain, and hen, ans o med again o physical co es. Mendez-Lojo e al.
[26] also desc ibed h ee echniques o op imize i egula applica ions. The
i s one is modi ying codes in a way ha all ead ope a ions a e done be o e
any w i e ope a ion. The second one, based on he calcula ion o dependences
be o e he execu ion. The las one, is used o hose algo i hms whose bo le-
necks a e loca ed in he accesses o da a se s and i is based on emo ing he
co espondence be ween i e a ion and ac i i ies. Unlike ou solu ion, all hese
op imiza ions a e e e ed o algo i hms.
Tian e al. [33] add essed he p oblems ela ed o s o age and loca ion o
in e media e alues in Co D wi h he use o a mapping able ha ansla e
add esses be ween specula i e and non-specula i e h eads. In ha wo k, au-
ho s a i med ha using a hash unc ion was ine icien , wi h a 6×slowdown
wi h espec o o he al e na i es due o he use o a complex hash unc ion.
Ou wo k shows ha he use o a simple hash unc ion leads o imp essi e
speedups in se e al applica ions.
Meh a a e al. [25] desc ibed STMLi e, a so wa e ansac ional memo y
model modi ied o suppo specula i e pa alleliza ion. I was specially designed
o educe o e heads o accesses o a iables logs in ansac ions using a h ead
ha managed he execu ion. Managemen o add esses was handled wi h he
use o hash-based solu ions. Mo e so wa e ansac ional model sys ems ha e
used hashes o imp o e hei pe o mance, i.e., Ha is e al. [12] used hashes
o emo e duplica es in an undo log.
Oancea e al. [27] desc ibed hei own TLS app oach called SpLIP, cen-
e ed on dec easing o e heads o specula i e ope a ions o p e ious app oaches.
They implemen ed non-locking ope a ions whe e was possible, and used a hash
unc ion o imp o e loca ion o e sion copies. Thei hash is based on mapping
adjacen zones o he a ay ha s o ed specula i e alues in a single place. As
we will see, ou solu ion is no based on joining nea add esses, since we do
no need o g oup specula i e a iables.
A simila app oach o SpLIP[27], called MiniTLS, was de eloped by Yi-
apanis e al. [36]. They in oduced a new s uc u e ha op imized memo y
o e heads o classical app oaches based on he idea o mapping e e y use -
accessed add ess in o an a ay o in ege s using a hash unc ion.
Jimbo ean e al. [13] in oduced a TLS amewo k specially designed o
specula i ely execu e nes ed loops. To do so, au ho s used ea u es o polyhe-
d al model o dynamically ans o m code in a mo e op imized e sion ha led
o highe speedups. F amewo k consis ed on di iding execu ion in wo pa s,
one o gene a e some skele ons, and o he one ha selec ed he op imized code
a un ime.

Es ebanez e al.
3 Desc ip ion o he baseline solu ion
So wa e specula i e schemes should alloca e some addi ional memo y in o de
o hold he in o ma ion ela ed o specula i e execu ions. The use o his da a
is manda o y o enable eco e y ope a ions ha could a ise in an op imis ic
execu ion. In his con ex , memo y needed could be alloca ed dynamically, o
s a ically, and he use o an app oach ins ead o he o he is a c i ical decision
ha di ec ly in luences in he o e all memo y used in a p og am.
Ou en i e esea ch amewo k elies on a i s , poin e -based e sion o a
so wa e-based TLS lib a y ha s ic ly ollows he p inciples o he lib a y
de eloped by Cin a and Llanos [3,4]. Tha wo ks es ablished he ounda ions
o he co ec ness o he specula i e execu ion o sequen ial applica ions. Thei
app oach only allowed o specula e on a iables encapsula ed inside a ec o .
The use o his solu ion equi ed h eads o alloca e memo y o he en i e
ec o , e en i many posi ions o i we e no used du ing he execu ion o
he assigned chunk o i e a ions. So, in he case ha Mwas he specula i e
a iables used in a p oblem execu ed wi h T h eads, and each a iable need
a by e, a iables equi e M×(T+1) by es o be s o ed, because an addi ional
space is equi ed o sa e he pe sis en copy. Mo eo e , using ec o s equi ed
ha all he a iables used had o sha e he same ype.
The e sion ha we use as a baseline in his wo k has been o iginally
p esen ed in [9]. This baseline e sion suppo s he specula i e execu ion o
o loops wi h dynamic and poin e - e e enced specula i e a iables, handling
dynamic memo y and managing on demand he space needed o specula i e
a iables in each h ead. This TLS un ime lib a y allows he pa alleliza ion
o loops wi h a iables o any da a ype, e e encing hese a iables ei he
by name o by add ess. As we will see, al hough his lib a y e ec i ely e-
mo es many cons ains o Cin a and Llanos’ solu ion, he s ic adhe ence
o he o iginal a chi ec u e leads o unaccep able cos s o specula i e eads
and w i es. In his sec ion we will b ie ly show he a chi ec u e o ou lib a y,
since i will be used as he baseline o es some imp o emen s p oposed in
his pape .
3.1 Da a s uc u es
The da a s uc u es needed by he baseline specula i e lib a y a e depic ed in
Fig. 1. A ma ix wi h Wwindow slo s ( ou in he igu e) implemen s a sliding
window ha manages he un ime o he lib a y. Each slo is esponsible o
manage he specula i e execu ion o a pa icula se o i e a ions. The slo s
assigned o he non-specula i e and he mos -specula i e h eads a e indica ed
by wo a iables, non-spec and mos -spec. Each slo is composed o wo ields,
STATE wi h he s a e o he execu ion being ca ied ou in each slo ; and a
poin e o main ain he posi ion o he specula i e a iables used by each slo
in he execu ion.
New Da a S uc u es o Handle Specula i e Pa alleliza ion a Run ime
1
Non−spec window slo
3
Mos −spec window slo
Poin e
o e .
copy
Da a
size
Poin e
o local
e sion
Ve sion
s a e
18.997
b1
9
a1
Poin e
o e .
copy
Da a
size
Poin e
o local
e sion
Ve sion
s a e
7
a3 b3
25.8
&a 1 EXPLD
MOD&b 4 &b3
&a3
18.997
b2 c2
128.215 7
a2
Poin e
o e .
copy
Da a
size
Poin e
o local
e sion
Ve sion
s a e
8&c ELUP&c2
&b 4 EXPLD&b2
&a 1 &a2 MOD
Running Done Running F eeSTATE
Poin e o e sion copy
Sliding window
loa bcha a
double c
9 23.4
32.88
specula i e
a iables
Use −labeled
&a
&b &b1 MOD
EXPLD&a11
4
Ve sion copy da a s uc u es
Slo 1 Slo 2 Slo 3 Slo 4
Fig. 1 Da a s uc u es o ou new specula i e lib a y.
An example o he execu ion o a loop is also depic ed in Fig. 1. The loop
has been di ided in o h ee chunks o i e a ions, and i will be execu ed in
pa allel using h ee h eads. I is e y impo an o unde s and ha he e
is no a ixed associa ion be ween h eads and slo s. Whene e a h ead is
assigned a new chunk o i e a ions, i is also assigned he co esponding slo
o wo k in. This allows o main ain an o de ela ionship among he chunks
being execu ed.
In he depic ed example, h ead wo king in slo 1 is execu ing he non-
specula i e chunk o i e a ions (as indica ed by i s RUNNING s a e); he ol-
lowing chunk has been al eady execu ed and i s da a has been le he e o be
commi ed a e he non-spec chunk inishes (since i is in DONE s a e), while
he las one, he mos -specula i e chunk launched so a , is also RUNNING. In
o he wo ds, he h ead in cha ge o he second chunk has al eady inished,
while he non-spec and mos -spec h eads a e wo king. I mo e chunks we e
pending, he eed h ead would be assigned he ollowing chunk, s a ing i s
execu ion in slo 4. Slo 2 can no be e-used ye , because he execu ion o
chunk 2 le changes o specula i e a iables ha a e ye o be commi ed. As
we will see in Sec . 3.3, when he non-specula i e h ead wo king in slo 1 in-
ishes, i will commi i s esul s and he esul s s o ed in all subsequen DONE
slo s, since commi s should be ca ied ou in o de . A e ha , in ou example,
he non-spec poin e will be ad anced o slo 3 o e lec he new si ua ion.
In addi ion o i s STATE, each slo poin s o a da a s uc u e ha holds he
e sion copies o he da a being specula i ely accessed. Fig. 1 ep esen s a loop
wi h h ee specula i e a iables. A a gi en momen , he h ead execu ing he
non-specula i e chunk has specula i ely accessed a iables aand b. Each ow
o he e sion copy da a s uc u e keeps he in o ma ion needed o manage
Es ebanez e al.
Exp. Loaded and Upda ed
(ELUP)
Exposed Loaded
(EXPLD)
No Accessed
Modi ied
(MOD)
s o e
load
s o e
Spec.
Spec.
Spec.
Spec. load
Spec. load / Spec. s o e
Spec. load / Spec. s o e
Fig. 2 S a e ansi ion diag am o specula i e da a.
he access o a di e en specula i e a iable. The i s column indica es he
add ess o he o iginal a iable, known as he e e ence copy. The second one
indica es he da a size. The hi d one indica es he add ess o he local copy
o his a iable associa ed o his window slo . Finally, he ou h column
indica es he s a e associa ed o his local copy. Once accessed by a h ead, he
e sion copies o he specula i e da a can be in h ee di e en s a es: Exposed
Loaded, indica ing ha he h ead has o wa ded i s alue om a p edecesso
o om he main copy; Modi ied, indica ing ha he h ead has w i en o ha
a iable wi hou ha ing consumed i s o iginal alue; and Exposed Loaded and
Upda ed, whe e a h ead has i s o wa ded he alue o a a iable and has
la e modi ied i . The ansi ion diag am o hese s a es is shown in Fig. 2.
Fig. 1 ep esen s a si ua ion whe e he h ead wo king in slo 1 has pe -
o med a specula i e load om a iable a(ob aining i s alue om he e e -
ence copy) and a specula i e s o e o a iable b. Rega ding a, he igu e shows
ha he h ead wo king in slo 3 has o wa ded i s alue. Wi h espec o
a iable b, he in o ma ion in he igu e shows ha bhas been o e w i en
bo h by h eads wo king in slo s 1 and 3.
3.2 Specula i e loads and s o es
The in e ace o ou implemen a ion o specload() is as ollows:
specload(VOID* add , UINT size, UINT chunk numbe , VOID* alue)
The i s pa ame e is he add ess o he specula i e a iable; he second one
is he size o he a iable; he hi d one is he numbe o he chunk being
execu ed (needed o in e he slo being used); and he ou h one is a poin e
o a place o s o e he da um eques ed.
New Da a S uc u es o Handle Specula i e Pa alleliza ion a Run ime
2
1E
F
A
B
D
G
C3
1
Non−spec window slo
Poin e
o e .
copy
Da a
size
Poin e
o local
e sion
Ve sion
s a e
Poin e
o e .
copy
Da a
size
Poin e
o local
e sion
Ve sion
s a e
18.997
b1
9
a1
9
a3 b3
25.8
18.997
b2 c2
128.215 7
a2
Poin e
o e .
copy
Da a
size
Poin e
o local
e sion
Ve sion
s a e
Slo 1 Slo 2 Slo 3 Slo 4
RunningSTATE
Poin e o e sion copy
Sliding window
loa bcha a
double c
9 23.4
32.88
specula i e
a iables
Use −labeled
&a
&b &b1 MOD
EXPLD&a11
4 &a 1 EXPLD
MOD&b 4 &b3
&a3
8&c ELUP&c2
&b 4 EXPLD&b2
Running
Ve sion copy da a s uc u es
&a 1 &a2 MOD
F eeRunning
SQUASHED
Mos −spec window slo
23
Fig. 3 S eps o a specula i e load (1..3) and specula i e s o e (A..G).
Recall ha specload() should e u n he mos up- o-da e alue a ailable
o he specula i e a iable. Fig. 3 shows how specula i e load wo ks. Suppose
ha he h ead wo king in slo 2 has only accessed a iable cso a , and hen i
calls specload(&b, sizeo (b), 2, & alue) o ob ain a alue o b. The h ead wo king
in slo 2 scans om i s e sion copy da a s uc u e o i s p edecesso s’ un il
he alue is ound (poin 1). O he wise, i alue has no been used be o e, i
is ob ained om e e ence copy. In he Fig. 3 he h ead wo king in slo 1 has
used b, so he h ead ha called specload() copies he alue o i s own local
copy (poin 2), and add a ow o i s e sion copy da a s uc u e. No e ha
he p ocess desc ibed in he poin 1 o Fig. 3, ha is, sea ching o a copy o
a a iable is a sequen ial p ocess ha o igins big bo lenecks.
The in e ace o specs o e() is simila as specload()’s, bu in his case he
las pa ame e is a poin e o he alue o be s o ed. Recall ha specs o e()
should no only s o e he new alue, bu also check whe he a successo has
consumed an ou da ed alue o i . Fig. 3 shows he sequence o e en s ela ed
o a specula i e s o e. Suppose ha he h ead wo king in slo 2 execu es
specs o e(&a, sizeo (a), 2, & emp), whe e emp holds he alue 7. Th ead wo king
in slo 2 sea ches o a local e sion copy o ain i s s uc u e (poin A). I
i was ound, i s local alue would be upda ed, bu in his case, a new ow
is added wi h he add ess o a, i s size, he add ess o he new local e sion
(poin B), and i s s a e (poin C). Then, he h ead ha pe o med he call
should check whe he any successo h ead has consumed an ou da ed alue
o a(poin D). In his case, he h ead wo king in slo 3 has loaded his alue
(poin E), so, i should be squashed (poin s F and G). No e ha he p ocess
desc ibed in he poin D o Fig. 3, ha is, sea ching o copies o ou da ed
a iables is a sequen ial p ocess ha o igins big bo lenecks.
Es ebanez e al.
1
Non-spec window slo
b'
c'
Poin e
o e .
copy
Da a
size
Offse
in local
e sion
Ve sion
s a e
Slo 1 Slo 2 Slo 3 Slo 4
STATE
Poin e o e sion copy
Sliding window
floa b
double c
23.4
32.88
specula i e
a iables
Use -labeled
8&c ELUP0
&b 4 EXPLD8
F ee
Ve sion copy da a s uc u es
F ee
Mos -spec window slo
1
Running F ee
Poin e o local e sion da a
ec o
Local e sion da a s uc u es
Ac ual fi s ee posi ion
12
128.215
01 2 345 6 78 9 10 11 12 13 ...
18.997
Fig. 5 Reducing ope a ing sys em calls: Example wi h he new da a s uc u es
#i de LP64 ypede s uc da acell {
ypede unsigned long long in baseType; oid ∗o igPoin e ;
#else unsigned in copyO se ;
ypede unsigned long in baseType;sho unsigned in size;
#endi sho unsigned in s a e;
}da acell;
... ...
baseType ma ix[HASH][4][ROWS]; da acell ma ix[HASH][ROWS]
... ...
(a) (b)
Fig. 6 Implemen a ion o a s a ic example o he da a s uc u e in (a) he baseline solu ion,
and (b) he imp o ed e sion.
7.2 S uc u es ins ead o bu e s
We ha e also modi ied he implemen a ion o e sion copy da a s uc u es in
o de o imp o e da a alignmen [1] and he space needed by each e sion copy
da a s uc u e. The baseline ep esen a ion is shown in Fig. 6(a). Al hough he
di e en elemen s in a ow ha e di e en sizes, he decla a ion should alloca e
space enough o s o e he bigges one, in ou case he poin e o he o iginal
da a. This implemen a ion equi es 8 by es o each alue, ha is, a o al o
32 by es o he ep esen a ion o each ow. Ou new ep esen a ion, shown
in Fig. 6(b), s a es a iables as a s uc . Wi h his ep esen a ion we achie e
wo goals. Fi s , we educe he necessa y memo y o a hal , since he memo y
needed o s o e his new s uc u e is 16 by es (a oid poin e needs 8 by es,
an unsigned in needs 4 by es, and each unsigned sho in needs 2 by es). Second,
his s uc u e also exploi s he memo y ep esen a ion o C s uc s because hese
ypes a e usually s o ed wi h he ollowing pa e ns[1]: S uc u es be ween 1

New Da a S uc u es o Handle Specula i e Pa alleliza ion a Run ime
0
1
2
3
4
5
6
7
1 3 5 7 9 11 13 15
Speedup
Numbe o p ocesso s
Baseline e sion
Imp o ed e sion
Cin a and Llanos’ e sion
1 3 5 7 9 11 13 15
Numbe o p ocesso s
Baseline e sion
Imp o ed e sion
Cin a and Llanos’ e sion
(a) (b)
0
1
2
3
4
5
6
7
1 3 5 7 9 11 13 15
Speedup
Numbe o p ocesso s
Baseline e sion
Imp o ed e sion
Cin a and Llanos’ e sion
(c)
Fig. 7 Pe o mance compa ison o 2D-Hull benchma k wi h h ee di e en inpu se s: (a)
Disc, (b) Squa e, and (c) Kuzmin.
and 4 by es o da a a e usually padded so ha he o al s uc u e is 4 by es;
S uc u es be ween 5 and 8 by es o da a a e padded so ha he o al s uc u e
is 8 by es; s uc u es be ween 9 and 16 by es o da a a e padded so ha he
o al s uc u e is 16 by es; and s uc u es g ea e han 16 by es a e padded
o 16 by e bounda y. A di e en o de o he a iables would add paddings
because he compile may decide o s o e hem in 4-by es places. The e o e,
ou new s uc u e is op imized o minimize he memo y space needed, hus
educing he numbe o cache misses.
8 Expe imen al esul s
Figs. 7 compa e he pe o mance esul s o he specula i e pa alleliza ion o
he 2D-Hull wi h inpu se s. Bo h he baseline e sion o he lib a y and ou
new solu ion a e compa ed. While he baseline sys em is no able o ob ain
speedups in any case, he new solu ion leads o a maximum speedup o 1.681×
o he Disc inpu se ( ep esen ing a 28×pe o mance inc emen wi h espec
o he baseline TLS lib a y), 3.094× o he Squa e inpu se (14.19×pe o -
mance inc emen ) and 4.188× o Kuzmin (8.63×pe o mance inc emen ). To
Es ebanez e al.
0
1
2
3
4
5
6
7
8
1 3 5 7 9 11 13 15
Speedup
Numbe o p ocesso s
Baseline e sion
Imp o ed e sion
Cin a and Llanos’ e sion
1 3 5 7 9 11 13 15
Numbe o p ocesso s
Baseline e sion
Imp o ed e sion
Cin a and Llanos’ e sion
(d) (e)
Fig. 8 Pe o mance compa ison o Delaunay benchma k wi h an inpu se o (a) 100K
poin s, and (b) 1M poin s.
pu hese esul s in o pe spec i e, we also show he bes speedups ob ained
by Cin a and Llanos wi h hei specula i e un ime sys em. Recall ha hei
solu ion, while e ec i e, is cons ained by many limi a ions, and i is no gen-
e alizable o any applica ions. Resul s show ha ou solu ion allows o deli e
a good pe cen age o he maximum speedup a ainable (up o 68%), while
o e ing a specula i e solu ion applicable in many mo e cases.
Figs. 8 compa es he pe o mance esul s o he specula i e pa alleliza ion
o he Delaunay iangula ion wi h wo inpu se s. The new solu ion is again
clea ly be e , wi h a maximum speedup o 3.646× o he 1M-poin s inpu
se ( ep esen ing a 3.58×pe o mance inc emen wi h espec o he baseline
TLS lib a y), and 3.873× o he 100K-poin s inpu se (5.40×pe o mance
inc emen ). Again, ou solu ion is compa ed o he ailo ed lib a y o Cin a
and Llanos, ob aining, on a e age, a 75% and a 68% o hei maximum speedup
in he 1M-poin s and he 100K-poin s inpu se s, espec i ely.
9 Conclusions
In his pape , we ha e shown a solu ion o a p oblem ha is common o any
so wa e-based TLS lib a y: How o educe sea ch imes when accessing o
emo e e sions o specula i e da a. To mi iga e his p oblem, we ha e im-
plemen ed some op imiza ions such as he use o an ex emely-simple hash
unc ion o a oid he need o a e sing all e sion da a, he educ ion in he
numbe o memo y managemen sys em calls, and he de elopmen o new
da a s uc u es o educe memo y consump ion and cache misses. Ou expe -
imen al e alua ion wi h non-syn he ic benchma ks on a eal, sha ed-memo y
mul ip ocesso clea ly shows ha hese imp o emen s ha e a d ama ic im-
pac on pe o mance: All applica ions es ed had a be e execu ion imes
han hose ob ained in he baseline e sion, and he pe o mance esul s a e
a signi ican ac ion o hose ob ained wi h a sys em speci ically designed o
handle hese benchma ks.
New Da a S uc u es o Handle Specula i e Pa alleliza ion a Run ime
Acknowledgemen s The au ho s would like o hank he anonymous e iewe s o hei
help ul commen s. The au ho s would also like o hank M . Se gio Aldea o his help in
his wo k. This esea ch is pa ly suppo ed by he Cas illa-Leon Regional Go e nmen
(VA172A12-2); Minis e io de Indus ia, Spain (CENIT OCEANLIDER); MICINN (Spain)
and he Eu opean Union FEDER (MOGECOPP p ojec TIN2011-25639, CAPAP-H3 ne -
wo k TIN2010-12011-E, CAPAP-H4 ne wo k TIN2011-15734-E).
Re e ences
1. B yan , R., Da id Richa d, O.: Compu e sys ems: a p og amme ’s pe spec i e. P en ice
Hall (2003)
2. Ceze, L., Tuck, J., To ellas, J., Casca al, C.: Bulk disambigua ion o specula i e h eads
in mul ip ocesso s. In: P ocs o he 33 d in l symposium on Compu e A chi ec u e,
ISCA ’06. IEEE Compu e Socie y, Washing on, DC, USA (2006)
3. Cin a, M., Llanos, D.R.: Towa d e icien and obus so wa e specula i e pa alleliza ion
on mul ip ocesso s. In: P oceedings o he SIGPLAN Symposium on P inciples and
P ac ice o Pa allel P og amming (PPoPP) (2003)
4. Cin a, M., Llanos, D.R.: Design space explo a ion o a so wa e specula i e pa alleliza-
ion scheme. IEEE T ans. on Pa al. and Dis . Sys ems 16(6), 562–576 (2005)
5. Cin a, M., Ma ´ınez, J.F., To ellas, J.: A chi ec u al suppo o scalable specula i e
pa alleliza ion in sha ed-memo y mul ip ocesso s. In: P oc. o he 27 h in l. symp. on
Compu e a chi ec u e (ISCA), pp. 256–264 (2000)
6. Cla kson, K.L., Mehlho n, K., Seidel, R.: Fou esul s on andomized inc emen al con-
s uc ions. Compu . Geom. Theo y Appl. 3(4), 185–212 (1993)
7. Dai, W., An, H., Li, Q., Li, G., Deng, B., Wu, S., Li, X., Liu, Y.: A p io i y-awa e
NoC o educe squashes in h ead le el specula ion o chip mul ip ocesso s. In: P ocs
o he 2011 IEEE 9 h In . Symposium on Pa allel and Dis ibu ed P ocessing wi h
Applica ions, ISPA ’11. IEEE Compu e Socie y, Washing on, DC, USA (2011)
8. Dou, J., Cin a, M.: Compile es ima ion o load imbalance o e head in specula i e pa -
alleliza ion. In: P ocs o he 13 h In . Con . on Pa allel A chi ec u es and Compila ion
Techniques, PACT ’04. IEEE Compu e Socie y, Washing on, DC, USA (2004)
9. Es ebanez, A., Llanos, D.R., Gonzalez-Esc ibano, A.: Desa ollo de un mo o de pa -
alelizaci´on especula i a con sopo e pa a a i m´e ica de pun e os. In: P oceedings o he
XXIII Jo nadas de Pa alelismo. Elche, Alican e, Spain (2012)
10. Gao, L., Li, L., Xue, J., Yew, P.C.: SEED: A s a ically-g eedy and dynamically-adap i e
app oach o specula i e loop execu ion. IEEE T ansac ions on Compu e s 62(5) (2013)
11. Hammond, L., Hubbe , B.A., Siu, M., P abhu, M.K., Chen, M., Oluko un, K.: The
s an o d Hyd a CMP. IEEE Mic o 20(2), 71–84 (2000)
12. Ha is, T., Plesko, M., Shinna , A., Ta di i, D.: Op imizing memo y ansac ions. In:
P oceedings o he 2006 ACM SIGPLAN Con e ence on P og amming Language Design
and Implemen a ion, PLDI ’06, pp. 14–25. ACM, New Yo k, NY, USA (2006)
13. Jimbo ean, A., Clauss, P., Dollinge , J.F., Loechne , V., Ma inez Caamao, J.: Dynamic
and specula i e polyhed al pa alleliza ion using compile -gene a ed skele ons. In e na-
ional Jou nal o Pa allel P og amming pp. 1–17 (2013)
14. Kelsey, K., Bai, T., Ding, C., Zhang, C.: Fas ack: A so wa e sys em o specula i e
p og am op imiza ion. In: P ocs o he 7 h annual IEEE/ACM In l symp on Code
gene a ion and op imiza ion, CGO ’09 (2009)
15. K ishnan, V., To ellas, J.: A chip-mul ip ocesso a chi ec u e wi h specula i e mul i-
h eading. Compu e s, IEEE T ansac ions on 48(9), 866–880 (1999)
16. Kulka ni, M., Bu sche , M., Inkulu, R., Pingali, K., Cas¸ca al, C.: How much pa allelism
is he e in i egula applica ions? In: P ocs o he 14 h ACM SIGPLAN Symposium on
P inciples and P ac ice o Pa allel P og amming, PPoPP ’09. New Yo k, USA (2009)
17. Kulka ni, M., Ca ibaul , P., Pingali, K., Ramana ayanan, G., Wal e , B., Bala, K.,
Chew, L.P.: Scheduling s a egies o op imis ic pa allel execu ion o i egula p og ams.
In: P ocs o he 20 h Annual Symposium on Pa allelism in Algo i hms and A chi ec-
u es, SPAA ’08, pp. 217–228. ACM, New Yo k, NY, USA (2008)
Es ebanez e al.
18. Kulka ni, M., Nguyen, D., P oun zos, D., Sui, X., Pingali, K.: Exploi ing he commu a-
i i y la ice. In: P ocs o he 32nd ACM SIGPLAN Con on P og amming Language
Design and Implemen a ion, PLDI ’11. ACM, New Yo k, NY, USA (2011)
19. Kulka ni, M., Pingali, K., Ramana ayanan, G., Wal e , B., Bala, K., Chew, L.P.: Op i-
mis ic pa allelism bene i s om da a pa i ioning. In: P oceedings o he 13 h In e na-
ional Con e ence on A chi ec u al Suppo o P og amming Languages and Ope a ing
Sys ems, ASPLOS XIII, pp. 233–243. ACM, New Yo k, NY, USA (2008)
20. Kulka ni, M., Pingali, K., Wal e , B., Ramana ayanan, G., Bala, K., Chew, L.P.: Op i-
mis ic pa allelism equi es abs ac ions. In: PLDI 2007 P oceedings. ACM (2007)
21. Kulka ni, M., Pingali, K., Wal e , B., Ramana ayanan, G., Bala, K., Chew, L.P.: Op i-
mis ic pa allelism equi es abs ac ions. Commun. ACM 52(9), 89–97 (2009)
22. Lee, D., Schach e , B.: Two algo i hms o cons uc ing a delaunay iangula ion. In-
e na ional Jou nal o Compu e & In o ma ion Sciences 9(3), 219–242 (1980)
23. M. Gup a and R. Nim: Techniques o specula i e un- ime pa alleliza ion o loops.
Supe compu ing (1998)
24. Ma cuello, P., Gonzalez, A., Tubella, J.: Specula i e mul i h eaded p ocesso s. In: P ocs
o he 12 h In l con e ence on Supe compu ing, ICS ’98. ACM, New Yo k, USA (1998)
25. Meh a a, M., Hao, J., Hsu, P.C., Mahlke, S.: Pa allelizing sequen ial applica ions on
commodi y ha dwa e using a low-cos so wa e ansac ional memo y. In: P ocs o he
2009 con on P og. language design and implemen a ion, PLDI ’09. NY, USA (2009)
26. M´endez-Lojo, M., Nguyen, D., P oun zos, D., Sui, X., Hassaan, M.A., Kulka ni, M.,
Bu sche , M., Pingali, K.: S uc u e-d i en op imiza ions o amo phous da a-pa allel
p og ams. In: P oceedings o he 15 h ACM SIGPLAN Symposium on P inciples and
P ac ice o Pa allel P og amming, PPoPP ’10, pp. 3–14. ACM, New Yo k, USA (2010)
27. Oancea, C.E., Myc o , A., Ha is, T.: A ligh weigh in-place implemen a ion o so -
wa e h ead-le el specula ion. In: P oceedings o he wen y- i s annual symposium on
Pa allelism in algo i hms and a chi ec u es, SPAA ’09. ACM, New Yo k, USA (2009)
28. P abhu, M.K., Oluko un, K.: Using h ead-le el specula ion o simpli y manual pa al-
leliza ion. In: P oceedings o he Nin h ACM SIGPLAN Symposium on P inciples and
P ac ice o Pa allel P og amming, PPoPP ’03. ACM, New Yo k, NY, USA (2003)
29. Raman, E., Vahha ajani, N., Rangan, R., Augus , D.I.: Spice: specula i e pa allel i -
e a ion chunk execu ion. In: P ocs o he 6 h annual IEEE/ACM In l symposium on
Code gene a ion and op imiza ion, CGO ’08. ACM, New Yo k, USA (2008)
30. Rauchwe ge , L., Padua, D.: The LRPD es : Specula i e un- ime pa alleliza ion o
loops wi h p i a iza ion and educ ion pa alleliza ion. SIGPLAN No . 30(6) (1995)
31. Sanka alingam, K., Naga ajan, R., Liu, H., Kim, C., Huh, J., Bu ge , D., Keckle , S.,
Moo e, C.: Exploi ing ILP, TLP, and DLP wi h he polymo phous TRIPS a chi ec u e.
In: P ocs o he 30 h Annual In l Symp on Compu e A chi ec u e, ISCA ’03 (2003)
32. S e an, J.G., Colohan, C.B., Zhai, A., Mow y, T.C.: A scalable app oach o h ead-le el
specula ion. In: P oceedings o he 27 h annual in e na ional symposium on Compu e
a chi ec u e, ISCA ’00, pp. 1–12. ACM, New Yo k, NY, USA (2000)
33. Tian, C., Feng, M., Gup a, R.: Suppo ing specula i e pa alleliza ion in he p esence o
dynamic da a s uc u es. In: P ocs o he 2010 ACM SIGPLAN con on P og amming
language design and implemen a ion, PLDI ’10. ACM, New Yo k, NY, USA (2010)
34. Tian, C., Feng, M., Naga ajan, V., Gup a, R.: Copy o disca d execu ion model o
specula i e pa alleliza ion on mul ico es. In: P ocs o he 41s annual IEEE/ACM In l
Symp on Mic oa chi ec u e, MICRO ’41. Washing on, DC, USA (2008)
35. Tian, C., Feng, M., Naga ajan, V., Gup a, R.: Specula i e pa alleliza ion o sequen ial
loops on mul ico es. In . J. Pa allel P og am. 37(5), 508–535 (2009)
36. Yiapanis, P., Rosas-Ham, D., B own, G., Luj´an, M.: Op imizing so wa e un ime sys-
ems o specula i e pa alleliza ion. ACM T ans. A chi . Code Op im. 9(4) (2013)
37. Zhao, Z., Wu, B., Shen, X.: Specula i e pa alleliza ion needs igo : p obabilis ic analysis
o op imal specula ion o ini e-s a e machine applica ions. In: P ocs 21s In l Con on
Pa allel a chi ec u es and compila ion echniques, PACT ’12. New Yo k, USA (2012)