Compu a ional DelayModels o Es ima e he
Delayo Floa ing Cubes in CMOS Ci cui s
D. Gue e o3,4,G.Wilke1,J.L.G¨u n zel2,M.J.Bellido3,4,J.Juan Chico3,4,
Ruiz-de-Cla ijo3,4,and A. Millan3,4
1Uni e sidade Fede al do Rio G ande do Sul
Ins i u o de In o m´a ica
Po o Aleg e -RS(B azil)
Tel.: +55 (51) 3316-6159 -Fax: +55 (51) 3316-7308
h p://www.in .u gs.b /
[email p o ec ed]
2Uni e sidade Fede al de Pelo as
Depa amen o de Ma em´a ica, Es a ´ı s ica eCompu a¸c˜ao
Pelo as -RS(B azil)
Tel.: +55 (53) 275-7000 -Fax: +55 (53) 275-9023
h p://www.u pel. che.b /
[email p o ec ed]
3Ins i u o de Mic oelec ´onica de Se illa -Cen o Nacional de Mic oelec ´onica
Se illa (Spain)
Tel.: +34 955056666 -Fax: +34 955056686
h p://www.imse.cnm.es
4Depa amen o de Tecnolog´ı aElec ´onica -Uni e sidad de Se illa
Se illa (Spain)
Tel.: +34 954556160 -Fax: +34 954552764
h p://www.d e.us.es
{gue e, bellido, jjchico, paulino, amillan}@d e.us.es
Abs ac . The e i ica ion o he iming equi emen s o la ge VLSI
ci cui s is gene ally pe o med by using simula ion o iming analysis on
eachcombina ional block o he ci cui . Akey ac o in iming analysis is
he elec ion o he delaymodel ype.Pin- o-pin delaymodels a e usually
employed, bu hei applica ion is limi ed in iming analysis when dealing
wi h loa ing mode o complex ga es. This pape does no in oduce a
delaymodel bu adelaymodel ype called T ansis o Pa h DelayModel
(TPDM). This new ype o delaymodel is specially use ul o iming
analysis in loa ing mode, since i is no equi ed o know he whole
inpu sequence o apply i , and can manage complex CMOS ga es. An
algo i hm o ge uppe bounds on he s abiliza ion ime o eachga e
ou pu using TPDM is also in oduced.
1In oduc ion
One o he mos impo an asks in he design p ocess o VLSI ci cui s is he
e i ica ion o he sys em. Timing e i ica ion may bepe o med by elec ic-le el
P.
simula ion, bu i demands huge execu ion imes. An al e na i eis iming sim-
ula ion, ha is as e because i uses less accu a e delaymodels, al hough s ill
equi es exe cising all possible inpu ec o sequences.
Designe s can also ely on he inpu -independen app oach o es ima ing he
c i ical delayo VLSI ci cui s. This app oach ep esen s eachcombina ional
block o he ci cui as adi ec acyclic g aph (DAG)[1], whe e nodes ep e-
sen ga es and edges ep esen connec ions.
The mos simple solu ion elies on dis ega ding logic beha iou o ga es and as-
suming he delayo he longes pa h as he c i ical delayo he combina ional
block.Hence, he c i ical delayp oblem o acombina ional block is educed o
inding i s longes pa h, whichcan be sol ed in linea ime by he well-known
opological so algo i hm. Suchapp oachis e e ed o as s a ic o opological
iming analysis (TTA).
Howe e , he e mayno exis anyinpu pa e n ha exe cises he longes pa h in
he ci cui , o con e sely,i may ne e ansmi anysignal ansi ion and hence,
he c i ical delaymay be smalle han he delayo he opologically longes
pa h. Pa hs ha ne e ansmi asignal ansi ion a e called alse pa hs [2] o
unsensi izable pa hs.
UnlikeTTA, unc ional iming analysis (FTA) akes in o accoun he logic be-
ha iou o ga es so i is mo e accu a e.
This pape in oduce anew ype o delaymodel a ge ing FTA. We begin wi h a
e iw o iming analysis ela ed e minology.Insec ion 3wewill see he aplica-
ion o apin- o-pin delaymodel in iming analysis. In sec ion 4wewill see how
TPDM can sol elacks o pin- o-pin delaymodels. In sec ion 5wewill gene al-
iza e TPDM o deal wi h complex ga es. Finally we will in oduce algo i hms o
employTPDM in cubesimula ion.
2Floa ing Delay: Delayo aCube
Timing analysis by pai s o ec o s is compu a ionally expensi eand can be oo
op imis ic, since i assumes ha p ima y inpu s change simul aneously while
memo y elemen s mayp esen di e en p opaga ion imes ha can lead o mis-
alignmen a he inpu s.
Ano he app oachis oge asa e uppe bound o all he possible ec o se-
quences ending in he same ec o V.Suchabound is called he delayo he
loa ing ec o V.I wecalcula e he delayo all he possible loa ing ec o s,
he maximum o hose delays will be an uppe bound on he delayo he ci -
cui . The delay husob ained is e e ed o as he loa ing delayo he ci cui .
To calcula e he delayo a loa ing ec o V,e e y node is assumed o be a
an unknown s a e be o e ins an 0,and he p ima y inpu s a e assumed o be
s able wi h alue Va e ins an 0.Anuppe bound on he ins an when each
node becomes s able is hen sys ema ically calcula ed.
Le be I he se o p ima y inpu s o alogic ci cui C,aninpu ec o o Ccan
be de ined as a unc ion V:I→{0,1}whose domain is I.E e y Wsubse o
such ha o all iin Dom(W), W(i)=V(i).
Le Wbe acube, le ec o s(W)be he se {V∈inpu ec o so C/W ⊆V},
he delayo cube Wis an uppe bound on he se { loa ing delay(V)/V ∈
ec o s(W)}.Toge suchanuppe bound, e e y node is assumed o be in an
unknown s a e be o e ins an 0,and e e y inpu i∈Dom(W)isassumed o be
s able wi h alue W(i)a e ins an 0.Anuppe bound on he ins an when each
node becomes s able is hen sys ema ically calcula ed. Le M={W1,.., Wn}be
a ini e non emp yse o cubes such ha anypossible inpu ec o is con ained
in ec o s(Wj) o a leas an Wj∈M, hen max{delay(W)/W ∈M}is an
uppe bound on he delays o all he loa ing ec o s, so i is also and uppe
bound on he delayo he ci cui .
3Applica ion o Pin- o-Pin DelayModels in Cube
Simula ion
Suppose aga e G ha ecei es asingle ansi ion in inpu aa ins an , ha is,
all he inpu s ha e been and will be alwayss able excep inpu a, ha changes
only in ins an ,and he ou pu has alwaysbeen s able be o e ins an .Unde
suchcondi ions, he delayo pin ais he ime elapsed om o he ansi ion
a he ou pu o G. In simple ga es his only makes sense when all he inpu s
bu aa e in non-con olling alues. Apin can ha e di e en delays o aising
ansi ions and alling ansi ions. This delayha ebeen modeled in [3], [4] and
[5].
Some imes i is possible o use apin- o-pin delaymodel o ge an uppe bound
on he ins an when aga e ou pu will become s able. This happens when we
ge an uppe bound on he ins an when one o he inpu s becomes s able and
we know ha i s inal alue is he con olling alue o he ga e. Fo example,
suppose ha he nand ga e in ig. 1ispa o aci cui . I du ing he compu a ion
Fig. 1. A3inpu nand ga e
o he delayo acubewe ind ha inpu bwill be s able a ins an (o be o e)
and ha i s inal alue will be he con olling alue o he ga e (i.e. 0), hen we
Vis called acube, ha is, Wis a unc ion whose domain is asubse o Iand
know hen ha he inal alue o ou pu dis 1. Howe e wedono know he
ins an when i becomes s able. To be pessimis ic we should suppose ha :
–The ou pu capaci ance CLis u e ly discha ged a ins an ,sonoPMOS
ansis o will be ac i ebe o e ins an (a=b=c=1be o e ins an ).
–Only he PMOS ansis o o inpu bwill cha ge CLa e ins an (a=c=1
a e ins an ).
Hence apessimis ic ec o sequence o his ga e would be ha shown in ig. 2.
No e ha pbis he pin- o-pin delayo inpu b.Then an uppe bound on he
Fig. 2. Pessimis ic ec o sequence o a3nand ga e
ins an when dbecomes s able is + pb.I wealso ind ha inpu cbecomes
s able a ins an !o be o e and i s inal alue is 0, hen ano he uppe bound on
he ins an when dbecomes s able would be !+ pc,whe e pcis he pin- o-pin
delayo inpu c. O cou se o be as accu a e as possible we should always ake
he lowes uppe bound.
4The Need o O he DelayModels: T ansis o Pa h
DelayModel
Pin- o-pin delaymodels do no allowcompu ing he delayo any loa ing ec o
o aci cui o simple ga es. We need adi e en model o de e mine an uppe
bound on he ins an when aga e ou pu will become s able i he inal alue
o all i s inpu s is he non-con olling alue o he ga e. Fo example, suppose
we ha e o compu e he delayo ec o (0,0) applied o he ci cui o ig. 3. We
know ha he inpu signals will be s able a e ins an wi h alue 0, and we
ha e o de e mine an uppe bound o he ins an when he ou pu will become
s able wi h i s inal alue (i.e. 1). To be pessimis ic, we can assume ha :
–CLand anyin e nal ga e node in he pa h om Vdd o he ou pu is u e ly
discha ged be o e ins an (b=1be o e ins an ).
–E e y inpu ecei es a alling ansi ion a ins an ,sonoPMOS ansis o
will be in sa u a ion ill he end o hose ansi ions.
Fig. 3. A2inpu no ga e
Fig. 4. Pessimis ic ec o sequence o ano ga e
So apessimis ic bu possible ec o sequence would be he showedin ig. 4. In
his ec o sequence we can no use apin- o-pin delaymodel since none o he
PMOS ansis o s is in sa u a ion jus be o e ins an ( ha is, no inpu is a non
con olling alue jus be o e ins an ). We p esen anew ype o delaymodel
called T ansis o Pa h ha sol es his by modeling he beha iou o he ga e
when all i s inpu s change simul aneously o non-con olling alue. In gene al,
i we ha e asimple ga e o inpu s i1,..,in(whe e inis he inpu whose PMOS
ansis o is connec ed o Vdd i i is aNOR ga e, o he inpu whose NMOS
ansis o is connec ed o g ound i i is aNAND ga e) ha a e se o non-
con olling alue espec i ely a ins an s 1,.., n(o be o e), we can ge an uppe
bound on he ins an when he ou pu u ns s able by simula ing he ec o
sequence shown in ig. 5. To simpli y we can assume ha he ansi ion ime o
all he inpu ansi ions abo eis he same, bu i mus be an uppe bound o all
he ansi ion imes. The e ec o mul iple inpu swi ches in simple ga es ha e
been s udied in [7] and [8] modeling he delayasa unc ion o he skew be wen
inpu ansi ions. As we can see, he cha ac e iza ion p ocess can be simpli ied
by modeling only he beha iou o he ga e o he mos pesimis ic skew.
5Gene aliza ion o T ansis o Pa h DelayModel o
Ci cui s Con aining Complex Ga es
In complex ga es he concep o con olling o non-con olling alue does no
makesense so we need amo e gene al delaymodel. The inal logic alue o a
complex ga e is known when a ansis o pa h om Vdd o om GND o he
ou pu is ac i a ed. Fo example suppose ha in he complex ga e o ig. 6we

Fig. 5. Gene ic pessimis ic ec o sequence o asimple ga e
know ha inpu cis s able wi h alue 0a e ins an 1and ha inpu bis
s able wi h alue 0a e ins an 2.The e will be apa h o conduc ing PMOS
ansis o s om Vdd o he ou pu a e ins an max{ 1,
2
}so we know ha he
inal logic s a e o he ou pu will be 1. We know ha inpu signals band cwill
Fig. 6. Aconduc ing ansis o pa h in acomplex ga e
be s able a e ins an max{ 1,
2
}wi h alue 0, and we ha e o ind an uppe
bound on he ins an when he ou pu will become s able wi h i s inal alue
(i.e. 1). To be pessimis ic and o simpli y he uppe bound compu a ion, we can
assume ha :
–CLand anyin e nal ga e node in he ac i epa h om Vdd o he ou pu is
u e ly discha ged be o e ins an (c=d=1be o e max{ 1,
2
}).
–The e will be a alling ansi ion a e e y inpu co esponding o aPMOS
ansis o in he pa h a ins an max{ 1,
2
},hence no pmos ansis o in
he pa h will be conduc ing be o e hose ansi ions.
–Only he pmos ansis o s in he pa h will cha ge CL(a=d=1a e ins an
max{ 1,
2
})
So apessimis ic ec o sequence would be he shown in ig. 7. We ha e simula ed
Fig. 7. Pessimis ic ec o sequence o acomplex ga e
his ec o sequence wi h he elec ic simula o SPECTRE using 0.35 µm CMOS
echnology.When inpu s band cchange simul aneously we ha e adelayo 0.219
ns. I bchanges 0.1 nanoseconds be o e cwe ha e adelayo 0.210 ns. I we
change c0.1 ns be o e bwe ha e adelayo only 0.154 ns, because he in e nal
node loads be o e he las inpu ansi ion. In o de o ge an uppe bound on he
ga e delayweneed o model he beha iou o he ga e when all he ansis o s o
he pa h a e ac i a ed simul aneously.The ac i a ion ins an o a ansis o pa h
Pis he maximum among he ac i a ion ins an s o i s ansis o s. I 1,.., na e
espec i ely uppe bounds on he ac i a ion ins an s o hose ansis o s, hen
max{ 1,.., n}is an uppe bound on he ac i a ion ins an o P.I a ins an
(o be o e) apa h wi h delay dis ac i a ed and in ins an !(o be o e) apa h
o he same ga e wi h delay d!is ac i a ed, hen +dand !+d!a e uppe
bounds o he ins an when he ga e ou pu becomes s able so we should ake
min{ +d, !+d!}as he uppe bound.
6
Applica ion o TPDM o Es ima e he Delay o Floa ing
Cubes
Fo e e y ga e ype we mus keep wo ansis o pa h se s: one o he se o pa hs
om Vdd o he ou pu and ano he o he se o pa hs om GND o he ou pu .
Fo e e y ansis o pa h we mus codi y he se o ga e inpu s co esponding o
ansis o s in ha pa h and he se o delaypa ame e s co esponding o ha
pa h. The se o ga e inpu s o he pa h can be implemen ed wi h an a ay o bi s
o dimension n,whe e nis he numbe o ga e inpu s. Le ansis o pa hs(0)
be he se o ansis o pa hs o aga e ha go om GND o he ou pu and
le ansis o pa hs(1) be he se o ansis o pa hs ha go om Vdd o he
ou pu , i he inpu alues o he ga e se he inal logic s a e o he ga e ou pu
o , oge an uppe bound o he ins an when he ga e ou pu becomes s able
we can ollow his algo i hm:
s abiliza ion ins an uppe bound(ou pu , )←∞
o e e y pa h pin ansis o pa hs( )do
i he inal logic alue o e e yga e inpu o pisno ( ) hen
←∞
o e e y ga e inpu io pdo
i s abiliza ion ins an uppe bound(i, no ( )) > hen
←s abiliza ion ins an uppe bound(i, no ( ))
end i
end o
d←delay o pa h p
i +d<s abiliza ion ins an uppe bound(ou pu , ) hen
s abiliza ion ins an uppe bound(ou pu , )← +d
end i
end i
end o
In he algo i hm, s abiliza ion ins an uppe bound(s, x)is he lowes known
uppe bound on he ins an when signal sbecomes s able when i s inal logic
alue is x.Fo example suppose he ga e in ig. 6. The se o ansis o s o each
pa h om Vdd o he ou pu could be codi ied using abi ec o o eachpa h as
shown in able 1. The ec o componen co esponding o ainpu will be se o
1i and only i he pa h o his ec o has a ansis o whose ga e is connec ed o
ha inpu . Du ing he compu a ion o he delayo acubeweha e ha inpu a
is s able wi h alue 0a e ins an a,inpu bis s able wi h alue 0a e ins an
band inpu cis s able wi h alue 0a e ins an c.Since he i s and hi d
pa h shown in able 1will be ac i eweknow ha he inal s a e o he ga e ou -
pu will be 1sowemus compu e s abiliza ion ins an uppe bound(ou pu , 1)
using he algo i hm abo e. We compu ed he delays o he known conduc ing
pa hs and ob ained adelay d o he i s pa h and adelay d! o he hi d pa h.
Valid uppe bounds a e hen max{ a,
c
}+dand max{ b,
c
}+d
!
.A he end
o he algo i hm, s abiliza ion ins an uppe bound(ou pu , 1)willbeequal o
helowes knownuppe bound.
I  he inal logic s a e o  he ga e ou pu  is no  se , we mus  calcula e
s abiliza ionins an bounduppe (ou pu ,0)and
s abiliza ionins an uppe bound(ou pu ,1),
bu wemus useadi e en algo i hm.Thisisbecause, omall he ansis o
pa hs ha canbeac i a ed,wedono knowwhichonewillac uallybeac i-
Table 1. ansis o pa hs(1) o he complex ga e o ig. 6
pa h 0 pa h 1 pa h 2 pa h 3
ansis o s connec ed o inpu a 1 1 0 0
ansis o s connec ed o inpu b 0 0 1 1
ansis o s connec ed o inpu c 1 0 1 0
ansis o s connec ed o inpu d 0 1 0 1
delaypa ame e s (depend on he delaymodel) ... ... ... ...
a ed. To be pessimis ic we mus ake he g ea e s abiliza ion ins an uppe
bound de e mined by apa h ha can be ac i a ed. The algo i hm o ge he
uppe bound when he inal alue o he ga e ou pu is unknown is he ollowing:
s abiliza ion ins an uppe bound(ou pu , )←∞
o e e y pa h pin ansis o pa hs( )do
i he inal logic alue o e e yga e inpu o pisno o isunknown hen
←∞
o e e y ga e inpu io pdo
i s abiliza ion ins an uppe bound(i, no ( )) > hen
←s abiliza ion ins an uppe bound(i, no ( ))
end i
end o
d←delay o pa h p
i +d>s abiliza ion ins an uppe bound(ou pu , ) hen
s abiliza ion ins an uppe bound(ou pu , )← +d
end i
end i
end o
Fo example suppose he ga e in ig. 6. The se o ansis o s o eachpa h
om GND o he ou pu could be codi ied using abi ec o o eachpa h
as shown in able 2. Du ing he compu a ion o he delayo acubeweha e
ha inpu dis s able wi h alue 1a e ins an dand inpu ais s able wi h
alue 0a e ins an a.Since he e a e no known ac i epa hs in able 1
o 2 he inal logic s a e o he ga e ou pu is unknown. We mus compu e
s abiliza ion ins an bounduppe (ou pu , 0) and
s abiliza ionins an bounduppe )
using healgo i hmabo e.To ge s abiliza ion ins an uppe bound(ou pu , 1)
we compu ed he delays o he possible conduc ing pa hs in able 1and ob-
ain adelay d o he i s pa h and adelay d! o he hi d pa h. Possi-
ble uppe bounds hen a e max{ a,
c }+dand max{ b ,
c }+d!,whe e
s abiliza ion ins an =uppe bound(c, 0) and
c
s abiliza ionins an bound=(
b uppe b,
s abiliza ion ins an uppe bound(ou pu , 1) will be
equal o he bigges uppe bound. To ge
s abiliza ion ins an uppe bound(ou pu ,
0)
wecompu ed hedelay o  heonlypossibleconduc ingpa hsin able2andob-
ainadelay d!! o he second pa h. The only possible uppe bound hen is
(ou pu ,1,
0).
A  heendo  healgo i hm