Computer implemented method for producing optimized cell placement for integrated circiut chip

• US 5,636,125 A
• Filed: 11/13/1995
• Issued: 06/03/1997
• Est. Priority Date: 04/19/1994
• Status: Expired due to Term

• Current Assignee: Bell Semiconductor, LLC (Hilco Inc. (d/b/a Hilco Global))
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Scepanovic, Ranko, Koford, James S., Boyle, Douglas B., Rostoker, Michael D., Jones, Edwin R.
• Primary Examiner(s): Trammell, James P.
• Application Number:
  US08/559,206
• Time in Patent Office: 568 Days
• Field of Search: 364/468, 364/488-493, 364/468.03, 364/468.2, 364/468.28, 395/10, 395/13
• US Class Current: 700/121
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

In a physical design automation system for producing an optimized cell placement for an integrated circuit chip, a placement optimization methodology is decomposed into a plurality of cell placement optimization processes that are performed simultaneously by parallel processors on input data representing the chip. The results of the optimization processes are recomposed to produce an optimized cell placement. The fitness of the optimized cell placement is analyzed, and the parallel processors are controlled to selectively repeat performing the optimization processes for further optimizing the optimized cell placement if the fitness does not satisfy a predetermined criterion. The system can be applied to initial placement, routing, placement improvement and other problems. The processors can perform the same optimization process on different placements, or on areas of a single placement. Alternatively, the processors can perform different optimization processes simultaneously on a single initial placement, with the resulting processed placement having the highest fitness being selected as the optimized placement. The processors can further selectively reprocess areas of a placement having high cell interconnect congestion or other low fitness parameters.

Claims

1. A computer implemented method for producing an optimized cell placement for an integrated circuit chip, comprising the steps of:

(a) decomposing a placement optimization methodology into a plurality of cell placement optimization processes;

(b) performing said optimization processes simultaneously on input data representing said chip;

(c) recomposing results of said optimization processes and producing an optimized cell placement corresponding thereto;

(d) analyzing a fitness of said optimized cell placement;

(e) selectively repeating performing said optimization processes for further optimizing said optimized cell placement if said fitness does not satisfy a predetermined criterion;

(f) identifying low fitness areas of said optimized placement; and

(g) selectively repeating performing said optimization processes on said low fitness areas respectively.

2. A method as in claim 1, in which:

step (f) comprises defining a plurality of movable windows that delineate subsets of cells in said low fitness areas respectively; and

step (g) comprises repeating performing said optimization processes on said subsets delineated by said windows respectively.

3. A method as in claim 1, in which:

step (f) comprises identifying cells in said low fitness areas having high interconnect congestion; and

step (g) comprises performing the substeps, for each cell, of;

(h) computing a centroid as a first predetermined function of locations of cells to which said each cell is connected;

(i) computing a first distance from a current location of said each cell to said centroid;

(j) computing a second distance as a second predetermined functions of said first distance; and

(k) moving said each cell from said current location toward said centroid by said second distance.

4. A method as in claim 1, in which:

step (a) comprises generating a plurality of initial placements;

step (b) comprises performing said cell optimization processes on said initial placements to produce a plurality of processed cell placements respectively; and

step (c) comprises designating a processed cell placement having a highest fitness as said optimized cell placement.

5. A method as in claim 1, in which steps (b), (e) and (g) each comprise performing said optimization processes individually.

6. A method as in claim 1, in which steps (b) (e) and (g) each comprise performing said optimization processes as including genetic alteration.

7. A method as in claim 1, in which steps (b) (e) and (g) each comprise performing said optimization processes as including simulated annealing.

8. A method as in claim 1, in which:

step (a) comprises the substeps of;

(h) generating an initial placement; and

(i) dividing said initial placement into a plurality of areas; and

steps (b), (e) and (g) each comprise performing said optimization processes on said areas respectively.

9. A method as in claim 1, in which:

step (a) comprises the substeps of;

(h) generating an initial placement; and

(i) dividing said initial placement into a plurality of contiguous areas; and

steps (b), (e) and (g) each comprise performing said optimization processes on said areas respectively.

10. A method as in claim 1, in which:

step (a) comprises generating a plurality of different initial placements; and

steps (b), (e) and (g) each comprise performing said optimization processes on said initial placements respectively.

11. A method as in claim 1, in which:

step (a) comprises providing a plurality of worker processors for independently performing said optimization processes and producing results, and a host processor for distributively assigning said optimization processes to the worker processors in response to work requests received therefrom; and

steps (b), (e) and (g) each comprise controlling each worker processor to send a work request to the host processor after completing an optimization process.

12. A computer implemented method for producing an optimized cell placement for an integrated circuit chip, comprising the steps of:

(a) decomposing a placement optimization methodology into a plurality of cell placement optimization processes;

(b) performing said optimization processes simultaneously on input data representing said chip;

(c) recomposing results of said optimization processes and producing an optimized cell placement corresponding thereto;

(d) analyzing a fitness of said optimized cell placement; and

(e) selectively repeating performing said optimization processes for further optimizing said optimized cell placement if said fitness does not satisfy a predetermined criterion, in which;

step (a) comprises generating a plurality of initial placements;

step (b) comprises performing said cell optimization processes on said initial placements to produce a plurality of processed cell placements respectively;

step (c) comprises designating a processed cell placement having a highest fitness as said optimized cell placement; and

steps (b) and (e) each comprise performing said optimization processes as including genetic crossover between said initial placements.

13. A computer implemented method for producing an optimized cell placement for an integrated circuit chip, comprising the steps of:

(a) decomposing a placement optimization methodology into a plurality of cell placement optimization processes;

(b) performing said optimization processes simultaneously on input data representing said chip;

(c) recomposing results of said optimization processes and producing an optimized cell placement corresponding thereto;

(d) analyzing a fitness of said optimized cell placement; and

(e) selectively repeating performing said optimization processes for further optimizing said optimized cell placement if said fitness does not satisfy a predetermined criterion, in which;

said optimization processes comprise different algorithms respectively;

step (a) comprises generating an initial placement;

step (b) comprises performing said cell optimization processes on said initial placement to produce a plurality of processed cell placements respectively; and

step (c) comprises designating a processed cell placement having highest fitness as said optimized cell placement.

14. A computer implemented method for producing an optimized cell placement for an integrated circuit chip, comprising the steps of:

(a) decomposing a placement optimization methodology into a plurality of cell placement optimization processes;

(b) performing said optimization processes simultaneously on input data representing said chip;

(c) recomposing results of said optimization processes and producing an optimized cell placement corresponding thereto; and

(d) analyzing a fitness of said optimized cell placement; and

(e) selectively repeating performing said optimization processes for further optimizing said optimized cell placement if said fitness does not satisfy a predetermined criterion, in which;

step (a) comprises the substeps of;

(f) generating an initial placement; and

(g) dividing cells of said initial placement into a plurality of nets of interconnected cells; and

step (b) comprises performing said optimization processes on said nets respectively.

15. A method as in claim 14, in which said optimization processes comprise cell interconnect routing.

16. A computer implemented method for producing an optimized cell placement for an integrated circuit chip, comprising the steps of:

(a) decomposing a placement optimization methodology into a plurality of cell placement optimization processes;

(b) performing said optimization processes simultaneously on input data representing said chip;

(c) recomposing results of said optimization processes and producing an optimized cell placement corresponding thereto; and

(d) analyzing a fitness of said optimized cell placement; and

(e) selectively repeating performing said optimization processes for further optimizing said optimized cell placement if said fitness does not satisfy a predetermined criterion, in which;

step (a) comprises the substeps of;

(f) generating an initial placement; and

(g) dividing cells of said initial placement into a plurality of groups of cells in accordance with a predetermined hierarchial organization; and

step (b) comprises performing said optimization processes on said groups respectively.

17. A system as in claim 16, in which said optimization processes comprise cell interconnect routing.