US5742510A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Simultaneous placement and routing (SPAR) method for integrated circuit physical design automation system
Assignee: LSI Corp
•
Filing: 1996-02-21
•
Granted: 1998-04-21
•
Expires: 2016-02-21
Abstract
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.
Inventors
- 👤 Michael D. Rostoker
- 👤 James S. Koford
- 👤 Edwin R. Jones
- 👤 Douglas B. Boyle
- 👤 Ranko Scepanovic
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 22:39
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
72 words
A method of optimizing a cell placement for an integrated circuit chip, comprising the steps of: (a) routing said cell placement; (b) identifying congested areas of said routing; (c) selectively applying a congestion reduction algorithm only within said congested areas to alter said cell placement in said congested areas; (d) computing a cell placement fitness; and (e) if said cell placement fitness is below a predetermined value, repeating steps (b) to (d).
Claim 2
Independent Claim
72 words
A method of optimizing a cell placement for an integrated circuit chip, comprising the steps of: (a) routing said cell placement; (b) identifying congested areas of said routing; (c) selectively applying a congestion reduction algorithm only within said congested areas to alter said cell placement in said congested areas; (d) computing a cell placement fitness; and (e) if said cell placement fitness is below a predetermined value, repeating steps (b) to (d).
Claim 3
Dependent Claim
15 words
A method as in claim 1, in which step (e) further comprises repeating step (a).
Claim 4
Dependent Claim
26 words
A method as in claim 1, in which: said placement comprises a plurality of nets of cells; and step (a) comprises routing said nets in parallel.
Claim 5
Dependent Claim
32 words
A method as in claim 1, in which step (a) comprises the substeps of: (f) dividing said placement into a plurality of predetermined areas; and (g) routing said predetermined areas in parallel.
Claim 6
Dependent Claim
22 words
A method as in claim 1, in which step (c) comprises applying said congestion reduction algorithm to said congested areas in parallel.
Claim 7
Dependent Claim
19 words
A method as in claim 5, in which step (c) comprises moving selected cells out of said congested areas.
Claim 8
Dependent Claim
25 words
A method as in claim 5, in which step (c) comprises relocating selected cells such that routing thereof does not pass through said congested areas.
Claim 9
Dependent Claim
48 words
A method as in claim 7, in which step (c) comprises the substeps of: (f) relocating said selected cells in a predetermined manner; (g) rerouting nets of cells that include said selected cells; and (h) repeating steps (f) and (g) if said rerouting passes through said congested areas.
Claim 10
Dependent Claim
23 words
A method as in claim 8, comprising performing steps (f), (g) and (h) on said selected cells and said nets respectively in parallel.
Claim 11
Dependent Claim
20 words
A method as in claim 8, in which step (g) comprises applying a Steiner tree algorithm for rerouting said nets.
Claim 12
Dependent Claim
23 words
A method as in claim 7, in which step (c) comprises selecting said cells for relocation as having high values of interconnect congestion.
Claim 13
Dependent Claim
24 words
A method as in claim 7, in which step (c) comprises selecting said cells for relocation if routing thereof passes through said congested areas.
Claim 14
Dependent Claim
36 words
A method as in claim 7, in which step (c) comprises selecting said cells for relocation if said cells are outside perimeters that surround other cells in nets to which said selected cells are connected respectively.
Claim 15
Dependent Claim
19 words
A method as in claim 13, in which step (c) comprises relocating said selected cells inside said perimeters respectively.
Claim 16
Dependent Claim
21 words
A method as in claim 14, in which step (c) comprises relocating said selected cells to centroids of said perimeters respectively.
Claim 17
Dependent Claim
53 words
A method as in claim 1, in which: step (c) comprises relocating selected cells without rerouting said placement; and the method further comprises the steps of: (f) calculating an amount of error in said routing created by step (c); and (g) repeating step (a) if said amount of error exceeds a predetermined value.
Claim 18
Dependent Claim
17 words
A method as in claim 16, in which steps (f) and (g) are performed after step (c).
Claim 19
Dependent Claim
37 words
A method as in claim 1, in which step (c) comprises the substeps of: (f) dividing said placement into a plurality of predetermined areas; and (g) applying said congestion reduction algorithm to said predetermined areas in parallel.
Claim 20
Dependent Claim
61 words
A method as in claim 18, in which step (g) comprises the substeps of: (h) relocating selected cells without rerouting said placement; (i) calculating amounts of error in said routing created by step (h) in each of said predetermined areas respectively; and (j) repeating step (a) if said amount of error in any of said predetermined areas exceeds a predetermined value.
Claim 21
Dependent Claim
39 words
A method as in claim 1, further comprising the step, performed prior to step (a), of: (f) decomposing said placement into a hierarchial order of groups of cells; and step (a) comprises routing said groups of cells in parallel.
Claim 22
Dependent Claim
83 words
A physical design automation system for optimizing a cell placement for an integrated circuit chip, comprising: a router for routing said cell placement; and a computer for performing operations of: identifying congested areas of said routing; selectively applying a congestion reduction algorithm only within said congested areas to alter said cell placement in said congested areas; and computing a cell placement fitness; and a controller for controlling the computer to repeat performing said operations until said cell placement fitness attains a predetermined value.
Claim 23
Dependent Claim
83 words
A physical design automation system for optimizing a cell placement for an integrated circuit chip, comprising: a router for routing said cell placement; and a computer for performing operations of: identifying congested areas of said routing; selectively applying a congestion reduction algorithm only within said congested areas to alter said cell placement in said congested areas; and computing a cell placement fitness; and a controller for controlling the computer to repeat performing said operations until said cell placement fitness attains a predetermined value.
Claim 24
Dependent Claim
26 words
A system as in claim 21, in which the controller further controls the router to reroute said placement if said fitness is below said predetermined value.
Claim 25
Dependent Claim
19 words
A system as in claim 21, in which the router comprises a global router for globally routing said placement.
Claim 26
Dependent Claim
32 words
A system as in claim 21, in which: said placement comprises a plurality of nets of cells; and the router comprises a plurality of parallel processors for routing said nets in parallel.
Claim 27
Dependent Claim
33 words
A system as in claim 21, in which the router divides said placement into a plurality of predetermined areas, and comprises a plurality of parallel processors for routing said predetermined areas in parallel.
Claim 28
Dependent Claim
32 words
A system as in claim 21, in which the computer comprises a plurality of parallel processors for applying said congestion reduction algorithm to alter said placement in said congested areas in parallel.
Claim 29
Dependent Claim
43 words
A system as in claim 21, in which: said congestion reduction algorithm comprises relocating selected cells such that routing thereof does not pass through said congested areas; and the computer comprises a plurality of parallel processors for relocating said selected cells in parallel.
Claim 30
Dependent Claim
40 words
A system as in claim 21, in which the computer divides said placement into a plurality of predetermined areas, and comprises a plurality of parallel processors for applying said congestion reduction algorithm to said plurality of predetermined areas in parallel.
References Cited (Backward Citations)
US4615011A
Cited
US4686629A
Cited
US4613941A
Cited
US4858143A
Cited
US4890238A
Cited
US4918614A
Cited
US5047949A
Cited
US4815003A
Cited
US4852015A
Cited
US4831725A
Cited
US5187668A
Cited
US5309370A
Cited
US5311443A
Cited
US5414638A
Cited
US5495419A
Cited
US5557533A
Cited
US5587923A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-04-20 | 2001-10-20 | 2002-04-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-04-20 | 2005-10-20 | 2006-04-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-04-20 | 2009-10-20 | 2010-04-21 | $7700.00 | Window Closed / Lapsed |