1108 IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 17, NO. 11, NOVEMBER 1998
S uc u al Me hods o he Syn hesis
o Speed-Independen Ci cui s
En ic Pas o , Jo di Co adella, Membe , IEEE, Alex Kond a ye , Membe , IEEE, and O iol Roig
Abs ac —Asynch onous ci cui s can be modeled as concu en
sys ems in which e en s a e in e p e ed as signal ansi ions.
The syn hesis o concu en sys ems implies he analysis o a
as s a e space ha o en equi es compu a ionally expensi e
me hods. This wo k p esen s new me hods o he syn hesis o
speed-independen ci cui s om a new pe spec i e, o e coming
bo h he analysis and compu a ion complexi y bo lenecks.
The ci cui s a e speci ied by ee-choice signal ansi ion g aphs
(STG’s), a subclass o in e p e ed Pe i ne s. The syn hesis ap-
p oach is di ided in o he ollowing s eps: co ec ness, bina y
coding, implemen abili y condi ions, and logic syn hesis. Each
s ep is e icien ly implemen ed by applying a se o s uc u al
echniques ha analyze STG’s wi hou explici ly enume a ing he
unde lying s a e space.
Expe imen al esul s show ha ci cui s can be gene a ed om
speci ica ions ha exceed in se e al o de s o magni ude he
la ges STG’s e e syn hesized—wi h o e 10
27
s a es. Compu a-
ion imes a e also d ama ically educed. Ne e heless, he quali y
o esul s does no su e om he use o s uc u al echniques.
Index Te ms— Asynch onous ci cui s, Pe i ne s, speed-
independen syn hesis.
I. INTRODUCTION
ASYNCHRONOUS ci cui s p omise a numbe o impo -
an ad an ages o he design o la ge digi al ci cui s.
Thei modula i y, po en ial low-powe consump ion, a e age-
case compu a ion ime, and elimina ion o he clock dis ibu-
ion p oblem ha e encou aged hei ex ensi e analysis. How-
e e , any asynch onous implemen a ion mus sa is y much
mo e es ic i e condi ions han i s synch onous coun e pa .
Asynch onous ci cui s mus be no only unc ionally equi a-
len o he speci ica ion bu also ee o haza ds—undesi ed
swi ching ac i i y due o he skew o ga e delays.
Speed-independen ci cui s (SI ci cui s) is a b oadly used
design s yle o asynch onous implemen a ions. SI ci cui s ely
on he unbounded ga e delay model, which assumes unknown
bu ini e delays on he ga es, and skew a he wi es bounded
by he delay o he as es ga e. Thus, he co ec ness o
he ci cui equi es he assump ion ha some wi e o ks a e
Manusc ip ecei ed No embe 13, 1997; e ised Ma ch 30, 1998. This
wo k was suppo ed in pa by CICYT unde G an TIC98-0410. This pape
was ecommended by Associa e Edi o A. Saldanha.
E. Pas o is wi h he Depa men o Compu e A chi ec u e, Uni e si a
Poli ´ecnica de Ca alunya, Ba celona 08034 Spain (e-mail: [email p o ec ed]).
J. Co adella is wi h he Depa men o So wa e, Uni e si a Poli ´
ecnica
de Ca alunya, Ba celona 08034 Spain (e-mail: [email p o ec ed]).
A. Kond a ye is wi h he Compu e A chi ec u e Labo a o y, Uni e si y
o Aizu, Aizu-Wakama su 965 Japan (e-mail: [email p o ec ed]).
O. Roig is wi h Na ional Semiconduc o Co p., San a Cla a, CA 95052
USA (e-mail: [email p o ec ed]).
Publishe I em Iden i ie S 0278-0070(98)08591-1.
isoch onic [1]. SI ci cui s a e obus o pa ame e a ia ions,
i.e., he esponse ime o an SI ci cui subjec ed o empe a u e
o ol age modi ica ions may a y, bu he ci cui keeps
wo king co ec ly. Addi ionally, an SI ci cui does no need
any modi ica ion o gua an ee i s co ec ness a e a echnology
mig a ion ( he alidi y o isoch onic o ks mus be checked,
howe e ). The mos obus delay model, delay-insensi i e
ci cui s, also assumes unbounded wi e delays. Un o una ely,
he class o delay-insensi i e ci cui s is e y small om he
p ac ical poin o iew [1].
A wide ange o syn hesis echniques o asynch onous
ci cui s ely on e en -based models, such as Pe i ne s (PN’s)
[2] o change diag ams [3]. PN’s a e a powe ul o malism o
model concu en sys ems ha g ace ully cap u es he no ions
o causali y, concu ency, and con lic be ween e en s. As
a model, hei mos in e es ing ea u e is he capabili y o
implici ly desc ibing a as s a e space by a succinc ep e-
sen a ion. Hence, PN’s ha e been chosen by many au ho s as
a o malism o desc ibe he beha io o asynch onous ci cui s
by in e p e ing he e en s as signal ansi ions, hus coining
he e m signal ansi ion g aph (STG) [4], [5].
Each eachable ma king o an STG has assigned a bina y
ec o wi h he alue o he ci cui signals in ha ma king.
De i ing logic equa ions om an STG equi es he gene a ion
o he bina y codes o all ma kings. Cu en ly, mos syn hesis
ools [6]–[8] pe o m an exhaus i e oken low analysis o
ob ain he comple e eachabili y g aph o he PN and all
bina y ec o s. Un o una ely, he eachabili y g aph o highly
concu en sys ems can be exponen ial in he size o he
STG ha leads o he well-known s a e explosion p oblem.
Some e o s ha e been de o ed o p opose s uc u al me hods
o syn hesis [9], [10], bu hey ha e been usually de ised
o es ic ed classes o PN’s ha comp omise he po en ial
exp essi eness o his o malism.
This wo k p esen s a s uc u al me hodology o he syn he-
sis o SI ci cui s om STG’s. The p oposed echniques ha e
polynomial complexi y i he unde lying PN is ee choice
[11], [12], and can be e icien ly ex ended o he class o PN’s
ha can be co e ed by s a e machines [13].
The p oposed s uc u al echniques a e based on he analysis
o he concu ency ela ions o STG’s [5], and he gene a ion
o co e ing cubes ha app oxima e he eachable ma kings.
Addi ional in o ma ion ob ained om he s a e machines o he
STG allows one o e ine he ini ial co e ing cubes, inc easing
he accu acy o he app oxima ions. This me hodology elim-
ina es he s a e explosion p oblem by a oiding he explici
gene a ion o all he ma kings in he STG. E en hough
0278–0070/98$10.00 1998 IEEE
PASTOR e al.: SYNTHESIS OF SPEED-INDEPENDENT CIRCUITS 1109
he concu ency ela ions ha e been p e iously applied o
syn hesis [10], [14], his wo k gene alizes he use o hese
ela ions, educing he gap be ween s uc u al and s a e-based
app oaches.
We aim a complemen ing he exis ing ools by p o iding al-
e na i e and e icien syn hesis algo i hms o s a e-machine-
co e able STG’s, which accoun o a la ge numbe o STG’s
used o ci cui design. The a ea and delay esul s o he SI
ci cui s syn hesized by applying ou me hod a e p esen ed and
compa ed wi h hose ob ained by p e ious syn hesis ools.
This pape is o ganized as ollows. The o mal no ions
on Pe i ne s and signal ansi ion g aphs a e p esen ed
in Sec ion II. The implemen abili y condi ions o speed-
independen ci cui s a e analyzed in Sec ion III. Sec ion IV
illus a es he s uc u al syn hesis amewo k and i s e iciency
by means o wo examples. To a oid he s a e explosion
p oblem, Sec ion V p oposes a me hod o de i e app oxi-
ma ions o he eachabili y g aph om he s uc u e o he
STG. Sec ion VI desc ibes how Boolean unc ions can be
ob ained om hese app oxima ions. A s a egy o inc ease he
accu acy o such app oxima ions is in oduced in Sec ion VII.
The o e all logic-minimiza ion amewo k is desc ibed in
Sec ion VIII, and u he minimiza ions a e ou lined in he
Appendix. Se e al expe imen al esul s and e iciency analysis
a e p esen ed in Sec ion IX. Sec ion X concludes his pape .
II. BASIC NOTIONS AND DEFINITIONS
In his sec ion, we b ie ly ecall some o he basic de ini ions
on logic unc ions, Pe i ne s, and signal ansi ion g aphs. Fo
mo e de ailed in o ma ion on hese opics, we e e he eade
o [5], [12], and [15]–[17].
A. Logic Func ions
An incomple ely speci ied - a iable logic unc ion is a
mapping . Each elemen is
called a e ex. The se o e ices whe e e alua es o 1,
0, and a e called on-, o -, and dc-se s and a e deno ed by
on ,o , and dc , espec i ely. A li e al is ei he a
a iable o i s complemen .Acube c is a se o li e als
such ha i , hen , and ice e sa. Cubes can
also be ep esen ed as an elemen , in which alue
“0” deno es a complemen ed a iable , alue “1” deno es
a a iable , and indica es ha he a iable is no in he
cube. A co e is a se o implican s ha con ains he on-se
and does no in e sec wi h he o -se .
B. Pe i Ne s and STG’s
A PN is a ou - uple , whe e is he
se o places, is he se o ansi ions,
is he low ela ion, and is he ini ial ma king. Gi en a
node , i s pos se and p ese a e deno ed by and
, espec i ely. A ma king o a PN is an assignmen o a
nonnega i e in ege o each place. I is assigned o place
by ma king , we will say ha is ma ked wi h okens,
i.e., .Apa h in a PN is a sequence o
nodes such ha . A pa h is
called simple i no node appea s mo e han once on i . A s a e
machine (SM) is a PN such ha each ansi ion has exac ly
one inpu place and one ou pu place. A ee choice (FC) ne
is a PN such ha e e y a c om a place is ei he a unique
ou going a c o a unique incoming a c o a ansi ion.
A ansi ion is enabled in a ma king , deno ed by ,
when all places in a e ma ked. An enabled ansi ion in
i es, emo ing one oken om each place in and adding
one oken o e e y place in . This p oduces a new ma king
( ). A ma king is eachable om i he e
is a sequence o i ings ha ans o ms in o
( ); hence is a easible sequence.
The se o eachable ma kings om is deno ed by .
The g aphical ep esen a ion o a eachabili y se wi h he
e ices co esponding o ma kings and a cs co esponding o
ansi ions be ween ma kings is called a eachabili y g aph
(RG). Two ansi ions and a e concu en i he e exis s
a ma king in which bo h ansi ions a e enabled and he i ing
o o does no disable he o he .
APNisli e i e e y ansi ion can be in ini ely enabled
h ough some easible sequence o i ings om any ma king
in . A PN is sa e i no ma king in can assign mo e
han one oken o any place. A place is edundan i i s emo al
p ese es he se o easible sequences in he PN. In he sequel,
we will assume ha all he conside ed PN’s a e ee choice,
li e,sa e, and do no con ain edundan places.1
A PN can be decomposed in o a po en ially exponen ial
se o s ongly connec ed s a e machines, also named SM-
componen s (SM’s) [11]. In pa icula , li e and sa e ee-
choice PN’s a e co e ed by one- oken SM’s; ha is, SM’s ha
con ain exac ly one oken [11]. Compu ing SM’s is educed
o sol ing a linea p og amming model, wi h polynomial
complexi y [18]. An SM-co e (SMC) is a subse o one-
oken SM’s such ha e e y place in a PN is included a leas
in one SM.
An STG is a iple , whe e is i s
unde lying PN, is a se o inpu and ou pu signals,
and is a labeling unc ion , in which he
ansi ions a e in e p e ed as alue changes on ci cui signals.
Rising and alling ansi ions o a signal a e deno ed
by and , espec i ely, while deno es a gene ic ising
o alling ansi ion. Mul iple ansi ions o a signal will be
dis inguished by means o indexes, e.g., . (In igu es,
ins ead o indexes o , will be used.) An STG is
au oconcu en i i con ains a pai o concu en ansi ions
o he same signal.
An STG is g aphically ep esen ed as a di ec ed g aph wi h
ansi ions deno ed by hei names and places by ci cles, whe e
places ha ha e only one ansi ion in i s p ese and pos se
a e usually omi ed. Also, ansi ions o inpu signals a e
unde lined. Fig. 1(a) depic s a ee-choice STG, aken om
[19], ha will be used h oughou his wo k. The example
con ains inpu ( ) and ou pu ( )
signals. The co esponding eachabili y g aph o he STG is
depic ed in Fig. 1(b). Fig. 2 depic s h ee SM’s ha co e
he STG.
1Checking o li eness, sa eness, and edundan places can be done in
polynomial ime o FC ne s [12].
1110 IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 17, NO. 11, NOVEMBER 1998
(a) (b)
Fig. 1. (a) STG example and (b) co esponding eachabili y g aph.
Fig. 2. SM-componen s o example depic ed in Fig. 1(a).
Each ma king o an STG is encoded wi h a bina y code
o signal alues by means o a labeling unc ion
, whe e deno es he bina y alue o signal
. The unc ion mus consis en ly encode he STG ma k-
ings; ha is, no ma king can ha e an enabled ising
( alling) ansi ion i
.In a nonau oconcu en STG, ansi ion is a p edecesso
o i he e exis s a easible sequence ha does
no include o he ansi ions o signal . Con e sely, is a
successo o —we will also say ha he pai is
adjacen . The se o p edecesso s (successo s) o is deno ed
by p e (nex . In Fig. 1(b), ansi ion has wo
successo ansi ions and , while a he same ime
is a single p edecesso o bo h ising ansi ions.
An STG is called ou pu semimodula i no ou pu signal
ansi ion enabled a any eachable ma king can be disabled
by he ansi ion o ano he signal [20]. I an STG is ou pu
semimodula , hen i can be implemen ed wi hou p oducing
unspeci ied changes o he ou pu signals; ha is, wi hou
in oducing haza ds.
C. Signal Regions
To de i e he co espondence among he signal ansi ions,
he eachable ma kings, and he p ope ies o he speci ica ion,
di e en signal egions a e de ined.
PASTOR e al.: SYNTHESIS OF SPEED-INDEPENDENT CIRCUITS 1111
TABLE I
SIGNAL REGIONS FOR THE EXAMPLE IN FIG.1
The exci a ion egion ER is he se o ma kings in
which ansi ion is enabled. I can be shown ha , o li e
and sa e ee-choice STG, exci a ion egions a e connec ed se s
o ma kings. The quiescen egion QR is he maximal
se o ma kings ha a e eached om ER a e i ing
wi hou enabling any o he ansi ion . The es ic ed
quiescen egion QR is he subse o he quiescen egion
QR ha does no con ain ma kings o o he QR’s o
signal .
The gene alized ising ( alling) exci a ion egion o signal
is he union o all exci a ion egions ER ER ,
deno ed by GER and GER . The gene alized
one (ze o) quiescen egion o is he union o all
quiescen egions QR QR , and i is deno ed
by GQR GQR . Fig. 1(b) depic s he exci a ion
egions ER ,ER ,ER o he ou pu
signal .
Regions a e collec ions o ma kings; hence, we use he
ope a o o de ine he cha ac e is ic unc ion o he bina y
codes o he ma kings in a se o egion. Addi ionally, we
will de ine he dc-se as he se o nonused bina y codes, i.e.,
. Examples o o he egions and bina y codes
o signal can be ound in Table I.
D. S a e Coding
An STG is said o sa is y he comple e s a e coding (CSC)
p ope y i , when he same bina y code is assigned o wo
di e en ma kings, he ou pu signals enabled a bo h ma kings
a e iden ical, i.e., . An e icien
echnique o e i y he CSC p ope y can be de i ed i ins ead
o analyzing indi idual ma kings, he encoding p ope ies a e
checked in e ms o se s o ma kings ela ed o he s uc u e
o he STG, i.e., GER GQR
GER GQR .
A mo e es ic i e p ope y, he unique s a e coding (USC)
condi ion, holds i all eachable ma kings o he STG a e
assigned a unique bina y code, i.e.,
. The example in Fig. 1 has a USC
con lic because ma kings and sha e he bina y code
(1111). Howe e , he STG sa is ies he CSC p ope y because
ou pu ansi ion is enabled a nei he no (i.e., no CSC
con lic exis s).
E. Nex -S a e Func ion
The de i a ion o a ci cui ha implemen s he beha io
speci ied by an STG consis s in inding a logic-ga e ealiza ion
o he nex -s a e unc ion o each ou pu signal. The nex -s a e
unc ion, , o a signal is
de ined as ollows [21]:
i GER GQR
i GER GQR
o he wise.
Fo any STG ha ul ills he consis ency and CSC condi-
ions, is consis en ly de ined, i.e., on o dc
is a comple e pa i ion o . No e ha o any pai o
ou pu signals and ,dc dc DC, whe e DC
deno es he dc-se o he eachabili y g aph.
An implemen a ion o he nex -s a e unc ion by a co e
is co ec i
on on DC (1)
III. SPEED-INDEPENDENCE SYNTHESIS CONDITIONS
The de i a ion o an SI ci cui om an STG speci ica ion
equi es wo ypes o co ec ness condi ions [20].
•Speci ica ion co ec ness condi ions: Consis ency, ou pu
semimodula i y, and CSC. These condi ions ha e been
de ined in Sec ion II and gua an ee ha a co ec SI ci cui
can be de i ed om he STG speci ica ion.
•Implemen a ion co ec ness condi ions: These condi ions
gua an ee ha a gi en ci cui implemen s he desi ed
beha io . We can dis inguish wo ypes o condi ions.
— Co ec nex -s a e unc ion condi ion (1).
— Condi ions o haza d eeness, which depend on
he speci ic ci cui a chi ec u e chosen o he im-
plemen a ion. These condi ions will be discussed in
Sec ion III-B.
Consis ency and CSC a e necessa y and su icien condi-
ions o he exis ence o a consis en nex -s a e unc ion. Ou -
pu semimodula i y is a necessa y condi ion o he exis ence
o a haza d- ee implemen a ion o he beha io . In he case
whe e all nex -s a e unc ions can be co ec ly implemen ed by
a haza d- ee complex ga e, he ci cui is gua an eed o be SI
[5]. The implemen abili y condi ions o SI ci cui s ha e been
exhaus i ely in es iga ed in [7], [17], [19], and [22].
Howe e , i is no always possible o implemen each nex -
s a e unc ion wi h one complex ga e. In gene al, ga e lib a ies
impose cons ain s on he size and unc ionali y o he logic
unc ions ha can be implemen ed wi h only one ga e.
This sec ion i s in oduces h ee di e en implemen a ion
a chi ec u es and discusses su icien condi ions o ob aining
co ec implemen a ions o he nex -s a e unc ions. I is shown
ha hese condi ions can be o mula ed in e ms o equi e-
men s o he co e s o he co esponding signal egions. The
es o he sec ion is de o ed o discussing he condi ions o
haza d eeness ha gua an ee he syn hesis o an SI ci cui .
One o he a chi ec u es is chosen o he illus a ion o
he me hodology o s uc u al syn hesis h oughou he pape .
Howe e , he sugges ed me hods a e easily adap ed o o he
a chi ec u e s yles as well.
A. Implemen a ion A chi ec u es
1) A omic Complex Ga e Pe Signal: This is he ini ial a -
chi ec u e o SI ci cui s s udied in [5] and [23]. The ci cui
1112 IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 17, NO. 11, NOVEMBER 1998
Fig. 3. Implemen a ion a chi ec u es.
is implemen ed as a ne wo k o a omic ga es, each one
implemen ing one ou pu signal. The Boolean unc ion o each
ga e can be ep esen ed as a sum o p oduc s (SOP). A simple
example o such ga e is p esen ed in Fig. 3(a). Each a omic
ga e con ains a combina ional pa and a possibly sequen ial
pa implemen ed as an in e nal eedback. The delay be ween
i s “ANDing” and “ORing” nodes and he in e nal eedback is
assumed o be negligible. In he igu es, he ga e ep esen a ion
is used o deno e he implemen ed logic unc ion, bu he ac ual
implemen a ion is esol ed on he ansis o le el.
The ci cui is assumed o be de i ed by building a co ec
co e o [acco ding o (1)] and implemen ed by a single
complex ga e. I was shown in [5] ha o co ec STG’s,
his equa ion gi es necessa y and su icien condi ions o he
speed independence o he implemen a ion (i.e., no addi ional
a chi ec u e-speci ic condi ions a e needed). Howe e , he
equi emen o implemen each co e by a single ga e migh
be qui e un ealis ic in p ac ice, which is he weakes poin o
his app oach.
2) A omic Complex Ga e Pe Exci a ion Func ion: This
a chi ec u e was sugges ed and s udied ex ensi ely in a numbe
o pape s, e.g., [20] and [24]. I assumes ha a sepa a e
memo y elemen is used o p oduce an ou pu signal. The
se and ese exci a ion unc ions o signal
a e ed o he memo y elemen . They a e implemen ed as
a omic complex ga es. Fig. 3(b) shows an example o such
a chi ec u e wi h a C-la ch used as a memo y elemen .
Su icien condi ions ha gua an ee he implemen a ion co -
ec ness o he nex -s a e unc ion a e he ollowing:
GER on
GER o (2)
The se unc ion o signal mus be u ned on e e y ime
some ising ansi ion is enabled and u ned o be o e
he enabling o any alling ansi ion ; simila ly o he
ese unc ion. Howe e , he condi ions in (2) do no gua an ee
an SI ci cui . Su icien ex a condi ions o haza d eeness
will be discussed in Sec ion III-B. I is possible o show he
exis ence o an implemen a ion in his a chi ec u e o any
STG sa is ying he CSC condi ion [5].
Fig. 4. Th ee speed-independen implemen a ions o signal
d
.
3) A omic Complex Ga e Pe Exci a ion Region: Signals in
his a chi ec u e a e c ea ed using ne wo ks o a omic complex
ga es o implemen he se and ese unc ions o he memo y
elemen . Each ansi ion is implemen ed by a single ga e,
which is hen connec ed o an OR-ga e whose ou pu is in u n
ed in o he memo y elemen . As a esul , smalle complex
ga es a e used. The basic s uc u e o his a chi ec u e is shown
in Fig. 3(c).
In his a chi ec u e, e e y ga e a he i s le el
o he se unc ion implemen s he beha io o a single
ising ansi ion . This ga e mus be u ned on e e y ime
ansi ion is enabled and u ned o be o e he enabling o
any alling ansi ion ; simila ly o he ese unc ion.
In a nonau oconcu en STG, only one ansi ion o he sig-
nal can be enabled a a ce ain ins an . The e o e, he p oposed
a chi ec u e e ol es unde a one-ho encoding discipline o he
ga es a he i s le el o he se and ese ne wo ks. Only one
o he ga es can be “ON” a he same ime, being esponsible
o he ou pu signal o swi ch. The ising and alling signal
swi ching is p oduced due o he al e na e ac i a ion o se
and ese ne wo ks.
The implemen a ion co ec ness condi ion o he co e s
is simila o condi ion (2) bu is limi ed o only use i s
exci a ion and quiescen egion
ER ER QR DC (3)
The de ailed discussion on he su icien condi ions o ensu e
an SI implemen a ion wi h his a chi ec u e can ound in [7]
and [19]. A gene al discussion on hese condi ions is p esen ed
in Sec ion III-B.
Fig. 4 shows he implemen a ions o signal om he STG
in Fig. 1 in all h ee a chi ec u es.
Mo e ecen de elopmen s aim a he decomposi ion o
complex ga es used o implemen each exci a ion egion. The
goal o hese echniques is o gua an ee he implemen abili y
o he ci cui in a pa icula ga e lib a y o wi h a ne wo k o
wo-inpu ga es [25], [26].
F om he e iew o he possible a chi ec u es, we can
conclude ha he a chi ec u e-speci ic condi ions o co ec
implemen a ions can always be o mula ed in e ms o co e -
ing he signal egions. In Sec ion VI, i will be shown how
o ob ain app oxima ions o each signal egion by using
he in o ma ion con ained in he s uc u e o he STG a he
han i s RG. The e o e, he syn hesis echniques sugges ed in

PASTOR e al.: SYNTHESIS OF SPEED-INDEPENDENT CIRCUITS 1113
(a) (b) (c)
Fig. 5. (a) STG and co e ing cubes o places, (b) eachabili y g aph, and (c) e ined co e s.
his wo k can be adap ed o any implemen a ion a chi ec u e.
Fu he , we will illus a e he syn hesis me hod in applica ion
o he a chi ec u e in Fig. 3(b), when he se and ese unc ions
a e implemen ed as a omic complex ga es. No e, howe e ,
ha he e a e no s ic bo de s be ween di e en a chi ec u e
s yles and, o op imiza ion pu poses, we can easily admi he
implemen a ion o one signal o a ci cui as an a omic complex
ga e while he o he is implemen ed by he se and ese
ne wo ks. These issues a e mainly add essed in Sec ion VIII,
whe e he ci cui minimiza ion loop is discussed.
B. Condi ions o Haza d F eeness
In he p e ious sec ion, we in oduced h ee main ypes
o implemen a ion a chi ec u es and o mula ed he condi ions
ha mus be sa is ied by Boolean unc ions o ga es o ensu e
he p ope alues o implemen ed signals. Howe e , his
unc ional co ec ness is no su icien o gua an ee he haza d-
ee beha io o a ci cui . E en when he Boolean unc ions o
ga es a e de ined acco ding o he equi emen s o Sec ion III-
A, he beha io o he ci cui can be haza dous due o he
delays in he p opaga ion o signals h ough he ga es. This
mus be a oided in speed-independen designs. In his sec ion,
we in oduce he su icien condi ions ha will cap u e he
absence o haza ds du ing he ope a ion o a ci cui .
F om now on, unless i is poin ed ou explici ly, we assume
ha each ou pu signal o he STG is implemen ed by complex
ga es o se and ese unc ions—a omic complex ga e pe
exci a ion unc ion—wi h a C-la ch as memo y elemen .
The co ec ness o he se and ese co e s is no su icien
o gua an ee he SI beha io o he implemen a ions. Addi ion-
ally, hese co e s mus be mono onic. In ui i ely,
is said o be mono onic i i changes exac ly wice in any
sequence o i ing ansi ions, ising a a ma king in GER
GER and alling ei he inside GQR GQR
o be o e en e ing GER GER .
Fo example, (see Fig. 1), assume ha co e s ma k-
ings and . is co ec , bu i he ci cui ollows he
sequence , i migh p oduce an undesi ed
gli ch a unc ion ha migh e en ually be
p opaga ed o ou pu .
The ollowing p ope y desc ibes how he se and ese
co e s can be e i ied o be mono onic explo ing he eachable
ma kings o he STG a he han i s easible i ing sequences.
P ope y 1 [Mono onic Co e s]: A se unc ion is
said o be mono onic i GQR such ha i s code
is co e ed by , hen GQR ,
he bina y code is also co e ed by . A ese
unc ion is said o be mono onic i GQR
such ha i s code is co e ed by , hen
GQR , he bina y code is also co e ed
by .
Fo he pa icula case o he a omic complex ga e pe
exci a ion egion a chi ec u e, each co e mus sa is y
an addi ional mono onic condi ion designed o gua an ee a
haza d- ee al e na ing one-ho ac i a ion o se and ese
ne wo ks. A co e canno eely use i s QR as dc-se
because some o i s ma kings may be sha ed by o he co e s
o signal . In Fig. 1, ma king is sha ed in he QR’s o bo h
ansi ions and . I he co e includes
ha sha ed ma king, bo h co e s and will
be inco ec ly exci ed (no necessa ily a he same ime) when-
e e ansi ion is expec ed o be i ed. The addi ional
condi ion o gua an ee he mono onic al e na ing ac i a ion o
se and ese ne wo ks can be exp essed by using he es ic ed
quiescen egion as
ER ER QR DC (4)
Imposing es ic ions on he ma kings ha can be co e ed o
gua an ee he one-ho enabling discipline is equi alen o he
single en ance cons ain desc ibed by o he au ho s [7], [24].
Howe e , in o de o e i y his es ic ion, es ic ed quiescen
egions a e easie o build and s uc u ally cha ac e ize han
i ing sequences.
The esul p o ed in [7] and [19] is he ollowing: “I he
co ec se and ese co e s sa is y he mono onici y condi ions,
he ci cui implemen a ion is speed independen .” The main
pu pose o he ollowing sec ions is o show how he co ec -
ness and mono onici y condi ions can be ensu ed o he se
and ese co e s wi hou gene a ing he eachabili y g aph o
he STG.
IV. APPLYING STRUCTURAL METHODS TO SYNTHESIS
This sec ion gi es an in ui i e pic u e o he p oposed
s uc u al me hods by using he example depic ed in Fig. 5(a).
The echniques he e desc ibed a e undamen al o suppo he
o e all syn hesis p ocess keeping i s complexi y polynomial.
1114 IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 17, NO. 11, NOVEMBER 1998
(a) (b) (c)
Fig. 6. Signal inse ion. (a) STG and co e ing cubes o places, (b) eachabili y g aph, and (c) implemen a ion o signal
y
.
Le us assume ha we wish o de i e a logic unc ion o
co e he exci a ion egion o [deno ed ER ]. This
egion co esponds o he se o ma kings in which place
is ma ked. The encoded eachabili y g aph ob ained om
he STG is depic ed in Fig. 5(b), in which ER is also
shadowed.
By a simple s uc u al analysis ha akes polynomial ime
[12], we can deduce ha he STG has an unde lying ee-
choice PN in which each SM has exac ly one oken. We
can also de i e a se o SM’s ha co e he ne (SM-co e ).
In his case, wo SM’s can be ob ained, namely, he se s
o nodes SM
and SM .
Ou pu pose is o calcula e a se o cubes ha sa ely
co e ER .2An ini ial single cube app oxima ion can be
calcula ed as ollows. I a signal ansi ion can i e while a
gi en place is ma ked, wi hou emo ing he oken om he
place, hen he alue o he signal is unknown while he place
is ma ked. Since ansi ions and can i e when is
ma ked, hen he alue o and is unknown in . On he
con a y, he alue o can be exac ly de e mined by analyzing
he o de ing ela ion o and wi h . Thus, he cube
can be de i ed o .
Howe e , we can easily de ec ha his cube is
an o e es ima ion o ER because he bina y code
which is ou side ER is also co e ed. Assuming o
be a co e cube o ER leads o he e oneous conclusion
on he enabling o in . No e ha o e es ima ion does
no necessa ily happen in he app oxima ion p ocess: o places
and , he cubes can be exac ly calcula ed, i.e., and
, espec i ely. To igh wi h he possible o e es ima ions,
wo s a egies can be applied.
1) Co e e inemen : Re ining he place co e s by analyzing
he concu en ela ions wi h o he places. To ob ain a
mul icube app oxima ion, we use he ac ha can
only be simul aneously ma ked wi h ,,o . The
2ER
(
y
+)
is he se o bina y codes o ma kings in ER
(
y
+)
. The co e
mus con ain ER
(
y
+)
(on-se ) and may con ain codes om he dc-se .
co e o should be in e sec ed wi h he conjunc ion
o he co e s o , , and [see Fig. 5(c)]. Then, he
unc ion (10 ) ( 01) co ec ly co e s ER [see
Fig. 6(c)]. No e ha , in gene al, se e al e inemen s may
be needed.
2) Signal inse ion: Inse ing s a e signals in he same way
as sol ing encoding con lic s, disambigua ing co e s
whose in e sec ion p oduces con adic ions o syn hesis.
This is illus a ed in Fig. 6, in which a new signal
dis inguishes he co e s o and . Then, he cube
co ec ly co e s ER [see Fig. 6(c)].
In gene al, bo h me hods can be combined o ob ain a co ec
se o co e s. In his wo k, we only p esen he condi ions
unde which a se o co e s can be sa ely used o syn hesis
wi hou he inse ion o ex a signals. The p ocedu es o
inse ion o ex a signals a e co e ed in [27].
To gi e an in ui i e idea abou he e iciency o he s uc u al
app oach, le us conside one illus a i e example. Fig. 7
p esen s an au onomous ci cui wi h a C-la ch closed on i s
inpu s h ough in e e s. A C-la ch is he basic cell used o
he synch oniza ion o p ocesses in asynch onous designs. I s
ou pu ises when all i s inpu s a e “1” and alls when all inpu s
a e “0”; in any o he case he ou pu emains unchanged. The
logic unc ion o a C-la ch is .
In ou example, a change on he ou pu o he C-la ch leads o
a concu en bu s o inpu changes. The numbe o ma kings
in an -inpu ci cui is , while he numbe o places in
he co esponding STG is only .
The use o co e cubes o he places in his example is
ex emely e icien because hey exac ly de ine he exci a ion
egions o all signal ansi ions; ha is, he in o ma ion
p o ided by he concu ency ela ions coincides wi h he
s uc u e o he eachabili y g aph. Gi en ansi ion , he
cube o i s p edecesso place is an exac co e
o ER (signal o de is used). Gi en ansi ion
, he in e sec ion o cubes o i s p edecesso places ,
, and gi es he single code (1110) whe e is enabled
.
PASTOR e al.: SYNTHESIS OF SPEED-INDEPENDENT CIRCUITS 1115
(a) (b)
Fig. 7. (a) Gene alized-la ch ci cui and (b) i s STG speci ica ion.
In his example, we ha e ob ained he unc ions o signals
om he s uc u al in o ma ion in he STG a he han by
es o a ion o i s eachabili y g aph. Al hough he unc ion
de i a ion p ocedu e is no always so simple, i allows one
o p esen a gene al iew o complexi y educ ion while using
he co e cube app oxima ions. In he es o his pape , we
desc ibe he condi ions o de e mine how he a o emen ioned
co e s can be i e a i ely imp o ed and when he eached
accu acy is su icien o be conside ed co ec .
V. STG STRUCTURAL ANALYSIS
This sec ion p esen s s uc u al me hods o analyzing
STG’s [28]. This me hod will be used in Sec ion VI o ind
app oxima e co e s o ER’s and QR’s. ER’s and QR’s will
be app oxima ed by a much simple egion ha cha ac e izes
he ma kings in which a gi en place is ma ked, he so-called
ma ked egion. The goal o his sec ion is o de i e a single
cube co e o each ma ked egion by using a se o s uc u al
p ope ies ha can be compu ed in polynomial ime on he
size o he STG.
Based on he concu ency ela ions and he analysis o
pa hs in he PN, we in oduce a polynomial algo i hm o
e i y he consis ency o he STG. Consis ency is a necessa y
condi ion o he syn hesis o SI ci cui s, bu i is also
necessa y o gua an ee he exis ence o a consis en nex -s a e
unc ion o he signals in he STG. Using he concu ency
and he in e lea ing be ween signals, cubes will be de i ed
o app oxima e he bina y codes o ma kings in he ma ked
egions.
A. Concu ency Rela ions
The concu ency ela ion (CR) [5] is a conse a i e concep
de ined in e ms o ma kings in he RG o an STG ha
p o ides a high-le el iew o i s dynamic beha io . When
wo ansi ions can i e om a ma king wi hou disabling each
o he , he ansi ions a e said o be concu en . Since his is
a s uc u al p ope y, i s de ini ion mus be conse a i e. Two
ansi ions may appea o be concu en in one pa o he RG
TABLE II
SCR
BETWEEN SIGNALS AND PLACES FOR THE STG IN FIG.1
while o de ed in ano he . In ha case, we should ake hem as
concu en because hey a e no always o de ed.
Concu ency ela ions can be ex ended o places and signals
[27]. We will e e o he o maliza ion o concu ency be ween
nodes and signals as signal concu ency ela ions (SCR).
De ini ion 2 (Concu ency Rela ions): The concu ency e-
la ion be ween pai s o nodes o an STG is de ined as
a bina y ela ion such ha gi en places , ansi ions
, exis s
De ini ion 3 (Signal Concu ency Rela ions): The signal
concu ency ela ion be ween a node and a
signal is de ined as a bina y ela ion such ha
.
Polynomial algo i hms o he compu a ion o he concu -
ency ela ions o a li e and sa e ee-choice PN ha e been
p esen ed in [29]. As an example, Table II depic s he ’s
o he places o STG in Fig. 1(a) [whe e indica es hose
pai s ha a e concu en ].
B. Consis ency Ve i ica ion
I an STG is no consis en , i canno be implemen ed
by a logic ci cui . The e o e, consis ency mus be checked
be o e pe o ming he syn hesis s ep. This sec ion p esen s an
e icien algo i hm o e i y he consis ency o a li e, sa e,
and i edundan ee-choice STG by using he concu ency
ela ions and he s uc u e o he unde lying PN.
1116 IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 17, NO. 11, NOVEMBER 1998
An STG sa is ies he consis ency condi ion i i does no con-
ain au oconcu en ansi ions and e e y sequence o signal
ansi ions is swi cho e co ec [20]. To a oid au oconcu en
ansi ions, no pai and o ansi ions o he same signal
is allowed o be simul aneously enabled a he same ma king.
Swi cho e co ec ness equi es he alue o each signal o
swi ch om ze o o one in esponse o a ising ansi ion and
om one o ze o due o a alling ansi ion.
Nonau oconcu ency can be s uc u ally e i ied by using
he signal concu ency ela ions, i.e., by checking ha each
ansi ion is nonconcu en wi h signal
.
The swi cho e co ec ness o a nonau oconcu en STG can
be e i ied by checking ha all adjacen ansi ions o he
same signal ha e al e na ing swi ching di ec ions. A pai o
ansi ions o he same signal can be de e mined o be adjacen
by inding a pa icula pa h in he STG connec ing bo h
ansi ions. The ollowing p ope y cha ac e izes he ela ion
be ween he o mal de ini ion o adjacency on he RG and i s
e icien compu a ion on he s uc u e o he STG.
P ope y 4 (S uc u al Cha ac e iza ion o Adjacency) [Nec-
essa y Condi ion]: In a li e and ee-choice STG, a ansi ion
nex i he e is a simple pa h be ween and
such ha :
1) no place is concu en o signal ;
2) con ains no o he ansi ions o signal excep
and .
P oo : The p oo is done by induc ion on he leng h o
he pa h . (The leng h o he pa h is always odd.)
1) . Then (whe e deno e a cs
be ween STG nodes). I is a choice place, hen i is
ee choice and he sequence is easible. I is
no a choice place, hen he oken in can be consumed
only by ansi ion . F om he li eness o he STG, i
ollows ha he e exis s a easible sequence ha con ains
bo h and . Suppose ha in any such sequence
he e is some o he ansi ion be ween and .
Clea ly, is concu en o any ansi ion be ween and
, and so i is concu en o , which con adic s he
ini ial assump ion. The e o e, nex .
2) F om he s a emen ’s being ue o , i ollows
ha i is also ue o . Conside he las
ansi ion be o e , i.e., . The
pa h be ween and has leng h , and by
he induc ion assump ion, he e exis s easible sequence
such ha does no con ain any ansi ion
o signal . Le us show ha can be ex ended as
, whe e con ains no ansi ions o signal
. This clea ly ollows om he conside a ion o i em 1)
o , and he e o e, nex .
Assuming ha an STG is nonau oconcu en , P ope y 4
p o ides he necessa y condi ions o check whe he is
adjacen o . To de i e he su icien condi ions, we need
o in oduce se e al addi ional no ions.
A pa h s a ing a and ending a is called ealizable
by a easible sequence i he sequence
includes all ansi ions in . The eason o in oduce he
(a) (b)
Fig. 8. STG showing (a) insu iciency o P ope y 4 and (b) nonconsis en ly
in e lea ed place
p
k
.
ealizable pa hs is o es ic he numbe o simple pa hs o be
analyzed when cons uc ing he se nex . Ac ually, i is
su icien o conside only hose simple pa hs ha a e ealizable
by , whe e con ains no ansi ion o signal .
The necessa y condi ions ha cha ac e ize he pa hs be ween
adjacen ansi ions o he same signal (gi en by P ope y
4) equi e any place in he pa h o be nonconcu en o all
ansi ions o he conside ed signal. This condi ion is no
su icien , as can be seen om he example in Fig. 8(a).
In his STG, he sequence is
easible, and he e o e nex . Howe e , place
is concu en o , and he only simple pa h be ween
and goes h ough .
To ob ain su icien condi ions o he adjacency be ween
ansi ions o he same signal, i is necessa y o dis inguish
which concu ency ela ions a e no ele an o adjacency.
This analysis can be done on he basis o o wa d educ ion
by concu en ansi ions.
In o mally, o wa d educ ion o PN by a se o ansi ions
is ob ained by emo ing om all he nodes s a ing
om ha canno be eached wi hou he i ing o some
ansi ion . We will deno e he esul ing PN ia
. The o wa d educ ion can be ob ained by
he ollowing p ocedu e:
Remo e ansi ions om
do un il a ixed-poin in modi ying is eached
i o all ansi ions ha e been emo ed hen
emo e om
i has been emo ed hen emo e all .
The mechanism o o wa d educ ion allows one o o mu-
la e he su icien condi ions o he exis ence o a ealizable
pa h be ween pai s o adjacen ansi ions o he same signal.
P ope y 5 (Cha ac e iza ion o Adjacency) [Su icien Con-
di ion]: In a nonau oconcu en , ee-choice STG ,i
nex , hen he e exis s a simple pa h be ween and
such ha :
PASTOR e al.: SYNTHESIS OF SPEED-INDEPENDENT CIRCUITS 1123
Fig. 12. Co e unc ion ma king coding e inemen algo i hm.
; which means ha place should ha e a s uc u al
coding con lic in e e y SM-componen (see P ope y 7). (The
mo i a ion o his ac is ha any eachable ma king should
be included in some ma ked egion.)
Con e sely, i SM con ains place bu does no con ain
any o he place o which , hen we can
conclude ha is no a eachable ma king, and he s uc u al
coding con lic be ween and is ake (happens only due
o an o e es ima ion o ) [27], [30]. Addi ionally, i can
be gua an eed ha he SM-componen SM can be used o
e ec i ely e ine he co e unc ion o place and elimina e
he o e es ima ion. Since no place SM has a s uc u al
con lic wi h , no co e cube in SM co e s .
The e inemen o is compu ed
SM , and a e he e inemen , he
co e unc ion does no ha e s uc u al coding con lic s
in SM . The p ocedu e depic ed in Fig. 12 e ines he co e
unc ions o places in he STG when ake s uc u al con lic s
a e de ec ed. No e ha e inemen s conce n no only he place
wi h s uc u al con lic s bu all he places in he STG. This is
done because we ound ha in p ac ice, places close o o he
places wi h ake s uc u al con lic s ha e also o e es ima ed
co e unc ions. E en hough he o e es ima ion could be
in he dc-se , ou expe imen s show ha his mo e gene al
applica ion o e inemen leads o much be e minimiza ion
solu ions.
The example in Fig. 1(a) con ains h ee s uc u al coding
con lic s a SM (Fig. 2)
Places and do no ha e s uc u al coding con lic s a
SM . The e o e, his SM-componen can be used o e ine he
co esponding co e unc ions
The echnique o he esol ing he s uc u al con lic be-
ween and is di e en and is discussed u he .
2) Re inemen Technique and CSC P ope y: Re inemen
does no wo k i he s uc u al coding con lic o places
and (in Fig. 1) co esponds o eachable ma kings
and MR MR . Howe e , he
co ec ness o he co e [see (2)] is no iola ed i a coding
con lic co esponds o ma kings and ha sa is y he
CSC p ope y. The s uc u e o he STG p o ides a su icien
condi ion o ind whe he he s uc u al coding con lic sa is ies
he CSC p ope y.
Theo em 14 (Su icien Condi ion o CSC): I an STG has
a CSC iola ion, hen in a gi en SM-co e SMC, one can ind
an SM-componen SM con aining a pai o places and
such ha :
1) is in he p ese o an ou pu ansi ion ;
2) is no in he p ese o any o he ansi ion o signal ;
3) ER MR .
P oo : A CSC iola ion means ha he e
exis s an ou pu signal such ha ER and
ER . Le us assume ha is he i s
ansi ion o signal ha can be enabled in a easible sequence
s a ing om , i.e., and no o he ansi ion
o signal is enabled in . Since ER , he e
is a leas one place ha is no ma ked in
. Le us ake an SM-componen SM including place .
Acco ding o he STG li eness, and should hold a
oken in places and , espec i ely ( SM, whe e
is an inpu place o ). Clea ly, by he choice o ,
place canno be in a p ese o any ansi ion , and
Condi ion 2) o he heo em is sa is ied. Taking in o accoun
ha ER ER and MR , we can
conclude ha ER MR .
Theo em 15 (De ec ion o Fake Coding Con lic s): An STG
sa is ies he CSC p ope y i o any place in he p ese o
an ou pu signal ansi ion , he e exis s an SM-componen
SM in he SMC including place such ha SM does no
con ain any s uc u al coding con lic o ; i.e.,
: SM SMC SM SM
MR MR .
P oo : Le us assume he exis ence o a CSC iola ion
due o ma kings and . F om Theo em 14, he e should
exis an SM-componen SM SMC con aining wo places
, , and a ansi ion such ha and
ER , MR , bu MR .
We will p o e ha i he e exis s SM SMC ha con ain
bo h nodes and wi hou coding con lic s o place
, hen he assumed CSC iola ion is con adic ed. Since
MR , he e should exis a place SM such ha
MR . Hence, a coding con lic should exis be ween
places and . Bu place does no con ain any coding
con lic in SM , which con adic s he assump ion abou he
CSC iola ion.
Bo h Theo ems 14 and 15 p o ide he condi ions o elim-
ina e s uc u al coding con lic s in speci ica ions ha sa is y
he CSC condi ion.
Le us go back o he s uc u al coding con lic be ween
places a SM o he STG in Fig. 1(a). This coding
con lic canno be elimina ed by means o e inemen because
place has he same coding con lic a SM , and a coding
con lic a SM . Howe e , he con lic be ween
places and sa is ies Theo em 14. No e ha
and ; he e o e, i i would co espond
o a eal CSC con lic , he e would exis some o he place no
in he p ese o any ansi ion o signal holding a con lic
wi h place . Since ha is no he case, his con lic can be
ela ed o ma kings ha sa is y he CSC condi ion. Las , i
can be concluded ha place has no con lic s and SM can

1124 IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 17, NO. 11, NOVEMBER 1998
be used o de e mine ha he con lic be ween and is
ake a bo h SM and SM .
VIII. SYNTHESIS METHODOLOGY
This sec ion comple es he syn hesis p ocess by applying
he signal egion app oxima ions o he design o an SI-
ci cui unde a pa icula a chi ec u e. Fo simplici y, we
ha e selec ed he a omic complex ga e pe exci a ion unc ion
a chi ec u e. This wo k p oposes a wo-s ep heu is ic syn hesis
algo i hm. Ini ially, nonop imized se and ese exci a ion
unc ions ha sa is y he implemen abili y condi ions (co -
ec ness and mono onici y) a e de i ed. S a ing om hese
co e s, se e al minimiza ions a e applied o simpli y he
unc ions while main aining he implemen abili y condi ions.
Howe e , e e y ime minimiza ion is applied, he algo i hm
mus de e mine whe he he inal esul is speed independence
o no . The e o e, bo h co ec ness and mono onici y should
be s uc u ally e i ied be o e accep ing he minimiza ion.
A. Ini ial Exci a ion Func ions
The se and ese unc ions o a signal mus co e all
bina y codes in i s ising and alling gene alized exci a ion
egions. Since ma kings in GER’s a e ob ained by combining
he pa icula ER’s, se and ese co e s can be compu ed as
he union o co e s o ansi ions, i.e.,
and . P ope y 13 gua an ees ha unde
he absence o s uc u al con lic s, he co e unc ions a e
co ec co e s o ER ; he e o e, and
. Following Theo em 15, a co e cube
does no o e es ima e ER i no p edecesso place
needs e inemen . S uc u al coding con lic s a e
checked in he SM-co e . I hey exis , e ining o inse ing
s a e signals is necessa y. The absence o s uc u al coding
con lic s gua an ees he CSC p ope y [27] and he exis ence
o co ec co e s.
By applying his scheme o signal in Fig. 1, we ob ain
. As place , co esponding
o , is in ol ed in a s uc u al con lic , i s co e
cube is e ined in o a se o bina y codes
. Place , co esponding o ,is
ee o s uc u al con lic s, and i s co e cube does no need any
e inemen . As a esul , .
Simila ly, we can ob ain .
B. Checking he Syn hesis Condi ions
F om he ini ial se o co e s, mul iple minimiza ion ech-
niques will be ied in o de o simpli y he inal implemen-
a ion. Some o hese ans o ma ions can be di ec ly applied
wi hou u he co ec ness o mono onici y checking because
hey a e known o p ese e hese p ope ies. Howe e , any
minimiza ion echnique ha implies inc easing he numbe o
ma kings co e ed by he se / ese co e s equi es checking he
SI syn hesis condi ions o gua an ee he speed independence
o he esul .
1) Co ec ness: The co ec ness condi ion [see (2)] e-
qui es all bina y codes o ma kings in GER GER
o be co e ed by . This condi ion de ines he
on-se on o he unc ion and can be e i ied as:
, and .
Also, no bina y code o ma kings inside GER
GQR GER GQR can be used in he
minimiza ion o . This condi ion de ines he
o -se o o he unc ion, and can be e i ied as:
QPS ,
and QPS
.
2) Mono onici y: The mono onici y condi ion has o be
checked o each co e by using a wo-s ep echnique. To
simpli y he easoning, le us assume ha con ains
exac ly one cube.
Assuming he co ec ness o he co e , i implies ha
he cube will be u ned on a ER bu should be u ned o
somewhe e inside QR o be o e eaching he ollowing
ER’s. Then, i canno be u ned on again inside he quiescen
egion wi hou iola ing he mono onici y condi ion; ha is, he
co e can only be swi ched on o implemen ansi ion
(see De ini ion 1).
The mono onici y condi ion can be s uc u ally e i ied by
de e mining he bo de places in QPS in which he co e
cube s ill can be ON, while in hei successo s i should be
u ned OFF.
Le us de ine as he se o ansi ions in
[whe e nex ] ha will u n o
o he i s ime. Le us also gene alize he in e lea ing
ela ion o he pai s and , whe e .
To gua an ee he mono onici y condi ion, gi en any place
in QPS ha is in e lea ed in ( is eached
a e ), he in e sec ion be ween he co e and he
co e unc ion should be emp y. This is cha ac e ized
o mally in he ollowing p ope y.
P ope y 16 (S uc u al Checking o Mono onici y): The
co ec co e is mono onic i o any nex
any and any place , he co e
does no in e sec wi h .
P oo : I a co e is co ec (2), hen has
o be u ned o somewhe e inside QPS . By examining he
ansi ions ha a e in [whe e nex ],
we can ind he se o ansi ions u ning o
o he i s ime. No e ha none o he li e als co esponding
o ansi ions be o e eaching can be p esen in he
cube .
To be mono onic, once is u ned o by a ansi ion in
, he cube canno be u ned on again inside QPS .
The ma ked egion o all sequences o places ha a e in
is co e ed by . Con e sely, all places ha
a e in can be eached only a e he i ing o ; ha
is, a e he cube is u ned o . The e o e, mono onici y
is ensu ed i cube is ne e u ned on again in he
ma kings ha a e co e ed by he ma ked egions o places
.
As an example, le us assume ha we ha e compu ed he
co e o he STG in Fig. 1. The se
will con ain ansi ions ; he e o e,
is mono onic because i can in e sec wi h he co e s
PASTOR e al.: SYNTHESIS OF SPEED-INDEPENDENT CIRCUITS 1125
o place bu canno in e sec wi h he co e s o any place
in e lea ed be ween and
.
When has se e al cubes, he mono onic sequences
de ined by he se a e conse a i ely compu ed.
A ansi ion belongs o he se i i is he i s
one such ha he co e cubes o he places in i s pos se
a e no comple ely co e ed by , i.e.,
QPS .
C. Syn hesis Algo i hm
F om he ini ial se o co e s, se e al minimiza ions a e
heu is ically applied. (A de ailed desc ip ion o each minimiza-
ion is desc ibed in he Appendix.) Fo simplici y, we assume
ha he STG sa is ies he CSC condi ion; o he wise, s a e
encoding echniques a e applied [30]. Addi ionally, sa eness,
li eness, and consis ency on he STG should be checked
be o ehand [12], [31]. The selec ed minimiza ion p ocess is
he ollowing.
1) Each se / ese co e is expanded owa d he quiescen
egions and dc-se by elimina ing li e als.
2) A e expansion owa d he quiescen egion, co e s a e
checked o be comple e; ha is, i he se ( ese ) co e
includes all bina y codes in GQR GQR , hen
he a omic complex ga e pe signal a chi ec u e can be
used, hence a oiding he use o a C-la ch.
3) Signals ha canno be di ec ly implemen ed by he se
o ese co e , i.e., equi ing he memo y elemen , can
be u he expanded owa d he quiescen egion o i s
p edecesso ansi ions (see he Appendix).
4) The C-la ch can be collapsed wi h he se and ese
co e s, leading o a po en ial simpli ica ion o he ci cui .
5) The o e all syn hesis p ocess is comple ed by c ea ing
he ci cui and mapping i s di e en elemen s on o a
ga e lib a y.
To demons a e he e olu ion o he co e s h ough he
minimiza ion p ocess, he syn hesis algo i hm will be applied
o he ou pu signal in Fig. 1. The p e iously compu ed ini ial
co e s a e , ,
, and in he i s s ep o he minimiza ion
p ocess a e expanded owa d he quiescen egion and dc-se .
Li e al can be elimina ed om he suppo o
including ma kings in he co e , which esul s in
. Li e al can be elimina ed
om bo h and , gene a ing he co e
. When simpli ying he co e
, li e al can be elimina ed, expanding he
co e owa d he dc-se , which esul s in .
Las , li e al can be elimina ed om , ob aining
. Bo h co e s a e used o implemen he
se unc ion . Wi h espec o ,
li e al can be elimina ed by expanding he co e owa d he
quiescen egion and ob aining .
Fo his pa icula signal, comple e co e minimiza ion no
backwa d expansion no memo y collapsing can be applied.
The inal implemen a ion is depic ed in Fig. 4(b).
IX. EXPERIMENTAL RESULTS
This sec ion p esen s a numbe o expe imen s ha e alua e
he quali y o he p oposed syn hesis me hodology. Fou
ele an issues ha e been analyzed: 1) he in luence o mini-
miza ion on he inal a ea o ci cui s, 2) a ea esul s compa ed
o p e ious syn hesis me hodologies, 3) CPU speedup due o
he s uc u al algo i hm compa ed o s a e-based algo i hms,
and 4) he ela ion among ma kings in he STG’s, he numbe
o cubes equi ed o he s uc u al app oxima ions, and he
quali y o a ea minimiza ions. No e ha all syn hesis esul s
ha e been o mally e i ied o be speed independen [32].
The CPU imes ha e been ob ained on a Sun SPARC20
wo ks a ion.
In all ables, columns labeled , , and indica e
he numbe o places, ansi ions, and eachable ma kings.
Columns labeled and SM deno e he numbe o cubes
and SM’s equi ed by s uc u al algo i hms. These alues
gi e an in ui i e idea abou he complexi y o each bench-
ma k.
A. Heu is ics o A ea Minimiza ion
This sec ion compa es he a e age a ea imp o emen ob-
ained in wo benchma k se s (see Fig. 13). In bo h cases, he
p ocess s a s om an ini ial semiop imized implemen a ion,
in which only expansions owa d he quiescen egion and dc-
se ha e been applied, and p og essi ely e ol es owa d mo e
e icien implemen a ions.
Poin s in he column labeled a e he ini ial semiop i-
mized implemen a ion. P og essi ely, in column , ansi-
ions a e allowed o be me ged; in ,comple e signal ne -
wo ks a e de ec ed. Memo y elemen collapsing is applied a
. Las , egion co e s a e expanded owa d he backwa d qui-
escen egions in (see he Appendix). F om a echnology-
independen implemen a ion, a Boolean-ma ching mapping
algo i hm is applied [33]. The column labeled p esen s
he esul s ob ained a e he applica ion o a echnology-
mapping s ep ha , o example, me ges simple ga es in o
complex ones when a ailable in he lib a y (cu en ly complex
ga es up o ou inpu s such as AOI22).
B. A ea o he Ci cui s
Table V compa es he a ea esul s o se e al syn hesis ools
including ou me hodology. The goal o his expe imen is o
show ha e en hough s uc u al echniques only app oxima e
he eachable ma kings in he STG’s, his me hodology does
no nega i ely in luence he quali y o he ci cui s.
Columns labeled SYN and FCG epo he a ea ob ained
by he syn hesis me hodologies de eloped a S an o d [24]
and Aizu [19]. Columns labeled S3C con ain a ea esul s
o ou me hodology wi hou using he backwa d minimiza-
ion and mapping (le column) and ully minimized ( igh
column).
The esul s show ha he new logic-minimiza ion echniques
p o ide signi ican imp o emen s—23% a ea educ ion wi h
espec o [24]—in sho CPU imes—less han 8 s o he
wo s case (pe-send-i c). We also ook in o accoun ha
some o he new minimiza ion echniques we e no ully
1126 IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 17, NO. 11, NOVEMBER 1998
Fig. 13. A e age minimiza ion esul s o he benchma k se s.
TABLE V
AREA RESULTS COMPARISON WITH TOTALS BY SYN (1) AND BY FORCAGE (2) (
3
NONFREE-CHOICE—NONAVAILABLE RESULT)
used by SYN and FORCAGE (e.g., backwa d expansions and
mapping). Thus, o he sake o compa ison ai ness, we dis-
abled such op imiza ions, s ill ob aining a 15% imp o emen .
The e o e, we can conclude om he expe imen al esul s ha
s uc u al me hods, e en being conse a i e, do no in luence
nega i ely on he quali y o he inal esul .
C. CPU Time: S uc u al Ve sus S a e Based
To illus a e he e ec i eness o s uc u al o e s a e-g aph-
based me hods, we ha e un some expe imen s o STG’s
wi h a la ge eachabili y g aph, compa ing CPU imes wi h
SIS [6] and ASSASSIN [8] (see Table VI). The supe io i y o
s uc u al me hods is e iden .
Table VII epo s he CPU imes o wo la ge scalable
benchma ks. The dining philosophe s benchma k is one o he
examples ha illus a es ha non ee-choice STG’s can also
be syn hesized i a co e o s a e machines can be ound o
he ne . Ano he scalable example is he Mulle pipeline. I s
STG con ains no choice places, and he ci cui ealiza ion is
a chain o C-la ches.
TABLE VI
CPU TIME FOR SYNTHESIS:COMPARISON WITH SIS AND ASSASSIN
D. E iciency o he Cube App oxima ions
We ha e analyzed he e iciency o app oxima ing he
bina y codes o a eachabili y g aph by se s o cubes. This is
achie ed by compa ing he numbe o equi ed cubes e sus
he numbe o nodes in he STG and he numbe o eachable
ma kings e sus he numbe cubes. The cube compa ison
is done sepa a ely o wo classes o STG’s, hose wi h
PASTOR e al.: SYNTHESIS OF SPEED-INDEPENDENT CIRCUITS 1127
TABLE VII
CPU TIME FOR SYNTHESIS:SCALABLE EXAMPLES (
3
NON-FC STG’s)
TABLE VIII
TRADEOFFS AMONG MARKINGS,NODES,AND CUBES
less han 10 ma kings and hose su passing his limi (see
Table VIII).
Fo small benchma ks, we ha e eached a cubes/node a io
close o 2.4, while he ma kings/cube a io is close o 1.7.
The e o e, we can conclude ha o small STG’s, he e a e no
signi ican di e ences be ween using he eachabili y g aph
o he p oposed s uc u al echniques. On he o he hand, o
la ge benchma ks, he cubes/node a io is close o 2.6, while
he ma kings/cube a io is close o 4 10 . Thus, each
node equi es 2.6 cubes, and each cube app oxima es up o
410 ma kings— he e o e jus i ying he e iciency o he
co e -app oxima ions me hodology.
X. CONCLUSIONS
S uc u al echniques o he analysis and syn hesis o
STG’s a e essen ial when he size o he s a e space becomes
unmanageable. The p oposed s uc u al echniques in end o
ill he gap be ween he STG’s ha can be analyzed by cu en
s a e-based echniques and he exis ing STG’s speci ica ions
o complex sys ems.
This wo k has p esen ed new me hods o syn hesize STG’s
whose unde lying PN is ee choice. The p oposed algo i hms
ha e polynomial complexi y in he size o he ne and can be
easily ex ended o he class o PN’s ha can be co e ed by
SM-componen s, al hough he exis ence o a SM-co e canno
be gua an eed o any non ee-choice Pe i ne .
The expe imen al esul s show ha he p oposed me hods
ob ain a ea-e icien implemen a ions in sho CPU imes. Mos
o he exis ing ools we e unable o syn hesize he la ges
ci cui s, whe eas he p esen ed me hod is able o do i in ew
seconds. Fu u e wo k will be de o ed o ully cha ac e ize
he class o Pe i ne s ha can be handled by he p esen ed
echniques.
APPENDIX
MINIMIZATION TECHNIQUES
This Appendix will p o ide an o e iew o he minimiza-
ion echniques ha a e s uc u ally applied o simpli y he
co e s used in an a omic complex ga e pe exci a ion egion
a chi ec u e.
A. Basic Concep s
To e icien ly implemen his a chi ec u e, ou pu signal an-
si ions a e pa i ioned in o se s o ansi ion clus e s [34], [35].
Each clus e implies a complex ga e o i s implemen a ion.
These complex ga es a e combined by OR o o m he se and
ese unc ions, espec i ely.
De ini ion 17 (T ansi ion Clus e ): We de ine he ansi ion
clus e s as a o al pa i ion o
he ising and alling ansi ions o one ou pu signal , which
mus sa is y he ollowing condi ions.
1) E e y ising o alling clus e con ains a leas one
ansi ion.
2) E e y ising ( alling) ansi ion mus be in one and only
one ansi ion clus e s ic ly composed o o he ising
( alling) ansi ions o he same signal.
A ansi ion clus e , whe he o no i con ains ising o
alling ansi ions, will be simply deno ed by . Supe sc ip s
a e used o di e en ia e clus e s o he same signal. All signal
egion de ini ions (ER’s, QR’s, QR , e c.) and implemen abil-
i y condi ions can be easily ex ended o he usage on ansi ion
clus e s.
Fig. 4(b) and (c) shows wo di e en implemen a ions o
ou pu signal in Fig. 1. The i s implemen a ion [Fig. 4(b)]
co esponds o he ansi ion clus e pa i ioning
, , and , which a e
implemen ed by co e s , ,
and . This ci cui is no SI because i he
AND-OR ga e o is slow enough, he pulse on inpu can
p opaga e o he ou pu . In Fig. 4(c), ansi ions and
a e me ged in o one clus e . This
makes he o e all ci cui simple and SI ( he aces be ween
inpu s and ake place only wi hin one AND–OR ga e).
B. Comple e Region Co e s
Gene a ing comple e co e s o all he ising o alling
ansi ions o an ou pu signal is one o he e icien min-
imiza ion echniques ha can be applied. In ha case, he
ci cui can be exclusi ely c ea ed by using he co esponding
se o ese unc ion [5]. E e y co e is checked o be comple e
by analyzing ha all ma kings in QR a e co e ed by
.
I all ising co e s a e comple e, he se unc ion implemen s
he ci cui . Simila ly, i all alling co e s a e comple e, he
ese unc ion can be al e na i ely used. In case bo h ising and
alling unc ions a e comple e, he smalles o as e unc ion
should be selec ed.
C. Region Expansions
Ci cui s can be minimized by expanding he egion co e s
owa d he quiescen egion and he dc-se . All ans o ma ions
a e cha ac e ized by ei he he elimina ion o a signal om
he suppo o he unc ion o he elimina ion o li e als om
he cubes. The main objec i e o expanding is o simpli y
he co e s bu also o ob ain comple e egion co e s wi h he
subsequen minimiza ion (allows a combina ional implemen a-
1128 IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 17, NO. 11, NOVEMBER 1998
ion o he signal). The e o e, his minimiza ion has a highe
p io i y han o he ans o ma ions.
T ansi ion clus e s a e me ged oge he when he complexi y
o he esul ing egion co e dec eases. T ansi ion clus e s
and a e me ged, c ea ing a new clus e
wi h co e s , and elimina ing
he seminal ones. Me ging equi es checking whene e he
esul ing co e can be posi i ely ma ched in he ga e lib a y.
Me ging also allows one o de i e an inc eased numbe o
comple e co e s.
D. Collapsing o Memo y Elemen s
The s uc u e o he a chi ec u e and he beha io o he C-
la ch can be used o u he simpli y he ci cui [24]. Conside
he signal ne wo k o an ou pu signal implemen ed by a
C-la ch wi h equa ion , and
se and ese ne wo ks wi h one egion co e each
. Bo h cubes can be collapsed in o he
C-la ch: , ob aining
. Hence, bo h se and ese egion ne wo ks
can be subs i u ed by , being and
.
Simila ly, i he se and ese ne wo ks
, hei cubes ha e he same suppo
and a e a dis ance one. Again, bo h cubes can be collapsed
in o he C-la ch, ob aining . Then, bo h se and
ese egion ne wo ks can be subs i u ed by he exp essions
, being and he da a and
con ol inpu s o a ga ed la ch ha eplaces he ini ial C-la ch.
E. Backwa d Region Expansions
The backwa d quiescen egion BR o a ansi ion is
he maximal connec ed se o ma kings ha can each ER
wi hou enabling any o he ansi ion .
Fu he ci cui minimiza ions can be ob ained i a co e
is also ex ended o co e ma kings in i s backwa d
quiescen egion BR . Co e ing ma kings in he backwa d
quiescen egions is only possible because o he cha ac e is ics
o he C-la ch (as poin ed ou by [19] and [36]). Main aining
one o he inpu s o he C-la ch a 1 (0) while i s ou pu is a
1 (0) c ea es and ex a obse abili y dc-se ha can be used
o u he minimize ci cui s.
Gi en he a chi ec u e in Fig. 3(c), i bo h he se co e
and he ou pu a e s ill a 1, ac i a ing he ese co e will
no p oduce a alling ansi ion o he ou pu un il he se
co e alls o 0. Hence, he co e o any alling ansi ion
can be ac i a ed be o e eaching i s ER, bu only i i can
be gua an eed ha he se co e will emain a 1 un il he
alling ansi ion is exci ed. Simila condi ions apply o ising
ansi ions.
Simila mono onici y condi ions a e equi ed in he back-
wa d egions; ha is, he co e changes exac ly wice in
any sequence, whe e he ising change is a a ma king in
BR ER and he alling change in QR .
The backwa d quiescen egion BR can be s uc u ally
de ined by he backwa d quiescen place se BPS .A
place belongs o BPS i i is in e lea ed be ween
and nex , i.e., BPS
nex . The same concep can be
ex ended o ansi ion clus e s and o es ic ed egions, i.e.,
BPS BPS .
Las , i is also essen ial o de e mine which a e he ma kings
ha he p edecesso ansi ion clus e s a e co e ing o de e -
mine he subse o he BR egion ha is allowed o be co e ed.
Fo each place in BPS , we will de ine by he
subse o ma kings in MR co e ed by some p edecesso
ansi ion :
QPS BPS . Once we
ha e compu ed hese subse s, he co ec co e ing o ma kings
in he backwa d quiescen egion is s aigh o wa d:
BPS .
F. Technology Mapping
Ci cui s gene a ed a e he o e all minimiza ion p ocess
a e mapped on o he echnology p o ided by he designe .
Blocks in he signal ne wo k can be combined in single cells
when a ailable in he lib a y o exis ing ga es. This cell-
binding p ocess p o ides an ex a deg ee o minimiza ion
by subs i u ing se e al logic blocks in he signal ne wo k
by a mo e e icien ly implemen ed cell in he lib a y. A
echnology mappe ailo ed o SI-ci cui s has been de eloped
ollowing he Boolean ma ching echniques p oposed in [33].
Howe e , no e ha i is no possible o apply a gene alized
decomposi ion p ocess o he blocks in he signal ne wo k due
o he es ic i e co ec ness condi ions imposed by speed-
independen ci cui s [37].
REFERENCES
[1] A. J. Ma in, “Fo mal p og am ans o ma ions o VLSI ci cui syn he-
sis,” in Fo mal De elopmen o P og ams and P oo s, E. W. Dijks a,
Ed. Reading, MA: Addison-Wesley, 1989, pp. 59–80.
[2] C. A. Pe i, “Kommunika ion mi Au oma en,” Ph.D. disse a ion, In-
s i u ¨
u Ins umen elle Ma hema ik, Bonn, 1962, Tech. Rep. Sch i en
des IIM N . 3.
[3] M. A. Kishine sky, A. Y. Kond a ye , and A. R. Taubin, “Fo mal
me hod o sel - imed design,” in P oc. Eu . Design Au oma ion Con .,
Feb. 1991, pp. 197–201.
[4] L. Y. Rosenblum and A. V. Yako le , “Signal g aphs: F om sel - imed
o imed ones,” in P oc. In . Wo kshop Timed Pe i Ne s, July 1985, pp.
199–206.
[5] T.-A. Chu, “Syn hesis o sel - imed VLSI ci cui s om g aph- heo e ic
speci ica ions,” Ph.D. disse a ion, Massachuse s Ins i u e o Technol-
ogy, Camb idge, June 1987.
[6] E. M. Sen o ich, K. J. Singh, L. La agno, C. Moon, R. Mu gai, A.
Saldanha, H. Sa oj, P. R. S ephan, R. K. B ay on, and A. Sangio anni-
Vincen elli, “SIS: A sys em o sequen ial ci cui s syn hesis,” Uni e si y
o Cali o nia, Be keley/ERL, Tech. Rep. M92/41, May 1992.
[7] P. A. Bee el and T. H. Meng, “Au oma ic ga e-le el syn hesis o speed-
independen ci cui s,” in P oc. IEEE/ACM In . Con . Compu e Aided
Design, IEEE Compu e Socie y P ess, No . 1992, pp. 581–586.
[8] C. Ykman-Cou eu , B. Lin, and H. De Man, “ASSASSIN: A syn hesis
sys em o asynch onous con ol ci cui s,” IMEC, Sep . 1994, Tech.
Rep., use and u o ial manual.
[9] K.-J. Lin and C.-S. Lin, “Au oma ic syn hesis o asynch onous ci cui s,”
in P oc. ACM/IEEE Design Au oma ion Con ., IEEE Compu e Socie y
P ess, June 1991, pp. 296–301.
[10] C. Ykman-Cou eu , B. Lin, G. Goossens, and H. De Man, “Syn hesis
and op imiza ion o asynch onous con olle s based on ex ended lock
g aph heo y,” in P oc. Eu . Con . Design Au oma ion (EDAC), Feb.
1993, pp. 512–517.
[11] M. Hack, “Analysis o p oduc ion schema a by Pe i ne s,” M.S. hesis,
Massachuse s Ins i u e o Technology, Camb idge, Feb. 1972.

PASTOR e al.: SYNTHESIS OF SPEED-INDEPENDENT CIRCUITS 1129
[12] J. Desel and J. Espa za, F ee Choice Pe i Ne s. Camb idge, U.K.:
Camb idge Uni . P ess, 1995.
[13] F. Ga c´ıa-Vall´es and J. M. Colom, “A Boolean app oach o he s a e
machine decomposi ion o Pe i ne s wi h OBDD’s,” in P oc. 1995 IEEE
In . Con . Sys ems, Man and Cybe ne ics, Oc . 1995.
[14] P. Vanbekbe gen, “Op imized syn hesis o asynch onous con ol ci -
cui s om g aph- heo e ic speci ica ion,” in P oc. IEEE/ACM In . Con .
Compu e Aided Design, No . 1990, pp. 184–187.
[15] R. K. B ay on, G. D. Hach el, C. T. McMullen, and A. L. Sangio anni-
Vincen elli, Logic Minimiza ion Algo i hms o VLSI Syn hesis. No -
well, MA: Kluwe Academic, 1984.
[16] F. M. B own, Boolean Reasoning: The Logic o Boolean Equa ions.
No well, MA: Kluwe Academic, 1990.
[17] V. I. Va sha sky, Sel -Timed Con ol o Concu en P ocesses. No -
well, MA: Kluwe Academic, 1990.
[18] K. Lau enbach, “Linea algeb aic echniques o place/ ansi ion ne s,”
in Pe i Ne s: Cen al Models and hei P ope ies, Ad ances in Pe i
Ne s 1986, W. B aue , W. Reisig, and G. Rozenbe g, Eds., ol. 254 o
Lec u e No es in Compu e Science. Be lin, Ge many: Sp inge Ve lag,
1987, pp. 142–167.
[19] 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 oc. ACM/IEEE Design Au oma ion Con ., June 1994, pp. 56–62.
[20] M. Kishine sky, A. Kond a ye , A. Taubin, and V. Va sha sky, “Con-
cu en ha dwa e. The heo y and p ac ice o sel - imed design,” Se ies
in Pa allel Compu ing. New Yo k: Wiley, 1994.
[21] L. La agno and A. Sangio anni-Vincen elli, Algo i hms o Syn hesis
and Tes ing o Asynch onous Ci cui s. No well, MA: Kluwe Aca-
demic, 1993.
[22] A. Yako le , L. La agno, and A. Sangio anni-Vincen elli, “A uni ied
signal ansi ion g aph model o asynch onous con ol ci cui syn-
hesis,” in P oc. IEEE/ACM In . Con . Compu e Aided Design, IEEE
Compu e Socie y P ess, No . 1992, pp. 104–111.
[23] T. H.-Y. Meng, R. W. B ode sen, and D. G. Messe schmi , “Au oma ic
syn hesis o asynch onous ci cui s om high-le el speci ica ions,” IEEE
T ans. Compu e -Aided Design, ol. 8, pp. 1185–1205, No . 1989.
[24] P. A. Bee el, “CAD ools o he syn hesis, e i ica ion, and es abili y o
obus asynch onous ci cui s,” Ph.D. disse a ion, S an o d Uni e si y,
S an o d, CA, Aug. 1994.
[25] S. Bu ns, “Gene al condi ions o he decomposi ion o s a e holding
elemen s,” in P oc. In . Symp. Ad anced Resea ch in Asynch onous
Ci cui s and Sys ems, Aizu, Japan, Ma . 1996, pp. 48–57.
[26] J. Co adella, M. Kishine sky, A. Kond a ye , L. La agno, E. Pas o ,
and A. Yako le , “Decomposi ion and echnology mapping o speed-
independen ci cui s using Boolean ela ions,” in P oc. IEEE/ACM In .
Con . Compu e Aided Design, No . 1997, pp. 220–227.
[27] E. Pas o and J. Co adella, “Polynomial algo i hms o he syn hesis o
haza d- ee ci cui s om signal ansi ion g aphs,” in P oc. IEEE/ACM
In . Con . Compu e Aided Design, San a Cla a, USA, IEEE Compu e
Socie y P ess, No . 1993, pp. 250–254.
[28] E. Pas o , J. Co adella, A. Kond a ye , and O. Roig, “S uc u al
me hods o he syn hesis o speed-independen ci cui s,” in P oc. Eu .
Design Tes Con . (EDAC-ETC.-Eu oASIC), Pa is, F ance, Ma . 1996,
pp. 340–347.
[29] A. Ko alyo and J. Espa za, “A polynomial algo i hm o compu e he
concu ency ela ion o ee-choice signal ansi ion g aphs,” in P oc.
In . Wo kshop Disc e e E en Sys ems, WODES’96, Aug. 1996, pp. 1–6.
[30] E. Pas o and J. Co adella, “An e icien unique s a e coding algo i hm
o signal ansi ion g aphs,” in P oc. IEEE In . Con . Compu e Design,
Camb idge, MA, Oc . 1993, pp. 174–177.
[31] J. Espa za and M. Sil a, “A polynomial- ime algo i hm o decide
li eness o bounded ee choice ne s,” Theo e ical Compu . Sci., no.
102, pp. 185–205, Ap . 1992.
[32] O. Roig, J. Co adella, and E. Pas o , “Ve i ica ion o asynch onous
ci cui s by BDD-based model checking o Pe i ne s,” in P oc. 16 h In .
Con . Applica ion and Theo y o Pe i Ne s, To ino, June 1995, ol. 935
o Lec u e No es in Compu e Science, Sp inge Ve lag, pp. 374–391.
[33] F. Mailho and G. De Micheli, “Technology mapping using Boolean
ma ching,” in P oc. Eu . Con . Design Au oma ion (EDAC), Glasgow,
U.K., Ma . 1990, pp. 180–185.
[34] E. Pas o , J. Co adella, and O. Roig, “A new look a he condi ions o
he syn hesis o speed-independen ci cui s,” in P oc. 5 h G ea Lakes
Symp. VLSI, Bu alo, NY, May 1995, pp. 230–235.
[35] A. Kond a ye , M. Kishine sky, and A. Yako le , “On haza d- ee
implemen a ion o speed-independen ci cui s,” in P oc. ASP-DAC’95,
Aug. 1995, pp. 241–248.
[36] P. A. Bee el and T. H.-Y. Meng, “Logic ans o ma ions and obse -
abili y don’ ca es in speed-independen ci cui s,” in ACM In . Wo kshop
Timing Issues in he Speci ica ion and Syn hesis o Digi al Sys ems, Sep .
1993.
[37] P. Siegel and G. De Micheli, “Decomposi ion me hods o lib a y bind-
ing o speed-independen asynch onous designs,” in P oc. IEEE/ACM
In . Con . Compu e Aided Design, 1994.
En ic Pas o ecei ed he M.S. and Ph.D. deg ees
in compu e science om he Uni e si a Poli ´
ecnica
de Ca alunya, Ba celona, Spain, in 1991 and 1996,
espec i ely.
He is an Associa e P o esso in he Depa men
o Compu e A chi ec u e o he Uni e si a
Poli ´
ecnica de Ca alunya. He was a Visi ing Schola
a he Uni e si y o Colo ado a Boulde , CO,
and he In e -uni e si y Mic oelec onics Cen e
(IMEC), Belgium, in 1992 and 1994, espec i ely.
In 1988, he was a Le e hulme T us Fellow isi ing
he Uni e si y o Newcas le upon Tyne, U.K. His esea ch in e es s include
o mal me hods o he compu e -aided design o VLSI sys ems wi h special
emphasis on syn hesis and e i ica ion o asynch onous ci cui s and concu en
sys ems.
Jo di Co adella (S’87–M’88) ecei ed he M.S.
and Ph.D. deg ees in compu e science om he
Uni e si a Poli ´
ecnica de Ca alunya, Ba celona,
Spain, in 1985 and 1987, espec i ely.
He is an Associa e P o esso in he Depa men
o So wa e o he Uni e si a Poli ´
ecnica de
Ca alunya. In 1988, he was a Visi ing Schola a
he Uni e si y o Cali o nia, Be keley. His esea ch
in e es s include compu e -aided design o VLSI
sys ems wi h special emphasis on syn hesis and
e i ica ion o asynch onous ci cui s, concu en
sys ems, compu e a i hme ic, and pa allel a chi ec u es. He has coau ho ed
mo e han 80 esea ch pape s in echnical jou nals and con e ences. He has
se ed on he echnical commi ees o se e al in e na ional con e ences in he
ield o design au oma ion and concu en sys ems.
Alex Kond a ye (M’97), o a pho og aph and biog aphy, see p. 771 o he
Sep embe 1998 issue o his TRANSACTIONS.
O iol Roig ecei ed he enginee in compu e science deg ee in 1991 and
he Ph.D. deg ee in compu e science in 1997, bo h om he Uni e si a
Poli ´
ecnica de Ca alunya, Ba celona, Spain.
He was an Assis an P o esso a he Uni e si a Poli ´
ecnica de Ca alunya
un il May 1998, when he joined he Me hodology g oup a Na ional Semi-
conduc o , San a Cla a, CA. His esea ch in e es s include asynch onous and
o mal ha dwa e e i ica ion.