High-Le el Syn hesis
o
Asynch onous Sys ems:
Scheduling and P ocess Synch oniza ion*
Rosa
M.
Badia Jo di Co adella
Poly echnic Uni e si y
o
Ca alonia, Dep .
o
Compu e A chi ec u e.
Campus No d, Modul
D4.
G an Capi a s/num. Ba celona,
E-08071
Abs ac
Asynch onous sys enis a e gaining accep ance as
he size and complexi y o digi al ci cui s inc ease.
Conco dan ly, syn hesis ools o asynch onous sys-
ems mus
be
de eloped
o
make
design p ocess eas-
ie . This pape aims a he de ini ion o basic con-
cep s
o
scheduling algo i hms and con ol syn he-
sis in high-le el syn hesis
o
asynch onous ci cui s.
Two scheduling s a egies a e p esen ed and e alua ed.
Expe imen s on di e en benchma ks show ha
e i:
cien asynch onous schedules can
be
ob ained. Con ol
is modelled in
a
dis ibu ed ashion wi h Local Con-
olle s synch onizing be ween hem
by
means o hand-
shaking p o ocols.
1
In oduc ion
Asynch onous ci cui s
p esen p ope ies ha mee
he equi emen s o la ge, complex sys ems
[l,
21:
no
clock skew, modula in e connec i i y, low peak cu -
en s, and pe o mance de e mined by a e age p o-
cessing speeds. The design o asynch onous sys ems
based on sel - imed ci cui s
[l]
has been mo e b oadly
accep ed in he las yea s. Mos wo k on design au-
o na ion o asynch onous sys ems has been ocused
o logic syn hesis o sequen ial machines
[3].
Cu -
en ly, signi ican e o is being in es ed in he syn-
hesis o haza d- ee ci cui s om
Signal T aiisi ion
G aphs
[2],
ini ially p oposed by Chu
[4]
o
desc ibe
he beha io o asynch onous sequen ial machines.
O he app oaches syn hesize asynch onous ci -
cui s om high-le el speci ica ions by syn ax-di ec ed
ansla ion, acco ding o p oduc ion ule se s. In
51
and
[6]
a simila s a egy is used o ansla e
(1:
!A
'P
in o delay-insensi i e ci cui s. We canno conside ,
howe e , hese app oaches wi hin he ca ego y o
high-
le el syn hesis,
since no a emp is done o imp o e he
quali y o he ci cui , (size and pe o mance) by using
op imiza ion echniques like
ope a ion scheduling
and
ha dwa e alloca ion
[7].
Syn ax-di ec ed ansla ion
gene a es ci cui s whose size depends linea ly on he
size o he inpu desc, ip ion
[5].
The e o s on
high-le el syn hesis
[7] ha e been
mainly ocused o synch onous designs.
A
clea e -
idence o his endency is ha he p oposed
schedul-
~
'Wo k
unded
by
CYCIT
TI(:
91-1036
aiid
ACiD-WG
(Es-
p i
7225)
ing algo i hms
[8,
93
a e based on he concep o
con-
ol s ep-i.e.
ime is measu ed in
cycles,
and cycle
ime is de e mined by he
wo s -case delay
o all he
ope a ions execu ed in
a
con ol s ep. Only Ku and
De Micheli
[lo]
conside he possibili y
o
ha ing syn-
ch onous ope a ions wi h unbounded delays.
F om he poin o iew o he iming model used
o ope a ion scheduling and con ol syn hesis, asyn-
ch onous sys ems p esen wo signi ican di e ences:
Time is conside ed
as
a
con inuous a iable
and ini-
ia ion and comple ion o ope a ions a e
e en s
ha
can occu a any ins an .
Ope a ions ha e
a iable, da a-dependen delays.
The e o e, di e en scheduling s a egies mus be con-
cei ed i an asynch onous iming model is conside ed.
This pape aims a he de ini ion o basic con-
cep s, da a s uc u es, and p imi i e unc ions o
asynch onous scheduling algo i hms and con ol syn-
hesis.
The pape is o ganized
as
ollows. Sec ion
2
de-
sc ibes he a chi ec u e model conside ed o he asyn-
ch onous execu ion o ope a ions. Sec ion
3
p esen s
an o e iew o a high-le el syn hesis sys em. Sec-
ion
4
de ines he basic da a s uc u es and unc ions
p oposed o scheduling algo i hms and p esen s wo
algo i hms o ope a ion scheduling. Sec ion
5
de-
sc ibes he connec ion be ween module binding and
p ocess synch oniza ion and how con ol can be syn-
hesized. Conclusions and u u e wo k a e p esen ed
in sec ion
6.
2
Asynch onous A chi ec u e Model
A
high-le el syn hesis sys em equi es
a
a ge a -
chi ec u e model o he mapping o high-le el objec s
(ope a ions, a iables, da a ans e s) in o ha dwa e
modules
(ALUs,
egis e s, mul iplexo s). This sec ion
p esen s a sho summa y o he a chi ec u e model
p oposed in [Ill (only de ails e e ing o ope a ion
scheduling and con ol syn hesis will be desc ibed).
2.1
Da a-Pa h
The da a-pa h is composed o sel - imed blocks
(ALUs,
egis e s, mul iplexo s, e c) synch onized by
means o a handshaking p o ocol implemen ed wi h
wo signals:
eques
and
comple zon
[l].
Regis e s
1066-1409/93 $03.00
0
1993
IEEE
70
a e implemen ed
as
la ches ( he
eques
signal indi-
ca es when la ching mus be ini ia ed). Each ha dwa e
module is conside ed a p ocess which execu es ope a-
ions and synch onizes wi h o he p ocesses when da a
ans e s a e equi ed.
2.2
Dis ibu ed
Con ol
.___-.---.---.-..___
-...--___.....-.-
Figu e
1
:
Local Con olle s o ganiza ion
Con ol is comple ely dis ibu ed in s ic,h a way
ha o each da a-pa h block
(o
a
g oup o da a-
pa h blocks) he e is a
local con olle
(LC:).
A
local
con olle has wo ypes o handshaking signals (see
igu e
1):
Local signals: eques
and
comple ion
signals o he
synch oniza ion wi h he da a-pa h block being con-
olled and o he signals such as he ope a ion code
o ALUs
o
he selec ion code o mul iplexo s.
0
Global signals
o he synch oniza ion associa ed
wi h da a ans e s be ween blocks.
The g anula i y o he con ol dis ibu ion may a y
o he sake o he ci cui pe o mance. He ea e and
wi hou loss o gene ali y, we will conside ha an LC
exis s o each co npu a ion block
(o
egis e ) and i s
inpu mul iplexo s.
The execu ion o an ope a ion has he ollowing
s eps:
1
Inpu da a a e ead om egis e s.
2
Mul iplexo s ans e inpu da a o hei co e-
sponding unc ional uni inpu .
3
Ope a ion is execu ed in a unc ional uni .
4
Mul iplexo s ans e ou pu da a o a egis e
5
Ou pu da a is la ched in o a egis e .
3
High-Le el Syn hesis: an O e iew
The sys em inpu is
a
beha io desc ip ion o he
ci cui desc ibed by a Con ol Da a Flow G aph
(CDFG). The i s s ep pe o med is
Scheduling
and
Alloca ion
( igu e
2).
Alloca ion selec s he numbe
and ype o ha dwa e modules ha will compose >he
da a-pa h. In ope a ion scheduling, ope a ions a e
dis ibu ed h ough he ime space a id a e assigned o
a ype o unc ional uni . The ou pu is a Scheduled
Da a Flow G aph (SDFG), which
is
a modi ica ion o
he p e ious CDFG con aining in o ma ion ela ed o
scheduling and alloca ion. In
Resou ce Banding
ope -
a ions a e bound o ha dwa e modules. The ou pu
is a Bound Da a Flow G aph (BDFG) whe e each op-
e a ion has been bound o an FU ins ance and each
a iable o
a
egis e . A e binding he se o ope a-
ions ha will be execu ed in each p ocess is o ally
de ined and he beha io o he local con olle s can
be de i ed
as
i is explained in sec ion
5.
4
Scheduling
We will ep esen he scheduling p oblem wi h
a
da a
low
g aph
(DFG),
G(V,E),
whe e e ices
and edges deno e ope a ions and dependencies espec-
i ely. Fo each e ex
E
V
we will use he ollowing
e minology:
o
:
execu ed
ope a ion
d, c
:
s a
and
comple ion
ime
(a e being scheduled)
unc ional uni ype ha execu es
uo
IJ~
:
pwd( )
=
szlcc( )
=
{U
I
(u,~)
E
E)
{U
I
(U,.)
E
E)
Fo now on, he ollowing assump ions will be consid-
e ed (which a e close o eali y):
0
Since con ol is e enly dis ibu ed all o e he ci -
cui , i is assumed ha delays in oduced by he
L(3
a e cons an .
0
La ching delays a e equal and cons an .
Thus, synch oniza ion and la ching delays can be in-
cluded in he delay o each ope a ion.
The lib a y o unc ional uni s (FUs) a ailable o
a gi en ec.hnology is ep esen ed by he
Delay Mal ix
6
(see igu e
4).
Each elemen
6 ,.
indica es he de-
lay o he execu ion o ope a ion
o
by he FU ype
(6j,.
=
CO
indica es ha
o
is no implemen ed by
).
We will deno e by
Fll(o)
he se o FU ypes
implemen ing
0.
In he en i onmen o asynch onous
sys ems, whe e execu ion delays a e da a-dependen ,
he
Delay Ma ix
6
ep esen s a e age delays. Thus,
scheduling imes ob ained by using
6
nus be consid-
e ed
as
es ima ed a e age p ocessing delays'.
A
esou ce ec o ,
R
=<
I ll,
I i ,.
. . ,
I n[
>,
ep-
esen s a se o esou ces a ailable o alloca ion, whe e
l il
indica es he numbe o ins ances o he FU ype
i
(I il
>
0).
Gi en a esou ce ec o
R,
we de ine he
a e age delay
o ope a ion
0,
bo,
as:
I P ,,o
I lI
-
-
-
IEFU(0)
0-
,
GWo)
6,
is a p e-scheduling es ima ion o he expec ed
exew ion delay o ope a ion
0,
assuming ha any
-
'
A
Wo s -
Case Delay h4a ix
would be
also
equi ed o cal-
cula e wo s -case p ocessing delays i iming cons ain s we e
imposed in he DFG. Dealing wi h iming cons ain s
is
ou o
he scope o his pape .
71
/
Con ol Gene a ion
A
Da a-pa h
-
SDFG
-F
Resou ce
-BDFG
0
Binding
Figu e
2:
High-le el syn hesis s eps
e ex
can be equip obabilis ically assigned o any
Finding an asynch onous schedule means de ining a
pa ial o de ing
o he e ices and
alloca ing
each
ope a ion o
a
ype o FU
so
ha he o al
es ima ed
p ocessing delay
is minimized.
4.1
Da a S uc u es
E
FU( 0).
ime
ELdus
FRT
(adde )
0
l
2
3
4
(4
(b)
(4
Figu e
3:
(a) F ame Rese a ion Table; (b) E en Lis ;
(c) Pa ially-scheduled DFG
A
F ame Rese a ion Table (FRTj)
is a da a s uc-
u e bound o a ype o FU
and epo s he num-
be
o
ac i e ins ances o ype
a each ime ins an .
FRTj
is upda ed each ime a new ope a ion is sched-
uled and bound o an FU
o
ype
.
The numbe o
ac i e ins ances can ne e be g ea e han
I l.
FRTj
can be ep esen ed
as
an
E en Lis (EL/).
ELj
is o med by
a
lis o pai s
<
ime;,
n q
>
o -
de ed by ime, whe e
n q
indic,a es he numbe o
a ailable (non-ac i e) FUs o ype
om
imei
o
iniei+l.
Figu es 3.a and 3.b depic he
FRTj
and
EL!
co esponding o he scheduled ope a ions shown
in 3.c.
Two unc ions ha e been de ined o nanaging he
E en Lis
[12]:
e
s a - ime
=
ind- ee-in e al
(EL,
min-s a - ime, delay)
This unc ion seeks in he e en lis
EL
o
he i s ime in e al o du a ion
delay
wi h
s a - ime
2
mins a - ime
such ha i has a
leas one ee FU.
This unc ion ese es a ime in e al o du a ion
delay
s a ing a
s a - ime.
0
ese e-in e al
(EL,
s a - ime, delay)
4.2
E en -Lis -Based Scheduling
Two algo i hms
o
ope a ion scheduling in asyn-
ch onous sys ems a e p esen ed in his sec. ion:
ELS
(E en -Lis Scheduling) and
ELLAS
(E en -Lis
Look-Ahead Scheduling). Bo h algo i hms selec e -
ices o be scheduled acxo ding o
a
p io i y unc ion.
They di e in he calcula ion o he p io i y unc ion:
in he o me he p io i y o each e ex is calcula ed
a he beginning
o
he algo i hm, while in he la e
i is dynamically e alua ed
as
a esul o a look-ahead
scheduling unc ion.
Du ing he execu ion o a scheduling algo i hm he
se o nodes
o
he DFG can be pa i ioned in o h ee
se s: he
Ready Se (RS),
he
Scheduled Se
(SS),
and
he
Non-Scheduled
Se
(NSS).
SS
con ains all he e -
ices al eady scheduled.
A
e ex
belongs o
RS
i i
has no been scheduled ye and
o
each
U
E
p ed( ),
U
E
SS.
The es o e ices belong o
NSS.
The
scheduling algo i hm is nex desc ibed.
ELS
(G(V,E),
6,
R)
{
o
each
in he lib a y
do
ini ializee en lis
(EL,,
I I);
calcula epa hleng hs~oend
(G,
6,
R);
RS
=
sou ce- e ices(G);
NSS
=
V
-
RS;
SS
=
0;
while RS
#
0
{
=
iiiaxp io i y e ex(RS);
inins a
=
iiiax
U,;
o
each
E
FU(w,)
do
{
u€p ed( )
niiiis a
=
iid eein e al
(EL
,
inins a ,
6 , o);
coiiiple ion,
=
inins a
+
6 ,,,,,
;
1
mln
=
such
ha
ese eiii e al
(
ELj,,,
,
niius a ,n,n,
s ,,,
,,,o);
wS
=
iiiins a jm,n
;
w,
=
coiiiple ioii min;
=
m n;
SS
=
SSU
{ };
i eable
=
{
E
NSS
I
Vu
E
p ed(w),u
E
SS};
RS
=
(RS
-
{w})
U
i eable;
NSS
=
NSS
-
i eable;
(comple ion,_,,
=
iiuii comple ion );
€FU( o)
Simila ly o
lis
scheduling[9],
his algo i hm cal-
cula es, i s , a p io i y o each e ex o he DFG.
Then e ices in
RS
a e scheduled in o de acco ding
o hei p io i y. The p io i y
o
each e ex
,
p,
is
calcda ed as he pa h leng h o he end o kDFG,
assuming ha each e ex
is execu ed in
Suo
ime.
The calcula ion o
p
can be done ecu en ly om
sink o sou ce e ices
as
ollows:
p
=
max
up
+
Suo
uEsucc( )
Fi s , all he e en lis s a e ini ialized wi h hei
co esponding numbe o esou ces
(I [),
and he p i-
o i y (pa h leng h o end) o each e ex is calcula ed.
The main loop o he algo i hm selec s, i s , he e -
ex
wi h maximum p io i y in he
Ready Se .
Then,
i calcula es he comple ion ime achie able by each
FIT ha can execu e
,,,
and selec s ha FU,
m n,
ha yields he minimum alue. Finally,
is sched-
uled and bound o
m n.
In o ma ion abou u iliza ion o esou ces is kep
in he e en lis s, and managed by unc ions
72
ind eein e al
and
ese ein e al.
When
an ope a ion can be execu ed by mo e han one ype o
FU,
ELS
ends o bind e ices wi h mo e p io i y o
as e FUs. The ime complexi y o
ELS
is
O(n
log
n).
As men ioned be o e,
ELLAS
dynamically calcu-
la es each e ex’s p io i y by using
a
look-ahead
scheduling unc ion. The ime complexi y
o
ELLAS
is O(n310gn) [12].
4.3
Resul s
Figu e
4:
Delay Ma ix used o he benchma ks.
In his sec ion, he scheduling algo i hms p e iously
p esen ed a e e alua ed. Two benchma ks ha e been
chosen o p esen he esul s o he expe i nen s: he
Di e en ial Equa ion Sol e
[8] and he
Fi h-o de
Wa e Digi al Fil e
[13]. The lib a y used o bo h
benchma ks is ep esen ed by he
Delay Ma ix
de-
pic ed in igu e
4.
Table
1:
Resul s o he Di e en ial Equa ion Sol e
and o he Ellip ic Fil e wi h
CPU
imes in
a
DEC-
sys em 5100 (all
CPU
imes
o
he ELS a e 0.Olsec.)
Figu e
5:
Schedule o he
Dz .
Eq.
Sol e
(00~+@0);
Table
4.3
p esen s ,he esul s ob ained o he wo
benchma ks conside ing di e en esou ce con ain s.
Fo he Di e en ial Equa ion
ELS
and
ELLA,Y
gi e
he same esul s.
(:PU
imes a e simila due o he
es 1
sch
lme
Figu e
6:
Schedule o he
Ellzp zc Fzl e
ob ained by
ELLAS
(@I @I
@OO)
small size o he p oblem. Figu e 5 depic s he esul -
ing schedule o one o he expe imen s. Fo he
El-
lip ic Fil e
ELLAS
is supe io o
ELS
in mos cases,
a he cos
o
highe
CPU
imes (bu s ill mode a e).
Figu e
6
shows he schedule ob ained wi h
ELLAS o
one o he expe imen s. I is wo h o emphasize he
skill o binding c i ical ope a ions o as FUs and
non-c i ical ope a ions o slow FUs when hey can be
concu en ly execu ed.
5
Binding and P ocess Synch oniza-
ion
Module binding is pe o med a e scheduling and
alloca ion in o de o bind ope a ions o ha dwa e
module ins ances. The c i e ia used o binding aims
a he educ ion
o
he connec i i y o he ci cui
so
ha ou ing a ea and communica ion delays a e min-
imized In ha espec , binding algo i hms al eady
p oposed o synch onous ci cui s can also be used
o
asynch onous ci cui s (i hey do no use con ol-s ep-
based app oaches)
[
141.
Once binding is pe o med, he sequence
o
ope -
a ions o be execu ed in each p ocess
is
comple ely
de ined. Each da a ans e be ween wo ope a ions
co esponds o
a
synch oniza ion be ween p ocesses
when he ope a ions a e bound o di e en ha dwa e
modules.
In
igu e
7
each a ow co esponds o
a
syn-
ch oniza ion be ween p ocesses o he scheduling ex-
ample o igu e 5
a.
Each da a ans e be ween
a
compu a ional block
and
a
egis e equi es an explici synch oniza ion be-
ween he p ocesses co esponding o each
o
he in-
73
Figu e
7:
Synch oniza ions be ween p ocesses (some
egis e assignmen s ha e been eplica ed o inc ease
he eadabili y o he diag am)
ol ed ha dwa e modules. Synch oniza ions a e e-
qui ed o assu e he sequenciali y imposed by da a
dependencies,
as
asynch onous sys ems do no ha e
a
global clock ha indica es he comple ion o ope a-
ions. A e he o de ing o
da a
ans e s and syn-
ch oniza ions
has
been de e mined, he beha io o
each local con olle is de i ed by de ining he an-
si ions o he handshake signals. Signal T ansi ion
G aphs
(STGs)
[4]
a e used
as
beha io al desc ip ion
o local con olle s. F om
STGs,
a
haza d- ee ci cui
can be syn hesized o each con olle . Fo mo e de-
ails, we e e he eade o
[ll],
whe e an app oach o
he syn hesis o dis ibu ed asynch onous con olle s
om high-le el desc ip ions is p oposed.
6
Conclusions and u u e
wo k
As
he design o asynch onous ci cui s is gaining ac-
cep ance, ools o high-le el syn hesis a e mo e iec-
essa y. This pape has p esen ed he i s , app oach,
o he knowledge o he au ho s, o scheduling o he
high-le el syn hesis o asynch onous ci cui s. Fo an
asynch onous iming model, in which no con ol s eps
exis , scheduling means de ining
a
pa ial o de ing o
he execu ion o he ope a ions. Basic
da a
s uc u es
and p imi i e unc ions o he ma iage nen o
ini i-
a ion
and
comple ion
ope a ion e en s ha e been de-
ined. Two algo i hms,
ELS
(O(n
log
n)
-
ime)
and
ELLAS
O(n3
log
n)
-
ime)
ha e been p oposed and
Fu he esea ch is equi ed in his eme ging a ea.
Among he issues no conside ed in his pape , we
men ion some o he mos signi ican : scheduling
ac oss basic. blocks, pipelined unc ional uni s, and
e alua e
6
.
scheduling unde iming cons ain s. On he o he
hand, u he esea ch is also equi ed in he a ea
o dis ibu ed con ol syn hesis o asynch onous sys-
ems.
Re e ences
C.L. Sei z,
In oduc ion
o
VLSI
Sys ems,
Chap e
7,
Mead and Conway (Eds.), Addison Wesley,
1981.
T.H.
Meng,
Synch oniza ion Design o Digi al Sys-
ems,
Kluwe Academic Publishe s,
1991.
G.
Mago, “Realiza ion Me hods o Asynch onous Se-
quen ial Ci cui s,”
IEEE
T ans. on Compu e s,
Vol.
C-20,
No.
3,
pp.
290-297,
Ma ch
1971.
T.A. Chu,
Syn hesis o Sel - imed
VLSI
Ci cui s om
G aph- heo e ic Speci ica ions,
Ph.D. hesis,
MIT,
June
1987.
A. J. Ma in, “Compiling Communica ing P ocesses
in o Delay-insensi i e VLSI Ci cui s,”
Dis ibu ed
Compu ing,
Vol.
1 (4),
Sp inge -Ve lag, pp.
226-234,
1986.
K.
an Be kel, J. Kessels,
M.
Roncken, R. Saeijs, and
F. Schalij, “The VLSI-p og amming language Tang am
and i s ansla ion in o handshake ci cui s,”
P oc. Eu-
opean Con e ence on design Au oma ion,
pp.
384-389,
Feb.
1991.
M.C. McFa land, A.C. Pa ke , and R. Camposano,
“Tu o ial on High-Le el Syn hesis,”
P oc. 25 h
ACM/IEEE Design Au oma ion Con e ence,
pp.
330-
336,
June
1988.
P.G. Paulin and J.P. Knigh , “Fo ce-Di ec ed Schedul-
ing in Au oma ic Da a Pa h Syn hesis,”
P oc. 4 h
A CM/IEEE Design Au oma ion Con e ence,
pp.
195-
202,
June
1987.
S.
Da idson, D. Landsko , B. D. Sh i e , and P.
W.
Malle , “Some expe imen s in local mic ocode com-
pac ion o ho izon al machines,”
IEEE T ans. on
Compu e s,
ol.
C-30,
July
1981.
[lo]
D. Ku and G. De Micheli, “Rela i e Scheduling Unde
Timing Cons ain s: Algo i hms o High-Le el Syn-
hesis o Digi al Ci cui s,”
IEEE
T ans. on Compu e -
Aided Design,
Vol.
11,
No.
6,
pp.
696-718,
June
1992.
[11]
J.
Co adella and R.M. Badia, “An Asynch onous A -
chi ec u e Model o Beha io al Syn hesis,”
P oc. Eu-
opean Con e ence
on
Design Au oma ion,
pp.
307-311,
Ma ch
1992.
[12]
R.M. Badia and J. Co adella, “High-Le el Syn-
hesis o Asynch onous Digi al Ci cui s: Scheduling
S a egies,” UPC/DAC Repo no.
RR-92/6,
No em-
be
1992.
[13]
P. Dewilde,
E.
Dep e e e, and R. Nou a, “Pa allel
and Pipelined VLSI Implemen a ion o Signal P ocess-
ing Algo i hms,” in
VLSI
and Mode n Signal P ocess-
ing,
ed.
T.
Kaila h, pp.
258-264, 1985.
[14]
C.J. Tseng and D.P. Siewio ek, “Au oma ed Syn he-
sis
o
Da a Pa hs on Digi al Sys ems,”
IEEE T ansac-
ions
on
Compu e -Aided Design o In eg a ed Ci cui s
and Sys ems,
ol. CAD-5, no.
3,
pp.
379-395,
July
1986.
74