C.-J. SEGER and J.A. BRZOZOWSKI 1. Introduction The ideas to be
Contents
1. 6 J A Brzozowski and M Yoeli Digital Networks Prentice Hall Englewood Cliffs NJ 1976 7 J A Brzozowski and M Yoeli On a ternary model of gate networks IEEE Trans Compui C 28 3 1979 178 183 8 E B Eichelberger Hazard detection in combinational and sequential switching circuits 13M J Res Develop 9 1965 90 99 9 J S Jephson R P McQuarrie and R E Vogelsberg A three levei design verification system IBM Systems J 8 3 1969 178 188 10 SimuTec SILOS Logic Simulator User s Manual2. It is this state that causes gate 5 to be unstable in the ternary simulation and eventually leads to the in y In general the discrepancy occurs because of the loss of information in the ternary simulation where we only use the average of the states reachable It appears that this pessimism occurs only in pathological examples and that for most practical circuits the ternary and the binary AED analysis correspond exactly However the problem of characteri ing the class of networks for which the two models agree remains open 7 Summary In this paper we have presented a new ternary simulation algorithm that can easily replace the unit delay algorithm in simulators The algorithm is very closely related to the binary almost equal delay model and hence is capable of detecting critical races under the assumption that all delays are approximately but not exactly equal Co nputationally the ternary algorithm is of the same order of complexity as the unit delay method in the worst case it involves twice as many function 66 C J Seger J A Brzozowski evaluations A major disadvantage with both this ternary algorithm and with the unit delay method is that the algorithms are not guaranteed to halt One can easily test whether a ternary stable state is reached by comparing y and y If y y and y is binary we know the circuit reliably reaches a unique stable state Otherwise a critical race or an oscillation is likely and further ana
3. Wp all the instabilities have been removed from V one way or another Thus we consider the previous race unit as completed and now start a new one by entering the race state yP U y where each unstable gate of y has an equal chance of winning If Wp then some of the instabilities of V still remain unsatisfied these are precisely all the gates in Wp These gates are given preference over any new instabilities that may have been introduced by the change from y to y We illustrate this definition by the following example Consider the network N of Fig 1 in state x 0 y 100 which is stable We now let X 1 and note that U y 1 2 Thus the network starts in the race state 100 1 2 The graph of the relation p is shown in Fig 6 where each edge has a label showing the gates that change during the transition corresponding to the edge For now ignore the _marking on some edges The relation graph shown in Fig 6 describes all the possible states that can be reached during the transition from the initial state y 100 when the input changes from 0 to 1 However we are normally interested only in the final outcome of the transition Thus we will consider only the set of cycles in the relation graph of 100 1 2 1 2 110 4 i i 019 2 3 000 o Lon 2 Fig 6 Race analysis of N according to the AED method 54 C J Seger J A Brzozowski p Note that by
4. is always marked and hence will also exist in Gp Conversely every stable state of Gp is a stable state of G by construction of R O For the next proposition we need a new concept Given any cycle yt V 09 V yy v in the graph G we call a race state y V initiating in this cycle iff the edge y V y V is marked where y V is interpreted as y V Proposition 3 3 Every simple cycle C in G of length 2 must contain at least two distinct initiating states in C Proof For any edge y V yi V in such a cycle either the edge is marked Case 2 a or V is a proper subset of V Case 2 b Thus from any race Optimistic ternary simulation of gate races 57 state in C we must reach an initiating state in C in a finite number of steps Starting from any initiating state y V in C we eventually must reach another initiating state j V in C We argue that these two race states must be different This is because the edge leaving y V involves changing at least one variable say y from V This variable cannot change again until a new initiating state in C is reached Thus y and y differ at least in O We now wish to show that the cyclic behavior predicted by p is in some sense preserved in R For any cycle C of race states in the graph G let I7 C be the sequence of initiating states of C in the same order as in C The AED model of Section 2 relation p and the step
5. subsets constructed by the subset construction when converting the nondeterministic finite state machine to a deterministic finite state machine In Fig 10 we show the deterministic finite state machine corresponding to the nondeterministic machine of Fig 9 We close this section with a discussioi of some limitations of the stepwise AED model One of the basic assumpiions in this model is that delays are only associated with gates and that delays are inertial in their nature In many real circuits these assumptions can be well justified However there is also a danger that the model may become unrealistic under certain conditions The model is only accurate as long as races from different race units do not get mixed up In general under the assumption that all gates have delays 4 in the interval 5 the following condition makes sure that the kth race unit does not get mixed up with the k 1 st k 6 e gt k 1 S e The condition states that the time to complete k changes in the fastest gates each with delay should be greater than the time required for k 1 slowest gates each with delay What can happen if the above condition is not satisfied is that the model may omit certain races that potentially could exist In summary a sufficient condition for the stepwise AED model to be accurate for at least k steps is that R N 2k 1 For example if the uncertainty of the delays in the gat
6. that the only likely final outcome is the stable state 0101000 However the GMW model will allow the possibility that y changes before y and that the state 0101001 is also reachable The almost equal delay AED model formally defined later represents an attempt to reduce the above pessimism by assuming that roughly speaking no gate delay exceeds the sum of any two gate delays Thus the AED model predicts only the state 0101000 as the outcome for the circuit of Fig 4 because the delay of gate 5 is assumed to be smaller than the sum of delays of gates 1 2 3 and 4 Note that the AED model extended to multiple winners is clearly more informative than the UD model since it always includes the outcome predicted by the UD model In this paper we define a new stepwise AED model and compare it with the original AED model We show that the two models are equivalent with respect to their capability of predicting the outcome of a transition However the new stepwise model has the attractive property of being closely related to a time scale hence it is possible to obtain some timing information from the analysis A major difficulty with models such as the GMW and AED is that the number of steps involved can be exponential in the number of gates To overcome this ternary simulation has been used 1 9 to perform the analysis more efficiently However the ternary simulation algorithm as suggested by Eichelberger 8 corre sponds to a binary
7. the cycle Dg in Gr such that I7 C Dr The final part of Theorem 3 4 follows immediately from the observation that a gate can change at most once between two initiating states C 4 Race units The definition of Q and R as given above can be simplified since it is possib to avoid using race states This follows because in any state y V in Q the set is uniquely determined by y V U y Below we give a different algorithm for computing Q and R where we do not explicitly form the graph of p The reader can easily verify that the result is equivalent to the previous definition 58 C J Seger J A Brzozowski As before we consider a gate network defined by x y and Y A sequence 2 S z S z S k 0 is called a race unit if i z B is a gate state and S U 2 ii z is state z with all the gate outputs in the set 4 complemented where A is any nonempty subset of S also S S A a U z and iii S Note that S gt S gt gt S where gt denotes proper containment We compute the set Z and also the relation o on Z inductively as follows Algorithm 4 1 Let x y be a stable total state and let the input change to X Basis y Z Induction step For every y Z if there exists a race unit beginning with y U y and ending with z then ze Z and yoz Now to obtain Q and R replace each state ye Z by y U y in Q and let y U y R z U z iff
8. the excitation of the gate depends only on the new input value On the other hand the instability of gate 2 depends on gate 1 which is unstable if gate 1 changes first gate 2 becomes stable Hence in the stepwise AED model we can reach in one race unit the states 00 or 01 Note that in the next race unit gate 2 will again be unstable but when re evaluated it will be forced to the binary value 0 This is also consistent with the stepwise AED model In the description above we simplified the re evaluation of the excitation of the unstable gates slightly As the following example shows it is not correct to use the y a b Fig 11 a Network N b network N Optimistic ternary simulation of gate races l values of for all gates Study network N of Fig 11 b started in the stable state x 0 y 1 and with the new input x 1 We immediately get t but if we use that value for the re evaluation the TAED model will predict that the state after one race unit will be However the stepwise AED model only predicts the state y 0 The reason for this discrepancy is that when there is a self loop the that the gate depends on is coming from itself Hence the only way to remove the instability of the gate is to change its state The solution to this problem is simply to use the old gate state for gate j when re evaluating gate We will use the notation t to denote the vector obtained from by replacin
9. yoz From now on we will be working with Z and rather than with Q and R when referring to the stepwise AED model To illustrate these ideas consider network N of Fig 1 as before started in the stable state x 0 y 100 and with the new input x 1 Since U y 1 2 there are only three possible race units starting with 100 1 2 1 100 1 2 000 2 100 1 2 110 1 010 and 3 100 1 2 010 Therefore we add the states 000 and 010 to Z and add the pairs 100 000 and 100 010 to the relation o It is easy to show that from the state 000 we can only go to 000 and from state 010 we can end up in 000 or 001 From 001 we can only reach 001 In summary Z 100 000 010 001 and the relation o over Z is as illustrated by the graph of Fig 9 Note the correspondence between Fig 9 and Fig 7 It is now convenient to interpret Fig 9 as a nondeterministic finite state machine with initial state 100 and as its only input letter After one race unit i e after roughly units of time we may nondeterministic t1y reach the states 000 or 010 100 100 219 000 010 000 004 A000 001 Fig 9 Stepwise AED analysis of N Fig 10 Corresponding 2terministic finite state inmachine io Fig 9 Optimistic ternary simulation of gate races 59 etc Let Z y and let Z be the set of states of Z reachable after i steps i e Z z y o z Note that these sets are the same as the
10. GMW analysis of the network assuming both gate and wire delays 3 4 and is therefore even more pessimistic than the GMW analysis To overcome this we propose a new ternary algorithm called the ternary almost equal delay TAED model This is a stepwise algorithm of the same complexity as the UD method but it takes into account possible races In fact we show that the TAED model is closely related to the stepwise AED model 2 The binary almost equal delay model The almost equal delay AED model was originally defined using the single winner concept for simplicity 5 6 In this paper we consider the more general multiple winner version of the model which is described below This generalization is quite straightforward The basic idea is illustrated in Fig 5 Suppose network N of Fig 1 starts in state 100 at time 0 with gates 1 and 2 unstable as shown in Fig 5 Suppose now that gate i 100 3i e 410 a ee a b Fig 5 Illustrating the AED idea a possible transition b timing diagram 52 C J Seger J A Brzozowski 2 wins the race at time t and that as a result of that change in gate 2 gate 3 becomes unstable Under the almost equal delay assumption it is unreasonable to let gate 3 win the new race between gates 1 and 3 since ie 1 has already been waiting for t units of time The model will remember this fact and will only permit gate 1 to change in state 110 predicting the
11. Theoretical Computer Science 61 1988 49 66 49 North Holland AN OPTIMISTIC TERNARY SIMULATION OF GATE RACES C J SEGER and J A BRZOZOWSKI Department of Computer Science University of Waterloo Waterloo Ontario Canada N2L 3G1 Communicated by M Nivat Received May 1987 Abstract The detection of timing problems in digital networks is of considerable importance In particular it is desirable to have efficient methods for discovering critical races and hazards Unfortunately commercial simulators rarely provide such facilities in fact the simulators usually assume that all the gate delays are exactly equal In contrast to this binary race analysis frequently assumes that gate delays can be arb irarily large though finite An exception to this is the almost equal delay race model where gates have different delays but the difference between any two delays cannot be arbitrary The difficulty with the use of this model is that it is computationally very inefficient In this paper we define a new ternary model which is very closely related to the binary almost equal delay model Moreover the ternary model is considerably more efficient as efficient as the unit delay model consequently it could easily be incorporated in simulators 1 Introduction The ideas to be presented will be introduced by examples note that these examples were chosen for their simplicity and not necessarily their usefulness Consider the circuit of Fig 1 th
12. e unit delay UD model in which all gates are assumed to have exactly equal delays In the state x 1 y 100 commas omitted from 1 0 0 for simplicity gates 1 and 2 are unstable and will both change Consequently the next state is 010 Now gates 2 and 3 are unstable and state 001 is reached This state is stable In summary the unit delay model predicts that the final outcome of this transition is the stable state 001 see Fig 2 where unstable gates are indicated by underlining In contrast to this the General Multiple Winner GMW model 7 permits the possibility of unequal delays The model assumes that any nonempty subset of the set of unstable gates can change in any race In Fig 3 we show the GMW analysis of network N If gate 1 is faster in state 100 the state 000 may be reached This is also a stable state and represents a likely outcome This shows that the UD model is inaccurate In fact the only justification of the use of the UD model appears to be its simplicity On the other hand the GMW model is too pessimistic as we show below Consider the circuit of Fig 4 started in the stable state x 0 y 1010100 and let x change to 1 It is reasonable to assume that y will change to 0 before y _ IO Fig 2 Unit delay analysis of network N Fig 3 Race analysis of N according to the GMW model Ye Fig 4 Network N Optimistic ternary simulation of gate races 51 changes to 1 and
13. e behavior of this circuit is governed by the following equations Y x Y xy Y yt y3 where for each gate y denotes the present output of gate i and Y called the excitation of gate i gives the value of the boolean function computed by gate i When y Y the gate has no tendency to change and we say that it is stable If y Y then the gate is unstable and the output y tries to change to Y This change does not always happen because it is possible that an earlier change in some other gate may cause Y to become equal to y This corresponds to the fact that the delay Fig 1 Network N This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant A0871 and by ascholarship from the Institute for Computer Research University of Waterloo 0304 3975 88 3 50 1988 Elsevier Science Publishers B V North Holland 50 C J Seger J A Brzozowski associated with gate i is inertial in the sense that short periods of instability are tolerated without any change Now suppose the circuit of Fig 1 is started with x 0 and y y1 Y2 3 1 0 0 which is a stable state What happens when x is changed to 1 This is the type of problem that we are concerned with in this paper Any state in which more than one gate is unstable at the same time is called a race The outcome of a race depends very much on the model used Commercial simulators like SILOS 10 or MOSSIM 2 use th
14. e sure that the R relation holds caly between states reachable by complete race units We will show that the R reiation contains all the useful information of the old AED relation p Assume the network is started in the stable state x y and that the new input is x For convenience let G be the directed graph of the relation p and Gr be the directed graph of the relation R Note that G and Gz depend not only on the network but also on the initial state and the input change Proposition 3 1 In the graph Gp every node y V e Q is reachable from the initial race state y U y Proof First note that by the definition of p all nodes in G are reachable from the initial race state y U y Consider y V Q either y V is the initial state or it has a marked edge j V y V in G into it Obviously if it is the initial state there is nothing to prove Otherwise study the state 7 V Note that jy V must be reachable from y U y in G and hence there must exist a path in G from y U y to y V ending with a marked edge In this path some other edges might also be marked but that will only mean that we can reach y V in Gr by going through more than one node Hence the claim follows O Proposition 3 2 The stable states of G are the same as the stable states of Gr Proof All stable states of G are of the form y with an edge y y Note that this type of edge in G
15. er can verify that R is as shown in Fig 7 The reader should note that the knowledge of a race state y V alone does not provide sufficient timing information about race units Consider the network N described by the following equations Y Xy25 Y2 x Y3 y2 started in the stable state x 9 y 000 and with the new input x 1 We use some strange gates in this network in order to keep the example small similar phenomena occur in more realistic larger circuits In Fig 8 we show the graph of the relation p for this transition It is easy to verify that the states 000 1 2 010 3 and 100 1 2 oio 2 3 000 001 0 O Fig 7 Relation R derived from p of Fig 6 ooo 1 2 490 2 Fig 8 AED analysis of network N3 56 C J Seger J A Brzozowski 110 1 3 are all in Q and that 000 1 2 R 010 3 because the change in gate 2 completes the race unit started in 000 1 2 When state 010 3 is reached in this way the instability of gate 3 represents a new race unit However despite the fact that the states 110 1 3 and 010 3 are both in Q and 110 1 3 9 010 3 they are not related by R The reason for this is that the transition from 110 1 3 to 010 3 does not represent the completion of a race unit because gate 3 is still unstable and that condition started in state 110 1 3 By requiring that the last edge in the p path be marked we mak
16. es is 10 the stepwise AED model is accurate for at least five steps However the reader should note that the above condition is only a sufficient condition in many cases the AED model is accurate for more than k steps 5 The TAED medel In this section we describe a ternary simulation method which is related to the stepwise AED model For more details about ternary simulation in general the reader should refer to 7 Let T 0 1 3 The values 0 and 1 represent the usual logic levels and 3 represents an unknown value We will use the following convention Variables like y etc which take values from B 0 1 will have corresponding variabies y etc taking values from T The partial order lt on T is defined by t lt f forall te T s and 1 lt 5 We extend the partial order lt to T in the usual way t lt r iff lt r foralli 1 m 60 C J Seger J A Brzozowski The statement t lt r means that whenever r is binary then has the same binary value as r but r may contain more unknown components i e components with value 4 Thus r has more uncertainty than For any vector of boolean functions f B gt B its ternary extension f T gt T is defined by f t lub f a ae B and a lt t It follows that for te B f t f t i e on binary vectors the ternary extension agrees with the original function The ternary extension obeys the following monotonicity property 7 t lt
17. g the jth component by y In network N we get x e 1 1 11 0 and hence the TAED model will correspond to the stepwise AED model We now formally define the TAED method We define the function next as follows Let x be the new binary input and let y be any ternary gate state We calculate the successor state of y as shown below function next y e 7 T for j 1 to n do first calculate the intermediate state t t lub y Y x y for j 1 to n do re evaluate the excitation if 4 gt then y x t m Sin ct VS eet else I 3 return y The TAED algorithm consists of repeatedly applying next Note that this will either lead to a stable ternary state or an oscillation In this respect the TAED method is similar to the unit delay method used by most commercial simulators To illustrate the algorithm consider network N of Fig 1 started in the stable state x 0 y 100 and with the new input x 1 The first time we call next we get the following intermediate values t luely y lub 1 x lub 1 0 3 t lub y Yo X y lub 0 Xy lub 0 1 3 t lub y 3 y lub 0 y2 y3 lub 0 0 0 Hence t 440 In the second step of the algoritm the gates with 3 in the intermediate state are re eva uated using the intermediate state except foi the value of the gate 62 C J Seger J A Brzozowski itself for which we use the old value F
18. lysis is required Since there are at most 3 reachable ternary states it is decidable whether the analysis predicts aunic binary stable state However for large networks this decision may involve an excessive amount of computation For such reasons commercial simulators simply terminate the computation when the number of steps exceeds some arbitrarily chosen relatively small limit The same approach can be used here One can argue that a practical circuit that does not stabilize in say ten race units is not very well designed Consequently the method can be made practical and should produce useful results References 1 R E Bryant Race detection in MOS circuits by ternary simulation in F Anceau and E J Aas eds VLSI 83 Elsevier Science Publishers B V Amsterdam 1983 85 95 2 R E Bryant A switch level model and simulator for MOS digital systems IEEE Trans Comput C 33 2 1984 160 177 3 J A Brzozowski and C J Seger A characterization of ternary simulation of gate networks EEE Trans Comput C 36 11 1987 1318 1327 4 J A Brzozowski and C J Seger Correspondence between ternary simulation and binary race analysis in gate networks in G Goos and J Hartmanis eds Lecture Notes in Computer Science 226 Springer Berlin 1986 69 78 5 J A Brzozowski and M Yoeli Models for analysis of races in sequential networks in A Blikle ed Lecture Notes in Computer Science 28 Springer Berlin 1975 26 32
19. n on i Basis i 0 Trivially true Induction Hypothesis Assume that for all k lt i we have that y lub z y o z Induction Step We need to show that for any z such that y o z we have y gt z But y o z implies there exists a w such that y o w and woz By the induction hypothesis w lt yf and Lemma 6 2 applies Thus y gt z O The following example shows that the inequality of the theorem can not be replaced by equality i e that the TAED model is sometimes overly pessimistic Study network N of Fig 13 started in the stable state x 0 y y y6 111000 and with the new input x 1 In Fig 14 we show the binary stepwise AED analysis of the race and in Fig 15 we show the TAED analysis Note that the for gate 5 in state y is incorrect The reason for this discrepancy between the ternary simulation Ya Fig 13 Network Ne Optimistic ternary simulation of gate races 65 111000 010100 O00000 000100 001000 001100 011000 010000 O Fig 14 Stepwise AED analysis of N y 141000 l u b Z 144000 t 00 y 0 00 l u b Z 0 1 00 t 0 0 y 01 0 0 l u b Z 014000 t3 01 0 y gt 01000 l u b Z5 010000 a b Fig 15 a TAED analysis of N b lub of the stepwise AED analysis and the binary race analysis is that in the state y not all binary states lt y are reachable and in particular the state y 011100 is not reachable from the initial state
20. nce b Y x w for w lt y Since w lt y and y b we must have w b Together this shows that gate j is unstable in any state w lt y Secondly we show that for any race sequence starting in state w gate j must change and therefore for any z such that waz we will have z b We prove this by contradiction Assume there exists a race sequence z S z S z5 S k 0 with z w S U w and S such that z b Since according to the first part above gate j is unstable in any state w lt y we can conclude that k 1 Furthermore since w lt y and by assumption y b we must have z b However by the definition of a race sequence it follows that a gate can change at most once during a race sequence since z b and z is assumed to be b it follows that z b for p 0 k Since t lub y x y it follows by the definition of ternary extension that t lub w Y x w for w lt y Furthermore by the definition of a race vnit it follows that for j 1 and p 0 k we have that z is either equal to w or Y X w We can therefore conclude that z lt lub w Y x w and hence t gt z ior p 0 k This together with the fact that z b y for p 0 k shows that gt z for p 0 k By the monotonicity of ternary extension Y x gt Y x z for p 0 k Furthermore since 4 3 we have y Y x t and since b by assumption it follows that Y
21. next state as 010 Informally we can consider that at time 0 a race unit has started involving gates 1 and 2 No other gate can enter this race unit until all the gates in the original unit are somehow satisfied A gate becomes satisfied if it either changes or becomes stable as a result of some other change These ideas will be made precise below Consider a network with n gates whose outputs are given by the vector y Vi5 5 Yn and with m inputs given by x X Xm With each gate y we associate its boolean function Y x y In the AED model a certain amount of previous race history is necessary to determine the outcome of a race We therefore define a race state to be an ordered pair y S where y B denotes a state of the network and S denotes the set of gates that are unstable in that state and are candidates to change according to the AED model as explained below Given any gate state y y Yn and any subset P of the set 1 n of gate subscripts we define y to be the vector obtained from y by complementing all the y such that i is in P For example if y 100 and P 1 3 then y 001 We now define a set K of race states and a binary relation p on K We begin with a stable state x y and change the input to X The initial race state of the network is y U y where for any y U y is the set of subscripts of unstable gates in state y i e U y j Y X y y N
22. on of gate races 63 Lemma 6 2 Let ye T and let be next y Then w lt y and woz implies z lt y Proof If y then for any such z we will trivially have y gt z Hence study the cases when J B Note that by the definition of it follows that y implies 4 Therefore there are only four cases to consider 123 4 y bbb b bE ES j bbbb Here b stands for some binary value 0 or 1 and b denotes the complement of b Case 1 y t b and b By the definition of t b implies that Y y b Furthermore by the definition of ternary extension we must also have Y X w b for every w y Since w lt y b gate j is stable in any such state w Consequently gate j remains unchanged in any race sequence beginning in state w Therefore if woz we must have z b By assumption b and y z holds Case 2 y b t and y b If t then Y X y is either 3 or b By 1 Y x t Y X y Thus y as computed by next must have the value or b But we have assumed y b Hence this case is impossible Case 3 y b t and y b We first prove that in any state w y gate j is unstable Since t we know that y Y x t Also by assumption y b Altogether we have Y x t b By 1 we know that x t gt Y X y so b Y x y Furthermore by the definition of ternary extension it follows that Y X w lt Y x y when w lt y He
23. or network N we re evaluate gates 1 and 2 and we get the following values v Y X t x 0 Ja YA 1 2 13 2 Hence we obtain the new state y 030 In Fig 12 a we give the complete TAED analysis of network N y 100 Z 100 t 0 y 0 0 2 000 016 t O y 00 z 000 001 Fig 12 Analysis of N a TAED model b states reachable in stepwise AED model It is interesting to note that the lub of the states reachable after i race units in the stepwise AED model corresponds exactly to the outcome of the TAED method after i steps see Fig 12 a and b In the next section we explore the relationship between the two models 6 A partial characterization of the TAED method In this section we show a partial correspondence between the binary stepwise AED model and the results of the TAED algorithm described above The main result is the following theorem Theorem 6 1 Let x y be a stable total state and let X denote a new input vector Let y denote the results of the TAED method after i 0 steps starting in y y Then y 2lub 2Z where Z is the set of states reachable in i steps in the stepwise AED model Before proving the theorem we will establish Lemma 6 2 below The following observation is useful in proving the lemma If y is the input to next then 1 gt p Hence by the monotonicity property of the ternary extension P gt Y5 y 1 Optimistic ternary simulati
24. ote that the input will be held constant at the value x for the rest of the analysis thus the dependency of U on x is suppressed The set K and the relation p are now defined inductively as follows Basis y U y e K Induction Step Given y Vye K 1 if V then y V p y Vy 2 if VQ then for each nonempty subset P of V compute Wp V P n U y a if Wp 9 then y U y e K and y V p y U y P b if Wp 9 then y W e K and y V p y Wp Nothing else is in K or p The set K defined above represents the set of all possible race states reachable from the initial race state y U y and the relation p describes the immediate successor race states In particular given y V if V then y is a stable state and this is indicated by stating that y is the only successor of itself Next if V 9 it turns out by this definition that V will always represent a subset of the gates which are unstable in y The model now assumes according to the multiple winner principle that the gates in any nonempty subset P of V may all change and Optimistic ternary simulation of gate races 53 so state y may be reached The gates in P are considered to have completed the race they were involved in As for the gates in V P one of two things can happen Either a gate y remains unstable in y i e ie Wp or the instability of y is removed when y changes to y In the latter case i Wp Now if
25. pose that all the gates have approximately the same delay e Then any race unit lasts for approximately 6 units of time Thus a transition between two distinct states related by R represents roughly 6 units of time In contrast to this consider the relation p of Fig 6 and the sequence 100 1 2 110 1 010 2 3 where consecutive race states are related by p Here the first transition takes about units of time whereas the second one takes only units of time because gate 1 became unstable in the first state and lagged behind gate 2 by a small amount of time Note that the above intuitive explanation is adequate as long as is much smaller than 5 Note also that the marking introduced in Section 2 has the following meaning a transition is marked iff that transition completes a race unit or it is a self loop on a stable state Formally the relation R is defined on a subset Q of the set K of race states as follows Q y U y U y V there is a marked edge into y V in the graph of p For Ys V 9 V EQ we define y V R j V iff there exists a path from y V to y V in the graph of p such that only the last edge of the path is marked Note in particular that y R y for all the stable states y in Q Optimistic ternary simulation of gate races 55 To illustrate this consider the example of Fig 6 We find Q 100 1 2 010 2 3 000 001 and the read
26. r implies f t f r The underlying idea behind the TAED method formally defined below is to find all the unstable gates in a state y and then determine which of these unstable gates must change in this race unit Consider network N of Fig 11 a started in the stable state x 0 y 11 and with the new input x 1 The first step of the TAED algorithm is to calculate the lub of the present state and the excitation of the gate network In this intermediate state called in the algorithm a gate will have the value 3 if it is unstable In network N both gate 1 and gate 2 are unstable and hence t 43 In order to determine which of the unstable gates must change in the present race unit the excitations of the unstable gates i e the gates for which are re evaluated However this re evaluation is done assuming is the total state of the network If the excitation of an unstable gate j is still binary then indepen dently of changes in the other unstable gates this gate has to change before the present race unit can finish On the other hand if the new excitation of an unstable gate j is then that instability depends on some gates that are also unstable Hence it is possible to change these other unstable gates first and thereby remove the instability of gate j In network N we get Y 1 43 1 Oand Y 1 3 14 3 so the new state we reach is 05 It is easy to see that gate 1 must change in any race unit since
27. the definition of p there cannot be any transient cycles in the graph A cycle is said to be transient if there is a gate that has the same value and is unstable in all the states of the cycle 7 In this case the network may end up in either one of two possible cycles namely the stable states 000 and 001 Thus the initial race is critical because the final outcome depends on the relative delays in the circuit For technical reasons which will become clearer later we mark certain edges by a in the graph of p as follows All edges of the type y y are marked Also every edge y V y U y added to p by rule 2 a i e with Wp is marked No other edges are marked Note that if an edge is introduced because of rule 2 a that same edge cannot be also generated by rule 2 b This follows because y V and yP uniquely determine Wp For example Fig 6 shows all the marked edges for the previous example 3 The stepwise AED modei In this section we introduce a new binary race model very closely related to the AED model of Section 2 This model which will be called the stepwise AED model has the advantage of showing more clearly certain timing information Also the stepwise model will be used later to establish a related ternary model To obtain more timing information from p we now define a new relation R derived from p as described below Intuitively one can interpret this relation R in the following way Sup
28. wise model of this section relation R are related by the following result Assume that the network is started in the stable state x y and the input changes to x Compute p and R starting from this condition Theorem 3 4 For every cycle C in the graph G there exists a cycle II C in the graph Gr Conversely for every cycle Din Gr there exists a cycle C in G such that D II C Furthermore given two corresponding cycles C in G and Cpr in Gr and any variable Yi either y has the same binary value in all the states of C and Cpr or y oscillates assumes the values 0 and 1 in both C and Cr Proof Consider a cycle C in G If the length of the cycle is 1 i e the state is a stable state then the result follows immediately from Proposition 3 2 Hence assume the length of the cycle is 2 By the definition of an initiating state in a cycle and the definition of II C it follows that if y V and 7 V are any two consecutive race states in I C then the path in C from y V to y V will have only the last edge marked Therefore we can conclude that y V R y V This together with Proposition 3 3 shows that 7 C is a cycle in Gr of length 22 Conversely let Dr be a cycle of Gr According to the definition of R for any two consecutive race states y V and j V in Dp there must exist a path in the graph G from y V to jy V with only the last edge marked Hence there must exist in G a cycle C corresponding to
29. x t b Together 64 C J Seger J A Brzozowski the above two facts imply that Y x z b for p 0 k However this implies that j isin U z for p 0 k contradicting the assumption that S Therefore the assumption must have been false and we can conclude that all states z such that woz must have z b Hence y gt z holds Case 4 y t and y b Since it follows that y Y X e and since we assumed j b it follows that Y x t b By 1 we know that X 1 gt Y x y so we can conclude that Y x y b By the definition of ternary extension it follows that Y x w b for any w y Study any state we B w lt y We have two cases i w b Since w b and Y x w b we have that gate j is stable and as in Case 1 above we can conclude that for any state z such that waz we have z b Hence y 2 holds ii w b Since w b and Y x w b we have that gate j is unstable Using similar arguments as in the second part of Case 3 above we can conclude that for any race sequence from the state w gate j must change and thus we have that if woz then z b Hence y z holds We have shown that y z for all possible cases and hence that y z for any state z such that woz where wsyp O We are now in position to prove Theorem 6 1 Proof of Theorem 6 1 We want to show that if yje B then lub z y o z y We will prove this by inductio
Download Pdf Manuals
Related Search