Patent Publication Number: US-6704911-B2

Title: RC netlist reduction for timing and noise analysis

Description:
BACKGROUND OF INVENTION 
     The capabilities of modern integrated circuits (“ICs”) continue to increase as technology improves. In order to increase the capabilities of an IC without increasing the size of the IC, sizes of devices on the IC must often be reduced to units of microns (10 −6 ). Circuit designs using devices having sizes measurable in microns are known and referred to as deep submicron (“DSM”) designs. 
     A typical IC having a DSM design has tens of millions of devices. With this increased number of devices, there are more devices per unit area than a non-DSM design IC. To connect the devices to the IC substrate itself and with other circuit devices and components, physical wires, known as interconnect, form a network of connections on the IC. From a technical viewpoint, interconnect does not behave as a virtual or ideal wire. Instead, the interconnect acts similarly to a network of capacitances and resistors, which can dominate circuit behavior, particularly with regard to timing. FIG. 1 shows a section of interconnect ( 10 ) on a typical IC ( 12 ). The interconnect ( 10 ) have inherent resistances (not shown) and capacitances ( 14 ). The section of interconnect ( 10 ) shown in FIG. 1 is typically part of a larger network of interconnect known and referred to as a “RC network.” 
     As the number of interconnect in a RC network increase with more devices per unit area on a DSM design IC, device performance, e.g., timing, signal integrity, power problems, etc., coupled with the demands for increased reliability, speed, and efficiency becomes increasingly harder to manage. In order to meet such demands, chip designers use automated tools to verify physical design and ensure circuit integrity. 
     One method used to facilitate the analysis and testing of an IC&#39;s interconnect is parasitic extraction. Parasitic extraction is the process of creating an electrical model representation of the physical connections present between devices in an IC. The electrical model formed as a result of parasitic extraction is typically known and referred to as a “netlist.” 
     Reduction entails removing unintentional circuit elements to ensure circuit integrity. One goal of typical reduction techniques is to make a netlist as compact as possible while preserving accuracy as much as possible. 
     FIGS. 2 a  and  2   b  respectively show an original circuit ( 20 ) before a typical reduction process and a reduced circuit ( 30 ) after the typical reduction process. As shown in FIG. 2 b , a topology of the reduced circuit ( 30 ) is different from a topology of the original circuit ( 20 ). Further, the reduced circuit ( 30 ) has resistive loops ( 32 ) that were not present in the original circuit ( 20 ). Further still, the reduced circuit ( 30 ) has ground resistances ( 34 ) that were not present in the original circuit ( 20 ). 
     In effect, the typical reduction process results in a netlist that is topologically and functionally different from an original circuit. In addition, with a typical reduction process, because modern circuits have large numbers of input/output ports, there is a tendency for the reduction process to couple input/output ports with each other; thereby actually increasing the size of the circuit. Thus, there is a need for a reduction process that maintains an original circuit&#39;s topology while maintaining functional accuracy in a netlist with respect to the function and characteristics of the original circuit. 
     SUMMARY OF INVENTION 
     According to one aspect of the present invention, a circuit reduction method comprises inputting information about an original circuit structure, using a resistive degree of at least one node in the original circuit structure to selectively sort the at least one node, determining at least one time constant of the original circuit, sorting the at least one time constant, and determining whether to remove a loop in the original circuit structure based on the sorted at least one time constant and the sorted at least one node. 
     According to another aspect, a computer-readable medium having recorded therein instructions executable by processing, where the instructions are for: inputting information about an original circuit structure; using a resistive degree of at least one node in the original circuit structure to selectively sort the at least one node; determining at least one time constant of the original circuit; sorting the at least one time constant; and determining whether to remove a loop in the original circuit structure based on the sorted at least one time constant and the sorted at least one node. 
     According to another aspect, a computer system comprises a processor, a memory, and instructions that reside in the memory and are executable by the processor, where the instructions are for: inputting information about an original circuit structure; using a resistive degree of at least one node in the original circuit structure to selectively sort the at least one node; determining at least one time constant of the original circuit; sorting the at least one time constant; and determining whether to remove a loop in the original circuit structure based on the sorted at least one time constant and the sorted at least one node. 
     Other aspects and advantages of the invention will be apparent from the following description and the appended claims. 
    
    
     BRIEF DESCRIPTION OF DRAWINGS 
     FIG. 1 shows a network of interconnects on a typical computer chip. 
     FIGS. 2 a  and  2   b  respectively show a circuit before and after a typical reduction process. 
     FIG. 3 shows a flow process in accordance with an embodiment of the present invention. 
     FIG. 4 a  shows a circuit for a reduction process in accordance with an embodiment of the present invention. 
     FIG. 4 b  shows a circuit reduction process in accordance with an embodiment of the present invention. 
     FIGS. 5 a - 5   c  show a circuit reduction process in accordance with another embodiment of the present invention. 
    
    
     DETAILED DESCRIPTION 
     Embodiments of the present invention relate to a method and apparatus for generating a netlist that maintains a topology of an original circuit while preserving an original circuit&#39;s functions and characteristics. Embodiments of the present invention further relate to a method and apparatus for reducing a circuit using a process that maintains both (1) an original circuit topology and (2) functional characteristics of the original circuit. 
     FIG. 3 shows an exemplary flow process in accordance with an embodiment of the present invention. Initially, a detailed standard parasitic format (“DSPF) is read (step  40 ). The DSPF has information regarding a structure of an original circuit. Once the DSPF has been read (step  40 ), a preprocessing phase occurs (step  42 ). The preprocessing phase involves preparing the original circuit such that it can be reduced. Thereafter, one or more nodes of the original circuit are sorted based on resistive degrees of the one or more modes (step  44 ). 
     Then, a timer is used to measure one or more time constants of the original circuit (step  46 ). Once the time constants have been determined (step  46 ), the time constants are evaluated and sorted (step  48 ). Using the evaluated and sorted time constant information, one or nodes in the original circuit are analyzed (step  50 ) in order to determine which loops of the original circuit to eliminate (step  52 ). Once one or more loops are eliminated from the original circuit, a time measurement may again be made (step  46 ) to determine one or more time constants of the modified circuit. After the loops are removed (step  54 ), a reduced circuit results, where after, the reduced circuit is post-processed and stored in a new DSPF file (step  56 ). 
     FIG. 4 a  shows a circuit for a reduction process in accordance with an embodiment of the present invention. Particularly, FIG. 4 a  shows a model of a node. In the reduction process, resistances and ground capacitances are redistributed by eliminating nodes with insignificant characteristic time constants based on local circuit transformation in order to keep an Elmore time constant from all directions. The characteristic time constant of a node is defined as: 
     
       
         τ C   =χ/γ=ΣC/Σg,   (1) 
       
     
     where χ=ΣC represents the total capacitance (including C c  and C g ) connected to a central node, and γ=Σg represents the total conductance connected to the central node. Further, τ C  is a measure of the significance of a node. 
     Those skilled in the art will appreciate that the elimination of insignificant nodes, there is only a relatively small effect in the time domain response. The critical time constant is determined by using a built-in fast delay and noise estimation engine to control the reduction process. 
     Still referring to FIG. 4 a , if R iN  and R jN  are present, then connect node i and node j with R ij , where R ij =γ N /(g iN *g jN ). If R iN  and C jN  are present, then connect node i and node j with C ij , where C ij =(g iN *C jN )/γ N . 
     FIG. 4 b  shows an exemplary circuit reduction process in accordance with an embodiment of the present invention. Particularly, the reduction process shows the steps in a circuit transformation according to values for R iN , R jN , γ N , and C ij . 
     FIGS. 5 a - 5   c  show an original circuit, a circuit reduced using traditional means, and a circuit reduced in accordance with embodiments of the present invention. 
     Those skilled in the art will appreciate that a circuit reduction method in accordance with embodiments of the present invention maintain global ground capacitance distribution along a particular net. Further, those skilled in the art will appreciate that the circuit reduction method maintains the global coupling capacitance distribution along a particular net. Those skilled in the art will also appreciate that the circuit reduction method maintains spatial latency, i.e., the coupling between a near end node and a far end node. 
     Additionally, those skilled in the art will appreciate that a reduction tool related to the present invention allows a user to select a node for reduction. 
     Furthermore, those skilled in the art will appreciate that a reduction tool related to the present invention reduces an original circuit regardless of the number of input/output ports in the original circuit. Thus, unlike the typical reduction tool, the present invention compensates for input/output port linkages and ensures actual reduction, i.e., an actual decrease in circuit size. 
     Advantages of the present invention may include one or more of the following. In some embodiments, a reduced circuit may be generated that has a similar topology of an original circuit. 
     In some embodiments, because a circuit reduction method maintains coupling capacitance distribution along a net, accuracy is increased relative to when the coupling capacitance distribution along the net is not uniform. 
     In some embodiments, a reduced circuit may be generated that maintains the total ground capacitance present in an original circuit. 
     In some embodiments, a reduced circuit may be generated that maintains the total resistance of an original circuit. 
     In some embodiments, a reduced circuit may be generated that removes loops present in an original circuit. 
     In some embodiments, a circuit reduction tool reduces a size of an original circuit regardless of the amount and positions of input/output ports in the original circuit. 
     In some embodiments, a circuit reduction method has error control by which a user may specify an amount of error that can be tolerated in the circuit reduction method. 
     In some embodiments, a circuit reduction tool is able to remove loops that are not present in an original circuit structure but are present after a reduction extraction of the original circuit. 
     In some embodiments, a circuit reduction tool allows a user to select which nodes to reduce. 
     While the invention has been described with respect to a limited number of embodiments, those skilled in the art, having benefit of this disclosure, will appreciate that other embodiments can be devised which do not depart from the scope of the invention as disclosed herein. Accordingly, the scope of the invention should be limited only by the attached claims.