Optimization processing for integrated circuit physical design automation system using parallel moving windows

• US 5,870,313 A
• Filed: 12/09/1997
• Issued: 02/09/1999
• 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): Teska, Kevin J.
• Assistant Examiner(s): PHAN, THAI Q
• Application Number:
  US08/987,865
• Time in Patent Office: 427 Days
• Field of Search: 364/489, 364/490, 364/491
• US Class Current: 716/122
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

One or more non-overlapping moving windows are positioned over a placement of cells for an integrated circuit chip to delineate respective subsets of cells. A fitness improvement operation such as simulated evolution is performed on the subsets simultaneously using parallel processors. The windows are either moved to specifically identified high interconnect congestion areas of the placement, or are moved across the placement in a raster type pattern such that each area of the placement is processed at least once. Exchange of misplaced cells between subsets can be accomplished by dimensioning the windows and designing the window movement pattern such that the subsets overlap. Alternatively, such exchange can be accomplished by using two sets of windows of different sizes. As yet another alternative, the improvement operation can allow misplaced cells to move to a border area outside a window. Each misplaced cell is placed on a list, and then moved to the centroid of a net of cells to which it is connected, which can be outside the subset that originally included the misplaced cell.

Claims

1. A physical design automation system for improving a cell placement of a circuit layout design, comprising:

a controller for defining a movable window that delineates subsets of cells of said circuit layout design; and

a computer for performing a predetermined placement improvement operation on said subsets,

wherein the controller moves said window to locations in said circuit layout design that are selected in accordance with a predetermined local fitness criterion.

2. A system as in claim 1, in which said local fitness criterion comprises cell interconnect congestion in said layout design.

3. A system as in claim 1, in which

said local fitness criterion comprises identifying low fitness areas in said circuit layout design;

and

the controller selects said locations such that said window successively delineates said low fitness areas.

4. A physical design automation system for improving a cell placement of a circuit layout design, comprising:

a controller for defining a movable window that delineates subsets of cells of said circuit layout design; and

a computer for performing a predetermined placement improvement operation on said subset,

wherein the controller successively moves said window to a plurality of predetermined locations in said circuit layout design, and

wherein the computer successively applies said improvement operation to subsets that are delineated by said window in said locations respectively.

5. A system as in claim 4, in which said locations are selected such that each cell is delineated by said window and the computer performs said improvement operation thereon at least once.

6. A system as in claim 4, in which said window is dimensioned and said locations are selected such that adjacent subsets partially overlap.

7. A system as in claim 4, in which:

the controller further successively moves a second window having a different size than said window to a plurality of predetermined second locations in said circuit layout design;

the computer successively performs said improvement operation on said second subsets that are delineated by said second window in said second locations respectively.

8. A system as in claim 7, in which said locations and said second locations are selected such that said subsets partially overlap said second subsets.

9. A system as in claim 8, in which:

said window is dimensioned and said locations are selected such that said subsets are contiguous; and

said second window is dimensioned and said second locations are selected such that said second subsets are contiguous.

10. A system as in claim 4, in which:

the controller further defines a second window that is integrally movable with and circumscribes said window such that a border area is defined between peripheries of said window and said second window; and

the computer performs said improvement operation such that misplaced cells of said circuit layout design are allowed to move from said window into said border area.

11. A system as in claim 10, further comprising a memory for storing a list of said misplaced cells.

12. A system as in claim 10, in which the computer further computes and moves said misplaced cells to new locations respectively in accordance with a predetermined function.

13. A system as in claim 12, in which said predetermined function comprises computing each new location as a centroid of a net of cells to which a respective misplaced cell is connected.

14. A system as in claim 10, in which the computer further computes new locations for said misplaced cells in accordance with a predetermined function and attempts to move said misplaced cells to said new locations respectively.

15. A system as in claim 14, in which said predetermined function comprises computing each new location as a centroid of a net of cells to which a respective misplaced cell is connected.

16. A system as in claim 14, in which the computer further excludes a misplaced cell from a subsequent improvement operation if an attempt to move said misplaced cell to a new location is unsuccessful.

17. A system as in claim 16, in which the computer determines that an attempt to move a misplaced cell to a new location is unsuccessful if said new location is already occupied by another cell of said circuit layout design.

18. A system as in claim 16, in which:

said predetermined function comprises computing a new location as a centroid of a net of cells to which a respective misplaced cell is connected; and

the computer computes said centroid as comprising any of said misplaced cells that are included in said net in said new locations thereof.

19. A physical design automation system for improving a cell placement of a circuit layout design, comprising:

a controller for defining a movable window that delineates subsets of cells of said circuit layout design; and

a computer for performing a predetermined placement improvement operation on said subsets,

wherein the controller further defines a movable second window that does not overlay said window and delineates second subsets of cells of said circuit layout design, and

wherein the computer comprises first and second processors for simultaneously performing said improvement operation on said subsets and said second subsets respectively.

20. A system as in claim 19, in which the controller moves said window and said second window integrally.

21. A method of performing a predetermined operation on a permutation of a predetermined number of entities of a circuit layout design, comprising the steps of:

(a) defining a window that variably delineates subsets of entities of said circuit layout design; and

(b) performing said predetermined operation on said subsets, wherein said entities are arranged in said circuit layout design in a predetermined pattern,

step (a) comprises moving said window to a plurality of predetermined locations in said pattern, and

step (b) comprises successively performing said operation on said subsets that are delineated by said window in said locations respectively.

22. A method as in claim 21, in which step (a) comprises selecting said locations such that each entity of said circuit layout design is delineated by said window and said operation is performed thereon at least once.

23. A method as in claim 21, in which step (a) comprises dimensioning said window and selecting said locations such that adjacent subsets partially overlap.

24. A method as in claim 21, further comprising the steps of:

(c) successively moving a second window having a different size than said window to a plurality of predetermined second locations in said pattern; and

(d) successively performing said operation on said second subsets that are delineated by said second window in said second location respectively.

25. A method as in claim 24, in which:

steps (a) and (c) comprise dimensioning said window and said second window and selecting said locations and said second locations such that said subsets and said second subsets partially overlay.

26. A method as in claim 25, in which:

step (a) comprises dimensioning said window and selecting said locations such that said subsets are contiguous; and

step (c) comprises dimensioning said second window and selecting said second locations such that said second subsets are contiguous.

27. A method of performing a predetermined operation on a permutation of a predetermined number of entities of a circuit layout design, comprising the steps of:

(a) defining a window that variably delineates subsets of entities of said circuit layout design; and

(b) performing said predetermined operation on said subsets, wherein

step (a) further comprises defining a second window that is integrally movable with and circumscribes said window such that a border area is defined between peripheries of said window and said second window, and

step (b) comprises performing said operation such that misplaced entities of said circuit layout design are allowed to move from said window into said border area.

28. A physical design automation method of improving a cell placement for an integrated circuit layout design, comprising the steps of:

(a) defining a movable window that delineates subsets of cells of said circuit layout design; and

(b) individually performing a predetermined placement improvement operation on said subsets, wherein

step (a) comprises moving said window to a plurality of predetermined locations in said circuit layout design, and

step (b) comprises successively performing said improvement operation on said subsets that are delineates by said window in said locations respectively.

29. A method as in claim 28, in which step (a) comprises selecting said locations such that each entity is delineated by said window and said improvement operation is performed thereon at least once.

30. A method as in claim 28, in which step (a) comprises dimensioning said window and selecting said locations such that adjacent subsets partially overlap.

31. A method as in claim 28, further comprising the steps of:

(c) successively moving a second window having a different size than said window to a plurality of predetermined second locations in said circuit layout design; and

(d) successively performing said improvement operation on second subsets that are delineated by said second window in said second locations respectively.

32. A method as in claim 31, in which:

steps (a) and (c) comprise dimensioning said window and said second window and selecting said locations and said second locations such that said subsets and said second subsets partially overlap.

33. A method as in claim 32, in which:

step (a) comprises dimensioning said window and selecting said locations such that said subsets are contiguous; and

step (c) comprises dimensioning said second window and selecting said second locations such that said second subsets are contiguous.

34. A method as in claim 28, in which:

step (a) further comprises defining a second window that is integrally movable with and circumscribes said window such that a border area is defined between peripheries of said window and said second window; and

step (b) comprises performing said improvement operation such that misplaced cells of said circuit layout design are allowed to move from said window into said border area.

35. A method as in claim 34, further comprising the step of:

(c) computing and moving said misplaced cells to new locations respectively in accordance with a predetermined function.

36. A method as in claim 35, in which step (c) comprises computing each new location as a centroid of a net of cells to which a respective misplaced cell is connected.

37. A method as in claim 34, further comprising the step of:

(c) computing new locations for said misplaced cells in accordance with a predetermined function; and

(d) attempting to move said misplaced cells to said new locations respectively.

38. A method as in claim 37, in which step (c) comprises computing each new location as a centroid of a net of cells to which a respective misplaced cell is connected.

39. A method as in claim 37, further comprising the step of:

(e) controlling step (b) to exclude a misplaced cell from a subsequent improvement operation if an attempt to move said misplaced cell to a new location is unsuccessful.

40. A method as in claim 39, in which step (e) comprises determining that an attempt to move a misplaced cell to a new location is unsuccessful if said new location is already occupied by another cell of said circuit layout design.

41. A method as in claim 39, in which step (c) comprises computing a new location as a centroid of a net of cells to which a respective misplaced cell is connected, comprising any of said misplaced cells that are included in said net in said new locations thereof.

42. A physical design automation method of improving a cell placement for an integrated circuit layout design, comprising the steps of:

(a) defining a movable window that delineates subsets of cells of said circuit layout design;

(b) individually performing a predetermined placement improvement operation on said subsets;

(c) movably defining a second window that does not overlap said window and delineates second subsets of cells of said circuit layout design; and

(d) independently performing said improvement operation on said subsets and said second subsets respectively.

43. A method as in claim 42, in which steps (a) and (c) comprise moving said window and said second window integrally.

44. A physical design automation system for improving a cell placement of a circuit layout design, comprising:

a controller for defining a boundary that limits a cell placement improvement operation to operating on cells within said boundary, and for moving said boundary in a rectilinear raster type scan pattern to a plurality of regions of said circuit layout design to delineate cells within each of said plurality of regions; and

a computer for performing said placement improvement operation on delineated cells of each respective region of said plurality of regions.

45. A physical design automation system for improving a cell placement of a circuit layout design, comprising:

a controller for defining a boundary that limits a cell placement improvement operation to operating on cells within said boundary, and for moving said boundary to a plurality of partially overlapping predetermined regions of said circuit layout design to delineate cells within each of said plurality of partially overlapping predetermined regions; and

a computer for performing said placement improvement operation on said delineated cells of each region of said partially overlapping predetermined regions.

46. A physical design automation system for improving a cell placement of a circuit layout design, comprising:

a controller for defining a boundary that limits a cell placement improvement operation to operating on cells within said boundary, and for moving said boundary to a plurality of cell congested regions of said circuit layout design to delineate cells within each of said plurality of cell congested regions; and

a computer for performing a predetermined placement improvement operation on said delineated cells of respective cell congested regions.

47. A method of improving a cell placement of a circuit layout design, comprising the steps of:

defining a boundary that limits a cell placement improvement operation to operating on cells of said circuit layout design that are situated within said boundary;

moving said boundary in a rectilinear raster type scan pattern to a plurality of regions of said circuit layout design to delineate cells within each of said plurality of regions; and

performing said placement improvement operation on said delineated cells of each respective region of said plurality of regions.

48. A method of improving a cell placement of a circuit layout design, comprising the steps of:

defining a boundary that limits a cell placement improvement operation to operating on cells of said circuit layout design that are situated within said boundary;

moving said boundary to a plurality of partially overlapping predetermined regions of said circuit layout design to delineate cells within each of said plurality of partially overlapping predetermined regions; and

performing said placement improvement operation on said delineated cells of each of said partially overlapping predetermined regions.

49. A method of improving a cell placement of a circuit layout design, comprising the steps of:

defining a boundary that limits a cell placement improvement operation to operating on cells of said circuit layout design that are situated within said boundary;

moving said boundary to a plurality of cell congested regions of said circuit layout design to delineate cells within each of said plurality of cell congested regions; and

performing said cell placement improvement operation on said delineated cells of each of said cell congested regions.