Method for successive placement based refinement of a generalized cost function

• US 7,076,755 B2
• Filed: 01/27/2004
• Issued: 07/11/2006
• Est. Priority Date: 01/27/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kurzum, Zahi M., Ramji, Shyam, Ren, Haoxing, Villarrubia, Paul
• Primary Examiner(s): WHITMORE, STACY
• Application Number:
  US10/707,942
• Publication Number:
  US 20050166164A1
• Time in Patent Office: 896 Days
• Field of Search: 716 7- 10, 716 12- 13, 716/2
• US Class Current: 716/123
• CPC Class Codes: G06F 2111/06 Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA]
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A generalized method for optimizing the global placement of a VLSI chip across multiple cost metrics, such as total wire length, timing, congestion, and signal integrity is described. The method relies upon a “look ahead” technique, combined with any generic cost function that can be used to set placement directives. These placement directives include net weights and cell spreading. The method of performing the placement involves the iterative reuse of the process of successive partitioning. This iterative reuse establishes the capability of looking ahead to determine what is to happen. Based on the look ahead, it is possible to evaluate the qualities of the placement about to be generated. The method proceeds through the placement from while maintaining the current state of the placement along with the look-ahead state of the placement. Directives are generated and modified in order that the next steps applied to the current state of the placement will cause it to change to achieve an ultimate higher quality final output.

Claims

1. A method for optimizing the placement of a plurality of cells on a Very Large Scale Integrated Circuit (VLSI) chip comprising the steps of

a) subdividing the plurality of cells into partitions by performing a sequence of cuts;

b) for each of the cuts, estimating a future placement by performing additional cuts based on a result of the current cut;

c) comparing the current placement to the estimated placement; and

d) altering the priority of the placement at the current cut to ensure that the quality of the results achieved at the look ahead point is improved.

2. The method of claim 1 wherein in step b) further comprises the steps of

performing a cost function analysis to quantify the quality of the placement;

optimizing the quality of the placement; and

generating placement directives to force the placement to move in a direction specified by the optimization.

3. The method of claim 2, wherein the selection of look ahead points varies in accordance with the level of optimization required.

4. The method of claim 2, wherein the degree of look ahead is variable and varies in accordance with the needs of a specific optimization.

5. The method of claim 2, wherein multiple optimizations are part of a single placement flow wherein a single optimization has the same or different degrees of look ahead.

6. The method of claim 2 wherein the cost function defines metrics that include the level of congestion of a placement and timing considerations.

7. The method of claim 2 wherein the optimization function identifies specific improvements that are required by the placement.

8. The method of claim 7 wherein the optimization function for timing comprises logic restructuring, repowering, and buffer insertion.

9. The method of claim 7 wherein the optimization function for congestion includes self-spreading of cells.

10. The method of claim 2 wherein the directives drive the placement process in a direction indicated by specific optimizations.

11. The method of claim 10 wherein the directives driving the placement towards a timing optimization comprise net weighting, capacitance, target generation, cell to cell affinities and cell to area affinities.

12. The method of claim 10 wherein the directives driving the placement towards a congestion optimization comprise the generation of reserve areas and cell expansion.

13. A method for optimizing the placement of a plurality of cells on a VLSI chip comprising the steps of:

a) subdividing the plurality of cells into partitions by performing a sequence of cuts;

b) iteratively managing the sequence of cuts to perform a look ahead operation, wherein the look ahead operation comprises the steps of;

b1) performing a global routing,

b2) evaluating the global routing congestion, and

b3) performing a cell expansion an blockage insertion where a congestion is encountered;

c) returning to the cut from where the look ahead operation was initiated by comparing the original placement with the cut provided by the look ahead operation; and

d) altering the priority of the placement to ensure that the quality of the results achieved at the look ahead point is improved.

14. A method for optimizing the placement of a plurality of cells on a VLSI chip comprising the steps of:

a) subdividing the plurality of cells into partitions by performing a sequence of cuts;

b) iteratively managing the sequence of cats to perform a look ahead operation, wherein the look ahead operation comprises the steps of;

b1) performing a timing analysis of the entire plurality of cells;

b2) repowering and inserting buffers in a netlist to improve the timing and for determining which timing problems are related to the placement; and

b3) generating net weights for critical nets;

c) returning to the cut from where the look ahead operation was initiated by comparing the original placement with the cut provided by the look ahead operation; and

d) altering the priority of the placement to ensure that the quality of the results achieved at the look ahead point is improved.

15. A program storage device readable by a machine, tangibly, embodying a program of instructions executable by the machine to perform method steps for performing static timing analysis of a digital system in the presence of a plurality of global sources of delay variation, said method steps comprising:

a) subdividing the plurality of cells into partitions by performing a sequence of cuts;

b) for each of the cuts, estimating a future placement by performing additional cuts based on a result of the current cut;

c) comparing the current placement to the estimated placement; and

d) altering the priority of the placement to ensure that the quality of the results achieved at the look ahead point is improved.