High-level synthesis techniques for reducing the activity of functional units

High-le el syn hesis echniques o educing he ac i i y o unc ional uni s E. Musoll and J. Co adella Depa men o Compu e A chi ec u e Uni e si a Poli `ecnica de Ca alunya 08071-Ba celona,Spain Abs ac Decisions aken a he ea lies s eps o he design p ocess may ha e a signi ican impac on he cha ac e is ics o he inal imple- men a ion. This pape illus a es how powe consump ion issues can be ackled du ing high-le el syn hesis (high-le el ans o ma- ions, scheduling and binding). Se e al echniques pu suing low powe a e p oposed and he po en ial bene i s e alua ed. The commonidea behind hese echniquesis o educe he ac i - i y o he unc ional uni s (e.g. adde s, mul iplie s) by minimizing he changes o hei inpu ope ands. P elimina y e alua ions ob- ained om swi ch-le el simula ions show ha signi ican imp o e- men s can be achie ed. 1 In oduc ion Powe consump ion can be aken in o accoun a di e en le - els [5]: echnological, opological, a chi ec u al and algo i hmic le el. High-le el syn hesis (HLS) comp ises echniques a he a chi- ec u al and algo i hmic le el. T adi ionally, HLS has been applied o ob ain small and as designs. Bu li le has been done o include powe consump ion as one o he design pa ame e s o cons ain s. In his pape we p esen some HLS echniques o powe educ- ion bea ing in mind ha design decisions aken a he a chi ec u al and algo i hmic le el canha e a signi ican impac on he quali y o he inal implemen a ion. No me hods o implemen he echniques a e p esen ed. In o de o e alua e he e iciency o he echniques, powe -consump ion models de i ed om swi ch-le el simula ions o he basic unc ional uni s (e.g. adde s and mul iplie s) will be used. The p oposed echniques a emp o educe he ac i i y o he unc ional uni s by minimizing he changes o hei inpu ope ands. The pape is o ganized as ollows: in Sec ion 2 he p e ious wo k on high-le el echniques o low powe is b ie ly p esen ed. Sec ion 3 p esen s he powe -consump ion models o adde s and mul iplie s along wi h an in oduc ion o he p oposed echniques. Sec ions 4-8 desc ibe he echniques o powe educ ion. Sec ion 9 concludes he pape . 2 P e ious wo k Resea ch in low-powe ci cui s has been de o ed o he powe consump ion es ima ion o ela i ely small ci cui s [18, 8, 12, 22]. The design o a i hme ic ci cui s aiming a minimizing powe con- sump ion has been a ely add essed [3, 27, 10]. Mos o he e o s in HLS o low powe p opose models and es ima ions o powe consump ion a algo i hmic and a chi ec u al le el. In [15], a model ha accoun s o he andom beha io o he LSB bi s and he co ela ed beha io o he MSB bi s is p esen ed. In [1] he impac o he cache a chi ec u e in powe consump ion is s udied. In [19] a echnique o e alua e a lowe bound o he h oughpu and cos du ing algo i hm selec ion is in oduced. In [2] di e en p ocesso models ha accoun o he ene gy o he majo modes o compu a ion a e desc ibed. Few au ho s ha e add essed he se o ans o ma ions a algo- i hmic and a chi ec u al le el o ob ain lowe -powe designs. In [6] he powe consump iono addi ions and cons an mul iplica ions as a unc ion o he ope and ac i i y is s udied. F om his s udy, a da a lowg aph ans o ma ion is desc ibed o a ypical ope a ion in sig- nal p ocessing applica ions. In [26] some memo y ans o ma ions o low powe sys ems a e hin ed. The aim o hese ans o ma ions is o educe bo h he ac i i y o he add ess lines and he numbe o o -chip e e ences. In [4] he adi ional ans o ma ions o as e and smalle ci cui s a e applied in o de o e alua e he powe con- sump ion sa ings. Whene e he esul ing ci cui is as e han he equi ed h oughpu , powe -supply educ ion can be applied o ake ad an age o i s quad a ic impac on consump ion. 3 Powe consump ionmodelsandpowe educ ion echniques This sec ion desc ibes he powe -consump ion models used o e alua e he echniques p esen ed in he pape . A summa y o all he echniques is also included. 3.1 Powe consump ion models Powe consump ion has been conside ed only in he a i hme ic componen so heda a-pa handsimplepowe -consump ionmodels ha e been de i ed o each basic unc ional uni (adde , mul iplie ). Powe consump ion in he da a-pa h accoun s o a la ge ac ion o he o e all sys em powe budge . The ool used in he es ima ions is sls [24], a swi ch-le el simula o . The designs o he unc ional uni s a e based on lib a y cells. In hese models he numbe o ope ands ha emain unchanged wi h espec o hep e iousope a ionis aken in oaccoun . Figu e1 illus a es his concep o an 8  8 adix-4 Boo h mul iplie [13]. In Figu e 1(a), plo (3) ep esen s he ene gy o he mul iplie in nJ =ope a ion when one ope and emains unchanged (x axis) wi h espec o he p e ious ope a ion and he o he ope and a ies andomly1. Line (2) is he a e age o plo (3) and line (1) is he a e age ene gy when bo h ope ands a y andomly wi h espec o he p e ious ope a ion. Compa ing lines (1) and (2), he a e age powe consump ion o he mul iplie is app ox. 35% less when one ope and emains unchanged. 0 1 2 3 4 5 6 -128 -64 -32 0 32 64 127 nJ = op: Unchanged op e and 8  8-bi Radix-4 Boo h mul iplie (1) (2) (3) 7 O * Figu e 1: Plo (3) ep esen s he ene gy o he mul iplie when one ope and emains unchanged (x axis) wi h espec o he p e ious ope a ion and and he o he ope and a ies andomly. Line (2) is he a e age o plo (3) and line (1) is he a e age ene gy when bo h ope ands a y andomly. The echniques p oposed in his pape will use he no a ion in Table 1. Fac o  deno es he powe consump ion ela ion among he adde and mul iplie whe eas ac o s  add (  mul ) deno e he 1Al hough da a is co ela ed o some o he HLS applica ions, we ha e ound he andom dis ibu ion o be a good i app oxima ion. De ini i e e sion o eco d in he ACM Digi al Lib a y: h ps://dl.acm.o g/ci a ion.c m?id=224099 Pa ame e Desc ip ion 8-bi 12-bi 16-bi P add 2A g. consump ion o an adde 0.35 0.53 0.90 when bo h ope ands change nJ =op: nJ =op: nJ =op: P add 1A g. consump ion o an adde 0.26 0.4 0.70 when only one ope and changes nJ =op: nJ =op: nJ =op: P mul 2A g. consump ion o a mul iplie 5.7 13.68 28.9 when bo h ope ands change nJ =op: nJ =op: nJ =op: P mul 1A g. consump ion o a mul iplie 3.7 8.88 19.9 when only one ope and changes nJ =op: nJ =op: nJ =op:  add P add 1/ P add 20 : 74 0 : 75 0 : 77  mul P mul 1/ P mul 20 : 65 0 : 65 0 : 68  P add 2/ P mul 20 : 06 0 : 04 0 : 03 Table 1: No a ion used in he p esen ed echniques. The alues ha e been ob ained o 8, 12 and 16-bi -wide unc ional uni s. a io o powe in an adde (mul iplie ) be ween ope a ions wi h one and wo ope and changes wi h espec o he p e ious ope a ion. We ha e ound ha good es ima ions o he ac o s  add ,  mul and  a e0.75, 0.65 and0.04 espec i ely o 12-bi -wide unc ional uni s. In DSPapplica ions,a bi -wid h o 12is conside edaccu a ed enough. Fo example, he alue 0.65 o ac o  mul indica es ha he a e age powe consump ion o a mul iplica ion when one o i s ope ands emains unchangedwi h espec o he p e ious ope a ion is 35% less han when bo h ope ands change. Fac o s  add and  mul ha dly change wi h he bi -wid h o he ope ands. Al hough he alues o hese ac o s a e ealis ic enough, hey mus be de i ed o each cell-lib a y i mo e accu a e es ima ions a e pu sued. Al hough he models p esen ed a e simplis ic, hey p o ide an easyway o es ima e he powe consump ionin high-le el syn hesis. The au ho s a e cu en ly wo king in a mo e p ecise model based on no only he numbe o ope and changes, bu on he a iabili y o he bi -pa e n o he ope ands. Wi h his model, he co ela ion p esen ed in he da a is aken in o accoun . 3.2 Powe - educ ion echniques The echniques p oposed in his pape a e summa ized as ol- lows: loop in e change: akes ad an age o da a locali y o e- duce he ac i i y o he inpu s o he unc ional uni s; ope and eo de ing: seeks an app op ia e ope and o de o commu a i e ope a ions o educe he swi ching ac i i y; ope and sha ing: a - emp s o schedule and bind ope a ions o unc ional uni s in such a way ha he ac i i y o he inpu ope ands is educed; idle uni s: ies o minimize he useless powe consump ion o he idle uni s and ope and co ela ion: uses he in o ma ion o he co ela ion among he a iablesand cons an so he algo i hm in he scheduling and egis e -binding s eps. 4 Loop In e change The loop-in e change echnique has been adi ionally imple- men ed in compile s o ob ain dependency g aphs wi h a highe deg ee o pa allelism o o inc ease da a locali y and, hus, educe memo y a ic [26]. We apply loop in e change wi h he goal o minimizing he numbe o ope and changes on he unc ional uni inpu s. This echnique will be applied o he mo ion es ima ion algo i hm o image comp ession [17] (Figu e2(a)) o illus a e i s e iciency. 4.1 Applica ion o loop in e change In he algo i hm o Figu e2(a)weobse e h eeope a ionsin he inne loop: absolu e alue,addi ion andsub ac ion. Fo simplici y, we will conside a sub ac ion o be he sameas an addi ion in e ms o powe consump ion. The absolu e alue in 2’s complemen a i hme ic has wo s eps: (a) o check whe he he alue is nega i e and (b) complemen he numbe and add 1 in his case. The i s s ep ep esen s negligible con ibu ion o he o al powe consump ion: jus check i he MSB bi is one. In a e age, he second s ep will be execu ed hal o he imes. In he algo i hm o Figu e 2(a) we obse e also ha : (1) bo h ope ands o he accumula ion usually change wi h espec o he p e ious i e a ion o he algo i hm and (2) bo h ope ands o he sub ac ion inside he absolu e alue ope a o also change because bo h a e e ched om memo y in he inne loop (whe e he absolu e alue ope a ion is execu ed). I we use ins ead he algo i hm o Figu e 2(b), we ind ou ha : (1) he o al numbe o ope a ions emains he same (app ox. P  L  M  N addi ions, P  L  M  N sub ac ionsand ( P  L  M  N ) = 2 inc emen s), (2) bo h ope ands o he accumula ionalso change a each i e a ion and (3) now one ope and o he sub ac ion inside he absolu e alue ope a o emains he same du ing M  N i e a ions. Wi h he no a ion in Table 1, he powe consump iones ima ion o algo i hm (a) is oughly P a = P LM N ( 2 P add 2 + P abs 2 ) and he powe consump ion es ima ion o algo i hm (b) is P b = P LM N ( P add 2 + P add 1 + P abs 2 ) We ha e es ima ed by simula ion he a e age powe consump- ion o he inc emen ope a ion execu ed on an adde as P abs  0 : 45 P add 2. Thus, he es ima ed educ ion ac o on powe con- sump ion is R (  add ) = 1 ?  add 2 : 225 Wi h he alue o  add in Table 1 o 12-bi -wide unc ional uni s, we ob ain a educ ion o he powe consump ion o 11%. The powe consump ion has only been es ima ed o he unc- ional uni s o he da a-pa h. The inc ease in he con ol logic can educe he sa ings achie ed. Wi h algo i hm (b) he o -chip e e ence o de has changed, al hough he o al numbe emains he same. O cou se, a wise use o he local egis e s is expec ed in o de o minimize he o -chip e e ences. This is impo an pa icula ly in he mo ion es ima ion algo i hm,whe e heda awo king-se isconside ablyla ge. Ino de o minimize o -chip e e ences, he mos equen ly e e enced da a can be s o ed in an in e nal cache. This implies ha he algo i hm mus adap i s s uc u e o he size o his in e nal cache o p ope ly exploi da a locali y. 5 Ope and Reo de ing The goal o his echniqueis o indan app op ia e inpu ope and o de o commu a i e ope a ions in such a way ha swi ching ac i i y is educed. In o de o es ima e i s e iciency, his echnique will be applied o he he mul iply-accumula e (MAC) uni . 5.1 The MAC s uc u e Digi al il e s a e basic componen s in DSP sys ems. A ypical subs uc u e o a il e is he MAC s uc u e, which pe o ms he ope a ion P p ? 1 i = 0 x i y i , whe e p mul iplica ions and p ? 1 addi ions a e execu ed. One possible da a- low g aph (DFG) o he ope a ion is shown in Figu e 3(a). Th ee adde s and ou mul iplie s a e used o im- plemen he MAC uni . The e a e o he ways o eo ganize he addi ions, bu he balanced s uc u e o Figu e 3(a) implies less powe consump ion [4]. Figu e 3(b) shows a 4 h-o de LMS adap i e il e [23]. In he LMS il e , and in some o he digi al il e s (g.e. FIR and IIR il e s), he MAC s uc u e plays an impo an ole and, he e o e, minimizing i s powe consump ion will dec ease he o al powe consump ion o he il e . 5.2 Applica ion o ope and eo de ing Fo powe consump ionpu poses, heMAC uni isclassi iedin o h ee cases: (a) bo h he x and y alueschange om one i e a ion o he nex one ( he gene al case); (b) ei he x o y alues a e cons an and (c) ei he he x o y alues o i e a ion i a e he same as hose o i e a ion i ? 1 bu shi ed one posi ion. The IIR and FIR il e s ollow cases (b) and (c). In he LMS il e , he MAC uni ollows case (c). In o de o p opose a be e ope and eo de ing o cases (a) and (b), he ac i i y o he ope ands is aken in o accoun whe eas o g = 0 o d P m e ? 1 o h = 0 o d L n e ? 1 4 op imal ( g ; h ) = 1 o i = ?b M 2 c o b M ? 1 2 c o j = ?b N 2 c o b N ? 1 2 c 4 pa ( i; j ) = 0 o k = 0 o m ? 1 o l = 0 o n ? 1 C V = C F ( m  g + k ; n  h + l ) RV = RF ( m  g + i + k ; n  h + j + l ) 4 pa ( i; j ) = 4 pa ( i; j ) + j C V ? RV j i 4 pa ( i; j ) < 4 op imal ( g ; h ) hen 4 op imal ( g ; h ) = 4 pa ( i; j ) M V ( g ; h ) = [ i; j ] T (a) o i = ?b M 2 c o b M ? 1 2 c o j = ?b N 2 c o b N ? 1 2 c 4 pa ( i; j ) = 0 o g = 0 o d P m e ? 1 o h = 0 o d L n e ? 1 o k = 0 o m ? 1 o l = 0 o n ? 1 C V = C F ( m  g + k ; n  h + l ) o i = ?b M 2 c o b M ? 1 2 c o j = ?b N 2 c o b N ? 1 2 c RV = RF ( m  g + i + k ; n  h + j + l ) 4 pa ( i; j ) = 4 pa ( i; j ) + j C V ? RV j 4 op imal ( g ; h ) = 1 o i = ?b M 2 c o b M ? 1 2 c o j = ?b N 2 c o b N ? 1 2 c i 4 pa ( i; j ) < 4 op imal ( g ; h ) hen 4 op imal ( g ; h ) = 4 pa ( i; j ) M V ( g ; h ) = [ i; j ] T 4 pa ( i; j ) = 0 (b) Figu e 2: (a) Mo ion es ima ion algo i hm and (b) mo ion es ima ion algo i hm wi h wo loop in e changes. No a ion: P and L , bi -leng h and bi -wid h o he cu en image ame; M and N , maximum ho izon al and e ical ec o coo dina e; m and n , bi -leng h and bi -wid h o he cu en block; C V and RV , cu en and e e ence image ame alue; C F and RF , cu en and e e ence ame; M V ( g ; h ) , mo ion ec o o block ( g ; h ) . x0 x1 x2 x3y0 y1 y2 y3 ou 1 2 3 4 1 2 3mul iplie adde (a) x( ) h0 x( −1) h1 x( −2) x( −3) d( ) 2a h2 h3 y( ) sh0 sh1 sh2 sh3 add1 add2 e be bes0 bes1 bes2 bes3 1 2 3 4 1 2 3 4 5 6 7 8 9 MAC 5 6 7 8 (b) Figu e 3: (a) MAC s uc u e o p = 4 and (b) DFG o he 4 h-o de LMS adap i e il e . o case (c), he epe i ion o he ope ands will de e mine he new ope and eo de ing. Ope andac i i y ela es o he a iabili y o hebi -pa e n o one ope and om onei e a ion o he nex (powe consump ionis some- how ela ed o he Hamming dis ance o consecu i e bi -pa e ns). Ope and epe i ion ela es o he coa se-g ained a iabili y o he ope and, i.e. he ope and may o may no change be ween wo consecu i e i e a ions. Case(b) has been add essedin [6], and he conclusionis ha he minimum a e age ac i i y o e all nodes o he balanced MAC uni is ob ained when he cons an ope ands (e.g. he y alues) sa is y y 0  y 1      y n o y 0  y 1      y n . 5.2.1 Inpu eo de ing o case (c) As p e iously explained, ope and epe i ion will de e mine he new eo de ing. In heMACs uc u e o he LMS il e o Figu e3(b)we obse e ha all mul iplica ions ecei e di e en ope ands a each i e a ion: he x alues a e shi ed one posi ion o he le and he i s posi ion is he new ope and alue; he h alues a e ecalcula ed a each i e a ion and, he e o e, a e di e en . This ac is clea ly shown in Table 2 ( eo de ing A). Table 2 ( eo de ing B) shows a di e en ope and eo de ing ha akes ad an ageo he shi -wise beha io o he x alues. Wi h his new eo de ing, each mul iplie will ha e one ixed ope and ( he x alue) du ing ou consecu i e i e a ions. i e . eo de ing A M 0 M 1 M 2 M 3 i ( x ; h 0 ) ( x ? 1 ; h 1 ) ( x ? 2 ; h 2 ) ( x ? 3 ; h 3 ) i + 1 ( x + 1 ; h 0 ) ( x ; h 1 ) ( x ? 1 ; h 2 ) ( x ? 2 ; h 3 ) i + 2 ( x + 2 ; h 0 ) ( x + 1 ; h 1 ) ( x ; h 2 ) ( x ? 1 ; h 3 ) i + 3 ( x + 3 ; h 0 ) ( x + 2 ; h 1 ) ( x + 1 ; h 2 ) ( x ; h 3 ) i e . eo de ing B M 0 M 1 M 2 M 3 i ( x ; h 0 ) ( x ? 1 ; h 1 ) ( x ? 2 ; h 2 ) ( x ? 3 ; h 3 ) i + 1 ( x ; h 1 ) ( x ? 1 ; h 2 ) ( x ? 2 ; h 3 ) ( x + 1 ; h 0 ) i + 2 ( x ; h 2 ) ( x ? 1 ; h 3 ) ( x + 2 ; h 0 ) ( x + 1 ; h 1 ) i + 3 ( x ; h 3 ) ( x + 3 ; h 0 ) ( x + 2 ; h 1 ) ( x + 1 ; h 2 ) Table 2: Two di e en inpu eo de ing o he 4-inpu MAC uni . M i ep esen he mul iplica ions o he MAC uni . Using he no a ion in Table 1 he es ima ed powe consump ion o he MAC ope a ion wi h eo de ing A a e p i e a ions is P A (  ) = p ( p P mul 2 + ( p ? 1 ) P add 2 ) = p P mul 2 ( p +  ( p ? 1 )) and he es ima ed powe consump ion wi h eo de ing B a e p i e a ions is P B (  mul ;  ) = p ( p P mul 1 + ( p ? 1 ) P add 2 ) = = p P mul 2 ( p  mul +  ( p ? 1 )) Thus, he es ima ed powe -consump ion educ ion ac o om eo de ing A o B is R (  mul ;  ) = p ( 1 ?  mul ) p ( 1 +  ) ?   1 ?  mul 1 +  Wi h he alues in Table 1 o 12-bi -wide unc ional uni s, a 34% o powe -consump ion educ ion is achie ed. 6 Ope and Sha ing The ope and-sha ing echnique a emp s o schedule and bind ope a ions o unc ional uni s in such a way ha he ac i i y o he inpu ope ands is educed. Ope a ions sha ing he same ope anda e scheduled in con ol s eps as nea as possible. Thus, he po en ial o a unc ional uni o euse he same ope and alue (and, he e o e, o dec ease i s inpu ac i i y) is highe . This echnique is e icien when i is applied o a DFG wi h a iables used by mo e han one ope a ion. TheAR il e [14]willbeused oillus a e his echnique. The DFG o he AR il e is p esen ed in Figu e 4(a). Figu e 4(b) shows a possible schedule o he AR il e wi h wo adde s (one cycle) and one pipelined mul iplie ( wo cycles). We obse e he e a e some ope a ionswhose esul is he inpu o mo e a m inpu /ou pu a iablei/o addi ion a execu ed in adde uni mul iplica ion m execu ed in mul iplie uni 1 2 3 4 5 6 7 8 2 3 4 5 6 9 10 11 12 7 8 13 14 15 16 9 10 11 12 1 (a) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 3 5 4 1 7 8 9 11 10 2 12 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 cycle 16 7 8 1 10 2 9 11 12 14 3 13 15 4 (b) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 3 5 4 1 7 8 9 11 10 2 12 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 cycle 16 5 6 7 8 1 10 2 11 12 3 13 15 4 9 14 (c) 5 6 mul iplica ion addi ion Figu e 4: (a) DFG o he AR il e ; (b) one possible schedule and binding o (a) wi h one adde (one cycle) and one pipelined mul iplie ( wo cycles) and (c) imp o ed schedulewi h 4 achie ed OPRs. han one ope a ion ( hick lines in Figu e 4(a)). Fo example, he esul o addi ion 5 is inpu o mul iplica ions 10 and 11. Assume we schedule mul iplica ions 10 and 11 o he same uni U . Assume also ha be ween he execu ion o mul iplica ion 10 and 11 he e is no o he use o uni U . Then, one o he ope ands o uni U will no change om mul iplica ion 10 omul iplica ion 11. Hence o h, we will call ope and eu iliza ion (OPR) he ac ha an ope and is eused by wo ope a ions consecu i elyexecu ed in he same unc- ional uni . In Figu e 4(a), 4 mul iplica ion OPRs can be po en ially ob ained. An al e na i e schedule and uni binding is p esen ed in Fig- u e 4(c) wi h 4 achie ed OPRs. In he scheduleand uni binding o Figu e 4(b) no OPRs can be ob ained. Thus, hees ima edpowe consump iono onei e a ioninsched- ule (b) is P b (  ) = 12 P add 2 + 16 P mul 2 = P mul 2 ( 16 + 12  ) and hees ima edpowe consump iono onei e a ioninschedule (c) is P c (  mul ;  ) = 12 P add 2 + 12 P mul 2 + 4 P mul 1 = = P mul 2 ( 12 + 4  mul + 12  ) The es ima ed powe -consump ion educ ion is R (  mul ;  ) = 1 ?  mul 4 + 3  Wi h he alues in Table 1 o 12-bi -wide unc ional uni s, a 8.5% educ ion is achie ed. 6.1 Applica iono loopun olling o ope andsha - ing The ope and-sha ing echniqueis applied when someope a ions sha e he same ope and in he same i e a ion o he algo i hm. Bu i canalso be applied e en i ope ands eed mo e han one ope a ion in di e en i e a ions. We jus need o un oll he loop. The low-pass image il e [16] will be used o illus a e his echnique. A DFG o he low-pass image il e is shown in Figu e 5(b) 2. We see ha no OPR is possible. Bu i we un oll he inne loop 2Fo cla i y, he di ision o he sum by nine is omi ed and he inpu ope ands a e assumed o be in egis e s. wice ( he loop body con ains now h ee i e a ions), he DFG o Figu e 5(c) is ob ained, whe e some OPRs a e possible. Wi h one adde , he schedule o he DFG in Figu e 5(c) can be ob ained in 24 cycles and he one in 5(b) in 8. The e o e, he o al la ency o he algo i hm is he same in bo h schedules. All 9 OPRs a e achie ed. The es ima ed powe -consump ion educ ion is now R (  add ) = 3 8 ( 1 ?  add ) Wi h he alue o  add in Table 1 o a 12-bi -wid h adde , he educ ion ob ained is 9.4%. 6.2 Applica ion o he echnique o o he bench- ma ks Table 3 shows he esul s ob ained when applying he ope and- sha ing echnique o o he high-le el syn hesis benchma ks. Benchma k +/  FUs Red. 5 h-o de Wa e ille [9] 26/8 1  (2) / 2  (1) 12% 4 h-o de Daubechies il e [20] 12/12 1  (2) / 1  (1) 21% SHARF [23] 11/12 1  pipel. (2) / 2  (1) 10% 1-D 8-inpu Lee DCT [21] 29/13 2  (2) / 2  (1) 6% 1-D 8-inpu Chen DCT [21] 26/16 2  (2) / 2  (1) 19% 4  4ma ix mul iplie 4/8 2  (2) / 1  (1) 26% Table 3: Resul s ob ained by applying he inpu -sha ing echnique o e a wide ange o benchma ks. The numbe and ype o ope a ions, he numbe and ype o unc ionaluni s (FUs) used and he powe consump ion educ ion is shown. The numbe s in pa en hesis a e he la ency in cycleso he unc ional uni s. In all benchma ks excep o he Wa e il e , he esul s ha e been ob ained by compa ing he powe consump ion es ima ion o he schedule wi h ewes OPRs and he schedulewi h he la ges numbe o OPRs, ha ing bo h schedules he lowes possiblela ency. In he Wa e il e we ha e de ec ed a adeo be ween he speed and he consump ion o he inal design: i is possible o ob ain a design wi h mo e la ency bu also wi h mo e numbe o achie ed OPRs. 7 Idle uni s No all esou ces o a da a-pa h a e always used du ing all cy- cles. Some emain idle when no ope a ion is a ailable o hem. The echnique p esen ed he e ies o minimize he useless powe consump ion o he idle unc ional uni s. I is specially e icien o i = 0 o M o j = 0 o N ou = ( A [ i ? 1 ][ j ? 1 ]+ =  a 0  = A [ i ? 1 ][ j ]+ =  a 1  = A [ i ? 1 ][ j + 1 ]+ =  a 2  = A [ i ][ j ? 1 ]+ =  b 0  = A [ i ][ j ]+ =  b 1  = A [ i ][ j + 1 ]+ =  b 2  = A [ i + 1 ][ j ? 1 ]+ =  c 0  = A [ i + 1 ][ j ]+ =  c 1  = A [ i + 1 ][ j + 1 ]) = 9 =  c 2  = (a) + + + ++ +++ a0 a1a2 b0 b1 b2 c0 c1 c2 ou (b) + + + + ++ +++ + + + +++ + + + +++ + + + a0 a1a2a3a4 b0 b1b2b3b4 c0c1c2c3c4 ou 0 ou 1 ou 2 (c) Figu e 5: (a) Low-pass image il e algo i hm; (b) DFG o he inne loop o (a) and (c) DFG a e loop un olling. o spa se schedules. A schedule is said o be spa se i he uni u iliza ion is ela i ely low. Some app oaches o minimizing he useless powe consump ion o he idle uni s a e: (a) wi h a p ope egis e binding ha mini- mizes he ac i i y o he unc ionaluni s ( his echnique is add essed in Sec ion 8); (b) by wisely de ining he con ol signals o he mul- iplexo s du ing he idle cycles in such a way ha he changes a he inpu s o he unc ional uni s a e minimized ( his may esul in de ining some o he don’ ca e alues o he con ol signals) and (c) la ching he ope ands o hose uni s ha will be o en idle. In his sec ion, app oach (c) is e alua ed. I consis s o he inse ion o la ches a he inpu s o he unc ional uni s o s o e he ope ands only when he uni equi es hem. Thus, in hose cycles in which he uni is idle noconsump ionin p oduced. The con ol uni has o be edesigned acco dingly, in such a way ha inpu la ches become anspa en du ing hose cycles in which he co esponding unc ional uni mus execu e an ope a ion. This echnique has beene alua edwi h he 5 h-o de Wa e il e . Wi h an schedule wi h wo adde s (one cycle) and one mul iplie ( wo cycles) a inal la ency o 21 cycles has been ob ained. Du ing one i e a ion o he algo i hm, he adde s become idle du ing 16 cycles and he mul iplie becomes idle du ing 5 cycles. Wi h he no a ion in Table 1 he powe consump ion gene a ed by he idle uni s (useless consump ion) is P useless (  add ;  mul ;  ) = 16 P add 1 + 5 P mul 1 = = 16  add  + 5  mul and he powe consump iondue o heuse ulcalcula ions(use ul consump ion) is P use ul (  add ;  mul ;  ) = 20 P add 2 + 6 P add 1 + P mul 1 + 7 P mul 2 = = 20  + 6  add  +  mul + 7 The es ima ed educ ion in powe consump ion is R (  add ;  mul ;  ) = P useless P useless + P use ul = = 16  add  + 5  mul 22  add  + 14  mul + 20  + 7 Wi h he alues in Table 1 o 12-bi -wide unc ional uni s, a 21% educ ion is achie ed. Fo simplici y in he e alua ion (and o a oid syn hesizing e e y con ol uni ), we ha e assumed ha , in a e age, only one o he ope ands changes in each idle uni a each cycle. This assump ionmay be op imis ic o pessimis ic depending on he inal implemen a ion. E icien la ches (bo h in a ea and powe ) a e in eg a ed using Clocked CMOS ga es (C2MOS [25]) in he ope and-selec ionmul- iplexe s. 8 Ope and Co ela ion In he echniques p e iously p esen ed, he main idea was o maximize he ope and locali y o , in o he wo ds, he ope and ep- e i ion in he unc ional uni s. The ope and-co ela ion echnique akes in o accoun he ope and ac i i y 3. This echnique uses he in o ma ion o he co ela ion among he a iables and cons an s o he algo i hm in he schedulingand egis e -binding s eps. We will show how he ac i i y o he inpu ope ands a ec he powe consump ion o he design. Two examples will be p esen ed o illus a e his echnique: a low-powe schedule o he ini e impulse esponse il e (FIR il e ) [23] and a low-powe egis e binding o he Di e en ial Equa ion Sol e [11]. 8.1 Inpu ope and ac i i y and i s e ec in powe consump ion The e a e algo i hms ha p esen co ela ion among hei a i- ables and cons an s. A high co ela ion be ween wo a iables does no imply a low ac i i y be ween hem; o example, in he exp es- sion x = 2 y ? 1bo h a iables x and y a e highly co ela ed bu i y always akes he alue 010101 o 101010, hen he A e age Hamming Dis ance (AHD) be ween x and y is maximum (6). Thus, a p o iling o he algo i hm o be syn hesized is needed in o de o de e mine he ac i i y (measu ed wi h he AHD) among i s a iables and cons an s. As an example, le us conside he leas -mean squa e adap i e il e (LMS il e ) [23] o Figu e 3(b). Two expe imen s ha e been pe o med: in expe imen A one o he inpu signals o he LMS il e is andom; in expe imen B he inpu is a wa e o m calcula ed as he sum o wo sines. In bo h expe imen s, he second inpu signal has a iangula shape and he ope a ion equency is 0.5 kHz. The AHD among he a iables assuming 12-bi ope ands ha e been ob ained. When wo a iables ha e no co ela ion a all, hei AHD is 6. Expe imen A implies ha he a iables x ( ) o x ( ? 3 ) ha e an AHD o 6 among hem, whe eas in B he AHD educes o 3.5 because o he smoo he ansi ion be ween one inpu da a and he nex one. This di e ence in he AHD a ec s he powe consump ion o he il e . A e simula ions wi h sls [7] we ha e obse ed ha expe imen B is 22.6% less powe consuming han expe imen A. The di e ence in powe consump ion ob ained is only p oduced by he inpu da a pa e n. This di e ence inc eases wi h he sam- pling equency. Wi h a highe sampling equency, he inpu da ain expe imen B is smoo he han wi h a lowe one. A highe sampling equency implies a lowe AHD in he inpu da a 4. The design is he same in bo h expe imen s and i has been scheduled wi h one adde (one cycle) and wo mul iplie s ( wo cycles). A simila expe imen has beenpe o med wi h he 4 h-o de FIR il e . A 7% powe -consump ion educ ion has been obse ed. 8.2 Example 1: scheduling o he FIR il e A FIR il e ollows he equa ion P p ? 1 i = 0 x i c i whe e c i a e cons an s. When speed is no a majo issue, a signi ican educ ion in ha d- wa e complexi y is achie ed by pe o ming mul iplica ions o e se e alclock cycles as a se ies o shi -add ope a ions. When speed is impo an , he mul iplica ions mus be execu ed by mul iplie s. We will ocuson hiscaseand will showhowa di e en mul iplica- ionexecu iono de canin luenceo e he inalpowe consump ion. As an example, assume p = 4, he alues -1870, 1867, -740 and -1804 o he cons an s c 0 o c 3and a bi -wid h o 12. Assume also ha he inpu da a is a wa e o m calcula ed as a sum o wo sines. I his 4-o de FIR il e is scheduledwi h one mul iplie and one adde , di e en minimum-la ency schedules a e possible wi h di e en mul iplica ion execu ion o de . In one o hose schedules, he mul iplie obse es he ollowing changesin one o i s ope ands (numbe son hea owsindica e heAHDbe weencons an s): c 010 ! c 17 ! c 26 ! c 33 ! c 010 !    whe eas in ano he schedule, i may obse e he ollowing changes: c 010 ! c 111 ! c 36 ! c 27 ! c 010 !    . 3See Sec ion 5 o he de ini ion o ope and epe i ion and ope and ac i i y. 4The powe consump ion is calcula ed as he ene gy pe i e a ion o he algo i hm. Indeed, i we double he ope a ion equency, he o e all powe consump ion is also doubled,bu no he ene gy pe i e a ion. By means o swi ch-le el simula ions, he calcula edpowe con- sump ion o he unc ional uni s associa ed o he i s schedule is 6.3% less han he one associa ed o he second. This educ ion has been achie ed only wi h he change o he schedule o wo ope a ions. 8.3 Example 2: egis e binding o he Di e en- ial Equa ion Sol e The expe imen s done in Sec ion 8.1 o he LMS il e o Fig- u e 3(b) showed ha he AHD among he a iables h i is lowe han among he o he a iables. The same occu s o x ( ? i ) , sh i , bes i and add i . This in o ma ion can be used in egis e -binding algo i hms o ob ain a egis e se whe e ac i i y o indi idual egis e s is mini- mized. As a side e ec , hose idle uni s ha obse e he changes in he egis e s will also educe i s consump ion. Fu he mo e, he ope and-co ela ion in o ma ion along wi h he commu a i e p op- e y o some ope a ions can be used also o dec ease he powe consump ion in he non-idle unc ional uni s by swapping hei ope ands. The Di e en ial Equa ion Sol e has been scheduled wi h one adde (one cycle) and wo mul iplie s ( wo cycles). The AHD be ween all pai s o a iables has been ob ained by means o sim- ula ions o he algo i hm wi h di e en inpu da a. The inal AHD used has been ob ained as he a e age o all simula ions. Two di e en egis e bindings (A and B) ha e been ob ained. Bo h bindings use 5 egis e s. The educ ion o he egis e ac i i y o binding B p oduces an a e age powe sa ings o 7.5% in he unc ional uni s wi h espec o A. This is ob ained by he educ ion o he ope and ac i i y a he inpu s o he unc ional uni s du ing he idle cycles. In ui i ely, powe consump ion can be u he educed by in- c easing he numbe o egis e s (i.e., he e exis s a powe -a ea adeo ). The wo s case, in e ms o a ea, is o alloca e one eg- is e o each a iable. In his case, he idle uni s will ha e almos no ope and changes on hei inpu s. Bu inc easing he numbe o egis e s also inc eases he numbe o con ol signals, implying a mo e complica ed con ol logic and in e connec ion, which may hen o se he powe sa ings achie ed in he unc ional uni s. 9 Conclusions The use o high-le el syn hesis echniques o low powe can ha e a signi ican impac on he esul ing implemen a ions. In his pape ,se e als a egies o ackle he p oblemo powe consump ion a high le el ha e been p esen ed. The po en ial bene i s ha e been e alua ed in di e en examples o DSP. All echniques ocus on he minimiza ion o he ac i i y o he unc ional uni s by p ope ly selec ing he ope ands used a each cycle. The p omising esul s ob ained om he p elimina y es ima ions should endo se u he esea ch on his a ea. Fo hcoming e o s mus be de o ed o au oma e hese echniquesand inco po a e hem in o syn hesis sys ems. The au ho s o he pape a e cu en ly pu suing his goal. Acknowledgmen s We a e indeb ed o P o . Tom´as Lang o insigh discussions and help ul commen s on his pape . This wo k has been pa ially suppo ed by CICYT TIC94-0531- E and Dep . d’Ensenyamen de la Gene ali a de Ca alunya. Re e ences [1] J. Bunda, W. A has, and D. Fussell. E alua ing powe impli- ca ions o CMOS mic op ocesso design decisions. In P oc. In . Wo kshop on Low Powe Design, pages 147–152, Ap . 1994. [2] T. Bu d and R. B o he sen. Ene gy e icien CMOS mic o- p ocesso design. In P oc. 28 h Hawaii In . Con . on Sys em Sciences,Jan. 1995. [3] T. Callaway and E. Swa zlande . Es ima ing he powe con- sump ion o CMOS adde s. In P oc. o he Cus omIn eg a ed Ci cui Con ., pages 210–216, 1993. [4] A. Chand akasan,M. Po konjak, J.Rabaey, andR. B ode sen. HYPER-LP: A sys em o powe minimiza ion usinga chi ec- u al ans o ma ions. IEEE T ans. on CAD, pages 300–303, No . 1992. [5] A. Chand akasan, S. Sheng, and R. B ode ssen. Low powe CMOS digi al design. IEEE T ans. on SSC, 27(4):473–483, Ap . 1992. [6] A. Cha e jee and R. Roy. Syn hesis o low powe linea DSP ci cui s using ac i i y me ics. In P oc. o he In . Con . on VLSI Design, pages 265–270,Jan. 1994. [7] A.deG aa andA. anGende en.SLS:Swi ch-le elsimula o use ’s manual. Technical epo , Del Uni . o Tech., 1987. [8] S. De adas, K. Keu ze , and J. Whi e. Es ima ion o powe dissipa ion in CMOS combina ional ci cui s using boolean unc ion manipula ion. IEEE T ans.on CAD, 11(3):373–383, Ma . 1992. [9] P. Dewilde, E. Dep e e e, and R. Nou a. Pa allel and pipelined VLSI implemen a ion o signal p ocessing algo- i hms, chap e 15, pages 257–264. VLSI and Mode n Signal P ocessing. P en ice-Hall, Inglewood Cli s, NJ, 1985. [10] M.E cego acandT.Lang.Reducing ansi ioncoun sina i h- me ic ci cui s. In P oc. In . Symp. on Low Powe Elec onics, pages 64–65, Oc . 1994. [11] D. Gajski, N. Du , A. Wu, and S. Lin. High-le el syn hesis: in oduc ion o Chip and Sys em Design. Kluwe Academic Publishe s, 1992. [12] A. Ghosh, S. De adas, K. Keu ze , and J. Whi e. Es ima ion o a e age swi ching ac i i y in combina ional and sequen ial ci cui s. In P oc. DAC, pages 253–259, 1992. [13] I. Ko en. Compu e A i hme ic Algo i hms. P en ice-Hall, 1993. [14] S. Kung. On supe compu ing wi h sys olic/wa e on a ay p ocesso . In P oc. o he IEEE, pages 867–884, July 1984. [15] P. Landman and J. Rabaey. Black-box capaci ancemodels o a chi ec u al powe analysis. In P oc. In . Wo kshop on Low Powe Design, pages 165–170,Ap . 1994. [16] J.Lim. Two-Dimen ionalSignalandImageP ocessing.Signal P ocessing Se ies. P en ice-Hall, 1990. [17] C. Lin and S. Kwa a. An adap i e algo i hm o mo ion compensa edcolou image coding. IEEE Globecom, 1984. [18] F. Najm. T ansi ion densi y, a s ochas ic measu e o ac i i y in digi al ci cui s. In P oc. DAC, pages 644–649, 1991. [19] M. Po konjakandJ. Rabaey. Algo i hm selec ion: A quan i a- i e compu a ion-in ensi i e op imiza ion app oach. In P oc. o he IEEE In . Con . on Compu e Aided Design, pages 90– 95, 1994. [20] W.P ess,S.Teukolsky,W.Ve e ling, andB.Flanne y.Nume - ical Recipesin C: The A o Scien i icCompu ing. Camb idge Uni e si y P ess, second edi ion, 1992. [21] K. Rao and P. Yip. Disc e e Cosine T ans o m. Academic P ess, 1990. [22] A. Shen, A. Ghosh, S. De adas, and K. Keu ze . On a e age powe dissipa ion and andom pa e n es abili y o CMOS combina ional logic ne wo ks. In P oc. o he IEEE In . Con . on Compu e Aided Design, 1992. [23] J. T eichle , C. Johnson, J ., and M. La imo e. Theo y and Design o Adap i e Fil e s. New Yo k: John Wiley & Sons, 1987. [24] A. an Ge enden. SLS: An e icien swi ch-le el iming sim- ula o using min-max ol age wa e o ms. In P oc. VLSI 89 Con ., pages 79–88, Aug. 1989. [25] N. Wes e and Esh agian. P inciples o CMOS VLSI Design: A sys ems Pe spec i e. Addison-Wesley, 1988. [26] S. Wuy ack, F. Ca hoo , F. F anseen, L. Nach e gaele, and H. D. Man. Global communica ions and memo y op imizing ans o ma ions o low powe . In P oc. In . Wo kshopon Low Powe Design, pages 203–208,Ap . 1994. [27] K.Yano, T. Yamanaka,T.Nishida, M. Sai o,K.Shimohigashi, and A. Shimizu. A 3.8-ns CMOS 16x16-b mul iplie using complemen a y pass- ansis o logic. IEEE JSSC, 25(2):388– 395, Ap . 1990.