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.