Au oma ic syn hesis and op imiza ion o pa ially speci ied asynch onous sys ems
Alex Kond a ye Jo di Co adella Michael Kishine sky Luciano La agno Alexande Yako le
Uni . o Aizu Uni . Poli `ecnica In el Co p. Uni . o Udine Uni . o Newcas le
Japan Ca alunya, Spain USA I aly upon Tyne, UK
Abs ac
A me hod o au oma ing he syn hesis o asynch onous con ol
ci cui s om high le el (CSP-like) and/o pa ial STG (in ol ing
only unc ionally c i ical e en s) speci ica ions is p esen ed. The
me hod sol es wo key sub asks in his new, mo e lexible, de-
sign low: handshake expansion, i.e. inse ing ese e en s wi h
maximum concu ency, and e en eshu ling unde in e ace and
concu ency cons ain s, by means o concu ency educ ion. In
doing so, he algo i hm op imizes he ci cui bo h o size and pe -
o mance. Expe imen al esul s show a signi ican inc ease in he
solu ion space explo ed when compa ed o exis ing CSP-based o
STG-based syn hesis ools.
1In o duc ion
Speci ying an asynch onous ci cui is a cumbe some and e o -
p one ask because he designe has o de ine he beha io o e -
e y signal a e e y momen o ime. Al hough he alue o a sig-
nal migh be some imes i ele an o he gene al unc ioning o he
sys em, one mus be speci ic abou i s beha io by exac ly de ining
whe he he signal is s able a 0 o 1 o making a ising o alling
ansi ion.
To ci cum en his p oblem, he designe should be able o
speci y he beha io o a ci cui by only de ining hose e en s ha
a e ele an o i s unc ion - hey a e called unc ional e en s. The
es o he e en s (non- unc ional) can be de ined a bi a ily unde
he equi emen o p ese ing he co ec ness o he ci cui beha -
io . This is exempli ied by he ga e-le el implemen a ion o a is-
ing edge- igge ed lip- lop. Only he ising edge is “ unc ional”,
and mus ha e a p ecise ela ionship wi h he inpu and he ou -
pu signals (se up/hold cons ain s and ou pu delay espec i ely).
The alling edge can occu almos a any ime be ween wo con-
secu i e ising edges. In he asynch onous con ex , his kind o
eedom p o ides addi ional oom o op imiza ion unde di e en
cos unc ions aimed a a ea and/o pe o mance.
The e a e a ious design scena ios in which his app oach may
be use ul:
1. The designe concen a es on he key unc ional aspec s and,
e.g., speci ies only he ising edges o signals. A ool au o-
ma ically inse s non- unc ional e en s. E en when all e en s
a e unc ional, he e is some eedom in making hem ei he
o de ed o concu en . The designe es ic s some unc ion-
ally impo an concu ency/o de ing ela ions and allows he
ool o choose how o educe concu ency and op imize he
ci cui .
2. The designe uses a high-le el language, such as CSP [1, 6],
ha igno es he bina y na u e o ci cui signals and speci ies
he beha io in e ms o abs ac e en s. The ollowing wo
design s eps mus hen p ecede logic syn hesis:
handshake expansion : eplacing each communica ion ac-
ion o a CSP p og am wi h signal ansi ions on he
wo wi es ha cons i u e he channel,
eshu ling : selec ing he o de o some non- unc ional e en s
( e u n- o-ze o signal ansi ions in ou phase expan-
sion o he channels) o op imizing a ea, pe o mance
o powe .
In his pape we sol e he p oblem o handshake expansion
in a canonical ashion, by inse ing “ ese ” e en s wi h max-
imum concu ency wi h espec o he o he signals. We hen
sol e he p oblem o eshu ling by only conside ing he op-
e a ion o concu ency educ ion.
The idea o using concu ency educ ion as an e icien me hod in
he op imiza ion loop was i s p oposed in [5]. The main dis inc-
i e ea u es o ou app oach wi h espec o ha wo k a e:
1. The educ ion mechanism is applied in a wide amewo k
(handshake expansion, eshu ling), ins ead o wo king a he
le el o comple ely speci ied S a e G aphs.
2. A educ ion based on emo al o S a e G aph a cs is used,
ins ead o coa se echniques based on emo al o s a es.
3. No e e y o m o concu ency educ ion can be modeled by
a sequence o pai wise educ ions. In [3] and Sec ion 5 a
mo e gene al (albei expensi e) echnique is discussed.
4. The educ ion p ocedu es p esen ed in his pape a e aimed
a he gene al minimiza ion o logic, ins ead o only sol ing
he CSC p oblem.
In he es o he pape , a e Sec ion 2, de o ed o heo e i-
cal backg ound, and Sec ion 3, de o ed o an in o mal o e iew,
we will answe he ollowing ques ions: (1) How is concu ency
exploi ed s a ing om a pa ial speci ica ion o an asynch onous
con olle ? (Sec ion 4); (2) Wha a e he alid educ ions o con-
cu ency? (Sec ion 5); (3) How can concu ency be educed by
i e a i e applica ion o a single, elemen a y ope a ion? (Sec ion 6);
(4) How is he quali y o he solu ion es ima ed? (Sec ion 7). Sec-
ion 8 p esen s expe imen al esul s.
2 Theo e ical backg ound
This sec ion assumes he eade o be amilia wi h Pe i ne s [7].
Figu e 1.a shows a iming diag am o a simple con olle be-
ween an asynch onous memo y and a p ocesso . An ope a ional
cycle is igge ed by he p ocesso eques ing da a (
Req
goes high).
A e his eques , memo y p epa es da a and he con olle eplies
wi h an acknowledgmen (
Ack
goes high). F om now on he p o-
cesso can ese he eques and immedia ely s a a new cycle. No e
_
De ini i e Ve sion o Reco d in he ACM Digi al Lib a y: h ps://doi.o g/10.1145/309847.309891
Req
Ack
(c) (d)
(b)
(a)
p2
p4
p3
p5
p1
p1
p3 p4
p5
p2
Ack-
Ack-
0*1
11*
1*0*
00* 1*1
Ack Req
Ack+
Req-
Req+
Ack+
Req-
Req+
Ack+
Req-
Req+Ack-
Req+ Ack-
Figu e 1: Simple asynch onous con olle : (a) wa e o ms, (b,c)
STG, (d) S a e G aph
ha in o de o inc ease he sys em h oughpu , he p ocesso can
send a new eques wi hou wai ing o he ese o he acknowledg-
men signal by he con olle . Figu e 1.b shows he Pe i Ne (PN)
co esponding o he iming diag am o he con olle . All e en s
in his PN a e in e p e ed as signal ansi ions: ising ansi ions o
signal
a
a e labeled wi h “
a
+
” and alling ansi ions wi h “
a

”.
We also use he no a ion
a

i we a e no speci ic abou he sign o
he ansi ion. Pe i Ne s wi h such in e p e a ion o he ansi ions
a e called Signal T ansi ion G aphs (o STGs) [2].
STG ansi ions co espond o sys em e en s. A ansi ion is
enabled i all i s inpu places con ain a oken. In he ini ial ma k-
ing o he STG in Figu e 1.c ansi ion
Ack
+
is enabled. E e y
enabled ansi ion can i e, emo ing one oken om e e y inpu
place o he ansi ion and adding one oken o e e y ou pu place.
A e he i ing o ansi ion
Ack
+
he ne mo es o a new ma king
p
5
g
and
Req

becomes enabled, e c.
S a e g aphs.
Playing he oken game one can gene a e a S a e
G aph (SG)in which each node (a ma king) is labeled wi h a ec-
o o signal alues (signals ha can change in he s a e a e ma ked
wi h an as e isk) and a cs be ween pai s o s a es a e labeled wi h
he co esponding i ed ansi ion. An SG is consis en i i s s a e
labeling
:
S
!
0
;
1
g
n
is such ha in e e y ansi ion sequence
om he ini ial s a e, ising and alling ansi ions al e na e o each
signal. Figu e 1.d shows he SG o he STG in Figu e 1.c, which
is consis en . The no a ion 0*1 in he ini ial s a e o Figu e 1.d in-
dica es ha signal
Ack
has alue
0
and
Ack
+
is enabled o i e,
while signal
Req
is s able a alue 1.
We w i e
s
a
!
(
s
a
!
s
0
) i he e is an a c om s a e
s
( o s a e
s
0
) labeled wi h
a
and
s

)
s
0
is he e is a pa h om s a e
s
o s a e
s
0
labeled wi h a sequence o e en s

.
The se o all signals is pa i ioned in o a se o inpu s,which
come om he en i onmen , and a se o ou pu s and s a e signals
ha mus be implemen ed.
Implemen abili y condi ions
In addi ion o consis ency, he ol-
lowing wo p ope ies a e equi ed o an SG o be implemen able
in o a haza d- ee asynch onous ci cui .
The i s p ope y is speed independence, wi h h eecons i uen s:
de e minism, commu a i i y and ou pu -pe sis ency. An SG is de-
e minis ic i o each s a e
s
and each label
a
he e can be a mos
one s a e
s
0
such ha
s
a
!
s
0
.AnSG is commu a i e i whene e
wo ansi ions can be execu ed om some s a e in any o de , hei
execu ion always leads o he same s a e, ega dless o he o de .
An e en
a

is pe sis en in s a e
s
i i is enabled in
s
and emains
l?
!
?
l!
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
li+
o+
i+
lo+
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
( )
li+
o+
i+
lo+
li-
o-
i-
lo-
li+
o+
i+
lo+
li-
lo- i-
o-
00
00
11
11
LR LR
l li
lo o
i
(a) (b)
(c) (d) (e)
Figu e 2: Speci ica ion o he LR-p ocess
enabled in any o he s a e eachable om
s
by i ing ano he e en
b

.AnSG is ou pu -pe sis en i all ou pu signal e en s a e pe -
sis en in all s a es and inpu signals canno be disabled by ou pu s.
The second p ope y, Comple e S a e Coding (CSC), is neces-
sa y and su icien o he exis ence o a logic ci cui implemen a-
ion. A consis en SGsa is ies he CSCp ope y i o e e y pai o
s a es
s; s
0
such ha
(
s
)=
(
s
0
)
, he se o ou pu e en s enabled
in bo h s a es is he same. The SGo Figu e 1.d is ou pu -pe sis en
bu does no ha e CSC (bina y codes 11* and 1*1 co espond o
di e en s a es).
Exci a ion Regions and Concu ency.
A se o s a es is he
exci a ion egion (ER)o e en
a

(deno ed by
ER
(
a

)
)i i isa
maximal connec ed se o s a es such ha
8
s
2
ER
(
a

):
s
a

!
.
SGs a e used in his pape as he main model o pe o ming he
concu ency educ ions. Hence we need o de ine he concu ency
no ion in e ms o he SG.
De ini ion 2.1 Two e en s
a
and
b
a e said o be concu en in
he SG
A
(
a
jj
b
) i he ollowing diamond s uc u e o s a es and
ansi ions belongs o
A
:
(
s
1
a
!
s
2
)
^
(
s
1
b
!
s
3
)
^
(
s
2
b
!
s
4
)
^
(
s
3
a
!
s
4
)
:
I can be easily shown ha o a speed-independen SG wo
ou pu e en s
a
and
b
a e concu en i hei ERs in e sec :
a
jj
b
,
ER
(
a
)
ER
(
b
)
6
=
;
:
In he SG o Figu e 1.d ansi ion
Req
+
is enabled in s a es
1*0* and 00* (
ER
(
Req
+)
=
1*0*,00*
g
) while
Ack

is enabled
in 1*0* and 1*1 (
ER
(
Ack

)
=
1*0*,1*1
g
). Exci a ion egions
o hese ansi ions in e sec , hus implying ha he co esponding
ansi ions a e concu en .
3O e iew o he me ho d
We illus a e ou me hodology by means o an example. Figu e 2.a
shows he s uc u e o an LR-p ocess [6] using he “handshake
componen ” no a ion [1]. The p ocess has a passi e po
l
and an
ac i e po
. I ans e s con ol om he le po o he igh po .
Figu e 2.b shows he e inemen o each channel wi h wo wi es:
l
=
li; lo
g
and
=
i; o
g
. Figu e 2.c gi es a speci ica ion o
his p ocess using CSP-like ac ions o e en s, whe e
l
?
;l
!
(
?
;
!
)
s and o he inpu and ou pu ac ions a channel
l
(
). Figu e 2.d
p esen s a handshake expansion o he p e ious speci ica ion. I is
ob ained by elabeling channel ac ions
l
?
and
l
!
o ising ansi ions
on he inpu and ou pu wi es o he po s,
li
+
and
lo
+
, co espond-
ingly ( he same o channel
). The la e speci ica ion is iewed as
a pa ially speci ied STG. I canno be di ec ly implemen ed by ex-
is ing STG-based syn hesis ools since he alling ( ese ) ansi ions
A ea Pe o mance
Ci cui a ea # CSC sign. c .cycle inp.e en s
Q-module (hand) 104 1 14 4
Full educ ion 0 0 8 4
Max.concu ency 168 2 13 3
li
k
i
144 0 9 3
li
k
o
160 1 11 3
lo
k
i
136 1 11 3
lo
k
o
232 2 16 3
Table 1: A ea/pe o mance ade-o o di e en implemen a ions
o he LR-p ocess
o he signals a e no speci ied. The e a e many di e en solu ions
o inse ing alling signal ansi ions. S a ing om he solu ion
wi h maximum concu ency one can de i e any o he alid eshu -
ling o ansi ions by concu ency educ ion. Figu e 2.e shows an
STG wi h maximal concu ency o all alling ansi ions, assum-
ing ha all signals a e independen , and ha no in e ace cons ain s
we e gi en.
This handshake expansion howe e is no alid o he LR-
p ocess. Indeed, we should obey addi ional o de ing cons ain s
o he channels: ne e ese he eques ing signal be o e ecei ing
he acknowledgmen . Fo example, o a passi e po
l
one should
sa is y he ollowing in e lea ing o signal ansi ions:

[
li
+;
lo
+;
li

;
lo

]
Simila ly o he ac i e channel. Figu e 2. p esen s a alid hand-
shake expansion wi h maximal concu ency o he LR-p ocess ak-
ing in e ace cons ain s in o accoun .
o-
i-
C
li+
o+
i+
lo-
lo+
li-
o-
i-
lo i
li o
C
S
RRs
lo i
o
li
li+
o+
i+
lo+
i-
li- o-
lo- (c)
lo-
li-
csc-
li+
o+
i+
csc+
o-
i-
lo+
C
C
li
lo
i
o
li+
o+
lo-
i+
csc+
lo+
li-
csc-
(a)
li
lo
o
i
(b)
(d)
Figu e 3: Implemen a ions o he LR-p ocess
This speci ica ion can be implemen ed wi h he cu en STG
based syn hesis ools. Two s a e signals a e inse ed o esol ing
he Comple e S a e Coding (CSC) con lic s.
Table 1 p esen s he a ea and pe o mance esul s o di e en
implemen a ions o he LR-p ocess. The ow “Max. concu ency”
co esponds o he implemen a ion o he STGwi h maximum con-
cu ency o he ese signal ansi ion. The ci cui a ea is 168 uni s.
Assuming ha all in e nal and ou pu e en s ha e a delay o 1 ime
uni , and ha all inpu e en s ha e a delay o 2 ime uni s, he c i i-
cal cycle is 13 uni s and con ains 3 inpu e en s. O he implemen-
a ions a e shown in Figu e 3. Figu e 3.a shows an implemen a ion
o he LR-p ocess known widely as Q-module [6] o S-elemen [1].
Figu e 3.b co esponds o he case o ull concu ency educ ion. I
p oduces he bes a ea ( wo wi es) bu does no allow o decouple
he le and he igh sides o LR-p ocess.
The abo e examples sugges he algo i hm o op imiza ion o
pa ially speci ied STGs shown in Figu e 4.
Inpu s: Ini ial STG
In e ace cons ain s (channel in e lea ing)
Concu ency cons ain s (concu en e en s,...)
Ou pu : Reduced S a e g aph and he co esponding STG
1: Inse he ‘‘ ese ’’ ansi ions wi h maximal
concu ency, sa is ying all in e ace cons ain s
2: Gene a e SG
A
om he STG
3: while he cos imp o es do
4: Reduce concu ency o SG
A
, sa is ying
in e ace and concu ency cons ain s
educing CSC con lic s and logic complexi y
endwhile
5: Gene a e a new STG o he bes educed SG
Figu e 4: Handshake expansion and eshu ling o STGs
p1 p2
p3
ai+ ai+
eq
a_ z
ack
p1 p2
p3
ao+ ao+
eq
ack
p_ z
p1 p2
p3
a!
p1 p2
p3
a?
(d) (e)
p1 p2
p3
b+
z
dy
b-
z
dy
p1 p2
p3
b
ai-
ao- ai-
ao-
ack
eq
p_ z a_ z
(b)
(a) (c)
Figu e 5: STG s uc u es o 4-phase e inemen . Pa ially speci-
ied signal: e u n- o-ze o e en (a) and unc ional e en (b). Chan-
nel: e u n- o-ze o pa (c) and unc ional pa s, o inpu channel
(d) and o ou pu channel (e).
4Handshake expansion
This sec ion explains how handshake expansion is pe o med. The
syn ax o ou speci ica ions allows one o desc ibe he beha io o
channels and pa ially speci ied signals. In bo h cases, he speci i-
ca ion only con ains he ac i e ansi ions, whe eas he handshake
expansion me hod ans o ms he speci ica ion acco ding o he e-
inemen chosen by he designe : 2-phase e inemen , wi h no dis-
inc ion be ween up and down ansi ions, o 4-phase e inemen ,
wi h e u n- o-ze o signaling o each handshake.
Pa ially specied signals.
The STG ans o ma ion equi ed
o expand a pa ially speci ied signal is shown in Figu e 5.a and
b. Figu e 5.a illus a es an addi ional e u n- o-ze o ansi ion ha
mus be connec ed (using he places labelled dy and z) o he
unc ional pa co esponding o he ising ansi ion o he signal,
shown in Figu e 5.a. No e ha each ising ansi ion isenabled only
when he e u n- o-ze o ansi ion has i ed (a c dy
!
b
+
). The
e u n- o-ze o ansi ion is enabled as soon as he ising ansi ion
has i ed (a c
b
+
!
z).
Channels.
Fo channel e inemen we use a no a ion simila o
ha p oposed o handshake p ocesses [1]. Two ypes o e en s can
occu in channel
a
: inpu e en s (
a
?
) and ou pu e en s (
a
!
). The
e minals o a channel a e called po s. A channel
a
is implemen ed
by wo signals:
a
i
(inpu ) and
a
o
(ou pu ).
The expansion om channel o signal e en s can be done by
manipula ing he s uc u e o he unde lying Pe i ne . Fo 2-phase
e inemen , he ans o ma ion simply equi es elabeling he STG
a!
a?
b
c+
a!
b
c-
a?
(a)
ao+ b-
ai+ ao-
c+ c-
b+ ai-
(b)
b+ao+
b+
c+
ai+
c-
ao+ai+
ai-
ao-
ao-
ai-
b-
b-
(c)
Figu e 6: (a) O iginal speci ica ion (SG), (b) 2-phase e inemen
(SG), (c) 4-phase e inemen (STG).
ansi ions om
a
?
o
a
i
~
and
a
!
o
a
o
~
, whe e he su ix
~
deno es a
ansi ion oggling he alue o he signal.
The expansion o a 4-phase p o ocol is pe o med by elabel-
ing ansi ions and inse ing e u n- o-ze o e en s. The ans o ma-
ions pe o med a he STG le el consis o adding a e u n- o-ze o
s uc u e and de ining mul iple ins ances o he ansi ions ep e-
sen ing channel e en s. The e u n- o-ze o s uc u e co esponding
o a channel is depic ed in Figu e 5.c. The place eq indica es
ha he channel is eady o a new handshake. The place ack in-
dica es ha he channel has ecei ed a eques (
a
?
o passi e and
a
!
o ac i e handshakes) and will pe o m an acknowledgmen (
a
!
o passi e and
a
?
o ac i e handshakes). The places p z ( o
passi e) and a z ( o ac i e) ecei e a oken as soon as he hand-
shake is comple e and ac i a e he e u n- o-ze o ansi ions. This
scheme allows a channel o ac bo h as an ac i e and as a passi e
po a di e en ins an s o he beha io o he sys em.
Figu es 5.d.e show how channel e en s a e ansla ed in o ac-
ual signal e en s by s uc u al ans o ma ions o he STG. Each
e en
a
?
is ans o med in o a ising ansi ion o he inpu signal
(
a
i
+
). Simila ly,
a
!
is ans o med in o
a
o
+
. Two ins ances o
a
i
+
and
a
o
+
in Figu es 5.d.e model di e en ypes o channel beha io
(ac i e o passi e). The pa allel composi ion o he STG pieces o
Figu es 5.c.d.e gi es an o e all pic u e o he channel beha io in
he se and ese phases. No e ha he speci ica ion mus p ope ly
in e lea e he e en s on he channel acco ding o he handshake
p o ocol, o he wise he expansion would p oduce an inconsis en ly
encoded STG.This scheme gua an ees he maximum concu ency
o he e u n- o-ze o sequence, ha is hen exploi ed by he con-
cu ency educ ion algo i hm desc ibed in Sec ion 3.
Example.
Figu e 6 p esen s an example illus a ing all he abo e
ans o ma ions. The o iginal speci ica ion (Figu e 6.a) has a chan-
nel (
a
), a pa ially speci ied signal (
b
) and a comple ely speci ied
signal (
c
). Two-phase and ou -phase e inemen s o he same spec-
i ica ion a e shown in Figu e 6.b.c.
5Concu ency educ ion
In his sec ion we de elop he heo y and algo i hms ha allow us
o explo e only alid educ ions o concu ency mo e e icien ly
han by wo king on a s a e-by-s a e basis. In pa icula , ou no ion
o concu ency educ ion is ela ed o he in oduc ion o places
(causal cons ain s) a he STG le el, and hen “ ixing” he STGso
ha consis ency and speed-independence a e p ese ed.
Valid concu ency educ ion should p ese e ce ain p ope ies.
Le
A
be he ini ial SG and
A
ed
be a educed SG. Reducing con-
cu ency o e en
e
means unca ing some ERs o his e en . In
o he wo ds, some o he a cs labeled wi h
e
a e emo ed om he
SG as a esul o concu ency educ ion. This may cause some o
he s a es o become un eachable and o be emo ed om he SG.
No s a es o a cs no p esen in he ini ial SG can appea in
A
ed
. This i ially implies ha consis ency, commu a i i y, and
de e minism o he SG canno be iola ed as a esul o concu -
ency educ ion. Also no new CSC con lic s can appea (in ac
some o all o he con lic s can disappea due o s a e emo al).
Validi y hen equi es he ollowing p ope ies o be sa is ied
a e concu ency educ ion:
1. Speed-independence is p ese ed: as no ed abo e, commu-
a i i y and de e minism a e au oma ically p ese ed, so he
only cons ain is ha i
A
is ou pu pe sis en , hen
A
ed
mus be ou pu pe sis en .
2. I/O in e ace is p ese ed:
(a) No ansi ion o inpu signals is delayed.
(b) The ini ial s a e is p ese ed wi h espec o he I/O sig-
nals, i.e., i
s
0
2
A
and
s
0
0
2
A
ed
a e he ini ial s a es
o he o iginal and he educed SGs espec i ely, hen
he e is a pa h
s
0

)
s
0
0
o
s
0
0

)
s
0
in
A
such ha
sequence

con ains only e en s o in e nal signals, no
obse able by he en i onmen .
Bo h condi ions can in ac be pa ially elaxed i he designe
can accep changing he in e ace beha io o he module,
e.g., i also he en i onmen will be syn hesized la e .
3. No e en s disappea : i o some e en
e
he eis
ER
(
e
)
2
A
,
hen
ER
ed
(
e
)
6
=
;
.
4. No deadlock s a es appea : i s a e
s
2
A
and
s
2
A
ed
,and
s
is no a deadlock s a e in
A
( he e exis s e en
e
:
s
e
!2
A
),
hen he e exis s some o he e en
e
0
such ha :
s
e
0
!2
A
and
s
e
0
!2
A
ed
.
Whene e concu ency is educed o an ou pu signal, one mus
also make su e ha his is e lec ed in he speci ica ion o he be-
ha io assumed by he en i onmen (e.g., by ano he design eam).
O he wise, concu ency educ ion may in oduce deadlocks in he
composi ion o he ci cui and he en i onmen , e.g., i he en i on-
men expec s
b
a e
a
and he ci cui p o ides
b
be o e
a
as a esul
o wo con lic ing concu ency educ ions o ini ially concu en
e en s
a
and
b
.
De ini ion 5.1 (Valid educ ion) I a educed SGsa is ies all p op-
e ies (1)–(4) abo e, hen he concu ency educ ion is alid.
6The basic op e a ion: o wa d educ ion
The algo i hm ske ched in Figu e 7 de ines ou basic ope a ion o
concu ency educ ion, called o wa d educ ion. I akes wo con-
cu en e en s as pa ame e s. Concu ency is educed o he i s
e en (
a
). The second e en (
b
) de ines he se o s a es
ER
(
a
)
ER
(
b
)
in which concu ency o
a
should (a leas ) be educed in
one s ep. In he simples case, when e en s enabled in
ER
(
a
)
a e
pe sis en , and
ER
(
a
)
has only one minimal s a e (a s a e is mini-
mal in an
ER
i i has no p edecesso s in he
ER
),FwdRed(a,b)
c ea es an a c om e en
b
o e en
a
a he STG le el.
The applica ion o he o wa d concu ency educ ion FwdRed
o an STG wi h choice (non-pe sis ency) and concu ency is illus-
a ed in Figu e 8. The educed SG co esponds o an STGwi h no
concu ency be ween
(
a; b
)
,
(
a; e
)
,and
(
a; d
)
. Hence, in gene al
educing concu ency o a pai o e en s can also educe concu -
ency o some o he pai s. No e ha in lines 1,2 o FwdRed, s a es
a e emo ed om he ER o e en
a
, no om he SG. I.e., a his
s ep only a cs labeled wi h
a
can be emo ed om he SG.
The ollowing p oposi ion shows ha i e a i e applica ion o
FwdRed o an SG esul s in a alid concu ency educ ion.
FwdRed(a,b)
1: /* emo e all a cs
s
a
!
such ha
s
is backwa d eachable om
ER
(
a
)
ER
(
b
)
*/
2:
ER
ed
(
a
)
=
ER
(
a
)

(
ER
(
b
)
[
back each
(
ER
(
a
)
ER
(
b
)))
3: emo e un eachable s a es and hei ou pu a cs
4: i exis s some
e
such ha
ER
(
e
)=
;
o
5: ini ial s a e w o I/O is changed hen
6: e u n (in alid educ ion)
7: else e u n ( educed SG)
Figu e 7: Reduc ion o concu ency o ou pu e en
a
by e en
b
.
c
a
e
d
b
c
de
b
a
(a)
c
a
a
b
b
d
e
de
s0
s1
s6
s7
s8
s2
s3
s5
s4
c
a
a
b
d
e
s0
s1
s8
s2
s3
s5
s4
c
a
a
a
a
b
b
d
e
de
s0
s1
s6
s7
s8
s2
s3
s5
s4
ER(a)
ER_ ed(a)
(b)
Figu e 8: Applying FwdRed(a,b) o an SG agmen (a) and he
co esponding STG ans o ma ion (b).
P oposi ion 6.1 (Validi y o FwdRed)Le
A
be a consis en and
speed-independen SG.I
a
is an ou pu e en and
a
and
b
a e
concu en in
A
, henFwdRed(a,b) is a alid concu ency e-
duc ion (See [3] o he p oo ).
No e. A mo e gene al o mula ion o concu ency educ ion is
done ia he emo al o a single a c om he co esponding SG
h ough he no ion o backwa d educ ion [3]. Howe e , con a y
o FwdRed(a,b) backwa d educ ion in gene al does no ha e a
clea in e p e a ion in e ms o o de ing ela ions be ween e en s.
The e o e, ou p ac ical implemen a ion desc ibed in he nex sec-
ion is es ic ed o he applica ion o FwdRed.
7Implemen a ion
As we men ioned in Sec ion 3, concu ency educ ion can educe
he logic complexi y o he ci cui in wo ways. Fi s o all, he
numbe o CSC con lic s is educed, and hence he complexi y o
he logic implemen ing he s a e signals is educed. Secondly, he
numbe o eachable s a es is educed, and hence he don’ ca e se
o logic minimiza ion is inc eased. Howe e , in case one signal
becomes o de ed wi h ano he , he suppo o i s boolean unc ion
inc eases. Fo his eason, we use a heu is ic cos unc ion ha es-
ima es changes in logic complexi y a each s ep, since exac com-
pu a ion by s a e signal inse ion, decomposi ion and echnology
mapping would be oo expensi e.
The algo i hm in Figu e 9 desc ibes how concu ency educ-
ion is pe o med. The designe ini ially p o ides a lis o pai s o
e en s whose concu ency canno be educed, e.g., because hey
a e c ucial o o e all sys em pe o mance. This will p e en he
algo i hm om adding causali y ela ions be ween hese pai s o
e en s.
The explo a ion is done by a s a egy simila o he



p un-
ing commonly used in game-playing algo i hms. A each le el o
he explo a ion om a gi en con igu a ion, a se o neighbo con-
igu a ions is gene a ed by pe o ming a basic ans o ma ion ( o -
wa d concu ency educ ion be ween wo e en s). Fo each le el
o he explo a ion, only a ew candida es, wi h he bes es ima ed
cos , su i e o he nex le el. These candida es a e kep in he
lis on ie . The wid h o he explo a ion is con olled by he
pa ame e size on ie .
No e ha a each le el o he explo a ion he ob ained s a e
g aphs a e less concu en han hei p edecesso s. This mono onous
beha io gua an ees ha he algo i hm will e mina e when no mo e
concu ency can be educed in he cu en sea ch space.
The cos unc ion o selec he bes con igu a ions a each le el
aims a educing he complexi y o he esul ing ci cui . Un o -
una ely, he es ima ion o he complexi y o he logic o ou pu
signals wi h CSC con lic s can be inaccu a e due o he impossi-
bili y o de i e co ec equa ions. Fo his eason, he cos unc-
ion combines he in o ma ion o CSC con lic s wi h he es ima ed
complexi y o he logic. A designe can speci y a pa ame e
W
(
0

W

1
) which de ines he ade-o be ween biasing he
heu is ic sea ch owa ds educing CSC con lic s (
W
;
0
)o e-
ducing es ima ed complexi y o he logic (
W
;
1
).
Inpu s: S a e g aph ini ial SG
Keep Conc

E

E
(p ese ed concu ency ela ions)
size on ie : size o he on ie o explo a ion
Ou pu : S a e g aph educed SG wi h educed concu ency
on ie = explo ed SGs =
ini ial SG
g
;
while on ie
6
=
;
do
new solu ions =
;
;
o each SG
2
on ie do
o each
(
e
1
;e
2
)
:s. .
e
1
k
e
2
,
(
e
1
;e
2
)
62
Keep Conc
and
e
2
is no an inpu e en do
new SG = FwdRed (SG,
e
2
,
e
1
);
explo ed = explo ed
[
new SG
g
;
new = new
[
new SG
g
;
end o
end o ;
on ie = “ he bes size on ie elemen s in new”;
endwhile;
educed SG = “bes elemen in explo ed”;
Figu e 9: Algo i hm o educing concu ency.
8Exp e imen al esul s
The echniques p esen ed in his pape ha e been implemen ed in
he ool pe i y [4]. A e handshake expansion and concu -
ency educ ion, ci cui s ha e been de i ed by using p e iously
published syn hesis echniques o speed-independen ci cui s. The
inal a ea was ob ained by decomposing he ci cui in o 2-inpu
ga es and mapping he ne wo k on o a ga e lib a y. The decom-
posi ion was pe o med by p ese ing he speed-independence o
he ci cui .
Fi s case s udy: he
PAR
comp onen
This sec ion p esen s
a case s udy conside ing he handshake expansion and concu ency
educ ion o he PAR componen used in VLSI p og amming om
he concu en language Tang am [1].
Figu e 10.a shows an STG speci ica ion in e ms o channel
e en s. This speci ica ion may yield di e en implemen a ions de-
pending on he selec ed phase e inemen and concu ency among
e en s. The mos challenging p oblem a ises when a 4-phase e-
inemen is desi ed. The eedom o schedule he e u n- o-ze o
ansi ions opens a spec um o di e en implemen a ions. Fig-
u e 10.c [9] (see implemen a ion in Figu e 10. ) has been ob ained
manually and is used by he cu en Tang am compile .

b!
b?
a?
a! c!
c?
ai+
bo+ co+
bo-
bi-
co-
ai-
ao-
bi+
bi+
bo+
bo-
bi-
co+
ci+
co-
ci-
ao+
ci+
ao-
ao+
ci-
ai+
bo+
bi+
bo-
bi-
co+
ci+
ao+
ai-
co-
ai-
ci-
C
C
C
C
C
ai+
ao-
(b)
(a)
ai
ai
ai
bi
bi
ci
ao
bo
co
bi
ai
ci
co
ao
bo (c)
(d)
(e) ( )
Figu e 10: Di e en speci ica ions and implemen a ions o a PAR
componen .
Ou ool can au oma ically pe o m a 4-phase expansion by us-
ing he s uc u al echniques discussed in Sec ion 4, and de i e he
speci ica ion shown in Figu e 10.b. A e his ans o ma ion, he
e u n- o-ze o signalling is pe o med wi h maximum concu ency.
Howe e , a di ec implemen a ion o his beha io would esul in a
complex ci cui due o he need o inse ing ex a logic o s a e en-
coding and logic decomposi ion ( wice as complex as Figu e 10.e).
Figu es 10.d.e depic he solu ion au oma ically ob ained by e-
ducing he concu ency o he 4-phase e inemen in Figu e 10.b.
The educ ion has been pe o med by p ese ing he concu ency
be ween he e en s
b
?
and
c
?
, hus main aining he pa allel execu-
ion o bo h p ocesses. In e es ingly, he ci cui mani es s an asym-
me ic beha io ha can be bene icial o implemen PAR compo-
nen s in which he p ocess a channel
b
is known o be slowe han
ha a
c
. The ci cui is sligh ly smalle (by 12% in ou s anda d
cell lib a y) han he known manual design. Howe e , i s es ima ed
pe o mance may be wo se han ha o Figu e 10. , i
b
and
c
ha e
balanced delays
1
.
Second case s udy: he MMU con olle
In [8] i was shown
ha by using iming assump ions on he beha io o he en i on-
men , i is possible o educe he a ea o an asynch onous Memo y
Managemen Uni con ol ci cui by o e 50 %, wi h espec o he
o iginal speed-independen implemen a ion. Ou expe imen s p e-
sen ed in Table 2 show ha app oxima ely he same a ea imp o e-
men can be eached wi hou sac i icing speed-independence,i we
a e allowed o use lexibili y in playing wi h concu ency o he
ese ansi ions o he ou -phase p o ocol. A combina ion o ou
high-le el ans o ma ion and Mye s’ lowe le el iming op imiza-
ions can concei ably p o ide e en be e op imiza ion esul s.
We can conclude ha :

Wi h espec o he o iginal solu ion, eshu ling can yield an
a ea educ ion o less han one hal .

This a ea educ ion can be ob ained wi hou losing pe o -
mance. E.g., he solu ion
k
(
b; m;
)
wi h a ea 384 uni s has
a c i ical cycle o 94 uni s, while he o iginal implemen a ion
wi h a ea 744 had a c i ical cycle o 100 uni s We used he
same iming delay assump ions as in [8]. In case [8] used a
ini e delay in e al, we conside ed he a e age delay, while
in case he uppe bound was in ini e, we conside ed he lowe
bound.
1
The c i ical cycle is longe by 11% unde he assump ion ha he delay o a com-
bina ional ga e is 1 ime uni , ha o a sequen ial ga e is 1.5 ime uni s, and ha o an
inpu e en is 3 ime uni s.
A ea Pe o mance
Ci cui a ea # CSC sign. c .cycle inp.e en s
o iginal 744 2 100 4
o iginal educed 208 0 118 6
csc educed 96 1 123 7
k
(
b; l;
)
440 1 101 4
k
(
b; m;
)
384 0 94 4
k
(
b; l; m
)
352 1 104 5
k
(
l; m;
)
368 1 105 5
Table 2: A ea/pe o mance ade-o o di e en implemen a ions
o he MMU con olle
9Conclusions
Speci ying he beha io o an asynch onous sys em is a complex
ask ha needs o be pe o med a he app op ia e high le el o ab-
s ac ion. Reasoning in e ms o ac ions (o e en s) and communi-
ca ion channels allows he designe o desc ibe a beha io wi hou
wo ying abou he implemen a ion de ails.
This pape has p esen ed a me hod o au oma e he decisions
aken a he lowes le els o ci cui syn hesis, conce ning phase e-
inemen s and e en eshu ling. Thus he designe is only le he
ask o de ining he causali y among ac ions and speci ying he de-
si ed concu ency in he sys em. The ask o ansla ing ac ions in o
signals ansi ions is au oma ically handled by CAD ools.
Some aspec s s ill equi e u he esea ch. In pa icula , be e
logic es ima ion s a egies when he speci ica ion has CSC con lic s
mus be sough . On he o he hand, simple bu accu a e me hods o
pe o mance es ima ion should be de ised o inc ease he deg ee o
au oma ion and p o ide a wide explo a ion o he solu ion space.
Acknowledgmen s.
We hank S e e Fu be o emphasizing he need
o ackle he p oblem o au oma ic handshake expansion and concu ency
educ ion. This wo k was suppo ed by ESPRIT ACiD-WG (21949), CI-
CYT TIC98-0410 and TIC98-0949, UK EPSRCGR/K70175 and GR/L24038,
and B i ish Council (Spain) Acci´on In eg ada MDR/1998/99/2463.
Re e ences
[1] Kees an Be kel. Handshake Ci cui s: an Asynch onous A chi ec u e
o VLSI P og amming, olume 5 o In e na ional Se ies on Pa allel
Compu a ion. Camb idge Uni e si y P ess, 1993.
[2] T.-A. Chu. Syn hesis o Sel - imed VLSI Ci cui s om G aph- heo e ic
Speci ica ions. PhD hesis, MIT, June 1987.
[3] J. Co adella, M. Kishine sky, A. Kond a ye , L. La agno, and
A. Yako le . Au oma ic handshake expansion and eshu ling using
concu ency educ ion. In Wo kshop on Ha dwa e Design and Pe i
Ne s, pages 86–110, June 1998.
[4] Jo di Co adella, Michael Kishine sky, Alex Kond a ye , Luciano
La agno, and Alex Yako le . Pe i y: a ool o manipula ing concu -
en speci ica ions and syn hesis o asynch onous con olle s. IEICE
T ansac ions on In o ma ion and Sys ems, E80-D(3):315–325, 1997.
[5] Bill Lin, Chan al Ykman-Cou eu , and Pe e Vanbekbe gen. A gene al
s a e g aph ans o ma ion amewo k o asynch onous syn hesis. In
P oc. Eu opean Design Au oma ion Con e ence (EURO-DAC), pages
448–453. IEEE Compu e Socie y P ess, Sep embe 1994.
[6] Alain J. Ma in. Syn hesis o asynch onous VLSI ci cui s. In J. S aun-
s up, edi o , Fo mal Me hods o VLSI Design, chap e 6, pages 237–
283. No h-Holland, 1990.
[7] T. Mu a a. Pe i Ne s: P ope ies, analysis and applica ions. P oceed-
ings o he IEEE, pages 541–580, Ap il 1989.
[8] Ch is J. Mye s and Te esa H.-Y. Meng. Syn hesis o imed asyn-
ch onous ci cui s. IEEE T ansac ions on VLSI Sys ems, 1(2):106–119,
June 1993.
[9] Ad Pee e s. Implemen a ion o a pa allel componen in ang am. Pe -
sonal communica ion, 1997.