Software prefetching for software pipelined loops

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