A BOUNDED DELAY SIMULATOR By Robin Morris Reid B.A.(Hons.), York University, 1990 A THESIS S U B M I T T E D IN PARTIAL F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F M A S T E R O F S C I E N C E in THE FACULTY OF GRADUATE STUDIES DEPARTMENT OF COMPUTER SCIENCE We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA 1992 © Robin Morris Reid, 1992 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. (Signature) Department of Computer Science The University of British Columbia Vancouver, Canada Date: June 15, 1992 DE-6 (2/88) Abstract Detecting the presence of timing problems in digital circuits is a difficult mat-ter, but one that can be greatly simplified with the aid of effective analysis tools. Such tools have traditionally lacked the ability to detect the presence of race and hazard conditions. In this thesis we present a simulation tool that is able to detect such problems. In addition, the tool provides two mechanisms for doing so. One approach gives the user the capability of explicitly generating all possible states of the circuit in response to an input change. This type of analysis is extremely time consuming but describes all behaviours possible according to the underlying model. The other approach is far more computationally efficient, dealing mainly with computing the final outcome. Alternatively, this second approach enables the user to analyse a circuit using "symbolic data". However, it is somewhat pes-simistic, giving rise to "false negative" results at times. Together though, the two approaches form a useful workbench for verification of circuit designs. 11 Table of Contents List of Figures v 1 Introduct ion: De lay Network Analys i s 1 1.1 Motivation 1 1.2 Outline of Thesis 4 2 Toward B o u n d e d Delay Analys is 5 2.1 Race Models 6 2.1.1 The General Multiple Winner Race Model 6 2.1.2 The Extended Multiple Winner Race Model 10 2.1.3 Ternary Simulation 13 2.2 Delay Models 16 2.2.1 Discrete Bounded Delay Models 19 2.2.2 Continuous Bounded Delay Models 22 3 Cont inuous B o u n d e d Delay Analys i s 29 3.1 Continuous Binary Bounded Delay Analysis 29 3.1.1 Components 30 3.1.2 Analysis Procedure 33 3.1.3 A Small Example 37 3.2 Ternary Bounded Delay Analysis 40 3.2.1 An Informal Description 41 3.2.2 Analysis Procedure 42 iii 3.2.3 A Small Example 46 3.2.4 Symbolic Simulation 49 4 A Continuous B o u n d e d De lay Network Simulator 58 4.1 Using the Simulator 58 4.2 Analysing Simple Circuits 62 4.3 Symbolic Analysis 66 4.4 A Larger Example 68 5 Conclusions and Future Work 72 5.1 Future Enhancements 74 5.1.1 Usability Features 74 5.1.2 Productivity Features 75 5.2 A Third Model 77 Bibl iography 79 A Interval Ar i thmet i c 81 B Ternary Algebra 83 C Dual-rai l encoding of Ternary functions 86 IV List of Figures 2.1 Example Circuit C\ 7 2.2 GMW transition analysis 7 2.3 A critcal race 8 2.4 A match-dependent oscillation 8 2.5 Example Circuit C2 9 2.6 GMW analysis for circuit C2 9 2.7 Example Circuit C3 10 2.8 GMW analysis for circuit C3 11 2.9 XMW analysis of circuit Cx 12 2.10 Example Circuit C4 14 2.11 Example Circuit C5 16 2.12 Delay Element 17 2.13 Circuit C4 with delay elements inserted 17 2.14 Circuit C4 represented as a network of delay elements and function nodes. 18 2.15 Example Circuit C6 19 2.16 Analysis Trace for Circuit Ce using delays of size 3 20 2.17 Example Circuit Ce with different delay values 20 2.18 Alternate analysis trace of Circuit Ce 21 2.19 Example Circuit C7 21 2.20 Analysis Trace for Circuit CV 22 2.21 Example Circuit C8 24 v 2.22 Two possible BBD transition sequences 24 2.23 Instantaneous vs. Non-Instantaneous Transistions 25 2.24 Two possible XBD transition sequences 28 3.25 Algorithm 0 32 3.26 Example Circuit Cg 37 3.27 Partial BD Analysis Graph for Circuit C9 40 3.28 Complete BD Analysis Graph for Circuit Cg 41 3.29 Delay Network N9 47 3.30 Complete Trace 49 3.31 Dual-rail encoding of ternary values 50 3.32 Ternary to dual-rail representation: (a) Input node; (b) Internal node; (c) Transitions 51 3.33 Dual-rail version of the TBD algorithm: (a) Input node; (b) Internal node. 52 3.34 Delay Circuit for Delay Element with bounds [d, D) 53 3.35 Example: Delay Circuit for Delay Element with bounds [1,3). Initially stable with ternary value of 0 54 3.36 Example: Delay Circuit for Delay Element with bounds [1,3). Configura-tion following the arrival of a ternary 1 on the input 55 3.37 Example: Delay Circuit for Delay Element with bounds [1,3). Demon-strating the intertial property of the delay circuit 56 3.38 Example: Delay Circuit for Delay Element with bounds [1,3). Configura-tion after two time units 56 3.39 Example: Delay Circuit for Delay Element with bounds [1,3). Stable configuration after six time units 57 4.40 Example Circuit C10 63 vi 4.41 Example Circuit C n 66 4.42 Example Circuit C12 69 4.43 Analysis traces run in (a) tbd mode, and (b) bbd mode 71 B.44 C relation on T 83 B.45 Ternary AND, OR, and NOT 84 C.46 Dual-rail encoding of ternary values 86 C.47 Encoded versions of ternary AND, OR, and NOT 87 vn Acknowledgements I would like to acknowledge the help and support provided by my supervisor Carl-Johan Seger. In particular I would like to thank Carl for being available during trying times as he anxiously awaited the arrival of his first child. I would also like to extend thanks to Jeff Joyce for serving as second reader, and to the many graduate students and faculty of the UBC Computer Science Department, who have helped and encouraged me throughout this process. In particular I would like to thank Grace Wolkosky for always being available to assist with administrative matters. V l l l Chapter 1 Introduct ion: De lay Network Analysis Digital circuit can be classified as either combinational or sequential. A combinational circuit is one whose output is completely determined by the current values of its inputs. A sequential circuit, on the other hand, may depend on previous input values. Sequential circuits may be categorized as being synchronous or asynchronous, depending on whether their behaviour is governed by a clock. In synchronous circuits, a clock signal is present to govern the moment at which an output signal from one circuit module may appear as input to another. In asynchronous circuits no clock signal is present to govern this action, and new output signals arrive as input signals to other modules as soon as they become ready. The presence of a clock signal is intuitively appealing, as without it comes the impression of chaos. However there are some real advantages that can be gained by its removal. 1.1 Mot iva t ion The clock signal in a sequential circuit may be thought of as a door that periodically opens and closes to allow signals to pass through. By adjusting the frequency with which the door is opened, one can ensure that all desired signals have arrived before allowing them to pass through. This ability is of great help to designers of synchronous circuits as it simplifies timing issues tremendously. However there is a potential drawback associated with having a clock. To ensure that all desired signals have arrived, the frequency of the clock must be set to accomodate the latest arrival. This means that the clock must cater 1 Chapter 1. Introduction: Delay Network Analysis 2 to the "worst case" speed of the circuit. By designing a circuit without a clock, one can hope to realize "average case" performance. There are several other reasons for considering asynchronous designs over synchronous ones. As we become able to pack more and more onto a single chip, it becomes increas-ingly difficult to ensure a clock pulse will arrive at different parts of the circuit at the same time. This is known as "the clock skew problem". The larger the circuit, the more difficult it becomes to distribute a single clock signal. As we move toward distributed computing environments we are forced to abandon the notion of a single clock in favour of an environment in which multiple clocks of varying frequencies exist, and where com-munication is carried out asynchronously by means of "handshaking" protocols. The need to develop suitable asynchronous design methodologies and analysis techniques is becoming unavoidable in light of technological advancements. Despite these arguments, there has not been a lot of attention paid to the develop-ment of asynchronous technologies. This is largely due to the difficulties introduced by the absence of a governing clock. Without a clock, a whole host of timing problems come into play, highlighting the virtues of synchronous design. Designing asynchronous circuits can be greatly simplified with the aid of reliable analysis tools. However, to be able to analyse the behaviour of an asynchronous circuit one must first develop a model that can "reasonably" represent and describe the behaviour of the circuit. What is reasonable depends on what is to be accomplished. The shear nature of circuit components prevents their precise modelling, as one can hardly expect to account for all characteristics. There-fore one introduces a model in hope that it captures as much of the typical behaviour of a circuit as possible. Quite often this results in the development of "pessimistic" models, so we can assume that if a circuit works according to the model it will also work in reality. In devising such a model, an important consideration is its intended use. When analysing very large circuits, one is often required to make sacrifices with respect to the Chapter 1. Introduction: Delay Network Analysis 3 ideal in favour of a model that lends itself to computation. This is true of many of the large simulators of today. The MOSSIM [2] and COSMOS [1] simulators are intended for large scale simulation and therefore are based on relatively simple models where each component in the circuit is assumed to have a fixed unit delay. On the other hand, the SPICE simulator is based on a model that at tempts to accurately model timing and electrical behaviour, involving large computational requirements. Consequently it is restricted to much smaller circuits. In addition to intended use, there is the question of the technology being modelled. Switch level simulation attempts to model the behaviour of networks of transistors, while gate level simulation is concerned with modeling networks of gates. Gate level simulation is typically more efficient than switch level, and provides the potential for modelling entire circuits. However, switch level simulation allows one to create new types of circuits without the notion of gates and can more easily take advantage of any features of the transistor technology being used. Such models are ultimately used as the basis for analysis procedures used to simulate circuit behaviour. When we speak of an analysis procedure or method we are referring to the way in which the results described by the model are computed. Ideally an analysis procedure should produce results "consistent" with that of the underlying model. This is not always possible, as we will see, and quite often methods are developed to generate results that are an approximation or summary of these behaviours. The degree to which the results of the analysis procedure match those of the underlying model is often a major factor in determining its usefulness. Factors that affect the model also affect the analysis method. This includes computational and space complexity requirements. These are also very important and deciding factors when selecting an analysis method. An analysis method that accurately computes the behaviours of a circuit with respect to the underlying model is of little use if it requires time and/or space beyond what is reasonable. Chapter 1. Introduction: Delay Network Analysis 4 In this thesis we will present a simulation tool that is intended to serve as a workbench for analysing small to medium sized circuits. It incorporates two methods for analysing networks in which delays are associated with gates. The ability of each method to detect the presence of "race" and "hazard" conditions make them particularly well suited for use on asynchronous circuits. 1.2 Outl ine of Thes is We begin in Chapter 2 by looking at various analysis models in which very little is known about the nature of the delays. We discover that very few circuit behaviours can be realized with such little knowledge and proceed to look at models in which more knowledge is assumed. This takes us to models in which the delay sizes are described using intervals. We characterize such models according to the way in which the delay sizes are allowed to vary within the intervals. Finally, we conclude the chapter by describing two models that capture the behaviours possible under these added assumptions. In Chapter 3 we introduce two analysis methods that capture the same behaviour as the models described at the end of Chapter 2. These methods are implemented in our simulator and therefore are described in this chapter in some detail. After demonstrating the methods using small examples, Chapter 4 describes the simulator in which they are employed. We start by describing some of the features of the simulator to give the reader some notion of how it is used. We then go on to consider how it might be used to analyse several small circuits. Finally, in Chapter 4, we take a look at a larger example and suggest a way in which the two components of the simulator may be used together to tackle bigger analysis problems. In Chapter 5 we conclude the discussion by summarizing what was covered and by looking at future possibilities for the simulator. Chapter 2 Toward B o u n d e d Delay Analysis In at tempting to accurately model the behaviour of a circuit one must be concerned with the location and nature of the components that delay electrical signals. For example, is it enough to associate a delay with each gate in the circuit or must delays be extended to wires as well? And what about the values of the delays themselves? Are they to be nominal and fixed, or must one allow for some degree of variance? Another, less obvious, concern has to do with the behavioural nature of a delay, how delays respond to short signal pulses or bursts. These are some of the questions that must be addressed when forming a delay model. For a more comprehensive coverage of delay models we refer the reader to [6]. To simplify the discussion we will associate delays with gates only1 (unless otherwise specified), and will make no assumptions about the sizes of the delays, allowing them to be arbitrary but finite. In this way we can steer attention away from the structural aspects of the circuit and focus on its behavioural aspects. Later we will return to consider some of the issues associated specifically with delays. Before continuing we will need the following definitions. Let B = {0,1}, and let T = { 0 , 1 , ^ } . Given a circuit, let x = (x\,... ,xm) m > 0 be a vector of m input values and y = ( y i , . . . , yn) n > 0 be a vector of n delay values. We associate variable X{ with input i, and variable ?/,- with delay i. Variables X{ and ?/; can take on values from B. The excitation function Yi(x,y) of delay vertex i is a Boolean 1Wire delays can be easily added to a gate-delay model by simply introducing identity-function "gates" in every wire. 5 Chapter 2. Toward Bounded Delay Analysis 6 function from Bd* —• B, where d{ denotes the in-degree of delay i. The ordered pair (x, y) denotes the total state of the circuit, and for notational convenience we write x • y. We say a delay i is unstable when its value "wants to change", or more formally, when Yi(x,y) =4 y,-. Otherwise the delay is stable. We may omit the (x,y) from Yi(x,y) when the context allows. We denote an unstable delay value by underlining it, as in y,-. Finally, we use the term total stable state, or just stable state, to refer to a total state in which all delays are stable. 2.1 Race Mode l s When analysing the behaviour of a circuit, one is largely concerned with its reaction to input changes. Given a circuit in a stable state x-y, what possible successor states can be reached as the result of an input change (i.e., a change in vector x)1 The answer to this question depends on the model used to predict successor states. Such models are known as race models. This term comes from a situation that can arise when two or more delays become unstable as a result of an input change. In such a situation, the successor state that results may depend on the outcome of a "race" between these unstable delays. The winner of such a race is the delay, or delays, that change value first. In the subsections that follow we will consider two race models, and then go on to consider an alternative analysis method that serves not to predict successor states, but instead to summarize the behaviour of a circuit. 2.1.1 T h e General Mult ip le Winner Race M o d e l The general multiple winner (GMW) race model is due to Brzozowski and Yoeli [10] and describes an approach that allows any nonempty subset of the unstable delay variables to change value at the same time ("multiple winners"). In addition, the model does not Chapter 2. Toward Bounded Delay Analysis 7 attempt to make any assumptions about the sizes of the delays except that they are finite, making it "general". Figure 2.1: Example Circuit C\. To illustrate this approach we will consider circuit C\ of Figure 2.1. The excitation functions are as follows: Y\ = ~>(xi + 2/2), Y2 = -i(x2 + 2/1) Assume the circuit is initially in the total stable state x • y = 11 • 00 when the input changes from 11 to 00. To describe the behaviour of the circuit we use a state transition graph as shown in Figure 2.2. Each node in this graph represents a possible state of the circuit, and each edge represents a possible state transition according to the GMW race model. Stable states are indicated by self loops. 00-00 o 00-10 00-01 O 00-11 Figure 2.2: GMW transition analysis. Analysis using this model reveals the existence of potential timing problems in the circuit. Among them is the existence of a critical race condition. A critical race condition Chapter 2. Toward Bounded Delay Analysis 8 exists when in any state more than one delay variable is unstable and where the outcome of the race, which depends on the relative sizes of the delays, can produce different final results. Figure 2.3, which is an extract of the transition graph of Figure 2.2, illustrates this condition. If the delay at gate 2 is greater than that of gate 1 then circuit will end up in stable state 00 • 10. If the relationship were reversed then stable state 00 • 01 would result. Note that in both cases, the new value reached by the gate that won the race prevented the opposing gate from changing, leaving both gates stable. In each case the losing gate was not unstable for a long enough period for the change to occur (this is what is known as an inertial property and will be discussed in more detail later). 00-00 - , 0 0 - 1 0 0 0 - 0 1 ^ 0 o Figure 2.3: A critcal race. 00 -Q0 00-11 Figure 2.4: A match-dependent oscillation. Another potential timing problem exhibited by the transition graph is shown in Fig-ure 2.4. Here we have a cycle, which presents the possibility for oscillation. If oscillation were to occur then it could do so for an indefinite amount of time. Of course for this to Chapter 2. Toward Bounded Delay Analysis 9 occur the delays of the unstable gates would have to be identical, which would be virtu-ally impossible in reality. Therefore there is essentially no chance that this condition can persist for more than a few cycles. Regardless, it introduces a degree of unpredictability into the circuit. This type of oscillation is known as match-dependent oscillation. Other varieties also exist. The interested reader is referred to [6] for more on race and oscillation conditions. Figure 2.5: Example Circuit C2. x-yjy2 Q-00 "I 1-00 0 Figure 2.6: GMW analysis for circuit Ci-The behaviour predicted by the GMW race model was based on the assumption that delays were associated with the gates in the circuit only. If we change this assumption to allow for the existence of other delays (i.e., delays associated with the wires) then GMW analysis may predict a different circuit behaviour. The behaviour predicted by GMW analysis of circuit Ci in Figure 2.5 is shown in Figure 2.6. If we associate a delay with one of the wires of circuit C2, as shown in Figure 2.7, then perform GMW analysis on Chapter 2. Toward Bounded Delay Analysis 10 it, we see that different results are predicted as shown in Figure 2.8. By introducing the wire delay it became possible for the input signals to the XOR gate to arrive at different times, allowing the XOR gate to generate a 1 on its output. The result being that it is now possible for the circuit to trap a 1 on the output of the OR gate and stabilize in the state 1 • 101. This poses the problem of having to account for delay sources other than those introduced by the gates. Next we look at a race model similar to GMW that contains a mechanism for handling such a problem. Figure 2.7: Example Circuit C3. 2.1.2 T h e E x t e n d e d Mult ip le Winner Race Mode l The approach taken by the extended multiple winner (XMW) race model is similar to that of the GMW race model except that signals are allowed to go through an intermediate value X. This value is intended to represent a state of uncertainty, where the value of the delay variable is as yet unknown. As with the GMW analysis we will be using a transition graph to illustrate this ap-proach. However, since delay variables can now assume values over T we must reconsider what it means for an unstable delay variable to change. In general, an unstable delay variable changes by assuming the value of its corresponding excitation function. In the GMW race model this was simply a matter of complementing the unstable delay vari-able. In XMW analysis we also allow unstable delay variables to assume an unknown Chapter 2. Toward Bounded Delay Analysis 11 0-000 1 1 0 0 1 1 0 1 0 0 Figure 2.8: GMW analysis for circuit C3. value, represented by X. Since we are now dealing with values over T some knowledge of Ternary Algebra will be helpful2. For convenience we will modify the nodes of the transition graph slightly to provide the current value of the delay variable, subscripted by its ternary excitation value, if the delay variable is unstable. Consider the behaviour predicted by the XMW race model for circuit C\ of Figure 2.1. The analysis assumes that the circuit starts in stable state 00-10 when the input changes to 10. This produces the state 10 • lo0 indicating that NOR gate 1 is unstable with ternary excitation 0. We now proceed by allowing the unstable delay variable to change to 0 or X, producing successor states 00i and .XoOx respectively (we have omitted the input values for clarity). Continuing in this way, the complete graph is generated as shown in Figure 2.9. In this example we see that the circuit will eventually stabilize in state 1 0 - 0 1 , in 2Refer to Appendix B for a discussion on ternary algebra. Chapter 2. Toward Bounded Delay Analysis 12 100 oo; 0 1 a x0ox ox, X 0 X Figure 2.9: XMW analysis of circuit C\. which all values are binary. Had there been a stable state in which one of the delay variables had the value X, then this would have indicated the presence of a potential timing problem similar to the critical race condition described for GMW. By allowing a delay variable to take on the value X, analysis using the XMW race model can subsume any delays in the circuit not accounted for by gates. In this way it is a "stronger" race model than GMW. The GMW and the XMW race models are both very rigorous. In the case of GMW race analysis, this means potentially generating 2™ states for a circuits with n gates. For XMW one might have to generate 3 n states. This exponential complexity makes either model an unlikely candidate for use on anything but the most trivial of circuits. Fortunately though, in many applications we are only interested in the final outcome and do not require knowledge of the intermediate states. This observation leads us to consider an alternative analysis method. Chapter 2. Toward Bounded Delay Analysis 13 2.1.3 Ternary Simulat ion Ternary simulation was developed by Eichelberger[12] as a method for detecting the presence of undesirable circuit behaviour, such as race conditions and hazards3. Unlike what we have seen so far, ternary simulation does not at tempt to predict all possible states the circuit may reach in response to an input change. Instead, it summarizes this behaviour in terms of the uncertainty introduced as a result of an input change. The method captures the notion of uncertainty by allowing delay variables to take on a third value, X. In this way it resembles the XMW race model. This however is where the similarity ends. Ternary simulation is a two step process in which the first step computes the amount of uncertainty introduced into the circuit as a result of changing the input from its initial value to X. The second step then, computes the amount of uncertainty removed from the circuit when the input changes from X to a binary value. We express the method informally as follows: 1. Change the value of the inputs that are going to change to X. Compute the amount of uncertainty introduced into the circuit in response to this change. 2. Change those inputs with value X to their final binary values. Compute the amount of uncertainty removed from the circuit in response to this change. Computing the amount of uncertainty is simply a matter of computing the ternary excitation values for each delay in the circuit until the circuit stabilizes. This can be best seen by way of an example. Consider circuit C± of Figure 2.10. 3The following definition of hazard is taken from [13]. A circuit is said to contain a hazard if there exists some possible combination of values of stray delays which will produce a spurious pulse or cause the circuit to enter an incorrect stable state, for some input change. Chapter 2. Toward Bounded Delay Analysis 14 V ~ ^ v i v ,^ ) r^ Z-^ r^o3'2 L^ ° \ ) " j Figure 2.10: Example Circuit C4. The circuit is initially in stable state 0-011 when new input 1 arrives. In response, ternary simulation requires that we first change the input value to X, giving us X • Oil. This X value now feeds the OR gate and the NAND gate making both unstable. We then stabilize these gates by assigning them the values computed by their respective excitation functions, giving us state X • XIX. The X present on the input to the inverter will make it unstable, requiring that we change its value to X, thus stabilizing the circuit in state X • XXX. A trace of this activity is shown below: Step 1: 0-011 — • X • 011 —> X • XIX — • X • XXX. The second step begins by changing the input value from X to 1, giving us 1 • XXX. In response to this change the OR gate becomes unstable requiring that we change it accordingly, and we reach state 1 • IXX. Subsequently the inverter becomes unstable and changes, producing state 1 • \QX. Finally, the NAND gate is affected and changes, giving us the stable state 1 • 101. The states generated by step 2 are shown below. Step 2: X • XXX —> 1 • XXX —> 1 • \XX — • 1 • \QX —> 1 • 101. Ternary simulation predicts that this circuit will eventually reach a single stable state. The presence of an X value after step 2 would have indicated that a degree of uncertainty remained, and thus the potential for timing problems. Chapter 2. Toward Bounded Delay Analysis 15 As in the XMW race model, by introducing the value X, ternary simulation can accounted for delays other than those produced by gates. In fact, it has been shown in [6] that with the addition of input delays, results predicted using the XMW race model are consistent with those of ternary simulation4. More importantly, [6] shows that the results of ternary simulation are also consistent with GMW analysis in which delays are associated with gates and wires. Ternary simulation requires only n2 t ime to compute its results (steps 1 and 2 require at most n iterations, evaluating at most n excitation functions for each iteration). Com-pare this to the exponential time required for GMW and XMW analysis, and ternary simulation becomes very desirable. In summary, we have seen examples of three different methods for analysing circuits. The GMW race model predicted all possible successor states but was sensitive to the presence of additional delays, such as those present in wires. Similar to the GMW model was the XMW race model, which allowed us to relax that requirement so that we need only associate delays with gates. Ternary simulation provided a more viable means of analysis, summarizing the results predicted by XMW and GMW analyses and thereby greatly reducing the cost. However all three are guilty of generating what we will call pessimistic results. This can be best seen by considering circuit C5 of Figure 2.11 in which we have six inverters, connected in series, feeding one input of the AND gate, and only one inverter feeding the other input. In response to the arrival of a 1 on the input, GMW, XMW, and ternary simulation would all provide for the possibility of a 1 on the output of the AND gate. Thus, suggesting that a the signal may make its way through all six inverters on the lower path before getting by the single inverter on the upper path. This would suggest that the output of the circuit may be uncertain. In reality though, it is extremely unlikely that such an event could occur. As a result we could conclude that 4XMW assumes input transitions are instantaneous, ternary simulation does not. Chapter 2. Toward Bounded Delay Analysis 16 this circuit does indeed produce a consistent output of 0. » ' — r ^ i r ^ ~ o j \ _ i j \ n [ \ ~ i | \ ~ o Figure 2.11: Example Circuit C5. In the next section we will take a closer look at delays to see how the assumptions made so far affect the usefulness of the analysis method. 2.2 De lay M o d e l s The analysis methods of the previous section made the assumption that the value of each delay could be arbitrary but finite. In addition, we have casually mentioned the existence of inertial behaviour among delays. By associating such properties with the delays of a circuit we have defined a delay model. So far the assumptions have been kept to a minimum in an at tempt to keep things as simple as possible. Clearly, the ability to design any circuit with the property that its behaviour is independent of its delay values is very desirable. Unfortunately it has been shown in [5] that such a model is too simple and that very few circuit behaviours can be realized by circuits in which delays are assumed to be arbitrary. As a result we are forced to strengthen this assumption and say more about the delays in the circuit. Before continuing we introduce the following concepts. Figure 2.12 represents what we will call a delay element. It is essentially a "black box" with a single input and a single output. Associated with a delay element is a delay value, S, which represents an amount of time through which a signal must pass before appearing Chapter 2. Toward Bounded Delay Analysis 17 in y Figure 2.12: Delay Element. on the output. In addition, we associate a variable y with each delay element to record the value on the output. When we speak of the value of a delay element, we are in fact referring to the value of this variable. The delay element then, can be used to simplify our discussion by providing an alternate way of viewing a circuit. Instead, we may view a circuit as a network of delay elements connected in series with completely delay free components, as shown in Figure 2.13. Alternately, we can dispose of gates altogether to provide the completely general notion of a network of delay elements whose inputs are governed by delay free function nodes as shown in Figure 2.14. We have introduced these concepts as it is sometimes convenient to think in terms of networks of delay elements rather than circuits of gates and wires. In future we will use these terms interchangeably. Figure 2.13: Circuit C4 with delay elements inserted. In an ideal delay model one might assume that delay elements behave in a pure man-ner. A pure delay can be thought of as something that simply replicates its input, making it available as output some 8 time units later. But this is an unrealistic assumption since Chapter 2. Toward Bounded Delay Analysis 18 Figure 2.14: Circuit C4 represented as a network of delay elements and function nodes. physical circuit delays tend to suppress short pulses. In any circuit there is always some amount of resistance and capacitance associated with a wire which serves to filter out short pulses. The fixed inertial delay model at tempts to address this shortcoming by assuming delays are fixed at some value, but inertial in nature. An inertial delay differs from a pure delay in that it will make a replica of its input available as output only if the input has been present for at least 8 time units, otherwise the output value will remain unchanged. This model is not much better though, as it assumes that at any time one can always know the exact delay -value of any delay element. In a physical circuit one can, at best, come up with some estimate of the delay of any component. Beyond that, com-ponent delays are subject to other factors such as temperature and age. Consequently one must allow delay values to vary in time between some upper and lower bound. Next we characterize a delay element according to the bounded inertial delay model. A delay element in the bounded inertial delay model has delay value d < 8 < D, where d and D are integer values denoting some basic unit of time. The input/output behaviour of the delay element obeys the following two rules: 1. If delay variable t/; changes from a to a, then a must have been present on the input of delay element i for at least d t ime units. 2. If new value a arrives on the input of delay element i at t ime t and remains through time D + t, then at time D + t we must have y^ — a. Chapter 2. Toward Bounded Delay Analysis 19 These two rules essentially state that a new signal arriving on the input of a delay element must be present for at least d t ime units before the signal will appear on the output, and after D time units is guaranteed to appear on the output. In the following subsection we will add some assumptions to the bounded inertial delay model and look at how these assumptions affect the network analysis. 2.2.1 Discre te B o u n d e d De lay M o d e l s The bounded inertial delay model allows for delay values to vary between some upper and lower integer bounds. The simplest approach to the analysis of networks of such delay elements is to assume that delays can only assume discrete values, giving rise to what we will call the Discrete Bounded Inertial Delay model, or simply the Discrete Bounded Delay model. Network analysis using the Discrete Bounded Delay model can take several forms. A very simple approach that appears to have some intuitive appeal is one that we will call the "slow mode" approach. t>~± [1,3] Figure 2.15: Example Circuit C&. The slow mode approach to analysis associates only the maximum bound with each delay in the network in an at tempt to arrive at an upper bound on the time the network will take to fully react to a transition. As an example consider circuit C& of Figure 2.15 Chapter 2. Toward Bounded Delay Analysis 20 where the circuit starts in state 0 • 1001 and at time 0 the input changes to 1. Slow mode analysis of this network yields the trace shown in Figure 2.16. Hence, slow mode analysis predicts that 3 time units is an upper bound on the time the network will take to stabilize in response to this transition. ie: 0: 3: x-y 1-1001 J 10101 o Figure 2.16: Analysis Trace for Circuit C% using delays of size 3. \ > ^ Figure 2.17: Example Circuit C6 with different delay values. Unfortunately this approach is too simplistic. By reducing two of the delays, as shown in Figure 2.17, the trace becomes as shown in Figure 2.18, demonstrating that slow mode cannot be relied upon to predict an upper bound time. One might then consider loosening this restriction to allow delays to assume all integer values between the upper and lower bound. Unfortunately this is still not enough to account for all possible behaviours in a network. Consider circuit CV of Figure 2.19. We Chapter 2. Toward Bounded Delay Analysis 21 time 0 1 2 3 4 5 x-y 1-1001 J 1-1101 1-1101 1-0111 1-0111 1-0101 o Figure 2.18: Alternate analysis trace of Circuit CQ. consider whether it is possible to "trap" a 1 on the output of the OR gate if the circuit begins in state 0 • 11100000 and the input changes to 1. [1,2] [1,1] Figure 2.19: Example Circuit C7. For a 1 to be trapped by the OR gate, it must be present on the output of the AND gate for at least one time unit. This means that 2/4, j/5, and y& must assume, respectively, values 0, 1, 0 at the same time for a duration of at least one time unit. This cannot happen in this circuit if we allow the delays of the three inverters to take on only discrete integer values. For y5 to change to 1 it must have as inputs a 1 and a 0 for a duration of Chapter 2. Toward Bounded Delay Analysis 22 one time unit, which means that delays for inverters 1 and 3 must be 1 and 2 respectively (or vice-versa due to symmetry). For y$ and y& to retain a 0 value during this time they must be unstable for time less than their lower bounds (one time unit). This can only be achieved by assigning a delay value 1 < 6 < 2 to inverter 2. The trace with delay values 1, 1.5, and 2 assigned to inverters 1, 2, and 3 respectively is given in Figure 2.20. time: x • y 0: 1-11100000 J 1: 1-0JI00000 1.5: 1-00100000 2: 1-00001000 3: 1-00000010 4: 1-00000001 o Figure 2.20: Analysis Trace for Circuit CV. In light of this one might think a finer resolution would help. However, in [7] it is shown that one can always come up with an example in which an even finer resolution is required. A consequence of this is that a discrete bounded delay model can never be as accurate as a continuous one. To achieve an accurate bounded delay analysis we must treat t ime as a continuous quantity by allowing delay values to assume any value between their respective bounds, thus characterizing the Continuous Bounded Delay model. 2.2.2 Continuous B o u n d e d Delay Mode l s In this section we look at two Continuous Bounded Delay (CBD) models. The first is a model in which delays are of the bounded inertial type and whose delay variables must assume binary values. We then go on to look at a slightly different model in which delay Chapter 2. Toward Bounded Delay Analysis 23 variables may assume values over T . The Binary B o u n d e d Delay M ode l The Binary Bounded Delay (BBD) model requires that a delay be of the bounded inertial variety, and that its delay variable take on values in B. Being a continuous model, the BBD model allows delay values to vary anywhere between their upper and lower delay bounds. In this way, for any delay element in the network, there are an infinite number of possible delay values it can assume. To account for the behaviours possible in a network of such delay elements, the corresponding race model, the BBD race model, must possess a single notion of time. We can then use the delay bounds of each delay element as a measure against the time present on this "global clock". An unstable delay element then, may change value only if the time on the clock falls somewhere between its delay bounds. In this way delay bounds can be thought of as time markers, bounding regions in time where transitions may occur. The race model must ensure that unstable delay elements change value only within the region of t ime bounded by its time markers. In response to such a change, the time markers would have to be adjusted accordingly. There are two cases that have to be considered. The first case involves shifting the time markers ahead to reflect those delay elements that have become newly unstable. A shift ahead would simply involve adding the current t ime to the delay bounds. The second case involves removing time markers altogether. This would be required for delay elements that became stable as a result of the previous transition. One can imagine then, how calculating successive states involves a process of enu-merating all non-empty subsets of unstable delay elements, and for each of these subsets, adjusting markers as outlined above. For example, consider circuit Cs of Figure 2.21 in stable state 0 - 0 1 1 . If at t ime 0 the input changes to 1, then two possible transition Chapter 2. Toward Bounded Delay Analysis 24 Figure 2.21: Example Circuit C8. sequences predicted by the BBD race model would be as shown in Figure 2.22. Here we represent a node in the transition graph as a triple consisting of the time, followed by the state of the network, followed by the time markers. Note that time is forever increasing and that this is reflected in the time markers. ( t = 0, 1-flU, (-, [1,3). -, 12,4)) y <%= 1.755, 1- 111, (-, -, [2.755,3.755), [2,4))N I <^t= 3.745, 1-101, (-,-,-,-)]> a ^ t = 2.3, 1-U0, (-,-,[3.3,4.3),-)^ J / t = 3.65, 1-100, (-, -, -, [5.65,7.65)) \ I ^t=5.97, 1-101, (- , - , - , -)^ 0 (a) (b) Figure 2.22: Two possible BBD transition sequences. In [7] it is shown that this race model captures exactly the behaviour of a delay element network in which delays conform to the BBD model. However, since time is a Chapter 2. Toward Bounded Delay Analysis 25 continuous quantity there can be an infinite number of starting states and an infinite number of successor states out of any unstable state. Therefore this is not a very useful method for analysis. In Chapter 3.1 we introduce a method that is able to efficiently capture this same behaviour by forming equivalence classes of these states. The E x t e n d e d B o u n d e d Delay M o d e l We now turn to a delay model similar to the Bounded Inertial Delay model but with one additional assumption. The delay models we have looked at so far have all assumed that when a delay element changes value, it does so instantaneously. In reality this is not so. There is always some region between the voltage that represents a 0 and the voltage that represents a 1 where the value of the delay element will be unknown. This is illustrated in Figure 2.23. The Extended Inertial Delay (XID) model at tempts to capture this fact by representing this region with the value X and insisting that transitions take place through it. 0 : J\ v_ — * \ x \ — _ru~ —Hxh— v _ Figure 2.23: Instantaneous vs. Non-Instantaneous Transistions The input /output behaviour of a delay element in the XID model obeys the following rules: 1. If delay variable y,- changes from binary value a to X, then a ^ a must have been present on the input of delay element i for t ime d < t < D. Chapter 2. Toward Bounded Delay Analysis 26 2. If delay variable yt- changes from X to binary value a, then a must have been present on the input of delay element i for time d < t < D. The first rule essentially states that a change in a delay element from a binary value to X can occur anywhere from its lower bound time to some time before its upper bound time. The second rule ensures that X to binary changes occur within the delay bounds with enough time to ensure that a binary to X transition can occur beforehand (t is strictly greater than d). The Extended Bounded Delay (XBD) model requires that a delay be of the extended inertial variety, and that its delay variable take on values in T. Furthermore, it is a continuous model and therefore allows delay values to vary anywhere between their upper and lower delay bounds. The XBD race model a t tempts to account for the behaviour of a network of delay elements that conform to the XBD model. It does so in a similar manner to that described for the BBD race model except that it must maintain two sets of t ime markers for each delay element. One set is required to keep track of the range of times in which a binary to X transition can occur, and the other to keep track of the times in which an X to binary transition can occur. Using circuit Cg, and starting once again in stable state 0-011, we see two possible XBD transition sequences in Figure 2.24. A node in each transition sequence is as before, except that we have changed con-ventions slightly by representing a network state as a vector of delay element values subscripted by the value present on there respective inputs. Also, for each delay element we now have two pairs of time markers. The first pair is for the binary to X transitions and keeps track of the range of times in which an unstable delay element may change to X. The second pair of markers is for the X to binary transitions. Unlike the first pair of markers, these markers are shifted ahead every time a new binary input value arrives. In [7] it is shown that this race model captures exactly the behaviour of a delay Chapter 2. Toward Bounded Delay Analysis 27 element network in which delays conform to the XBD model. Once again though, we one can see how treating time as a continuous quantity can yield an infinite number of these transition sequences, making it very undesirable as an analysis method. In Chapter 3.2 we will show an efficient method that is able to capture the same results predicted by the XBD model. Chapter 2. Toward Bounded Delay Analysis 28 O = o,(voii, |[;;|;;;;;)> 6 = 1 . 7 1 , XrOxllx, (-.12.71,4.71),-, [3.71,5.71)) \ \ X X X ([1,2),-,-,-) / I 6 = 1.95, 1-0,1 lx , (". [2-71,4.71), -, [3.71,5.71)) \ \ (-, [2.95,4.95), -, -) / I / t = 3, 1-X,1X1X,(-,-, [4,5), [3.71,5.71)) \ N (-, [2.95,4.95), -, -) / I (-, -, -, -) (-,-,[5.2,6.2),-) I I A = 9.1, i-ioi,J;;"'"}^> 0 < t - 4 . 2 , l - l X o X , ( - : - . - | > < t = 5 . 5 3 , i - i o x 1 , ( : : : ; : : ; ) ^ 9 _ 5 3 ) ) > 6 = 1 - 4 , X.-Oxllx, (-,[2.4,4.4),-,[3.4,5.4)) \ / t - 1 5 1-011 <"• [2-4,4.4), -, [3.4,5.4)) \ V " ° ' 1 U l U ° ' (-, [2.5,4.5), -, [3.5,5.5)) / I <f _ a c i . Y i Y (-,-,[4.5,5.5),-) \ t - 3.5, 1 X,lxAo, ^ [25A5X _? [3StSS)) / 6=5, MX0X, (.;.; ^ . ) > J < . = 6 . i 2 , i . iox,.<;•;•;• ; > J 2 i l o a 2 ) ) > <..9.77. i-ioi, J?;;;;;>> 0 (a) (b) F igure 2.24: Two possible X B D t rans i t ion sequences . Chapter 3 Continuous B o u n d e d Delay Analys is As discussed in the previous chapter the Continuous Bounded Delay (CBD) model is the only model that can truly account for the behaviours possible in a network assuming inertial bounded delays. In this chapter we will look at two analysis methods based on the CBD model. The first method is based on the work of David Dill [11] and Harry Lewis [14] and describes a procedure for analysing delay networks where delays elements may assume only binary values. This analysis method is to be known as continuous binary bounded delay analysis. The second analysis method we will look at is also based on the CBD model and is due to Carl-Johan Seger [16]. This method not only allows the delay elements of the network to take on binary values but also allows them to assume a third value, denoted X, to represent the instant when the value of the delay element is uncertain due to an impending change. This analysis method is to be known as ternary bounded delay analysis. 3.1 Cont inuous Binary Bounded De lay Analys is We begin the discussion of the Dill/Lewis method by introducing the components of the associated algorithm and at tempt to provide the intuition behind them. 29 Chapter 3. Continuous Bounded Delay Analysis 30 3.1.1 C o m p o n e n t s Timers In order to determine the set of possible transitions (or states) of a network of bounded delay elements it is necessary to record some information about the previous excitation history of each of the delay elements. This is required to ensure consistency between unstable delay elements. That is, if two delay elements have been unstable for some period of t ime and their delay bounds dictate that one must change before the other then we must have a way of determining how long each has been unstable to ensure that the changes take place in the proper order. In the Dill/Lewis approach this is done by associating with each delay element a "timer" or "alarm clock" to record the amount of time remaining1 before an unstable delay element must change. With these timers it is then possible to maintain a set of relationships between the different delay elements. In particular we are interested in maintaining a set of differences between all timer pairs, as this will allow us to determine if certain combinations of delay element changes are possible from a given state. More precisely, define a state to be a tuple < ?/, E > where y is a vector of the current state of a network with n delay elements and E is a lower triangular matrix of intervals depicting the differences between the times remaining on delay elements i and j (0 < j < i < n). While E will give us the relative differences between timers, it can only provide differences relative to other timers in the network. What is also needed is another timer or clock that keeps track of the "actual" time so that the differences maintained represent differences with respect to some real time. This is achieved by introducing a base line timer in column 0 of E that always has zero time remaining on it. In this way we can decrease the time on the timers of those delay elements that remained unstable through a transition. This will be made more precise 1Note that this differs from the way time was maintained in the BBD race model of Chapter 2.2.1 Chapter 3. Continuous Bounded Delay Analysis 31 later. For now we will take a closer look at the lower triangular matrix of intervals to gain a better understanding of the information it provides. Lower Triangular M a t r i x We begin by considering the information provided by an arbitrary entry a^ of the lower triangular matrix E. As previously mentioned, <7,j is an interval that represents the difference between the time remaining on timers i and j . To properly understand what such an entry tells us we consider an example where the time remaining on timers i and j are bounded by intervals [3,4] and [3,5] respectively. Interval i tells us that the corresponding delay element will remain unstable anywhere from 3 time units up to and including 4 t ime units from the current time; similarly for interval j . Now consider the difference between these intervals, specifically i — j (refer to appendix A for information on interval arithmetic). This difference is represented by the interval [—2,1]. What this tells us is that delay element i can change anywhere from 2 time units before delay element j to 1 time unit after delay element j . A lower triangular matrix of such intervals then, provides us with all difference pairs. At this point it should be mentioned that we are only interested in considering (re-entries where both timers i and j represent unstable delay elements. For all practical purposes, timers of stable delay elements have infinite time remaining on their them and therefore cannot contribute to the body of information contained in E. In the analysis procedure described in the next section, the interval (—oo, oo) is used to represent stable delay elements. This lower triangular matrix, as is, does not necessarily provide us with an accurate account of a state of the network. The intervals it contains were derived without consid-eration of constraints that may be imposed by other pairs. That is, the difference pairs were derived through a "one step" comparison without considering other information Chapter 3. Continuous Bounded Delay Analysis 32 that could be provided by a less restrictive comparison. For instance, the interval o^ was derived by only considering the information from timers i and j . But what of other timers in the network? Certainly they are capable of influencing (tightening) this rela-tionship. Without a more precise account it becomes very difficult to determine possible successor states, as what may appear to be a possible transition may not be as a result of hidden constraints imposed by other timers. Algor i thm 0 This brings us to one of the most important components of the analysis procedure, that of transforming S into a lower triangular matrix that captures precisely all the information obtainable from S. This transformation process, which we will call algorithm 0 (shown in Figure 3.25), is an adaptation of the Floyd-Warshall all-pairs shortest path algorithm, and indeed derives the desired information producing a new canonical lower triangular matrix [11]. for k = 0 to m such that k £ U(x • y) U {0} for i = 1 to m such that i ^ k and i 6 U(x • y) for j — 0 to i — 1 such that j ^ k and j £ U(x • y) U {0} <Tij Pi (aik + <rkj) if j < k < i Vij n (<Tik - <?jk) if k < j <*%i H (akj - (Tki) if i < k <Tij = < Figure 3.25: Algorithm 0 The algorithm proceeds by considering all pairs of intervals in the lower triangular matrix over indices i, j , and k such that i, j , and k are not equal and correspond to unstable delay elements. It then deduces what information it can about the interval at position i, j in an at tempt to tighten it. For example, consider the following intervals in S before running 0 ; a^ = [—1,2], c^y = [0, 2], and aki = [—1,0]. 0 attempts to deduce Chapter 3. Continuous Bounded Delay Analysis 33 more information about (T,j by subtracting (Jfci from crfcj (i.e.,. (z—j) = (k —j) — (k — i)). This gives us crij = crkj — &ki = [0,2] — [—1,0] = [0,3]. By intersecting this new er,j value with the original we get a new tighter bound of [0,2] based on the information provided by timer k. Had (Tkj = [—3, —2], and (Tki = [0,1] then the new tighter bound would have been [—1, —2], where the lower bound exceeds the upper bound. This is known as an empty interval and indicates an inconsistency between the timers. The presence of an empty interval is fundamental in the determination of successive states. This will be seen when we discuss the analysis procedure. In [11] it was shown that the lower triangular matrix produced by 0 is canonical and contains complete and accurate information about the differences between timers. 3.1.2 Analys i s Procedure We now proceed to describe the procedure in which the above components are used. The general strategy is to build a directed graph that corresponds to all possible transitions of the circuit2. The graph will represent the behaviour of the circuit with respect to the initial input configuration and therefore can then be used to determine if the circuit behaves as desired. The graph to be constructed contains nodes which represent possible states and edges which represent transitions from one state to another. A transition is made by selecting a subset of the unstable delay elements and changing them (complementing them). In this way it resembles the GMW approach, but, as we will see, not all subsets represent possible transitions. It should be noted at this point that the procedure to be described is singly exponential in the number of delay elements (this will be clear from the construction) and therefore may only be useful for analysing circuits with a relatively small number of delay elements, particularly when a large degree of parallelism exists in the circuit. Chapter 3. Continuous Bounded Delay Analysis 34 Initially we are given vectors x and y which represent the current input values and the current values of the delay elements respectively. They represent a "snapshot" of the current state of the network. In addition, for each delay element i we are given its bounds [di,Di), and excitation function Y{{x • y). With these components the procedure begins by constructing the initial state < y, E >, where E = €)(?/, E) and E is the lower triangular matr ix (0 < J < i < n) (Tij = < [di,Di) if j = 0 (—oo,oo) otherwise Note that by adding the (—00,00) entries at positions where j / 0 in E we are saying nothing about the differences between timers in the network. Instead we leave it up to 0 to derive this information for us to produce E. Subsequent states are generated by considering all possible transitions out of the current state. However, as mentioned above not all transitions may be possible due to constraints imposed by the bounds. In addition, we impose constraints to ensure the following conditions hold. First, we must ensure that each timer has positive time remaining on it as we are moving forward in time. Second, that those delay elements that are about to change must all have the same value on their timers. And finally, the timers for those unstable delay elements that will not change must be strictly larger than the timers for those that will change. These constraints are enforced by intersecting the lower triangular matrix of the current state with a constraint matrix defined as follows. Let U(x • y) represent the set of unstable variables of the current state (i.e., where Y{ ^ ?/,•), and let P be a non-empty subset of U(x • y) representing the delay elements under consideration for change. Then E, the constrained S, is defined as: Chapter 3. Continuous Bounded Delay Analysis 35 (Tij n(0,oo) if j = 0 (1) <Tij n [0,0] if i € P and j eP (2) (0 < j < i < n) &ij = \ aij 0 (0, oo) if i G U(x • y) - P and j € P (3) crtj Pi ( - o o , 0) if z G P and j G i7(x • y) - P (4) <Tjj otherwise Condition (1) enforces our first constraint of positive t ime. Condition (2) enforces our second constraint by assigning 0 as the difference between the times remaining on timers of delay elements that are about to change. Conditions (3) and (4) enforce our third constraint that changing delay elements be strictly larger than non-changing delay elements. We must now execute 0 on E to generate the canonical lower triangular matrix E of intervals satisfying these constraints, from which we can determine whether or not this transition (characterized by P) is possible. We will henceforth refer to this process as determining the feasibility of a transition. Should E contain an empty interval in some position, then we would know that such a transition is inconsistent with the values on at least two timers of unstable delay elements, meaning this transition can not occur. Consequently, the transition for this P is deemed infeasible, and this branch in the graph is abandoned. In this way the feasibility test may be thought of as a trimming step of erroneous branches. Should the branch prove feasible then we proceed to generate the state that results from taking this branch. This involves actually changing (complementing) the delay elements in P and updating E in a manner that reflects the passage of time. Conceptually this means reducing the time on the timers of those unstable delay elements that did not change, and adjusting the time on the timers of those delay elements that have now Chapter 3. Continuous Bounded Delay Analysis 36 become unstable as a result of the transition. This is accomplished as follows. Yi(x-y) if i € P (1 < i < n) Vi yi otherwise Define set O = {i \ i £ U(x • y) f) U(x • y),i $ P} to contain those delay elements that remained unstable through the transition while retaining the same value. This can then be used to identify the timers to be reduced. The idea is to move interval '&ik into the baseline position i of the lower triangular matrix where i is in 0 and k is some fixed element of P (any will do since they all change at the same time). More formally, define the updated S to be S where (1 < i < n) cri0 = < (To, if i € O and k < i (1) —<7ki if i £ 0 and k > i (2) [di,Di) otherwise (3) Assignments (1) and (2) are simply the converse of each other (since we are using an lower triangular matrix) so it will be enough to consider assignment (1) only. What this assignment is essentially doing is reducing the time on timer i. To convince oneself that this is correct one need only consider what the move represents. <7;o represents the difference between timer 0 and timer i. Since timer 0 has no t ime on it, it is in the same state as timer k whose time just ran out resulting in the transition. So the difference between timer 0 and timer i is the same as the difference between timers k and i. As for cTik-, this is modified as described below to allow us to use the new information in column 0 of E, together with 0 , to obtain the correct value. Assignment (3) is intended to represent the interval assigned to column 0 of S for the Chapter 3. Continuous Bounded Delay Analysis 37 remaining cases, consisting of delay elements that have become unstable as a result of the transition and those that are now stable. As for the other positions in £ , they are somewhat more difficult to determine so we assign intervals that we know to be "safe" and let 0 deduce their correct values later. The assignments are (1 < i < n) frij = < era ifieOaadjeO (1) (—oo,oo) otherwise (2) It is easy to see that these are safe assignments, for, in case (1) we know that the new bound after the passage of time must be subsumed by the old bound for the delay elements that remain unstable, and in case (2) we simply enter the interval that represents stability to allow 0 to determine the correct values. 3.1.3 A S m a l l E x a m p l e To demonstrate the method we will carry out the analysis procedure on a small circuit, shown in Figure 3.26. Figure 3.26: Example Circuit Cg. In this example we have two delay elements y\ and y2 with bounds [1,3) and [1,2) respectively. If the input value of x • y — 1 • 11 then the initial state of our graph will be formed as follows: Chapter 3. Continuous Bounded Delay Analysis 38 S = [1,3) [1,2) ( -00 ,00) After running 0 on E to get E we form our initial state, shown here: 11, [1,3) [1,2) ( - 2 , 1 ) As indicated by the underlines, both delay elements are unstable, yielding set U(x • y) = {1,2} for this state. Consequently there are three (the number of non-empty subsets of U) transitions out of this state that must be considered. To simplify the example we will consider only the transition when delay element 2 changes (i.e., when P = {2}). First we must determine if this is a feasible transition. This is done by constraining E, producing E, then running 0 on E to get E. [1,3) [1,2) ( - 2 , 0 ) E = [1,3) [1,2) ( - 2 , 0 ) Since E contains no empty intervals this transition is deemed feasible. Thus, we can proceed to make the transition and construct the state that results. To begin we must change the values on the unstable delay elements. This is simply a mat ter of complementing the values, producing y = 10. As one can see, y\ and 3/2 became Chapter 3. Continuous Bounded Delay Analysis 39 unstable as a result, and therefore U(x • y) = {1, 2}. Using U(x • y), U(x • y), and P we form 0 = {1}. Recall that this means that delay element 1 remained unstable through the transition while maintaining the same value. Set 0 now can be used together with P and E to obtain £ . " ( 0 , 2 ) [1,2) ( -00 ,00) We now run 0 on E producing 0 ( E ) . 0 ( E ) (0,2) [1,2) ( - 1 , 2 ) Therefore the successor state with P = {2} is 1Q, (0,2) [1,2) ( - 1 , 2 ) and the graph becomes as shown in Figure 3.27. Continuing this same process for the remaining subsets of U(x • y), and recursively for each new state generated, we produce the complete graph shown in Figure 3.28. This graph then, may be analysed to determine the behaviour of the corresponding circuit. In this example the absence of cycles (apart from self loops) indicates that no oscillation is present and that all transitions lead to a single stable state. In conclusion, it is shown in [11] that the outcome computed by this method is iden-tical to the final outcome predicted by the Binary Bounded Delay race model presented in Chapter 2.2.1. Chapter 3. Continuous Bounded Delay Analysis 40 I I , [1,3) [1,2) (-2,1) Figure 3.27: Partial BD Analysis Graph for Circuit Cg. 3.2 Ternary B o u n d e d Delay Analys is The Dill/Lewis analysis method introduced in the previous section has as a very serious drawback, an exponential running time with respect to the number of delay elements in the network. Consequently, use of this analysis method must be restricted to very small delay element networks. The problem is compounded by the fact that the general process for verifying the correctness of any network using binary bounded delay analysis involves simulation using all possible combinations of input and delay element values. In the general case, for a circuit with m inputs and n delay elements this means 2*m + n ' potential simulation runs. For the circuit of Figure 3.26, 23 separate simulation runs would be required for the complete circuit behaviour to be mapped. It is clear then, that the Dill/Lewis analysis method, although rigorous, is extremely limited in its practical application. Ideally, the analysis method should provide a high level of accuracy with respect to the underlying race model, be computationally efficient, and moreover provide some degree of data independence so that the analysis can be performed using various forms of data. To be useful in the context of circuit analysis, data independence should allow for data to be represented symbolically as Boolean expressions. This would make it possible Chapter 3. Continuous Bounded Delay Analysis 41 \ |[1,2)(-2,1)J S Figure 3.28: Complete BD Analysis Graph for Circuit C9. to capture the entire behaviour of the network in a single simulation run. For example, consider a correctly functioning two input NOR gate with boolean expressions a and b representing the values on the inputs. Symbolic simulation based on these inputs would yield the output value ->(a + b) and thus provide all the information necessary in a single run to evaluate the behaviour of the gate. In this section we will introduce an analysis method due to Carl-Johan Seger [16] that approaches this ideal. The method is also based on the continuous bounded delay (CBD) model and is referred to as ternary bounded delay analysis. 3.2.1 A n Informal Descr ipt ion Ternary bounded delay (TBD) analysis can be used to derive the behaviour of a network of delay elements under the CBD model. Recall that among the assumptions of the CBD Chapter 3. Continuous Bounded Delay Analysis 42 model was that the delays associated with each element be bounded from above and below by some integer bounds, and that the actual delay associated with any particular element at any moment in time can be anywhere between these bounds. The CBD model however says very little about how transitions from one value to another occur. In BBD analysis, delay elements changed directly from one binary value to another, and this was done for all feasible transistions. In TBD analysis this is not the case. Instead, transitions are allowed to go through an intermediate state where delay elements take on an uncertain value denoted X. This mechanism is used to account for the moments when the value of the delay element is unknown. We begin by informally stating the TBD analysis procedure, as follows: 1. Change the value of unstable delay elements to X as soon as possible (governed by the lower delay bound). 2. Change the value of delay elements from X to a binary value as late as possible (governed by the upper delay bound). 3.2.2 Analys i s Procedure To implement the TBD algorithm we must record a certain amount of information about the previous excitation history of each delay element in the network. This is accomplished using the vectors i*, [/', and V1. The first vector, i*, simply records the current value appearing on the output of each delay element in the network at time t. The second vector, £/', records the number of t ime units each delay element has been unstable at a binary value3. The delay elements that are stable or do not have binary values at time t assume value 0. Consider what it means for an entry Uj = k, k > 0. Obviously we can say that delay element j has been unstable for k time units with a binary value, but 3Since we are now dealing with values over {0,X, 1} some familiarity with Ternary Algebra will be helpful. A brief discussion of Ternary Algebra is provided in Appendix B. Chapter 3. Continuous Bounded Delay Analysis 43 more than that we can say that delay element j has been unstable for k time units at the same binary value. This is so because we have insisted that changes between binary values go through the intermediate value J . In a similar manner, vector Vt records the number of time units each delay element has been unstable with a binary excitation. Because transitions must go through X, together with the fact that the excitation function is monotone4, we can tighten this definition by stating that Vt records the number of time units each delay element has been unstable with the same binary excita-tion value. Together these three vectors describe the state of the network at time t, and provide all the information necessary to determine the next possible state of the network. We begin our look at the TBD analysis procedure by first introducing the following definitions. Definit ion 3.1 Let U{x,y) = {j \ Yj(x,y) ^ yj} be the set of delay elements such that in total state (x,y) j G U(x,y) if delay delay element j is unstable. Definit ion 3.2 Let B{y) — {j | yj e B} be the set of delay elements that have a binary value in the state y. Definit ion 3.3 Let BE(x,y) = {j \ Yj(x,y) £ B} be the set of delay elements whose excitation function has a binary value in total state (x,y). Given these sets we can now formally describe the TBD analysis procedure. Assuming the network of delay elements is started in total state (a, b) and that the input a changes to a at time 0 and held stable, the TBD analysis procedure can be defined inductively as follows. 4The monotonicity property provides that the arrival of new X values cannot change the value of the excitation function from one binary value to another. See Appendix B. Chapter 3. Continuous Bounded Delay Analysis 44 Basis: Let the initial tbd-state ( i ° , U°, V°) = (b, ( 0 , . . . , 0), ( 0 , . . . , 0)) Induction Step: Given (z\U\ V ' ) , the state ( i m , Ut+1, Vt+1) is computed as follows: ur U] + 1 if J G f/(a, i*) n £( i*) Vt+1 3 — < ;t+l 0 otherwise V$ + 1 if j € U(a, zl) n B £ ( a , i*) 0 otherwise Yj(a, zf) if 1 < j < m and V/+1 = 2Dj - 1 (1) Yj(a, z*) if m < j < n and V/+ 1 = 2L>, (2) X if c>i+1 = 2^- (3) z\ otherwise (4) Conceptually, for a delay element with bounds [d, D) to assume an X value it must currently have a binary value and have been unstable for at least d consecutive time units. U keeps track of this information for each delay element in the network. Similarly, for the delay element to take on a binary value after having been X it must have been unstable with a binary excitation for D — e time units (for a sufficiently small e). V keeps track of this information. The value e is to account for the fact that delay bounds are always open on the right (e.g., [d, D)) requiring that changes take place at some time strictly less than D. The algorithm accomplishes this by scaling the delay bounds by 2, in effect creating openings where values can be safely changed from X to binary without fear of overlap between intervals. The algorithm associates these openings with odd time units and behaves in such a way as to ensure that all delay element changes from X to Chapter 3. Continuous Bounded Delay Analysis 45 binary take place in these openings only, and that all changes from binary to X take place outside these openings (i.e., during even time units). Assignment (1) above sets things up by changing input nodes from X to binary at odd time steps (2Dj — 1). This change, if it is to affect another delay element i in the network, will do so at some 2D{ t ime units later (assignment (2)). This means that subsequent X to binary changes will also occur at odd time steps, each being a 2Dj offset of the initial odd time step. Assignment (3) corresponds to the transition that occurs when a node has been un-stable with a binary value for t ime equal to its scaled lower bound 2dj. Since we are starting from an initial stable state and changing inputs at time 0, the effect of these input changes will be felt at time 2dj, an even number of steps, when the value of the delay elements become X. This change will be felt subsequently by other delay elements in the network at 2d offsets of time 2dj, thus ensuring that binary to X transitions take place only during even time steps. Assignment (4) simply handles those cases where no changes occur. For the algorithm to work as outlined above it must ensure that values can only be propagated through each delay element via X. Proper ty 3.1 In the TBD algorithm, the value of a delay element can only change from a binary value to X and from X to a binary value. Proof: Given some delay element j with delay bounds [dj, Dj) where 0 < j < (m + n), dj < Dj, and dj, Dj G AT. Assume this delay element currently has a binary value and that it is possible to transition from one binary value to another without going through X. For this delay element to change directly to another binary value it must avoid assignment (3) of the algorithm. This means that it must be unstable with a binary Chapter 3. Continuous Bounded Delay Analysis 46 excitation for less t ime than it is unstable with a binary value. In other words Vj < Uj => 2Dj - 1 < 2dj => Dj-\<dj =* #i <<*; + § But dj < Dj and dj,Dj 6 JV, therefore Dj ft dj + \ and we have a contradiction. Consequently we conclude that it is not possible to transition from one binary value to another without going through X. • Once a binary to X transition has occurred in the TBD algorithm, a degree of uncer-tainty has been introduced into the circuit that did not exist before. Whether or not this uncertainty (X) will be removed later on will depend on subsequent behaviour. There is no mechanism for remembering previous behaviour. For this reason TBD analysis does not make use of all information available. A consequence of this is that TBD analysis is much faster than analysis using the Dill/Lewis method, but can produce pessimistic results, indicating the presence of timing problems where none exist. In this way TBD analysis may be guilty of computing false negative results. To conclude, in [7] it is shown that the results obtained by applying the TBD algorithm to a delay element network of bounded inertial delays summarize exactly the outcome predicted by the Extended Bounded Delay race model. 3.2.3 A Small E x a m p l e To illustrate this algorithm we will run it on a very simple network of three delay elements connected as shown in Figure 3.29. This network corresponds to circuit Cg of Figure 3.26. We have introduced delay element 0 to account for the delay associated with the input and arbitrarily assigned delay bounds [1,2). Chapter 3. Continuous Bounded Delay Analysis 47 v— n ii v — ' n -n ^ rt -n [1,2) ^ - ^ [1,3) v - ^ [1,2) Figure 3.29: Delay Network JV9. With excitation functions YQ = 1, Y\ — yo, and Y2 = yoyiV2, assume the network is initially in the stable state described by ( i° ,o>0 ,y°) = ((1,0,1), (0,0,0) , (0,0,0)) and that at time t = 0, Y0 changes from 1 to 0. This will generate the next state {i\U\V') = ((1,0,1), (1,0,0), (1,0,0)) Since delay element 0 has lower delay bound d\ = 1 it will not be affected by the change until it has been unstable at value 1 for 2d\ = 2 time units. We can see that this is not yet so, as the value of UQ = 1. Notice also at this t ime that V0l = 1 indicating that delay element 1 has been unstable with a binary excitation (lo = 0) for 1 time unit. Delay elements 1 and 2, so far, have been isolated from the input change. At the next time step delay element 0 will have been unstable at value 1 for 2d\ = 2 t ime steps and therefore will change to X as shown here. (P,U\V2) = ( (X,0,1) , (2,0,0) , (2,0,0)) Note that the transition to X occurred on an even time step. All transitions to X resulting from this transition are henceforth guaranteed to occur on even time steps (2dj offsets from time t = 2). At this point delay element 0 no longer has a binary value which will be reflected in UQ = 0. However, at the same time, delay element 0 has had a binary excitation of 0 Chapter 3. Continuous Bounded Delay Analysis 48 for 2D\ — 1 = 3 time units, and being an input node will now change from X to its new value 0. The next state is shown here. (P,U3,V3) = ((0,0,1), (0,1,1), (3,0,0)) Note that this X to 0 transition occurred during an odd time step ensuring that all future X to binary transitions resulting from this transition will occur at odd time steps (2Dj offsets from time t — 3). The next three states will be as follows (i\U\V4) = ((0,X,X), (0,2,2), (0,1,1)) ( i 5 ,c> 5 , ! / 5) = ( ( 0 , * , * ) , (0,0,0) , (0,2,2)) ( i 6 , £ / 6 ,V 6 ) = ((Q,X,X), (0,0,0), (0,3,3)) with delay elements 1 and 2 changing to X at even time step 4. Note that despite the presence of two X ' s on the inputs to excitation function Y2, the sole 0 value is enough to produce a binary excitation, and consequently we have incremented the value of V24 from 0 to 1. During the next step delay element 2 will have been unstable for 4 time units with a binary excitation (value 1) as recorded by entry V27 = 2D2 = 4. Delay element 2, being an internal node, will now change from X to 1 producing the state (i7,U7,V7) = ( (0 ,X,1) , (0,0,0), (0,4,4)) After two more steps delay element 1 will have been unstable with a binary excitation and it too will change from X to binary as shown here. ( i* ,£ /s ,ys) = ((0,X,1), (0,0,0), (0,5,0)) (i9,£79,I>9) = ((0,1,1), (0,0,0), (0,6,0)) Chapter 3. Continuous Bounded Delay Analysis 49 Now that delay element 1 is no longer unstable, V^° will become 0 and the trace will terminate in the state ( i 1 0 , c>10, Vw) = ((0,1,1), (0,0,0), (0,0,0)) indicating that the network is now stable. The complete trace is shown in Figure 3.30. <i°, U°, V°) {z\U\V^) (z\U\V>) (i3,u3,v3) <i4,c>4,V4) (i5,U5,V5) (i6,U6,V6) (i7,U7,V7) (i8 , L>8, V8) (i9 , c>9, V9) (i10, l>10, V10) = = = = = = = < = < = ( = ( = ( ; (i,o,i), ; ( i ,o , i ) , ' (*,0,1), ' (0,0,1), (Q,X,X), (0,X,X), (0,X,X), (0,X,1), (0,X,1), ( (0,1,1), ( (0,1,1), ( '0,0,0), [1,0,0), [2,0,0), :o , i , i ) , [0,2,2), [0,0,0), [0,0,0), [0,0,0), [0,0,0), 0,0,0), 0,0,0), (0,0,0 (1,0,0 (2,0,0 (3,0,0 (0,1,1 (0,2,2 (0,3,3 (0,4,4 (0,5,0 (0,6,0 (0,0,0 Figure 3.30: Complete Trace. 3.2.4 Symbol ic Simulat ion In this section we transform the TBD algorithm of the last section into a version that is data independent. To achieve this we must remove conditions that test for specific values such as those required for incrementing entries in U and V. In the TBD algorithm we had associated with each delay element a ternary value and a ternary excitation. In an at tempt to simplify matters we introduce an encoding scheme known as "dual-rail" encoding which will take us from a ternary domain to the more familiar binary domain5. This encoding scheme is shown in Figure 3.31. 5For a discussion on translating ternary excitation functions into their encoded forms see Appendix C. Chapter 3. Continuous Bounded Delay Analysis 50 Ternary Value a 0 X 1 Encoded Value oc.la.0 0 1 1 1 1 0 Figure 3.31: Dual-rail encoding of ternary values. A side effect of this encoding scheme is that each delay element must now be repre-sented by two, one for each rail. We denote the high rail by .1 and the low rail by .0. This is shown in Figure 3.32 along with the possible transitions that can occur. A very significant feature of these encoded transitions is that changing from a binary value to an X involves changing one of the rails from 0 to 1, and that changing from X to a binary value involves changing one of the rails from 1 to 0. Consequently, in deriving a "dual-rail version" of the TBD algorithm, a 0 to 1 transition should occur as soon as possible and a 1 to 0 transition should occur as late as possible. This is represented graphically in Figure 3.33. Recall that in the TBD algorithm, binary to X transitions occur at even time steps and X to binary transitions occur at odd time steps. In the dual-rail version this translates into 01 or 10 to 11 transitions occurring at even time steps and 11 to 01 or 10 transitions occurring at odd time steps. As a result there is no danger of two rails changing at the same time. So far however, all that has changed from the original TBD algorithm is that the domain of values over which we must test has moved from ternary to strictly binary. We have yet to achieve any kind of data independence. To do so we must now modify the delay elements so that they no longer test for specific binary values. The required modification is presented in Figure 3.34 and shows the general transformation for an Chapter 3. Continuous Bounded Delay Analysis 51 (a) y j (b) rYj.i fYj.O Ternary Values 0 ^ X 1 X X »• 0 X — - 1 Encoded Values 01 » - l l 10 »-l l 11 »-01 11 »-10 (c) y j . i yj.o yj.i Figure 3.32: Ternary to dual-rail representation: (a) Input node; (b) Internal node; (c) Transitions. internal delay element. The transformation for input delay elements is exactly the same except there are only 2D — 1 unit delay elements in the delay chain. We refer to the modified delay element as a delay circuit. To simplify the discussion of the delay circuit we will discuss only the delay circuit of an internal delay element as it is trivial to extend the discussion to delay circuits that represent input delay elements. A delay circuit consists of a series of 2D unit delay elements, to be known as a "delay chain", connected as shown to some delay free AND and OR gates. The delay Chapter 3. Continuous Bounded Delay Analysis 52 0 — * - l 2dj -1 Mj (a) -1 2dj 2D-0 —»-l 1 —»-0 2dj 2 DJ (b) • yj.i Figure 3.33: Dual-rail version of the TBD algorithm: (a) Input node; (b) Internal node. chain behaves in a manner similar to a shift register where values arriving at the left are shifted to the right during each time unit of the simulation. The delay chain serves as the mechanism for recording the number of time units a signal has been present on the input of the delay element. In this way it takes the place of sets U and V described in the last section. The AND and OR gates serve to make proper use of the information recorded in the delay chain. AND gate 1 sends the new value to OR gate 2 as soon as possible (i.e., after 2d time units), playing the role of assignment (3) of the TBD algorithm described in the last section. OR gate 2 is present to give favour to 1 values seeing to it that binary to X transitions to occur as soon as possible. Together, OR gate 1 and AND gate 2 send the new value to the output as late as possible (i.e., after 2D time units), corresponding to assignment (2) of the TBD algorithm. The feedback loop from OR gate 2 to AND gate 2 is the mechanism for retaining the value of the old output (i.e., preventing a X to binary transition) for as long as possible. Chapter 3. Continuous Bounded Delay Analysis 53 Figure 3.34: Delay Circuit for Delay Element with bounds [d, D). To provide more insight into the behaviour of the delay circuit we will consider an example of a ternary 0 to 1 transition and view the behaviour on both rails. Refer to Figure 3.35. In this example we have on each rail a delay chain of length 2D = 6. In addition the number of inputs to each AND gate 1 is 2d — 2, consequently these delay chains are associated with delay elements that are bounded by the interval [1,3). Initially each rail is stable and together represent the encoded value for a ternary 0. Assume that at time 0 a ternary 1 becomes present on the input. At time 1 this new value will be felt on the delay chain as seen in Figure 3.36 where the values 1 and 0 are now present in the first unit delay element of the high and low rail respectively. Since the signal must be present for at least 2 time units it does not affect the output yet, demonstrating the delay property. Consider, for a moment, what would happen if the input value suddenly changed back to a ternary 0 at this t ime. This would be felt on the delay chain at the next time unit with values 0 and 1 in the first unit delay element Chapter 3. Continuous Bounded Delay Analysis 54 Figure 3.35: Example: Delay Circuit for Delay Element with bounds [1,3). Initially stable with ternary value of 0. of the high and low rail respectively (see Figure 3.37). In such a case, AND gate 1 would serve to suppress the initial ternary 1, preventing it from reaching the output of the delay circuit, thus providing the circuit with the desired inertial property. Referring again to Figure 3.36, notice that on the low rail the output of AND gate 1 is now 0 but that it does not affect the output of OR gate 2. This is due to the feedback loop from OR gate 2 to AND gate 2 mentioned earlier. If the previous value of OR gate 2 was a 1, as in this case, then this loop will ensure that it remains a 1 for as long as possible, doing its part to ensure the binary to X transition occurs once the high rail changes. During the next t ime unit the signals propagate along their respective delay chains as shown in Figure 3.38. At this time AND gate 1 on the high rail outputs a 1 which now appears on the Chapter 3. Continuous Bounded Delay Analysis 55 {£}< {?} £}l{7]i{7}XJ7} Figure 3.36: Example: Delay Circuit for Delay Element with bounds [1,3). Configuration following the arrival of a ternary 1 on the input. output of that rail. Both rails are now at value 1 representing a ternary X, and will remain so until the low rail changes from 1 to 0 which will not occur until O's are present in all unit delay elements of that rail. This of course will occur 4 time units later at which time at total of 6 time units will have elapsed from the time the ternary 1 first appeared on the input. The resulting configuration will be as shown in Figure 3.39 whose output represents a ternary 1. Finally, it is important to notice that the transformed delay elements represent cir-cuits in which no data dependent tests are present. The unit delay elements of the delay chain can assume any Boolean value. Consequently, by using this transformation tech-nique together with dual-rail encoding, the TBD analysis method can be used to analyse networks of delay elements using symbolic data. Chapter 3. Continuous Bounded Delay Analysis 56 {oHIHo}i{o}i{£}X0 3 4 5 6 D 7$J>±° Figure 3.37: Example: Delay Circuit for Delay Element with bounds [1,3). Demonstrat-ing the intertial property of the delay circuit. {o> ^ •{7jl{7]l{7fJ{7} 3 4 5 6 Figure 3.38: Example: Delay Circuit for Delay Element with bounds [1,3). Configuration after two time units. Chapter 3. Continuous Bounded Delay Analysis {^{^•{oJiCojlCoJ^ D -z^jylo Figure 3.39: Example: Delay Circuit for Delay Element with bounds [1,3). configuration after six time units. Chapter 4 A Continuous B o u n d e d Delay Network Simulator We now present a simulation tool for analysing circuit behaviour under the Continuous Bounded Delay model. The simulator transforms a circuit specification into a network of delay elements for analysis using either the Binary Bounded Delay method described in Chapter 3.1, or the Ternary Bounded Delay method of Chapter 3.2. We begin by describing the simulator interface, features, and how it would typically be used. We then consider a couple of small examples to demonstrate how it can be used as a design aid. Finally, we present an example of a larger circuit to demonstrate how the two methods can be used in concert to tackle a more difficult problem. 4.1 Us ing the Simulator To describe the general use of the simulator we will guide the reader through a typical session, taking time to point out some of the simulator's features in order to give a general overview of the tool. For a more complete discussion on its use we refer the reader to the users guide. The simulator is invoked by entering the command 'cbd' at the command line. This may be followed by an optional file name argument which contains a circuit specification. Once invoked the user is greeted with the prompt (cbd), indicating that the simulator is at its root level. At this level, one typically enters the circuit specification (if not provided upon invocation) either manually or through input redirection. The specification will contain a list of all components (nodes) in the circuit. This includes input and non-input 58 Chapter 4. A Continuous Bounded Delay Network Simulator 59 nodes. For each node a value is to be provided corresponding to the nodes initial state. Also required for each node is an interval indicating the upper and lower delay bounds, and for all non-input nodes, an excitation function. For circuit C$, of Figure 3.26 the specification would be as follows: ::define net :begin inputs x 0 :end inputs :begin noninputs " y l " 1 "y2" 1 :end noninputs :begin excitations II 1 II ii II y l ~ x "y2" ~ ("x" & " y l " &"y2" ) :end excitations :begin delays "x" [1,2) " y l " [1,3) "y2" [1,2) :end delays ::edefine net Upon reading the specification, the simulator generates an internal network represen-tation and returns to the user with the (cbd) prompt. At this stage the user is ready to enter one of two analysis modes. Depending on the size of the network and the type of analysis required, the user may either enter ternary bounded delay (tbd) mode or binary bounded delay (bbd) mode. Symbolic analysis can be carried out in tbd mode only, for reasons described in Chapter 3, otherwise the user is free to choose between the two. To perform tbd analysis the user enters tbd at the (cbd) prompt. This will result in the new prompt (tbd), indicating that we are now in tbd mode. To enter bbd mode, one enters Chapter 4. A Continuous Bounded Delay Network Simulator 60 bbd at the (cbd) prompt. To return to the (cbd) prompt from either mode, one must enter the quit command. Commands in either mode are essentially the same, so we will proceed as if in bbd mode. There are various things the user may wish to do at this stage. When carrying out any analysis one usually requires a trace of the network activity. This involves setting up a list of those nodes in the network that we wish to view. This is accomplished with the view (or just v) command. In the analysis examples used throughout, we have monitored the behaviour of all nodes in the network. To do the same for the network specified above, one would enter the following. (bbd) view "x" "yl" "y2" This sets up a view list to contain the three nodes entered. To see the current contents of the view list one may enter the view command with no arguments. Now that the view list has been set up, we may begin the analysis. This may involve supplying a new input value. The network specified above is in a stable state, as can be easily verified, and consequently requires a new input value before analysis can begin. Tbd analysis requires that we begin with a stable network. This is necessary so that the delay chains for each node can be properly initialized. For bbd analysis, this is not a requirement. Had the network been unstable to begin with, we could have gone straight to the analysis stage without having to provide a new input value. However, since our network is stable we must supply a new input value. This is accomplished by using the newinput (or just n) command as follows. (bbd) newinput "x" 1 We are now ready to analyse the networks response to this new input value. This is done using the step command. However, before we issue this command, a few words are required to understand what it means to "step the network". Chapter 4. A Continuous Bounded Delay Network Simulator 61 A step corresponds to a single time unit, as dictated by the delays. The notion of a step in tbd analysis is quite natural as was seen in Chapter 3.2. However the same cannot be said of bbd analysis, as the graph generated cannot be easily understood in terms of steps. To remedy this we have introduced a "clock" into the network that changes at the completion of every time unit. The graph generated then, contains an extra value representing the value of the clock. The different values a node can assume at time t correspond to the values present on the vertices in the graph in which the clock reads t. To be consistent with tbd analysis, we output the least upper bound of these values, using an X to indicate that a node may be either 1 or 0 at that time. The step command has a single optional argument for specifying the number of steps to take. The default is one step. The user may also specify an * for repeated steps. In tbd mode the step * command repeatedly steps the network, stopping only when it becomes stable. The same cannot be done in bbd mode. Oscillation in a network analysed in bbd mode is represented in the graph by the presence of a cycle as discussed in Chapter 3. This means stepping will continue without end if not checked. The same is true for stable states which are represented as self loops. For this reason we introduce a limit on the number of steps that can be taken when the step * command is entered in bbd mode. Detecting stability then becomes a matter of interpreting the output. We now issue the step command as follows. (bbd) step * In response to this command, bbd analysis will construct the complete graph which will essentially correspond to that shown in Figure 3.28 in Chapter 3.1. In general, for medium sized circuits this may take quite a while to generate as this is an exponential procedure. Once the graph has been completed, stepping is a mat ter of traversing the graph in a breadth first manner, searching for children with the same clock value. For Chapter 4. A Continuous Bounded Delay Network Simulator 62 our network, the step * command will generate the following trace. 1: "x" 1 "yl" X "y2" X 2: "x" 1 "yl" 0 "y2" X 3: "x" 1 "yl" 0 "y2" 1 4: "x" 1 "yl" 0 "y2" 1 5: "x" 1 "yl" 0 "y2" 1 6: "x" 1 "yl" 0 "y2" 1 7: "x" 1 "yl" 0 "y2" 1 8: "x" 1 "yl" 0 "y2" 1 9: "x" 1 "yl" 0 "y2" 1 10: "x" 1 "yl" 0 "y2" 1 Here we can see that the network requires 3 time units to stabilize. At present, only a single run is possible in bbd mode. In tbd mode, entering a new input value at this stage, then stepping the network, will cause the trace to continue to step 11 and on. Since bbd proceeds by constructing the entire graph, continuing beyond this point with a new input value would involve the construction of a new graph. This is not a problem in cases such as this when the circuit stabilizes with binary values on all nodes. But when this is not the case it becomes unclear how to proceed. Such issues will likely be addressed in future versions. In the next section we will look at more interesting examples to discover more about how the simulator can be used to study network behaviour. 4.2 Analys ing S imple Circuits Circuit Cio of Figure 4.40 provides an interesting example for analysis under the CBD model. This circuit, which we will loosely refer to as a latch, serves as a particularly useful example due to its size and susceptibility to oscillation. Chapter 4. A Continuous Bounded Delay Network Simulator 63 reset Figure 4.40: Example Circuit C\Q. We "set" the latch by lowering the reset input signal. This should result in a high signal on the output at Q. Alternatively, we "reset" the latch by raising the reset signal, to give us a low signal on Q. For circuit C\o to behave correctly, according to the set and reset operations, we must carefully select the delay bounds for each component. The delay bounds associated with the input can be arbitrary chosen, as they do not affect the correct functioning of the circuit. As a result we will select the interval [1, 2) to represent its delay bounds. Selecting the bounds for the two NAND gates requires some thought. This can be aided through simulation. To get an idea of how the circuit behaves we can use the same interval assigned to the input delay for the NAND gates, and try it out. A stable state specification for circuit Cio, in which all components are governed by delay bounds [1,2), is given below. Chapter 4. A Continuous Bounded Delay Network Simulator 64 ::define net .begin inputs r 0 :end inputs :begin noninputs "Q" 1 y i :end noninputs :begin excitations 11 /~\11 til 11 ft FF tt \ Q ~ ( r & y j it n (it ii ft it f\u \ y ~ ( r &; Q ) :end excitations :begin delays "r" [1,2) "Q" [1,2) "y" [1,2) :end delays ::edefine net Since this circuit is quite small we can run binary simulation in either tbd or bbd mode. Once the simulator has been invoked and assuming the specification is in file 'speclO', the session proceeds as follows. (cbd) < speclO - provide circuit specification (cbd) bbd - enter bbd mode (bbd) v "r" "y" "Q" - view all components (bbd) n "r" 1 - new input value (reset) (bbd) s 3 - step 3 time units In response to the step command, the simulator will generate the following output. Constructing graph... 1: "r" X "y" 1 "Q" 1 2: "r" 1 "y" X "Q" X Chapter 4. A Continuous Bounded Delay Network Simulator 65 3: "r" 1 "y" X "Q" X The circuit stabilizes in state 1 • XX. As we expected, the circuit contains timing problems as indicated by the presence of the X values. By assigning the same delay bounds to both NAND gates, the results of the simulation are dependent on the winner of the race. The first NAND gate to output 0 will hold the other at value 1, and the circuit will stabilize. With the same delay bounds, one cannot predict a winner. It follows then, that delay bounds must be chosen in a way that will "force" a winner. For our circuit to behave as desired under these input conditions we clearly want the top NAND gate to win the race so that it will register a 0 on output Q. To achieve this we must assign delay bounds that are strictly less than those assigned to its opponent. We will select delay bounds [2, 3) so that this NAND gate will not be affected by the input until it becomes stable. For the opposing NAND gate we select delay bounds [4,5), and run the simulation again. This t ime we get the following results. Constructing graph... 1 2 3 4 5 "r" "r" "r" "r" "r" X "y" 1 "Q" 1 1 "y" 1 "Q" 1 1 "y" 1 "Q" X 1 "y" 1 "Q" X 1 "y" 1 "Q" 0 As expected, the adjustment to the delay bounds were sufficient to ensure that the upper NAND gate prevailed as the decisive winner. Consequently the circuit stabilized after 5 t ime units with the desired results. To completely verify the circuit, one would have to carry out this sort of analysis on all input changes. In this example that would mean one more simulation run. However, this can be more of an issue as the number of test cases increases. Chapter 4. A Continuous Bounded Delay Network Simulator 66 4.3 Symbol ic Analys is Circuit C\\ of Figure 4.41 is, what we will call, a "reset dominant latch". Output Q responds to a low reset signal regardless of the signal on the set input. To set the latch the reset signal must be high. set [1,2) [1,2) Figure 4.41: Example Circuit C\\. This circuit can begin in any of the 5 different stable states s r • y Q £ {10 • 10, 01 • 00, 01 • 11, 00 • 00, 11 • 11}. For each of these states, analysis can proceed by changing each of the inputs individually or together, giving us 3 possible input changes for each stable state. To completely verify circuit C\\ using the simulation techniques demonstrated so far, one would have to carry out a total of 15 simulation runs. Even on such a small circuit as this, such a task can be daunting, especially if timing problems are encountered along the way. It is for this reason that symbolic simulation is so desirable. By representing the data using Boolean expressions, symbolic analysis can express all states reachable as a result of an input change in a single simulation run. We now demonstrate this using the simulator for circuit C\\. With two Boolean variables we can represent four of the five stable states at any one time. For instance, the stable states s r • y Q 6 {10 • 10, 01 • 00, 00 • 00, 11 • 11}, can be represented symbolically as a b • a (a&b). Consider the result of symbolic analysis Chapter 4. A Continuous Bounded Delay Network Simulator 67 when we represent the starting stable states by a b • a (a&b), then complement the set input value. / i i i \ if it 11 tt fi it 11 s\tt (tbd) view s r y Q ( tbd) newinput "s" ~a (tbd) step * 1: "s" X "r" b "y" a "Q" a&b "s" a "r" b "y" a&b + X(a&b') + a' "Q" a&b "s" a "r" b "y" a&b + X(afcb') + a' "Q" a&b + X(a'&b) "s" a "r" b "y" a&b + a' "Q" a&b + X(a'&b) "s" a "r" b "y" a&b + a' "Q" a&b + X(a'&b) 2 3 4 5 6 Steps required to stabilize: 6 6: "s" a "r" b "y" a&b + a' "Q" b 'r" b "y" afeb + a' "Q" b This result captures the four stable states {10 • 10, 01 • 11, 00 • 00, 11 • 11}. The stable state 01 • 00 is not represented because it can only result from a change in the reset input, as we demonstrate next. ( tbd) newinput " r" ~ b (tbd) step * 7: "s" a' "r" X "y" a&b + a' "Q" b "s" a' "r" b ' "y" a&b + a' "Q" X(aM> + a') "s" a' "r" b ' "y" a' + X(a&b) "Q" X(a&b + a') "s" a' "r" b ' "y" a' + X(a&b) "Q" a'&b' "s" a' "r" b ' "y" a' + X(a&b) "Q" a'&b' 9 10 11 12 Steps required to stabilize: 6 TO. "r." ~' "~" u' "^r" n> "r»" ^i " r . " ^1 " - ~ " U ' " I T " n> " / " » ' ' r" b ' "y" a' "Q" a'&b' r" b ' "y" a' "Q" a'&b' This takes us back to the stable state from which we originally started (except a and b are now complemented). Now the stable state 01 • 11 is not represented. It can be reached only in response to a change in the set input. Chapter 4. A Continuous Bounded Delay Network Simulator 68 Using only two simulation runs we were able to determine that our circuit will stabilize in response to a set or reset signal in 6 time units (under the given delay bounds). To finish the verification process we would also have to check the response to multiple input changes. In light of the current delay bounds, the simulation would likely reveal timing problems as the AND gate and OR gate race to change value. This may, or may not, be a problem, depending on the assumptions one is willing to make about the arrival of input signals. Regardless of what the results indicate, symbolic simulation is a very powerful mechanism for analysis. 4.4 A Larger Example In Chapter 3.2 we introduced the TBD algorithm and noted, among its desirable prop-erties, its speed of computation and ability to produce results free of false positives1. Such properties make it the obvious first choice method when analysing a circuit. How-ever, it was also discussed in Chapter 3.2 how the TBD algorithm could be pessimistic at times, predicting timing problems where none exist. For this reason it can be very helpful to have an alternative method available to verify suspicious results predicted by TBD analysis. The Dill/Lewis approach serves well in this capacity. In this section we will demonstrate what we consider to be one of the major benefits of the simulator, the ability to perform analysis on two levels. In practice, simulation will be carried out on much larger circuits than those presented in the previous sections. In such cases the Dill/Lewis method will be completely unsuit-able, and designers will be forced to use TBD analysis. In the event of timing problems, that need not be the end of the story. Quite often such problems can be isolated to smaller parts of the overall circuit, resulting in a smaller, more manageable subject for 1A false positive result is one that appears correct but is, in fact, incorrect. Chapter 4. A Continuous Bounded Delay Network Simulator 69 analysis. By decomposing the circuit in this way a designer can hope to discover frag-ments that are suitable for analysis using the Dill/Lewis method. Consider the circuit in Figure 4.42 in which we associate with each gate, delay bounds [7,13). r^oy? i? i > Jy s r-\ y-\ ^ > -V u -^Tv^ j ) IS v^ \ \ h ! J Ls Figure 4.42: Example Circuit Ci2 . We can think of this circuit as a fragment of a much larger circuit that proved to contain timing problems under TBD analysis. These problems can be revealed by per-forming the analysis on the fragment alone (refer to trace (a) in Figure 4.43). Such problems may be due to a design flaw, but the fragment is small enough for analysis using the Dill/Lewis method, so it is worth analysing again. The result of the second analysis is shown in trace (b) of Figure 4.43. As we can, the results of TBD analysis were indeed pessimistic. The analysis using the Dill/Lewis method reveals that the circuit stabilizes in the binary state 1111010 after 80 time units. Consequently the circuits performance under this transition can be evaluated with the knowledge that no timing problems exist. Here we have seen how the two analysis modes available in the simulator can be used together to handle a much larger circuit. In the design of asynchronous circuits, a high Chapter 4. A Continuous Bounded Delay Network Simulator 70 degree of modularity is required to keep things manageable. Such circuits are well suited to this sort of analysis and justify the need for a "dual-mode" simulator. Chapter 4. A Continuous Bounded Delay Network Simulator 71 ^7 >2 x? y4 ys ys y? yj yz ys y4 ys ye y? 1: 0 0 0 0 0 0 1 1: 0 0 0 0 0 0 1 V. X 0 0 15: 1 0 0 22: 1 O X 28: 1 O X 29: 1 X X 36: 1 X X 41: 1 X 1 43: 1 X 1 0 0 0 1 0 X 0 1 0 X 0 1 0 1 0 1 X 1 0 1 X 1 X X X 1 X X X X X X 50: 1 X X X X X X 0 8: X 0 0 15: 1 0 0 22: 1 O X 28: 1 O X 29: 1 X X 36: 1 X X 41: 1 X 1 43: 1 X 1 54: 1 1 1 67: 1 1 1 0 0 0 1 0 X 0 1 0 X 0 1 0 1 0 1 X 1 0 1 X 1 X X X 1 X X X X X X 1 X X X 1 X 1 0 80: 1 1 1 1 0 1 0 0 (a) (b) Figure 4.43: Analysis traces run in (a) tbd mode, and (b) bbd mode. Chapter 5 Conclusions and Future Work In this thesis we looked at several delay models in hope of finding one that could be used to accurately represent the delays found in VLSI circuits. It was further hoped that such a model would give rise to an analysis method for not only describing the behaviours possible in networks of such delays, but also for detecting the presence of critical race and hazard conditions. Such a method, when used to analyse networks representing VLSI circuits, could then serve as a means for circuit verification. We began by assuming very little about the sizes of the delays, assuming they could be arbitrary but finite. This led us to consider three methods for analysing networks of such delays: the GMW race model, the XMW race model, and Ternary Simulation. Each of the three methods were capable of detecting the presence of critical race and hazard conditions, producing results consistent with the other. However, their usefulness was limited due to the very small number of behaviours that can be realized by circuits in which delays are assumed to be arbitrary. By allowing delays to be arbitrary in size, we allow too much room for the "devils advocate" to play, and consequently limit what can be done. In a physical circuit, one can always say something about the relative sizes of delays, but due to factors such as temperature and age, it is difficult to establish a precise fixed size. As a result, delays were allowed to vary in time, but only between some integer bounds. We then looked at what could be discovered about the behaviour of a network of such delay elements. In the hope of simplifying the process, we began by allowing the 72 Chapter 5. Conclusions and Future Work 73 delays to assume only integer values between the upper and lower bounds. This lead us to consider a number of Discrete Bounded Delay models. Unfortunately this proved to be less than ideal. The Discrete Bounded Delay model had to be abandoned in favour of the Continuous Bounded Delay model as it could not match its level of accuracy. As a result we were forced to treat t ime as a continuous quantity if we were to acquire the kind of accuracy desired. Two Continuous Bounded Delay race models were presented. The Binary Bounded Delay (BBD) race model and the Extended Bounded Delay (XBD) race model were both capable of capturing all behaviours possible according to their underlying delay models. Unfortunately both methods would produce an infinite number of possible race sequences and therefore were not very useful for practical analysis. However, in Chapter 3 we de-scribed two analysis methods capable of efficiently capturing the behaviours predicted by these race models. Continuous Binary Bounded Delay Analysis captured the behaviours predicted by the BBD race model, and Continuous Ternary Bounded Delay Analysis captured the behaviours predicted by the XBD race model. Individually, each analysis procedure contained a drawback. The binary method captured precisely the results of the BBD race model, but did so in singly exponential time. The ternary method was much more efficient, requiring only polynomial time, but could produce results that contained false negatives. However, when used together it was possible for each method to "back up" the other. In Chapter 4 we presented a simulation tool that made use of this potential by making both analysis methods available to the user. In addition, the simulator contained a data independent implementation of the ternary procedure, making it possible for analysis to be performed using symbolic data. In Chapter 4 we demonstrated the simulator, showing its features and how it can be used to understand and verify circuit behaviour. Currently, it implements what was Chapter 5. Conclusions and Future Work 74 originally conceived. However, during its construction and use, many potential improve-ments and enhancements came to light. In the section that follows, we will look at some of these improvements to show how they can make the simulator a more powerful and useful design aid. 5.1 Future E n h a n c e m e n t s The initial notion of a simulator with two analysis modes seemed very appealing in itself. From a single specification, one would be able to simulate a circuit using one mode, study the results, and if desired, do the same afterward in the other mode. But, as with any software development project, the realization of an even greater potential became evident soon after the development started. This included ideas of how to make the simulator easier to use, and how to make it more productive and thus more useful. In this section we will present only some of the ideas that came to light in hope that they might be implemented in future versions. We have divided these ideas into two main categories; those that improve the tools usability, and those that improve its ability to analyse results. 5.1.1 Usabi l i ty Features While using the simulator it became apparent that certain features could be added to avoid some of the more more tedious tasks. Most notable was the view command. This command takes as arguments the nodes whose values are to be displayed. In the analyses performed, we were interested in viewing all nodes in the majority of cases which made it quite onerous to have to enter all the nodes, particularly when there were many. Once the input specification has been read in, the simulator knows the names of all the nodes. Therefore, an obvious improvement to the view command would be to introduce a flag Chapter 5. Conclusions and Future Work 75 that indicates that we wish to view all nodes, thus saving a lot of typing. Another feature that could help would be to allow input redirection to this command so that different lists of nodes could be maintained in separate files. This would be particularly useful for analysing large circuits. Beyond that one could imagine providing set operations so that the nodes in separate files could be combined or differentiated. In line with the notion of increasing usability through the of addition input redirection, is allowing input redirection to be nested within specification files. This becomes more of a necessity when dealing with circuits with hundreds of nodes. As such, one could maintain a separate file for input nodes, non-input nodes, excitation functions, and delay bounds. Output redirection could also serve as a useful enhancement. For traces that might be very long (i.e., issuing step * in tbd mode), output redirection would provide the ability for the user to view the results later with aid of an editor. Together, input and output redirection could be used to run the simulator in "batch-mode". For a very large circuit it would certainly be desirable to be able to leave the simulation to run on its own. 5.1.2 Produc t iv i ty Features The more significant enhancements that came to light were those that could improve the simulators ability to assist the user in diagnosing problems. For large or complicated circuits, a simulator will only be used if it can make the job of troubleshooting easier. To this end we present several proposals for improvement. First of all, it can be quite cumbersome to interpret traces in which activity at all steps has been provided. More often we are interested only in places where changes occur. By providing the ability to detect these changes, the simulator would be able to limit the trace displayed to the user in much the same way as watch points are used in a debugger. In addition, such changes could signal break points to limit the progress of Chapter 5. Conclusions and Future Work 76 the run. In many ways the simulator can be thought of as a debugger, and hence, can include many of the features typically found in a debugger. We could go even further by specifying that the trace only be displayed on certain steps if a particular node changes value. In this way the commands to the simulator could resemble queries to a database. For extremely low level analysis we might wish to make available more than just the least upper bound of a result. In bbd mode this could involve providing an image of the partial or complete graph. By being able to visualize timing problems, the graph may provide another level of insight. In tbd mode, low level analysis might involve displaying the contents of the delay chains. One could imagine this to be a tremendous aid to understanding the method. A current restriction is the inability to introduce new input values to the circuit in bbd mode once the graph has been generated. This was discussed in Chapter 4. To do so one must determine when new inputs would be allowed. Recall that at any step we could be in more than one state. Therefore one must deal with the question of whether or not new inputs should be accepted in such a case, and if so whether or not the new input should spawn a new graph from each of these states or some subset of them. There are many issues to address here. One way of dealing with this is to generate the graph "on the fly", rather than construct the complete graph in the beginning, as we do now. This could drastically reduce space and running time, since problems could be detected well before the entire graph takes shape. It would also more easily facilitate new input values. Another feature that could prove useful is the ability to "back up" in a simulation run. One could imagine following a trace so far, introducing a new input, then discovering an error. Rather than having to rerun the simulation to try other sequences of new input values, we could simply back up a number of steps and introduce different inputs to see how the circuit responds. If, while working in tbd mode, an error is detected, we could Chapter 5. Conclusions and Future Work 77 then switch to bbd mode to determine if the error was simply a result of pessimism on the part of the TBD analysis. This sort of ability would allow us to maximize the potential introduced by having two simulators in one. To add to this, the tool might provide the ability to generate "test sequences" in response to an error detected in tbd mode while performing symbolic analysis. The suspected errant expression could be used to generate a list of binary expressions to be used as input to the simulator run in bbd mode. For example, if a two input AND gate with inputs a and b produced a result a + b in tbd mode, then to test this in bbd mode we might have to run the simulation on this gate for all four different input combinations. These combinations could be automatically generated as input for bbd mode analysis. Testing in bbd mode would simply be a matter of changing modes and redirecting these cases to the procedure. With the ability to run both modes concurrently as separate processes, we envision the user switching back and forth between windows as he debugs his design. 5.2 A Third M o d e l The ability to use two analysis techniques clearly provides great benefits for verifying ones design. However with the methods implemented in our simulator, there remains quite a gap between the size of circuit each is capable of efficiently handling. TBD analysis is quite capable of dealing with circuits of large numbers of gates, but BBD analysis is restricted to circuits of not much more than a dozen or so gates. This can be a problem if TBD analysis yields many pessimistic results. To verify each using the BBD approach can take quite a while and may not be practical due to the size of the module and its dependency on other modules. A remedy to this problem might come by way of a third analysis method, one that could provide a level of accuracy and speed somewhere between the TBD and BBD methods. There seems to be a natural trade off between accuracy Chapter 5. Conclusions and Future Work 78 and speed. In TBD analysis we gain speed at the cost of pessimism, and in BBD we gain accuracy at the expense of speed. The question then arises as to whether there exists an analysis method that can provide accuracy approaching that of the BBD method, and speed approaching that of the TBD method. Jerry Burch's work on trace theory [4] may lend itself to such a method. In his trace theory with discrete time he describes a trace structure in which symbols represent physical wires in a circuit. This structure is then augmented with an additional set of symbols to represent the passage of time. In this way a trace can represent a single behaviour in which a transition occurs. For instance, if a: is a symbol representing a physical wire in a circuit, and (f is a symbol representing a single unit of time, then the trace tptpxtp represents a transition that can occur 2 time units from the current time. By representing transitions in this way, the complete behaviour of the circuit can be expressed in the form of a finite state automaton. If we associate the time symbols with discrete units of time, the traces can approximate continuous time. Interpreted in this way, the above trace bounds the set of transitions that can occur on wire x by the interval [2, 3). The verifier described in Burch's paper uses linear time in the number of states in the circuit, but exponential time in the number of components. Although the worst case behaviour is asymptotic, he believes its average case performance can be improved. Some interesting possibilities may lie in approximating continuous time using discrete time models, but much work remains to be done in this area. Bibl iography [1] R.E. Bryant, D. Beatty, K. Brace, K. Cho, and T. Sheffler, COSMOS: A Compiled Simulator for MOS Circuits, In 22nd Design Automation Conference, pp. 715-719, ACM and IEEE, 1985. [2] R.E. Bryant, A Switch-Level Model and Simulator for MOS Digital Systems, Trans-actions on Computers, C-33(2):160-177, February, 1984. [3] R.E. Bryant, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, C-35(8), August, 1986. [4] J.R. Burch, Modeling Timing Assumptions with Trace Theory, IEEE The Proceed-ings of the International Conference on Computer Design: VLSI in Computers, 1989. [5] J. A. Brzozowski and J.C. Ebergen, On the Delay-Sensitivity of gate Networks, Com-puting Science Notes 90/05, Department of Mathematics and Computing Science, Eindhoven University of technology, Eindhoven, The Netherlands, June 1990. [6] J.A. Brzozowski and C-J.H. Seger, Advances in Asynchronous Circuit Theory Part 1, Bulletin of the European Association of Theoretical Computer Science, No. 42, October 1990. [7] J.A. Brzozowski and C-J.H. Seger, Advances in Asynchronous Circuit Theory Part 2, Lecture Notes, University of British Columbia, 1990. [8] J. A. Brzozowski and C-J.H. Seger, A Unified Framework for Race Analysis of Asyn-chronous Networks Journal of the Association for Computing Machinery, Vol. 36, No. 1, January 1989, pp. 20-45. [9] J.A. Brzozowski and C-J.H. Seger, An Characterization of Ternary Simulation of Gate Networks, IEEE Transactions on Computers, Vol. C-36, No. 11, November 1987. [10] J.A. Brzozowski and M. Yoeli, On a Ternary Model of Gate Networks, IEEE Trans-actions on Computers, Vol C-28, No. 3, pp. 178-183, March 1979. [11] D.L. Dill, Timing Assumptions and Verification of Finite-State Concurrent Systems, Lecture Notes in Computer Science, Springer Verlag, Vol. 407, 1989. 79 Bibliography 80 [12] E.B. Eichelberger, Hazard Detection in Combinational and Sequential Switching Cir-cuits, IBM Journal of Research and Development, Vol. 9, pp. 90-99, March 1965. [13] Friedman, A.D. and P.R. Menon, Theory and Design of Switching Circuits, Com-puter Science Press Inc., Woodland Hills, California (1975). [14] H.R. Lewis, Finite-State Analysis of Asynchronous Circuits with Bounded Temporal Uncertainty, Tech. Report TR-15-89, Harvard University, 1989. [15] C-J.H. Seger, Ternary Simulation of Asynchronous Gate Networks Master's The-sis, Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada, May 1985. [16] C-J.H. Seger, Models and Algorithms for Race Analysis in Asynchronous Circuits, Ph.D. Thesis, Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada, May 1988. [17] C-J.H. Seger and R.E. Bryant, Modeling of Circuit Delays in Symbolic Simulation, Formal VLSI Correctness Verification, VLSI Design Methods, II, Elsevier Science Publishers B.V., North Holland, 1990. [18] C-J.H. Seger and J.A. Brzozowski An Optimistic Ternary Simulation of Gate Races Theoretical Computer Science, Elsevier Science Publishers B.V., North Holland, 1988. Appendix A Interval Ar i thmet i c In this section1 we introduce some simple concepts about intervals and investigate the properties of arithmetic and computation on intervals. We write |_rj for the lower bound of the interval r ; that is, L M J = LM)J = LM]J=« Thus [T\ € T (where r is nonempty) if and only if r is closed on the left. Similarly we write |Y] for the upper bound of the interval T. The intersection of two intervals T\ and r2 is that interval r = Ti fl r2 such that | r j = maa;(Lr1J, \T2\) \T\ = m m ( f r i l , |"r2]) r is closed on the left if and only if either both T\ and r2 are closed on the left, or their lower bounds are distinct and the one with the larger lower bound is closed on the left; and r is closed on the right if and only if either both rx and r2 are closed on the right, or their upper bounds are distinct and the one with the smaller upper bound is closed on the right. Intervals can be added In + T2\ = [TlJ + [r2\ fn + r2] = fnl + \T2] 1 Taken from [14]. 81 Appendix A. Interval Arithmetic 82 where T\ + r2 is closed on the left (or right) if and only if both T\ and r2 are closed on the left (or right). Here oo + a = oo for any a. Subtraction of r is defined as addition of —r, where — r is defined by L-^ J = - M and each end of — r is open or closed according to whether the opposite end of r is open or closed. Finally, note that an interval r is nonempty just in case either (a) \r\ < \T],OT (b) both ends of r are closed and [rj = |Y]. A p p e n d i x B Ternary Algebra In this section we introduce some properties of the Ternary Algebra, an algebra over the set T = { 0 , X , 1 } . Define the partial order relationship Q over T as follows: OQX, 1 OX, i \Zi \fi g T One can take the relationship 0 C X to mean 0 is no more uncertain than X. This relationship is graphically represented in Figure B.44. X 0 1 Figure B.44: C relation on T . We can extend this relationship for vectors s,t G T n as follows: s E < iff* E <i V 1 < i < n When s C. t and s / t we say that s is /ess uncertain than £ and write s C t. As an 83 Appendix B. Ternary Algebra 84 example, the following relations hold: 001 C 00X 001 C 00X 0X10 C 0X1X 0X10 C 0 X X X Note that values 0 and 1 are not comparable and therefore are not related by C. As a result 0X10 and 0 X X 1 are not related by C. For any Boolean function / : {0,1}™ —>• {0,1}™, there exists a ternary function called the ternary extention of / and is denoted / : Tn —» T . We define / as follows: f(i) = lub{f(t)\t(E{0,l}n,tOi} The least upper bound (lub) is defined as: for any nonempty set S C T n , £ is the lub of £ iff s C i V ^ € 5", and 5 C r V 5 £ S implies t C. r. Thus, lub{0,1} = X (see Figure B.44), and lub{X0l0,1110, 0100} = X X X 0 . The ternary extensions of the Boolean functions AND, OR and NOT are given in Figure B.45 and can be easily verified. AND 0 X 1 0 0 X 1 X X X 1 1 1 1 1 OR 0 X 1 0 0 0 0 X 0 X X 1 0 X 1 NOT 0 X 1 1 X 0 Figure B.45: Ternary AND, OR, and NOT. The following monotonicity property holds for the ternary extention / of any Boolean function / : sQt=> f(s) Q f(t) Appendix B. Ternary Algebra 85 for all s,t G Tn. This property states that if vector t is at least as uncertain as vector 5 then through the application of / to each vector no more certainty can be gained. This can easily verified. A p p e n d i x C Dual-rail encoding of Ternary functions We introduced in Chapter 3 an encoding scheme that would allow us to disguise ternary values using pairs of binary values. This scheme is known as dual-rail encoding and is shown in Figure C.46. Ternary Value a 0 X 1 Encoded Value a.la.0 0 1 1 1 1 0 Figure C.46: Dual-rail encoding of ternary values Similarly, ternary functions can be encoded using the dual-rail scheme. Following suit, each ternary function Y will be represented by a pair of binary functions [Kl , Y.O]. The encoded versions of the ternary extension of the Boolean functions AND, OR, and NOT are given in Figure C.47. Using these definitions one can easily transform ternary functions into their dual-rail encoded form. For example, the ternary function aX + ft becomes [a.l + /3.0,a.0j3.1]. In the same way one can easily verify that the ternary function a/3 + a/3X has an encoded version [a.l0.1 + a.0/3.0,a.O + /?.0]. 86 Appendix C. Dual-rail encoding of Ternary functions 87 JO aB a+B a f.lO a.lB.l a.l+B.l a.0 f.oO a.O+p.0 a.Op.0 a.l Figure C.47: Encoded versions of ternary AND, OR, and NOT.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- A bounded delay simulator
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
A bounded delay simulator Reid, Robin Morris 1992
pdf
Page Metadata
Item Metadata
Title | A bounded delay simulator |
Creator |
Reid, Robin Morris |
Date Issued | 1992 |
Description | Detecting the presence of timing problems in digital circuits is a difficult matter, but one that can be greatly simplified with the aid of effective analysis tools. Such tools have traditionally lacked the ability to detect the presence of race and hazard conditions. In this thesis we present a simulation tool that is able to detect such problems. In addition, the tool provides two mechanisms for doing so. One approach gives the user the capability of explicitly generating all possible states of the circuit in response to an input change. This type of analysis is extremely time consuming but describes all behaviours possible according to the underlying model. The other approach is far more computationally efficient, dealing mainly with computing the final outcome. Alternatively, this second approach enables the user to analyse a circuit using "symbolic data". However, it is somewhat pessimistic, giving rise to "false negative" results at times. Together though, the two approaches form a useful workbench for verification of circuit designs. |
Extent | 1842104 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2008-12-18 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0051374 |
URI | http://hdl.handle.net/2429/3137 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 1992-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_1992_fall_reid_robin_morris.pdf [ 1.76MB ]
- Metadata
- JSON: 831-1.0051374.json
- JSON-LD: 831-1.0051374-ld.json
- RDF/XML (Pretty): 831-1.0051374-rdf.xml
- RDF/JSON: 831-1.0051374-rdf.json
- Turtle: 831-1.0051374-turtle.txt
- N-Triples: 831-1.0051374-rdf-ntriples.txt
- Original Record: 831-1.0051374-source.json
- Full Text
- 831-1.0051374-fulltext.txt
- Citation
- 831-1.0051374.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051374/manifest