Timing Analysis of VLSI Circuits

This invention relates to the computer-aided design (CAD) of very large scale integrated (VLSI) circuits and more particularly to functional timing analysis of such circuits as part of the design process.

The size and complexity of state-of-the-art very large scale integrated circuits has made it necessary that much of their design and testing be computer-implemented.

Logic synthesis has now become an integral part of the synthesis pipeline of VLSI designs. Algorithms for automatic design of logic, targeting circuit area, delay, testability and power dissipation are now available in most logic synthesis systems. Analysis tools play an integral part in design automation, both in their own right as well as pat of synthesis systems where they are used to evaluate the quality of the synthesized circuits. Timing analysis analyzes the temporal behavior of a circuit; it determines when event occur in a circuit. In a synchronous digital system timing analysis is used to determine the delay of the combinational part of the circuit. The delay of the combinational part is the time taken for the outputs of the combinational circuit to settle to their final value after the inputs have been applied. This delay in turn determines the minimum permissible clocking period of the synchronous circuit. This invention addresses the problem of accurately determining the delay of combinational logic circuits. It is important to know this delay so that the clocking period can be made as short as feasible.

It is familiar practice in a CAD process to represent a combinational logic circuit as a Directed Acyclic Graph (DAG) with the nodes in the DAG corresponding to gates, and the links corresponding to the wires between the gates. Each DAG node can be weighted by the delay of the corresponding gate. The method used to arrive at the node weights is termed the delay model. Delay models vary in the level of accuracy with which they reflect the true gate delay. The choice of the delay model is largely orthogonal to the problem solved by this invention. Hence, the solutions provided by this invention are independent of the delay model used.

Until recently, circuit delay was computed as the length of the topologically longest path in a weighted-DAG representation of the circuit. While this approach is computationally very simple, it tends to be grossly inaccurate (pessimistic) in most situations. The source of this inaccuracy is that in most circuits, the designed signal value propagates to the circuit output via multiple paths, either by design or as a side effect of the application of logic synthesis and high-level synthesis algorithms. A path that is one of the topologically longest paths, but is never the first path to propagate a value to the output for any input vector, cannot be responsible for the circuit delay. Delay estimation under this additional complication requires a functional timing analysis of the circuit. Functional timing analysis is timing analysis which takes into account only true paths.

While various conditions have been proposed for characterizing a path actually responsible for circuit delay (also known as a true path), it was only recently that a correct necessary and sufficient condition was proposed. This was in a paper entitled "Delay Computation in Combinational Circuits: Theory and Algorithms", by Devadas, Keutzer and Malik, in the Proceedings of the International Conference on Computer-Aided Design (November 1991). The application of this condition, one path at a time, is not generally feasible because of the large number of long paths in a typical circuit. It was the extension of this condition in the paper to characterize sets of paths responsible for circuit delay that made its use practical. In that paper, a relationship was established between the truth or falsity of the set of longest paths and the testability of an appropriate multiple fault in the Equivalent Normal Form (ENF) representation of the circuit. The ENF of a circuit is a two-level representation that represents the logic function computed by the multi-level circuit while retaining path information. Since the ENF is exponentially larger than the multi-level representation this technique cannot directly be used in practice. To overcome this, it was then shown how test generation for the multiple fault could be performed on the original circuit by taking into consideration timing information during test generation. This approach was called timed test generation, and the associated calculus was called timed D-calculus.

There are some drawbacks associated with timed test generation:

In particular, Automatic Test Pattern Generators (ATPG) cannot be used directly for timed test generation. Considerable modification has to be performed to the basic routines like backward/forward implication and backtrace in the ATPG. The specifics of the modifications are intertwined into the details of the ATPG algorithm, and are therefore non-trivial.

Additionally, timing information of each error value at the input of the gate needs to be taken into account while evaluating a fanout edge of the gate. This adds considerable complexity to error value propagation.

Moreover, unlike in conventional stuck-fault test generation, when an error value has to be propagated across a gate, the evaluation of each fanout edge has to be performed separately. Since an error value may have to be propagated across a gate a large number of times, in timed test generation considerable additional computation is required over conventional test generation.

Finally, the extension of times test generation to handle complex gates is non-trivial.

The invention provides a technique which is relatively free of these problems.

The present invention seeks to avoid the need for timed test generation in timing analysis of combinational logic circuits and its various complexities. In particular, the invention aims to permit the use simply of unmodified conventional Automatic Test Pattern Generation (ATPG) for functional timing analysis.

Basically, the invention involves transforming the circuit on which timing analysis is to be performed to a functionally equivalent circuit having the same number of levels of gates, such that timing analysis on the original circuit can be performed by performing unmodified conventional test pattern generation on the transformed circuit.

To this end, the invention involves first modifying for test purposes in the light of timing information, the original circuit into a transformed but functionally equivalent circuit in which all the paths beginning at a primary input fanout point are all either of length equal to or greater than .delta., or all of length less than .delta.. Such a circuit is said to be .delta. path disjoint for the delay value .delta..

Any circuit can be transformed to a functionally equivalent .delta. path disjoint circuit by a simple topological transformation, as will be discussed hereinafter. Then, additionally, the resulting circuit is modified further to propagate all inverters to primary inputs of the circuit. The, as the next step of the novel testing process there is performed a conventional multifault test on all primary input fanouts from which all paths have a length equal to or greater than .delta.. If no test is found, the value of .delta. is reduced by a unit time and the process repeated until a test is found.

The invention is based on our discovery that there exists a true path of length equal to or greater than .delta. if, and only if, there exists a test for a multiple fault consisting of all zeroes or all ones on the first wires of the paths of length equal to or greater than .delta. in the transformed circuit. In particular, we find it unnecessary to see if there exists a test for multiple faults including both some ones and some zeroes on the first wires of paths length equal to or greater than .delta. in the transformed circuit. Since in complex circuits there generally are many paths that need testing, this factor results in considerable simplification and makes practical a technique that might otherwise usually be impractical.

FIG. 1 shows in schematic form a circuit that will be used in the discussion as an example of a circuit that includes a false path.

FIG. 2 illustrates how an inverter in an output may be pushed to a primary input, a technique used in the invention, and

FIG. 3 is a flow chart of the basic steps of the process of the invention.

It will be helpful to the understanding of the invention first to discuss the following material on false paths.

Informally, a path is an alternating sequence of gates and edges in a circuit. False paths in combinational logic circuits have been studied extensively in recent years. These paths are never exercised during the operation of the circuit due to the logical functionality and delay values of the circuit components.

The exemplary circuit in FIG. 1 will serve to illustrate the notion of false paths as well as their removal in combinational circuits. As shown, the circuit 10 includes a pair of buffers 11 and 12 whose inputs are supplied via terminals a and b, respectively and whose outputs are supplied to the two input terminals of AND gate 13. The output of buffer 12 is also applied to one input of OR gate 14 whose other input is supplied by the output of the AND date 13. The two output terminals 01 and 02 are connected to the outputs of the AND fate 13 and OR gate 14, respectively. The integers inside the gates in this circuit represent the delays of the gates. We will consider the floating mode operation of the circuit. In this mode, the state of the circuit is considered to be unknown when a given input vector is applied. This is a pessimistic assumption; it does not underestimate the length of the longest true path. In addition, we allow for monotone speedup, i.e. the analysis remains valid even when one or more gates in the circuit speed up to switch faster than their specified delay values. In this context a path is false when for each primary input vector v one of the following two things happens:

1. At the inputs to some gate along the path in question, the signal value on the path presents a non-controlling value while an off-path signal (also referred to as a side-input) presents a controlling value. Thus, the off-path signal controls the output. A controlling value for a gate is a value that determines the output value for a gate independent of the other inputs to a gate, for example 0 for an AND gate. A non-controlling value cannot determine the output value by itself, for example, 1 for an AND gate.

2. Both the on-path signal and the off-path signal present controlling values, but the off-path signal presents the controlling value first (this is referred to as an early input), thereby determining the output of the gate.

FIG. 1 illustrates both these conditions. Consider the path of length 4 from a to o2. Consider all possible assignments to a and b.

Thus, this path is false.

It can be shown that if all paths of length greater than .delta. are false in a circuit, then these paths can be removed from the circuit while preserving its logical functionality and guaranteeing that its true delay does not increase. This invention is not particularly concerned with the removal of false paths. The sole purpose of introducing this discussion is to introduce the notion of .delta. path disjoint circuits.

The following characterization of true paths was previously developed. For a path .pi. to be true, it is necessary and sufficient that there exist an input vector such that for every gate g along the .pi.,

1. if all inputs to g have a non-controlling value, then .pi. is the last one to present the non-controlling value, or

2. if there is even one controlling value at the inputs to g, then .pi. is the first one to provide the controlling value.

It is also important to understand what is meant by timed-test generation, and this concept will be described with reference to an original circuit 20 and its functionally equivalent, transformed version 21, both shown in FIG. 2. Circuit 20 includes the AND gate 22, one input of which is supplied via input terminal w and the other via input terminal x by way of the inverter 23. The output of the AND gate 22 is supplied directly to output terminal y and by way of inverter 24 to the output terminal z.

Timed-test generation is used to answer the question: Is there a single path of length at least .delta. that is true? This question normally is answered separately for the rising and falling delays. We consider only the rising delay, the falling delay can be handled similarly.

We will demonstrate timed test generation on a transformed circuit 21 obtained from the original circuit 20 as follows: circuit 21 is obtained from circuit 20 by migrating all inverters to the primary inputs. The inverter at the output of a gate may be moved to the input by using DeMorgan's laws of complementation. Thus, all the inverters may be moved to the primary inputs starting at the primary outputs and recursively applying this procedure to all gates in the circuit. Moreover, a gate that is used in both inverting and non-inverting phase may need to be duplicated. As seen in FIG. 2, the circuit portion involving output z needs to be transformed. In particular, now the input terminal x directly supplies one input to OR gate 34 and the input terminal w supplies the other input terminal of gate 34 by way of the inverter 35. The portion of circuit 20 involving output y remains as before so the same reference numerals are maintained. Since each gate is duplicated no more than once, 21 is at most twice the size of 20. The sensitization conditions on paths in 21 are the same as those for the corresponding paths in 20. It is to be understood that 21 is being used only for purpose of exposition and, as will be shown later, timed test generation may be done directly on 20 without need for constructing 21.

For each edge i in 21 we determine max.sup.t (e.sub.i), which is the length of the longest path starting at the source of edge i and ending at some sink of the circuit DAG, i.e. at some primary output.

There is at least one true path of length at least .delta. in the circuit, if and only if, (iff() the multifault {e.sub.i stuck--at--0} can be tested using timed test generation. Here e.sub.i is the fanout edge of a primary input (after any possible inverters) for which max.sup.t (e.sub.i).gtoreq..delta.. The goal of test generation is to propagate a D to the output of the circuit along only paths of length at least .delta.. For each D that we are trying to propagate forward through the circuit there is an associated value D.s, which captures the timing information associated with the error value. The semantics of D.s will be described shortly, at this point it is sufficient to note that for each D placed on the fanout edges of the primary inputs, D.s=0.

There is a difference in the testing of this multifault and classical stuck-at-fault testing in terms of how a fault effect is propagated through a gate. We now examine this difference.

Evaluation of the output of a gate, g, given its inputs, is done in a manner similar to the standard D-calculus with two differences. The first is that the evaluation for each fanout edge, e.sub.i, of g is done separately. Thus, the different fanout edges may evaluate to different values. The second is that the timing information of each error value E (D or D), i.e. E.s is taken into account while evaluating the value for e.sub.i.

The following cases describe the evaluation of the value on e.sub.i, given the values on the inputs to g for some input vector v.

1. There is a controlling value at the input of g: This forces e.sub.i to the corresponding controlled value.

2. Each input of g has a non-controlling value on it: e.sub.i takes on the non-controlled value.

3. Some set of inputs have an error value on them, some (possibly none) have non-controlling values: Note that D and D cannot be present on the inputs of g since we only propagate either D's or D's at a time, but not both. Let E.sub.k be the error values on the inputs and d(g) be the delay of gate g. Let s be as given by the following table:

(a) If s+d(g)+max.sup.t (e.sub.i).gtoreq..delta., then e.sub.i evaluates to the error value E with E.s=s.

(b) If s+d(g)+max.sup.t (e.sub.i)<.delta., then e.sub.i evaluates to the error free value, i.e., 1 for a D and 0 for a D.

Timed test generation can be applied directly on C without needing to generate C' by doing some additional bookkeeping that keeps track of the parity of inversions seen by the error value in the circuit but these are not being discussed in detail herein.

The invention is a confluence of the results on the characterization of sets of true/false paths in the manner described in the previously identified paper of Devadas, Keutzer and Malik, and results on the removal of false paths. An efficient algorithm for minimally transforming a circuit in order to remove long false paths was provided in a paper by A. Saladanha, R. K. Brayton, and A. Sangiovanni-Vincentelli entitled "Circuit structure relations to redundancy and delay: The KMS algorithm revisited." In The Proceedings of the Design Automation Conference, pages 245-252, June 1992. Our invention is the discovery that the same transformation, in conjunction with a test pattern generator for stuck faults, can be used for functional timing analysis. The motivation for this approach is from the results on the characterization of sets of true/false paths in the paper of Devadas, Keutzer and Malik.

We will now describe in detail our novel method for true-delay computation. The goal of the method is to find the true delay of the circuit. It begins with some assumed delay value .delta., either provided by the user, or obtained by computing the length of the topologically longest path in the circuit. For computer implementation the circuit diagrams in its synthesized form is transferred to a computer format by any of the techniques known for such purposes, such as BLIF (Berkeley Logic Interface Format) and then stored in this format in the computer that is to do the timing analysis.

The method basically operates in two steps. In the first step, given the input circuit C and a delay value of .delta., C is transformed by a computer into the circuit C.sup..delta.. C.sup..delta. satisfies the following property: Given a gate G in C.sup..delta., the set of all paths, ={.pi..sub.i }, from the primary inputs of C.sup..delta. to the output of G, and the set of all paths .GAMMA.={.gamma..sub.j }, from the output of G to primary outputs of C.sup..delta.. The path, .pi..sub.i .gamma..sub.j corresponds to the concatenation of the paths .pi..sub.i and .gamma..sub.j. Therefore, a path .pi..sub.i .gamma..sub.j, .pi..sub.i .epsilon. and .gamma..sub.j .epsilon..GAMMA., is a path from a primary input to a primary output. For each .pi..sub.i .epsilon. , consider the set of paths, S.sub..pi..sbsb.i .gamma..sub.j, .gamma..sub.j .epsilon..GAMMA.}, formed by concatenating the chosen value of .pi..sub.i with all the paths in .GAMMA.. C.sup..delta. satisfies the property that for each S.sub..pi..sbsb.i, there is no pair of paths in S.sub..pi..sbsb.i such that one of the paths in the pair is of length .gtoreq..delta. and the other path in the pair is <.delta.. A circuit satisfying this property is called an .delta. path disjoint circuit in the Saldanha, Brayton and Sanvioganni-Vincentelli paper mentioned earlier. An efficient algorithm for making a circuit .delta. path disjoint was given in such paper. The same algorithm advantageously is used in the invention. A detailed description of the algorithm is provided later. In addition to being .delta. path disjoint, C.sup..delta. also satisfies the property that all inverters have been pushed to the primary inputs. The first step of the algorithm returns a set (called .delta..sub.-- leaves) of wires in C.sup..delta. which correspond to the first edges of all the paths of length .gtoreq..delta.. If a primary input is used by a path in the inverted phase, the corresponding wire in .delta..sub.-- leaves is the inverter output, otherwise it is the fanout point of a primary input. There is no inversion between a wire in .delta..sub.-- leaves and any primary output.

In practice, there is a small area penalty associated with making the circuit .delta. path disjoint. In addition, pushing the inverters can cause some gates in the circuit to be duplicated. However the increase in the size in C.sup..delta. is manageable.

In the second step of the method, a multiple stuck-at fault (m.sub.1), consisting of the wires in .delta..sub.-- leaves stuck-at one, is injected on the wires in .delta..sub.-- leaves and test generation is attempted for it. If the fault is found to be redundant, test generation is attempted for a second multiple fault (m.sub.2) obtained by inverting the polarities of all the single faults contained in m.sub.1. If m.sub.2 is also redundant, then we conclude that the delay of the circuit is <.delta.. Both the steps above are now repeated for a lower value of .delta.. The algorithm stops when a test is found for either m.sub.1 or m.sub.2.

Note that the test generation part of the method (i.e. the part of the method which does a functional analysis of the circuit) is completely decoupled from the timing-dependent part of the method. This fact makes it possible to use unmodified conventional ATPG in our timing analysis algorithm.

C-like pseudo code for the method is given below:

FIG. 3 depicts the basic steps of the method in flow chart form. As shown, step 41 involves an initial selection f a suitable .delta. as a starting point. Normally, the computer would select for this value the delay of the longest path in the circuit under test, using any standard known process for determining such value. Then the computer would transform the original circuit to the modified form appropriate for the value of .delta. chosen following the rules discussed, as indicated by step 42. This is followed by the multifault testing described to see if a valid test exists for the particular value of .delta., shown as step 43. If a valid test is found, the delay of the original circuit is .delta. as indicated by step 44. If no valid test is found the value of .delta. is decremented in step 45 by some amount, and the new value of .delta. is fed back to step 42 for use in a new transformation of the circuit in view of the new value of .delta., and steps 43 and 45 repeated until .delta. has been reduced sufficiently that a valid test is found and a final .delta. is determined.