ANALYTICAL GLOBAL PLACEMENT FOR AN INTEGRATED CIRCUIT

• US 20090031269A1
• Filed: 07/07/2008
• Published: 01/29/2009
• Est. Priority Date: 07/27/2007
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: SpringSoft, Inc. (Synopsys Incorporated)
• Inventors: Jiang, Che-Wei, Chen, Tung-Chieh
• Granted Patent: US 7,984,410 B2
• Time in Patent Office: Days
• US Class Current: 716/119
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A placer produces a global placement plan specifying positions of cell instances to be interconnected by nets within an integrated circuit (IC) by initially clusterizing cell instances to form a pyramidal hierarchy of blocks and generating an initial global placement plan specifying a position of each block at a highest level of the hierarchy. The placer then declusterizes the global placement plan by replacing the highest level blocks with their component blocks and then improves the routability of the global placement plan by iteratively moving specified block positions in directions and by distances dynamically determined by analyzing the global placement plan and an objective function having a total wirelength term and having a bin density term reflecting density of blocks in specified areas (bins) of the IC. The placer iteratively repeats the declusterization and routability improvement process until the global placement plan specifies positions of all blocks residing at the lowest level of the hierarchy, with weighting of the bin density term adjusted when necessary during each iteration of the routability improvement process to provide sufficient white space in each bin. The placer employs a look-ahead legalization technique to move low level blocks to legal positions during later iterations of the plan improvement process.

Claims

1. A method for specifying positions of cell instances to be interconnected by nets within an integrated circuit (IC) to be fabricated, the IC having defined legal and illegal positions for cell instances, the method comprising the steps of:

a. generating a global placement plan specifying positions for the cell instances within the IC;

b. iteratively modifying the global placement plan to move specified cell instance positions in directions and by distances determined by analyzing the global placement plan and an objective function that is a function of the specified cell instance positions, wherein a portion of the specified cell instance positions are illegal positions;

c. look-ahead legalizing the global placement plan produced at step b by modifying the global placement plan to reduce the portion of specified cell instance positions that are in illegal positions;

d. modifying the objective function; and

e. iteratively repeating steps b, c and d,

2. The method in accordance with claim 1 further comprising the step of:

f. legalizing the global placement plan produced during one iteration of step c such that every cell instance position it specifies is in a legal position.

3. The method in accordance with claim 1 further comprising the step of

g. defining the IC as being divided into an array of bins,

wherein the objective function comprises weighted wirelength and bin density terms,

wherein the wirelength term is a function of estimated total wirelength of the nets when the cell instances are positioned as specified by the global placement plan, and

wherein the density term is a function of cell instance density in each bin when the cell instances are positioned as specified by the global placement plan.

4. The method in accordance with claim 3 further comprising the step of:

h. specifying a maximum amount of available space M_b within each bin b for accommodating cell instances,

wherein the density term is a function of a difference between areas of cell instances specified by the global placement plan as being positioned within each bin b and the specified maximum amount of available space M_b for each bin b.

5. The method in accordance with claim 4, where the objective function is modified at step d by altering relative weighting of its wirelength and bin density terms.

6. The method in accordance with claim 5 wherein step a comprises the substeps of:

a1. defining a hierarchy of blocks wherein each block residing at a lowest level of the hierarchy consists of a separate one of the cell instances, wherein all blocks residing at each level of the hierarchy other than a highest level form blocks at a next higher level of the hierarchy, such that at least one block residing at each level of the hierarchy comprises a plurality of component blocks residing at a next lower level of the hierarchy;

a2. generating the global placement plan containing a position specification for each block residing at the highest level of the hierarchy, wherein the position specification for each block specifies a position within the IC for that block;

a3. modifying the global placement plan to replace a position specification for at least one block formed by a plurality of component blocks with a separate position specification for each of its component blocks;

a4. modifying the global placement plan by altering its position specifications to move specified positions of blocks within the IC by distances and in directions determined by analyzing the global placement plan and the objective function; and

a5. iteratively repeating steps a3 and a4 until the global placement plan includes position specifications for all blocks residing at the lowest level of the hierarchy, thereby specifying a position with the IC for each individual cell instance.

7. The method in accordance with claim 6 wherein step a4 comprises the substeps of:

a41. initializing weighting of the wirelength and bin density terms of the objective function;

a42. analyzing the objective function and the global placement plan to determine distances and directions within the IC to move specified block positions so as to improve routability of the global placement plan as indicated by the value of the objective function;

a43. modifying the global placement plan to move specified positions of blocks in accordance with distances and directions determined at step a42;

a44. iteratively repeating steps a42 and a43 to maximize routability indicated by the value of the objective function.

8. The method in accordance with claim 7 where step a4 further comprises the steps of:

a45. altering weighting of the objective function'"'"'s wirelength and bin density terms to increase an influence on objective function value of the bin density term relative to an influence on objective function value of the wirelength term; and

a46. iteratively repeating steps a42 through a45 until each bin has at least a specified amount of unoccupied space.

9. The method in accordance with claim 8,

wherein at least one of the blocks is a preplaced block that is constrained to be placed a particular positions within the IC and all other blocks are moveable blocks each of which may be placed at any of a variety of locations within the IC, and

wherein at step a46 each bin is determined to have at least the specified amount of unoccupied space by computing an overflow ratio (OFR) for that bin and determining the total overflow ratio (TOFR) of all bins is higher than a predetermined minimum value, wherein the OFR of bin b is defined as:

OFR_b=max(0,Occupied_Area−

Available_Area)/Available_Area)

and TOFR for all bins is defined as;

10. The method in accordance with claim 8 wherein the weighting of the wirelength and bin density terms is initialized at step a41 such that the wirelength term has a greater influence on the objective function value than the bin density term

11. The method in accordance with claim 8 wherein the objective function is:

12. The method in accordance with claim 11 where the total wirelength W(x, y) of each net e of the set E of all nets interconnecting blocks k positioned a coordinates (x_k, y_k) is determined in accordance with

13. The method in accordance with claim 11 where total wirelength W(x, y) of all nets e interconnecting blocks k positioned at coordinates (x_k, y_k) is determined in accordance with

14. The method in accordance with claim 8 wherein the distance α

_i that blocks are to be moved are determined at step d2 in accordance with the expression

15. The method in accordance with claim 14

wherein

d_i=B_id_i−

1−

f′

(x_i)

wherein

16. The method in accordance with claim 1 wherein step a comprises the substeps of:

a1. defining a hierarchy of blocks wherein each block residing at a lowest level of the hierarchy consists of a separate one of the cell instances, wherein all blocks residing at each level of the hierarchy other than a highest level form blocks at a next higher level of the hierarchy, such that at least one block residing at each level of the hierarchy comprises a plurality of component blocks residing at a next lower level of the hierarchy;

a2. generating the global placement plan containing a position specification for each block residing at the highest level of the hierarchy, wherein the position specification for each block specifies a position within the IC for that block;

a3. modifying the global placement plan to replace a position specification for at least one block formed by a plurality of component blocks with a separate position specification for each of its component blocks;

a4. modifying the global placement plan by altering its position specifications to move specified positions of blocks within the IC by distances and in directions determined by analyzing the global placement plan and the objective function; and

a5. iteratively repeating steps a3 and a4 until the global placement plan includes position specifications for all blocks residing at the lowest level of the hierarchy, thereby specifying a position with the IC for each individual cell instance.