Abs ac
This pape in es iga es he in e ac ion be ween so wa e
pipelining and di e en so wa e p e e ching echniques
o VLIW machines. I is shown ha p ocesso s alls due o
memo y dependences ha e a g ea impac in o execu ion
ime. A no el heu is ic is p oposed and i is show o ou pe -
o m p e ious p oposals.
1. In oduc ion
So wa e pipelining ep esen s a amily o loop sched-
uling echniques ha ies o exploi ILP by execu ing in
pa allel consecu i e i e a ions o a loop. The mos popula
scheme is called modulo scheduling, and i consis s o ind-
ing a ixed pa e n o ope a ions (o leng h II o ini ia ion
in e al) om dis inc i e a ions([3]).
Se e al schemes ha e been p oposed in he li e a u e
wi h he goal o minimize he II and/o egis e p essu e,
bu none o hem has e alua ed he e ec o memo y. When
so wa e pipelining is applied in VLIW a chi ec u es,
whe e ins uc ion la encies and scheduling a e ixed a
compile- ime, execu ion ime can be highly deg aded due
o he s all ime p o oked by dependences wi h memo y
ins uc ions. E en i a nonblocking cache is used, ue
dependences wi h p e ious memo y ope a ions a a nea
dis ance1 can make he p ocesso o s all a e wa ds. The
choice o scheduling all loads using he cache-miss la ency
equi es conside able ILP and inc eases egis e p es-
su e([1]).
Di e en echniques o imp o e memo y beha io
exis and a e well-known, and so wa e p e e ching is one
o hem. The main idea o his me hod is o b ing o cache
he da a ha will be used in a nea u u e([2]).
In his pape we in es iga e he in e ac ions be ween
so wa e pipelining and so wa e p e e ching in a VLIW
a chi ec u e. Some al e na i es o pe o m so wa e
p e e ching a e desc ibed, and a no el heu is ic is p e-
sen ed. An e alua ion in execu ion ime e ms is epo ed as
well as some conclusions.
1.Almos all modulo scheduling schemes use a ixed cache-hi
la ency o all memo y ope a ions
2. So wa e p e e ching schemes
So wa e p e e ching is an e ec i e echnique o ole -
a e memo y la ency. When i is used wi h a nonblocking
cache, his echnique allows he p ocesso o hide pa o all
he memo y la ency by o e lapping he e ch o da a and
he compu a ion.
So wa e p e e ching can be pe o med h ough wo
al e na i e schemes: binding and nonbinding p e e ching.
The i s al e na i e, also known as ea ly scheduling o
memo y ope a ions, mo es memo y ins uc ions away
om hose ins uc ions ha depend on hem. The second
al e na i e in oduces in he code special ins uc ions,
which a e called p e e ch ins uc ions. These a e non aul -
ing ins uc ions ha pe o m a cache lookup bu do no
modi y any egis e .
In he s udy p esen ed in his pape we ha e e alua ed
wo echniques o binding p e e ching:
•Ea ly scheduling always (ESA): all memo y ope a-
ions o he loop a e scheduled using cache-miss
la ency.
•Ea ly scheduling acco ding o locali y (ESL): sched-
ule ins uc ions ha ha e some ype o locali y using
he cache-hi la ency and schedule he emaining ones
using he cache-miss la ency.
We ha e also e alua ed h ee dis inc schemes o
inse ing p e e ch ins uc ions (nonbinding p e e ch):
•Inse p e e ch always (IPA): inse a p e e ch ins uc-
ion o e e y memo y ope a ion.
•Inse p e e ch acco ding o empo al locali y (IPT):
inse p e e ch o hose e e ences wi hou empo al
locali y e en i hey exhibi spa ial locali y.
•Inse p e e ch acco ding o locali y (IPL): inse
p e e ch o hose ins uc ions wi hou any ype o
locali y.
3. A no el so wa e p e e ching echnique
The p oposed so wa e p e e ching scheme is called
cache sensi i e modulo scheduling (CSMS), and i ies o
minimize bo h he compu e ime and he s all ime. These
e ms a e no independen and educing one o hem may
So wa e P e e ching o So wa e Pipelined Loops
F. Jesús Sánchez and An onio González
Depa men o Compu e A chi ec u e
Uni e si a Poli ècnica de Ca alunya
Campus No d - c./ Jo di Gi ona, 1-3 - Mòdul D6
08034 - Ba celona (SPAIN)
E-mail: { an,an onio}@ac.upc.es
1060-3425/98 $10.00 (c) 1998 IEEE
esul in an inc ease in he o he . The p oposed algo i hm
ies o ind he bes ade-o be ween he wo e ms.
The CSMS algo i hm is based on ea ly scheduling o
some selec i ely chosen memo y ope a ions. Scheduling a
memo y ope a ion using he cache-miss la ency can hide
almos all memo y la ency wi hou inc easing much he
numbe o ins uc ions (as opposed o he use o p e e ch
ins uc ions). Howe e , i can inc ease he execu ion ime
in h ee ways:
• I may inc ease he egis e p essu e, and he e o e, i
may inc ease he II due o spill code.
• I may inc ease II ec because he la ency o memo y
ope a ions is augmen ed.
• I may inc ease he SC (s age coun e ) because he
leng h o indi idual loop i e a ions may be inc eased.
Two o he main issues o he CSMS algo i hm is he
educ ion o he impac o ecu ences on he II and he
minimiza ion o he s all ime. The p oblem o he cos o
he p olog and epilog is handled by compu ing wo al e na-
i e schedules. Bo h ocus on minimizing he s all ime and
he II. Howe e , one o hem educes he impac o he p o-
log and he epilog a he expense o an inc ease in he s all
ime whe eas he o he does no ca e abou he p olog and
epilog cos . Then, depending on he numbe o i e a ions o
he loop, he mos e ec i e one is chosen.
The algo i hm consis s o c ea ing wo dependence
g aphs, one using he cache-miss la ency o scheduling
each memo y ope a ion, and ano he one using cache-miss
o hi la ency acco ding o a s a ic locali y analysis. The
e ec o ecu ences ha limi de ini ia ion in e al is
educed by changing, om cache-miss o cache-hi , he
la ency o some memo y ope a ions ( ollowing a locali y
o de ) un il his ecu ence minimizes he II. An uppe
bound in he numbe o i e a ions o he loop help us o
choose be ween he scheduling o bo h g aphs.
Mo e de ails abou he CSMS algo i hm a e epo ed
in [4].
4. Some pe o mance esul s
The pe o mance o he so wa e p e e ching schemes
has been s udied o some SPEC p95 benhma ks, and o
wo VLIW a chi ec u es: simple (4-issue and he cache-
miss la ency is 10 cycles) and agg essi e (8-issue and he
cache-miss la ency is 20 cycles).
In addi ion o he abo e-men ioned schemes,we ha e
measu ed he scheduling using cache-hi la ency always
(CHL) and a lowe bound o he execu ion ime (LBND).
In Figu e 1 esul s a e p esen ed. Black ba s ep esen s
s all ime, and g ey ba ep esen s compu e ime, all o
hem no malized o CHL. I is show ha he CSMS scheme
achie es he bes ade-o be ween s all and compu e ime,
and i s pe o mance is close o he lowe bound.
5. Conclusions
In his pape we ha e compa ed he e ec ha some
so wa e p e e ching echniques ha e in so wa e pipelined
loops o VLIW a chi ec u es. We ha e seen ha he p o-
posed CSMS scheme signi ically ou pe o ms p e ious p o-
posals.
Re e ences
[1] S.G. Ab aham, R.A. Suguma , B.R. Rau and R. Gup a, “P e-
dic abili y o Load/S o e Ins uc ion La encies”, in P ocs. o
26 h In . Symp. on Mic oa chi ec u e, pp. 129-152, Dec. 1993
[2] D. Callahan, K. Kennedy and A. Po e ield, “So wa e
P e e ching”, in P ocs o he IV Symp. on A ch. Suppo o
P og. Lang. and Ope . Sys . (ASPLOS), pp. 40-52, Ap il 1991
[3] M.S. Lam, “So wa e Pipelining: an E ec i e Scheduling
Technique o VLIW Machines”, in P ocs. o Con . on P og.
Lang. Desing and Impl. (PLDI), pp. 43-53, May 1991
[4] F.J. Sánchez and A. González, “Cache Sensi i e Modulo
Scheduling”, in P ocs. o 30 h In . Symp. on Mic oa chi ec-
u e, Dec. 1997
CHL
ESA
ESL
IPA
IPT
IPL
CSMS
LBND
CHL
ESA
ESL
IPA
IPT
IPL
CSMS
LBND
CHL
ESA
ESL
IPA
IPT
IPL
CSMS
LBND
CHL
ESA
ESL
IPA
IPT
IPL
CSMS
LBND
CHL
ESA
ESL
IPA
IPT
IPL
CSMS
LBND
CHL
ESA
ESL
IPA
IPT
IPL
CSMS
LBND
0.0
0.2
0.4
0.6
0.8
1.0
No malized Loop Execu ion Time
omca swim su2co hyd o2d mg id u b3d
Simple a chi ec u e
1.593
1.371
CHL
ESA
ESL
IPA
IPT
IPL
CSMS
LBND
CHL
ESA
ESL
IPA
IPT
IPL
CSMS
LBND
CHL
ESA
ESL
IPA
IPT
IPL
CSMS
LBND
CHL
ESA
ESL
IPA
IPT
IPL
CSMS
LBND
CHL
ESA
ESL
IPA
IPT
IPL
CSMS
LBND
CHL
ESA
ESL
IPA
IPT
IPL
CSMS
LBND
0.0
0.2
0.4
0.6
0.8
1.0
No malized Loop Execu ion Time
omca swim su2co hyd o2d mg id u b3d
Agg essi e a chi ec u e
1.257
3.618
3.034
Figu e 1. So wa e p e e ching schemes pe o mance
1060-3425/98 $10.00 (c) 1998 IEEE