econ posi ion and Technology Mapping
o
Speed-Independen
Ci cui s Using Boolean Rela ions*
Jo di Co adella, Uni . Poli knica de Ca alunya, Ba celona, Spain
Michael Kishine sky, Alex Kond a ye , The Uni e si y
o
Aizu, Japan
Lucian0 La agno, Poli ecnico di To ino, I aly
En ic Pas o , Uni . Poli kcnica de Ca alunya, Ba celona, Spain
Alex Yako le , Uni e si y
o
Newcas le upon Tyne, Uni ed Kingdom
Abs ac
This pape p esen s a new echnique o decomposi ion and ech-
nology mapping
o
speed-independen ci cui s. An ini ial ci cui
implemen a ion is ob ained in he o m o a ne lis o
complex
ga es,
which may
no
be a ailable in he design lib a y. The p o-
posed me hod i e a i ely pe o ms
Boolean decomposi ion
o
each
such ga e
F
in o a wo-inpu combina ional o sequen ial ga e
G
a ailable in he lib a y and wo ga es
HI
and
H2
simple han
F,
while p ese ing he o iginal beha io and speed-independence
o he ci cui .
To
ex ac unc ions o
H1
and
H2
he me hod
uses
Boolean ela ions,
as opposed o he less powe ul algeb aic
ac o iza ion app oach used in p e ious me hods. A e logic de-
composi ion, he o e all lib a y ma ching and op imiza ion is ca -
ied
ou .
Logic esyn hesis, pe o med a e speed-independen
signal inse ion o
HI
and
Hz,
allows o sha ing o decomposed
logic. O e all, his me hod is mo e gene al han he exis ing
echniques based
on
es ic ed decomposi ion a chi ec u es, and
he eby leads o be e esul s in echnology mapping.
1
In oduc ion
Speed-independen
ci cui s a e.
haza d- ee unde he unbounded
ga e delay model.
[4,9,
61
p o ide gene al condi ions o logic
implemen abili y o speci ica ions in o
complex ga es.
The la e
a e allowed o ha e an a bi m y anin.
To achie e g ea e p ac icali y mo e ecen wo k has been o-
cused
on
he de elopmen o logic decomposi ion echniques. I
alls in o wo ca ego ies. One o hem a emp s o achie e logic de-
composi ion h ough he use o
s anda d a chi ec u es.
The o he
g oup comp ises wo k a ge ing he decomposi ion o complex
ga es di ec ly, by inding a beha io -p ese ing in e connec ion
o simple ga es. In bo h cases, he majo unc ional issue, in
addi ion o logic simpli ica ion, is ha he decomposedlogic mus
no iola e he o iginal
speed-independen specijica ion.
Two examples o he i s ca ego y a e
[l,
81.
The basic ci cui
a chi ec u e includes
C
elemen s (ac ing as la ches) and combina-
ional logic. This logic is assumed o consis o
AND
ga es wi h
po en ially unbounded ain and unlimi ed inpu in e sions and
bounded anin
OR
ga es.
Mono onic Co e
(MC) equi emen s
ensu e implemen abili y o a speci ica ion in his “s anda d-C” a -
chi ec u e and ha e an in ui i e objec i e o making he i s le el
(AND)
ga es wo k in a
one-ho
ashion wi h acknowledgmen
h ough one o he C-elemen s. Following his app oach, me h-
ods o speed-independen decomposi ion in o
implemen able
li-
b a ies ha e been de eloped. E.g., he me hodo [13] decomposes
(i possible) exis ing ga es (e.g., a 3-inpu
AND
in o wo 2-inpu
ANDs),
wi hou any u he sea ch o he implemen a ion space,
and he me hod o [7] ex ends he decomposi ion o mo e complex
(algeb aic) di iso s, bu does no ackle he limi a ion o he ini ial
MC a chi ec u e.
*This
wo k
has been unded by ESPRIT
ACiD-WG
N .
214949, CICYT TIC
95-0419,EPSRC g an s Gm24038 and GR/K70175, and MURST (p ojec
“VLSI
A chi ec u es”).
The bes ep esen a i e o he second ca ego y appea s o be
he wo k o
S.
Bums [3]. I p o ides gene al condi ions o speed-
independen decomposi ion o complex (sequen ial) elemen s in o
wo sequen ial elemen s (o a sequen ial and a combina ional el-
emen ). No ably, hese condi ions a e analyzed using he o iginal
(unexpanded) beha io al model, hus imp o ing he e iciency o
he me hod. This wo k is, in ou opinion, a big s ep
in
he igh
di ec ion, bu add esses mainly co ec ness issues. I does no
desc ibe how o use he e icien co ec ness checks in an op i-
miza ion loop, and does no allow he sha ing o a decomposed
ga e by di e en signal ne wo ks.
In [14, 121 me hods o echnology mapping o undamen al
mode and speed-independen ci cui s using complex ga es we e
p esen ed. These me hods howe e only iden i y when a se o
simple logic ga es can
be
implemen ed as a complex ga e, bu
canno pe o m a speed-independen decomposi ion o a signal
unc ion in case i does no i in o a single ga e.
A
BDD-based
implemen a ion o [12] is used a e decomposi ion as a pos -
op imiza ion s ep in his wo k.
In ou p esen wo k we a e conside ing a mo e gene al ame-
wo k which allows use o
a bi a y ga es and la ches
a ailable
in he lib a y o decompose a complex ga e unc ion, as shown
in Figu e
1.
In ha espec , we a e e ec i ely making p og ess
owa ds he mo e lexible second app oach. The basic idea
o
his
new me hod is as ollows.
An ini ial complex ga e is cha ac e ized by i s unc ion
F.
The
esul o decomposi ion is
a
lib a y componen designa ed by
G
and a se o (possibly s ill complex) ga es labeled
HI,
H2,
. .
.
H,.
The la e a e decomposed ecu si ely un il all elemen s a e ound
in
he lib a y and op imized o achie e he lowes possible cos .
We hus by and la ge pu no es ic ions on he implemen a ion
a chi ec u e
in
his wo k. Howe e , as will be seen u he , o
he sake o p ac ical e iciency, ou implemen ed p ocedu e deals
only wi h he 2-inpu ga es and/o la ches o ac as G-elemen s
in
he decomposi ion. The second impo an change o his wo k
compa ed o [7] is ha he new me hod is based on a ull scale
Boolean decomposi ion a he han jus
on
algeb aic ac o iza ion.
This allows us o widen he scope o implemen able solu ions
and imp o e on a ea cos ( u u e wo k will ackle pe onnance-
o ien ed decomposi ion).
Ou
second goal
in
gene alizing he C-elemen based decom-
posi ion has been o allow
he
designe
o
use
mo e
con en ional
ypes
o
la ches,
e.g. D-la ches and SR-la ches, ins ead
o
C-
elemen s ha may no exis in con en ional s anda d-cell lib a ies.
Fu he mo e, as ou expe imen al esul s show (see Sec ion
6),
in
many cases he use o s anda d la ches ins ead o C-elemen s helps
imp o ing he ci cui implemen a ions conside ably.
The powe o his new me hod can
be
app ecia ed by looking
a he example
haza d.
g.The o iginal STG speci ica ion and i s
s a e g aph a e shown in Figu e 2,a and b. The ini ial implemen-
a ion using he “s anda d C-a chi ec u e” and i s decomposi ion
using wo inpu ga es by he me hod desc ibed in
[7]
a e shown
in Figu e 2,c and d.
Ou
new me hod p oduces a much cheape
220
1092-3152/97
$10.00
0
1997
IEEE
p-3
*
.
-
-
-.
:
Hn
Figu e
1
:
F amewo k o speed-independen decomposi ion
solu ion wi h jus wo D-la ches, shown in Figu e 2,e. Despi e
he appa en i iali y ( o an expe ienced human designe !) o
his solu ion, none o he p e iously exis ing au oma ed ools has
been able o ob ain i . Also no e ha he D-la ches a e used in a
speed-independen
ashion, and a e hus ee om me as abili y
and haza d p oblems.
acdz
a+
I
~
V
a-
ci
Z+
Jd+
V
i.
I
(a) (b) (4
Figu e 2: An example o Signal T ansi ion G aph (a), S a e G aph
(b) and hei implemen a ion (c)(d)(e) (benchma k
haza d.
g)
The pape is o ganized as ollows. Sec ion 2 in oduces he
main heo e ical concep s. Sec ion
3
p esen s an o e iew o he
me hod. Sec ion
4
desc ibes he Boolean ela ion-based decom-
posi ion echnique in mo e de ail. Sec ion
5
b ie ly desc ibes i s
algo i hmic implemen a ion. Expe imen al esul s a e p esen ed
in Sec ion
6.
2
Backg ound
2.1
S a e G aphs and Logic Implemen abili y
A
S a e G aph
(SG)
is a labeled di ec ed g aph whose nodes a e
called
,s a es.
Each a c o an
SG
is labeled wi h an
e en ,
ha is a
ising
(a+)
o
alling
(a-)
ansi ion o a signal
a
in he speci ied
ci cui . We also allow no a ion
a*
i we a e no speci ic abou
he di ec ion o he signal ansi ion. Each s a e is labeled wi h a
ec o o signal alues. An
SG
is
consis en
i i s s a e labeling
II
:
S
-4
(0,
lJn
is such ha : in e e y ansi ion sequence om
he ini ial s a e, ising and alling ansi ions al ema e o each
signal. Figu e 2,b shows he
SG
o he Signal T ansi ion G aph
in Figu e 2,a, which is consis en . We w i e
s
5
(s
5
s')
i he e
is an a c om s a e
s
( o s a e
s')
labeled wi h
a.
The se o all signals whose ansi ions label
SG
a cs a e
pa i ioned in o a (possibly emp y) se o inpu s, which come
"
he en i onmen , and a se
o
ou pu s o s a e signals ha
mus be implemen ed. In addi ion o consis ency, he ollowing
wo p ope ies o an
SG
a e needed o hei implemen abili y in
a speed-independen logic ci cui .
The i s p ope y is
speed-independence.
I consis s o h ee
pa s: de e minism, commu a i i y and ou pu -pe sis ence. An
SG
is called
de e minis ic
i o each s a e
s
:nd each label
a
he e can
be
a mos one s a e
s'
such ha
s
+
s'.
An
SG
is
called
commu a i e
i whene e wo ansi ions can be execu ed
om some s a e in any o de , hen hei execu ion always leads
o he same s a e, ega dless o he o de . An e en
a*
is called
pe sis en
in
s a e
s
i i is enabled a
s
and emains enabled in any
o he s a e eachable om
s
by i ing ano he e en
b*
.
An
SG
is
called
ou pu -pe sis en
i i s ou pu signal e en s a e pe sis en in
all s a es and no ou pu signal e en can disable inpu e en s. Any
ans o ma ion (e.g., inse ion
o
new signals o decomposi ion),
i pe o med a he
SG
le el, may a ec all h ee p ope ies.
The second equi emen ,
Comple e S a e Coding
(CSC),
be-
comes necessa y and su icien o he exis ence o a logic ci cui
implemen a ion. A consis en
SG
sa is ies he
CSC
p ope y i
o e e y pai o s a es
s,
s'
such ha
(s)
=
(s'),
he se o
ou pu e en s enabled in bo h s a es is he same. (The
SG
in Fig-
u e 2,b is
ou pu -pe sis en
and has
CSC.)
CSC
does no howe e
es ic he ype o logic unc ion implemen ing each signal. I
equi es ha each signal is cas in o a
single a omic
ga e. The
complexi y o such a ga e can howe e go beyond ha p o ided
in a conc e e lib a y
o
echnology.
The concep s o exci a ion egions and quiescen egions a e
essen ial o ans o ma ion
o
SGs.
A se o s a es is called
an
exci a ion egion
(ER)
o e en
a*
(deno ed by
ER(a*))
i
s
E
ER(a*)
s
5.
The
quiescen egion
(QR)
(deno ed by
QR(n*))
o a ansi ion
a,*,
wi h exci a ion egion
ER(a*),
is
he se o s a es in which
a
is s able and keeps he same alue.
Examples o
ER
and
QR
a e shown in Figu e 2,b.
2.2
P ope y-p ese ing e en inse ion
E en inse ion is an ope a ion on an
SG
which selec s a subse
o s a es, spli s each
o
hem in o wo s a es and c ea es, on he
basis o hese new s a es, an exci a ion egion o a new e en .
Figu e
3
shows he chosen inse ion scheme, analogous o ha
used by mos au ho s
in
he a ea
[15].
We say ha an inse ed
signal
a
is acknowledged
by a signal
b,
i
b
is one o he signals
delayed by he inse ion
o
a,
( he same e minology will be used
o he co esponding ans,i ions).
Fo
example,
d
acknowledges
x
in Figu e
3.
Figu e
3:
E en inse ion: (a) be o e, (b) a e inse ion
S a e signal inse ion mus p ese e he
speed-independence
o he o iginal speci ica ion. The e en s co esponding o an
inse ed signal
x
a e deno ed
a,
x+,
E-,
o ,
i
no con usion
occu s, simply by
E.
Le
l
be a de e minis ic, commu a i e
SG
and le
A'
be he
SG
ob ained om
A
by inse ing e en
E.
We say
ha an inse ion s a e se
ER(x)
in
A
is a
speed-independence
p ese ing se (SIP-se )
i 2
(1)
o each e en
a
in
A,
i
a
is
pe sis en in
A,
hen i emains pe sis en in
A',
and
(2)
A'
is
de e minis ic and commu a i e. The o mal condi ions o he se
o
s a es
T
o
be
a SIP-se can be gi en
in
e ms
o
in e sec ions o
T
wi h he so-called s a e diamonds o SG
[5].
A
new signal is inse ed using an
I-pa i ion
o a se
o
s a es
S
in o ou blocks:
ER(e+
,
QR(z+),
ER(z-),
Q l(x_)}
(simila o
[15]).
QRI
de ines he s a es in which
x
will ha e he s able%?/z
($+k?R(z+)
(ER(x-))
de ines
he exci a ion egion o
E
in he new
SG
A'.
To dis inguish be-
ween he se s o s a es ox he exci a ion (quiescen ) egions o
he
inse ed
signal
z
in
an
o iginal
SG
A
and
he
new
SG
A'
we
will e e
o
hem as
ERA(z*)
and
ERA,(E*) (QRA(z*)
and
QRA (z*)),
espec i ely. [ he inse ion o
x
p ese es consis-
ency and pe sis ency, hen he only ansi ions c ossing bound-
22
1
a ies o he blocks a e he ollowing:
QR(x-)
+
ERA(x+)
-+
Example
2.1
Figu e4 shows h ee di e en caseso he inse ion
o a new signal
x
in o he SG o he
haza d.
g
example. The
inse ion using
ERA(x+)
and
ERA(x-)
o Figu e 4,a does
no p ese e speed-independence as he SIP se condi ions a e
iola ed o
ERA(x+)
since ansi ion
d+,
enabled in s a e
1100,
will be delayed in s a e
0100
a e inse ing
x.
When signal
x
is inse ed by he exci a ion egions in Figu e 4,b
hen i s posi i e swi ching is acknowledged by ansi ions
a-,
d+,
while i s nega i e swi ching by ansi ion
z-.
The co esponding
exci a ion egions sa isjj he SIP condi ions and he new
SG
A',
ob ained a e inse ion o signal
x,
is shown in Figu e 4,b. No e
ha he acknowledgmen
o
x+
by ansi ions
a-,
d+
esul s in
delaying
some inpu signal
ansi ions in
A'
un il
x+
i es. This
changes he o iginal
I10
in e ace o
SG
A,
because i equi es
he en i onmen o
look
a he new signal be o e i can change
a
and
d.
This is gene ally undesi able and hence his inse ion is
ejec ed.
QR(x+)
+
ERA(x-)
-+
QR(x-).
acdm
y+-
SG
A:
acdz
SG
A':
acd x
Oy2-
001
II
0111
1111
J
c-
sa*
2-
Figu e
4:
Di e en cases o signal inse ion o benchma k
haza d.
g:
iola ing he SIP-condi ion (a), changing he
U0
in e ace (b), co ec inse ion (c)
The exci a ion egions
ERA(x+)
and
ERA(x-)
shown in
Figu e 4,c a e SIP se s. They comply wi h he o iginal NO in-
e ace because posi i e and nega i e ansi ions o signal
x
a e
acknowledged only by ou pu signal
z.
This inse ion scheme is
alid.
2.3
Basic de ini ions abou Boolean Func ions and Rela ions
An
incomple ely speci ied (scala ) Boolean unc ion is a mapping
F
:
B"
-
{0,1,
-},
whe e
B
=
{0,1}
and
'-'
is
adon' ca e
alue. The subse s o domain
B"
in which
F
holds he
0,
1
and
don' ca e alue a e espec i ely called he
OFF-se , ON-se
and
DC-se .
F
is
comple ely speci ied
i
i s DC-se is emp y. We shall
u he always assume ha
F
is a comple ely speci ied Boolean
unc ion unless said o he wise speci ically.
A
a iable
x
E
X
is
essen ial
o unc ion
F
(o
F
is dependen
on
x)
i he e exis a leas wo min e ms
1,
2
di e en only in
he alue o
x,
such ha F( 1)
#
F( 2).
The se o essen ial
a iables o a Boolean unc ion
F
is called he
ue suppo
o
F
and is deno ed by
sup)(
F).
I is clea ha o an a bi a y Boolean
unc ion i s suppo may no be he same as he ue suppo . E.g.,
o asuppo X
=
{a,
b,c}anda unc ionF(X) =b+c hehue
suppo o
F(X)
is
sup(
F)
=
{b,
c},
i.e. only a subse o
X.
The
co ac o
o
F(X)
wi h espec o x
(E)
is de ined as
,
espec i ely). The Shannon expansion o
a
Boolean
The
Boolean di e ence,
o
Boolean de i a i e,
o
F(X)
wi h
espec o
x,
E
X
is de ined as
6FISx
=
F,,
@
Fc
Fx,
=
F(z~
,...,
=
1
,...,
~n)
(FK
=
F(x~
,...,
X,
=
unc ion
O,
. .
.
"'%
(X)
is basedoni sco ac o s:
F(X)
=
xz
F,,+KF-
do
1:
o each
non-inpu signal
x
do
solu ions(x)
:
=0
;
2: o each
ga e
G
E
{la ches, and2,
o 2)
do
solu ions(x)
:
=solu ions(x)
U
decomposi ions(x.G);
end o
3:
bes H(x)
:=
Bes
SIP
candida e om
solu ions(x);
4: i
o each
x,
bes H(x)
is
implemen able
5:
Le
H
be he mos complex
bes H(x);
6:
Inse signal
d
implemen ing
H,
de i e new
SG;
7:
Lib a y ma ching;
end o
o
o each
x,
bes H(x)
is
emp y
hen exi loop;
o e e
Figu e
5
:
Algo i hm o logic decomposi ion and echnology map-
Ping-
A
unc ion
F(x1,.
. . ,
x ,.
. .
,xn)
is
una e in a iable
x
i
ei he
Fc
5
F,,
o
F,,
5
F
unde o de ing
0
5
-
5
1.
In
he o me case
(F
5
Fxz)
i<is called
posi i e una e in
xl,
in
he la e case
nega i e una e in
2%.
A
unc ion ha is no una e in
xz
is called
bina e
in
x
. A
unc ion is (posi i elnega i e)
una e
i
i is (posi i e/nega i e)
una e
in
all
suppo a iables. O he wise
i
is
bina e.
Fo
example, he unc ion
F
=
a
+
b
+
Z
is
posi i e
una e in a iable
a
because
Fa
=
1
2
Fz
=
b
+
E.
Fo
an
incomple ely speci ied unc ion
F(X)
wi h a DC-
se , le us de ine he DC unc ion
FDC
:
B"
-+
B
su2h ha
ON(FDC)
=
DC(F).
We will say ha a unc ion
F
is an
implemen a ion o
F
i
F
'
5
5
F
5
F
+
FDC.
A
Boolean ela ion,
R,
is a gene aliza ion o a Boolean unc-
ion, whe e
a
poin in he domain
B"
can
be
associa ed wi h
se e al poin s in he codomain, i.e.
R
B"
x
{0,1}"
[2,
1
I].
Some imes, we use he
"-"
symbol as a sho hand in deno ing
elemen s in he codomain ec o , e.g.
-0
o 10 and
00.
Boolean
ela ions play an impo an ole
in
mul i-le el logic syn hesis
[I
11,
and we shall use hem in ou decomposi ion me hod.
Conside a se o Boolean unc ions
3.1
=
{HI,
Hz,
. . .
,
Hm}
wi h he same domain. Le
R
E
B"
x
(0,
1)"
be a Boolean
ela ion wi h he same domain as unc ions om
X.
We will say
ha
X
is
compa ible
wi h
R
i
o e e y poin
in he domain
o
R
he ec o o alues
( ,
Hl( ),
Hz( ),
. . . ,
Hm( ))
is an
elemen o
R.
3
O e iew
o
he me hod
Ou
p oposed me hod o sequen ial decomposi ion o speed-
independen ci cui s aimed a echnology mapping consis s
o
h ee main s eps:
1.
Syn hesis ia decomposi ion based
on
Boolean ela ions;
2.
Signal inse ion and gene a ion o a new
SG;
3.
Lib a y ma ching
The i s wo s eps a e i e a ed un il all unc ions a e decom-
posed in o implemen able ga es
o
no
u he p og ess can be
made. Each ime a new signal is inse ed (s ep
2),
esyn hesis
is pe o med o all ou pu signals (s ep
1).
Finally, s ep
3
col-
lapses decomposed ga es and ma ches hem wi h lib am ga es.
The pseudo-cbde o he echnology mapping algo i hm
is
ii en
in Figu e
5.
By using a speed-independen ini ial
SG
speci ica ion, a com-
plex ga e implemen a ion o each
SG
signal is gua an eed o be
speed-independen . Un o una ely his ga e
may
be
oo
la ge
o
be
iiiipleme i ed
in
a
lib a y.
The
goal
o he p oposed me hod
is
o b eak his ga e
s a i ig om
i s
oc pu
by
using
sequen ial
(i i s unc ion
is
sel -dependen , i.e.
i
has in emal eedback)
o
co nbinu ional
ga es.
222
Gi en a ec o X o
SG
signals and gi en one non-inpu signal
y
E
X
we
y
o decompose he unc ion
F(X)
in o (line
2
o
algo i hm in Figu e
5):
0
a combina ional
o
sequen ial ga e wi h unc ion
G(Z,
y),
0
a ec o o combina ional’ unc ions
X(X)
o signals
Z,
so
ha
G(’H(X))
implemen s
F(X).
Mo eo e , we equi e he
newly in oduced signals o be speed-independen (line
3).
The p oblem o ep esen ing he lexibili y in he choice o he
‘H
unc ions has been explo ed, in he con ex o combina ional
logic minimiza ion, by [18] among o he s. He e we ex end i s o -
mula ion o co e also
sequen ial
ga es (in Sec ions
4.1
and
4.3).
This is essen ial in o de o o e come he limi a ions o p e ious
me hods
o
speed-independen ci cui syn hesis ha we e based
on a speci ic a chi ec u e. Now we a e able o use a b oad ange
o
sequen ial elemen s, like se and ese dominan
SR
la ches,
anspa en
D
la ches, and
so
on. We belie e ha o e coming
his limi a ion
o
p e ious me hods ( ha could only use
C
ele-
men s and dual- ail SR-la ches) is one o he majo s eng hs o
his wo k. Apa om d ama ically imp o ing some expe imen al
esul s, i allows one o use a “gene ic” s anda d-cell lib a y ( ha
gene ally includes
SR
and
D
la ches, bu no
C
elemen s).
The algo i hm p oceeds as ollows. We s a om an
SG
and
de i e a logic unc ion o all i s non-inpu signals (line
1).
We
hen pe o m an implemen abili y check o each such unc ion as
a lib a y ga e. The la ges non-implemen able unc ion is selec ed
o decomposi ion. In o de o limi he sea ch space, we cu en ly
y
as candida es o
G
(line
2):
0
all he sequen ial elemen s in he lib a y (assumed o ha e
wo inpu s a mos , again in o de o limi he sea ch space),
wo-inpu
AND,
OR
ga es wi h all possible inpu in e sions.
The se o unc ion pai s
(HI,
H2)
compa ible wi h he
Boolean ela ion
is
hen checked o speed-independence (line
3),
as desc ibed in Sec ion
2.2.
I bo h a e no speed-independen ,
he pai is immedia ely ejec ed.
Then, bo h
HI
and
H2
a e checked o app oxima e (as dis-
cussed abo e) implemen abili y in he lib a y, in inc easing o de
o es ima ed cos . We ha e wo cases:
1.
bo h a e speed-independen and implemen able: in his case
2.
o he wise, he mos complex implemen able
H;
is selec ed,
The la e is a heu is ic echnique aimed a keeping he decompo-
si ion balanced. No e ha a his s age we can also implemen
HI
o
H2
as
a
sequen ial ga e
i
he
su icien
condi ions desc ibed in
Sec ion
4.3
a e me .
The p ocedu e is i e a ed as long as he e is p og ess
o
un-
il e e y hing has been decomposed (line
4).
Each ime a new
unc ion
H,
is selec ed o
be
implemen ed as a new signal, i is
inse ed in o he
SG
(line
6)
and esyn hesis is pe o med in he
nex i e a ion.
The incomple eness o he me hod is essen ially due o he
g eedy heu is ic sea ch ha accep s he smalles implemen able
o
non-implemen able bu speed-independen solu ion. We
be-
lie e ha an exhaus i e enume a ion wi h back acking would
be
comple e e en o non-au onomous ci cui s, by a ela i ely
s aigh o wa d ex ension o he esul s in [161.
A he end, we pe o m a Boolean ma ching s ep
([lo])
o
eco e a ea and delay (line
7).
This s ep can me ge oge he
he simple 2-inpu combina ional ga es ha we ha e (conse a-
i ely) used in he decomposi ion in o a la ge lib a y ga e. I is
gua an eed
no
o
in oduce
any
haza ds
i
he ma ched ga es a e
a omic.
whe e
Z
is a ec o o newly in oduced signals,
he decomposi ion is accep ed,
and he o he one is me ged wi h
G.
‘The es ic ion ha X(X) becombina ional will
bepa iallyli edinSec ion4.3.
4
4.1
Speci ying pe missible decomposi ions wi h
BRs
In his pape we apply
BRis
o he ollowing p oblem.
Gi en an incomple ely speci ied Boolean unc ion
F
(X
o signal
y,
y
E
X,
decomposei in o wo-le els
y
=
G(Z,
y);
d
=
X(X)
such ha
G(
‘H(
X)
,
y
)
implemen s
F (X)
and unc ions
G
and
‘H
ha e a simple implemen a ion han
F
(any such
3-1
will be called
pe missible).
The i s -le el unc ion
N(X)
=
{H1(X),
.
. .
,
Hn(X)}
is a
mul i-ou pu logic unc ion, speci ying he beha io o in emal
nodes o he decomposi ion,
Z
=
{
z1
, . .
. ,
zn}
’.
A each s ep o decomposi ion a small mappable piece ( unc-
ion
G)
is cu om he po en ially complex and unmappable unc-
ion
F.
Fo
a selec ed
G
all pe missible implemen a ions o
unc ion
7i
a e speci ied wi h a
BR
and hen ia minimiza ion
o
BRs
a ew bes compa ible unc ions a e ob ained. All o hem
a e e i ied o speed-independence by checking SIP-se s. The
one which is speed-independen and has he bes es ima ed cos is
selec ed.
Since he ue suppo o unc ion
F
can include he ou pu
a iable
y,
i can speci y sequen ial beha io . In he mos gene al
case we pe o m wo-le el
sequen ial
decomposi ion such ha
bo h unc ion
G
and unc1.ion
‘H
can be sequen ial, i.e., con ain
hei own ou pu a iables in he ue suppo s. The second le el
o he decomposi ion is ma de sequen ial by selec ing a la ch
”
he lib a y as a candida e ga e,
G.
The echnique o de i ing a
sequen ial solu ion o he i s le el
X
is desc ibed in Sec ion
4.3.
We nex show by example how all pe missible implemen a-
ions
o
decomposi ion can be exp essed wi h
BRs.
Logic decomposi ion using Boolean ela ions
a+-
-c-
d-
o
a-
I I
ai:-*
d
Y
d
aF
P
e)
Figu e 6: Sequen ial decomposi ion o
y
=
acz
+
y(C
+
2)
Example
4.1
Conside he
STG
in Figu e 6,a, whose
SG
ap-
pea s in Figu e 7,a. Signals
a,
c
and
d
a e inpu s and
y
is an
ou pu .
A
possible implenien @on o he logic unc ion o
y
is
F(a,
c,
d,
y)
=
ad
+
y(C
+
d).
Le us decompose his unc ion
using as
G
a ese -domin an Rs-la ch ep esen ed
by
he equa-
ion
y
=
G(R,
S,
y)
=
x(S
+
y)
(see Figu e 6,b). A he i s
s ep we speci y he pe mis: ible implemen a ions o he i s le el
unc ions
R
=
H1
and
S
==
H2
by using he
BR
speci ied in Fig-
u e 7,b. Conside , o example, ec o
a,
c,
d,
y
=
0000.
I is easy
o check ha
F(0,
0,
0,O)
=
0.
Hence, o ec o
0000
he able
speci ies ha
(R,
S)
=
{
11
1,
10,00}
=
{
1-,
-O},
i.e. any im-
plemen a ion
o
R
and
S
mus keep o his inpu ec o
ei he 1
a
’Fo simplici y we conside he decomposi ionp oblem o a
single-ou pu bina y
unc ion
F,
al hough gene aliza ion o he mul i-ou pu and mul i- alued unc ions
is s aigh o wa d.
223
1010
101
1
1100
1101
0100 iiin
I
iiii
(a>
I"
1-,4
1L-O
1L.4
1
0-
1
0-
1
01
1
0-
I-,4
-
-
Figu e
7:
(a) S a e g aph, (b) Decomposi ion o
y
by an
Rs
la ch
Table 1
:
Boolean ela ions o di e en ga es
R
o
0
ai
S.
On
he o he hand, only one solu ion
R
=
0,
S
=
1
is possible o he inpu ec o
1100
which co esponds o se ing
he ou pu o he Rs-la ch o
1.
The Boolean ela ion sol e will
jind, among o he s, he wo solu ions illus a ed in Figu e 6,c,d:
(I)
R
=
cd;
S
=
ad and
(2)
R
=
cd
-1-
ijC;
S
=
a.
Any o
hese solu ions can be chosen depending
on
he cos unc ion.
Table 1 speci ies compa ible alues o
BRs
o di e en ypes
o ga es: a D-la ch, a ese -dominan Rs-la ch, a wo inpu AND
ga e and a wo inpu
OR
ga e.
All
s a es o an
SG
a e pa i ioned
in o ou subse s,
ER(y+),
QR(y+),
ER(y-),
and
QR(y-),
wi h espec o signal
y
wi h unc ion
F(X)
o which decompo-
si ion is pe o med.
All
s a es ha a e no eachable
in
he
SG
o m a DC-se o he
BR.
E.g., o each s a e,
s,
om
ER(y+)
only one compa ible solu ion, 11, is allowed
o
inpu unc ions
HI,
Hz
o
a D-la ch. This is because he ou pu o a D-la ch in
all s a es,
s
E
ER(y+)
is a
0
and
F(s)
=
1. Unde hese con-
di ions he combina ion
11
(clock and da a inpu s a e bo h high)
is he only possible inpu combina ion ha implies 1 a he ou pu
o
a D-la ch.
On
he o he hand, o each s a e
s
E
Q
R(y+),
he
ou pu
y
=
1 and
F(s)
=
1, hence i is enough o equi e ei he
da a inpu
o
be
in
1
o
clock inpu o be
in
0
o keep he ou pu o
a la ch in
1.
This is exp essed by alues
{OW,
-1)
in he second
line o he able.
4.2
Func ional ep esen a ion
o
Boolean ela ions
Gi en an
SG
sa is ying
CSC
equi emen , each ou pu signal
y
E
X
is associa ed wi h a unique
incomple ely
speci ied unc ion
F
X
,
whose DC-se ep esen s he se o un eachable s a es.
FIX]
can be ep esen ed by h ee
comple ely
s
eci ied unc ions,
deno ed
ON
(
y)
(X),
OFF(
g)&XJand
DC(
yy(X)
ep esen ing
he
ON-,
OFF-, and DC-se o
(
),
such ha hey a e pain ise
disjoin and hei union
is
a au ology.
Le a gene ic n-inpu
ga e
be
ep esen ed
by
a
Boolean
equa-
ion
q
=
G(Z,
q),
whe e
Z
=
(21,.
.
.
,
zn}
a e he inpu s o hc
ga e, and
q
is i s ou pu . The ga e is sequen ial i
q
belongs o he
ue suppo o
G(Z,
q).
We now gi e he cha ac e is ic unc ion o he Boolean ela ion
o
he implemen a ion
o
F(X)
wi h ga e
G.
I ep esen s
all
pe missible implemen a ions o
z1
=
HI
(X),
.
.
.
,
zn
=
Hn(X)
ha allow
F
o be decomposed by
G.
BR(Y)(X,
Z)
=
ON(y)(X)
.
G(Z,
Y)
+
OFF(Y)(X)
'
Go
+
WY)(X)
(1)
Gi en cha ac e is ic unc ion
(I),
he co esponding able de-
sc ibing Boolean ela ion can be de i ed using co ac o s. Fo
each min e m
m
wi h suppo in
X,
he co ac o
BR(Y)~
gi es
he cha ac e is ic unc ion o
all
compa ible alues o
21,
. . .
,
zn
(see example below).
Finding
a
decomposi ion o
F
wi h ga e
G
is educed o inding
a se o
n
unc ions
N(X)
=
(H1(X),
.
. .
,
H,(X))
such ha
BR(Y)(X,
WX))
=
1
(2)
Example
4.2
(Example
4.1
con inued.)
The
SG
shown in Fig-
u e 7.a co esponds
o
he
STG
in
Figu e
6.
Le us conside
how he implemen a ion o signal
y
wi h a ese -dominan Rs
la ch can be exp essed using he cha ac e is ic unc ion
o
BR.
Recall ha he able shown in Figu e 7.b ep esen s he unc ion
F(a,
c,
d,
y)
=
acs+
y(C+d)
and hepe missible alues o he
inpu s
R
and
S
o he Rs la ch. The
ON-,
OFF-, and DC-se s
o
unc ion
F(a,
c,
d,
y)
a edejinedby:
oN(y)
=
y(~
+
Z)
+
ac2
DC(y)
=
acdy
OFF(?/)
=
?j(Z
+
C
+
d)
+
Zcd
The se o pe missible implemen a ions o
R
and
S
is cha ac-
e ized by he ollowing cha ac e is ic unc ion
o
he
BR
speci ied
in
he able. I can be ob ained using equa ion
I
by subs i u ing
exp essions o
ON
(y
)
,
OFF
(
y
)
,
DC(
y
),
and he unc ion o an
Rs-la ch,
R(
S
+
y)
:
BR(y)(a,
c,
d,
y,
R,
S)
=
ZSacZ
+&/(E
+
Z)
-
(R++)ij(E+c+d)
+Zcd(R+~V)+acdy
This unc ion has alue
1
o
all
combina ions ep esen ed in
he able and alue
0
o
all combina ions ha a e no in he
able (e.g., o
(a,
c,
d,
y,
R,
S)
=
000001).
Fo example, he se
o compa ible alues o
ncdy
=
01 10
is gi en
by
he co ac o
BR(y)*=dB
=
R
+
3
which co espond o he e ms
1
-
and
-0
gi en o he Boolean ela ion o ha min e m.
Two possible solu ions o
BR(y)(a,
c,d,
y,
R,
S)
=
1
co -
esponding o Figu e 6,c,d a e:
(1)
R
=
cd
;
S
=
acd
-
(2)
R
=
cd
+YE;
S
=
0,
4.3
Two-le el sequen ial decomposi ion
Accu a e es ima ion
o
he cos
o
each solu ion p oduced by
he Boolean ela ion minimize is essen ial
in
o de o ensu e
he quali y o he inal esul . The minimize i sel can only
handle
combina ional
logic,
bu
o e
(as
shown
below)
he
bes
solu ion can be ob ained by eplacing a combina ional ga e wi h a
sequen ial one. This sec ion discusses some heu is ic echniques
ha can
be
used o iden i y when such a eplacemen is possible
wi hou al e ing he asynch onous ci cui beha io , and wi hou
unde going he cos o a ull-blown sequen ial op imiza ion s ep.
Le
us
conside
ou
example again.
Exaniple
4.3
(Example
4.1
con inued,)
Le
us
ussume
hu
[he
lib a y con ains h ee-inpu AND, OR ga es and
Rs-,
S - and
D-
la ches. Implemen a ion
(I)
o
signal
y
by an Rs-la ch wi h inpu s
R=cd and S=acdma ches he lib a y and equi es
wo
AND ga es
224

(one wi h
wo
and one wi h h ee inpu s) and one Rs-la ch. The
implemen a ion
(2)
o
y
by an Rs-la ch wi h inpu s R=cd+yEand
S=a
would be ejec ed, as i equi es a complex
AND-OR
ga e
which is
no
in he lib a y. Howe e , when inpu
jj
in he unc ion
cd
+
7;
is eplaced by signal
R,
he ou pu beha io o
R
will
no chcunge, i.e. unc ion
R=cd
+
jj
E
can be sa ely eplaced by
R=cd
+
RE.
The la e equa ion co esponds o he unc ion o a
D-la ch and gi es he alid implemen a ion shown in Figu e 6,e.
Ou
echnique o imp o e he accu acy o he cos es ima ion
s ep, by pa ially conside ing sequen ial ga es, is as ollows:
1. P oduce pe missible unc ions
21
=
H1(X)
and
z2
=
H2(X)
ia he minimiza ion o Boolean ela ions
(zl
and
z2
a e always combina ional as
z1,z2
@
X).
i
Hi
ma ches he lib a y
hen
Complexi y
=
cos o he ga e
else
Complexi y
=
li e al coun
3.
Es ima e he possible simpli ica ion o
HI
and
H2
due o
adding signals
z1
and
z2
o hei suppo s, i.e. es ima e he
complexi y o he new pai
{
Hj,
Hi}
o pe missible unc-
ions
21
=
H;(X,
ZI,
z2),
22
=
H;(X,
ZI,.~).
4. Choose he bes complexi y be ween
HI
(Hz)
and
Hi
(Hi).
Le
us
conside he ask o de e mining
H;
and
Hi
as in s ep
3.
Le
A
be an
SG
encoded by a iables om se
V
and le
z
=
I (
X,
y
)
,
such ha
X
C
V,
y
E
V,
be an equa ion o he new a iable
z
$2
V
which is o be inse ed in
A.
The esul ing
SG
is deno ed
A’=ln.s(A,
z=H(X,
y))
(o
A’=Ins(A,
z1,.
. .
,
zk)
when mo e
han one signal is inse ed).
A
solu ion o S ep
3
o he abo e p ocedu e can be ob ained
by minimizing unc ions
o
signals
21
and
22
in an
SG
A’
=
Ins(A,
21,
z2).
Howe e his is a he ine icien because he
c ea ion o
SG
A’
is compu a ionally expensi e. Hence ins ead
o looking o an exac es ima ion o complexi y o signals
z1
and
zz
we will ely on
a
heu is ic solu ion, ollowing he ideas on
inpu esubs i u ion p esen ed in Example 4.3.
Fo
compu a ional
e iciency, he o mal condi ions on in u esubs i u ion should be
o mula ed in e ms
o
an o iginal
S&
A
a he han in e ms
o
he
SG
A’
ob ained a e he inse ion o new signals3.
Lemma 4.1
Le Boolean unc ion
B(X,
y)
implemen he in-
se ed ,signal z.Func ion
H
can be ep esen ed as
H(X,
y)
=
Fy
+
Gjj
+
R,
whe e
F,
G
and
R
a e Boolean unc ions
no
depending on
y.
Le
H’(X,
z)
=
z(F
+
G)
+
R,
hen
SGs
A’=Ins(A,
z=H(X,
y))
andA”=Ins(A,
z=H’(X,
2))
a eiso-
mo phic i he ollowing condi ions a e sa is ied:
2.
Es ima e he complexi y o
HI
and
H2:
6H(X,y)/6y.S*
-0
(1)
F*G*RnS+
ZO
(2),
whe e
S”
and
S’
a e cha ac e is ic Boolean unc ions desc ib-
ing se ,s o s a es ERA(z+)
U
ERA(z-) and ERA(z+) in
A,
espec i ely.
In o mally Lemma 4.1 s a es ha esubs i u ion o inpu
y
by
z
is pe missible i in all s a es whe e he alue o unc ion
H(X,
y)
depends on
y,
he inse ed signal
z
has
a
s able alue.
The condi ions o Lemma 4.1 can
be
e icien ly checked wi hin
ou
BDD-based amewo k. They equi e o check wo au ologies
in ol ing unc ions de ined o e he s a es o he o iginal
SG
A.
Example 4.4 (Example 4.1 con inued.)
Le inpu
R
o he RS-
la ch be implemen ed as
cd
+
SE
(see Figu e 6,d). The ON-se o
unc ion
H
=cd+jjFis shown by he dashed line in Figu e
7,a.
The
inpu bo de
o
H
(deno ed by I
B(
H))
is he se
o
s a es by which
3No e
ha his heu is ic
es ima ion co e s
only
he
cases when one
o
he inpu
signals
o
a
combina ionalpe missible
unc ion
H,
is eplaced by he eedback
z.
om he ou pu o
H,
i sel . O he cases can
also
be
in es iga ed, bu checking hem
would
be
oo
complex.
i sUN-se isen e edin heo iginalSGA,i.e.
IB(H)
=
(0111).
By simila conside a ion we ha e ha IB(H)
=
(0100).
These
inpu bo de ssa is y he SIP condi ions and hence In(
H)
can be
akenas ERA(R+), while ERA(R-) mus beexpandedbeyond
IB
H)
by s a e 1100 o no o delay he inpu ansi ion
a+
H
is nega i e una e in
y
and hence Condi ion
2
o
Lemma
4.1
is always sa is ied. The se o s a es whe e he alue
o
unc ion
H
essen ially depends on signal
y
is gi en
by
he unc-
ion
6H(X,
y)/Sy
=
aE.
Cube
a?
has no in e sec ion wi h
ERA(R+)
U
ERA(R-) and Condi ion 1 o Lemma
4.1
is
also
sa is ied. The e o e li e al
y
can be eplaced by li e al
R,
hus
p oducing a new pe missible unc ion R=cd
+
RE.
(E
a
A(R-)
=
(0100,110~0)).
5
Implemen a ion aispec s
The me hod o logic decomposi ion p esen ed in he p e ious
sec ion has been implemen ed in a syn hesis ool o
speed-
independen ci cui s. The main pu pose o such implemen a ion
was o e alua e he po en ial imp o emen s ha could
be
ob ained
in he syn hesis o speed-independen ci cui s by using a Boolean-
ela ion-based decomposi ion app oach. E iciency o he cu en
implemen a ion was consi’de ed o
be
a seconda y goal a his
s age o he esea ch.
5.1 Sol ing Boolean ela ions
In he o e all app oach, i io equi ed o sol e
BRs
o each ou pu
signal and
o
each ga e anid la ch used o decomposi ion.
Fu -
he mo e,
o
each signal and o each ga e, se e al solu ions a e
desi able in o de o inc ease he chances o ind
SIP
unc ions.
P e ious app oaches o sol e
BRs
[2,
171
do no sa is y he
needs o
ou
syn hesis me hod, since (1) hey minimize he numbe
o e ms o a
mul iple-ou pu unc ion
and
(2)
hey deli e (wi hou
signi ican modi ica ions o he algo i hms and hei implemen a-
ion) only one solu ion o each
BR.
In
ou
case we need o ob ain
se e al compa ible solu ions
wi h he p ima y goal o
minimizing
he complexi y o each unc ion indi idually.
Te m sha ing is no
signi ican because wo-le el decomposi ion o a unc ion is no
speed-independen in gene al, and hence each minimized unc ion
mus be ea ed as an
a omic
objec . Sha ing can
be
exploi ed,
on
he o he hand, when e-syn hesizing he ci cui a e inse ion o
each new signal.
Fo
his eason we de ised a heu is ic app oach
o sol e
BRs.
We nex b ie ly ske ch i .
Gi en a
BR
BR(y)(X,
Z),
each unc ion
A;
o
z
is indi id-
ually minimized by assumhg ha all o he unc ions
H3
(z
#
j)
will
be
de ined in such a sway ha
Z(X)
will
be
a compa ible
solu ion o
BR.
In
gene al, an incompa ible solu ion may
be
gene a ed when combining: all
H;
’s.
Taking he example o Fig-
u e
7,
an indi idual minimiza ion o
R
and
S
could gene a e he
solu ion
R
=
cd
and
S
=
I.
Nex , a min em wi h
incompa ible
alues is selec ed, e.g.
iC&j
o which
RS
=
01 bu only he compa ible alues 1-
o
-0
a e accep able. New
13Rs
a e de i ed by eezing di e en
compa ible alues o he selec ed min e m. In his case, wo new
BRs
will
be
p oduced wi h he alues
1
-
and
-0,
espec i ely o
he min e m
iiczij.
Nex , ea.ch
BR
is again minimized indi idually
o each ou pu unc ion and new min e ms a e ozen un il a
compa ible solu ion is ob ained.
This app oach gene a es a ee o
BRs
o be sol ed. This
p o ides a way o ob aining se e al compa ible solu ions o he
same
BR.
Howe e , he explo a ion may become p ohibi i ely
expensi e i he sea ch ee is no p uned.
In
ou
implemen a ion,
a b anch-and-bound-like p uning s a egy has been inco po a ed
o such pu pose. S ill, he ime equi ed by he
BR
sol e domi-
na es he compu a ional cos o he o e all me hod in
ou
cu en
implemen a ion. Ongoing i esea ch on sol ing
BRs
o
ou
ame-
wo k
is being camed ou .
‘We
belie e ha he ac ha we pu sue
o minimize unc ions indi idually, i.e. wi hou ca ing abou e m
225
sha ing among di e en ou pu unc ions, and ha we only deal
wi h 2-ou pu decomposi ions, may he c ucial o de i e algo i hms
much mo e e icien han he exis ing app oaches.
5.2
Selec ion
o
he bes decomposi ion
Once a se o compa ible solu ions has been gene a ed o each
ou pu signal,
he
bes candida e is selec ed acco ding o he ol-
lowing c i e ia (in p io i y o de ):
1. A leas one o he decomposed unc ions mus be speed-
independen .
2. The acknowledgmen o he decomposed unc ions mus no
inc ease he complexi y o he implemen a ion o o he sig-
nals (see sec ion
5.3).
3.
Solu ions in which all decomposable unc ions a e imple-
men able in he lib a y a e p e e ed.
4.
Solu ions in which he complexi y o he la ges non-
implemen able unc ion
is
minimized
a e
p e e ed. This
c i e ion helps o balance he complexi y o he decomposed
unc ions and de i e balanced ee-like s uc u es a he han
linea ones4.
5.
The es ima ed sa ings ob ained by sha ing a unc ion o he
implemen a ion o se e al ou pu signals is also conside ed
as
a
second o de p io i y c i e ion.
Among he bes candida e solu ions o all ou pu signals, he
unc ion wi h he la ges complexi y, i.e. he a hes om imple-
men abili y, is selec ed o be implemen ed as a new ou pu signal
o he
SG.
The complexi y
o
a unc ion is calcula ed as he numbe o
li e als in ac o ed o m. In case i is a sequen ial unc ion and i
ma ches some o he la ches o he ga e lib a y, he implemen a ion
cos is di ec ly ob ained om he in o ma ion p o ided by he
lib a y.
5.3
Signal acknowledgmen and inse ion
Fo
each unc ion deli e ed by he
BR
sol e , an e icien
SIP
inse ion mus be ound. This educes o inding a pa i ion
{ERA(%+
,QRA(z+),ERA(~-),QRA(z-)}
o he
SG
A
such ha
~RA(Z+)
and
ERA(z-)
a e es ic ed o
be
SIP-
se s (Sec ion 2.2). In gene al, each unc ion may ha e se e al
ERA(z+)
and
ERA(z-)
se s accep able as
ERs.
Each one
co esponds o a signal inse ion wi h di e en acknowledging
ou pu s signals o i s ansi ions. In
ou
app oach, we pe -
o m a heu is ic explo a ion seeking o di e en
ERA(z+)
and
E
RA
(z
-)
se s o each unc ion. We inally selec one acco ding
o he ollowing c i e ia:
0
Se s ha a e only acknowledged by he signal ha is being
decomposed (i.e. local acknowledgmen ) a e p e e ed.
0
I no se wi h local acknowledgmen is ound, he one wi h
leas acknowledgmen cos is selec ed. The cos is calcula ed
by inc emen ally de i ing he new
SG
a e signal inse ion.
As an example conside he
SG
o Figu e 4,c and he inse ion o
a new signal
x
o he unc ion
x
=
c
+
d.
A alid
SIP
se o
ERA(%+)
wouldbe he se o s a es {1100,0100,1110,0110},
whe e he s a e
{
1100) is he in u bo de o he inse ed unc-
ion.
A
alid
SIP
se
o
ERA?%-
would
be
he
se
o
s a es
{
1001,0001}.
Wi h such inse ion,
RA(%+)
will be acknowl-
edged by he ansi ion
z+
and
ERA(z-) by
z-.
Howe e ,
his inse ion is no unique.
Fo
he sake o simplici y, le
us
assume ha
a
and
d
a e also ou pu signals. Then an inse ion
wi h
ERA
(x+)
=
{
1100) would
be
also alid. In ha case, he
ansi ion
x+
would
be
acknowledged by he ansi ions
a-
and
d+.
4Di e en c i e ia, o cou se,may be used when we also conside he delay
o
he
esul ing implemen a ion,since hen keeping la e
a i ing
signals close
o
he
ou pu
is gene ally use ul and
can
equi e unbalanced ees.
am- ead-sbu
sbu - am-w i e
sbu -send-c l
S -
3i
-26ic
200
160
224
80
136
130
96
634
232
846
328
304
344
128
216
338
250
304
664
450
644
226
168
456
584
114
E
Table
2:
Expe imen al esul s.
5.4
Lib a y mapping
The logic decomposi ion o he non-inpu signals is comple ed
by a echnology mapping s ep aimed a eco e ing a ea and de-
lay based on a echnology-dependen lib a y o ga es. These
educ ions a e achie ed by collapsing small anin ga es in o com-
plex ga es, p o ided ha he ga es a e a ailable in he lib a y.
The collapsing p ocess is based on he Boolean ma ching ech-
niques p oposed by Mailho e al. [lo], adap ed o he exis ence
o asynch onous memo y elemen s and combina ional eedback
in speed-independen ci cui s. The o e all echnology mapping
p ocess has been e icien ly implemen ed using BDDs.
6
Expe imen al esul s
6.1
Resul s in decomposi ion and echnology mapping
The me hod o logic decomposi ion p esen ed in he p e ious
sec ions has been implemen ed and combined wi h he algeb aic
me hod p esen ed in [7]. The esul s ob ained om a se o
benchma ks a e shown in Table
2.
The benchma ks co espond
o hose p esen ed in [7] ha we e comple ely decomposed in o
2-inpu ga es.
The columns “1i e alsAa ches” epo he complexi y o he
ci cui s de i ed a e logic decomposi ion in o 2-inpu ga es. The
esul s ob ained
by
he me hod p esen ed in his pape (“new”) a e
signi ican ly be e han hose ob ained by he me hod p esen ed in
[7] (“old”). No e ha he lib a y used o he “new” expe imen s
was delibe a ely es ic ed o D,
S
and Rs la ches (i.e. wi hou
C-elemen s, since hey a e gene ally no pa o s anda d cell
lib a ies). This imp o emen is mainly achie ed because o wo
easons:
0
The supe io i y o Boolean me hods e sus algeb aic me h-
ods o logic decomposi ion.
0
The in ensi e use o di e en ypes o la ches o implemen
sequen ial unc ions compa ed o he C-elemen -based im-
plemen a ion in [7].
Howe e , he imp o ed esul s ob ained by using boolean
me hods a e
paid
in e ms
o
a signi ican inc ease
in
e ms
o
CPU
ime. This is he eason why he boolean me hod has been
combined wi h he algeb aic me hod (ins ead o subs i u ing i ), in
such a way ha boolean ela ions a e only sol ed o ind solu ions
226
ha imp o e he cos o he solu ions p e iously ob ained by using
algeb aic me hods.
6.2
The
cos
o
speed independence
The second pa o Table
2
is an a emp o e alua e he cos o im-
plemen ing an asynch onous speci ica ion as a speed-independen
ci cui . The expe imen s ha e been done as ollows.
Fo
each benchma k, he ollowing sc ip has been un in SIS,
using he lib a y
asynch. genlib: as g- o- ; sou ce
sc ip . ugged; map.
The esul ing ne lis s epo ed in col-
umn
a ea non-SI
could
be
conside ed a lowe bound
on
he
a ea
o
he ci cui ega dless o i s haza dous beha io (i.e. he ci -
cui only implemen s he co ec unc ion o each ou pu signal,
wi hou ega d o haza ds).
sc ip . ugged
is he bes known
gene al-pu pose op imiza ion sc ip o combina ional logic.
The columns labeled
a ea
SI
epo he esul s ob ained by
he me hod p oposed in his pape . We epo esul s
on
wo
s a egies o decomposi ion be o e mapping he ci cui on o a
lib a y:
0
Decompose all ga es in o 2-inpu ga es
(2i).
0
Decompose all ga es in o 3-inpu ga es
(3i).
Expe imen s ha e also been
un
o
4-inpu ga es, wi h
no
an-
gible imp o emen s. In bo h cases, decomposi ion and mapping
p ese e speed independence, since we do no use ga es (such as
MUXes) ha may ha e a haza dous beha io when he selec inpu
changes. The e is
no
clea e idence ha pe o ming an agg es-
si e decomposi ion in o 2-inpu ga es is always he bes app oach
o echnology mapping. The inse ion
o
mul iple- anou signals
o e s
oppo uni ies o sha e logic in he ci cui , bu also p ecludes
he mappe om aking ad an age o he lexibili y
o
mapping
ee-like
s uc u es. This ade-o mus
be
be e explo ed in
o hcoming wo k.
Looking a he bes esul s o non-SUS1 implemen a ions,
we
can conclude ha p ese ing speed independencedoes no in ol e
a signi ican o e head.
In
ou
expe imen s we ha e shown ha
he epo ed a ea is simila?. Some benchma ks we e e en mo e
e icien ly implemen ed by using he SI-p ese ing decomposi-
ion. We impu e hese imp o emen s o he e icien mapping o
unc ions in o la ches by using Boolean ela ions.
7
Conclusions and u u e
wo k
In
his pape we ha e shown a new solu ion o he p oblem o
mul i-le el logic syn hesis and echnology mapping o asyn-
ch onous speed-independen ci cui s. The me hod consis s o
h ee majo pa s. Pa
1
uses Boolean ela ions o compu e
a
se
o candida es o logic decomposi ion o he ini ial complex ga e
ci cui implemen a ion. Thus each complex ga e
F
is i e a i ely
spli in o
a
wo-inpu combina ional
o
sequen ial ga e
G
a ailable
in he lib a y and wo ga es
HI
and
H2
ha a e simple han
F,
while p ese ing he o iginal beha io and speed-independence o
he ci cui . The bes candida es o
HI
and
H2
a e selec ed o he
nex s ep, p o iding he lowes cos in e ms o implemen abili y
and new signal inse ion o e head. Pa
2
o he me hod pe o ms
he ac ual inse ion o new signals
o
HI
and/o
Hz
in o
he s a e
g aph speci ica ion, and e-syn hesizes logic om he la e . Thus
pa s
1
and
2
a e applied o each complex ga e ha canno be
mapped in o he lib a y. Finally, Pa 3 does lib a y ma ching o
eco e a ea and delay.
This me hod imp o es signi ican ly o e p e iously known
echniques
[l,
8,
71.
This is due o he signi ican ly la ge op i-
miza ion space exploi ed by using
(1)
Boolean ela ions o de-
composi ion and
(2)
a b oade class o la ches6. Fu he mo e, he
abili y o implemen sequen ial unc ions wi h
SR
and
D
la ches
signi ican ly imp o es he p ac icali y o he me hod.
'Taking he bes esul s om
21
and
31
he o al is
8582
men s, he only limi being he size
o
he space o be explo ed.
ac , any sequen ial ga e could be used, including, e.g., asymme ic
C
ele-
In he u u e
we
a e planning o imp o e he Boolean ela ion
solu ion algo i hm, aimed a inding a se
o
op imal unc ions
compa ible wi h a Boolean ela ion. This is essen ial in o de o
imp o e he CPU imes ancl syn hesize success ully mo e complex
speci ica ions.
Re e ences
P.
A.
Bee el and
T.
H-Y.
Meng. Au oma ic ga e-le el syn hesis
o speed-independen ci cui s.
In
P oceedings o he In e na ional
Con e ence on Compu e -AidedDesign,
No embe 1992.
R.
K.
B ay on
and
E
So nenzi.
An
exac minimize o boolean ela-
ions. In
P oceedings
o
he In e na ional Con e ence on Compu e -
Aided Design,
pages 316-319, No embe 1989.
S.
Bums. Gene al condi ions
o
he decomposi ion o s a e holding
elemen s. In
In e na io~nal Symposium on Ad anced Resea ch in
Asynch onousCi cui s a'nd Sys ems, Aim, Japan,
Ma ch 1996.
T.-A. Chu.
Syn hesis o Sel - imed
VLSl
Ci cui s om G aph-
heo e ic SpeciJica ions.
PhD hesis, MIT, June 1987.
J. Co adella,
M.
Kishine sky,
A.
Kond a ye , L. La agno, and
A.
Yako le . Comple e s a e encoding based on he heo y o egions.
In
In e na ional Sympos,ium on Ad ancedResea ch in Asynch onous
Ci cui s and Sys ems, Am, Japan,
Ma ch 1996.
M.
A. Kishine sky,
A.
Y.
Kond a ye , A.
R.
Taubin, and V.
I.
Va -
sha sky.
Concu en Ha dwa e. The Theo y and P ac ice o Sel -
Timed Design.
John Wiley and Sons L d., 1993.
A.
Kond a ye ,
J.
Co adella,
M.
Kishine sky, L. La agno, and
A.
Yako le . Technology mapping o speed-independen ci cui s:
decomposi ion and esyn hesis. In
Thi d In e na ional Symposium
on Ad ancedResea ch i Asynch onous Ci cui s and Sys ems, Eind-
ho en,
Ap il 1997.
A.
Kond a ye ,
M.
Kishine sky, B. Lin,
P.
Vanbekbe gen, and
A.
Yako le . Basic ga e implemen a ion
o
speed-independen
ci -
cui s. In
P oceedings
o
he Design Au oma ion Con e ence,
1994.
L. La agno and
A.
Sangio anni-Vincen elli.
Algo i hms o syn he-
sis and es ing
o
asynch onousci cui s.
Kluwe Academic Publish-
e s, 1993.
E
Mailho and
G.
De Micheli. Algo i hms
o
echnology map-
ping based on bina y decision diag ams and on boolean ope a-
ions.
IEEE T ansac ions on Compu e -Aided Design,
12(5):599-
620, May 1993.
G.
De Micheli.
Syn hesis and Op imiza ion
o
Digi al Ci cui s.
McG aw-Hill,
Inc.,
1994.
En ic Pas o , Jo di Con adella, Alex Kond a ye , and
O iol
Roig.
S uc u al me hods
o
he syn hesis
o
speed-independen ci cui s.
In
P oc. o Eu opean Design and Tes Con e ence,
pages 340
-
347,
Pa is(F ance), Ma ch 19196.
P.
Siegel and
G.
De Micheli. Decomposi ion me hods
o
lib a y
binding o speed-independen asynch onous designs.
In
P oceedings
o he In e na ional Co ge ence
on
Compu e -Aided Design,
pages
558-565, No embe 1904.
P.
Siegel,
G.
De Micheli, and D. Dill. Au oma ic echnology map-
ping
o
gene alized undamen al mode asynch onous designs.
In
P oceedings o he Design Au oma ion Con e ence,
June 1993.
P.
Vanbekbe gen, B. Lin,
G.
Goossens, and
H.
De Man.
A
gene -
alized s a e assignmen heo y o ans o ma ions
on
Signal T an-
si ion G aphs. In
P oceedings o he In e na ional Con e ence on
Compu e -Aided Design,
pages 11 2-1 17, No embe 1992.
V.
I.
Va sha sky,
M.
A.
Kishine sky, V. B. Ma akho sky, V.
A.
Peschansky,L.
Y.
Rose blum,
A.
R. Taubin, and B.
S.
Tzi lin.
Sel -
imed Con ol
o
Concu en P ocesses.
Kluwe Academic
Pub-
lishe , 1990. (Russian edi ion: 1986).
Y.Wa anabe and
R.K.
B ay on. Heu is ic minimiza ion o mul iple-
alued ela ions.
IEEE T ansac ions on Compu e -Aided Design,
12(10):1458-1472, Oc obe 1993.
Y.Wa anabe, L.M.Gue a, and R.K. B ay on. Pe missible unc ions
o
mul iou pu componen s in combina ional logic op imiza ion.
IEEE T ansac ions on Compu e -Aided Design,
15 (7x732-744, July
1996.
227