Method for Performing Timing Analysis of a Clock Circuit

This invention relates to a method for static timing analysis of integrated circuits, and more particularly, to a method for determining the timing of an output signal of a clock circuit.

A wide variety of design verification tools are required to produce a working integrated circuit from a functional specification. These tools analyze different parameters of a circuit design to insure that the circuit will function properly after it is fabricated. One important set of verification tools includes timing analysis tools which are widely used to predict the performance of very large scale integrated (VLSI) designs. Such timing analysis tools may be either static or dynamic. Dynamic timing analysis tools provide the most detailed and accurate information obtainable concerning the performance of a circuit being simulated. This type of timing analysis is often generated through simulation of a circuit model by simulation programs which operate at the transistor level. Examples of such circuit simulation programs are SPICE by University of California at Berkeley and ASTAP by IBM Corporation. These dynamic timing analysis programs typically operate by solving matrix equations relating to the circuit parameters such as voltages, currents, and resistances. Additionally, such circuit simulation approaches to performance analysis are pattern dependent, or stated another way, the possible paths and the delays associated therewith depend upon a state of a controlling mechanism or machine of the circuit. Thus, the result of a dynamic timing analysis depends on the particular test pattern, or vector, applied to the circuit.

While such circuit simulation programs and dynamic timing analysis tools provide high accuracy, long simulation times are required because a large number of patterns must be simulated because the best and worst case patterns are not known before the simulation occurs. In fact, a number of simulations which must be performed is proportional to 2.sup.n, where "n" is a number of inputs to the circuit being simulated. Thus, for circuits having a large number of inputs, dynamic timing analysis is not always practical.

Static timing analysis tools are also widely used to predict the performance of VLSI designs. Static timing analyzers are often used on very large designs for which exhaustive dynamic timing analysis is impossible or impractical due to the number of patterns required to perform the analysis. In static timing analysis, it is assumed that each signal being analyzed switches independently in each cycle of the state machine controlling that circuit. Furthermore, in static timing analysis, only the best and worst possible rising and falling times are computed for each signal in the circuit. The best and worst possible rising and falling times are typically determined in a single pass through a topologically sorted circuit. When referring to a topologically sorted circuit, it should be noted that a signal time associated with each point in the circuit being tested is determined in a sequential nature. Therefore, the signal time associated with the input of a first subcircuit whose output will be propagated to the input of a second subcircuit must be determined before the signal time associated with the input of the second subcircuit is calculated. Typical static analysis methods are described in "Timing Analysis of Computer Hardware" by Robert B. Hitchcock, Sr., et al., IBM J. Res. Develop., Vol. 26, No. 1, pp. 100-105 (1982), which is incorporated by reference herein.

Static timing analysis may be applied to a simple two input NAND circuit 100 such as that illustrated in FIG. 1. Typically, cells such as the one shown in FIG. 1 are kept in cell libraries and may be used as building blocks by designers to construct larger and more complex integrated circuits. Typically, for each cell in a cell library, a dynamic timing analysis has already been performed and the timing parameters of the cell are maintained as part of the cell description. In the example shown, NAND circuit 100 is known to have a minimum delay of 30 picoseconds, and a maximum delay of 40 picoseconds, for a rising edge received at an inputs A and B. Thus, if it is known that a rising edge will be received at input A at sometime between 10 and 20 picoseconds measured from an initial time p0, then the earliest output will be a falling edge at output C at 40 picoseconds and a latest falling edge at output C at 60 picoseconds from time p0. Since in any given cycle a data signal on input B can be either high or low, input B is ignored when computing the delay from input A to the output C. Thus, the timing computed for the circuit is described in terms of minimum and maximum signal switching times and is independent of the actual pattern received at the inputs.

Transistor-level timing analyzers eliminate the need for predefined cell libraries by decomposing circuits into channel-connected components and automatically computing the delay of each component. Such channel connected components are non-intersecting groups of transistors which are connected by source and drain terminals to one another and to supply and ground nets, or connections. Each channel connect component can be analyzed independently to compute the worst case delays from each input to each output for both rising and falling signals.

In the traditional transistor-level static timing analysis approach, each pull-up and pull-down path in a clock network is treated independently. Therefore, when a traditional approach is used to evaluate a delay in a clock driver circuit with parallel drivers, the delays will be overestimated by a factor which is proportional to the number of parallel drivers. An amount of time in which the delay and signal transition times are overestimated is generally by a factor proportional to a number of parallel drivers. For example, in a network which is driven by eight identical parallel inverters, the delay will be overestimated by a factor of eight.

A typical clock driver circuit is illustrated in FIG. 5. In clock driver circuit 500 of FIG. 5, a clock input signal is buffered through a "tree" of inverters and reconverge in a single grid which is driven by a large number of parallel inverters. This grid may be distributed directly to latches and dynamic logic circuitry or buffered again through another grid to another set of parallel inverters.

Details of prior art delay calculation techniques for transistor-level circuits are well-known to those with skill in the art. For additional information, refer to "Timing Analysis and Performance Improvement of MOS VLSI Designs," by Jouppi, IEEE Transactions on Computer-Aided Design, Vol. 6, No. 4 (1987), and "Crystal: A Timing Analyzer for NMOS VLSI Circuits," by Ousterhout, Proc. 3rd Cal. Tech. VLSI Conf., Computer Science Press, pp. 57-69 (1983), each of which is incorporated herein by reference.

The previously mentioned needs are fulfilled with the present invention. Accordingly, there is provided, in a first form, a method for performing a timing analysis of a clock circuit wherein a plurality of input signals are received at a node of the clock circuit. A phase corresponding to a first one of the plurality of input signals of the node is determined. A first portion of the clock circuit which is enabled and a second portion of the clock circuit which is disabled when the phase corresponding to the first one of the plurality of input signals is in a first logic state is identified. A generated signal is provided in response to the first portion and the second portion of the clock circuit. The generated signal selectively stimulates the node of the clock circuit to transition from a second logic state to a third logic state.

There is provided, in a second form, a data processing system. The data processing system includes a memory for storing a model of a clock circuit and a data processor for determining a phase corresponding to a first input signal to a first one of a plurality of nodes of the model of the clock circuit. The data processor identifies a portion of the clock circuit which is enabled when a phase corresponding to the first input signal is in a first logic state and provides a generated signal in response to the portion of the clock circuit to selectively stimulate the first one of the plurality of nodes of the model of the clock circuit to transition from a second logic state to a third logic state.

These and other features, and advantages, will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawings. It is important to note the drawings are not intended to represent the only form of the invention.

The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention.

For a more complete understanding of the present invention, and the advantages thereof, reference is now made to the following descriptions taken in conjunction with the accompanying drawings, in which:

FIG. 1 is a diagram illustrating a logic circuit which is analyzed using conventional static timing analysis techniques;

FIG. 2 illustrates, in block diagram form, a data processing system which implements one embodiment of the present invention;

FIG. 3 illustrates, in flow diagram form, a method for performing a static timing analysis of a clock-shaping circuit in accordance with one embodiment of the present invention;

FIG. 4 illustrates, in flow diagram form, a step of computing and propagating delays in accordance with the methodology of the present invention as illustrated in FIG. 3;

FIG. 5 illustrates, in circuit diagram form, one embodiment of a clock driver circuit such as that analyzed in accordance with the method of the present invention;

FIG. 6 illustrates, in timing diagram form, a clock signal associated with a phase table of the present invention; and

FIG. 7 illustrates, in block diagram form, an embodiment of a data processing system for implementing the present invention.

The present invention implements a methodology for accurately and precisely computing the output signal transition times in a clock distribution, or buffering, network of a data processing system. Specifically, the methodology of the present invention may be implemented in transistor-level static timing analysis tools which compute delays of blocks or subcircuits that correspond to channel-connected components of transistors. In the present invention, the static timing analysis techniques traditionally implemented are modified to more accurately compute signal delays and transition times at the outputs of a clock distribution network circuit. The operation and implementation of the present invention will subsequently be described in greater detail.

During a following description of the implementation of the invention, the terms "assert" and "negate" and various grammatical forms thereof, are used to avoid confusion when dealing with a mixture of "active high" and "active low" logic signals. "Assert" is used to refer to the rendering of a logic signal or register bit into its active, or logically true state. "Negate" is used to refer to the rendering of a logic signal or register bit into its inactive or logically false state.

In the following description, numerous specific details are set forth to provide a thorough understanding of the present invention. However, it will be obvious to those skilled in the art that the present invention may be practiced without such specific details. In other instances, well-known circuits have been shown in block diagram form in order not to obscure the present invention in unnecessary detail. For the most part, details concerning timing considerations and the like have been omitted inasmuch as such details are not necessary to obtain a complete understanding of the present invention and are within the skills of persons of ordinary skill in the relevant art.

Refer now to the drawings wherein depicted elements are not necessarily shown to scale and wherein like or similar elements are designated by the same reference numeral through the several views.

FIG. 2 is a block diagram illustrating a data processing system in which the present invention may be used. The data processing system of FIG. 2 comprises a terminal 202, an input device 204, and a data processing system 300. When utilizing the present invention, a circuit design engineer may access the static timing analysis program stored in data processing system 300 using both terminal 202 and input device 204. Use of terminal 202 and input device 204 to access a static timing analysis is well-known to those skilled in the data processing art and will not be described in greater detail herein.

FIG. 3 is a block diagram illustrating the steps implemented in the performance of an improved static timing analysis method according to the present invention. Initially, a logic model 310 primary output (PO) required times and assertion data 314, which comprise primary input (PI) arrival times and clock phase definitions for all clocks, are combined to establish a timer model load in block 316. The timer model load 316 constructs a graph-like representation of a circuit being tested using inputs from logic model 310 and assertion data 314. With phase information from assertion data 314, data processing system 300 constructs a phase table in block 318. An example of a phase table is illustrated in Table 1.

The clocks associated with one embodiment of the present invention are illustrated in FIG. 6.

The phase table of Table 1 includes the set of tags used to label the phases of signal transitions. The phase table is used to relate those tags to a type of a signal (clock, static data, etc.) and an idealized "base time" for the signal switching event. The base time of an event can be interpreted as the time that the event would occur if all delays in the circuit being evaluated were zero. Base times are specified in a global frame of reference. Since the clock circuit is assumed to be controlled by periodic signals, a period for each phase is also stored in the phase table with its associated phase tag. Creation and use of such phase tables is described in greater detail in U.S. Pat. No. 5,210,700 by David Tom, assigned to International Business Machines Corporation, and filed on May 11, 1993, which is incorporated by reference herein.

Once the phase table has been constructed in block 318, data processing system 300 assigns the primary input arrival times (AT) assertions in block 320. Each arrival time assertion specifies both an actual signal event time and the phase associated with that event. Subsequently, data processing system 300 propagates the phases through a model of the circuit to label each point in the circuit as carrying either clock or data signals. This propagation is guided by a set of rules, such as those listed below:

If a subcircuit has only data inputs, then its output is a data signal.

If a subcircuit has clock inputs and is a latch, then its output is a data signal.

If a subcircuit has clock inputs and is a dynamic logic gate, then its output is a data signal.

If a subcircuit has clock inputs and is a static gate, then its output is a data signal.

Additional rules may exist, and if necessary, users can provide manual overrides to the normal labelling.

It should be noted that this set of rules is one embodiment which may be implemented and other embodiments may also be used in the present embodiment of the invention.

Afterwards, in block 324, data processing system 300 computes delays and arrival times for all points in the circuit starting from the times given in the user-specified arrival time assertions. This results in all points in the timing model having valid signal times and associated phase tags. This step will subsequently be described in greater detail.

In block 326, data processing system 300 computes required times and slacks. It should be noted that slacks are the differences between a signal event's required time and its actual arrival time. In establishing the selection of a test edge for each data test point, data processing system 300 extracts the necessary data records for the test from required time assertions and timing constraints that are generated upon recognition of specific circuit structures. For the data test point, data processing system 300 extracts a reference point and a reference signal level. Furthermore, data processing system 300 then obtains the test signal levels to be tested against the reference signal level. Data processing system 300 then extracts a signal time and a phase record index from the reference point. From the phase table, data processing system 300 extracts the phase time for the reference edge. For the test point and test signal level, data processing system 300 extracts the test signal time and phase record index from the test point. Next, from the phase table, data processing system 300 extracts the phase time for the test edge. Finally, data processing system determines an amount of time to adjust the reference signal to account for the periodicity of the controlling clock signals.

To implement step 324 of the flow chart of FIG. 3, the present invention implements a methodology which takes advantage of the fact that certain signals, such as clock signals, have predictable behavior which may be denoted in the timing model utilized to perform the static timing analysis. To indicate whether a signal has a predictable behavior, such as the periodicity exhibited by clock signals, a special designation is used to indicate which nodes of a circuit being analyzed are clock nodes. To determine whether or not a node is a clock node or a data node, heuristic and user-provided rules are selectively used in a preprocessing step.

The distinction between data and clock nodes is important because of the assumptions made about each type of node. Signals on data nodes may or may not switch in a given cycle. Conversely, signals on a clock node are expected to switch in every cycle. In the present invention, for each channel-connected component output, or node, that is labeled as a clock, a delay is calculated assuming that all clock inputs switch at the latest or earliest times in order to obtain the latest or earliest output signal time, respectively. When this delay calculation is performed by circuit simulation or transient analysis, the analysis will include an actual logical function of the channel-connected component which reflects the interaction among input signals.

For example, in the inverters 530-544 of the clock distribution circuit 500 of FIG. 5, a delay between the provision of an input to inverters 502 and 504 and an output being inverters 530-544 will be computed by assuming that all pull-up or pull-down paths act in parallel. The computation of the delay may be computed using any one of several well-known delay calculation techniques. For example, one common transistor level delay calculation technique treats all "on" transistors as linear resistors and all "off" transistors as open circuits. The delay is computed as a step response of the resulting RC (resistor-capacitor) network. When the RC network is a tree, a simple measure such as the Elmore delay may be used. For more complex circuits, or for higher-order approximations, a network response may be computed using Asymptotic Waveform Evaluation techniques such as those implemented in the RICE tool kit. For more information on such techniques, refer to "RICE: Rapid Interconnect Circuit Evaluator," by Curtis L. Ratzlaff, et al., and published at the 28th ACM/IEEE Design Automation Conference, Paper 33.1, pp. 555-560, which is incorporated by reference herein.

Another possible technique for transistor-level delay calculation relies on circuit simulation to directly compute the output response as a function of the input signals. Thus, to implement the methodology of the present invention, after the clock nodes are identified, a reference table is accessed from a memory of data processing system 300 (not illustrated herein) to determine event times. Such event times include properties of the identified clock nodes in ideal situations. As previously described, the properties of the identified clock nodes indicate a rise time and a fall time, as well as a frequency of the clock signal provided thereto. In the alternative, a circuit simulator may be used to determine event times for each gate implemented in the circuit being simulated. In this case, correct input patterns must be provided to the circuit simulator. By utilizing the recognition that clock signals are periodic in nature, a number of input patterns required to test each logic gate is reduced and a correct result may be efficiently calculated using circuit simulation procedures.

In either of the above implementations, the steps of the flow chart illustrated FIG. 4 are executed. Each of those steps will subsequently be described in greater detail.

To compute the arrival time at a node of a circuit being simulated, it must first be determined in step 404 whether the node is a clock node or a data node. If the node is a data node, a data node analysis is performed in step 406. Performance of this analysis will not be described in detail herein. However, it should be noted that this analysis is done primarily in a pattern-independent way that assumes that data signals can have arbitrary values and computes delays assuming worst-case assignments to these data signals. The analysis for a clock node computes one latest (and possibly also one earliest) transition for each clock phase associated with the node. To do this, the phases of all input signals to the node must be collected from memory in a step 408. As previously mentioned, the memory which stores such phases is included in data processing system 300, but not illustrated herein.

In the present invention, the clock phase tags which are associated with each of the clock nodes are analyzed to determine whether or not the inverters of the clock distribution network of FIG. 5 are going to work together. Thus, when the present invention is applied, all inputs with the same clock phase tag are switched at the same time during simulation to determine a best case delay time period. Similarly, for the worst-case response time, the worst-case input switching times are used.

Next, in step 410, a pattern for simulation is generated for each input clock phase This step is performed by applying an input signal with a direction, arrival time, and slope which matches a transition on the input of the same phase. Each clock input is stimulated with an input signal having a direction (rising or falling), arrival time, and transition time which matches a transition on the corresponding input having the matching phase. Any data inputs are set to constant noncontrolling values (a noncontrolling value is a value of an input signal which does not force an output to have a constant value).

After a first pattern has been generated for a first input clock phase, the circuit being analyzed is simulated with a generated pattern in a step 412. A result is subsequently measured on the node being tested in step 414. The result indicates a delay associated with the provision of the input to the node and an output generated by the circuit under test. If the result measured in step 414 is worse than all previous transitions on the node for the specific phase, direction, and mode (early or late), a memory location which corresponds to a delay associated with the present circuit being tested is updated with the new pattern. Each of steps 410 through 416 is repeated for all nodes included in a circuit being analyzed. If all the nodes have been tested, a delay associated with the circuit being simulated has been determined and step 324 of the general flow illustrated in FIG. 3 has been completed. Subsequently, a next circuit is analyzed using this procedure.

It should be noted that the present invention may be implemented as a computer program and executed on a data processing system such as that illustrated in FIG. 7. While FIG. 2 provides a basic system for implementing the present invention, FIG. 7 illustrates an alternate embodiment.

Referring first to FIG. 7, an example is shown of a data processing system 700 which may be used for the invention. The system has a central processing unit (CPU) 710, such as a Power PC microprocessor ("PowerPC" is a trademark of IBM Corporation) according to "The PowerPC Architecture: A Specification for a New Family of RISC Processors", 2nd edition, 1994, Cathy May, et al. Ed., which is hereby incorporated herein by reference. A more specific implementation of a PowerPC microprocessor is described in the "PowerPC 604 RISC Microprocessor User's Manual", 1994, IBM Corporation, which hereby incorporated herein by reference. The history buffer (not shown) of the present invention is included in CPU 710. The CPU 710 is coupled to various other components by system bus 712. Read only memory ("ROM") 716 is coupled to the system bus 712 and includes a basic input/output system ("BIOS") that controls certain basic functions of the data processing system 700. Random access memory ("RAM") 714, I/O adapter 718, and communications adapter 734 are also coupled to the system bus 712. I/O adapter 718 may be a small computer system interface ("SCSI") adapter that communicates with a disk storage device 720. Communications adapter 734 interconnects bus 712 with an outside network enabling the data processing system to communication with other such systems. Input/Output devices are also connected to system bus 712 via user interface adapter 722 and display adapter 736. Keyboard 724, track ball 732, mouse 726 and speaker 728 are all interconnected to bus 712 via user interface adapter 722. Display monitor 738 is connected to system bus 712 by display adapter 736. In this manner, a user is capable of inputting to the system throughout the keyboard 724, trackball 732 or mouse 726 and receiving output from the system via speaker 728 and display 738. Additionally, an operating system such as AIX ("AIX" is a trademark of the IBM Corporation) is used to coordinate the functions of the various components shown in FIG. 7.

Preferred implementations of the invention include implementations as a computer system programmed to execute the method or methods described herein, and as a computer program product. According to the computer system implementation, sets of instructions for executing the method or methods are resident in the random access memory 714 of one or more computer systems configured generally as described above. Until required by the computer system, the set of instructions may be stored as a computer program product in another computer memory, for example, in disk drive 720 (which may include a removable memory such as an optical disk or floppy disk for eventual use in the disk drive 720). Further, the computer program product can also be stored at another computer and transmitted when desired to the user's work station by a network or by an external network such as the Internet. One skilled in the art would appreciate that the physical storage of the sets of instructions physically changes the medium upon which it is stored so that the medium carries computer readable information. The changes may be electrical, magnetic, chemical or some other physical change. While it is convenient to describe the invention in terms of instructions, symbols, characters, or the like, the reader should remember that all of these and similar terms should be associated with the appropriate physical elements.

Note that the invention describes terms such as comparing, validating, selecting or other terms that could be associated with a human operator. However, for at least a number of the operations described herein which form part of the present invention, no action by a human operator is desirable. The operations described are, in large part, machine operations processing electrical signals to generate other electrical signals.

The implementation of the invention described herein is provided by way of example only. However, many other implementations may exist for executing the function described herein. For example, rather than using circuit simulation to compute delays of circuit stages, the delays could be computed using one of the RC circuit analysis techniques previously mentioned.

Furthermore, while there have been described herein the principles of the invention, it is to be clearly understood to those skilled in the art that this description is made only by way of example and not as a limitation to the scope of the invention. Accordingly, it is intended, by the appended claims, to cover all modifications of the invention which fall within the true spirit and scope of the invention. Furthermore, it is to be noted that although the present invention and its advantages have been described in detail, it should be understood that various changes, substitutions, and alterations can be made herein without departing from the spirit and scope of the invention as defined by the appended claims.