Abstract:
An IC layout containing megacells placed in violation of design rules is corrected to remove design rule violations while maintaining the original placement as near as practical. The sizes of at least some of the megacells are inflated. The megacells are placed and moved in a footprint of the circuit in a manner to reduce placement complexity. The placement of the megacells is permuted to reduce placement complexity. Additional movements are be applied to the permuted placement to further reduce placement complexity.

Description:
FIELD OF THE INVENTION 
   This invention relates to integrated circuits (ICs), and particularly to placement of megacells during the design phase of manufacturing ICs. 
   BACKGROUND OF THE INVENTION 
   During the design phase of an integrated circuit, it is necessary to place cells within the bounds (footprint) of the semiconductor chip layout in accordance with certain design rules. The placement of cells takes into account routing of wires between the cells, pin placement, timing considerations, etc. Certain cells, called “megacells”, occupy a considerably larger area than most cells. Examples of megacells include flip-flops, memories, etc. 
   When the cells are initially placed, the positions of certain cells, including certain megacells, are considered “fixed” due to design constraints. For example, it is common to fix the position of cells having pins coupled to an edge of the IC chip for connection to external devices. 
   During the design phase, wires are routed between cells. These wires form “blockages” where cells and megacells cannot be placed. Thus, if the position of a cell or megacell encroaches on a blockage, either the blockage or the cell (or megacell) must be moved. Ordinarily, movement of a blockage is a relatively complex task, because it usually involves movement of numerous other cells and megacells. On the other hand, it is a relatively simple matter to move ordinary cells to accommodate blockages. Therefore, it is common to move ordinary cells rather than blockages. But it is not an altogether easy task to move megacells to accommodate blockages. 
   Another problem encountered in megacell placement occurs where plural megacells overlap. The size of megacells usually makes it difficult to move megacells after placement of other cells. Moreover, movement of fixed megacells, including flipping and rotation, might adversely affect timing considerations to pins of the megacell, and might adversely affect the space available for routing wires and subsequent cell placement. 
   Consequently, there is a need for a technique to place megacells to the footprint of an IC chip such that the placement of all megacells is “legal”. As used herein, megacell placement is considered legal if no two megacells intersect, if no megacell occupies area covered by blockages, if fixed megacells are not moved, rotated or flipped, and if there is enough space between megacells to create a legal placement of the remaining cells and blockages. 
   SUMMARY OF THE INVENTION 
   The present invention is directed to legal placement of megacells, and particularly to correcting an initial design that violates design rules so that the corrected design satisfies the design rules while maintaining placement that is similar to the initial placement. 
   In one embodiment of the invention, megacells are in an initial integrated circuit layout that violates design rules. A size of each not-fixed megacell is inflated, and the inflated megacell is placed in a footprint of the chip to reduce placement complexity. Megacell placements are permuted to reduce placement complexity. 
   In some embodiments, the megacell size is inflated by identifying a distance between an edge on the megacell and each side of the chip. A distance between the centers of the megacell and each other not-fixed megacell is identified, and an inflation factor is applied to the sides of the megacell. 
   In other embodiments, the megacells are placed by placing all fixed megacells and blockages in the footprint. A list is generated of free rectangles in the footprint that do not contain megacells and blockages. Beginning with the largest not-fixed megacell, each not-fixed megacell is placed in a free rectangle that is large enough to receive the megacell. A transformation movement is then applied to the megacell if the movement reduces placement complexity. 
   In other embodiments, the permutation of megacell placements is performed by swapping positions of megacells of each pair of not-fixed megacells if the swapping reduces placement complexity, and then applying a transformation movement to each megacell if the movement reduces placement complexity. 
   In a second embodiment, a computer usable medium contains computer readable program code that causes a computer to carry out the process. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIGS. 1–3 , taken together, is a flowchart of a process of megacell placement according to the present invention. 
   

   DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
   In preferred embodiments, the process is carried out in a computer under the control of a computer readable program having code that controls the computer to perform steps of the process. For purposes of explanation, it is assumed that the input layout includes an illegal megacell placement. It is also assumed that the input placement satisfies all requirements other than being legal. Therefore, the goal of the present invention is to obtain a legal placement of megacells that is as similar to the input placement as possible. 
   For purposes of the present invention, a placement is considered legal if all of the following conditions are satisfied: (1) no megacells intersect, (2) no megacells occupy areas covered by blockages, (3) fixed megacells are not moved, rotated or flipped, and (4) there is enough space between megacells to create a legal placement of the entire IC chip. If the input placement is legal, the process ends. Otherwise, process is carried out to place megacells to a legal placement satisfying the above requirements, with the final placement as similar to the initial placement as possible. 
   The process consists of three primary steps: 1) parameter initialization, 2) initial placement, and 3) local improvements. These steps are shown in  FIGS. 1–3 , respectively. 
   1. Algorithm Parameters Initialization— FIG. 1   
   At step  10 , the initial layout of the IC chip is input to the system, and at step  12  a list of megacells is generated. Blockages are treated as fixed megacells. The list commences with the fixed megacells, including blockages, arranged in arbitrary order. The not-fixed megacells are then arranged in order by area, commencing with the largest. There are two groups of megacell parameters: distance parameters and inflation parameters. 
   The distance parameters are side distance parameters and megacell center distance parameters. At step  14 , the side distance parameters are identified for each megacell in the design based on the initial placement. The side distance parameters are the distances, in the initial placement, from each megacell corner to each chip edge in Manhattan metrics. For each megacell M i , there are sixteen side distance parameters Ds i1 , . . . , Ds i16 . At step  16 , the megacell center distance parameters are identified for each pair of megacells (M i , M j ) in the initial placement. More particularly, a center distance parameter Dm ij  equal to the distance between megacell centers is identified in the input placement in Manhattan metrics. 
   Inflation parameters are calculated for each megacell that is not fixed in the initial design. At step  18 , a static parameter I S  is identified for all not-fixed megacells. The static inflation parameter, which may be a pre-established inflation factor, will simply inflate the size of each not-fixed megacell by a design amount. At step  20 , a dynamic inflation parameter is calculated for each not-fixed megacell. More particularly, for each half p i  of each not-fixed megacell M i , the number of pins np i  in the half is identified, and a dynamic inflation parameter for the part p i  is set equal to np i *I dyn , where I dyn  is a pre-selected dynamic inflation coefficient. The procedure is applied to four overlapping halves on the not-fixed megacell: left and right halves of the megacell, and the upper and lower halves of the megacell, to derive the dynamic inflation parameter for the two orthogonal directions of the megacell. 
   After the inflation parameters are established, each not-fixed megacell is inflated at step  22 . More particularly, if the megacell size is equal to m×n, new sizes are m′=m+2*I S +(np left +np right )*I dyn  and n′=n+2I S +(np upper +np lower )*I dyn , where m and m′ are the respective dimensions of the horizontal sides, n and n′ are the respective dimensions of the vertical sides, and np leftr *I dym , np right *I dym , np upper *I dym  and np lower *I dym  are the dynamic inflation parameters for the left, right, upper and lower halves of the megacell. The inflation thus forms a larger megacell with dimensions m′×n′ to provide enough space for wires. The process then continues to  FIG. 2 . 
   2. Initial Placement— FIG. 2   
   At step  100 , the fixed megacells are placed to their positions. This step commences with a rectangle identifying the footprint of the IC chip and initially consisting entirely of free space. The fixed megacells, including blockages, are placed in the footprint. As a result of step  100 , some of the space of the footprint is occupied by fixed megacells and blockages. At step  102 , a list of maximal free rectangles is updated. The number of maximal free rectangles grows at a rate not greater than a linear function of the placement of megacells. 
   At step  104 , a not-fixed megacell is selected from the list. The megacells are selected in the same order as they appear in the list. Since the not-fixed megacells are in order by size in the list, the largest not-fixed megacell is placed first. 
   At step  106  the megacell is placed at the next rectangle in the list of maximal free rectangles. If, at step  108 , the megacell will fit in the selected free rectangle, at step  110  it is initially placed to a corner of the rectangle, such as the upper left corner. However, if at step  108  there is not enough space in the rectangle to accommodate the megacell, the process loops back to step  106  to select the next rectangle. 
   After the not-fixed megacell is placed, transformations are performed at steps  112 – 116  to improve placement complexity. More particularly, the placement complexity is represented by the function: 
                 ∑     {   megacellsplaced   }               ⁢           ⁢     CM   i       +     CS   i       ,         
where
 
               CM   i     =       ∑     i   ≠   j               ⁢           ⁢              Dm   ij     -     Cm   ij            /     (     2   ·     M   norm       )           ,         
CS i =Σ k=i   16 |Ds ik −Cs ik |/S norm , Cm ij  is the current distance between megacells i and j in Manhattan metrics, Cs ik  is the corresponding distance between the megacell corner and chip side in Manhattan metrics, and M norm  and S norm  are norming coefficients.
 
   There are three types of transformations: shifts, rotations, and flips. Shifts are iteratively applied vertically and/or horizontally. The initial iteration shifts the megacell by a distance equal to one-half of the corresponding dimension of the free rectangle, less the minimal size of the megacell placed. The shift distance is divided by two for each subsequent iteration. 
   Transformation by rotation is in fixed angular rotations of 90°, 180°, and 270°. A transformation by flipping creates a mirror image of the megacell against the horizontal or vertical axis. 
   A transformation is performed if it reduces placement complexity. Thus, for each transformation type, at step  112  the transformation type and amount is calculated. For example, if a horizontal shift is attempted, the first iteration will shift the megacell to the right (assuming it is initially in the upper left corner) by a distance equal to one-half of the horizontal dimension of the free rectangle less the minimal size of the megacell. If the shift results in improved placement complexity, a second shift is attempted, also to the right, by one-half the distance (¼ of the dimension of the free rectangle less ½ the size of the megacell). If the second shift did not improve placement complexity, a third shift from the ending point of the second shift is attempted to the left by one-quarter the distance (e.g., to a point ⅝ the dimension of the free rectangle less ¼ the size of the megacell). The process continues until a position for the megacell is selected. 
   The transformation process continues through all three types until an optimal transformation is achieved at step  112  for all transformation types. If at step  114  the result is a better placement, the transformation is applied at step  116 . If no more applicable transformations remain, the current complexity value is memorized and the process continues to step  118 . If at step  118  the megacell placed by the process of  FIG. 2  was not the last not-fixed megacell, the process loops back to step  102  to update the free rectangle list and place the next not-fixed megacell. 
   After all not-fixed megacells are placed and the maximal free rectangles are covered, the minimal complexity value is selected, and the corresponding placement is accepted. The initial placement is completed and the process continues from step  118  to  FIG. 3 . In the worst case the placement complexity is N 3 , where N is the number of not-fixed megacells. 
   3. Local Improvements— FIG. 3   
     FIG. 3  is a flowchart of a process for local improvements of the placement of megacells. In preferred embodiments, the process is repeated for N ij  iterations, with each iteration comprising two stages: permutations and movements. In this procedure, only not-fixed megacells are considered. 
   Permutations are performed by trying to swap pairs of megacells. At step  200 , a pair of not-fixed megacells is selected. If there is enough free space in the rectangle to perform swapping, and if complexity is reduced by swapping, the permutation is accepted. If no permutation is acceptable, the process of  FIG. 3  is finished. If a permutation is accepted, movements in the form of shifts, rotations and flips are applied to the not-fixed megacells inside the free rectangle. The movement process is the same as the transformation process of  FIG. 2 , and is iteratively applied to each not-fixed megacell in the same sequence as they appear in the list as long as complexity is improved. When all megacells are transformed, the placement is finished. 
   At step  200 , a pair of not-fixed megacells within the rectangle is selected, and their positions are swapped. At step  202 , the result of the permutation is computed and compared for better results at step  206 . For example, consider not-fixed megacells A, B and C, initially positioned as A/B/C. The position of megacell A is swapped with megacell B, so placement A/B/C becomes B/A/C. If the placement complexity is better, the new position is applied at step  206 . At step  208 , if a pair of megacells has not been considered, the process loops back to step  200  where another pair of megacells, such as megacells A/C is considered. As a result of the second iteration, B/A/C might become B/C/A. The process continues until all pairs of megacells have been considered with no further improvement in complexity. Thus in the example, the B/C pair will be considered, and pairs previously considered will be re-considered. For example, the positions of megacells A and B might again be swapped if the A/C swap allows improved complexity by swapping B/A. Thus, B/C/A might become A/C/B. When the permutation process of steps  200 – 208  results in no further improvement, the process continues to step  210 . 
   At step  210 , the not-fixed megacell that is first in the list (for example megacell A) is selected, and at steps  212 ,  214  and  216  transformations are proposed and performed. Steps  212 ,  214  and  216  are the same as steps  112 ,  114  and  116  in  FIG. 2 . Thus, the megacell is shifted, rotated and/or flipped as previously described. At step  218 , if the megacell was not the last megacell in the list, the process loops back to step  200  to consider the next not-fixed megacell. Thus, the megacells are transformed in the same order that they appear in the list. After all not-fixed megacells have been considered at step  218 , the process continues to step  220 . 
   Step  220  causes the process to loops back to step  20  if the last iteration has not been completed. Thus, the permutations and transformations are re-computed in the manner previously described. The decision at step  220  is based on design parameters. For example, the number of iterations may be pre-selected, and a counter simply ends the process when the maximum number of iterations is reached. Alternatively, the amount of improvement of the complexity might be recorded for each iteration of the process, and the process ended when the improvement between successive iterations is less than some predetermined amount. 
   Although the present invention has been described with reference to preferred embodiments, workers skilled in the art will recognize that changes may be made in form and detail without departing from the spirit and scope of the invention.