Con ol Specula ion in Mul i h eaded P ocesso s
h ough Dynamic Loop De ec ion
Jo di Tubella and An onio González
Depa amen d’A qui ec u a de Compu ado s
Uni e si a Poli ècnica de Ca alunya,
Campus No d, Jo di Gi ona 1-3, Edi ici D6, 08034 Ba celona, Spain
e-mail: {jo di ,an onio}@ac.upc.es
Abs ac
This pape p esen s a mechanism o dynamically de ec
he loops ha a e execu ed in a p og am. This echnique
de ec s he beginning and he e mina ion o he i e a ions
and execu ions o he loops wi hou compile /use
in e en ion. We p opose o apply his dynamic loop
de ec ion o he specula ion o mul iple h eads o con ol
dynamically ob ained om a sequen ial p og am. Based
on he highly p edic able beha io o he loops, he his o y
o he pas execu ed loops is used o specula e he u u e
ins uc ion sequence. The o e all objec i e is o
dynamically ob ain coa se g ain pa allelism (a he h ead
le el) ha can be exploi ed by a mul i h eaded
a chi ec u e. We show ha o a 4-con ex mul i h eaded
p ocesso , he specula ion mechanism p o ides a ound 2.6
concu en h eads in a e age.
1. In oduc ion
Con ol specula ion inc eases he po en ial pa allelism
ha a p ocesso can exploi (see [7] [12] among o he s).
B anch p edic ion is he mos s udied con ol specula ion
echnique, and i is inco po a ed in he la ge majo i y o
pas and cu en mic op ocesso s (see [8] [13] among o h-
e s). Such specula ion app oaches ha e been o ien ed o
supe scala p ocesso s. Howe e , li le esea ch has been
done on con ol specula ion o o he eme ging a chi ec-
u es. In pa icula , his wo k ocuses on mul i h eaded
a chi ec u es. In his pape , a mul i h eaded a chi ec u e
e e s o any a chi ec u e ha can concu en ly execu e
se e al h eads o con ol1 om a single sequen ial p o-
1. In his pape , a h ead o con ol (o h ead o sho ) e e s o any
con iguous egion o he dynamic ins uc ion sequence.
g am, ega dless o he app oach used o ob ain such
h eads. Fo ins ance, he mul iscala [9] a chi ec u e
belongs o his class o a chi ec u es. In his pa icula
case, he pa i ion o a p og am in o h eads equi es some
compile suppo .
The wo k ha is p esen ed in his pape is aimed a
ob aining mul iple h eads om a sequen ial p og am
wi hou any use /compile in e en ion. The e a e se e al
easons o a gue o a ha dwa e mechanism: (i) he s a ic
analysis ha he compile may pe o m is less accu a e
han he ac ual dynamic beha io han can be ob ained
du ing he execu ion; (ii) p o iling mechanisms ha cha -
ac e ize he execu ion o a p og am ely on a conc e e se
o inpu da a; (iii) he ins uc ion se a chi ec u e is no
modi ied, gi ing backwa d compa ibili y wi h p e ious
implemen a ions. In e - h ead con ol specula ion is based
on a dynamic de ec ion o he loops in a p og am. The
h eads a e ob ained based on he highly p edic able
beha io o he loops.
We p esen a gene al mechanism ha allows he de ec-
ion o loops wi h a easonable cos and we also desc ibe
he applica ion o his dynamic loop de ec ion o imple-
men he in e - h ead con ol specula ion in a mul i-
h eaded a chi ec u e. The esul s show ha loops a e an
impo an sou ce o accu a e h ead p edic ion. Fo
ins ance, we show ha o a 4-con ex p ocesso , he p o-
posed h ead specula ion app oach can p o ide abou 2.6
concu en h eads in a e age.
In addi ion o in e - h ead con ol dependences, he p o-
posed mechanism can be used o specula e on bo h in e -
h ead da a dependences and he da a ha low h ough
hem. The de ini ion and implemen a ion o a pa icula
da a/da a dependence specula ion mechanism is beyond
he scope o his pape . Howe e , o show i s po en ial, we
p esen some p elimina y s a is ics abou he p edic abili y
o alues o li e-in2 egis e s and memo y loca ions o
specula i e h eads.
The e a e se e al p oposals in he li e a u e ega ding
mul i h eaded a chi ec u es o ien ed o he execu ion o a
single sequen ial p og am. The mos ema kable wo ks a e
he Expandable Spli Window pa adigm [3], he Mul isca-
la [9], he SPSM [2], he Supe h eaded [11] and he Mul-
i h eaded Decoupled [1] a chi ec u es. Howe e , all o
hem equi e ei he some use /compile in e en ion and/
o some ex ensions in he ins uc ion-se a chi ec u e.
Con ol low specula ion o Mul iscala p ocesso s has
been s udied in a ecen pape [5]. In such p oposal he
h eads (called asks in ha pape ) a e delimi ed a com-
pile ime and he un- ime mechanism is only esponsible
o p edic ing he sequence ha such h eads will ollow.
This pape p oposes a no el app oach ha can be used by
such ype o a chi ec u es in o de o ob ain mul iple
h eads o con ol by means o ha dwa e mechanisms.
The p oposed specula ion mechanism is based on a
loop de ec ion scheme. Dynamic loop de ec ion has been
s udied in [6] bu he mechanism p oposed in ha pape is
o ien ed o ex ac s a is ics om a ace gene a ed by a
p og am execu ion. I is no adequa e o a ha dwa e
implemen a ion and i does no ca e abou con ol specula-
ion.
This pape is o ganized as ollows. Sec ion 2 desc ibes
and analyzes he mechanism p oposed o he dynamic
de ec ion o loops. Sec ion 3 p esen s i s applica ion o
h ead con ol specula ion. Sec ion 4 p esen s some p e-
limina y s a is ics abou da a specula ion issues. Finally,
he main conclusions a e summa ized in sec ion 5.
2. Dynamic loop de ec ion
Loops a e a e y common con ol s uc u e in e e y
p og am. A high pe cen age o all ins uc ions execu ed in
a p og am belong o loops. Since in addi ion he closing
b anches o loops a e highly p edic able, loops a e po en-
ially use ul o pe o m con ol specula ion. In his sec ion
we i s de ine he ypes o loops ha we conside in his
pape . Then, an implemen a ion o dynamically de ec
such loops and he pe o mance exhibi ed o he SPEC95
benchma k sui e is p esen ed.
2.1. Loop de ini ions
Fo s uc u ed code, he e is a unanimous de ini ion o
wha a loop is. Howe e , o non-s uc u ed code di e en
in e p e a ions can be applied. In his subsec ion, we
p esen ou pa icula de ini ion o loops, which will be
used in he es o his pape . Fi s , we de ine he s a ic
2. A li e-in egis e (li e-in memo y loca ion) is a egis e (memo y
loca ion) ha is li e-on-en y o a h ead.
iew o a loop in a p og am. Then, we de ine he dynamic
iew o a loop wi h he concep s o loop execu ion and
loop i e a ion.
The e is a loop in a p og am, which i is iden i ied by
add ess T, when he e is a leas one backwa d b anch o
jump o add ess T. The e may be mo e han one b anch
wi h he same a ge add ess. In his case, we conside ha
all such b anches a e closing b anches o he same loop. A
main a ibu e o a loop is he highes add ess ha con ains
a backwa d b anch o jump o add ess T. This add ess is
deno ed by add ess B. All ins uc ions in he ange o
add esses [T,B] cons i u e he body o loop T. Once
en e ed in he loop body, i is possible o lea e i wi h an
ins uc ion ha o ces he execu ion con ol low o p o-
ceed o an add ess ou side he ange o he loop. This con-
ol low ins uc ion may be a b anch, a jump o a e u n
ins uc ion. The e may be any numbe o sub ou ine ac i-
a ions inside a loop body. No e ha his de ini ion o he
s a ic loop body does no include he bodies o he sub ou-
ines ha a e ac i a ed.
Figu e 1 shows a s a ic iew o a loop. Exi b anches
can be a he beginning o a he end o he loop body in
he case o while o do_while high-le el loop s uc u es. I
is also possible o lea e a loop om any o he pa o i , as
i is he case o a b eak,go o o e u n high-le el language
ins uc ions.
On he o he hand, we also de ine a dynamic iew o a
loop. Conside ing add ess B as he highes add ess o all
execu ed b anch o jump ins uc ions o a ge add ess T,
an execu ion o loop T consis s o a ce ain numbe o
sequen ially execu ed ins uc ions which a e delimi ed by
he ollowing condi ions.
An execu ion o loop T is ini ia ed when he i s
ins uc ion whose add ess belongs o he loop body ( ange
o add esses [T,B]), is execu ed.
An execu ion o loop T is e mina ed by one o he ol-
lowing ins uc ions: (i) a no aken b anch a add ess B, o
(ii) a aken b anch o a jump a an add ess belonging o he
T:
B:
JMP, BR o RET
JMP o BR
JMP o BR
Figu e 1: S a ic iew o a loop.
loop body o a a ge add ess ou side he loop body, o (iii)
a e u n ins uc ion a an add ess belonging o he loop
body.
Since usually any sub ou ine ac i a ion e u ns o he
add ess below he call ins uc ion, we conside ha inside
a loop execu ion he e may be any numbe o nes ed sub-
ou ine ac i a ions. No e ha ins uc ions belonging o he
sub ou ine body also belong o he loop execu ion.
Mo eo e , when a loop is inside a ecu si e sub ou ine,
no e ha he di e en ins an ia ions o he same loop ha
a e ob ained h ough ecu si e ac i a ions wi hou any
e u n in be ween a e conside ed o belong o he same
loop execu ion.
All ins uc ions in a loop execu ion a e di ided in o a
ce ain numbe o loop i e a ions. An i e a ion o loop T
consis s o a ce ain numbe o sequen ially execu ed
ins uc ions belonging o an execu ion o loop T wi h he
ollowing cha ac e is ics. The i s i e a ion o a loop T is
s a ed when i s loop execu ion is also ini ia ed. The es o
he i e a ions always begin a add ess T. All i e a ions o
loop T, excep he las one, always inish wi h a aken
backwa d b anch o jump o add ess T. The las i e a ion
inishes when i s loop execu ion also inishes.
A gi en dynamic ins uc ion may belong o se e al
loop execu ions. This occu s when loop s uc u es a e
nes ed o o e lapped.
Loops T1 and T2, wi h co esponding B1 and B2
b anch add esses, a e nes ed when he ange o add esses
[T2,B2] is included in o [T1,B1]. In his case, loop T2 is
he inne mos , and all ins uc ions in he execu ion o loop
T2 also belong o he execu ion o loop T1. Loops T1 and
T2 a e o e lapped when T2 > T1 and B2 > B1. In his
case, ins uc ions in he i s i e a ion o one o hese loops
also belong o he execu ion o he o he loop. Figu e 2
shows some samples o loop execu ions and loop i e a-
ions when wo loops a e ei he nes ed o o e lapped.
2.2. Ha dwa e mechanism o loop de ec ion
In o de o de ec loop execu ions and loop i e a ions,
we in oduce he Cu en Loop S ack (CLS). This s ack is
de o ed o con ain all loops which a e being cu en ly exe-
cu ed. The op o he s ack co esponds o he inne mos
loop, and he emaining loops a e s o ed acco ding o he
nes ing o de .
The elemen s in he CLS con ain wo ields (T,B). Field
T s o es he a ge add ess o a loop (i s iden i ie ) and ield
B s o es he highes add ess o all b anch o jump ins uc-
ions execu ed so a o add ess T. The CLS is upda ed
when execu ing h ee kinds o ins uc ions (b anch, jump
and e u n) in he ollowing manne (conside PC as hei
ins uc ion add ess).
Whene e a backwa d b anch o jump ins uc ion o
a ge T is execu ed, he CLS is sea ched. I he e is no
any en y wi h a ge add ess T and he b anch is aken, i
means ha a new loop execu ion is s a ed. In his case,
T1:
B1:
T2:
B2:
execu ion o loop T1
execu ions o loop T2
i e a ions o loop T1
i e a ions o loop T2
T1 T2
ins uc ion add ess T2 T2T2 B2B2 B1T1
T1:
B2:
T2:
B1:
Figu e 2: Nes ed and o e lapped loops: (a) S a ic iew o wo nes ed loops; (b)
Dynamic samples o loop execu ions and loop i e a ions o wo nes ed loops; (c)
S a ic iew o wo o e lapped loops; (d) Dynamic samples o loop execu ions and
loop i e a ions o wo o e lapped loops.
execu ions o loop T1
execu ions o loop T2
i e a ions o loop T1
i e a ions o loop T2
T1 T2
ins uc ion add ess T1 T2 B2B1T2B1 B2
B2 B1 B2
B1
(a) (b)
(c) (d)
loop (T,PC) is pushed on o he CLS. I he b anch is no
aken, no ac ion is pe o med. I means ha a loop wi h
only one i e a ion has been execu ed. I loop T is ound in
he en y i o he CLS and he b anch is aken, an i e a ion
o loop T has inished and consequen ly, a new i e a ion o
he same loop execu ion is s a ed. The CLS en ies in he
ange [ op,i+1] a e popped ou (we assume ha he op o
he s ack co esponds o he highes add ess). I PC is
highe han he alue o ield B, his ield is upda ed. I he
b anch is no aken and he alue o ield B is lowe han o
equal o PC, i means ha bo h he i e a ion and he execu-
ion o loop T ha e inished. The CLS en ies in he ange
[ op,i] a e popped ou .
Whene e he add ess o a jump o a aken b anch
belongs o a loop in he CLS, i is checked whe he he a -
ge add ess is ou side he loop body. All loops ha mee
his condi ion a e emo ed om he CLS (i.e., i is consid-
e ed ha hei execu ions ha e inished). Finally, o any
execu ed e u n ins uc ion, all loops in he CLS whose
body comp ise such ins uc ion a e also popped ou .
In he mos equen case, when an i e a ion o a loop
inishes, he en y ela ed o his loop is a he op o he
CLS. No e ha he op o he CLS co esponds o he
inne mos loop ha is being execu ed. Ne e heless, he e
a e wo si ua ions ha may cause an i e a ion o a loop ha
is no loca ed a he op o he CLS o inish. In hese si ua-
ions, all inne mos loops a e popped ou (as desc ibed wo
pa ag aphs abo e), and hus, hei execu ion is inished.
The i s si ua ion occu s when a sub ou ine call in a
loop body ne e e u ns o his loop body (e.g., when he
se jmp() lib a y call is used). I his loop is nes ed inside
ano he one, when an i e a ion o he ou e inishes i
implies he e mina ion o he inne one. I could also hap-
pen ha no ou e loop exis s, and hus, he loop would
emain in he CLS a he end o he execu ion. None he-
less, we ha e obse ed ha he CLS is always emp y a he
end o he en i ely execu ion o he SPEC95, which means
ha his e en ne e happens o his benchma k sui e. In
any case, such si ua ion could be handled by pe iodically
lushing he con en s o he CLS.
The second si ua ion is caused by no di e en ia ing he
ins an ia ions o he same loop T p oduced in ecu si e
sub ou ine ac i a ions. Fo ins ance, gi en he ollowing
s uc u e o a ecu si e sub ou ine:
s() {
i () {
o () s(); /* loop T1 */
} else {
o () s(); /* loop T2 */
}
}
Suppose ha ini ially loop T1 is being execu ed. The
ecu si e call o s() causes a new ac i a ion o he sub-
ou ine and his ime he else pa is execu ed. Since call
ins uc ions do no e mina e a loop execu ion, T2 is con-
side ed o be nes ed in o he p e ious T1 execu ion. I s()
is again ac i a ed om T2 and hen T1 is execu ed, his
loop will be ound in he CLS and i will be conside ed
ha a new i e a ion o his loop begins. In his case, loop
T2 is popped ou and is conside ed o be e mina ed. The
nex i e a ion o T2 will be conside ed as a di e en exe-
cu ion. No ice ha his is jus one possible way o classi y
loop i e a ions in o loop execu ions in he p esence o
ecu si e sub ou ines. Anyway, his e en a ely happens
and hus, i has a e y low in luence on he inal pe o -
mance.
Dynamic loop de ec ion is based on iden i ying back-
wa d con ol ans e ins uc ions. This means ha he i s
i e a ion o a loop execu ion is no de ec ed un il i has in-
ished. Thus, a loop is no conside ed un il he second i e a-
ion begins. In his way, igu e 2 depic s he i s i e a ion
o each loop execu ion in g ey because i is no de ec ed
wi h he p oposed mechanism.
When he CLS is ull and a new loop mus be pushed
on o i , he deepes en y is los . This policy ends o penal-
ize he ou e mos loops, which a e he leas common ones.
Howe e , as i is shown in sec ion 2.2.1, a ew en ies a e
enough o gua an ee no o e low o mos p og ams.
2.2.1 SPEC95 loop s a is ics. The p e ious mechanism
o de ec loops has been applied o ob ain s a is ics o he
SPEC95 benchma k sui e. The me hodology o collec
hese da a (and he es o da a p esen ed in he pape ) is
he ollowing. The benchma ks ha e been compiled using
he DEC Alpha compile wi h he ollowing op ions: -O5 -
une e 5 -mig a e -i o ( o C p og ams) and -O5 - une e 5
( o Fo an p og ams). They ha e been ins umen ed wi h
he a om ool [10] and un using he e e ence inpu da a,
excep o he gcc,ijpeg and pe l p og ams. Fo hese
p og ams, a single ile o he e e ence inpu da a has been
used.
Table 1 shows he numbe o ins uc ions (#ins /109),
he s a ic numbe o loops (#loops), he a e age numbe o
loop i e a ions pe loop execu ion (#i e /exec), he a e age
numbe o ins uc ions pe loop i e a ion (#ins /i e ), he
a e age nes ing le el (a g. nl) and he maximum nes ing
le el (max. nl). These igu es co espond o he whole exe-
cu ion o he p og ams.
2.3. Ga he ing loop in o ma ion
The abo e p esen ed CLS allows o de ec he s a and
he end o loop i e a ions and loop execu ions. Such in o -
ma ion can be used by a mul i h eaded p ocesso o c ea e
mul iple h eads o con ol, each one co esponding o a
di e en i e a ion o a loop. Howe e , in gene al such a
con ol specula ion app oach will equi e addi ional in o -
ma ion abou he loop i e a ions and he loop execu ions.
Fo ins ance, i can be use ul o know he numbe o i e a-
ions pe execu ion, o he li e-in egis e alues o each
i e a ion. The o me can be used o de e mine he numbe
o h eads ha a e o be c ea ed whe eas he la e can be
used o en o ce da a dependences among h eads. In gen-
e al, wo ypes o in o ma ion a e equi ed: one a he le el
o he loop i e a ion and he o he a he le el o he loop
execu ion. The pa icula in o ma ion o be s o ed depends
on he conc e e implemen a ion. In his subsec ion, we
desc ibe a gene al amewo k ha is common o any
implemen a ion.
The in o ma ion p e iously men ioned is s o ed by
means o wo ables (LET and LIT). The LET, which
s ands o Loop Execu ion Table, s o es in o ma ion abou
p e ious loop execu ions. The LIT, o Loop I e a ion
Table, is used o cha ac e ize he i e a ions o a loop.
These ables a e associa i ely sea ched, and e e y en y
is iden i ied by he same iden i ie o loops, ha is, he
loop a ge add ess T. En ies in bo h ables a e inse ed
when he execu ion o a loop s a s. We conside a LRU
eplacemen policy. Mo e conc e ely, he en y disca ded
in LIT co esponds o he loop ha has ini ia ed a new i e -
a ion leas ecen ly, while he en y disca ded in LET co -
esponds o he loop ha has ini ia ed a new execu ion
leas ecen ly.
Du ing he execu ion o he p og am, hese ables a e
#ins /
109
#loops #i e /
exec #ins /
i e a g.
nl max.
nl
applu 53.02 189 3.50 261.08 5.16 7
Table 1: Loop s a is ics.
apsi 33.06 207 10.75 229.34 3.14 5
comp ess 61.05 45 6.27 84.65 2.52 4
pppp 144.49 83 3.05 3217.80 6.66 9
gcc 1.93 1229 5.28 80.21 3.43 7
go 38.87 709 3.76 156.60 4.86 11
hyd o2d 50.57 291 29.37 127.66 3.50 4
ijpeg 40.98 198 20.75 336.26 6.37 9
li 70.77 94 3.48 107.80 5.15 10
m88ksim 79.19 127 9.38 39.82 1.98 5
mg id 102.81 142 28.93 512.68 4.93 6
pe l 30.66 147 3.11 47.02 1.35 5
su2co 40.23 213 51.23 257.17 3.50 5
swim 40.75 79 188.54 278.89 2.99 3
omca 32.05 91 57.18 224.82 3.01 4
u b3d 96.27 152 4.11 239.44 3.97 6
o ex 94.98 220 12.08 215.56 3.06 6
wa e5 35.69 195 56.15 164.25 3.12 5 accessed in o de o know he beha io o a gi en loop. In
his case, en ies in he ables a e di ec ly accessed h ough
poin e s ha a e s o ed in he CLS s ack. A NULL poin e
is used when he loop is no s o ed in he ela ed able.
Figu e 3 depic s he da a s uc u es used o dynamically
de ec loops (CLS) and o ga he in o ma ion abou hem
(LET and LIT). En ies in he CLS con ain he a ge and
b anch add esses o a loop ( ields T and B, espec i ely),
and he co esponding poin e s o LIT and LET ( ields
@LET and @LIT, espec i ely). En ies in he LIT and he
LET con ain ield T ( a ge loop add ess) and ield R (used
o implemen he LRU eplacemen policy). The es o he
ields in each able en y depend on he kind o in o ma-
ion ha i is decided o ga he om he loops o each pa -
icula mul i h eaded implemen a ion.
Ou ongoing wo k ocuses on using he LET o p edic
he numbe o i e a ions o each loop and o gene a e spec-
ula i e h eads acco dingly. In o de o implemen a s ide
p edic o , each LET en y con ains, in addi ion o he T
and R ields, he las i e a ion coun and he di e ence
be ween he p e ious wo coun s. The LIT is used o s o e
in o ma ion ela ed o he li e-in egis e s and memo y
loca ions o he las i e a ion o he loop. Fo each li e-in
egis e o memo y loca ion i s o es he alue a he
beginning o he las i e a ion and he las s ide, so ha
li e-in alues o u u e i e a ions can be p edic ed wi h a
s ide p edic o . Besides, o li e-in memo y loca ions i
s o es he las e ec i e add ess and he las s ide so ha
in e - h ead memo y ope a ions can be specula ed h ough
add ess p edic ion using a simila scheme as ha p oposed
in [4] o supe scala p ocesso s. In his way, h eads co -
T B @LET @LIT
CLS
op
# CLS en ies
TR . . .
TR . . .
# LET en ies
# LIT en ies
LET
LIT
Figu e 3: CLS, LET and LIT s uc u es.

esponding o di e en (maybe dependen ) i e a ions can
p oceed in pa allel, wi hou any synch oniza ion i he p e-
dic ed alues a e co ec .
2.3.1 Pe o mance. Depending on he pa icula
implemen a ion, he con en s o he LIT/LET a e use ul
a e se e al i e a ions/execu ions. Fo ins ance, o p edic
he numbe o i e a ions as he las numbe o i e a ions o
he same loop, only a p e ious execu ion is equi ed. On
he o he hand, i he p edic ion is based on a s ide
p edic o , wo execu ions a e equi ed o compu e a s ide.
To e alua e he pe o mance o he p oposed scheme, we
conside ha he con en s o he LIT/LET a e use ul a e
wo i e a ions/execu ions.
The pe o mance o his gene al mechanism o ga he
in o ma ion abou he loops is measu ed h ough LET and
LIT hi a ios. The LET hi a io measu es, when a new
execu ion o a loop is s a ed, whe he wo comple e exe-
cu ions o he same loop ha e been de ec ed since i was
s o ed in he able. The LIT hi a io measu es, when a
loop i e a ion s a s, whe he wo comple e i e a ions ha e
been de ec ed since i was s o ed in he able. This condi-
ion is no es ed o he i s i e a ion o all he execu ions
because he i s i e a ion is no de ec ed un il i inishes.
Figu e 4 shows he a e age LET and LIT hi a ios o
he whole SPEC95 benchma ks. The numbe o CLS
en ies is 16, which is enough o s o e he maximum num-
be o cu en loops (we ha e shown in able 1 ha he
maximum nes ing le el is lowe han 16). The numbe o
en ies o he LIT and LET is 2, 4, 8 and 16. A ade-o
be ween he space needed o he ables and he hi a io
could be o choose 4 en ies o he LIT (90.50% hi a io)
and 16 en ies o he LET (91.98% hi a io). I a la ge
quan i y o in o ma ion is s o ed in each able, a 2-en y
LIT and a 8-en y LET ha e also an accep able pe o -
mance (85.00% and 72.44% hi a ios, espec i ely).
2.3.2 Addi ional issues. When a new loop is execu ed,
he p oposed app oach always inse s a new en y in bo h
16842
0.0
20.0
40.0
60.0
80.0
100.0
a e age hi
LET
LIT
Figu e 4: LET and LIT hi a ios.
ables o ha loop. I may be con enien o disable he
ecogni ion o some loops by in oducing a new able
con aining hose po en ial loops ha a e no sui able o
specula ion. This able should be associa i ely accessed
be o e inse ing a new en y in he LET and he LIT. Fo
example, hose loops wi h a poo p edic ion a e may be
good candida es o s o e in his able. In his way, a loop
wi h mo e eliable in o ma ion is no elimina ed.
Taking in o accoun ha i is p e e able o s o e he
inne mos loops in on o he ou e mos , we ha e consid-
e ed an al e na i e eplacemen algo i hm ha inhibi s he
inse ion o a loop in he LIT and he LET when i implies
o elimina e a loop ha is nes ed in o i . This policy needs
o s o e o each loop, which o he loops a e nes ed in o i .
I has been e alua ed ha he imp o emen on he hi a io
is negligible wi h espec o he LRU algo i hm. This is so
because when he nes ing le el o loops is no highe han
he numbe o en ies o he LIT and LET, he beha io o
his policy is iden ical o LRU. We ha e shown ha he
a e age nes ing le el o loops in he SPEC95 is no e y
high. Thus, we ha e no conside ed any mo e his policy.
3. Con ol specula ion in mul i h eaded p o-
cesso s
In his sec ion we show how o apply he p e ious
scheme o dynamically gene a e h eads, ob ained om a
single sequen ial p og am, o a gene al mul i h eaded
a chi ec u e.
We conside a mul i h eaded a chi ec u al model con-
sis ing o se e al h ead uni s (TUs) which a e able, a
leas , o e ch and decode ins uc ions om di e en pa s
(o h eads) o he same sequen ial p og am. The es o
he ins uc ion s ages may be pe o med by ei he a epli-
ca ed o a sha ed se o unc ional uni s. The TUs o a mul-
i h eaded a chi ec u e can be in a non-specula i e,
specula i e o idle s a e. Ini ially, he e is one non-specula-
i e TU and he es o hem a e idle. When h ead con ol
specula ion is pe o med, some idle TUs change o he
specula i e s a e. All specula i e TUs main ain he o de
in which he associa ed h eads mus be execu ed inside
he sequen ial p og am. When a specula i e TU eaches i s
e mina ion poin , i wai s un il he non-specula i e TU
con i ms he con ol low o he execu ion, ha is, he
specula i e h ead becomes non-specula i e.
A pa icula implemen a ion o he mul i h eaded
model mus de ine h ee addi ional issues ega ding con-
ol specula ion:
• When in e - h ead con ol specula ion can be pe -
o med?
• Which a e he h eads o be specula ed?
• When he e i ica ion o a specula ion mus be done?
Fo ins ance, he mechanism de ined in [5] o he mul-
iscala p ocesso de ine hese 3 issues in he ollowing
manne . Specula ion can be done when a ask is ini ia ed.
No ice ha he esponsibili y o a ange he code in o asks
elies on he compile , unlike he app oach p oposed in
his pape . When a ask begins, i is p edic ed he ollow-
ing ask based on he ecen his o y. The e i ica ion o he
specula ion is pe o med when he ask ha p o oked he
specula ion inishes. In he scheme p oposed in his pape ,
all hese issues in ol ing h ead con ol specula ion a e
done en i ely by ha dwa e, based on loop de ec ion.
We de ine he concep o h ead-le el pa allelism
(TLP) o e e o he pa allel execu ion o h eads. Th ead-
le el pa allelism is measu ed h ough he a e age numbe
o ac i e and co ec ly specula ed h eads pe cycle (TPC).
The TPC is he main sou ce o addi ional pa allelism ha
can be p o ided by he no el con ol specula ion
app oach. In addi ion o he TPC, he inal amoun o pa -
allelism exploi ed by a pa icula implemen a ion will
depend on he app oach o deal wi h in e - h ead depen-
dences and in a- h ead pa allelism.
The po en ial TLP ha can be exploi ed i loops a e
au oma ically de ec ed is e y high. Figu e 5 p esen s he
TPC ha a h ead specula ion mechanism based on loop
de ec ion o an ideal machine wi h in ini e TUs can p o-
ide. This mechanism specula es only when he non-spec-
ula i e h ead de ec s a loop execu ion. The managemen
o da a dependences is an o hogonal issue wi h espec o
con ol specula ion ha will be conside ed in u u e wo k,
as ou lined in sec ion 2.3. Fo each p og am, he le ba
co esponds o he TPC when execu ing all ins uc ions,
whe eas he igh ba e lec s he execu ion o he i s 109
ins uc ions. I can be seen ha mos p og ams beha e
app oxima ely in he same way when execu ing only a
educed pa o i . In he es o he pape , igu es will only
e e o he educed pa o he p og am. I is impo an o
emphasize he po en ial la ge amoun o pa allelism ha
can be exploi ed wi h he loop de ec ion mechanism we
ha e p esen ed in he p e ious sec ion.
In he ollowing subsec ions we p opose a ealis ic
h ead con ol specula ion echnique and analyze i s
beha io .
3.1. Th ead con ol specula ion using dynamic
loop de ec ion
The h ead con ol specula ion ha we p opose in his
pape answe s he 3 issues desc ibed in he p e ious sec-
ion in he ollowing manne .
3.1.1 When specula ion is pe o med?. Whene e a
loop i e a ion s a s in he non-specula i e h ead. Only he
non-specula i e h ead can c ea e specula i e h eads.
3.1.2 Which h eads a e specula ed?. The answe o
his ques ion is he numbe o h eads ha a e specula ed
and hei iden i ica ion.
The specula ed h eads, i any, a e always consecu i e
i e a ions o he same loop ha has ini ia ed an i e a ion in
he non-specula i e TU. No e ha when an i e a ion o a
loop begins, ha loop is he inne mos , bu i may become
non-inne mos i o he loops a e de ec ed be o e he i e a-
ion o ha loop inishes. To p ese e he o de among
h eads, he iden i ie o he TU assigned o each specu-
la ed h ead is placed in he en y o he CLS associa ed o
he loop.
Wi h espec o he numbe o specula ed h eads we
ha e conside ed 3 policies:
• IDLE. The numbe o specula ed h eads is equal o
he numbe o idle TUs exis ing in ha momen .
• STR. The numbe o specula ed h eads is based on
he i e a ion coun o he las execu ion plus he s ide
be ween he las wo execu ions. I he s ide is eli-
able (a wo-bi sa u a ing coun e is used), he num-
be o specula ed h eads is he minimum be ween he
numbe o idle TUs and he numbe o p edic ed
emaining i e a ions o he cu en execu ion. I he
s ide is no eliable bu he numbe o i e a ions o
he las execu ion is known, i is used he same policy
bu p edic ing ha he i e a ions o he cu en execu-
ion will be he same as he las one. In case ha nei-
he he numbe o i e a ions no he s ide a e
known, any idle TUs is alloca ed o a u he i e a ion
o he same loop.
• STR(i). I is based on he las s a egy bu i adds a
pa ame e i, which co esponds o he maximum
numbe o non-specula ed loops ha can be nes ed
in o a loop ha is being specula ed. I his limi is
exceeded, all specula i e h eads co esponding o
he ou e mos loop a e squashed. In his way, idle
comp ess
m88ksim
swim
apsi
wa e5
omca
hyd o2d
u b3d
o ex
mg id
gcc
ijpeg
su2co
go
pppp
applu
li
pe l
1.0
10.0
100.0
1000.0
10000.0
100000.0
TPC
ALL ins .
1e9 ins .
Figu e 5: TPC o in ini e TUs.
TUs can be used o specula e in inne loops.
An impo an issue o any pa allel execu ion is load
balancing. The p oposed specula ion app oach allows o
simul aneous specula ion on se e al loops. In his case, he
specula i e h eads a e o de ed om inne mos o ou e -
mos (i.e., he non-specula i e h ead co esponds o an
i e a ion o he inne mos loop; he ollowing one co e-
sponds o he same loop o o an ou e loop and so on).
Since usually inne mos loops a e smalle han ou e mos
ones, i will a ely happen ha a h ead is s alled a he end
wai ing o he e mina ion o a p e ious h ead ha co e-
sponds o an inne loop. Besides, we ha e measu ed ha in
a e age abou 85% o he i e a ions o a loop ollow he
same con ol low (see sec ion 4). Thus, mos o he i e a-
ions will ha e he same amoun o ins uc ions and i will
a ely happen ha a h ead is s alled a he end wai ing o
he e mina ion o a p e ious one co esponding o he
same loop.
3.1.3 When e i ica ion is pe o med?. Ve i ica ion is
pe o med by he non-specula i e h ead when i s a s a
loop i e a ion o i inishes a loop execu ion.
When a loop i e a ion s a s, i is checked i an i e a ion
o he same loop had been specula ed. In his case, he
specula i e h ead associa ed o he i s specula ed i e a-
ion becomes he new non-specula i e h ead and he TU
associa ed o he cu en non-specula i e h ead becomes
idle. The new non-specula i e h ead upda es all global
da a s uc u es used o h ead specula ion (CLS, LIT and
LET).
When a loop execu ion inishes, all specula i e h eads
execu ing u he non-exis en i e a ions o he same loop
a e squashed. This co esponds o a con ol misspecula-
ion.
3.2. Pe o mance
The TPC (ac i e and co ec ly specula ed h eads pe
cycle) ob ained wi h hese specula ion policies has been
compu ed o he execu ion o he i s 109 ins uc ions o
all he p og ams in he SPEC95.
Figu e 6 shows he TPC o he STR specula ion policy.
The numbe o TUs is 2, 4, 8 and 16. Da a is shown o
e e y p og am o he SPEC95. No e ha he achie ed TPC
is conside able. Fo a small numbe o TUs, he p oposed
con ol specula ion app oach keeps hem busy mos o he
ime ( he a e age TPC o 2 and 4 TUs is 1.65 and 2.6
Figu e 6: TPC in he SPEC95 sui e o 2, 4, 8 and 16 TUs using he STR policy.
AVG
applu
apsi
comp ess
pppp
gcc
go
hyd o2d
ijpeg
li
m88ksim
mg id
pe l
su2co
swim
omca
u b3d
o ex
wa e5
5.0
10.0
15.0
16 h eads
AVG
applu
apsi
comp ess
pppp
gcc
go
hyd o2d
ijpeg
li
m88ksim
mg id
pe l
su2co
swim
omca
u b3d
o ex
wa e5
2.0
4.0
6.0
8.0
8 h eads
AVG
applu
apsi
comp ess
pppp
gcc
go
hyd o2d
ijpeg
li
m88ksim
mg id
pe l
su2co
swim
omca
u b3d
o ex
wa e5
1.0
2.0
3.0
4.0
4 h eads
AVG
applu
apsi
comp ess
pppp
gcc
go
hyd o2d
ijpeg
li
m88ksim
mg id
pe l
su2co
swim
omca
u b3d
o ex
wa e5
1.0
1.2
1.4
1.6
1.8
2 h eads
espec i ely). As he numbe o TUs inc eases, hei u ili-
za ion dec eases bu i is s ill accep able e en o 16 TU.
In his case, he a e age TPC is 6.2 bu se e al p og ams
achie e a TPC highe han 10. I is ema kable he high
e iciency o he mechanism o omca and wa e5. Fo
bo h p og ams, he maximum TPC is nea ly achie ed.
Mo eo e , igu e 7 compa es he di e en policies ha
ha e been desc ibed: IDLE, STR and STR(i), o i anging
om 1 o 3. The ba s show he TPC a e aged o all he
p og ams o he SPEC95. The STR policy beha es sligh ly
be e han he IDLE policy. The STR(i) policy beha es
wo se han STR, which is due o he highe numbe o co -
ec specula ions ha a e squashed. No ice ha in addi ion,
bo h policies di e in he selec ion o loops ha a e specu-
la ed. STR(i) a o s he specula ion o inne loops; he
lowe i is, he mo e a o ed he inne loops a e. In gene al,
inne loops ha e smalle g anula i y, which may be bene i-
cial when in e - h ead da a dependences a e conside ed.
Al hough his issue is beyond he scope o his pape , we
conside he STR(i) policy, and conc e ely STR(3), o be
e y a ac i e when da a dependences a e aken in o
accoun .
Finally, able 2 shows some igu es abou he STR(3)
specula ion algo i hm when he numbe o TUs is 4. The
columns a e he numbe o con ol specula ions pe o med
(#spec.); he a e age numbe o specula ed h eads pe
con ol specula ion (# h eads/spec.); he h ead con ol
specula ion hi a io (hi a io); he a e age numbe o
ins uc ions since a h ead is specula ed un il i is pe -
o med i s e i ica ion (#ins . o e i .); and he TPC.
No ice ha he hi a io is qui e high o mos p og ams,
which con i ms he accu acy o he con ol specula ion
app oach.
Figu e 7: TPC in he SPEC95 sui e o 2,
4, 8 and 16 TUs using IDLE, STR, STR(1),
STR(2) and STR(3) policies.
16
8
4
2
2.0
4.0
6.0
TPC
IDLE
STR
STR(1)
STR(2)
STR(3)
4. P elimina y da a specula ion s a is ics
The ocus o his pape is he p oposal o a con ol
specula ion mechanism o gene a e h eads om a sequen-
ial p og am. The managemen o in e - h ead depen-
dences is an ongoing wo k ha is ou lined in sec ion 2.3.
In his sec ion, we p esen some p elimina y s a is ics o
gi e a la o o he po en ial o such app oach.
We ha e i s iden i ied o each loop he di e en con-
ol lows ha i s i e a ions can ake. The sequence o
ins uc ions ha make up an i e a ion wi h a pa icula
con ol low is called a pa h. We ha e hen e alua ed ha
he mos equen pa h o each loop accoun s o 85% o
all he i e a ions in he SPEC95.
Fo hese i e a ions, we ha e measu ed i he con en s
o li e-in egis e s and memo y loca ions can be p edic ed
based on he alue compu ed in he las i e a ion o he
loop plus i s s ide ( ha is, he di e ence be ween he las
wo consecu i e i e a ions). Figu e 8 depic s he da a we
ha e ob ained. I con ains he pe cen age o i e a ions co -
e ed by he mos equen pa h (same pa h); he pe cen age
o co ec ly p edic ed li e-in egis e s (l p ed); he pe -
cen age o co ec ly p edic ed li e-in memo y loca ions
(lm p ed); he pe cen age o i e a ions wi h all hei li e-in
egis e s co ec ly p edic ed (all l ); he pe cen age o i e -
a ions wi h all hei li e-in memo y loca ions co ec ly
p edic ed (all lm); and he pe cen age o i e a ions wi h all
#spec. # h eads/
spec. hi a io
(%) #ins .
o e i TPC
applu 218661 2.62 54.51 2316 2.21
Table 2: Con ol specula ion s a is ics.
apsi 118637 2.91 90.48 2301 3.51
comp ess 2804450 2.69 100.00 91.94 3.23
pppp 3417 1.67 86.92 191727 2.71
gcc 1206937 2.06 76.05 370 2.37
go 18427 2.09 71.17 69749 1.06
hyd o2d 706635 2.99 99.43 433 2.52
ijpeg 150450 2.72 96.54 1608 2.36
li 1567433 1.71 69.16 353 1.75
m88ksim 1097194 2.77 97.32 292 2.78
mg id 7900 2.80 97.50 36523 3.71
pe l 3114338 2.33 60.34 35 1.17
su2co 4906331 2.22 99.92 45 1.94
swim 61005 3.00 99.91 4455 3.48
omca 111394 2.86 77.24 2363 3.85
u b3d 106237 2.99 99.18 2417 3.84
o ex 131024 2.12 90.25 2502 3.03
wa e5 165950 2.60 99.95 1778 3.75