ZZ
A Su ey on Th ead-Le el Specula ion Techniques
Al a o Es ebanez, Uni e sidad de Valladolid
Diego R. Llanos, Uni e sidad de Valladolid
A u o Gonzalez-Esc ibano, Uni e sidad de Valladolid
Th ead-Le el Specula ion (TLS) is a p omising echnique ha allows he pa allel execu ion o sequen ial
code wi hou elying on a p io , compile- ime dependence analysis. In his wo k we in oduce he echnique,
p esen a axonomy o TLS solu ions, and summa ize and pu in o pe spec i e he mos ele an ad ances
in his ield.
Ca ego ies and Subjec Desc ip o s: F.1.2 [Modes o Compu a ion]: Pa allelism and Concu ency; D.1.3
[Concu en p og amming]: Pa allel p og amming
Gene al Te ms: Run ime pa alleliza ion
Addi ional Key Wo ds and Ph ases: Specula i e mul i h eading, specula i e un ime pa alleliza ion,
h ead-le el da a specula ion, TLDS, op imis ic pa alleliza ion, h ead-le el specula ion, TLS
ACM Re e ence Fo ma :
Al a o Es ebanez, Diego R. Llanos, A u o Gonzalez-Esc ibano, 2014. A Su ey on Th ead-Le el Specula ion
Techniques. ACM Compu . Su . X, Y, A icle ZZ ( 20YY), 40 pages.
DOI:h p://dx.doi.o g/10.1145/0000000.0000000
1. INTRODUCTION
Th ead-Le el Specula ion (TLS), also called Specula i e Pa alleliza ion (SP), o e en
Op imis ic Pa alleliza ion, is a un ime echnique ha execu es in pa allel agmen s
o code ha we e o iginally in ended o un sequen ially. Ins ead o elying on compile-
ime analysis o iden i y independen pa s o sequen ial code ha can be un con-
cu en ly, TLS echniques op imis ically assume ha hese pa s can be execu ed in
pa allel by di e en h eads. To ensu e co ec ness, specula i e h eads should de ec
whe he hey ha e consumed a da um ha was subsequen ly upda ed by a p edecces-
so h ead, ha is, a h ead execu ing an ea lie pa o he code, acco ding o sequen-
ial seman ics. Such si ua ions, called dependence iola ions, should be de ec ed and
ec i ied by ha dwa e o so wa e mechanisms, o a combina ion o bo h, o keep se-
quen ial seman ics. I a dependence iola ion is de ec ed, a co ec i e ac ion will ake
place, ypically disca ding he esul s calcula ed by he h ead ha has consumed he
inco ec alue, and es a ing i o be ed wi h he upda ed da um.
In his pape we e iew he li e a u e ela ed o Th ead-Le el Specula ion ech-
niques, p esen ing a axonomy ha helps o be e unde s and each p oposed solu ion
in i s con ex . The pape is o ganized as ollows. Sec ion 2 p esen s a global iew o he
This esea ch has been pa ially suppo ed by MICINN (Spain) and ERDF p og am o he Eu opean Union:
HomP og-He Sys p ojec (TIN2014-58876-P), CAPAP-H5 ne wo k (TIN2014-53522-REDT), and COST P o-
g am Ac ion IC1305: Ne wo k o Sus ainable Ul ascale Compu ing (NESUS).
Au ho ’s add esses: A. Es ebanez, D. R. Llanos and A. Gonzalez-Esc ibano, Depa amen o de In o m´
a ica,
Uni e sidad de Valladolid, Paseo Bel´
en 15, Valladolid, Spain.
Pe mission o make digi al o ha d copies o pa o all o his wo k o pe sonal o class oom use is g an ed
wi hou ee p o ided ha copies a e no made o dis ibu ed o p o i o comme cial ad an age and ha
copies show his no ice on he i s page o ini ial sc een o a display along wi h he ull ci a ion. Copy igh s
o componen s o his wo k owned by o he s han ACM mus be hono ed. Abs ac ing wi h c edi is pe -
mi ed. To copy o he wise, o epublish, o pos on se e s, o edis ibu e o lis s, o o use any componen
o his wo k in o he wo ks equi es p io speci ic pe mission and/o a ee. Pe missions may be eques ed
om Publica ions Dep ., ACM, Inc., 2 Penn Plaza, Sui e 701, New Yo k, NY 10121-0701 USA, ax +1 (212)
869-0481, o [email p o ec ed].
c
20YY ACM 0360-0300/20YY/-ARTZZ $15.00
DOI:h p://dx.doi.o g/10.1145/0000000.0000000
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
ZZ:2 A. Es ebanez, D. R. Llanos, and A. Gonzalez-Esc ibano
p oblem, including a desc ip ion o sou ces o specula ion in he code, oge he wi h
he main design choices ha may a ise while designing a TLS solu ion. Sec ion 3 ex-
amines he i s solu ions ha se ed as a base o he de elopmen o TLS sys ems.
Sec ion 4 de ails ha dwa e-based app oaches, whe e addi ional ha dwa e is added o
suppo specula ion. Sec ion 5 shows so wa e-based p oposals, which do no equi e
addi ional ha dwa e o moni o he pa allel execu ion, a he cos o a ce ain pe o -
mance loss. Sec ion 6 desc ibes o he wo ks ha ake ad an age o TLS capabili ies o
di e en pu poses. Sec ion 7 ci es some s udies ha ha e poin ed ou he heo e ical
and p ac ical limi s o he TLS pa adigm. Finally, Sec ion 8 concludes ou pape .
2. SOURCES OF TLS AND DESIGN CHOICES
In [To ellas 2011], an accu a e summa y o Th ead-Le el Specula ion echniques is
gi en, including a de ailed desc ip ion o he wo main issues ha any TLS sys em
should sol e: How o bu e and manage specula i e s a es, and how o de ec and
handle dependence iola ions. His analysis makes any e o o ep oduce a summa y
o TLS cha ac e is ics he e meaningless: we sugges he eade o consul his wo k o
be e unde s and he undamen als o he ield and he managemen o side e ec s
due o he use o h ead-le el specula ion. In his sec ion, we will b ie ly discuss whe e
a e he main sou ces o specula ion, how TLS echniques can be classi ied, and which
a e he mos impo an design choices ha ha e o be aced o se up a TLS sys em.
2.1. Loops as a sou ce o specula ion
Due o how easy i is o dis ibu e wo k among h eads, loops a e he mos impo -
an sou ce o TLS. The syn hesis o loop-based specula ion w i en by [Rauchwe ge
2011], who was also a pionee in he ield, accu a ely e lec s he impo ance o loops as
a sou ce o specula ion. Unde TLS, loops a e di ided in o blocks o i e a ions ha a e
dispa ched o be op imis ically execu ed in pa allel, while a moni o ensu es ha he
execu ion ollows sequen ial seman ics. I his is no he case, he moni o squashes
o ending h eads, es a ing hem wi h he co ec alues. O he wise, e sion da a
s o ed in he local specula i e bu e s a e commi ed o he main copy. We will i s
b ie ly desc ibe how da a p ocessed in one i e a ion may in e ac wi h calcula ions in
di e en i e a ions, a si ua ion known as da a dependence.
The e a e h ee basic ypes o da a dependences among wo agmen s o code,
namely ue,an i, and ou pu dependences. In he ollowing examples, le Siand Sj
be wo s a emen s, whe e Sishould be execu ed ea lie han Sjacco ding o sequen-
ial seman ics.
—T ue dependence: S a emen Siw i es in o a loca ion ha is la e ead by Sj. These
si ua ions a e also called RAW (Read A e W i e) con lic s, o low dependences.
—An i dependence: S a emen Si eads a loca ion ha is la e w i en by Sj. These
si ua ions a e also called WAR (W i e A e Read) con lic s.
—Ou pu dependence: Bo h s a emen s Siand Sjw i e in o he same loca ion. These
si ua ions a e also called WAW (W i e A e W i e) con lic s.
These de ini ions can be used o c ea e a axonomy o loops, acco ding o he p esence
o da a dependences among hei i e a ions. One o he i s axonomies was p oposed
by [Polych onopoulos and Kuck 1987]. This wo k classi ied loops in o h ee di e en
ypes: doall, o all, and doac oss.
—Doall loops: Loops ha do no p esen any dependence among hei i e a ions. The e-
o e, all i e a ions can be p ocessed in pa allel wi h no u he checking [Tang and
Yew 1986]. Figu e 1(a) shows an example o his loop. Mos o cu en compile s can
pa allelize his kind o loops au oma ically.
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
A Su ey on Th ead-Le el Specula ion Techniques ZZ:3
o (i=0; i<SIZE; i++)
V[i] = i; // S a emen S
(a) DOALL Loop
o (i=0; i<SIZE; i++) {
V[i] = ... ; // S a . S1
}
(b) FORALL Loop
o (i=0; i<SIZE; i++) {
... = (V[i-x]); // S a . S1 (x>0)
V[i] = ... ; // S a . S2
}
o (i=0; i<SIZE; i++) {
V[W[i]] = ...; // S a . S1
... = (V[Z[i]]); // S a . S2
}
o (i=0; i<SIZE; i++) {
... = (V[i-1]); // S a . S1
V[i] = ...; // S a . S2
}
(c) Regula DOACROSS Loop
(e) I egula DOACROSS Loop
(d) DOSEQUENTIAL/DOSERIAL Loop
S
Loop body
S1
S2
x
i
j
... = (V[i-x]); // S a . S2 (x>0)
Dependency g aph
i
S2i
S1j
Loop body Dependency g aph
Loop body Dependency g aph
Loop body Dependency g aph
S1
S2
x
i
j
S2i
S1j
Sync needed
Sync needed
?
S1i
S2j
S2i
S1j
Loop body Dependency g aph
S1
S2
1
i
j
S2i
S1j
Sync needed
Time
Time
Time
Time
Fig. 1. Di e en ypes o loops acco ding o he p esence o da a dependences. The label in each edge ep-
esen s he dependence dis ance. Da a lows a e ep esen ed by he a ow di ec ions.
—Fo all loops: Loop whose i e a ions may p esen ue ( ha is, RAW) dependences:
Values p oduced by one i e a ion may be used in a subsequen i e a ion. An example
is depic ed in Fig. 1(b). All i e a ions o a o all loop can be execu ed simul aneously i
and only i all he s a emen s ha p oduce he alue (S1 in he igu e) ha e inished
be o e he execu ion o any s a emen ha consumes he alue (S2 in he igu e). I
his beha io canno be gua an eed, a synch oniza ion mechanism is needed.
—Doac oss loops: Loops ha may ha e c oss-i e a ion an i (also known as WAR o
backwa d) dependences. [K o hapalli and Sadayappan 1990] di ides doac oss loops
in o h ee ca ego ies:
—Regula doac oss loops: Loops whose an i dependences among i e a ions a e domi-
na ed by a cons an alue x. Figu e 1(c) shows an example. Regula doac oss loops
wi h x>1can be pa allelized by ensu ing ha he execu ion o he i e a ions in-
ol ed in he dependence ollows sequen ial seman ics. I he alue o xis known
a compile ime, compile s a e usually able o p oduce a pa allel e sion o he
loop.
—Dosequen ial o dose ial loops: A special ype o egula doac oss whose i e a ions
depend on he p e ious one ( ha is, loops ha ha e a dependence dis ance x=1).
Figu e 1(d) shows an example whe e he dependence is om he las s a emen o
he body o he loop o he i s s a emen . These loops ha e no pa allelism a he
i e a ion le el.
—I egula doac oss loops: Loops whose an i (also kwown as backwa d) dependences
among i e a ions a e no known a compile ime. Figu e 1(e) shows an example.
These loops a e commonly called “i egula loops”, and in gene al hey canno be
pa allelized sa ely a compile ime.
Compile- ime echniques can be used o gene a e pa allel e sions o doall, o all
and, when he dependence dis ance is known a compile ime, egula doac oss loops.
Since TLS is a un ime echnique, i can use he a ailable in o ma ion in all o he de-
sc ibed loops, including i egula doac oss loops. Wi h espec o dosequen ial loops, a
TLS sys em will also gua an ee ha he pa allel execu ion will be co ec , a he cos o
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
ZZ:4 A. Es ebanez, D. R. Llanos, and A. Gonzalez-Esc ibano
squashing and e-s a ing i e a ions con inuously o ollow sequen ial seman ics, hus
deg ading pe o mance. The main applica ion o TLS is in he pa allel execu ion o i -
egula doac oss loops when he o al numbe o dependences ha appea a un ime
is low.
2.2. D awbacks o TLS
Al hough TLS can ex ac pa allelism e en om i egula doac oss loops, i will likely
be slowe han a compile- ime pa alleliza ion, i he la e can be applied. Sou ces
o o e head in TLS include he cos associa ed o h ead squash and es a due o
da a dependence iola ions, specula i e bu e o e lows, load imbalance due o da a
locali y issues, h ead dispa ch and commi , and in e - h ead communica ions [Dou
and Cin a 2004].
TLS o e heads may no only lead o lowe pe o mance in e ms o execu ion ime,
bu also o a g ea e ene gy consump ion. This issue appea s in so wa e solu ions,
due o he ene gy cos associa ed o he execu ion o addi ional ins uc ions o gua -
an ee ha sequen ial seman ics a e ollowed, and o he was ed wo k ca ied ou by
squashed h eads. Ene gy ine iciencies also appea in ha dwa e app oaches, due o
he need o addi ional ha dwa e s uc u es in he cache hie a chy o da a e sioning,
dependence checking, and i s associa ed bus a ic [Renau e al. 2005]. We will e u n
o his p oblem in Sec . 6.3.
2.3. A i s classi ica ion o TLS echniques
Acco ding o [Ma cuello e al. 1998; Keja iwal e al. 2006], he e a e h ee ypes o
specula ion echniques: (1) con ol specula ion; (2) da a dependence specula ion; and
(3) da a alues specula ion (also called alue p edic ion). These ypes a e no disjoin ,
and hei basis can be combined o achie e be e esul s.
2.3.1. Con ol specula ion. Con ol specula ion applies specula ion o loops ha include
condi ional sen ences. Execu ion pa hs o each i e a ion a e de ec ed, mapping hem o
di e en h eads. [Jacobson e al. 1997b; Wallace e al. 1998; Akka y and D iscoll 1998]
combined con ol specula ion wi h b anch p edic ion. [Puiggali e al. 2012] ied o
p edic he ou come o condi ional b anches wi hou he need o know all he a iables
implied in he condi ion.
2.3.2. Da a dependence specula ion. Da a dependence specula ion is a echnique sui -
able o he pa allel execu ion o loops ha may lead o in e - h ead memo y depen-
dences. Load ope a ions om specula i e a iables ( ha is, a iables whose use may
lead o a dependence iola ion) usually e u n he mos ecen alue o ha a i-
able, while specula i e s o e ope a ions sea ch o he use o inco ec alues in hose
h eads, execu ing subsequen i e a ions acco ding o sequen ial seman ics. Many e-
sea che s ha e con ibu ed o his solu ion: Please e e o [Rauchwe ge and Padua
1995; F anklin and Sohi 1996; B each 1998; Ma cuello e al. 1998; Cin a and Llanos
2003; Tian e al. 2008].
2.3.3. Da a alues specula ion. Da a alue specula ion echniques, also known as alue
p edic ion echniques, p edic a un ime he esul o ins uc ions be o e hei exe-
cu ion. This app oach is based on he idea ha an accu a e p edic ion may a oid a
squash. Fo example, he wo k by [Raman e al. 2008] desc ibes a p edic ion-based
TLS so wa e ha p edic ed alues o he ollowing i e a ions wi hou speci ying he
i e a ion whe e a alue would be aken om. The main disad an age o hese p opos-
als is ha , in gene al, o loops wi h i egula memo y accesses and complex con ol
low, his solu ion does no ob ain good p edic ions. O he wo ks ha use p edic o s
a e [Sohi e al. 1995; Akka y and D iscoll 1998; Cod escu and Wills 1999a; S e an
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
A Su ey on Th ead-Le el Specula ion Techniques ZZ:5
e al. 2002; Cin a and To ellas 2002; P abhu and Oluko un 2003; Li e al. 2005; Tian
e al. 2010a; Fan e al. 2012; Gao e al. 2013].
2.4. Design choices o e iew
To be specula i ely execu ed, he o iginal code should be ins umen ed a compile o
un ime o handle di e en ope a ions, such as loading and s o ing o specula i e da a,
pe o ming commi ope a ions i he specula i e execu ion succeeds, and disca ding
inco ec wo k i i does no . The main design choices ha should be aced in a TLS
sys em a e desc ibed in [Yiapanis e al. 2013]. To implemen a TLS sys em, a numbe
o decisions should be aken1:
2.4.1. Me ada a managemen . TLS app oaches should manage some in o ma ion in o -
de o de ec whe he a dependence iola ion has occu ed. Thus, each h ead should
know bo h wha memo y add esses ha e been used, wha ope a ions ha e been done,
and which h ead has done each ope a ion. All his in o ma ion is collec i ely known
as me ada a [Yiapanis e al. 2013], and i s managemen has wo goals: P ese ing he
in o ma ion ela ed o a iables a isk o su e ing iola ions, such as which h ead
has loaded, s o ed, o is locking a ce ain a iable; and main aining e e ences abou
ope a ions done by each h ead, speci ically, eco ding he a iables loaded o w i en.
The choice o he da a s uc u e o handle me ada a may se e ely a ec pe o mance,
depending on he ela i e cos s o accessing and upda ing in o ma ion du ing he pa -
allel execu ion. An example o such adeo can be ound in [Es ebanez e al. 2014a].
2.4.2. Ve sion Managemen . When execu ing se e al consecu i e agmen s o sequen-
ial code in pa allel, each h ead usually main ains a e sion copy o he da a s uc u e
ha is accessed specula i ely. This solu ion allows changes o his da a o be pe o med
locally, only s o ing hese changes o a pe manen place i he specula i e execu ion o
his h ead p o es success ul. To do so, TLS sys ems equi e some addi ional s o age
o main ain he in e media e copies o each h ead. The e a e wo ways o managing
hese da a:
—Lazy Ve sion Managemen . In his case, a local copy o he exposed da a is indi id-
ually s o ed and managed. The e o e, when a load o s o e ope a ion is pe o med,
only he local e sion is changed. When a RAW dependence iola ion is de ec ed,
only local e sions o h eads in con lic ha e o be disca ded, ins ead o modi ying
he e e ence e sion in memo y2.
— The o he app oach, Eage Ve sion Managemen , equi es ewe esou ces, because
he e e ence e sion in memo y is modi ied. An addi ional bu e (called undo log in
he li e a u e) eco ds old alues and is used o es o e o iginal da a in he case o a
dependence iola ion.
Rega ding e sion managemen , [Ga za ´
an e al. 2003; Ga za ´
an e al. 2005] p o-
posed a axonomy o classi y specula i e sys ems acco ding o he way o bu e ing he
specula i e e sions o a iables. They ook in o accoun he isola ion o specula i e
h ead s a es in each p ocesso , and how he new da a e sions p oduced by specula-
i e h eads is me ged wi h he main memo y.
2.4.3. Con lic De ec ion. Dependence iola ions can be checked wi h ei he a lazy o an
eage app oach: Lazy Con lic De ec ion a oids he need o check o con lic s on e e y
access, by delaying his ask o a la e s age be o e he commi ope a ion. This solu-
1Unless o he wise no ed, he ollowing discussion applies o bo h loop-le el and block-le el TLS sys ems.
2No e ha WAW dependence iola ions can be a oided by a commi ope a ion ha ollows sequen ial se-
man ics. Rega ding WAR dependences, he use o local e sions o exposed da a a oids his p oblem.
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.

ZZ:6 A. Es ebanez, D. R. Llanos, and A. Gonzalez-Esc ibano
ion implies o s o e he sequence o accesses o each specula i e da um by di e en
h eads, in o de o ensu e ha all accesses we e pe o med ollowing sequen ial se-
man ics. Al hough his app oach a oids ime-consuming checks du ing he specula i e
execu ion, he amoun o wo k ha migh be po en ially disca ded is much highe . A
mo e s ic app oach, called Eage Con lic De ec ion, looks o po en ial dependence
iola ions on e e y access. This design a oids pe o mance losses p oduced by la e
checks, by squashing and es a ing h eads as soon as a dependence iola ion is p o-
duced. Howe e , he ime de o ed o checking each po en ial dependence iola ion is
much highe , slowing down he pa allel execu ion e en when no dependence iola ions
a ise.
2.4.4. Scheduling o i e a ions. To specula i ely pa allelize a loop, i should be pa i-
ioned in o chunks (o blocks) o i e a ions o be assigned o di e en h eads. Ea ly
app oaches included a compile phase capable o classi ying i e a ions in o se s o in-
dependen i e a ions. Al hough i e a ions wi hin a se should be execu ed in o de ,
he se s should be execu ed sequen ially, in o de o a oid dependence iola ions. This
compile- ime scheduling solu ion came a he cos o pe o ming a cos ly analysis, ha
in many cases could no be ca ied ou due o i s complexi y and/o he p esence o po-
en ial dependence iola ions ha depended on un ime in o ma ion. In hese cases,
he simples solu ion is o use chunks o ixed size [K uskal and Weiss 1985]. The
pa icula size chosen is an impo an design decision. The use o smalle chunks will
educe squashing cos s, a he cos o a highe scheduling o e head. On he o he hand,
bigge chunks will inc ease he cos o h ead squashing and may lead o load imbal-
ance.
To mi iga e hese p oblems, a iable chunk size s a egies o iginally designed o
achie e load balancing in pa allel compu a ions, such as [Hummel e al. 1992; Poly-
ch onopoulos and Kuck 1987], can also be used in specula i e execu ion. Rega ding
he pa icula con ex o TLS, [Llanos e al. 2007] p oposed a a iable chunk size o
he specula i e execu ion o andomized inc emen al algo i hms, an impo an class o
p oblems whe e he p obabili y o a dependence iola ion dec eases as execu ion p o-
ceeds. Thei wo k uses smalle chunks o he i s i e a ions, whe e andomized inc e-
men al algo i hms p esen mo e dependence iola ions, hen g adually inc eases he
chunk size o educe scheduling o e heads, and inally educes he size o he chunks
again o achie e a be e load balancing.
The use o chunk sizes ha ollows a p ede ined dis ibu ion, howe e , may no be
he bes solu ion. Specula i e pa alleliza ion poses a mo e complex scheduling chal-
lenge han adi ional pa alleliza ion, because, o i egula applica ions, bo h he
numbe and he pa icula dis ibu ion o dependence iola ions a e unknown be o e
he loop is execu ed. The e o e, he idea o changing he chunk size a un ime depend-
ing on he numbe o squashes p oduced makes sense [Llanos e al. 2008]. Recen ly,
[Es ebanez e al. 2015] p oposed a me hod, called Moody Scheduling, ha makes use
o bo h he numbe o e-execu ions o he las chunks o i e a ions and hei endency
(inc easing, dec easing, s able) o igu e ou an app op ia e chunk size o he ollowing
chunk o be scheduled.
2.4.5. Squashing al e na i es. I a RAW dependence iola ion is p oduced, all da a calcu-
la ed by he o ending h ead ( he one ha ha e consumed he inco ec alue) should
be disca ded. The mechanism chosen o do so is a design decision ha se e ely a ec s
pe o mance. Some app oaches jus disca d he h eads ha ha e consumed his pa -
icula , w ong alue, and o he s disca d he o ending h ead and all i s successo s.
This leads o he ollowing solu ion space, as desc ibed by [Ga cia-Yaguez e al. 2014]:
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
A Su ey on Th ead-Le el Specula ion Techniques ZZ:7
—S ops pa allel execu ion: Fi s solu ions, such as [Rauchwe ge and Padua 1995],
simply disca d he en i e specula ion execu ion when a dependence iola ion was
p oduced, and hen es a he loop sequen ially om he beginning. Due o hei
high cos in e ms o execu ion ime, hese solu ions only bene i loops ha we e
indeed pa allel.
—Inclusi e squashing: This app oach s ops and es a s he i s h ead ha ha e con-
sumed he w ong alue, oge he wi h all i s successo s, ega dless o whe he hey
ha e consumed any alue om he o ending h ead. Due o i s simplici y o imple-
men a ion, his is he mos used solu ion (see [Cin a and To ellas 2002; Cin a and
Llanos 2003; P abhu and Oluko un 2003; Ceze e al. 2006]), al hough i may dis-
ca d po en ially use ul wo k ca ied ou by a successo ha has no consumed any
pollu ed da a.
—Exclusi e squashing: This app oach squashes (a) he o ending h ead, (b) all suc-
cesso h eads ha ha e consumed any alue gene a ed by him, and (c) all h eads
ha ha e consumed any alue p oduced by he a o emen ioned squashed h eads. In
o he wo ds, only successo h eads ha ha e no consumed any alue ha may be
de i ed om he o ending h ead a e allowed o su i e. No e ha his solu ion may
disca d h eads ha ha e consumed alues om he o ending h ead ha ha e no
ela ionship wi h he alue ha igge ed he dependence iola ion. [Li e al. 2005]
ied o implemen his ideas in ha dwa e. [Colohan e al. 2006] also used his kind o
squashing mechanism in he con ex o da abases (whe e es a ing a h ead leads o
big pe o mance losses), and used sub- h eads o check o squashed h eads. [Tian
e al. 2010b] also p oposed a solu ion ha does no disca d all he p oduced alues,
only a small pa o hem. Also, [Ga c´
ıa-Y´
ag¨
uez e al. 2011; Ga cia-Yaguez e al. 2014]
de eloped a so wa e-only e sion o his idea, wi h he help o a lis ha s o es which
h eads ha e consumed a alue o a pa icula p edecesso .
—Pe ec squashing: Disca ds o ending h eads and hose successo s ha ha e con-
sumed he inco ec alue o any alue gene a ed using i . Th eads ha ha e con-
sumed co ec alues om he o ending h ead a e no squashed. This is he ap-
p oach ha leads o ewe squashes. Howe e , o keep ack o he de ini ion and use
o each pa icula da um, an in-dep h analysis should be pe o med, This ope a ion
seems o be oo cos ly. Fo example, [Akka y and D iscoll 1998] p oposed a speci ic
able o s o e dependences, while [Ro enbe g e al. 1997] used a able ha sa ed
all in e media e alues. Ne e heless, [Tian e al. 2011] add essed his p oblem and
concluded ha his squash mechanism is no p o i able.
The abo e discussion assumes ha he da a dependences a e handled a he da a-
elemen g anula i y le el. No e ha , i he TLS sys em uses a g anula i y coa se han
he da a-elemen o specula i e da a, o example a he cache le el, alse con lic s
may appea , leading o unnecessa y squashes o specula i e h eads.
The ollowing sec ion desc ibes he ideas ha led o mode n TLS echniques.
3. PRECURSORS
One o he i s app oaches cen e ed on he pa alleliza ion o loops ha may p esen
dependence iola ions was he one p oposed by [Knigh 1986]. Wi h he unc ional
languages in mind, speci ically he Mul i-Lisp app oach, [Hals ead 1985] in oduced a
ha dwa e app oach ha allowed specula ion h ough he use o wo di e en caches,
one dedica ed o s o ing hose alues loaded om memo y, and he o he used o hold
hose alues p oduced by he p ocesso whose accu acy was no con i med ye , hus
using lazy e sion managemen (see Sec . 2.4.2). [Midki and Padua 1987] desc ibed a
solu ion o synch onize he concu en execu ion o singly-nes ed loops, while [Zhu and
Yew 1987] desc ibed an algo i hm o handle all ypes o loops desc ibed in Sec . 2.1.
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
ZZ:8 A. Es ebanez, D. R. Llanos, and A. Gonzalez-Esc ibano
[Aiken and Nicolau 1988] desc ibed ano he scheduling algo i hm (see Sec . 2.4.4),
which analyzed loops and ob ained he op imal, dependence- ee dis ibu ion, making
use o compile- ime analysis echniques (See Sec .2.4.4). In hose yea s, [Bax e e al.
1989] pe o med esea ch o ex ac some pa allelism o Doconside loops, a kind o
egula Doac oss loops (see Sec . 2.1). whe e i e a ions could be ea anged, in o de
o p ese e dependence seman ics, and pa allelize as many i e a ions as possible. They
de eloped a compile plugin ha di ided i e a ions in o subse s o i e a ions ha de-
pend on each o he , so as o execu e se e al independen subse s a he same ime. Al-
hough his pape was ocused on p og ams whose dependences a e known a compile
ime, i also men ioned codes no schedulable a s a - ime [Mi chandaney and Sal z
1988; Sal z and Mi chandaney 1988], which a e codes whose dependences could only
be ex ac ed du ing hei execu ion, and he e o e a compile- ime scheduling mech-
anism is no applicable. [K o hapalli and Sadayappan 1988] explo ed a solu ion o
emo e an i and ou pu dependences (see Sec . 2.1). Fo ha pu pose, hey pe o med
a e e ence analysis, s o ing mul iple copies o suspicious a iables used in he loop.
La e , [K o hapalli and Sadayappan 1990] p oposed a dynamic schedule based on syn-
ch onism (see Sec . 2.4.4), ha allowed doac oss loops o be add essed wi h complex
in e -i e a ion dependences. A e wa ds, [Wol and Lam 1991] used ma ices o ans-
o m and pa allelize loops in a gene al way, wi h he help o compile- ime scheduling
mechanisms capable o dealing wi h nes ed loops.
The idea o he use o a dynamic inspec o -execu o model appea ed a ha ime.
Wi h his app oach, an inspec o loop checks o dependences in a p elimina y phase,
and i no dependences a ise, a second phase execu es he loop in pa allel. [Sal z e al.
1991] in oduced his me hod in o de o pa allelize loops, showing ha his echnique
allowed a signi ican pe o mance imp o emen in loops wi h a big numbe o ope a-
ions, whe e inspec o phase ime was no signi ican compa ed o he execu o phase.
Howe e , none o hese app oaches pa allelize loops wi h ou pu dependences. [Chen
e al. 1994] de eloped a so wa e solu ion ha educed delays be ween p ocesso com-
munica ions and allowed he pa alleliza ion o loops wi h ou pu dependences. They
eused some esul s du ing he execu ion, allowing he o e lap o dependence i e a-
ions and he sha ing o some in o ma ion be ween inspec o and execu o phases.
4. HARDWARE-BASED APPROACHES
Se e al ha dwa e implemen a ions ha e been de eloped o suppo TLS, mainly
h ough he addi ion o auxilia y egis e s o manage specula ion. E en hough mos
ha dwa e app oaches ha e some pa s implemen ed in so wa e, in his sec ion, we
will e iew bo h pu e ha dwa e-based and mixed implemen a ions. The e a e mainly
wo ways o implemen TLS on ha dwa e (HTLS): De eloping a chip om sc a ch, o
cus omizing an exis ing chip. The modi ica ion o an exis ing chip led o he de elop-
men o Simul aneous Mul i h eading (SMT) p ocesso s3.
This sec ion is s uc u ed in h ee pa s. The i s desc ibes he app oaches ha did
no ely upon any p e iously de eloped scheme; he second de ails hose based on he
SMT a chi ec u e; and he hi d depic s hose ha p oposed CMP enhancemen s.
4.1. Pionee s
4.1.1. Mul iscala pa adigm. [Sohi e al. 1995] de eloped he Mul iscala p ocesso , one
o he i s and mos impo an app oaches ha execu ed sequen ial code (called asks)
3[Packi isamy e al. 2008; Tang e al. 2005] compa ed SMT wi h CMP (Chip Mul ip ocesso s) in he con ex
o TLS, gi ing a pe spec i e o pe o mance, powe and he mal; [Unge e e al. 2003] desc ibed chips ha
suppo mul i h eading. Howe e , a ull desc ip ion o hese p ocesso s is beyond he scope o his su ey,
and will no be p o ided.
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
A Su ey on Th ead-Le el Specula ion Techniques ZZ:9
in pa allel h ough specula ion. The unde lying idea was o pe o m some asks in
pa allel wi h he use o a chip ha included se e al p ocesso s, ensu ing sequen ial
seman ics. Pa alleliza ion was o ganized by using g aphs o asks. In his way, each
p ocesso ecei ed a ask and execu ed i . Consis ency was ensu ed wi h he help o
addi ional con ol logic, ha synch onized he p oduc ion o egis e alues in p ede-
cesso asks wi h he consump ion in successo asks. A ha dwa e moni o also en-
su es co ec ness in specula i e memo y accesses. The execu ion o pa allel asks in
each p ocesso ollowed a ixed o de , needed o ensu e sequen ial seman ics. To han-
dle his, a ing o p ocesso s was p oposed. I a p ocesso used a w ong alue om a
p edecesso , i s ask was squashed and es a ed (see Sec . 2.4.5). When each p oces-
so inished i s execu ion, alues we e commi ed in he o de imposed by he ing. As
will be seen in Sec . 5.1.2, his idea was la e used by se e al so wa e-based TLS so-
lu ions o implemen sliding-window mechanisms. The au ho s also sugges ed he use
o a alue p edic o (see Sec . 2.3.3) o educe squash o e heads, and o imp o e load
balance among p ocesso s in o de o a oid was ing compu a ional cycles, h ough he
choice o an app op ia e g anula i y. [Sohi e al. 1995] a i med ha co ec ness o he
ope a ions could be ensu ed by di e en ha dwa e implemen a ions. A ull desc ip-
ion o one ha suppo s he Mul iscala a chi ec u e can be ound in [B each e al.
1994; B each 1998; F anklin 1993; Vijaykuma 1998]. [Vijaykuma 1998; Vijaykuma
and Sohi 1998] also desc ibed e icien ways o choosing a good ask di ision by using
compile- ime scheduling echniques (see Sec . 2.4.4).
Imp o emen s in he s o age o specula i e alues. Se e al solu ions ied o educe
o e heads wi h he use o lazy e sion managemen (see Sec . 2.4.2) [F anklin and
Sohi 1996; Gopal e al. 1998] desc ibe se e al me hods o suppo di e en da a e -
sions p oduced du ing specula i e execu ion, h ough he use o ha dwa e wi h he
Mul iscala a chi ec u e. [F anklin and Sohi 1996] p oposed ARB, an Add ess Resolu-
ion Bu e used by all p ocesso s. This solu ion in oduced some o e heads due o he
a ic caused by he simul aneous accesses o he ARB. [Gopal e al. 1998] p oposed a
Specula i e Ve sioning Cache (SVC), in ended o o e come he limi a ions o ARB by
assigning a di e en cache o each p ocesso . [Jacobson e al. 1997a] s udied di e en
b anch p edic ion echniques o con ol specula ion (see Sec . 2.3.1): An au oma a-
based p edic o , a p edic ion based on he his o y, and an add ess p edic o o jumps
and indi ec calls.
4.1.2. The T ace p ocesso . [Ro enbe g e al. 1997] de eloped an a chi ec u e based on
he pa allel execu ion o aces. Unlike he asks used in he Mul iscala pa adigm,
ha we e ob ained by he compile di iding he sequen ial p og am, a ace is a dy-
namic sequence o ins uc ions ha a e buil as he p og am execu es, and s o ed in
a so-called ace cache [Ro enbe g e al. 1996]. This p oposal consis ed o a p ocesso
composed o di e en p ocessing elemen s, each ha ing he o ganiza ion o a small-
scale supe scala p ocesso , wi h enough space o hold an en i e ace and enough
unc ional uni s and egis e iles. Ins uc ions we e execu ed in pa allel, while in e -
ace dependences we e specula ed wi h he use o alue p edic o s.
Imp o emen s o T ace. [Pa el e al. 1998] de ised a way o educe he size o aces
and a modi ica ion o b anches wi h he aim o making hem mo e p edic able. [Black
e al. 1999] modi ied he o iginal T ace app oach, managing aces as se ies o poin e s
o basic blocks s o ed in cache. [Ro enbe g and Smi h 1999] add essed he p oblem
o con ol independence o be e exploi he pa allelism o his a chi ec u e, using
con ol specula ion (see Sec . 2.3.1) o s uc u e codes in o con ol-independen code
blocks. [Jacobson and Smi h 2000] imp o ed he ins uc ion dispa ching o ace caches
h ough he cons uc ion o se s o aces be o e hey we e needed. Se e al yea s la e ,
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
ZZ:16 A. Es ebanez, D. R. Llanos, and A. Gonzalez-Esc ibano
in o de o ake ad an age o he wo k ca ied ou be o e a dependence iola ion ap-
pea s, and hus ied o minimize he numbe o squashed h eads o hose ha had
ac ually consumed a pollu ed alue and i s sucesso s (a echnique known as inclusi e
squashing (see Sec . 2.4.5).
Again, we will ollow a his o ical pe spec i e o desc ibe he esea ch in his ield.
We will i s cen e ou a en ion on hose solu ions whe e p og amme s should explic-
i ly in oke un ime lib a y unc ions and/o compile suppo o manage specula i e
execu ion. Then, we will mo e o solu ions ha a e based on highe -le el p og am-
ming abs ac ions. We will inish his discussion wi h some p oposals ela ed o TLS
beha io , and a b ie e iew o some wo ks ha mixed TLS wi h o he echniques.
5.1. Solu ions elying on compile- ime and un ime suppo
Fi s app oaches equi ed p og amme s o use di e en me hods o explici ly in oke
TLS mechanisms. The mos ep esen a i e ones a e desc ibed below.
5.1.1. LRPD es . We can place he o igins o So wa e TLS (STLS) in he wo k ca ied
ou by [Rauchwe ge and Padua 1995; 1999], wi h hei esea ch in he pa allelism o
doall loops. They p oposed he use o a es called LRPD o suppo he specula i e pa -
alleliza ion o loops wi h some back acking capabili ies. This p oposal e-execu ed he
loop se ially i he un ime es ailed, a squashing solu ion ha is simple o implemen
bu wi h a huge cos in case o misspecula ion (see Sec . 2.4.5). The p oposal wo ked
as ollows: The a ge loop was i s ly ans o med h ough p i a iza ion ( ha is, mak-
ing p i a e copies o sha ed a iables) and educ ion pa alleliza ion (de e mining a
compile- ime ha ce ain ope a ions a e indeed educ ions, and eplacing hem wi h a
pa allel algo i hm), and hen i was specula i ely execu ed as a doall loop. Du ing his
pa allel execu ion, he es s o ed he i e a ion numbe whe e sha ed a iables we e
de ined and/o used. A e he pa allel loop execu ion, a ully-pa allel da a dependence
es was applied o e his in o ma ion o ensu e ha he loop had no c oss-i e a ion
dependence. I he es ailed, he loop was sequen ially e-execu ed. O he wise, he
pa allel execu ion o he loop was conside ed success ul. This app oach had he dis-
ad an age o de ec ing c oss-i e a ion dependences only a e he end o he pa allel
execu ion, hus implying a hea y pe o mance penal y. [Gup a and Nim 1998] p e-
sen ed a mo e e icien me hod o specula i e a ay p i a iza ion ha did no equi e
he compu a ion o be olled back when a pa icula a iable was ound o p oduce
a dependence iola ion. To do so, hey p esen ed a echnique ha allowed he ea ly
de ec ion o loop-ca ied dependences, and ano he ha de ec ed pa alleliza ion haz-
a ds immedia ely a e hey we e p oduced. In addi ion, hey p oposed a se o new
un ime es s o specula i e pa alleliza ion o loops ha de ied pa alleliza ion me h-
ods based solely on s a ic analysis. [Dang e al. 2002] de eloped a echnique o ex ac
he maximum a ailable pa allelism o loops ha we e known o p esen some depen-
dences. This solu ion p esen ed an e olu ion o he LRPD es , called Recu si e LRPD
(R-LRPD). The basic idea was o ans o m a pa ially-pa allel loop in o a sequence o
ully-pa allel loops. A each s age, his p oposal specula i ely execu ed all emaining
i e a ions in pa allel and he R-LRPD es was applied o de ec he po en ial depen-
dences.
5.1.2. So wa e e sions o ha dwa e solu ions. [Rundbe g and S ens ¨
om 2000] applied
many o he ideas o ha dwa e-based specula i e a chi ec u es in so wa e. Fi s , name
dependences we e sol ed by dynamically enaming da a a un ime. Second, he o e -
head o es o ing he o iginal si ua ion a e a misspecula ion was g ea ly educed
by educing he amoun o da a o commi , and by suppo ing pa allel implemen a-
ions o he commi phase. Thi d, some an i da a dependence iola ions we e a oided
by suppo ing lazy e sion managemen wi hou he need o en o ce synch oniza ions
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.

A Su ey on Th ead-Le el Specula ion Techniques ZZ:17
be ween a pai o con lic ing h eads. Fou h, ue da a dependence iola ions we e de-
ec ed when hey happened, which educes he cos o misspecula ions. To do so, each
ins uc ion on specula i e da a was augmen ed wi h a checking code ha de ec s da a
dependence iola ions dynamically, ha is, using eage con lic de ec ion (Sec . 2.4.3).
Finally, i commi ed da a ollowing sequen ial seman ics.
[Cin a and Llanos 2003; 2005] de eloped a di e en scheme based on an agg essi e
sliding window. I checks o da a dependence iola ions on e e y specula i e s o e,
while a oiding synch oniza ion whene e possible. The sliding window used consis ed
o an a ay o slo s which s o e he s a us o each unning h ead, and poin e s o hei
own e sion o he specula i e da a, Commi s we e ca ied ou in o de om he non-
specula i e h ead. Each ime a commi ope a ion was inished, he sliding window
ad anced one posi ion, allowing a new, mos -specula i e h ead o s a . This solu ion
used lazy e sion managemen , eage con lic de ec ion and inclusi e squashing. Mo e
ecen ly, [Es ebanez e al. 2014b] imp o ed his solu ion wi h a di e en implemen-
a ion ha suppo ed he specula i e access o dynamically-alloca ed da a s uc u es
and suppo o he use o poin e a i hme ic. This solu ion used a sophis ica ed me a-
da a managemen (see Sec . 2.4.1) wi h he help o hash ables o educe he ime
needed o ind he mos up- o-da e e sion o a da um (see Sec . 2.3.2), a p oblem also
desc ibed in [Tian e al. 2010b].
5.1.3. Based on mas e /sla e pa adigm. [Zilles and Sohi 2002] in oduced he Mas-
e /Sla e specula i e pa allelism, a new kind o specula ion whose basics we e he use
o a mas e h ead and some sla es ha pe o med he ask assigned by hei mas e .
The main idea o his echnique was o di ide a compile ime he p og am in o asks
ha would be ca ied ou by he sla es, while he mas e h ead p edic ed he alues
ha would be p oduced by each ask and con inued wi h he execu ion o he code
wi hou wai ing o hei esul s. This app oxima ion needed o check all he alues
p oduced by sla es a e he execu ion o a ask wi h espec o he alues p edic ed
by he mas e . I bo h we e equal, he mas e ’s p edic ion had been success ul, on he
o he hand, a misspecula ion had been de ec ed. In his case, he wo k inco ec ly ca -
ied ou by he mas e and all sla es since he las checkpoin needed o be disca ded
and e-execu ed.
5.1.4. Au oma ic h ead ex ac ion. [O oni e al. 2005] p oposed an au oma ic app oach
o h ead ex ac ion. The sys em, called DSWP, exploi ed he ine-g ained pipeline
pa allelism o many applica ions o ex ac long- unning, concu en ly execu ing
h eads. Thei esul s showed signi ican imp o emen s when execu ing hese appli-
ca ions on a dual-co e CMP.
5.1.5. Complemen ing compile- ime echniques o au o-pa alleliza ion. [Tou na i is e al.
2009] p oposed he use o p o ile-d i en pa allelism de ec ion o augmen he numbe
o loops ha may conside ed sa e o pa allelize, elying on he use o inal app o al.
This wo k also uses machine-lea ning echniques o ake be e mapping decisions o
di e en a ge a chi ec u es.
5.1.6. O he solu ions: SpLIP, MiniTLS, and La e . [Oancea e al. 2009] de eloped SpLIP, a
specula i e ool cen e ed on dec easing o e heads o specula i e ope a ions o p e i-
ous app oaches, implemen ing non-locking ope a ions whe e was possible, making use
o hash unc ions o me ada a managemen (see Sec . 2.4.1) and elying on e sions
o da a ins ead o ollbacks (see Sec . 2.4.2). [Yiapanis e al. 2013] in oduced a new
s uc u e ha educed 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. The au ho s implemen ed his compac da a s uc u e in wo app oaches, namely
MiniTLS and La e . The main cha ac e is ic o MiniTLS was ha h eads upda ed
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
ZZ:18 A. Es ebanez, D. R. Llanos, and A. Gonzalez-Esc ibano
memo y loca ions in-place, and also ha all ope a ions ollowed as and op imis ic
design pa e ns. As in SpLIP, hash unc ions we e used o me ada a managemen .
Howe e , his app oach used ollback mechanisms ins ead o e sion managemen ,
because specula i e h eads modi ied alues di ec ly, possibly p oducing e o s ha
needed o be handled. This solu ion is simila o SpLIP, so bo h we e compa ed in his
wo k. La e ollowed a di e en design, implemen ing a lazy e sion managemen o
alues, oge he wi h pessimis ic design pa e ns in i s ope a ions. The s uc u e used
was a bi di e en , bu i was based on he same ope a ions and pa e ns. This ap-
p oach also in oduced a combina ion o inspec o -execu o echniques (desc ibed in
Sec . 3) and he LRPD es (desc ibed in Sec . 5.1.1), implemen ing he new solu ion
upon hem.
5.1.7. TLS compile and un ime o dis ibu ed sys ems. [Kim e al. 2012] p esen an au-
oma ic specula i e pa alleliza ion sys em o clus e s, composed o a pa allelizing
compile and a specula i e un ime ha minimizes he o e heads due o alida ions,
h ough he use o lazy e sion managemen and con lic de ec ion.. O he STLS un-
ime solu ions o dis ibu ed en i omen s a e co e ed in Sec . 5.4.
5.1.8. TLS o web applica ions. [Ma insen e al. 2013] used a specula i e mechanism in
he con ex o web b owsing. To do so, hey implemen ed hei so wa e by means o he
Squi el ish Ja aSc ip en i onmen , ha enabled he pa allel execu ion o Ja asc ip
unc ions. They modi ied Squi el ish in e p e e o enable each ins ance o he in e -
p e e o be execu ed as a h ead, while execu ing as many ins ances as unc ions.
The used a iables we e main ained in a special ec o ha showed modi ied alues
o de ec dependence iola ions. The use o TLS in his con ex allowed hese au ho s
o achie e no iceable speedups.
5.1.9. Apollo. [Jimbo ean e al. 2012a; Jimbo ean 2012; Jimbo ean e al. 2013] in-
oduced a TLS amewo k specially designed o specula i ely execu e nes ed loops,
by using ea u es o he polyhed al model [Ancou and I igoin 1991] o dynamically
ans o m code in o a mo e op imized e sion ha led o highe speedups. Fi s , a com-
pile [Jimbo ean e al. 2012b] gene a ed skele ons6 ha we e he basis o execu ions,
due o hei abili y o p oduce di e en code e sions ha could be selec ed a un-
ime. Then, a dynamic pa was esponsible o (a) ep esen ing memo y accesses as
p edic ing linea unc ions o he loop indices, wi h he help o in e pola ing unc ions,
(b) pe o ming dynamic dependence analysis and ans o ma ion selec ion, (c) ins an-
ia ing he pa allel skele on code, and (d) guiding he execu ion. The execu ion was
based on p o iling he code se e al imes du ing he execu ion in o de o choose he
polyhed al ans o ma ions ha could be e speed up he execu ion. The de ec ion o
dependence iola ions (see Sec . 2.3.2) was done a h ee le els: Basic scala s, memo y
accesses, and loop bounds. This amewo k led he au ho s o pa allelize some bench-
ma ks ha had no been pa allelized be o e due o dependence managemen hu dles.
5.1.10. HVD-TLS. [Fan e al. 2012] de eloped a so wa e-based specula i e amewo k
ha imp o ed classical TLS mechanisms by he de elopmen o new echniques o im-
p o e alue p edic ion (see Sec . 2.3.3), alue checking, dynamic ask pa i ion, and
scheduling (see Sec . 2.4.4). P edic ions pe o med we e done using se e al p edic-
o s based on he o iginal alue o he a iables in con lic . Such p edic ions used a
p edic o able ha also main ained he numbe o co ec p edic ions. Values we e
checked by he main h ead o p e en commi ing unmodi ied alues, a si ua ion e-
6Skele ons [Da ling on e al. 1993] a e a se o high-o de pa allel o ms in ended o be used as basic build-
ing blocks o pa allel implemen a ions. They include p og am ans o ma ions o ease po abili y be ween
di e en sys ems.
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
A Su ey on Th ead-Le el Specula ion Techniques ZZ:19
pea ed many imes acco ding o he au ho s. Also, his sys em allowed di e en le -
els o g anula i y o be assigned a un ime, ollowing a linea scheme o a heu is ic
scheme, whe e he sys em moni o ed he execu ion and changed he g anula i y ac-
co dingly.
5.2. Solu ions elying on addi ional p og amming abs ac ion laye s
Ou second se o so wa e-based solu ions eased he use o TLS by o e ing new,
highe -le el abs ac ion laye s.
5.2.1. Fas T ack. [Kelsey e al. 2009] de eloped a sys em called Fas T ack, whe e a
p og amme can ins all po en ially-unsa e op imized code while lea ing he ask o
e o checking and eco e y o he unde lying implemen a ion. Speci ically, hei p o-
g amming in e ace allowed use s o sugges as e implemen a ions based on pa ial
knowledge o a p og am and i s usage. Fas T ack di ided code in o wo b anches, he
as ack and he no mal ack, and p og amme s could change be ween bo h acks
when needed. Thei implemen a ion included bo h compile- ime and un ime suppo .
A compile inse s unc ion calls o ensu e ha he as ack p oduced he same e-
sul as he sequen ial execu ion. To p o ec un ime da a, he sys em elied on he
compile o inse checking code ha p o ec s s ack da a. Rega ding global and heap
da a, he sys em elied on he ope a ing sys em o p o ec hem, by u ning o w i e
pe missions o hem in bo h acks, and ins alling cus om page- aul handle s. These
handle s i s eco ded which page had been modi ied in an access map and hen e-
enabled w i e pe missions. The un ime suppo checked p og am co ec ness h ough
he compa ison o esul s a he end o he acks. I bo h esul s we e simila , esul s
we e supposed o be co ec . O he wise, he as ack esul s we e disca ded. In his
sys em, one p ocesso was ese ed o un he as ack, and he es o he execu ion
o no mal acks.
5.2.2. The Copy-o -Disca d model. [Tian e al. 2008; 2009] p oposed he Copy-o -Disca d
(Co D) execu ion model, in which he execu ion o pa allel h eads was sepa a ely
managed by a non-specula i e one. Specula i e h eads ead alues o he non-
specula i e h ead and pe o med hei compu a ion. A e ha , specula i e h eads
we e commi ed in o de . Then, esul s we e checked by a non-specula i e h ead so
as o p ese e he seman ics o he sequen ial o de , using a lazy con lic de ec ion
(see Sec . 2.4.3). The commi ope a ion was pe o med by he non-specula i e h ead
h ough he Co D mechanism, which checked whe he esul s we e co ec . In his
case, esul s we e copied o he non-specula i e da a. O he wise, hey we e disca ded
a no addi ional cos , hanks o he use o e sion copies.
Co D and dynamic memo y. The Co D app oach did no gi e suppo o hose appli-
ca ions whose specula i e a iables we e dynamically alloca ed, so [Tian e al. 2010b]
enhanced Co D o be used wi h p og ams ha had such dynamic da a s uc u es. The
main p oblem o his app oach was da a a e sing, because a dynamic s uc u e could
change hei size du ing he execu ion. Poin e s imposed ano he p oblem, since a
specula i e copy o a dynamic s uc u e migh ha e a poin e wi h an add ess o a
non-specula i e copy. In o de o sol e hese p oblems, hey p oposed using a mapping
able ha ansla ed add esses among specula i e and non-specula i e h eads. They
also included op imiza ions in he ea men o linked s uc u es. Finally, [Tian e al.
2010a] used a alue p edic o o imp o e he pa alleliza ion o p og ams wi h equen
and p edic able c oss-i e a ion dependences (see Sec . 2.3.2).
Reducing misspecula ions. [Tian e al. 2011] la e ied o u he educe misspec-
ula ions. They p oposed an app oach in ended o euse almos all he co ec calcu-
la ions pe o med by a h ead whose i e a ions had su e ed dependence iola ions,
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
ZZ:20 A. Es ebanez, D. R. Llanos, and A. Gonzalez-Esc ibano
ins ead o disca ding all his in o ma ion, as mos app oaches did. To do so, hey used
a pa ial specula i e space in addi ion o he p ima y specula i e space o each h ead.
This new space main ained he i s ead alues o a specula i e a iable. I a misspec-
ula ion was ound, only he successo spaces o he o ending space we e squashed (see
Sec . 2.4.5). This app oach led o be e pe o mance and o a educ ion in he numbe
o dependence iola ions, due o lowe eco e y imes.
5.2.3. TLS based on he use o compile- ime di ec i es. [Bhowmik and F anklin 2002] de-
sc ibed a compile amewo k o TLS ha allowed he pa alleliza ion o all ins uc-
ions o a code, ins ead o only hose ha compose a loop. This ea u e specially bene-
i ed non-nume ical applica ions wi h complex ins uc ions. Codes we e ini ially ana-
lyzed by he compile and p o iled o p oduce a con ol low g aph. I was hen used o
p oduce pa i ions ha could be execu ed by mul iple h eads. [Chen e al. 2003] also
de eloped a compile ha ocused on p o iding a quan i a i e analysis o codes wi h
complex dependences. Thei aim was o gi e p obabili ies abou he possible lows o
he code, and de ec i a squash was likely o be p oduced.
Mi osis. Mi osis is a compile amewo k de eloped by [Qui˜
nones e al. 2005] ca-
pable o deciding which agmen s o code could be specula i ely execu ed. To do so,
he Mi osis compile ma ked he beginning o a egion whose ou come could be spec-
ula i ely guessed wi h a so-called spawning poin (SP), and i s end wi h he con ol
quasi-independen poin (CQIP) ma k. When he sequen ial execu ion eached he SP,
a specula i e h ead was launched. This h ead p edic ed he possible alues o he
ou come o he pa allel egion and used hem o s a he specula i e execu ion o he
code om he CQIP. Meanwhile, he non-specula i e h ead con inued i s execu ion.
I no e o s we e p oduced, specula i e h eads we e commi ed, o he wise, hey we e
disca ded. The choice o hese spawning poin s was a key pa o he wo k. To do so,
ma ks we e chosen wi h he use o a syn he ic ace. I selec ed he mos sui able pa s
o codes o be specula i ely execu ed ega ding some equi emen s, such as he amoun
o wo kload o ou ines wi h espec o he o al, o possible misspecula ions.
Spice C. SpiceC was an app oach p oposed by [Feng e al. 2011]. SpiceC imple-
men ed a numbe o di ec i es ha , when added o sequen ial code, eased pa allel
p og amming. P og amme s did no need o be pa icula ly ca e ul abou communi-
ca ions o dependences, because his model suppo ed doall,doac oss, pipelining and
specula i e pa allelism. This solu ion also suppo ed dynamic s uc u es and poin e
add esses. SpiceC h eads had hei own p i a e space o da a. A sha ed global space
was used o s o e sha ed da a. Th eads’ i s accesses we e e e ed o sha ed space
and loaded o each local space, whe e ollowing accesses we e edi ec ed o. When
h eads ended hei execu ions, hey checked o misspecula ions, and commi ed hei
da a o he sha ed space i hey we e co ec . Di ec i es we e simila o OpenMP’s
[Dagum and Menon 1998], so sequen ial p og ams only needed a ew addi ional di ec-
i es: A di ec i e o sugges wha kind o pa allelism would be used, and ano he o
ma k whe e commi ope a ions had o ake place.
[Feng e al. 2012a] ex ended SpiceC wi h some addi ional di ec i es o suppo I/O
ope a ions wi hin pa allel loops. To he bes o ou knowledge, his was he i s ap-
p oach ha add essed he pa alleliza ion o his kind o codes h ough TLS. The main
idea behind his esea ch was o b eak he c oss-i e a ion dependences caused by I/O
ope a ions (see Sec . 2.3.2) modi ying he o iginal code. To pa allelize inpu ope a ions,
his app oach calcula ed ile poin e s be o e en e ing he loop o be used in each i e -
a ion. File poin e copies we e c ea ed on demand by he i e a ions ha used hem.
Rega ding ou pu ope a ions, hey equi ed he use o some addi ional bu e s, in o -
de o s o e in e media e ou pu s p oduced by each h ead. Each ou pu alue was
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
A Su ey on Th ead-Le el Specula ion Techniques ZZ:21
s o ed in he co esponding h ead bu e and lushed a he end o each i e a ion ol-
lowing sequen ial seman ics. [Feng e al. 2012b] also augmen ed SpiceC di ec i es o
pa allelize loops wi h dynamically-linked da a s uc u es. This wo k ied o manage
di e en da a pa i ions o loops using he same code, add essing he p oblem o codes
whe e mul iple h eads managed se e al da a pa i ions.
ATLaS. [Aldea e al. 2014; 2015] de eloped a GCC plugin so as o add loop-based
TLS suppo o OpenMP. Thei p oposal include he de elopmen o a new OpenMP
specula i e clause o be used in o loops [Aldea e al. 2012], which allowed p og am-
me s o decla e all a iables whose eads o w i es may lead o dependence iola ions.
The use o his clause gua an eed ha all de ini ions and uses o specula i e a iables
would ollow sequen ial seman ics. The ATLaS amewo k consis ed on a GCC plug-in
ha ga e suppo o he new specula i e clause, and a un ime lib a y ha managed
he specula i e execu ion. The ATLaS un ime lib a y is able o anspa en ly suppo
specula ion o e a iables o any size, and pe mi s he use o poin e a i hme ic. I s
implemen a ion o e ed e sion managemen , eage con lic de ec ion, ixed, dynamic,
and adap i e chunk scheduling, and bo h inclusi e and exclusi e squashing. The in-
e nals o he un ime lib a y ha managed dependence iola ions we e desc ibed in
[Es ebanez e al. 2014b]. The en i e ATLaS amewo k can be eely downloaded om
a las.in o .u a.es.
5.2.4. The Galois model. [Kulka ni e al. 2007; 2009] in oduced Galois, a sys em ha
suppo ed complex poin e -based se s o elemen s in op imis ic pa allelism. They we e
cen e ed on benchma ks ha should ge a subse o poin s om a big se , in o de
o ob ain a solu ion o he p oblem. To do so, hey in oduced wo cons uc s called
op imis ic i e a o s ha could be added o objec -o ien ed p og amming languages
like Ja a: The se i e a o , in ended o execu e a loop ha p ocesses in pa allel an
uno de ed se o elemen s, and he o de ed-se i e a o , ha a e ses in pa allel
pa ially-o de ed se s while ensu ing sequen ial seman ics. The consis ency o da a
was implemen ed using locks. Mo eo e , o allow eco e y om misspecula ions, all
ope a ions had hei co esponding in e se me hods. Wi h his pu pose, an undo log
was de ined o each i e a ion. In o de o manage all i e a ions, his solu ion de ined a
commi pool ha con ained da a such as he s a e o i e a ion execu ions, o he posi-
ion o he log. I con olled he en i e execu ion, deciding how i e a ions we e assigned
and commi ed, con lic s we e sol ed, e c.
E iciency imp o emen h ough da a pa i ioning. A e ha , [Kulka ni e al. 2008]
in oduced some mechanisms aimed o imp o e he e iciency o Galois, by be e ex-
ploi ing locali y o e e ence, educe mis-specula ion, and p oducing a lowe synch o-
niza ion o e head. The mechanisms p oposed include da a pa i ioning, o assign ele-
men s o da a s uc u es o co es; da a-cen ic assignmen policy o imp o e locali y;
eplacing ine-g ain synch oniza ion on da a s uc u e elemen s by coa se -g ain syn-
ch oniza ion on da a s uc u e pa i ions; and o e -decomposi ion o da a, o assign
se e al pa i ions o he same co e, hus a oiding ha a lock on a pa i ion s alls he
execu ion o ha co e.
Scheduling. [Kulka ni e al. 2008] add essed he p oblem o scheduling (see
Sec . 2.4.4), de eloping an addi ional amewo k o Galois. Al hough i e a ions could
be execu ed in any o de wi hin hei baseline scheduling policy, his wo k showed he
ine iciencies associa ed o his beha io , and p oposed an imp o emen based on clus-
e ing (selec a clus e o i e a ions), labelling (assign he selec ed clus e s o co es),
and o de ing (o de o he clus e s o be execu ed) o i e a ions. Scheduling s a egies
o i egula applica ions in TLS we e also add essed by [Jo and Kulka ni 2010] wi h
Galois. Thei s a egies wen om “s ealing” he wo k o o e loaded p ocesso s by idle
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.

ZZ:22 A. Es ebanez, D. R. Llanos, and A. Gonzalez-Esc ibano
p ocesso s in he s a ic assignmen , o using a cen alized place as a wa ehouse o he
ex ac ed pa i ions.
A p o ile : Pa aMe e . [Kulka ni e al. 2009b] de eloped a ool o ex ac pa allelism
p o iles om i egula applica ions. This me hod ook abs ac measu es o he in-
he en pa allelism o he di e en poin s o a code, showing ins uc ions ha could
be execu ed concu en ly. Al hough his ool has been used in he con ex o Galois,
he au ho s a i med ha i is amewo k-independen . [Kulka ni e al. 2009a] also
in oduced a sui e o benchma ks o es i egula applica ions wi h he use o TLS
lib a ies, including hose used in he men ioned pape s.
5.2.5. Op imizing i egula applica ions. [M´
endez-Lojo e al. 2010] desc ibed h ee manual
echniques o op imize i egula applica ions in o de o imp o e hei pa allel execu-
ion. The i s one was based on he idea o modi ying codes in such a way ha all
ead ope a ions we e done be o e any w i e ope a ion. The second one, called “one-
sho ”, was based on he de ec ion o dependences be o e he execu ion. I none we e
de ec ed, checks o hem could be disabled, and code could be pa allelized wi hou
locks. Finally, o hose algo i hms whose bo lenecks we e loca ed in he accesses o
da a se s (app op ia e o he benchma ks es ed by hem, desc ibed in [Kulka ni e al.
2009a]), hey de eloped he “i e a ion coalescing” op imiza ion. While in Galois he e
was a one- o-one co espondence be ween i e a ions and da a elemen s o be p ocessed
(which was called ac i i ies), his i e a ion allowed a single i e a ion o g ab mul i-
ple ac i e elemen s om he se o da a elemen s o be p ocessed (called he wo king
se ), hus educing he o e head associa ed o hei access. La e , [P oun zos e al.
2011] comple ed his wo k by au oma izing he manual echniques desc ibed. They
add essed again he o e head p oblems ha eme ged om op imis ic pa alleliza ion,
speci ically, hose ela ed o con lic checking and undo ac ions. The cen e o his e-
sea ch was o educe locks and ollbacks o he sha ed objec s, using some in e ed
p ope ies. In 2011, [Kulka ni e al. 2011] analyzed whe he he o de used o launch
me hods a ec ed execu ion imes.
5.2.6. SEED. An app oach o specula i e loop execu ion ha handled nes ed loops
was ecen ly p oposed by [Gao e al. 2013]. They de eloped and implemen ed SEED, a
ool ha p o ided a un ime schedule capable o adap i ely selec ing loops o pa al-
leliza ion in e ms o hei po en ial bene i s, by pe o ming a cos -bene i analysis ha
ook in o accoun he inpu da a. This ool was composed by wo phases, one ela ed o
compila ion ime, and he o he ela ed o un ime. In he compile phase, loops we e
selec ed, h eads we e exposed in o de o be la e c ea ed, and he esul ing code was
op imized using p ecompu a ion and so wa e alue p edic ion (see Sec . 2.3.3) o e-
duce misspecula ions. A un ime, he basic TLS ope a ions, such as h ead spawning,
dependence iola ions de ec ion, and squashes, we e ca ied ou , oge he wi h he use
o adap i e scheduling echniques (see Sec . 2.4.4) ha we e sensi i e o inpu da a.
5.3. TLS mixed wi h o he echniques
5.3.1. Helpe h eads, unahead and mul i pa h execu ion. [Xekalakis e al. 2009] p oposed
a model ha combined di e en echniques such as TLS, helpe h eads, and una-
head execu ion, in o de o dynamically choose a un ime he mos app op ia e com-
bina ion. The helpe h eads echnique is based on he un ime gene a ion o small
h eads (also called slices) o imp o e he e iciency o he main h ead, o exam-
ple, by esol ing highly-unp edic able b anches and cache misses. By con as , una-
head execu ion was based on execu ing ins uc ions in ad ance when a long la ency
ope a ion was expec ed. Runahead h eads ei he igno e o p edic he ou comes o
his long la ency ope a ion. Consequen ly, unahead h eads would be as e han he
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
A Su ey on Th ead-Le el Specula ion Techniques ZZ:23
o he s, and hey would se e o p edic cache misses o help TLS h eads. In o he
wo ds, hese p e e ched h eads we e essen ially helpe h eads ac ing in a unahead
mode o help he execu ion o main h eads. The main di e ence o his echnique
wi h espec o helpe h eads was ha he o me did no equi e addi ional h eads.
[Xekalakis and Cin a 2010] la e combined TLS wi h Mul iPa h execu ion, a ech-
nique consis ing in execu ing he wo b anches o ha d- o-p edic b anches. The main
idea behind his app oach was o enhance p ocesso s wi h mul iple-con ex execu ion
o enable a as way o disca d e oneous da a o w ong b anches. The execu ion had
no mal TLS and Mul iPa h modes, depending on he numbe o occu ences o ha d- o-
p edic b anches. The p e ious combina ions we e mo e de ailed, ex ended and mixed
in [Xekalakis e al. 2012], whe e he au ho s desc ibed a sys em ha applied TLS o
loops. O he echniques we e also p oposed, such as he use o p e e ched h eads when
delays we e de ec ed.
5.3.2. Con inuous specula ion. [Zhang e al. 2010] desc ibed con inuous specula ion, a
echnique whose main objec i e was o achie e ull-occupancy o p ocesso s. Fo ha
pu pose, hey used specula ion echniques o achie e he pa alleliza ion o la ge se-
quen ial codes. Thei solu ion used a sliding window and a g oup classi ica ion o
ensu e he co ec o de o he asks. To ge in o ma ion abou he possibly pa allel
egions o a sequen ial code, hey used BOP [Ding e al. 2007; Ding 2011], a ool ha
analyzed he p og am beha io o pa allelize i .
5.3.3. STLS and T ansac ional Memo y. The e we e se e al wo ks ha made a join use o
TLS and T ansac ional Memo y (TM) solu ions. [Meh a a e al. 2009] desc ibed STM-
Li e, a STM implemen a ion cus omized o acili a e p o ile-guided au oma ic loop pa -
alleliza ion, by suppo ing TLS using a simpli ied a ian o STM. STMLi e was spe-
cially designed o educe o e heads o accesses o logs o a iables used in ansac ions.
[Raman e al. 2010] p oposed SMTX, a so wa e sys em ha gene alized exis ing so -
wa e TLS memo y sys ems o suppo specula i e pipelining schemes, and was uned
o loop pa alleliza ion. I was specially designed o exploi ha dwa e MTX (mul i-
h ead ansac ions) capabili ies. Concep ually, an MTX p o ides a p i a e memo y
ha was ini ialized wi h he con en s o commi ed memo y a he ime o c ea ion o
he MTX. Se e al h eads could pa icipa e concu en ly in he MTX, by pe o ming
loads and s o es in his p i a e memo y. A he end o he MTX, i no con lic es we e
de ec ed, he con en s o he p i a e memo y we e commi ed. O he wise, he MTX
was olled back. [Ba e o e al. 2012] p oposed uni ying so wa e ansac ional mem-
o y and STLS in TLSTM. They de eloped a so wa e ool ha imp o ed he execu ion
o each ansac ion o pa allel p og ams h ough he use o TLS.
5.3.4. So wa e-based lock elision. [Roy e al. 2009] p oposed a so wa e e sion o he
specula i e lock elision p oposed by [Rajwa and Goodman 2001] (see Sec 4.4.2) ha
was ully implemen ed in so wa e. I a misspecula ion was p oduced, he sys em exe-
cu ed he o iginal lock. Synch oniza ion and p i a iza ion we e implemen ed h ough
special ins umen a ion o objec s and h ough signals be ween h eads implemen ed
inside he Linux ke nel.
5.4. STLS on dis ibu ed-memo y sys ems
The e ha e been some e o s on applying TLS echniques on clus e s o commodi y
se e s. [Kim e al. 2010] p esen a un ime moni o called Dis ibu ed So wa e Mul i-
h eaded T ansac ional Memo y (DSMTX) ha allows he applica ion o pipeline pa -
allelism, mul i- h eaded ansac ions and TLS on dis ibu ed-memo y en i onmen s.
[Kodu u e al. 2013] desc ibed dyDSM, a dis ibu ed-sha ed memo y abs ac ion o
p ocess la ge dynamic g aphs ha p o ides suppo o exploi ing specula i e pa al-
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
ZZ:24 A. Es ebanez, D. R. Llanos, and A. Gonzalez-Esc ibano
lelism. The balance be ween communica ion and compu a ion in g aph-based applica-
ions is s udied in [Cha an Kodu u e al. 2014], p oposing a new un ime, called ABC2,
ha dynamically modi ied he con igu a ion o he unde lying DSM. Finally, [Palmie i
e al. 2011] p oposed a ansac ional eplica ion p o ocol, named OSARE, buil on op
o an Op imis ic A omic B oadcas (OAB) se ice, ha in u n was designed o speed
up A omic B oadcas s in dis ibu ed-memo y sys ems. OSARE oppo unis ically p o-
cesses ansac ions in mul iple, specula i e se ializa ion o de s, o inc emen he like-
lihood ha he inal message o de ing es ablished by he OAB se ice ma ches one o
he al eady specula ed se ializa ion o de s.
5.5. STLS using GPUs
Nowadays, pa allelism applied o GPUs is one o he mos p o i able esea ch ields
due o hei la ge numbe o compu ing uni s. This cha ac e is ic makes hem desi -
able o ind ways o use TLS wi h hese a chi ec u es. [Liu e al. 2010] discussed how
TLS could be co ec ly used in he con ex o GPU compu a ion. Meanwhile, [Diamos
and Yalamanchili 2010] ex ended Ha mony, a un ime o he e ogeneous, many-co e
sys ems, o suppo specula ion in GPUs. [Samadi e al. 2012] in oduced Pa agon,
a solu ion ha combined CPU and GPU execu ions o achie e he bes pe o mance.
[Feng e al. 2012; 2014] p oposed a amewo k o un loops specula i ely in GPUs. The
main idea o hei solu ion was o di ide he asks ha should be ca ied ou by a spec-
ula i e un ime amewo k in o i e ca ego ies, and o assign some o hem o CPUs
and he o he s o GPUs. Scheduling, esul s commi ing and misspecula ion eco e -
ies we e assigned o CPUs, while compu a ion and misspecula ion checks we e ca ied
ou in GPUs. In a mo e ecen app oach, [Zhang e al. 2013] in oduced a new lib a y
based on sliding windows ha suppo TLS in GPUs. Classical solu ions ha we e ex-
pec ed o ha e a be e beha io wi h GPUs, such as hyb id dependence checking, and
he use o a pa allel commi scheme, we e adap ed by hese au ho s o hei so wa e.
5.6. O he p oposals
Finally, we will now desc ibe o he so wa e-based app oaches ha uses specula ion
in pa icula domains.
5.6.1. Fini e-S a e Machine in TLS. [Zhao e al. 2012; 2014] in oduced he use o p ob-
abilis ic analysis in o he design o specula ion schemes. In pa icula , hey ocused
on applica ions ha we e based on Fini e-S a e Machines. The au ho s a i med ha
his ype o applica ions had he mos p e alen dependences o all he p og ams. They
de eloped a p obabilis ic model o o mula e he ela ionship be ween specula i e ex-
ecu ions and he p ope ies o he a ge compu a ion and inpu s. Based on ha o -
mula ion, hey p oposed wo model-based specula ion schemes ha au oma ically cus-
omized hemsel es wi h he bes con igu a ions o a gi en Fini e-S a e Machine and
i s inpu s. [Zhao and Shen 2015] p esen ed a se o echniques o emo e he need
o o line aining o collec p obabilis ic p ope ies ha help o educe he p obabil-
i y o misspecula ions. Ins ead, hei echniques allowed p obabilis ic analysis o be
pe o med on- he- ly.
5.6.2. MUTLS. [Cao and Ve b ugge 2013] in oduced a mixed model o o k h eads
in bo h in-o de and ou -o -o de ways in a TLS lib a y. Thei wo k was based on he
use o he LLVM compile amewo k [La ne and Ad e 2004] which allowed mul-
iple sou ce languages and a ge a chi ec u es h ough he use o an in e media e
ep esen a ion. MUTLS allowed h eads o o k and join in di e en pa s o he code,
and also implemen ed ba ie s o a oid some ollbacks. Func ions anno a ed wi h o k
and join poin s a e ans o med a compile ime. Fo each one, a specula i e e sion
was gene a ed, ha included helpe unc ions o in e ac ion wi h he TLS un ime
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
A Su ey on Th ead-Le el Specula ion Techniques ZZ:25
lib a y, he use o synch oniza ion poin s, and he assignmen o local bu e s. Th eads
we e managed by ou modules: one dedica ed o main aining he s a us o specula i e
h eads, wo dedica ed o manage local and global a iables o specula i e h eads, and
he las one used o managing o he modules and in e ac wi h he LLVM specula o
pass.
5.6.3. TLS o decomp ess: SDM. [Jang e al. 2013] desc ibed a TLS scheme specially
designed o be applied o decomp ession algo i hms. Thei app oach was cen e ed on
he applica ion o p edic ion echniques based on pa ial decomp ession and pa e n
ma ching, o quickly iden i y block chunks ha can be independen ly decomp essed.
The ool decomp essed in pa allel all he blocks iden i ied.
6. OTHER STUDIES RELATED TO TLS
The e a e se e al wo ks ha used TLS o o he pu poses, such as imp o ing manual
pa alleliza ion, o pe o ming module-le el specula ion. O he s udies include how he
ene gy consumed by TLS p oposals could be educed. In his sec ion we will e iew
some o hem.
6.1. TLS as a help o manual pa alleliza ion
In o de o a oid making specula i e codes ha migh be slowe han he o iginal
sequen ial ones, some esea che s ha e p oposed echniques o p edic o e heads o
specula i e pa alleliza ion. Fo example, he wo k de eloped by [Dou and Cin a 2004;
2007] con ained a compile pass ha can be used o es ima e he o e heads and he
expec ed esul ing pe o mance gains, i any. [Ding e al. 2007] p oposed a so wa e-
based TLS sys em o help in he manual pa alleliza ion o applica ions. The sys em
equi ed he p og amme o ma k “possibly pa allel egions” (PPR) in he applica ion
o be pa allelized. The sys em elied on a so-called “ ou namen ” model, wi h di e -
en h eads coope a ing o execu e he egion specula i ely, while an addi ional h ead
an he same code sequen ially. I a single dependence a ose, specula ion ailed en-
i ely and he sequen ial execu ion esul s we e used ins ead. [Ke e al. 2011] imp o ed
ha wo k wi h a sys em ha elied on dependence hin s p o ided by he p og amme .
This allowed explici da a communica ion be ween h eads, hus educing un ime
dependence iola ions. [Ioannou and Cin a 2011] s udied he p oblem o aking ad-
an age o u u e many-co e a chi ec u es by complemen ing pa allel p og amming a
a coa se-g ain le el wi h ha dwa e TLS suppo o launch ine-g ain implici specu-
la i e h eads. O he au ho s ha e ocused on p o iding assis ance o hose p og am-
me s ha ex ac TLS om he applica ions. Fo example, [Aldea e al. 2011; Wu e al.
2008] de eloped ools ha made a s a ic and/o dynamic p o ile o he codes, e u ning
in o ma ion ha allowed a decision o be made abou which loop would be he bes can-
dida e o be specula i ely pa allelized. [P abhu e al. 2010] de eloped some di ec i es
and ope a ions o acili a e p og amme s o make hei own specula i e p og ams.
[Chen e al. 2004] designed a dependence p o ile o ex ac in o ma ion om a code.
[Bha acha yya 2012] also de eloped a simila ool ha s udied he p o i abili y o TLS
wi h he use o p o iling. Mo e ecen ly, [Bha acha yya and Ama al 2013] used poly-
hed al analysis o de ec dependences o loops a compile ime (see Sec . 2.3.2), s a ing
ha his analysis o e came he p e ious one.
6.2. Module-le el specula ion
Module-le el specula ion is he applica ion o specula ion in a module-based laye .
[Chen and Oluko un 1998] applied his echnique o objec -o ien ed Ja a p og ams.
[Wa g and S ens ¨
om 2001] compa ed he use o objec -o ien ed and impe a i e lan-
guages in he con ex o Module-le el pa allelism, concluding ha he e we e no sig-
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
ZZ:32 A. Es ebanez, D. R. Llanos, and A. Gonzalez-Esc ibano
Robe H. Hals ead, J . 1985. MULTILISP: a language o concu en symbolic compu a ion. ACM T ans.
P og am. Lang. Sys . 7, 4 (Oc . 1985), 501–538. DOI:h p://dx.doi.o g/10.1145/4472.4478
Pe Hamma lund and e al. 2014. Haswell: he ou h-gene a ion In el co e p ocesso . IEEE Mic o 2 (2014),
6–20.
Lance Hammond, Benedic A. Hubbe , Michael Siu, Manoha K. P abhu, Michael Chen, and
Kunle Oluko un. 2000. The S an o d Hyd a CMP. IEEE Mic o 20, 2 (Ma ch 2000), 71–84.
DOI:h p://dx.doi.o g/10.1109/40.848474
Lance Hammond, Ma k Willey, and Kunle Oluko un. 1998. Da a Specula ion Suppo o a Chip Mul-
ip ocesso . In P oceedings o he Eigh h In e na ional Con e ence on A chi ec u al Suppo o P o-
g amming Languages and Ope a ing Sys ems (ASPLOS VIII). ACM, New Yo k, NY, USA, 58–69.
DOI:h p://dx.doi.o g/10.1145/291069.291020
John L. Henning. 2006. SPEC CPU2006 Benchma k Desc ip ions. SIGARCH Compu . A chi . News 34, 4
(Sep . 2006), 1–17. DOI:h p://dx.doi.o g/10.1145/1186736.1186737
John L. Henning. 2007. SPEC CPU Sui e G ow h: An His o ical Pe spec i e. SIGARCH Compu . A chi .
News 35, 1 (Ma ch 2007), 65–68. DOI:h p://dx.doi.o g/10.1145/1241601.1241615
Mau ice He lihy and J. Elio B. Moss. 1993. T ansac ional Memo y: A chi ec u al Suppo o Lock- ee
Da a S uc u es. In P oceedings o he 20 h Annual In e na ional Symposium on Compu e A chi ec u e
(ISCA ’93). ACM, New Yo k, NY, USA, 289–300. DOI:h p://dx.doi.o g/10.1145/165123.165164
Ben He zbe g and Kunle Oluko un. 2009. DBT86: A Dynamic Bina y T ansla ion Resea ch F amewo k
o he CMP E a. In P oceedings o he 2nd Wo kshop on Pa allel Execu ion o Sequen ial P og ams on
Mul i-co e A chi ec u es (PESPMA ’09). 41–46.
Ben He zbe g and Kunle Oluko un. 2011. Run ime au oma ic specula i e pa alleliza ion. In P oceedings
o he 9 h Annual IEEE/ACM In e na ional Symposium on Code Gene a ion and Op imiza ion (CGO
’11). IEEE Compu e Socie y, Washing on, DC, USA, 64–73. h p://dl.acm.o g/ci a ion.c m?id=2190025.
2190054
Susan Flynn Hummel, Edi h Schonbe g, and Law ence E Flynn. 1992. Fac o ing: A me hod o scheduling
pa allel loops. Commun. ACM 35, 8 (1992), 90–101.
Nikolas Ioannou and Ma celo Cin a. 2011. Complemen ing use -le el coa se-g ain pa allelism wi h implici
specula i e pa allelism. In P oceedings o he 44 h Annual IEEE/ACM In e na ional Symposium on
Mic oa chi ec u e. ACM, 284–295.
N. Ioannou, J. Singe , S. Khan, P. Xekalakis, P. Yiapanis, A. Pocock, G. B own, M. Luj´
an, I. Wa son, and M.
Cin a. 2010. Towa d a mo e accu a e unde s anding o he limi s o he TLS execu ion pa adigm. In
Wo kload Cha ac e iza ion (IISWC), 2010 IEEE In e na ional Symposium on. IEEE Compu e Socie y,
Washing on, DC, USA, 1–12. DOI:h p://dx.doi.o g/10.1109/IISWC.2010.5649169
M.M. Islam, A. Busck, M. Engbom, S. Lee, Michel Dubois, and P. S ens om. 2007a. Limi s on Th ead-
Le el Specula i e Pa allelism in Embedded Applica ions. In Ele en h Wo kshop on In e ac ion be ween
Compile s and Compu e A chi ec u es (INTERACT-11). 10.
M.M. Islam, A. Busck, M. Engbom, S. Lee, Michel Dubois, and P. S ens om. 2007b. Loop-
le el Specula i e Pa allelism in Embedded Applica ions. In Pa allel P ocessing, 2007. ICPP
2007. In e na ional Con e ence on. IEEE Compu e Socie y, Washing on, DC, USA, 3–13.
DOI:h p://dx.doi.o g/10.1109/ICPP.2007.53
Quinn Jacobson, S e e Benne , Nikhil Sha ma, and James E. Smi h. 1997a. Con ol Flow Specula ion in
Mul iscala P ocesso s. In P oceedings o he 3 d IEEE Symposium on High-Pe o mance Compu e A -
chi ec u e (HPCA ’97). IEEE Compu e Socie y, Washing on, DC, USA, 218–. h p://dl.acm.o g/ci a ion.
c m?id=548716.822688
Quinn Jacobson, E ic Ro enbe g, and James E. Smi h. 1997b. Pa h-based Nex T ace P edic ion. In P oceed-
ings o he 30 h Annual ACM/IEEE In e na ional Symposium on Mic oa chi ec u e (MICRO 30). IEEE
Compu e Socie y, Washing on, DC, USA, 14–23. h p://dl.acm.o g/ci a ion.c m?id=266800.266802
Quinn Jacobson and James E. Smi h. 2000. T ace P econs uc ion. In P oceedings o he 27 h Annual
In e na ional Symposium on Compu e A chi ec u e (ISCA ’00). ACM, New Yo k, NY, USA, 37–46.
DOI:h p://dx.doi.o g/10.1145/339647.339653
Hakbeom Jang, Channoh Kim, and Jae W. Lee. 2013. P ac ical specula i e pa alleliza ion o a iable-
leng h decomp ession algo i hms. In P oceedings o he 14 h ACM SIGPLAN/SIGBED con e ence on
Languages, compile s and ools o embedded sys ems (LCTES ’13). ACM, New Yo k, NY, USA, 55–64.
DOI:h p://dx.doi.o g/10.1145/2465554.2465557
Alexand a Jimbo ean. 2012. Adap ing he poly ope model o dynamic and specula i e pa alleliza ion. Ph.D.
Disse a ion. Uni e si y o S asbou g, S asbou g,F ance. Ad iso (s) Clauss, Philippe.
Alexand a Jimbo ean, Philippe Clauss, Jean-F anois Dollinge , Vincen Loechne , and JuanManuel
Ma inez Caama˜
no. 2013. Dynamic and Specula i e Polyhed al Pa alleliza ion Using Compile -
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.

A Su ey on Th ead-Le el Specula ion Techniques ZZ:33
Gene a ed Skele ons. In e na ional Jou nal o Pa allel P og amming 42, 4 (2013), 529–545.
DOI:h p://dx.doi.o g/10.1007/s10766-013-0259-4
Alexand a Jimbo ean, Philippe Clauss, Benoˆ
ı P adelle, Luis Mas angelo, and Vincen Loechne . 2012a.
Adap ing he Polyhed al Model As a F amewo k o E icien Specula i e Pa alleliza ion. In P oceedings
o he 17 h ACM SIGPLAN Symposium on P inciples and P ac ice o Pa allel P og amming (PPoPP ’12).
ACM, New Yo k, NY, USA, 295–296. DOI:h p://dx.doi.o g/10.1145/2145816.2145861
Alexand a Jimbo ean, Luis Mas angelo, Vincen Loechne , and Philippe Clauss. 2012b. VMAD: An Ad-
anced Dynamic P og am Analysis and Ins umen a ion F amewo k. In P oceedings o he 21s In e -
na ional Con e ence on Compile Cons uc ion (CC’12). Sp inge -Ve lag, Be lin, Heidelbe g, 220–239.
DOI:h p://dx.doi.o g/10.1007/978-3-642-28652-0 12
Youngjoon Jo and Milind Kulka ni. 2010. B ie Announcemen : Locali y-awa e Load Balancing o
Specula i ely-pa allelized I egula Applica ions. In P oceedings o he 22Nd ACM Symposium on
Pa allelism in Algo i hms and A chi ec u es (SPAA ’10). ACM, New Yo k, NY, USA, 183–185.
DOI:h p://dx.doi.o g/10.1145/1810479.1810516
Chuanle Ke, Lei Liu, Chao Zhang, Tongxin Bai, B ian Jacobs, and Chen Ding. 2011. Sa e Pa allel P o-
g amming using Dynamic Dependence Hin s. In OOPSLA’11 P oceedings. ACM, New Yo k, NY, USA,
243–258.
A un Keja iwal, Milind Gi ka , Xinmin Tian, Hideki Sai o, Alexand u Nicolau, Alexande V. Vei-
denbaum, U pal Bane jee, and Cons an ine D. Polych onopoulos. 2010a. Exploi a ion o Nes ed
Th ead-le el Specula i e Pa allelism on Mul i-co e Sys ems. In P oceedings o he 7 h ACM In-
e na ional Con e ence on Compu ing F on ie s (CF ’10). ACM, New Yo k, NY, USA, 99–100.
DOI:h p://dx.doi.o g/10.1145/1787275.1787302
A un Keja iwal, Milind Gi ka , Xinmin Tian, Hideki Sai o, Alexand u Nicolau, Alexande V. Veiden-
baum, U pal Bane jee, and Cons an ine D. Ppoluch onopoulos. 2010b. On he E icacy o Call G aph-
le el Th ead-le el Specula ion. In P oceedings o he Fi s Join WOSP/SIPEW In e na ional Con-
e ence on Pe o mance Enginee ing (WOSP/SIPEW ’10). ACM, New Yo k, NY, USA, 247–248.
DOI:h p://dx.doi.o g/10.1145/1712605.1712645
A un Keja iwal, Xinmin Tian, Milind Gi ka , Wei Li, Se gey Kozhukho , U pal Bane jee, Alexande Nico-
lau, Alexande V. Veidenbaum, and Cons an ine D. Polych onopoulos. 2007. Tigh analysis o he pe o -
mance po en ial o h ead specula ion using spec CPU 2006. In P oceedings o he 12 h ACM SIGPLAN
symposium on P inciples and p ac ice o pa allel p og amming (PPoPP ’07). ACM, New Yo k, NY, USA,
215–225. DOI:h p://dx.doi.o g/10.1145/1229428.1229475
A un Keja iwal, Xinmin Tian, Wei Li, Milind Gi ka , Se gey Kozhukho , Hideki Sai o, U pal Bane jee,
Alexand u Nicolau, Alexande V. Veidenbaum, and Cons an ine D. Polych onopoulos. 2006. On he pe -
o mance po en ial o di e en ypes o specula i e h ead-le el pa allelism: The DL e sion o his
pape includes co ec ions ha we e no made a ailable in he p in ed p oceedings. In P oceedings o
he 20 h annual in e na ional con e ence on Supe compu ing (ICS ’06). ACM, New Yo k, NY, USA, 24–.
DOI:h p://dx.doi.o g/10.1145/1183401.1183407
Ki k Kelsey, Tongxin Bai, Chen Ding, and Chengliang Zhang. 2009. Fas T ack: A So wa e Sys em o
Specula i e P og am Op imiza ion. In P oceedings o he 7 h Annual IEEE/ACM In e na ional Sympo-
sium on Code Gene a ion and Op imiza ion (CGO ’09). IEEE Compu e Socie y, Washing on, DC, USA,
157–168. DOI:h p://dx.doi.o g/10.1109/CGO.2009.18
Hanjun Kim, Nick P Johnson, Jae W Lee, Sco A Mahlke, and Da id I Augus . 2012. Au oma ic specula i e
DOALL o clus e s. In P oceedings o he Ten h In e na ional Symposium on Code Gene a ion and
Op imiza ion. ACM, 94–103.
Hanjun Kim, A un Raman, Feng Liu, Jae W Lee, and Da id I Augus . 2010. Scalable specula i e pa al-
leliza ion on commodi y clus e s. In P oceedings o he 2010 43 d Annual IEEE/ACM In e na ional
Symposium on Mic oa chi ec u e. IEEE Compu e Socie y, 3–14.
Tom Knigh . 1986. An a chi ec u e o mos ly unc ional languages. In P oceedings o he 1986 ACM
con e ence on LISP and unc ional p og amming (LFP ’86). ACM, New Yo k, NY, USA, 105–112.
DOI:h p://dx.doi.o g/10.1145/319838.319854
Sai Cha an Kodu u, Min Feng, and Raji Gup a. 2013. P og amming la ge dynamic da a s uc u es on a
DSM clus e o mul ico es. In 7 h In e na ional Con e ence on PGAS P og amming Models. 126.
Poonacha Konge i a, Ka hi gama Ainga an, and Kunle Oluko un. 2005. Niaga a: A 32-Way Mul i h eaded
Spa c P ocesso . IEEE Mic o 25, 2 (Ma ch 2005), 21–29. DOI:h p://dx.doi.o g/10.1109/MM.2005.35
Venka a K ishnan and Josep To ellas. 1998. Execu ing Sequen ial Bina ies on a Clus e ed Mul i h eaded
A chi ec u e wi h Specula ion Suppo . In P oceedings o he 1998 Fou h In e na ional Symposium on
High-Pe o mance Compu e A chi ec u e (HPCA ’98). IEEE Compu e Socie y, Washing on, DC, USA.
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
ZZ:34 A. Es ebanez, D. R. Llanos, and A. Gonzalez-Esc ibano
V. K ishnan and J. To ellas. 1999. 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 (1999), 866–880. DOI:h p://dx.doi.o g/10.1109/12.795218
V. P. K o hapalli and P. Sadayappan. 1988. An app oach o synch oniza ion o pa allel compu ing. In P o-
ceedings o he 2nd in e na ional con e ence on Supe compu ing (ICS ’88). ACM, New Yo k, NY, USA,
573–581. DOI:h p://dx.doi.o g/10.1145/55364.55420
V. P. K o hapalli and P. Sadayappan. 1990. Dynamic scheduling o DOACROSS loops o
mul ip ocesso s. In Da abases, Pa allel A chi ec u es and Thei Applica ions,. PARBASE-
90, In e na ional Con e ence on. IEEE Compu e Socie y, Washing on, DC, USA, 66–75.
DOI:h p://dx.doi.o g/10.1109/PARBSE.1990.77118
C.P. K uskal and A. Weiss. 1985. Alloca ing Independen Sub asks on Pa allel P ocesso s. So wa e Engi-
nee ing, IEEE T ansac ions on SE-11, 10 (1985), 1001–1016.
M. Kulka ni, M. Bu sche , C. Casca al, and K. Pingali. 2009a. Lones a : A sui e o pa allel
i egula p og ams. In Pe o mance Analysis o Sys ems and So wa e, 2009. ISPASS 2009.
IEEE In e na ional Symposium on. IEEE Compu e Socie y, Washing on, DC, USA, 65–76.
DOI:h p://dx.doi.o g/10.1109/ISPASS.2009.4919639
Milind Kulka ni, Ma in Bu sche , Rajeshka Inkulu, Kesha Pingali, and Calin Casc¸a al. 2009b. How
Much Pa allelism is The e in I egula Applica ions?. In P oceedings o he 14 h ACM SIGPLAN Sym-
posium on P inciples and P ac ice o Pa allel P og amming (PPoPP ’09). ACM, New Yo k, NY, USA,
3–14. DOI:h p://dx.doi.o g/10.1145/1504176.1504181
Milind Kulka ni, Pa ick Ca ibaul , Kesha Pingali, Ganesh Ramana ayanan, B uce Wal e , Ka i a Bala,
and L. Paul Chew. 2008. Scheduling S a egies o Op imis ic Pa allel Execu ion o I egula P og ams.
In P oceedings o he Twen ie h Annual Symposium on Pa allelism in Algo i hms and A chi ec u es
(SPAA ’08). ACM, New Yo k, NY, USA, 217–228. DOI:h p://dx.doi.o g/10.1145/1378533.1378575
Milind Kulka ni, Donald Nguyen, Dimi ios P oun zos, Xin Sui, and Kesha Pingali. 2011. Exploi -
ing he Commu a i i y La ice. In P oceedings o he 32Nd ACM SIGPLAN Con e ence on P o-
g amming Language Design and Implemen a ion (PLDI ’11). ACM, New Yo k, NY, USA, 542–555.
DOI:h p://dx.doi.o g/10.1145/1993498.1993562
Milind Kulka ni, Kesha Pingali, Ganesh Ramana ayanan, B uce Wal e , Ka i a Bala, and L. Paul Chew.
2008. Op imis 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). ACM, New Yo k, NY, USA, 233–243. DOI:h p://dx.doi.o g/10.1145/1346281.1346311
Milind Kulka ni, Kesha Pingali, B uce Wal e , Ganesh Ramana ayanan, Ka i a Bala, and L. Paul Chew.
2007. Op imis ic pa allelism equi es abs ac ions. In PLDI 2007 P oceedings. ACM, New Yo k, NY,
USA, 211–222.
Milind Kulka ni, Kesha Pingali, B uce Wal e , Ganesh Ramana ayanan, Ka i a Bala, and L. Paul
Chew. 2009. Op imis ic Pa allelism Requi es Abs ac ions. Commun. ACM 52, 9 (Sep . 2009), 89–97.
DOI:h p://dx.doi.o g/10.1145/1562164.1562188
Ch is La ne and Vik am Ad e. 2004. LLVM: A Compila ion F amewo k o Li elong P og am Analysis
& T ans o ma ion. In P oceedings o he In e na ional Symposium on Code Gene a ion and Op imiza-
ion: Feedback-di ec ed and Run ime Op imiza ion (CGO ’04). IEEE Compu e Socie y, Washing on, DC,
USA, 75–. h p://dl.acm.o g/ci a ion.c m?id=977395.977673
Peng Li and Song Guo. 2010. Ene gy Minimiza ion on Th ead-Le el Specula ion in Mul ico e
Sys ems. In P oceedings o he 2010 Nin h In e na ional Symposium on Pa allel and Dis-
ibu ed Compu ing (ISPDC ’10). IEEE Compu e Socie y, Washing on, DC, USA, 125–132.
DOI:h p://dx.doi.o g/10.1109/ISPDC.2010.17
Xiao-Feng Li, ZhaoHui Du, Chen Yang, Chu-Cheow Lim, and Tin-Fook Ngai. 2005. Specula i e Pa al-
lel Th eading A chi ec u e and Compila ion. In P oceedings o he 2005 In e na ional Con e ence on
Pa allel P ocessing Wo kshops (ICPPW ’05). IEEE Compu e Socie y, Washing on, DC, USA, 285–294.
DOI:h p://dx.doi.o g/10.1109/ICPPW.2005.81
Xiao-Feng Li, Zhao-Hui Du, Qingyu Zhao, and Tin-Fook Ngai. 2003. So wa e alue p edic ion o specula-
i e pa allel h eaded compu a ions. In Fi s alie P edic ion Wo kshop. 18–25.
Shaoshan Liu, Ch is ine Eisenbeis, and Jean-Luc Gaudio . 2010. Specula i e Execu ion on
GPU: An Explo a o y S udy. In P oceedings o he 2010 39 h In e na ional Con e ence on
Pa allel P ocessing (ICPP ’10). IEEE Compu e Socie y, Washing on, DC, USA, 453–461.
DOI:h p://dx.doi.o g/10.1109/ICPP.2010.53
Wei Liu, James Tuck, Luis Ceze, Wonsun Ahn, Ka in S auss, Jose Renau, and Josep To ellas. 2006. POSH:
a TLS compile ha exploi s p og am s uc u e. In P oceedings o he ele en h ACM SIGPLAN sym-
posium on P inciples and p ac ice o pa allel p og amming (PPoPP ’06). ACM, New Yo k, NY, USA,
158–167. DOI:h p://dx.doi.o g/10.1145/1122971.1122997
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
A Su ey on Th ead-Le el Specula ion Techniques ZZ:35
Diego R. Llanos, Da id O den, and Bel´
en Palop. 2007. New Scheduling S a egies o Randomized Inc e-
men al Algo i hms in he Con ex o Specula i e Pa alleliza ion. IEEE T ans. Compu . 56, 6 (2007),
839–852. DOI:h p://dx.doi.o g/10.1109/TC.2007.1030
Diego R. Llanos, Da id O den, and Bel´
en Palop. 2008. Jus -In-Time Scheduling o Loop-based Specula i e
Pa alleliza ion. Pa allel, Dis ibu ed, and Ne wo k-Based P ocessing, Eu omic o Con e ence on 0 (2008),
334–342. DOI:h p://dx.doi.o g/10.1109/PDP.2008.13
Yangchun Luo, Wei-Chung Hsu, and An onia Zhai. 2013. The Design and Implemen a ion o He e ogeneous
Mul ico e Sys ems o Ene gy-e icien Specula i e Th ead Execu ion. ACM T ans. A chi . Code Op im.
10, 4, A icle 26 (Dec. 2013), 29 pages. DOI:h p://dx.doi.o g/10.1145/2541228.2541233
Ped o Ma cuello, An onio Gonzalez, and Jo di Tubella. 1998. Specula i e mul i h eaded p ocesso s. In P o-
ceedings o he 12 h in e na ional con e ence on Supe compu ing (ICS ’98). ACM, New Yo k, NY, USA,
77–84. DOI:h p://dx.doi.o g/10.1145/277830.277850
Jos´
e F. Ma ´
ınez and Josep To ellas. 2002. Specula i e Synch oniza ion: Applying Th ead-le el Specula ion
o Explici ly Pa allel Applica ions. In P oceedings o he 10 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 X). ACM, New Yo k, NY, USA,
18–29. DOI:h p://dx.doi.o g/10.1145/605397.605400
Jan Ma insen, Hakan G ahn, and Ande s Isbe g. 2013. Using Specula ion o Enhance Ja aSc ip
Pe o mance in Web Applica ions. IEEE In e ne Compu ing 17, 2 (Ma ch 2013), 10–19.
DOI:h p://dx.doi.o g/10.1109/MIC.2012.146
Moj aba Meh a a, Je Hao, Po-Chun Hsu, and Sco Mahlke. 2009. 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 oceedings o he 2009
ACM SIGPLAN con e ence on P og amming language design and implemen a ion (PLDI ’09). ACM,
New Yo k, NY, USA, 166–176. DOI:h p://dx.doi.o g/10.1145/1542476.1542495
Ma io M´
endez-Lojo, Donald Nguyen, Dimi ios P oun zos, Xin Sui, M. Ambe Hassaan, Milind Kulka-
ni, Ma in Bu sche , and Kesha Pingali. 2010. 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 in-
ciples and P ac ice o Pa allel P og amming (PPoPP ’10). ACM, New Yo k, NY, USA, 3–14.
DOI:h p://dx.doi.o g/10.1145/1693453.1693457
Samuel P Midki and Da id A Padua. 1987. Compile algo i hms o synch oniza ion. Compu e s, IEEE
T ansac ions on 100, 12 (1987), 1485–1495.
R. Mi chandaney and J. H. Sal z. 1988. Dodynamic: A cons uc o on- he- ly pa alleliza ion o loops. Tech-
nical Repo 650. Yale Uni e si y. in p epa a ion.
Cosmin E. Oancea, Alan Myc o , and Tim Ha is. 2009. 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, NY, USA, 223–232.
DOI:h p://dx.doi.o g/10.1145/1583991.1584050
Kunle Oluko un, Lance Hammond, and Ma k Willey. 1999. Imp o ing he pe o mance o specula i ely
pa allel applica ions on he Hyd a CMP. In P oceedings o he 13 h in e na ional con e ence on Supe -
compu ing (ICS ’99). ACM, New Yo k, NY, USA, 21–30. DOI:h p://dx.doi.o g/10.1145/305138.305155
Kunle Oluko un, Basem A. Nay eh, Lance Hammond, Ken Wilson, and Kunyung Chang. 1996. The Case o
a Single-chip Mul ip ocesso . In P oceedings o he Se en 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 VII). ACM, New Yo k, NY, USA,
2–11. DOI:h p://dx.doi.o g/10.1145/237090.237140
K. Oluko un, O.A. Oluko un, L.S. Hammond, and J.P. Laudon. 2007. Chip Mul ip ocesso A chi ec u e: Tech-
niques o Imp o e Th oughpu and La ency. Mo gan & Claypool Publishe s, San Ra ael, CA, USA.
h p://books.google.es/books?id=spZZDwuAgUYC
Je ey Oplinge , Da id Heine, Shih Liao, Basem A. Nay eh, Monica S. Lam, and Kunle Oluko un. 1997.
So wa e and Ha dwa e o Exploi ing Specula i e Pa allelism wi h a Mul ip ocesso . Technical Repo .
S an o d Uni e si y, S an o d, CA, USA.
Je ey T. Oplinge , Da id L. Heine, and Monica S. Lam. 1999. In Sea ch o Specula i e Th ead-Le el Pa -
allelism. In P oceedings o he 1999 In e na ional Con e ence on Pa allel A chi ec u es and Compila ion
Techniques (PACT ’99). IEEE Compu e Socie y, Washing on, DC, USA, 303–. h p://dl.acm.o g/ci a ion.
c m?id=520793.825732
Guilhe me O oni, Ram Rangan, Adam S ole , and Da id I Augus . 2005. Au oma ic h ead ex ac ion wi h
decoupled so wa e pipelining. In P oceedings o he 38 h annual IEEE/ACM In e na ional Symposium
on Mic oa chi ec u e. IEEE Compu e Socie y, 105–118.
V. Packi isamy, Yangchun Luo, Wei-Lung Hung, A. Zhai, Pen-Chung Yew, and Tin-Fook Ngai. 2008. E i-
ciency o h ead-le el specula ion in SMT and CMP a chi ec u es - pe o mance, powe and he mal
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
ZZ:36 A. Es ebanez, D. R. Llanos, and A. Gonzalez-Esc ibano
pe spec i e. In Compu e Design, 2008. ICCD 2008. IEEE In e na ional Con e ence on. IEEE Compu e
Socie y, Washing on, DC, USA, 286–293. DOI:h p://dx.doi.o g/10.1109/ICCD.2008.4751875
Venka esan Packi isamy, Shengyue Wang, An onia Zhai, Wei-Chung Hsu, and Pen-Chung Yew. 2006. Sup-
po ing Specula i e Mul i h eading on Simul aneous Mul i h eaded P ocesso s. In P oceedings o he
13 h In e na ional Con e ence on High Pe o mance Compu ing (HiPC’06). Sp inge -Ve lag, Be lin, Hei-
delbe g, 148–158. DOI:h p://dx.doi.o g/10.1007/11945918 19
V. Packi isamy, A. Zhai, Wei-Chung Hsu, Pen-Chung Yew, and Tin-Fook Ngai. 2009. Explo ing specu-
la i e pa allelism in SPEC2006. In Pe o mance Analysis o Sys ems and So wa e, 2009. ISPASS
2009. IEEE In e na ional Symposium on. IEEE Compu e Socie y, Washing on, DC, USA, 77–88.
DOI:h p://dx.doi.o g/10.1109/ISPASS.2009.4919640
Sh u i Padmanabha, And ew Luke ah , Ree upa na Das, and Sco Mahlke. 2013. T ace Based Phase
P edic ion o Tigh ly-coupled He e ogeneous Co es. In P oceedings o he 46 h Annual IEEE/ACM
In e na ional Symposium on Mic oa chi ec u e (MICRO-46). ACM, New Yo k, NY, USA, 445–456.
DOI:h p://dx.doi.o g/10.1145/2540708.2540746
Robe o Palmie i, F ancesco Quaglia, and Paolo Romano. 2011. Osa e: Oppo unis ic specula ion in ac i ely
eplica ed ansac ional sys ems. In Reliable Dis ibu ed Sys ems (SRDS), 2011 30 h IEEE Symposium
on. IEEE, 59–64.
Il Pa k, Babak Falsa i, and T. N. Vijaykuma . 2003. Implici ly-mul i h eaded P ocesso s. In P oceedings o
he 30 h Annual In e na ional Symposium on Compu e A chi ec u e (ISCA ’03). ACM, New Yo k, NY,
USA, 39–51. DOI:h p://dx.doi.o g/10.1145/859618.859624
Sanjay Je am Pa el, Ma ius E e s, and Yale N. Pa . 1998. Imp o ing T ace Cache E ec i eness wi h
B anch P omo ion and T ace Packing. In P oceedings o he 25 h Annual In e na ional Sympo-
sium on Compu e A chi ec u e (ISCA ’98). IEEE Compu e Socie y, Washing on, DC, USA, 262–271.
DOI:h p://dx.doi.o g/10.1145/279358.279394
A. Phansalka , A. Joshi, L. Eeckhou , and L. K. John. 2005. Measu ing P og am Simila i y: Expe imen s
wi h SPEC CPU Benchma k Sui es. In P oceedings o he IEEE In e na ional Symposium on Pe o -
mance Analysis o Sys ems and So wa e, 2005 (ISPASS ’05). IEEE Compu e Socie y, Washing on, DC,
USA, 10–20. DOI:h p://dx.doi.o g/10.1109/ISPASS.2005.1430555
Ch is ophe J. F. Picke . 2007. So wa e Specula i e Mul i h eading o Ja a. In Companion o he 22Nd
ACM SIGPLAN Con e ence on Objec -o ien ed P og amming Sys ems and Applica ions Companion
(OOPSLA ’07). ACM, New Yo k, NY, USA, 929–930. DOI:h p://dx.doi.o g/10.1145/1297846.1297950
Ch is ophe J. F. Picke and Cla k Ve b ugge. 2005. SableSpMT: A So wa e F amewo k o Analysing
Specula i e Mul i h eading in Ja a. In P oceedings o he 6 h ACM SIGPLAN-SIGSOFT Wo kshop on
P og am Analysis o So wa e Tools and Enginee ing (PASTE ’05). ACM, New Yo k, NY, USA, 59–66.
DOI:h p://dx.doi.o g/10.1145/1108792.1108809
Ch is ophe J. F. Picke and Cla k Ve b ugge. 2006. So wa e Th ead Le el Specula ion o he Ja a Lan-
guage and Vi ual Machine En i onmen . In P oceedings o he 18 h In e na ional Con e ence on Lan-
guages and Compile s o Pa allel Compu ing (LCPC’05). Sp inge -Ve lag, Be lin, Heidelbe g, 304–318.
DOI:h p://dx.doi.o g/10.1007/978-3-540-69330-7 21
C. D. Polych onopoulos and D. J. Kuck. 1987. Guided sel -scheduling: A p ac ical scheduling
scheme o pa allel supe compu e s. IEEE T ans. Compu . 36, 12 (Dec. 1987), 1425–1439.
DOI:h p://dx.doi.o g/10.1109/TC.1987.5009495
Leo Po e , Bumyong Choi, and Dean M. Tullsen. 2009. Mapping Ou a Pa h om Ha dwa e T ansac ional
Memo y o Specula i e Mul i h eading. In P oceedings o he 2009 18 h In e na ional Con e ence on
Pa allel A chi ec u es and Compila ion Techniques (PACT ’09). IEEE Compu e Socie y, Washing on,
DC, USA, 313–324. DOI:h p://dx.doi.o g/10.1109/PACT.2009.37
Manoha K. P abhu and Kunle Oluko un. 2003. Using Th ead-le el Specula ion o Simpli y
Manual Pa alleliza ion. In P oceedings o he Nin h ACM SIGPLAN Symposium on P inci-
ples and P ac ice o Pa allel P og amming (PPoPP ’03). ACM, New Yo k, NY, USA, 1–12.
DOI:h p://dx.doi.o g/10.1145/781498.781500
Manoha K. P abhu and Kunle Oluko un. 2005. Exposing specula i e h ead pa allelism in SPEC2000. In
P oceedings o he en h ACM SIGPLAN symposium on P inciples and p ac ice o pa allel p og amming
(PPoPP ’05). ACM, New Yo k, NY, USA, 142–152. DOI:h p://dx.doi.o g/10.1145/1065944.1065964
P akash P abhu, Ganesan Ramalingam, and Kapil Vaswani. 2010. Sa e p og ammable spec-
ula i e pa allelism. In P oceedings o he 2010 ACM SIGPLAN con e ence on P og am-
ming language design and implemen a ion (PLDI ’10). ACM, New Yo k, NY, USA, 50–61.
DOI:h p://dx.doi.o g/10.1145/1806596.1806603
Dimi ios P oun zos, Roman Mane ich, Kesha Pingali, and Ka h yn S. McKinley. 2011. A Shape Analysis
o Op imizing Pa allel G aph P og ams. In P oceedings o he 38 h Annual ACM SIGPLAN-SIGACT
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
A Su ey on Th ead-Le el Specula ion Techniques ZZ:37
Symposium on P inciples o P og amming Languages (POPL ’11). ACM, New Yo k, NY, USA, 159–172.
DOI:h p://dx.doi.o g/10.1145/1926385.1926405
Joan Puiggali, Boleslaw K Szymanski, Teo Jo ´
e, and Jose L Ma zo. 2012. Dynamic b anch specula ion in a
specula i e pa alleliza ion a chi ec u e o compu e clus e s. Concu ency and Compu a ion: P ac ice
and Expe ience 25, 7 (2012).
Ca los Ga c´
ıa Qui˜
nones, Ca los Mad iles, Jes´
us S´
anchez, Ped o Ma cuello, An onio Gonz´
alez, and
Dean M. Tullsen. 2005. Mi osis compile : an in as uc u e o specula i e h eading based
on p e-compu a ion slices. In P oceedings o he 2005 ACM SIGPLAN con e ence on P og am-
ming language design and implemen a ion (PLDI ’05). ACM, New Yo k, NY, USA, 269–279.
DOI:h p://dx.doi.o g/10.1145/1065010.1065043
Ra i Rajwa and James R. Goodman. 2001. Specula i e Lock Elision: Enabling Highly Concu en Mul i-
h eaded Execu ion. In P oceedings o he 34 h Annual ACM/IEEE In e na ional Symposium on Mi-
c oa chi ec u e (MICRO 34). IEEE Compu e Socie y, Washing on, DC, USA, 294–305. h p://dl.acm.
o g/ci a ion.c m?id=563998.564036
A un Raman, Hanjun Kim, Thomas R. Mason, Thomas B. Jablin, and Da id I. Augus . 2010. Specula i e
pa alleliza ion using so wa e mul i- h eaded ansac ions. In P oceedings o he i een h edi ion o
ASPLOS on A chi ec u al suppo o p og amming languages and ope a ing sys ems (ASPLOS XV).
ACM, New Yo k, NY, USA, 65–76. DOI:h p://dx.doi.o g/10.1145/1736020.1736030
Easwa an Raman, Neil Vahha ajani, Ram Rangan, and Da id I. Augus . 2008. Spice: specula i e pa -
allel i e a ion chunk execu ion. In P oceedings o he 6 h annual IEEE/ACM in e na ional sym-
posium on Code gene a ion and op imiza ion (CGO ’08). ACM, New Yo k, NY, USA, 175–184.
DOI:h p://dx.doi.o g/10.1145/1356058.1356082
Law ence Rauchwe ge . 2011. Specula i e Pa alleliza ion o Loops. In Encyclopedia o Pa allel Compu ing,
Da id Padua (Ed.). Sp inge US, USA, 1901–1912. DOI:h p://dx.doi.o g/10.1007/978-0-387-09766-4 35
Law ence Rauchwe ge and Da id Padua. 1995. 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 (June 1995), 218–232.
DOI:h p://dx.doi.o g/10.1145/223428.207148
L. Rauchwe ge and D. A. Padua. 1999. The LRPD Tes : Specula i e Run-Time Pa alleliza ion o Loops wi h
P i a iza ion and Reduc ion Pa alleliza ion. IEEE T ansac ions on Pa allel and Dis ibu ed Sys ems 10,
2 (1999), 160–180.
Jose Renau, Ka in S auss, Luis Ceze, Wei Liu, Sm u i Sa angi, James Tuck, and Josep To ellas.
2005. Th ead-Le el Specula ion on a CMP can be ene gy e icien . In P oceedings o he 19 h an-
nual in e na ional con e ence on Supe compu ing (ICS ’05). ACM, New Yo k, NY, USA, 219–228.
DOI:h p://dx.doi.o g/10.1145/1088149.1088178
J. Renau, K. S auss, L. Ceze, Wei Liu, S.R. Sa angi, J. Tuck, and J. To ellas. 2006. Ene gy-E icien Th ead-
Le el Specula ion. Mic o, IEEE 26, 1 (2006), 80–91. DOI:h p://dx.doi.o g/10.1109/MM.2006.11
Jose Renau, James Tuck, Wei Liu, Luis Ceze, Ka in S auss, and Josep To ellas. 2005. Tasking wi h ou -
o -o de spawn in TLS chip mul ip ocesso s: Mic oa chi ec u e and compila ion. In P oceedings o he
19 h annual in e na ional con e ence on Supe compu ing (ICS ’05). ACM, New Yo k, NY, USA, 179–188.
DOI:h p://dx.doi.o g/10.1145/1088149.1088173
Anne Roge s, Ma in C. Ca lisle, John H. Reppy, and Lau ie J. Hend en. 1995. Suppo ing Dynamic Da a
S uc u es on Dis ibu ed-memo y Machines. ACM T ans. P og am. Lang. Sys . 17, 2 (Ma ch 1995),
233–263. DOI:h p://dx.doi.o g/10.1145/201059.201065
E ic Ro enbe g, S e e Benne , and James E. Smi h. 1996. T ace Cache: A Low La ency App oach o
High Bandwid h Ins uc ion Fe ching. In P oceedings o he 29 h Annual ACM/IEEE In e na ional
Symposium on Mic oa chi ec u e (MICRO 29). IEEE Compu e Socie y, Washing on, DC, USA, 24–35.
h p://dl.acm.o g/ci a ion.c m?id=243846.243854
E ic Ro enbe g, Quinn Jacobson, Yiannakis Sazeides, and Jim Smi h. 1997. T ace P ocesso s. In P oceed-
ings o he 30 h Annual ACM/IEEE In e na ional Symposium on Mic oa chi ec u e (MICRO 30). IEEE
Compu e Socie y, Washing on, DC, USA, 138–148. h p://dl.acm.o g/ci a ion.c m?id=266800.266814
E ic Ro enbe g and Jim Smi h. 1999. Con ol Independence in T ace P ocesso s. In P oceedings o he 32Nd
Annual ACM/IEEE In e na ional Symposium on Mic oa chi ec u e (MICRO 32). IEEE Compu e Soci-
e y, Washing on, DC, USA, 4–15. h p://dl.acm.o g/ci a ion.c m?id=320080.320084
Ami abha Roy, S e en Hand, and Tim Ha is. 2009. A Run ime Sys em o So wa e Lock Elision. In P o-
ceedings o he 4 h ACM Eu opean Con e ence on Compu e Sys ems (Eu oSys ’09). ACM, New Yo k, NY,
USA, 261–274. DOI:h p://dx.doi.o g/10.1145/1519065.1519094
Pe e Rundbe g and Pe S ens ¨
om. 2000. Low-Cos Th ead-Le el Da a Dependence Specula ion on Mul i-
p ocesso s. In Wo kshop on Scalable Sha ed Memo y Mul ip ocesso s.
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.

ZZ:38 A. Es ebanez, D. R. Llanos, and A. Gonzalez-Esc ibano
J. H. Sal z and R. Mi chandaney. 1988. How o schedule complex loops in pa allel. Technical Repo 657.
Yale Uni e si y.
Joel H Sal z, Ra i Mi chandaney, and Kay C owley. 1991. Run- ime pa alleliza ion and scheduling o loops.
Compu e s, IEEE T ansac ions on 40, 5 (1991), 603–612.
Meh zad Samadi, Ami Ho ma i, Janghaeng Lee, and Sco Mahlke. 2012. Pa agon: Collabo a i e Spec-
ula i e Loop Execu ion on GPU and CPU. In P oceedings o he 5 h Annual Wo kshop on Gene al
Pu pose P ocessing wi h G aphics P ocessing Uni s (GPGPU-5). ACM, New Yo k, NY, USA, 64–73.
DOI:h p://dx.doi.o g/10.1145/2159430.2159438
Gu inda S. Sohi, Sco E. B each, and T. N. Vijaykuma . 1995. Mul iscala p ocesso s. In P oceedings o he
22nd annual in e na ional symposium on Compu e a chi ec u e (ISCA ’95). ACM, New Yo k, NY, USA,
414–425. DOI:h p://dx.doi.o g/10.1145/223982.224451
J. S e an and T Mow y. 1998. The Po en ial o Using Th ead-Le el Da a Specula ion o Facili a e Au o-
ma ic Pa alleliza ion. In P oceedings o he 4 h In e na ional Symposium on High-Pe o mance Com-
pu e A chi ec u e (HPCA ’98). IEEE Compu e Socie y, Washing on, DC, USA, 2–. h p://dl.acm.o g/
ci a ion.c m?id=822079.822712
J. G ego y S e an, Ch is ophe Colohan, An onia Zhai, and Todd C. Mow y. 2005. The STAMPede
App oach o Th ead-le el Specula ion. ACM T ans. Compu . Sys . 23, 3 (Aug. 2005), 253–300.
DOI:h p://dx.doi.o g/10.1145/1082469.1082471
J. G eggo y S e an, Ch is ophe B. Colohan, An onia Zhai, and Todd C. Mow y. 2000. 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). ACM, New Yo k, NY, USA, 1–12. DOI:h p://dx.doi.o g/10.1145/339647.339650
J. G ego y S e an, Ch is ophe B. Colohan, An onia Zhai, and Todd C. Mow y. 2002. Imp o ing Value Com-
munica ion o Th ead-Le el Specula ion. In P oceedings o he 8 h In e na ional Symposium on High-
Pe o mance Compu e A chi ec u e (HPCA ’02). IEEE Compu e Socie y, Washing on, DC, USA, 65–.
h p://dl.acm.o g/ci a ion.c m?id=874076.876480
Peiyi Tang and Pen-Chung Yew. 1986. P ocesso Sel -Scheduling o Mul iple-Nes ed Pa allel Loops.. In
ICPP, Vol. 86. CRC P ess, USA, 528–535.
YuXing Tang, Kun Deng, and XingMing Zhou. 2005. The Design Space o CMP s. SMT o High Pe o mance
Embedded P ocesso . In Embedded So wa e and Sys ems, Lau enceT. Yang, Xingshe Zhou, Wei Zhao,
Zhaohui Wu, Yian Zhu, and Man Lin (Eds.). Lec u e No es in Compu e Science, Vol. 3820. Sp inge ,
Be lin Heidelbe g, 30–38. DOI:h p://dx.doi.o g/10.1007/11599555 6
Chen Tian, Min Feng, and Raji Gup a. 2010a. Specula i e Pa alleliza ion Using S a e Sepa a ion and
Mul iple Value P edic ion. In P oceedings o he 2010 In e na ional Symposium on Memo y Managemen
(ISMM ’10). ACM, New Yo k, NY, USA, 63–72. DOI:h p://dx.doi.o g/10.1145/1806651.1806663
Chen Tian, Min Feng, and Raji Gup a. 2010b. Suppo ing specula i e pa alleliza ion in he p es-
ence o dynamic da a s uc u es. In P oceedings o he 2010 ACM SIGPLAN con e ence on P o-
g amming language design and implemen a ion (PLDI ’10). ACM, New Yo k, NY, USA, 12.
DOI:h p://dx.doi.o g/10.1145/1806596.1806604
Chen Tian, Min Feng, Vijay Naga ajan, and Raji Gup a. 2008. Copy o Disca d execu ion model o specu-
la i e pa alleliza ion on mul ico es. In P oceedings o he 41s annual IEEE/ACM In e na ional Sym-
posium on Mic oa chi ec u e (MICRO 41). IEEE Compu e Socie y, Washing on, DC, USA, 330–341.
DOI:h p://dx.doi.o g/10.1109/MICRO.2008.4771802
Chen Tian, Min Feng, Vijay Naga ajan, and Raji Gup a. 2009. Specula i e Pa alleliza ion
o Sequen ial Loops on Mul ico es. In . J. Pa allel P og am. 37, 5 (Oc . 2009), 508–535.
DOI:h p://dx.doi.o g/10.1007/s10766-009-0111-z
Chen Tian, Changhui Lin, Min Feng, and Raji Gup a. 2011. Enhanced specula i e pa alleliza-
ion ia inc emen al eco e y. In P oceedings o he 16 h ACM symposium on P inciples
and p ac ice o pa allel p og amming (PPoPP ’11). ACM, New Yo k, NY, USA, 189–200.
DOI:h p://dx.doi.o g/10.1145/1941553.1941580
Josep To ellas. 2011. Specula ion, Th ead-Le el. In Encyclopedia o Pa allel Compu ing, Da id Padua (Ed.).
Sp inge US, USA, 1894–1900. DOI:h p://dx.doi.o g/10.1007/978-0-387-09766-4 170
Geo gios Tou na i is, Zheng Wang, Bj¨
o n F anke, and Michael FP O’Boyle. 2009. Towa ds a holis ic ap-
p oach o au o-pa alleliza ion: in eg a ing p o ile-d i en pa allelism de ec ion and machine-lea ning
based mapping. In ACM Sigplan No ices, Vol. 44. ACM, 177–187.
Jo di Tubella and An onio Gonzalez. 1998. Con ol specula ion in mul i h eaded p ocesso s h ough
dynamic loop de ec ion. In P oceedings o he 1998 Fou h In e na ional Symposium on High-
Pe o mance Compu e A chi ec u e (HPCA ’98). IEEE Compu e Socie y, Washing on, DC, USA, 14–23.
DOI:h p://dx.doi.o g/10.1109/HPCA.1998.650542
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
A Su ey on Th ead-Le el Specula ion Techniques ZZ:39
Dean M. Tullsen, Susan J. Egge s, Joel S. Eme , Hen y M. Le y, Jack L. Lo, and Rebecca L. S amm. 1996.
Exploi ing Choice: Ins uc ion Fe ch and Issue on an Implemen able Simul aneous Mul i h eading P o-
cesso . In P oceedings o he 23 d Annual In e na ional Symposium on Compu e A chi ec u e (ISCA
’96). ACM, New Yo k, NY, USA, 191–202. DOI:h p://dx.doi.o g/10.1145/232973.232993
Dean M. Tullsen, Susan J. Egge s, and Hen y M. Le y. 1998. Simul aneous Mul i h eading: Maximizing On-
chip Pa allelism. In 25 Yea s o he In e na ional Symposia on Compu e A chi ec u e (Selec ed Pape s)
(ISCA ’98). ACM, New Yo k, NY, USA, 533–544. DOI:h p://dx.doi.o g/10.1145/285930.286011
Theo Unge e , Bo u Robiˇ
c, and Ju ij ˇ
Silc. 2003. A Su ey o P ocesso s wi h Explici Mul i h eading. ACM
Compu . Su . 35, 1 (Ma ch 2003), 29–63. DOI:h p://dx.doi.o g/10.1145/641865.641867
T. N. Vijaykuma . 1998. Compiling o he mul iscala a chi ec u e. Ph.D. Disse a ion. The Uni e si y o
Wisconsin - Madison. AAI9813127.
T. N. Vijaykuma and Gu inda S. Sohi. 1998. Task selec ion o a mul iscala p ocesso . In P oceedings o he
31s annual ACM/IEEE in e na ional symposium on Mic oa chi ec u e (MICRO 31). IEEE Compu e
Socie y P ess, Los Alami os, CA, USA, 81–92. h p://dl.acm.o g/ci a ion.c m?id=290940.290963
S e en Wallace, B ad Calde , and Dean M. Tullsen. 1998. Th eaded Mul iple Pa h Execu ion. In P oceedings
o he 25 h Annual In e na ional Symposium on Compu e A chi ec u e (ISCA ’98). IEEE Compu e
Socie y, Washing on, DC, USA, 238–249. DOI:h p://dx.doi.o g/10.1145/279358.279392
Shengyue Wang, Xiao u Dai, Ki an S. Yellajyosula, An onia Zhai, and Pen-Chung Yew. 2006. Loop Se-
lec ion o Th ead-le el Specula ion. In P oceedings o he 18 h In e na ional Con e ence on Lan-
guages and Compile s o Pa allel Compu ing (LCPC’05). Sp inge -Ve lag, Be lin, Heidelbe g, 289–303.
DOI:h p://dx.doi.o g/10.1007/978-3-540-69330-7 20
F ed ik Wa g and Pe S ens ¨
om. 2001. Limi s on Specula i e Module-Le el Pa allelism in Impe a i e and
Objec -O ien ed P og ams on CMP Pla o ms. In P oceedings o he 2001 In e na ional Con e ence on
Pa allel A chi ec u es and Compila ion Techniques (PACT ’01). IEEE Compu e Socie y, Washing on,
DC, USA, 221–230. h p://dl.acm.o g/ci a ion.c m?id=645988.674160
F ed ik Wa g and Pe S ens ¨
om. 2003. Imp o ing Specula i e Th ead-Le el Pa allelism Th ough Mod-
ule Run-Leng h P edic ion. In P oceedings o he 17 h In e na ional Symposium on Pa allel and Dis-
ibu ed P ocessing (IPDPS ’03). IEEE Compu e Socie y, Washing on, DC, USA, 12.2–. h p://dl.acm.
o g/ci a ion.c m?id=838237.838521
F ed ik Wa g and Pe S ens ¨
om. 2005. Reducing misspecula ion o e head o module-le el specula i e
execu ion. In P oceedings o he 2nd con e ence on Compu ing on ie s (CF ’05). ACM, New Yo k, NY,
USA, 289–298. DOI:h p://dx.doi.o g/10.1145/1062261.1062310
Michael E Wol and Monica S Lam. 1991. A loop ans o ma ion heo y and an algo i hm o maximize
pa allelism. Pa allel and Dis ibu ed Sys ems, IEEE T ansac ions on 2, 4 (1991), 452–471.
Peng Wu, A un Keja iwal, and C˘
alin Cas¸ca al. 2008. Compile -D i en Dependence P o iling o Guide P o-
g am Pa alleliza ion. In Languages and Compile s o Pa allel Compu ing, Jos´
e Nelson Ama al (Ed.).
Sp inge -Ve lag, Be lin, Heidelbe g, 232–248. DOI:h p://dx.doi.o g/10.1007/978-3-540-89740-8 16
P. Xekalakis and M. Cin a. 2010. Handling b anches in TLS sys ems wi h Mul i-Pa h Execu ion. In High
Pe o mance Compu e A chi ec u e (HPCA), 2010 IEEE 16 h In e na ional Symposium on. IEEE Com-
pu e Socie y, Washing on, DC, USA, 1–12. DOI:h p://dx.doi.o g/10.1109/HPCA.2010.5416632
Polych onis Xekalakis, Nikolas Ioannou, and Ma celo Cin a. 2009. Combining Th ead Le el
Specula ion, Helpe Th eads and Runahead Execu ion. In P oceedings o he 23 d In e -
na ional Con e ence on Supe compu ing (ICS ’09). ACM, New Yo k, NY, USA, 410–420.
DOI:h p://dx.doi.o g/10.1145/1542275.1542333
Polych onis Xekalakis, Nikolas Ioannou, and Ma celo Cin a. 2012. Mixed Specula i e Mul i h eaded
Execu ion Models. ACM T ans. A chi . Code Op im. 9, 3, A icle 18 (oc 2012), 26 pages.
DOI:h p://dx.doi.o g/10.1145/2355585.2355591
Polych onis Xekalakis, Nikolas Ioannou, Salman Khan, and Ma celo Cin a. 2010. P o i abili y-based powe
alloca ion o specula i e mul i h eaded sys ems. In Pa allel & Dis ibu ed P ocessing (IPDPS), 2010
IEEE In e na ional Symposium on. IEEE, 1–11.
Pa aske as Yiapanis, Demian Rosas-Ham, Ga in B own, and Mikel Luj´
an. 2013. 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, A icle 39 (Jan.
2013), 27 pages. DOI:h p://dx.doi.o g/10.1145/2400682.2400698
Chao Zhang, Chen Ding, Xiaoming Gu, Ki k Kelsey, Tongxin Bai, and Xiaobing Feng. 2010. Con inuous
specula i e p og am pa alleliza ion in so wa e. 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). ACM, New Yo k, NY, USA, 335–336.
DOI:h p://dx.doi.o g/10.1145/1693453.1693501
Chenggang Zhang, Guodong Han, and Cho-Li Wang. 2013. GPU-TLS: An E icien Run ime o Specu-
la i e Loop Pa alleliza ion on GPUs. In Clus e , Cloud and G id Compu ing (CCG id), 2013 13 h
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.
ZZ:40 A. Es ebanez, D. R. Llanos, and A. Gonzalez-Esc ibano
IEEE/ACM In e na ional Symposium on. IEEE Compu e Socie y, Washing on, DC, USA, 120–127.
DOI:h p://dx.doi.o g/10.1109/CCG id.2013.34
Zhijia Zhao and Xipeng Shen. 2015. On- he-Fly P incipled Specula ion o FSM Pa alleliza ion. In P oceed-
ings o he Twen ie 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. ACM, 619–630.
Zhijia Zhao, Bo Wu, and Xipeng Shen. 2012. 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 oceedings o he 21s in e na ional
con e ence on Pa allel a chi ec u es and compila ion echniques (PACT ’12). ACM, New Yo k, NY, USA,
433–434. DOI:h p://dx.doi.o g/10.1145/2370816.2370882
Zhijia Zhao, Bo Wu, and Xipeng Shen. 2014. Challenging he emba assingly sequen ial: pa allelizing i-
ni e s a e machine-based compu a ions h ough p incipled specula ion. In ACM SIGARCH Compu e
A chi ec u e News, Vol. 42. ACM, 543–558.
Chuan-Qi Zhu and Pen-Chung Yew. 1987. A scheme o en o ce da a dependence on la ge mul i-
p ocesso sys ems. So wa e Enginee ing, IEEE T ansac ions on SE-13, 6 (June 1987), 726–739.
DOI:h p://dx.doi.o g/10.1109/TSE.1987.233477
C aig Zilles and Gu inda Sohi. 2002. Mas e /sla e specula i e pa alleliza ion. In P oceedings o he 35 h
annual ACM/IEEE in e na ional symposium on Mic oa chi ec u e (MICRO 35). IEEE Compu e Soci-
e y P ess, Los Alami os, CA, USA, 85–96. h p://dl.acm.o g/ci a ion.c m?id=774861.774871
ACM Compu ing Su eys, Vol. X, No. Y, A icle ZZ, Publica ion da e: 20YY.