Abstract:
One embodiment of the present invention provides a system that facilitates routing nets between cells in a circuit layout. During operation, the system receives a circuit design to be routed, wherein the circuit design includes multiple circuit blocks that have been placed at specific locations within the circuit layout. Next, the system determines estimated lengths for nets that couple these circuit blocks together. The system then calculates the delay for the nets that couple the circuit blocks using a class one rule. If the delay in a given net is greater than a specified delay, the system inserts a virtual repeater into the given net to decrease the delay.

Description:
BACKGROUND  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates to the process of routing signals between circuit elements within an integrated circuit. More specifically, the present invention relates to a method and an apparatus for assigning nets that carry signals between circuit elements to specific metal layers during the process of routing of signals between circuit elements within an integrated circuit.  
           [0003]    2. Related Art  
           [0004]    Dramatic advances in integrated circuit technology presently make it possible to integrate hundreds of millions of transistors onto a single semiconductor chip. These dramatic advances are made possible by improvements in wafer processing technology and by automated design tools, which can handle the complexity involved in designing circuits with hundreds of millions of transistors.  
           [0005]    These automated design tools operate by receiving a functional specification of an integrated circuit and then decomposing the functional specification into corresponding circuit elements. These circuit elements are then placed at specific locations on the semiconductor chip. During a subsequent routing operation, various nets are routed to form signal pathways between the circuit elements. A timing model can subsequently be used to calculate path delays through the nets to verify that the circuit meets timing constraints. These path delays can be adjusted, if necessary, by assigning nets to metal layers with different delay characteristics. Also, flip-flops can be inserted into nets that do not meet minimum timing requirements. Since inserting flip-flops changes the logic of the circuit, a design engineer typically performs this step manually before repeating the placement and routing operations.  
           [0006]    One routing technique operates by assigning nets to groups associated with specific metal layers according to an engineer&#39;s estimate of the speed of particular nets. However, this technique is not ideal because it requires the engineer to manually assign nets to metal layers on an ad hoc basis, without providing the engineer with a clear set of alignment rules.  
           [0007]    Hence, what is needed is a method and an apparatus for assigning nets to specific metal layers during the process of routing of signals between circuit elements without the drawbacks described above.  
         SUMMARY  
         [0008]    One embodiment of the present invention provides a system that facilitates routing nets between cells in a circuit layout. During operation, the system receives a circuit design to be routed, wherein the circuit design includes multiple circuit blocks that have been placed at specific locations within the circuit layout. Next, the system determines estimated lengths for nets that couple these circuit blocks together. The system then calculates the delay for the nets that couple the circuit blocks using a class one rule. If the delay in a given net is greater than a specified delay, the system inserts a virtual repeater into the given net to decrease the delay.  
           [0009]    In a variation of this embodiment, determining estimated lengths for nets involves computing a Steiner tree.  
           [0010]    In a further variation, determining the estimated lengths for the nets involves assigning nets to layers.  
           [0011]    In a further variation, the class one rule assigns the given net to a first through fourth metal layer.  
           [0012]    In a further variation, if the delay is less than one clock cycle, the system assigns the given net to a first group.  
           [0013]    In a further variation, if the delay is not less than one clock cycle the system calculates the delay for the nets using a class two rule, and if the delay in the given net is greater than a specified delay, the system inserts a virtual repeater in the given net to decrease the delay.  
           [0014]    In a further variation, the class two rule assigns the given net to a fifth through sixth metal layer.  
           [0015]    In a further variation, if the delay is less than one clock cycle, the system assigns the given net to a second group.  
           [0016]    In a further variation, if the delay is not less than one clock cycle the system calculates the delay for nets using a class three rule and if the delay in the given net is greater than a specified delay, the system inserts a virtual repeater in the given net to decrease the delay.  
           [0017]    In a further variation, the class three rule assigns the given net to a seventh through eighth metal layer.  
           [0018]    In a further variation, if the delay is less than one clock cycle, the system assigns the given net to a third group.  
           [0019]    In a further variation, the system reports the first group, the second group, and the third group to provide a starting assignment for a subsequent routing process.  
           [0020]    In a further variation, if the delay is not less than one clock cycle, the system inserts a virtual flip-flop in the given net, and changes the delay criterion from greater than one clock cycle to greater than two clock cycles. The system then repeats the process. 
       
    
    
     BRIEF DESCRIPTION OF THE FIGURES  
       [0021]    [0021]FIG. 1A illustrates a computer system  102  in accordance with an embodiment of the present invention.  
         [0022]    [0022]FIG. 1B illustrates a router  112  in accordance with an embodiment of the present invention.  
         [0023]    [0023]FIG. 2 is a flowchart illustrating the process of routing nets in a circuit design in accordance with an embodiment of the present invention.  
         [0024]    [0024]FIG. 3 illustrates total path delay in accordance with an embodiment of the present invention.  
         [0025]    TABLE 1 is a table of class rules in accordance with an embodiment of the present invention.  
     
    
     DETAILED DESCRIPTION  
       [0026]    The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.  
         [0027]    The data structures and code described in this detailed description are typically stored on a computer readable storage medium, which may be any device or medium that can store code and/or data for use by a computer system. This includes, but is not limited to, magnetic and optical storage devices such as disk drives, magnetic tape, CDs (compact discs) and DVDs (digital versatile discs or digital video discs), and computer instruction signals embodied in a transmission medium (with or without a carrier wave upon which the signals are modulated). For example, the transmission medium may include a communications network, such as the Internet.  
         [0028]    Computer System  
         [0029]    [0029]FIG. 1A illustrates a computer system  102  in accordance with an embodiment of the present invention. Computer system  102  includes design  104 , placement  106 , virtual routing  108 , and routing  110 .  
         [0030]    Computer system  102  receives design  104  and routes design  104  to placement  106  for placement of the circuit blocks included in the design. Note that the terms “circuit blocks”, “cells”, and “circuit elements” are used interchangeably in this document and generally refer to circuit components, which are placed on a substrate and coupled together with metal to form the completed circuit.  
         [0031]    After placement  106  places the blocks, the placement is passed to virtual routing  108  for routing the interconnections nets between the various circuit elements. Finally, the virtual routing is passed to routing  110  to finish the routing based upon the virtual routing.  
         [0032]    [0032]FIG. 1B illustrates a router  112  in accordance with an embodiment of the present invention. Router  112  includes design  104 , length determiner  116 , delay calculator  118 , repeater inserter  120 , flip-flop inserter  122 , and report generator  124 . Length determiner  116  and delay calculator  118  receive input from class rules  126 , which includes resistance/capacitance (RC) information for each metal type, width, and spacing and layer assignments as described below in conjunction with Table 1.  
         [0033]    Length determiner  116  determines the length of the nets within design  104 , which couple the cells for example by using a Steiner tree or Manhattan distance technique. These are well-known techniques in the art for determining net lengths and will not be discussed further herein.  
         [0034]    Next, delay calculator  118  determines the delay for the various nets. If the maximum allowed delay is reached for a specific net, repeater inserter  120  inserts a repeater in the net to reduce the delay time. If the maximum allowed delay is still exceeded, the system uses higher levels of class rules. Higher levels of class rules provide shorter delays because of the increased metal widths and increased spacing on these layers. Details of the total path delay model are shown in FIG. 3.  
         [0035]    If the delay for a given net cannot be brought below the maximum allowed delay by inserting repeaters and using higher class rules, flip-flop inserter  122  inserts a flip-flop into the given net, sets the delay criterion from greater than one clock cycle to greater than two clock cycles and repeats the process of calculating net delays, inserting inverters, and using different class rules to determine a net routing, which will meet the specified maximum allowed delay.  
         [0036]    Report generator  124  generates a report, which includes the net groupings according to class, the inserted repeaters, and the inserted flip-flops. This report provides the input to a subsequent routing process.  
         [0037]    Net Routing  
         [0038]    [0038]FIG. 2 is a flowchart illustrating the process of producing a virtual routing for nets in a circuit design in accordance with an embodiment of the present invention. The system first receives a circuit design  104  for routing (step  202 ). This circuit design includes a placement for the cells, which comprise the circuit. Next, length determiner  116  determines the length of the nets, which couple the cells for example by using a Steiner tree or Manhattan distance technique (step  206 ).  
         [0039]    Delay calculator  118  then calculates the delay for each net using the class-one rule (step  208 ). If necessary, repeater inserter  120  inserts a virtual repeater into the net to improve timing (step  210 ). The system then determines if the delay is greater than one clock cycle (step  212 ). If not, the net is added to group one (step  214 ).  
         [0040]    If the delay is greater than one clock cycle, delay calculator  118  calculates the delay for each net using the class-two rule (step  216 ). If necessary, repeater inserter  120  inserts a virtual repeater into the net to improve timing (step  218 ). The system then determines if the delay is greater than one clock cycle (step  220 ). If not, the net is added to group two (step  222 ).  
         [0041]    If the delay is greater than one clock cycle, delay calculator  118  calculates the delay for each net using the class-three rule (step  224 ). If necessary, repeater inserter  120  inserts a virtual repeater into the net to improve timing (step  226 ). The system then determines if the delay is greater than one clock cycle (step  228 ). If not, the net is added to group three (step  230 ).  
         [0042]    If the delay is still greater than one clock cycle, flip-flop inserter inserts a virtual flip-flop into the net (step  232 ). The system then changes the delay criterion from greater than one clock cycle to greater than two clock cycles (step  234 ) and then returns to step  208  to repeat the process.  
         [0043]    When the nets have been assigned to group one, group two, or group three, report generator  124  reports the results as a starting point for a subsequent routing step (step  236 ).  
         [0044]    Total Path Delay  
         [0045]    [0045]FIG. 3 illustrates a total path delay model in accordance with an embodiment of the present invention. Flip-flops  302  and  308  are coupled together by a net, which includes repeaters  304  and  306 , resistors R 1 -R 3 , and capacitors C 1  and C 2 . Repeaters  304  and  306  may have been inserted by repeater inserter  120 . R 1 -R 3  and C 1 -C 2  are lumped values of resistance and capacitance representing the distributed resistance and capacitance on the metal layers that couple repeaters  304  and  306 . Clock  310  is coupled to flip-flops  302  and  308  and provides timing signals to these flip-flops.  
         [0046]    The total path delay includes delays  312 ,  314 ,  316 ,  318 , and  320 . Delay  312  is the clock to output delay time of flip-flop  302 . Delays  314 ,  316 , and  318  are the delays for the respective portions of the net coupling flip-flops  302  and  308 . Delay  320  is the setup time for flip-flop  308 . The total path delay is adjusted by inserting repeaters into the net, inserting flip-flops into the net, and/or by assigning the net to different class groups. Assigning the net to different class groups effectively changes the values of R 1 -R 3  and C 1  and C 2 , thereby changing the delay value.  
         [0047]    Class Rule Table  
         [0048]    Table 1 is a table of class rules in accordance with an embodiment of the present invention. In general, class rules  126  relate metal layers, width, and spacing for the metal. Specifically, class one includes metal layers  1 - 4  with width equal to one unit and spacing equal to two units; class two includes metal layers  5  and  6  with width equal to two units and spacing equal to two units; and class three includes metal layers  7  and  8  with width equal to three units and spacing equal to three units. Other combinations are equally acceptable for a given layer.  
         [0049]    The foregoing descriptions of embodiments of the present invention have been presented for purposes of illustration and description only. They are not intended to be exhaustive or to limit the present invention to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the present invention. The scope of the present invention is defined by the appended claims.