Abstract:
Clock paths are routed in two steps or phases. First, a local clock distribution network is generated to minimize as much as possible the length of conductors within regions and positioning local clock buffers, one in each region. Second, a global clock distribution network is designed to couple the local clock buffers to a clock source using equidistant conducting path between the local clock buffers. Consideration is given to constraints imposed by capacitance, conductor length, and power requirements. The second phase repeats the first phase when power constraints are violated.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention relates to the layout of printed and integrated circuits and particularly to the routing of clock signals. More particularly, it relates to the distribution of clock signals in large integrated circuits. 
     2. Description of the Related Art 
     Large circuits such as Application Specific Integrated Circuits (ASIC) require the distribution of clock signals from a single clock driver source to each clocked element (sink). The skew, i.e., unequal delay times, of the clock from the source to the sinks has a deleterious effect on the performance of the entire circuit. Since large integrated circuits such as ASICs include numerous clocked elements, into the tens or even hundreds of thousands, it is important to design the clock circuitry so as to minimize the skew. 
     Due to the narrow width of conductors in large scale integrated circuits, a clock network must meet electromigration reliability rules. The clock network must be capable of being analyzed by using industry standards of extraction and analysis tools. Other factors impacting the design are implementation with industry standard circuit libraries and EDA (Engineering Design Automation) tools and low impact on the chip size and performance. 
     Prior art clock distribution networks sometimes use a package routing layer. The package routing layer usually has very little sheet resistivity so the clock signal can be distributed throughout the package. This approach is not available for those designs where the package does not include routing layers. It can also be costly to implement due to the routing customization of the specific application. This technique does not address the problems of local clock distribution. 
     “H” or “I” tree methods, a form of balanced routing to achieve low skew, depends on symmetric placement of clocked elements in the integrated circuit. Some applications may contain some regular structures that are symmetrical such as in a microprocessor, but VLSI applications are often asymmetrical. This prior art approach also uses wide “H” or “I” structures at the global level with increases power consumption and increases the complexity of the analysis. 
     Grid structures have the disadvantage of additional wiring to form the grid and larger power consumption. It requires a significant amount of wiring, especially when multiple clock domains must be driven which increases the chip size. 
     Methods which demand a large amount of wiring increase the net capacitance of the distribution and need additional power. The electromigration effect is increased with increases in power. 
     BRIEF SUMMARY OF THE INVENTION 
     This invention is a method of designing a low skew clock distribution system for circuit layouts containing clocked elements, especially very large scale integrated circuits (VLSI). Although it is applicable and useful in any circuit layout utilizing distributed signals, the description is especially applicable to VLSI and ASIC in particular. The faster the circuit elements, the more necessary a balanced clock distribution scheme. 
     The method disclosed maximizes VLSI performance due to the low skew. It also minimizes the development time and cost because it can be implemented with industry standard circuit libraries and EDA tools. 
     In accordance with the invention, local clock distribution networks are designated within regions in which a circuit layout is divided. Each local clock distribution network contains a local clock buffer which is coupled to the clocked circuit elements within the region by a minimum length path. A global clock distribution network is generated to couple the local clock buffers to the clock source by using serially connected buffers along equidistant paths. 
    
    
     BRIEF DESCRIPTION OF THE DRAWING 
     The invention is described in detail by referring to the various figures which illustrate specific embodiments of the invention, and wherein like numerals refer to like elements. 
     FIG. 1 is illustrative example of an integrated circuit layout showing a plurality of clock load locations. 
     FIG. 2 is the layout of FIG. 1 with the layout of FIG. 1 divided into a plurality of regions. 
     FIG. 3 is a flowchart of the process for routing a local distribution network. 
     FIG. 4 is an illustration of an example of a region with a local clock network having clock loads connected by conductor lengths of minimum Steiner distances. 
     FIG. 5 is an illustrative example of a circuit showing the location of local clock buffers. 
     FIG. 6 is an illustration of the placing of global clock buffers on an example of a circuit. 
     FIG. 7 is a flowchart of the procedure for positioning global clock buffers. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The clock distribution network design is performed in two stages, both of which may be implemented after all the components have been positioned on the integrated circuit, including the clocked elements, and preferably prior to routing other signal conductors. First, a local clock distribution network is established followed by the generation of a global clock distribution network. 
     The end of the first stage is determined according to several factors including power constraints, area of the bounding box of all the sinks (clocked elements) in the local box, and considerations of wiring capacitance and resistance. Local Clock Distribution Networks 
     Local clock distribution networks are implemented by grouping all the clock input pads or pins, into regions. Each region will include a local clock buffer network to drive the clock loads contained in the region. The clock delay of the buffer circuit in each region depends on factors including three components, the type of buffer used, the capacitive load at the output and the interconnect delay from a buffer to a clocked element. The skew is minimized within each region and between regions by matching these factors to each load, i.e., clocked element. This can be accomplished for two of the delay components by using dummy capacitive loads and the use of a single buffer type. The interconnect delay, D i  is proportional to the RC time constant of the wiring, i.e., D i ∝R w (0.5C w +C cl ) where R w  is resistance of the wire, C w  is the capacitance of the wire, and C cl  is the capacitance of the clock load. 
     The wire resistance is inversely proportional to its width and directly proportional to its length, R w ∝L w /W w . The capacitance of the wire is proportional to the product of its length and width, C w ∝L w W w . Therefore, D i ∝0.5L w   2 +(L w /W w )C cl . By use of these relationships, the interconnect delays will be bounded by setting a maximum capacitive load on each buffer output. 
     To comport with electromigration rules of metal wiring layers, the current, width, operating conditions, and technological parameters must be taken into consideration. The maximum allowable capacitance can be found from the maximum allowable current, information which is provided in technology user guides. 
     Next, the maximum allowable interconnect delay is set. This value is set as low as possible taking into account the power required. A common design value is 2% of the cycle time. 
     To satisfy both conditions,                C   max     =     min        {                      C   em               C   dm                                  (   1   )                                
     where C dm  is the capacitive load resulting in the maximum allowed interconnect delay. From C dm =C w +C cl , C w =C dm −C cl . With C w =K 1 L w W w  (where K 1  is a technological proportionality constant), 
     
       
           L   w =( C   dm   −C   cl )/ K   1   W   w .  (2) 
       
     
     The resistance R w ∝L w /W w  with the wire width remaining constant, R w =K 2 (C dm −C cl ) where K 2  is another technological proportionality constant. The interconnect delay can now be represented by a combination of the above: D i ∝0.5K 2 (C dm −C cl ) 2 +K 2 C cl (C dm −C cl ). As C cl  approaches 0, the interconnect delay approaches a maximum, and C dm  can be derived. The value of C max  is selected and the value used as a constraint when inserting the clock buffer in each region. 
     The process for inserting the clock buffers begins by establishing the boundary of all the clock loads. An illustrative example is shown in FIG.  1 . The box is bounded by X min , y min  in the lower left corner  1  and by x max , y max  in the upper right comer  2 . Next, the box is divided into a plurality of rows of equal height as shown in FIG.  2 . Each row is divided into regions  21 ,  22 , and  23  up to the last region  24  in the box. 
     The rows are scanned by region, searching for the location of the clock loads from left to right. The clock load x,y locations are placed in an array together with the circuit type or the capacitance of the load. The capacitance data can be determined by table look-up using the circuit type as the criteria. This is performed for each region and the array data is used to determine a clock buffer for the related region. 
     The total net capacitance of the clock loads in a region is calculated using the data in its related array. It is determined from C net =C w +C cl . The value of C w  is based on the minimum Steiner length of the segments connecting the clock loads. The procedure for calculating minimum Steiner lengths is well known in the art or available in software routines. 
     A preferred technique is to calculate a running total of the net capacitance and continue the process so long as C net ≦C max . If C net &gt;C max , the last clock load is removed from the array and the remaining clock loads assembled into other regions with their own arrays. 
     A clock buffer is located in each region and positioned in one of the steiner segments so as not to add additional wiring which would increase the net capacitance, C net . Logic circuit changes can then be made to couple the clock loads in the region to the clock buffer. 
     The above procedure is repeated for each region along each row until all regions have a clock buffer. This method of inserting the local clock distribution networks is independent from the method of locating the clocked elements on the circuit layout which can be randomly placed. It is not essential to the method that the clocked elements be evenly distributed. 
     The procedure described above for the first phase of generating local clock distribution networks is shown in FIG.  3 . In the following description, references are made to the flowcharts depicting the sequence of operations performed by the program. The symbols used are standard flowchart symbols approved by the American National Standards Institute and the International Standards Organization. In the explanation, an operation may be described as being performed by a particular block in the flowchart. This is to be interpreted as meaning that the operations referred to are performed by programming and executing a sequence of instructions that produces the result said to be performed by the described block. The actual instructions used depend on the particular system employed to implement the invention. Different processors have different instruction sets but persons of ordinary skill in the art are familiar with the instruction sets with which they work and can implement the operations set forth in the blocks of the flowchart. 
     The process of FIG. 3 begins at a start terminal  301  and the boundaries of a box delineating the clocked elements to be driven are set by a process block  303 . In a process block  305 , the box is divided into rows of equal-height regions. Data for a first clock load is placed into an array by a process block  307 . Next, a subroutine  308  calculates the minimum Steiner distance and the net capacitance of the clock loads in the array is calculated in a process block  309 . 
     In a decision block  311 , the net capacitance is compared to the maximum allowable predetermined capacitance. If the net capacitance exceeds the maximum, then the last load is removed from the array in a process block  315 . Next, a clock buffer is placed in the region by a process block  319 . 
     If the region just processed is the last region in the box as determined by a decision block  321 , the procedure is exited via a terminal block  323 . Otherwise, a process block  325  initializes a new array and a new region is processed by returning to the process block  307 . 
     If the net capacitance in the array does not exceed the maximum predetermined capacitance at the decision block  311 , then the next clock load data in the region is added to the array by a process block  313  and a return is made to the process block  308 . 
     An example of a region with a local clock network is shown in FIG.  4 . The region  41  has nine clock loads connected by a minimum length Steiner circuit path. A clock buffer  43  is positioned on a circuit so as not to require additional wiring, in this case in as central a position as possible to minimize the distance to all the clock loads. Global Clock Distribution Network 
     The use of balanced length serial redrive segments by a global clock distribution network according to the invention minimizes or eliminates clock distribution skew. To accomplish this, a standard length is first defined with a concomitant power calculation. The process is comparable to the procedure for generating the local clock distribution network already described in that a maximum capacitance is first designated as in equation (1) above, but no skew is introduced into the global clock distribution network. Therefore, C emax  is set to the maximum allowable capacitance according to the specifications in the technology electromigration rules. 
     Replacing the appropriate terms in equation (2) above and considering that the global clock distribution network will drive only clock buffer loads, L w =(C emax −C bl )/K 1 W w  where C bl  is the clock buffer load capacitance. 
     The substantially exact center of the box bounding the buffer circuits of the local network is determined. This center  50  is shown in FIG. 5, which shows the locations of the local clock buffers, and is referred to as x c ,y c . Each of the clock buffer locations is compared to x c ,y c . The clock buffer most distant from x c ,y c  is denoted by L max . In the illustrative example shown in FIG. 5, it is a local clock buffer  53 . The distance is the Manhattan length, i.e., along paths parallel to the x- and y-axes. The clock buffer location  52  of FIG. 5 is the one at a minimum distance, L min , from the center, x c ,y c . 
     The number of redrive segments is defined as        S   =     max        {         L   max   2       L   w       .                                
     That is, S is not less than two. The length of each redrive segment is then defined as L S =L max /S. The total capacitance of each segment is next calculated by C S =C bl +K 1 W w L S . 
     Next, the power calculation is made using the well-known formula P=0.5CV 2 f. Therefore, if the global clock distribution network has to drive a total of z clock buffers, then P=0.5zSC S V 2 f. If the resulting power requirements exceed the circuit estimates, the local clock distribution network generation is repeated to force z sufficiently small to meet the total power estimate. This is accomplished by considering each of the z clock buffers as a clock load for the local clock distribution procedure. 
     The clock buffers of the global clock distribution network are then inserted into the design. For each of the z local clock buffers, S global buffers are added ad seriatim with as an exact distance of L S  between the global buffers as possible. The exact distance can be a forced constraint. The insertion of the buffers is performed according to the following steps.: 
     (1) the location of one of the z local clock buffer circuits is selected. 
     (2) a global clock buffer circuit is placed at x c ,y c . This is shown in FIG. 6 as a global clock buffer circuit  61 . The output of this buffer is coupled to the input of the local clock buffer and the input is coupled to the clock source. 
     (3) insert another global clock buffer. 
     If this is the last global clock buffer circuit to be added for the selected local buffer, the S-th buffer, it is positioned at a distance L S  from the selected local clock buffer and a distance of L S  from the previously inserted global clock buffer, e.g., global clock buffers  68  and  63  in FIG.  6 . 
     If this is not the last global clock buffer to be added, then it is placed at a distance L S  from the previously inserted global clock buffer in the direction of the local clock buffer. For example, in FIG. 6, the global clock buffer  66  is placed a distance of L S  from the global clock buffer  61  in a direction toward the local clock buffer  53 . Another example is the global clock buffer  65  placed a distance of L S  in the direction of the local clock buffer  52 . 
     The outputs from these global clock buffers are coupled to the local clock buffers and their inputs are coupled to the outputs from the previously inserted global clock buffers. 
     (4) Repeat step (3) until S global clock buffers have been added for the selected local clock buffer. 
     (5) repeat step (2) through (4) for the next local clock buffer. The other global clock buffers  63 ,  64 ,  67 , and  68  are positioned the same way. 
     As a result of performing the above steps, the delay path from the clock source to any of the local clock distribution networks is equal. As shown in FIG. 6, although local clock buffer  52  is close to the center x C ,y c  and local clock buffer  53  is far from the center x c ,y c , the delay in the path to local clock buffer  52 , the sum of path lengths S 10 , S 11 , S 12 , and S 13 , is equal to the delay in the path to local clock buffer  53 , the sum of path lengths S 00 , S 01 , S 02 , and S 03 . 
     It has been presumed that the capacitance and resistance of the horizontal and vertical clock routing layers are equal, a usually valid presumption. If not, then the lengths of the x and y legs of the clock paths can be made equal for each path leg. This and other modifications such as revisions to the equations to take into account the different capacitances of vertical and horizontal clock routing layers is within the skill of the art given the teachings of the invention. 
     FIG. 7 is a flowchart showing the procedure for positioning global clock buffers. The procedure begins at a terminal  701  followed by a process block  703  in which the parameters described above are calculated. 
     In a decision block  704 , excess power requirements call the local clock distribution network procedure of FIG. 3 to generate a new local clock distribution network which will drive the existing local clock distribution network. Then control returns to the process block  703  for a recalculation of the parameters. 
     If the power requirements are not excessive, then a process block  705  selects a first local clock buffer. A process block  707  positions a global clock buffer at the center of the region. A decision block  709  determines whether this is the last buffer for the region. If not, then a global clock buffer is positioned the L S  distance from the previously inserted global clock buffer in a process block  715  and the decision block  709  determines whether it is the last global clock buffer for the region. If it is the last global clock buffer for the region, then a process block  711  positions a global clock buffer at a position equidistant between the previously inserted global clock buffer and the last local clock buffer so that it is a distance of L S  from both. 
     A decision block  717  determines whether it is the last local clock buffer and if it is, the procedure is exited via a terminal block  721 . If not, then a process block  719  selects the next local clock buffer and a return is made to the process block  707  to place the global clock buffers for the selected local clock buffer as described above. 
     While the invention has been particularly shown and described with reference to a preferred embodiment thereof, it will be understood by those skilled in the art that various changes and modifications in form and details may be made therein without departing from the spirit and scope of the invention according to the following claims.