Computational Delay Models to Estimate the Delay of Floating Cubes in CMOS Circuits

Computational DelayModels to Estimate the DelayofFloating Cubes in CMOS Circuits D. Guerrero3,4,G.Wilke1,J.L.G¨u ntzel2,M.J.Bellido3,4,J.Juan Chico3,4, Ruiz-de-Clavijo3,4,and A. Millan3,4 1Universidade Federal do Rio Grande do Sul Instituto de Inform´atica Porto Alegre -RS(Brazil) Tel.: +55 (51) 3316-6159 -Fax: +55 (51) 3316-7308 http://www.inf.ufrgs.br/ [email protected] 2Universidade Federal de Pelotas Departamento de Matem´atica, Estat´ı stica eComputa¸c˜ao Pelotas -RS(Brazil) Tel.: +55 (53) 275-7000 -Fax: +55 (53) 275-9023 http://www.ufpel.tche.br/ [email protected] 3Instituto de Microelectr´onica de Sevilla -Centro Nacional de Microelectr´onica Sevilla (Spain) Tel.: +34 955056666 -Fax: +34 955056686 http://www.imse.cnm.es 4Departamento de Tecnolog´ı aElectr´onica -Universidad de Sevilla Sevilla (Spain) Tel.: +34 954556160 -Fax: +34 954552764 http://www.dte.us.es {guerre, bellido, jjchico, paulino, amillan}@dte.us.es Abstract. The verification of the timing requirements of large VLSI circuits is generally performed by using simulation or timing analysis on eachcombinational block of the circuit. Akey factor in timing analysis is the election of the delaymodel type.Pin-to-pin delaymodels are usually employed, but their application is limited in timing analysis when dealing with floating mode or complex gates. This paper does not introduce a delaymodel but adelaymodel type called Transistor Path DelayModel (TPDM). This new type of delaymodel is specially useful for timing analysis in floating mode, since it is not required to knowthe whole input sequence to apply it, and can manage complex CMOS gates. An algorithm to get upper bounds on the stabilization time of eachgate output using TPDM is also introduced. 1Introduction One of the most importanttasks in the design process of VLSI circuits is the verification of the system. Timing verification may beperformed by electric-level P. simulation, but it demands huge execution times. An alternativeistiming simulation, that is faster because it uses less accurate delaymodels, although still requires exercising all possible input vector sequences. Designers can also rely on the input-independentapproachfor estimating the critical delayofVLSI circuits. This approachrepresents eachcombinational block of the circuit as adirect acyclic graph (DAG)[1], where nodes representgates and edges representconnections. The most simple solution relies on disregarding logic behaviour of gates and assuming the delayofthe longest path as the critical delayofthe combinational block.Hence, the critical delayproblem of acombinational block is reduced to finding its longest path, whichcan be solved in linear time by the well-known topological sort algorithm. Suchapproachisreferred to as static or topological timing analysis (TTA). However, there maynot exist anyinput pattern that exercises the longest path in the circuit, or conversely,itmay never transmit anysignal transition and hence, the critical delaymay be smaller than the delayofthe topologically longest path. Paths that never transmit asignal transition are called false paths [2] or unsensitizable paths. UnlikeTTA,functional timing analysis (FTA) takes into accountthe logic behaviour of gates so it is more accurate. This paper introduce anew type of delaymodel targeting FTA. We begin with a reviw of timing analysis related terminology.Insection 3wewill see the aplication of apin-to-pin delaymodel in timing analysis. In section 4wewill see how TPDM can solvelacks of pin-to-pin delaymodels. In section 5wewill generalizate TPDM to deal with complex gates. Finally we will introduce algorithms to employTPDM in cubesimulation. 2Floating Delay: DelayofaCube Timing analysis by pairs of vectors is computationally expensiveand can be too optimistic, since it assumes that primary inputs change simultaneously while memory elements maypresentdifferentpropagation times that can lead to misalignmentatthe inputs. Another approachistoget asafe upper bound for all the possible vector sequences ending in the same vector V.Suchabound is called the delayofthe floating vector V.Ifwecalculate the delayofall the possible floating vectors, the maximum of those delays will be an upper bound on the delayofthe circuit. The delaythusobtained is referred to as the floating delayofthe circuit. To calculate the delayofafloating vector V,every node is assumed to be at an unknown state before instant0,and the primary inputs are assumed to be stable with value Vafter instant0.Anupper bound on the instantwhen each node becomes stable is then systematically calculated. Let be Ithe set of primary inputs of alogic circuit C,aninput vector of Ccan be defined as afunction V:I→{0,1}whose domain is I.Every Wsubset of suchthat for all iin Dom(W), W(i)=V(i). Let Wbe acube, let vectors(W)bethe set {V∈input vectorsofC/W ⊆V}, the delayofcube Wis an upper bound on the set {floating delay(V)/V ∈ vectors(W)}.Toget suchanupper bound, every node is assumed to be in an unknown state before instant0,and every input i∈Dom(W)isassumed to be stable with value W(i)after instant0.Anupper bound on the instantwhen each node becomes stable is then systematically calculated. Let M={W1,.., Wn}be afinite non emptyset of cubes suchthat anypossible input vector is contained in vectors(Wj)for at least an Wj∈M,then max{delay(W)/W ∈M}is an upper bound on the delays of all the floating vectors, so it is also and upper bound on the delayofthe circuit. 3Application of Pin-to-Pin DelayModels in Cube Simulation Suppose agate Gthat receives asingle transition in input aat instant t,that is, all the inputs have been and will be alwaysstable except input a,that changes only in instant t,and the output has alwaysbeen stable before instant t.Under suchconditions, the delayofpin ais the time elapsed from tto the transition at the output of G. In simple gates this only makes sense when all the inputs but aare in non-controlling values. Apin can have differentdelays for raising transitions and falling transitions. This delayhavebeen modeled in [3], [4] and [5]. Sometimes it is possible to use apin-to-pin delaymodel to get an upper bound on the instantwhen agate output will become stable. This happens when we get an upper bound on the instantwhen one of the inputs becomes stable and we knowthat its final value is the controlling value of the gate. Forexample, suppose that the nand gate in fig. 1ispart of acircuit. If during the computation Fig. 1. A3input nand gate of the delayofacubewefind that input bwill be stable at instant t(or before) and that its final value will be the controlling value of the gate (i.e. 0), then we Vis called acube, that is, Wis afunction whose domain is asubset of Iand knowthen that the final value of output dis 1. Howeverwedonot knowthe instantwhen it becomes stable. To be pessimistic we should suppose that: –The output capacitance CLis utterly discharged at instant t,sonoPMOS transistor will be activebefore instant t(a=b=c=1before instant t). –Only the PMOS transistor of input bwill charge CLafter instant t(a=c=1 after instant t). Hence apessimistic vector sequence for this gate would be that shown in fig. 2. Note that tpbis the pin-to-pin delayofinput b.Then an upper bound on the Fig. 2. Pessimistic vector sequence for a3nand gate instantwhen dbecomes stable is t+tpb.Ifwealso find that input cbecomes stable at instant t!or before and its final value is 0, then another upper bound on the instantwhen dbecomes stable would be t!+tpc,where tpcis the pin-to-pin delayofinput c. Of course to be as accurate as possible we should alwaystake the lowest upper bound. 4The Need for Other DelayModels: Transistor Path DelayModel Pin-to-pin delaymodels do not allowcomputing the delayofany floating vector of acircuit of simple gates. We need adifferentmodel to determine an upper bound on the instantwhen agate output will become stable if the final value of all its inputs is the non-controlling value of the gate. Forexample, suppose we have to compute the delayofvector (0,0) applied to the circuit of fig. 3. We knowthat the input signals will be stable after instant twith value 0, and we have to determine an upper bound of the instantwhen the output will become stable with its final value (i.e. 1). To be pessimistic, we can assume that: –CLand anyinternal gate node in the path from Vdd to the output is utterly discharged before instant t(b=1before instant t). –Every input receives afalling transition at instant t,sonoPMOS transistor will be in saturation till the end of those transitions. Fig. 3. A2input nor gate Fig. 4. Pessimistic vector sequence for anor gate So apessimistic but possible vector sequence would be the showedinfig. 4. In this vector sequence we can not use apin-to-pin delaymodel since none of the PMOS transistors is in saturation just before instant t(that is, no input is at non controlling value just before instant t). We presentanew type of delaymodel called Transistor Path that solves this by modeling the behaviour of the gate when all its inputs change simultaneously to non-controlling value. In general, if we have asimple gate of inputs i1,..,in(where inis the input whose PMOS transistor is connected to Vdd if it is aNOR gate, or the input whose NMOS transistor is connected to ground if it is aNAND gate) that are set to noncontrolling value respectively at instants t1,..,tn(or before), we can get an upper bound on the instantwhen the output turns stable by simulating the vector sequence shown in fig. 5. To simplify we can assume that the transition time of all the input transitions aboveisthe same, but it must be an upper bound of all the transition times. The effect of multiple input switches in simple gates have been studied in [7] and [8] modeling the delayasafunction of the skew betwen input transitions. As we can see, the characterization process can be simplified by modeling only the behaviour of the gate for the most pesimistic skew. 5Generalization of Transistor Path DelayModel for Circuits Containing Complex Gates In complex gates the concept of controlling or non-controlling value does not makesense so we need amore general delaymodel. The final logic value of a complex gate is known when atransistor path from Vdd or from GND to the output is activated. Forexample suppose that in the complex gate of fig. 6we Fig. 5. Generic pessimistic vector sequence for asimple gate knowthat input cis stable with value 0after instant t1and that input bis stable with value 0after instant t2.There will be apath of conducting PMOS transistors from Vdd to the output after instant max{t1,t 2 }so we knowthat the final logic state of the output will be 1. We knowthat input signals band cwill Fig. 6. Aconducting transistor path in acomplex gate be stable after instant max{t1,t 2 }with value 0, and we have to find an upper bound on the instantwhen the output will become stable with its final value (i.e. 1). To be pessimistic and to simplify the upper bound computation, we can assume that: –CLand anyinternal gate node in the activepath from Vdd to the output is utterly discharged before instant t(c=d=1before max{t1,t 2 }). –There will be afalling transition at every input corresponding to aPMOS transistor in the path at instant max{t1,t 2 },hence no pmos transistor in the path will be conducting before those transitions. –Only the pmos transistors in the path will charge CL(a=d=1after instant max{t1,t 2 }) So apessimistic vector sequence would be the shown in fig. 7. We have simulated Fig. 7. Pessimistic vector sequence for acomplex gate this vector sequence with the electric simulator SPECTRE using 0.35 µm CMOS technology.When inputs band cchange simultaneously we have adelayof0.219 ns. If bchanges 0.1 nanoseconds before cwe have adelayof0.210 ns. If we change c0.1 ns before bwe have adelayofonly 0.154 ns, because the internal node loads before the last input transition. In order to get an upper bound on the gate delayweneed to model the behaviour of the gate when all the transistors of the path are activated simultaneously.The activation instantofatransistor path Pis the maximum among the activation instants of its transistors. If t1,..,tnare respectively upper bounds on the activation instants of those transistors, then max{t1,.., tn}is an upper bound on the activation instantofP.Ifatinstant t (or before) apath with delay dis activated and in instant t!(or before) apath of the same gate with delay d!is activated, then t+dand t!+d!are upper bounds of the instantwhen the gate output becomes stable so we should take min{t+d, t!+d!}as the upper bound. 6 Application of TPDM to Estimate the Delay of Floating Cubes For every gate type we must keep two transistor path sets: one for the set of paths from Vdd to the output and another for the set of paths from GND to the output. Forevery transistor path we must codify the set of gate inputs corresponding to transistors in that path and the set of delayparameters corresponding to that path. The set of gate inputs of the path can be implemented with an array of bits of dimension n,where nis the number of gate inputs. Let transistor paths(0) be the set of transistor paths of agate that go from GND to the output and let transistor paths(1) be the set of transistor paths that go from Vdd to the output, if the input values of the gate set the final logic state of the gate output to v,toget an upper bound of the instantwhen the gate output becomes stable we can followthis algorithm: stabilization instant upper bound(output, v)←∞ forevery path pintransistor paths(v)do if the final logicvalue of everygate input of pisnot(v)then t←∞ forevery gate input iofpdo if stabilization instant upper bound(i, not(v)) >tthen t←stabilization instant upper bound(i, not(v)) end if end for d←delay of path p if t +d<stabilization instant upper bound(output, v)then stabilization instant upper bound(output, v)←t+d end if end if end for In the algorithm, stabilization instant upper bound(s, x)isthe lowest known upper bound on the instantwhen signal sbecomes stable when its final logic value is x.For example suppose the gate in fig. 6. The set of transistors of each path from Vdd to the output could be codified using abit vector for eachpath as shown in table 1. The vector componentcorresponding to ainput will be set to 1ifand only if the path of this vector has atransistor whose gate is connected to that input. During the computation of the delayofacubewehavethat input a is stable with value 0after instant ta,input bis stable with value 0after instant tband input cis stable with value 0after instant tc.Since the first and third path shown in table 1will be activeweknowthat the final state of the gate output will be 1sowemust compute stabilization instant upper bound(output, 1) using the algorithm above. We computed the delays for the known conducting paths and obtained adelay dfor the first path and adelay d!for the third path. Valid upper bounds are then max{ta,t c }+dand max{tb,t c }+d ! .Atthe end of the algorithm, stabilization instant upper bound(output, 1)willbeequalto thelowestknownupperbound. If the final logic state of the gate output is not set, we must calculate stabilizationinstant boundupper (output,0)and stabilizationinstantupperbound(output,1), butwemustuseadifferentalgorithm.Thisisbecause,fromallthetransistor pathsthatcanbeactivated,wedonotknowwhichonewillactuallybeacti- Table 1. transisto paths(1) for the complex gate of fig. 6 path 0 path 1 path 2 path 3 transistors connected to input a 1 1 0 0 transistors connected to input b 0 0 1 1 transistors connected to input c 1 0 1 0 transistors connected to input d 0 1 0 1 delayparameters (depend on the delaymodel) ... ... ... ... vated. To be pessimistic we must takethe greater stabilization instantupper bound determined by apath that can be activated. The algorithm to get the upper bound when the final value of the gate output is unknown is the following: stabilization instant upper bound(output, v)←∞ forevery path pintransistor paths(v)do if the final logicvalue of everygate input of pisnot vorisunknownthen t←∞ forevery gate input iofpdo if stabilization instant upper bound(i, not(v)) >tthen t←stabilization instant upper bound(i, not(v)) end if end for d←delay of path p if t +d>stabilization instant upper bound(output, v)then stabilization instant upper bound(output, v)←t+d end if end if end for Forexample suppose the gate in fig. 6. The set of transistors of eachpath from GND to the output could be codified using abit vector for eachpath as shown in table 2. During the computation of the delayofacubewehave that input dis stable with value 1after instant tdand input ais stable with value 0after instant ta.Since there are no known activepaths in table 1 or 2the final logic state of the gate output is unknown. We must compute stabilization instant boundupper (output, 0) and stabilizationinstant boundupper ) usingthealgorithmabove.To get stabilization instan upper bound(output, 1) we computed the delays for the possible conducting paths in table 1and obtain adelay dfor the first path and adelay d!for the third path. Possible upper bounds then are max{ta,t cf }+dand max{tbf ,t cf }+d!,where tf stabilization instant=upperbound(c, 0) and c tstabilizationinstant bound=( bf upper b, stabilization instant upper bound(output, 1) will be equal to the biggest upper bound. To get stabilization instant upper bound(output, 0) wecomputedthedelayfortheonlypossibleconductingpathsintable2andobtainadelay d!! for the second path. The only possible upper bound then is (output,1, 0). Attheendofthealgorithm