Patent Publication Number: US-6990648-B2

Title: Method for identification of sub-optimally placed circuits

Description:
FIELD OF THE INVENTION 
   This invention relates to the physical design process of designing VLSI semiconductor chips, and particularly is directed at the alleviation of wiring congestion. 
   Trademarks: IBM® is a registered trademark of International Business Machines Corporation, Armonk, N.Y. U.S.A. S/390, z900 and z990 and other product names may be registered trademarks or product names of International Business Machines Corporation or other companies. 
   BACKGROUND 
   Wiring congestion in an area of a semiconductor chip can have an adverse impact on timing due to longer than minimum (non-steiner) wire lengths causing larger than necessary wire and circuit delays. Ideally, the placement of an individual circuit should be somewhere between the circuit(s) that drives it and the circuit(s) that it drives. This eliminates the needless consumption of wiring tracks due to cross wiring along the path. Typically, automated placement programs are driven by metrics that result in this condition. However, subsequent steps in the physical design process, such as replication of clock network circuits followed by placement legalization, can lead to situations where circuits are moved outside of their area of connectivity. Steps to replace a particular region to alleviate wiring congestion may negate prior logical or physical design modifications made to improve timing. U.S. Pat. No. 5,859,781 for a “Method and Apparatus For Computing Minimum Wirelength Position (MWP) For Cell in Cell Placement for Integrated Circuit Chip”, describes a method for optimizing the placement of circuits in order to minimize total wire length by employing bounding boxes of connectivity for each net connected to a circuit. Although this is adequate from a pure wirability viewpoint, one drawback is that not all net segments have an equal relationship to timing. Particularly in a design that has gone through some level of logic optimization based on physical design parameters, such as those described in U.S. Pat. No. 6,192,508, “Method For Logic Optimization For Improved Timing and Congestion During Placement In Integrated Circuit Design”, longer length nets have probably already had the circuit driving them bumped up in strength while shorter lengths potentially have smaller/weaker circuits driving them. In this case, decreasing the total net length of a set of nets at the expense of increasing certain pin to pin segments could have an adverse impact on timing. This is illustrated by the two examples shown in  FIG. 1 . For circuit D 1 , a placement move to the left will decrease total net length as both nets IN 1 B and IN 2 B are reduced by the same length that net OUT 1 B is increased. However, if circuit D 1  is a weak strength circuit, the delay increase due to the longer length of net OUT 1 B is likely to outweigh the delay decrease due to the shorter lengths of nets IN 1 B and IN 2 B, creating a potential timing problem. Even in the case where no net lengths increase, there can still be a timing impact due to an increased pin to pin connection. A placement move to the left for circuit B 1  in the figure will decrease the net lengths of nets IN 1 A and OUT 1 A and net IN 2 A&#39;s length will remain the same. However, the pin to pin length from A 2  to B 1  will increase, potentially leading to a larger path delay if the delay of circuit B 1  is particularly sensitive to input slew and/or if the magnitude of increase in wire delay from A 2  to B 1  is greater than the decrease in wire delay from B 1  to C 1 . Such scenarios could require further design iteration to achieve timing closure. 
   SUMMARY OF THE INVENTION 
   The preferred embodiment of the invention relates to a method for identifying and quantifying the situation where a circuit placement leads to unnecessary wire length which can be reduced without increasing the length of any pin to pin connections of that circuit, thus freeing up wiring tracks with no impact to timing. 
   The invention provides a method for identifying circuits in a region of wiring congestion whose placement can be modified in order to reduce net length on each of their net connections without increasing the length of any particular pin to pin segment. The method includes determining the placement locations of all the circuits connected to a particular circuit, excluding the coordinates of that circuit itself. A rectangle is then defined by the X min, Y min, X max, and Y max of these placement coordinates, and the placement of the circuit in question is checked to see if it falls within that rectangle. If not, the rectilinear distance from the circuit to the rectangle is calculated along with the closest placement location along the border of the rectangle. By replacing the circuit along the rectangle border at the location closest to the original circuit position, it is assured that no pin to pin segment will see an increase in length. The circuit instance name is reported along with the distance to the rectangle and recommended placement location. The chip designer can then use this information to decide which circuits to move and quickly replace them with minimal disruption to other circuit placements and no adverse impact on timing. In comparison to a placement or optimization run such as those previously described on the whole chip or a portion of the chip, there is less design change. This is a particularly advantageous in the latter stages of the design cycle, where typically manual logic and physical modifications have already been and are currently being implemented to compensate for deficiencies in the automated processes described and it is desired to minimize the impact to the design parameters those modifications were based on. 
   These and other improvements are set forth in the following detailed description. For a better understanding of the invention with advantages and features, refer to the description and to the drawings. 

   
     DESCRIPTION OF THE DRAWINGS 
       FIG. 1  illustrates how algorithms aimed at reducing total net length can increase pin to pin connections and hence impact timing. 
       FIG. 2  illustrates how the circuits under consideration and their associated rectangles of connectivity are established. 
       FIG. 3  illustrates the determination of the recommended placement location for a circuit outside its rectangle of connectivity. 
       FIG. 4  is a flow diagram of the process steps of the preferred embodiment of the invention. 
   

   Our detailed description explains the preferred embodiments of our invention, together with advantages and features, by way of example with reference to the drawings. 
   DETAILED DESCRIPTION OF THE INVENTION 
     FIG. 4  is a flow diagram describing the process steps of the preferred embodiment. Initially, a region of wiring congestion is defined and described by a set of rectangular coordinates. At step  700 , circuits in the design are tested to determine the set of circuits whose placement falls within the congestion region. Referring to  FIG. 2 , this would include all the circuits shown with the exception of B 3 . For each circuit instance in that set, at step  701 , a program is used to determine the set of net names connected to that circuit. For example, in  FIG. 2 , if circuit B 1  is the current circuit under consideration, nets IN 1 , IN 2 , and OUT 1  will then be the set of nets connected to B 1 . This data is output in a format such that the relationship between B 1  and nets IN 1 , IN 2  and OUT 1  is denoted, call it the circuit info file. At step  702 , the nets in this output are then run through a program which finds the circuit instance names attached to each net along with their placement location. For net IN 2  in  FIG. 2 , this would be circuits A 2 , B 4  and B 1 . This data is output in a format such that the relationship between net name and connected circuits is maintained, call it the net info file. 
   At step  703 , a program is used to correlate each circuit and its associated nets from the circuit info file with the circuits that connect with those nets in the net info file. At this point, we now have all the circuits which connect to the originally identified circuits (the result of step  700 ) along with their placement locations. For the example in  FIG. 2 , this would be circuit B 1  connected to circuits A 1 , A 2 , B 2 , B 3 , B 4 , C 1  and C 2 . For each originally identified circuit, the placement locations of its set of connected circuits are analyzed to determine the X min, Y min, X max and Y max. In  FIG. 2 , circuit B 2  defines the X min, C 1  defines the Y max, C 1  and C 2  define the X max and B 3  defines the Y min. These coordinates are used to define a rectangle of connectivity, shown by the dashed line marked “Connectivity Rectangle” in  FIG. 2 . 
   At step  704 , each originally identified circuit is then checked to determine if its placement falls within its associated rectangle of connectivity. If it does not, at step  705  the rectilinear distance from the circuit to the rectangle is calculated. Referring to  FIG. 3 , assuming the connectivity rectangle shown applies to both circuits A 1  and A 2 , for circuit A 1  this distance corresponds to a straight drop from Y coordinate YA 1  to the northern border of the rectangle at Y=Y 1  for a length of YA 1 −Y 1 . For circuit A 2 , this corresponds to an X distance of X 1 −XA 2  plus a Y distance of Y 1 −YA 2 . At step  706 , a recommended placement location for each circuit is determined based on the closest point along the rectangle edge to the circuit. In FIG.  3 ., the recommended placement location for circuit A 1  would be point X 2 , Y 1  along the rectangle and for circuit A 2  it would be the corner of the rectangle at X 1 , Y 1 . By modifying the circuit&#39;s placement to this position, all net connections associated with the circuit are reduced in length by the distance to the rectangle and no pin to pin connection can be increased as all pins connected to the circuit lie within the rectangle. Referring back to FIG.  2 ., if circuit B 1  is replaced at its recommended location straight down along the northern border of the rectangle, nets IN 1 , IN 2 , and OUT 1  as well as all pin to pin segments are reduced by the length Ydiff, thus freeing up wiring tracks with only the possibility of decreasing path delays. 
   The circuit instances lying outside their rectangle of connectivity are reported at step  707  along with their current placement, distance from the rectangle, and recommended placement location. At step  708 , this information is used at the chip designer&#39;s discretion to determine the circuit placement modifications which will be implemented and aid in the replacing of the selected circuits. 
   By using this process to identify and replace circuits, not only are the path delays encompassing the circuits reduced but wiring tracks are freed up to aid in alleviating wiring congestion and increase the probability of non-related nets routing in with minumum wire length. 
   While the preferred embodiment to the invention has been described, it will be understood that those skilled in the art, both now and in the future, may make various improvements and enhancements which fall within the scope of the claims which follow. These claims should be construed to maintain the proper protection for the invention first described.