Abstract:
Disclosed are novel methods and apparatus for efficiently providing critical path analysis of a design. In an embodiment, an apparatus disclosed can assist in creating a single critical path schematic which can be used to simulate both rising and falling edge delays. This saves time as only one schematic and one simulation is required instead of the two generally required.

Description:
[0001]    This application is a continuation application of Ser. No. 10/062,591, filed on Jan. 31, 2002, entitled “Method and Apparatus for Improving Critical Path Analysis Using Gate Delay”, and claims priority therefrom. 
     
    
     
       FIELD OF INVENTION  
         [0002]    The subject of this application relates generally to the field of integrated circuit (IC) design and, more particularly, to reducing critical path schematics apparatus and methods.  
         BACKGROUND OF INVENTION  
         [0003]    Critical path analysis is one of the most important stages of circuit design, in part, because it can help determine the speed at which a circuit may be run. As circuits are quickly becoming more complicated, critical path analysis, as with many other circuit analysis techniques, is becoming increasingly computerized for efficiency purposes.  
           [0004]    Also, as circuits grow in complexity (sometimes reaching thousands and sometimes millions of gates), it is imperative to decrease the number of computer resources and hours spent on evaluating these designs. This is extremely important with respect to critical path analysis. Especially, in the current climate of competition, it is imperative that the speed of a circuit be determined before investing substantial amounts of money on making and marketing a device that may be dwarfed by solutions from competitors.  
           [0005]    Accordingly, critical path analysis is not only a tool for engineers to determine if their circuit design works, but also a tool for a marketing and finance division of a company to determine whether a given circuit design is worthy of pursuing.  
           [0006]    Generally, circuit designers use a software program, such as HSpice provided by Avant Corporation of Fremont, California, to simulate the critical path schematics for their designs. Since the logic gates have different delays through them for rising and falling output nodes, the critical path of a circuit would have to be simulated for both rising and falling edges of a final output node. This requires creating at least two different schematics and simulations to calculate these delays.  
           [0007]    After running these simulations, the higher of the rising or falling delays represents the worst-case delay. And, the worst-case delay in turn defines the final delay of the circuit. The final delay indicates the maximum frequency at which a design may safely run. Accordingly, it is important to set up these simulations carefully and efficiently.  
         SUMMARY OF INVENTION  
         [0008]    The present invention, which may be used/set up on a general-purpose digital computer, includes methods and apparatus to provide efficient critical path analysis of a design, utilizing single or multiple processors.  
           [0009]    In an embodiment, the techniques described herein disclose two devices that can be used to simulate both rising and falling delays through gates in a critical path using only one schematic and, hence, one simulation.  
           [0010]    In another embodiment, an apparatus disclosed may assist in creating a single critical path schematic which can be used to simulate both rising and falling edge delays. This saves time as only one schematic and, hence, one simulation is required instead of the two generally required.  
           [0011]    In yet a different embodiment, a method of efficiently performing critical path analysis is disclosed. The method includes providing a device to assist in determining both rising and falling delays for the critical path analysis of a gate; coupling an input of the device to a controlling input of the gate; coupling an output of the device to a non-controlling input of the gate, the device having an I/O characteristic wherein: signals at both the input and output of the device rise and fall substantially simultaneously on a first edge; and on a remaining edge, a signal at the device output follows one of a rise and a fall of a signal at the device input after a output node delay; and determining the rising and falling delays for the critical path analysis of the gate utilizing the device. 
       
    
    
     BRIEF DESCRIPTION OF DRAWINGS  
       [0012]    The present invention may be better understood and it&#39;s numerous objects, features, and advantages made apparent to those skilled in the art by reference to the accompanying drawings in which:  
         [0013]    [0013]FIG. 1 illustrates an exemplary computer system  100  in which the present invention may be embodied;  
         [0014]    [0014]FIG. 2A illustrates an exemplary configuration of input settings for determining rising and falling delays through a NAND gate;  
         [0015]    [0015]FIG. 2B illustrates an exemplary configuration of input settings for determining rising and falling delays through a NOR gate;  
         [0016]    [0016]FIG. 3A( a ) illustrates an exemplary system  300  utilizing a AND_NC gate  302  in accordance with an embodiment of the present invention;  
         [0017]    [0017]FIG. 3A( b ) illustrates exemplary I/O characteristics of the system  300  of FIG. 3A( a ) in accordance with an embodiment of the present invention;  
         [0018]    [0018]FIG. 3B( a ) illustrates an exemplary system  350  utilizing an OR_NC gate  312  in accordance with an embodiment of the present invention;  
         [0019]    [0019]FIG. 3B( b ) illustrates exemplary I/O characteristics of the system  350  of FIG. 3B( a ) in accordance with an embodiment of the present invention;  
         [0020]    [0020]FIG. 4 illustrates an exemplary schematic for an AND_NC gate in accordance with an embodiment of the present invention;  
         [0021]    [0021]FIG. 5 illustrates an exemplary OR_NC schematic in accordance with an embodiment of the present invention; and  
         [0022]    [0022]FIG. 6 illustrates an exemplary system  600  in accordance with an embodiment of the present invention. 
     
    
       [0023]    The use of the same reference symbols in different drawings indicates similar or identical items.  
       DETAILED DESCRIPTION  
       [0024]    In the following description, numerous details are set forth. It will be apparent, however, to one skilled in the art, that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form, rather than in detail, in order to avoid obscuring the present invention.  
         [0025]    Reference in the specification to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the invention. The appearances of the phrase “in one embodiment” in various places in the specification are not necessarily all referring to the same embodiment.  
         [0026]    [0026]FIG. 1 illustrates an exemplary computer system  100  in which the present invention may be embodied in certain embodiments. The system  100  comprises a central processor  102 , a main memory  104 , an input/output (I/O) controller  106 , a keyboard  108 , a pointing device  110  (e.g., mouse, track ball, pen device, or the like), a display device  112 , a mass storage  114  (e.g., hard disk, optical drive, or the like), and a network interface  118 . Additional input/output devices, such as a printing device  116 , may be included in the system  100  as desired. As illustrated, the various components of the system  100  communicate through a system bus  120  or similar architecture.  
         [0027]    In an embodiment, the computer system  100  includes a Sun Microsystems computer utilizing a SPARC microprocessor available from several vendors (including Sun Microsystems of Palo Alto, Calif.). Those with ordinary skill in the art understand, however, that any type of computer system may be utilized to embody the present invention, including those made by Hewlett Packard of Palo Alto, Calif., and IBM-compatible personal computers utilizing Intel microprocessor, which are available from several vendors (including IBM of Armonk, N.Y.). Also, instead of a single processor, two or more processors (whether on a single chip or on separate chips) can be utilized to provide speedup in operations.  
         [0028]    The network interface  118  provides communication capability with other computer systems on a same local network, on a different network connected via modems and the like to the present network, or to other computers across the Internet. In various embodiments, the network interface  118  can be implemented in Ethernet, Fast Ethernet, wide-area network (WAN), leased line (such as T 1 , T 3 , optical carrier  3  (OC 3 ), and the like), digital subscriber line (DSL and its varieties such as high bit-rate DSL (HDSL), integrated services digital network DSL (IDSL), and the like), time division multiplexing (TDM), asynchronous transfer mode (ATM), satellite, cable modem, and FireWire.  
         [0029]    Moreover, the computer system  100  may utilize operating systems such as Solaris, Windows (and its varieties such as NT, 2000, XP, ME, and the like), HP-UX, Unix, Berkeley software distribution (BSD) Unix, Linux, Apple Unix (AUX), and the like. Also, it is envisioned that in certain embodiments, the computer system  100  is a general purpose computer capable of running any number of applications such as those available from companies including Oracle, Siebel, Unisys, Microsoft, and the like.  
         [0030]    [0030]FIG. 2A illustrates an exemplary configuration of input settings for determining rising and falling delays through a NAND gate  201 . Generally, the input settings for determining the rising and falling delays through a logic gate are different.  
         [0031]    In the figures, the controlling input of each gate is marked with a “c” and the non-controlling input is marked with an “n” symbol. The gate delay is normally evaluated from the controlling input to the output. However, specific combinations may be given at the non-controlling input to evaluate the worst-case delay through the gate.  
         [0032]    In case of a NAND gate (illustrated in FIG. 2A), if there is a rising edge on a controlling input  202 , a substantially simultaneous rising edge is present at a non-controlling input  204  to obtain the worst-case falling delay at an output  206  (FIG. 2A( a )). If there is a falling edge at the controlling input  202 , the non-controlling input  204  is kept at a logic high level to obtain the worst-case rising delay at the output  206  (FIG. 2A( b )).  
         [0033]    [0033]FIG. 2B illustrates an exemplary configuration of input settings for determining rising and falling delays through a NOR gate  211 . NAND and NOR gates are appropriate choices as examples because they are the most basic of the gates that need different input settings for simulating rise and fall delays through them. Other examples of such gates include.  
         [0034]    In case of a NOR gate (illustrated in FIG. 2B), if there is a falling edge on a controlling input  212 , a substantially simultaneous falling edge is present at a non-controlling input  214  to obtain the worst-case rising delay at an output  216  (FIG. 2B( b )). If there is a rising edge at the controlling input  212 , the non-controlling input  214  is kept at a logic low level to obtain the worst-case falling delay at the output  216  (FIG. 2B( a )).  
         [0035]    [0035]FIG. 3A( a ) illustrates an exemplary system  300  utilizing a AND_NC gate  302  in accordance with an embodiment of the present invention. FIG. 3A( b ) illustrates exemplary characteristics of the system  300  of FIG. 3A( a ) in accordance with an embodiment of the present invention.  
         [0036]    In FIG. 3A( a ), the system  300  includes the NAND gate  201  and the AND_NC gate  302 . As illustrated, the AND_NC gate  302  receives the controlling input  202  as I and     —     nc    304  and provides its output O and     —     nc  to the non-controlling input  204  of the NAND gate  201 .  
         [0037]    In FIG. 3A( b ), I and     —     nc , O and     —     nc , and output  206  characteristics are shown. As illustrated, both I and     —     nc  and O and     —     nc  signals have a substantially simultaneous rise. As these signals rise (see, e.g., the left half of FIG. 3A( b )), the output  206  will fall after an output falling delay  308  (see also FIG. 2A( a )). Once I and     —     nc  falls, the output  206  will rise after an output rising delay  310  (see also FIG. 2A( b )). Accordingly, the system  300  of FIG. 3A( a ) can determine both the rising and falling output delays for the NAND gate  201 . Also indicated is a non-controlling fall input delay  306  between the time I and     —     nc  falls and when O and     —     nc  falls (see, e.g., the right half of FIG. 3A( b )). It is envisioned that the fall delay  306  be selected such that it is sufficiently longer than the output rising delay  310 . Otherwise, if the O and     —     nc  signal falls prior to the output  206  rising, the rising output delay for the output  206  may not be accurately determined.  
         [0038]    [0038]FIG. 3B( a ) illustrates an exemplary system  350  utilizing an OR_NC gate  312  in accordance with an embodiment of the present invention. FIG. 3B( b ) illustrates exemplary characteristics of the system  350  of FIG. 3B( a ) in accordance with an embodiment of the present invention.  
         [0039]    In FIG. 3B( a ), the system  350  includes the NOR gate  211  and the OR_NC gate  312 . As illustrated, the OR_NC gate  312  receives the controlling input  212  as I or     —     nc    314  and provides its output O or     —     nc  to the non-controlling input  214  of the NOR gate  211 .  
         [0040]    In FIG. 3B( b ), I or     —     nc , O or     —     nc , and output  216  characteristics are shown. As illustrated, both I or     —     nc  and O or     —     nc  signals have a substantially simultaneous fall. As these signals fall (see, e.g., the right half of FIG. 3B( b )), the output  216  will rise after an output rising delay  320  (see also FIG. 2A( b )).  
         [0041]    Once I or     —     nc  rises, the output  216  will fall after an output falling delay  318  (see also FIG. 2A( a )). Accordingly, the system  300  of FIG. 3B( a ) can determine both the rising and falling output delays for the NOR gate  211 . Also indicated is a non-controlling rise input delay  316  between the time I or     —     nc  rises and when O or     —     nc  falls (see, e.g., the left half of FIG. 3A( b )). It is envisioned that the rise delay  316  be selected such that it is sufficiently longer than the output falling delay  318 . Otherwise, if the O or     —     nc  signal rises prior to the output  216  falling, the falling output delay for the output  216  may not be accurately determined.  
         [0042]    It is envisioned that no logic gate be used in design of the AND_NC and OR_NC devices, in part, because logic gates generally have a finite delay through them. Based on the I/O characteristics of these devices (as illustrated in FIGS.  3 A( b ) and  3 B( b )), it is desirable that the output signal be substantially similar to the input signal for at least one of the edges (i.e., without any finite delay). For example, FIG. 3A( b ) illustrates that I and     —     nc  c and O and     —     nc  have a substantially simultaneous rise. And, FIG. 3B( b ) illustrates that I or     —     nc  and O or     —     nc  have a substantially simultaneous fall. Additionally, it is desirable that the input signal for the AND_NC and OR_NC devices have a substantially logic high or logic low for the other edge. It is, however, envisioned that the output signals of these devices, e.g., O and     —     nc  and O or     —     nc , may have a fall or rise delay associated with the other edge as illustrated in FIGS.  3 A( b ) and  3 B( b ), respectively. It is also envisioned that the delay associated with the non-controlling input of the gate being tested be sufficiently long enough to allow measurement of the rising or falling output delays accurately.  
         [0043]    In an embodiment, AND_NC and OR_NC devices can be designed using several voltage controlled voltage sources (VCVS). It is also envisioned that these devices can be created utilizing operational amplifiers (including an operational transconductance amplifier (OTA)) configured to represent a VCVS such as PSpice model for the  741  op-amp. Other examples include current controlled current sources (CCCS), voltage controlled current sources (VCCC), current controlled voltage sources (CCVS), and the like.  
         [0044]    [0044]FIGS. 4 and 5 illustrate exemplary VCVS devices in accordance with various embodiments of the present invention. FIG. 4 illustrates an exemplary schematic for an AND_NC gate in accordance with an embodiment of the present invention. FIG. 5 illustrates an exemplary OR_NC schematic in accordance with an embodiment of the present invention.  
         [0045]    [0045]FIG. 4 illustrates a system  400  which includes three VCVS devices  402 ,  404 , and  406 . As illustrated, each VCVS has positive and negative element (output) nodes marked as N+ and N−, respectively. Each VCVS also has positive and negative controlling nodes VC+ and VC−, respectively. All VC− nodes are grounded in FIG. 4. The N− node of both VCVS  402  and  406  are also grounded. An input  408  of the system  400  is provided to the VC+ nodes of VCVS  402  and VCVS  404 . The N+ node of VCVS  402  is provided to N− node of VCVS  404  and the N+ node of VCVS  404  is provided to VC+ node of VCVS  406 . The N+ node of VCVS  406  provides an output  410  of the system  400 . In some embodiments, it is envisioned that the voltage gain for all the VCVSes may be 1 (i.e., unity). It is further envisioned that the connection between different terminals may create the output waveforms. In some embodiments employing HSpice, the HSpice delay time for the device  402  may be set to the “fall delay” (such as the fall delay  306  discussed with respect to FIG. 3). It is also envisioned that for the device  406  Vmax may be set to Vdd and Vmin may be set to Vss in certain embodiments.  
         [0046]    [0046]FIG. 5 illustrates a system  500  which includes three VCVS devices  502 ,  504 , and  506 . As with FIG. 4, each VCVS has positive and negative element (output) nodes marked as N+ and N−, respectively. Each VCVS also has positive and negative controlling nodes VC+ and VC−, respectively. As illustrated, two of the VC− nodes are grounded in FIG. 5 (for devices  502  and  506 ). The N− node of both VCVS  502  and  504  are also grounded. An input  508  of the system  500  is provided to the VC+ nodes of VCVS  502  and VCVS  504 . The input  508  is additionally provided to the VC−node of VCVS  504 . The N+ node of VCVS  502  is provided to VC+ node of VCVS  504  and the N+ node of VCVS  504  is provided to N− node of VCVS  506 . The N+ node of VCVS  506  provides an output  510  of the system  500 .  
         [0047]    In some embodiments employing HSpice, the HSpice delay time for the device  502  may be set to the “rise delay” (such as the rise delay  316  discussed with respect to FIG. 3). It is also envisioned that for the device  506  Vmax may be set to Vdd and Vmin may be set to Vss in certain embodiments. Additionally, it is envisioned that for the device  504  the Vmaz may be set to zero in some embodiments.  
         [0048]    Those with ordinary skill in the art would readily recognize that the use of these devices can be extended to more complex gates than just NAND or NOR gates. For example, an AND type gate would work similar to the NAND gate configuration described herein. Moreover, an OR type gate would work similar to the NOR gate configuration described herein. Even for gates like and-or-invert (AOI), combination of both the devices can be utilized to simulate the falling and rising delays through the gates in one schematic. An example of how these devices can be used with AOI gate is shown in FIG. 6.  
         [0049]    In FIG. 6, a system  600  includes an AND gate  604 , an AND_NC device  606 , an OR_NC device  608 , and a NOR gate  612 . An input  602  of system  600  provides signals to a controlling input of the AND gate  604 , an input of the AND_NC device  606 , and an input of an OR_NC device  608 . In some embodiments, the AND_NC  606  and OR_NC  608  devices can be similar to or exactly the same as any respective devices discussed herein. An output  610  of the AND_NC device  606  is provided to the non-controlling input of the AND gate  604 . An output  611  of the OR_NC device  608  is provided to the non-controlling input of the NOR gate  612 . A controlling input of the NOR gate  612  receives its input from the AND gate  604 . An output  614  of the NOR gate  612  provides the output of the system  600 .  
         [0050]    The foregoing description has been directed to specific embodiments. It will be apparent to those with ordinary skill in the art that modifications may be made to the described embodiments, with the attainment of all or some of the advantages. For example, AND_NC devices can be used for NAND or AND gates and OR_NC devices can be used for NOR or OR gates. Also, while behavior of signals herein may be described by utilizing verbs such as “falls” or “rises,” this description is fully intended to be interchangeable where a signal starting to fall or starting to rise may be a triggering event. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the spirit and scope of the invention.