Abstract:
Objects are placed in a rectangle and their coordinates of the objects and are adjusted to establish a substantially uniform density of objects in the rectangle. The evaluation of coordinates is performed by placing the wires between cells coordinates and adjusting the cell coordinates to connect the cells to the wires. The substantially uniform density is achieved by dividing the rectangle into first and second rectangles having equal free areas and into third and fourth rectangles having equal areas of objects. The coordinates of the objects are adjusted based on boundaries between the first and second rectangles and between the third and fourth rectangles.

Description:
FIELD OF THE INVENTION  
       [0001]     This invention relates to design of integrated circuits (ICs), and particularly to cell placement during floorplan creation.  
       BACKGROUND OF THE INVENTION  
       [0002]     The placement of cells in an IC chip design during development can be summarized as encompassing three stages: During a first stage, the size of the chip is selected and the I/O (input/output) cells are placed. The I/O cells are the cells having pins that connect the chip to the outside world. During a second stage, placement of megacells (such as memories, large blocks of cells, etc.) is accomplished. The third stage comprises the placement of all other cells, such as logic cells, flip-flops, latches, etc. The first two stages are usually referred to as the floorplan development, and the third stage is often referred to as the placement stage.  
         [0003]     Integrated circuits are used in a wide range electronic devices produced by a large number of device manufacturers. In practice, ICs are seldom manufactured (fabricated) by the electronic device manufacturer. Instead ICs are manufactured by an IC foundry to the specifications of the electronic device manufacturer. The design of the IC is usually the result of corroboration between the device manufacturer and the IC foundry. Hence, the device manufacturer is a customer to the foundry and the foundry develops the chip for the customer. The first stage of choosing the size of the chip and the placement of its I/O cells is usually performed by the customer to meet the customer&#39;s requirements of circuit form, fit and function. The second and third stages are performed by the developer, usually to meet the foundry&#39;s processes. In most cases the developer places the megacells manually in accordance with its own heuristic suggestions. Then the developer finishes the process of chip creation using computer tools.  
         [0004]     Upon completion of the chip design, the developer decides whether the chip design is acceptable; that is, whether it satisfies certain specifications, such as timing, etc. If it does not, the designer returns to the second stage, remakes the floorplan, and repeats the process until a suitable chip is obtained.  
         [0005]     One criterion for determined whether or not a chip design is acceptable is based on the presence or absence of timing violations. The present invention is directed to a process, and to a computer program that causes a computer to carry out the process, for placing megacells during creation of the floorplan to satisfy timing requirements.  
       SUMMARY OF THE INVENTION  
       [0006]     In a first embodiment of the invention, objects are placed in a rectangle. The coordinates of the objects are evaluated and are adjusted to establish a substantially uniform density of objects in the rectangle.  
         [0007]     In some embodiments, the evaluation of coordinates is performed by evaluating coordinates of all wires connected to the cells and evaluating cell coordinates based on the wire coordinates. In some embodiments, the wires are placed between cells coordinates and the cell coordinates are then adjusted to connect the cells to the wires.  
         [0008]     In other embodiments, the adjustment of the coordinates is performed by dividing the rectangle into first and second rectangles having equal free areas. The rectangle is separately divided into third and fourth rectangles having equal areas of objects. The coordinates of the objects are adjusted based on boundaries between the first and second rectangles and between the third and fourth rectangles.  
         [0009]     In other embodiments, the objects are standard cells and megacells of an integrated circuit. Clusters of standard cells are created by creating a cluster for each flip-flop cell, creating a cluster for each logic cell in a path that does not terminate at a flip-flop cell, and assigning each logic cell in a path that terminates at a flip-flip cell to the cluster of a flip-flop cell at the termination of the respective path.  
         [0010]     A second embodiment of the present invention is a computer readable program containing computer readable code that causes a computer to perform the above process. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0011]      FIG. 1  is a flowchart of a process for cell placement according to an embodiment of the present invention.  
         [0012]      FIGS. 2-4  are flowcharts of portions of the process shown in  FIG. 1 .  
         [0013]      FIG. 5  is a diagram useful in explaining a distribution of cells used in the present invention. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0014]     The present invention is directed to a process and computer program that places cells, particularly megacells, during floorplan creation to satisfy timing restrictions. More particularly, cells in paths with large delays are differentiated from cells in paths with small delays. The cells in paths with large delays are identified as the most critical cells. If several cells belong to one path with a large delay, these cells are placed as close to each other as possible, thus reducing the lengths of wires that connect these cells. Vice versa, plural cells belonging to a path with a small delay may be placed at large distances from each other.  
         [0015]     For purposes of explanation of the invention, consider a chip that contains I/O cells, megacells, flip-flops and logic cells. Assume further that the chip has a rectangular configuration and contains blockages, which are rectangular fragments of the chip where cells may not be placed. Assume too that all the I/O cells are already placed and are fixed on respective positions on the chip. The area of the chip that is not covered by any blockage or a fixed cell is referred to as a free area, and is available for cell placement. The flip-flops and logic cells are sometimes herein referred to as standard cells.  
         [0016]      FIG. 1  is a flowchart of a process of placement of cells or megacells in accordance with a preferred embodiment of the present invention. At step  10 , the chip design is input to the computer system. Preferably, the chip design has already completed the first stage of the floorplan creation and includes placed I/O cells. Only I/O cells are fixed in place. Therefore, only the megacells and standard cells that are not I/O cells are not fixed at this point. Additionally, the values of K, M and N are input into the computer for use in connection with the process, to be explained.  
         [0017]     At step  12 , clusters of standard cells are created.  FIG. 2  is a detailed flowchart of step  12 . Most of the cells in a chip are standard, composed of logic cells and flip-flops. As will be more fully understood hereinafter, the process does not consider standard cells separately. Instead, the present invention deals with clusters of standard cells composed of one or several standard cells (logic cells and flip-flops). Because the number of clusters of the standard cells is significantly less than the total number of standard cells in the chip, the process of megacell placement in accordance with the present invention can be accelerated.  
         [0018]     Referring to  FIG. 2 , at step  40 , the values of delays of each of the paths of the chip are evaluated. In the initial iteration of the process, there may not be any values to evaluate since there has been no chip placement. In such a case, values of delays in average cases can be employed, and modified as the placement continues. At step  42  a cluster is created for each flip-flop. At step  44  a logic cell is selected.  
         [0019]     The remainder of the process of  FIG. 2  concerns the decision as to whether to add the logic cell to an existing cluster, or create a new cluster for the cell. This part of the process begins at step  46  that identifies the timing paths that contains the logic cell. Particularly, if at step  46  there is no path that begins or ends on a flip-flop cell, then at step  48  a new cluster is created about the logic cell. If at step  46  a path exists containing the logic cell that begins or ends at a flip-flop, then at step  50  the path is selected that begins or ends at a flip-flop and that has the maximal delay.  
         [0020]     At step  52 , if the path containing maximal delay does not begin and end at respective flip-flops (i.e., both ends of the maximal delay path are not flip-flops, so the decision at step  52  is “no”), then at step  54  the logic cell is added to the cluster of the one identified flip-flop. Otherwise, if both paths terminate at flip-flops at step  52  (the decision at step  52  is “yes”), then at step  56  the logic cell is added to the cluster of the closest flip-flop. A logic cell is “close” to a flip-flop cell if the value of the delay of the path fragment between the logic cell and one terminating flip-flop cell is smaller than the delay value of the other path fragment to the other terminating flip-flop cell.  
         [0021]     Returning to  FIG. 1 , at step  14 , all megacells and clusters of standard cells are placed at the center of the chip. At loop  16  the coordinates of the wires and cell/clusters are evaluated. More particularly, at step  18 , new wire and new cell/cluster coordinates are evaluated as more fully described in association with  FIG. 3 .  
         [0022]     As shown in  FIG. 3 , at step  60  the pins P 1 , P 2 , . . . , P s  of the megacells, the I/O cells and the standard cell clusters that are connected to each wire W are evaluated. For a given pin P i  having coordinates (x i , y i ) new coordinates are assigned to the wire W as follows:  
       x   =         1   S     ⁢       ∑     i   =   1     S     ⁢           ⁢       x   i     ⁢           ⁢   y         =       1   S     ⁢       ∑     i   =   1     S     ⁢           ⁢     y   i               
 
 This means that wire W is placed between the pins that are connected to this wire. It will be appreciated that wires do not ordinarily actually have coordinates of their own. Instead, the term “coordinates of wires” is used herein to simplify the explanation of the process. 
 
         [0023]     At step  62 , the cell/cluster coordinates are evaluated based on wire coordinates. More particularly, new coordinates of cells and clusters of the standard cells are evaluated based on the coordinates of wires that are connected to its pins. This step is applied to all standard cells and to megacells that are not fixed. This step is not applied to cells whose positions are fixed, namely I/O cells and fixed megacells.  
         [0024]     Consider some cell or cluster of the standard cells having wires W 1 , W 2 , . . , W t  connected to the pins of the cell/cluster. The coordinates of wire W i  are (x i , y i ) and maximal delay of the path that contains wire W i  is D i . New coordinates of the cell/cluster are calculated as follows:  
       x   =           (       ∑     i   =   1     t     ⁢           ⁢       D   i     ⁢     x   i         )     /     (       ∑     i   =   1     t     ⁢           ⁢     D   i       )       ⁢           ⁢   y     =       (       ∑     i   =   1     t     ⁢           ⁢       D   i     ⁢     y   i         )     /     (       ∑     i   =   1     t     ⁢           ⁢     D   i       )             
 
 Note that moving the cell/cluster takes into account the delay values; the greater the delay value of the path that contains the wire W i , the closer the new coordinates of the cell/cluster are to the coordinates of the wire W i . 
 
         [0025]     Returning to  FIG. 1 , at step  20 , a decision is made as to whether step  18  has been performed K times. If not, the process loops back to step  18  and repeats the evaluation of wire and cells/cluster coordinates described in connection with  FIG. 3  until performed K number of times.  
         [0026]     Another loop  22  is formed that includes steps  24  and  26 . Step  24  adjusts the free area density so that it is substantially uniform across the chip. Step  24  is described in greater detail in association with  FIG. 4 , and may be explained with reference to  FIG. 5 .  
         [0027]     After re-calculation of cell coordinates at loop  16 , the cells may become distributed non-uniformly across the chip. This means that some fragments of the chip may be empty, having no cells, whereas other fragments may be densely packed. The process of  FIG. 4  executes movements of the cells and clusters, but does not change the relative positions of the cells and clusters. If a cell/cluster is to a given side of another cell/cluster before applying the process of  FIG. 4 , that same relative position is retained on execution of the process of  FIG. 4 .  
         [0028]     The process of  FIG. 4  is a binary recursive algorithm. Shown in  FIG. 4  is the procedure UNIFORM_DENSITY(R), where R is some rectangular fragment of the chip. The same algorithm is applied to the entirety of the chip and is designated UNIFORM_DENSITY(total chip).  
         [0029]     At step  70 , a rectangle R is defined (shown in  FIG. 5 ) having left and right edges a and b and bottom and top edges c and d. Coordinates x and y lie in rectangle R such that a≦x≦b and c≦y≦d. At step  72 , if the free area of rectangle R is less than some minimum, for example 0.1%, of the total area of the chip, the process ends at step  74  and rectangle R is considered as having substantially uniform density distribution. If the free area of rectangle R is greater than the threshold minimum, the process continues to step  76  where rectangle R is divided by its longest dimension into two rectangles R 1  and R 1  having equal free areas. The example of  FIGS. 4 and 5  is of a rectangle whose greatest dimension is horizontal, rather than vertical. Thus, (b−a)≧(d−c) . Consequently, rectangle R is divided vertically at line e to form rectangles R 1  and R 2  which are not necessarily the same physical size but they are equal in free area. 
 
R 1 ={a≦x≦e,c≦y≦d}, R 2 ={e≦x≦b,c≦y≦d}. 
 
 (In the case (b−a)≦(d−c) the vertical dimension of rectangle R will be greater than the horizontal dimension, in which case the rectangle will be split horizontally into rectangles R 1  and R 2  that are oriented vertically to each other. The process would then be carried out in the same manner herein described, exchanging the coordinates x and y.) 
 
         [0030]     At step  78 , rectangle R is split into two rectangles R 3  and R 4  by a vertical line f such that the area of not-fixed cells and clusters in rectangle R 3  is equal to the area of not-fixed cells and clusters in rectangle R 4 . 
 
R 3 ={a≦x≦f,c≦y≦d}, R 4 ={f≦x≦b,c≦y≦d}. 
 
 Again, the physical sizes of rectangles R 3  and R 4  are not necessarily the same; they only contain the same areas of non-fixed cells and clusters. 
 
         [0031]     At step  80 , if e=f , then the density of non-fixed cells and clusters is substantially uniform though the long dimension of rectangle R (between a and b in the example), and at step  82  the process of  FIG. 4  ends. If e≠f, as shown in  FIG. 5 , there is an unequal distribution of non-fixed cells and clusters in the long dimension across rectangle R. Consequently, at step  84  the cell/cluster coordinates of each rectangle R 3  and R 4  is adjusted based on the values of the rectangle edges a and b and the division lines e and f. More particularly, the x coordinate of each cell/cluster of rectangle R 3  is changed as  
       x   =     a   +         (     e   -   a     )       (     f   -   a     )       ⁢     (     x   -   a     )             
 
 and the x component of each cell/cluster of rectangle R 4  is changed as  
       x   =     b   -         (     b   -   e     )       (     b   -   f     )       ⁢       (     b   -   x     )     .             
 
 At step  86 , the procedure of steps  70 - 84  is repeated, using rectangles R 1  and R 2 . 
 
         [0032]     Optionally, the procedure of  FIG. 4  is repeated for the short dimension of rectangle R. In the example, the y coordinates of cells/clusters are thus adjusted.  
         [0033]     Returning again to  FIG. 1 , at step  26 , a decision is made as to whether loop  16  and step  24  have been performed M number of times. If not, the process loops back to step  18  to repeat step  18  K number of times, then perform another step  24  to make the free area density uniform, repeating the process M number of times. Once the loop  22 , including the K sub-loop  16  have been performed M times at step  26 , then at step  28  the new wire and new cell/cluster coordinates are evaluated.  
         [0034]     More particularly, with reference to  FIG. 3 , the process of step  28  evaluates new wire coordinates based on cell coordinates as described at step  60  in  FIG. 3 . However, step  62  is slightly different in that at step  28  the evaluation of new cell coordinates based on wire coordinates is applied to all megacells rather than clusters of standard cells and non-fixed megacells as was done in step  18 . Otherwise, step  62  of step  26  is the same as previously described.  
         [0035]     At step  30 , all megacells that had been previously fixed are unfixed, and the megacells are placed in the coordinates that were evaluated at step  28 . The megacells are then fixed to their new positions.  
         [0036]     At step  32  a decision is made as to whether loop  22 , including sub-loop  16  and steps  28  and  30  have been performed N number of times. If not, the process returns to step  18 , re-iterating through loop  16  K number times, iterating through loop  22  M number of times until N iterations have been completed at step  32 . Then at step  34 , the megacell coordinates are output.  
         [0037]     The present invention provides a process for placing megacells, such as memories, in chips. In one embodiment, the parameters N=10, M=5, K=2 were found to be quite satisfactory. The process finds “most attractive” coordinates for placement of megacells. However, in some cases the found coordinates may violate certain design rules of the fabrication technology. In such a case, it may be necessary to subsequently apply tools for legal placement of the megacells that is close to the “most attractive” coordinates obtained by the present process. Such tools to accomplish legal placement are well known in the art.  
         [0038]     In preferred embodiments, the process is carried out by a computer employing a computer program comprising computer readable program code recorded or embedded on a computer-readable medium, such as a recording disk or other readable device.  
         [0039]     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.