US6442743B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Placement method for integrated circuit design using topo-clustering
Assignee: Synopsys Inc
•
Filing: 1998-06-12
•
Granted: 2002-08-27
•
Expires: 2018-06-12
Abstract
Abstract The disclosure describes a placement method for the physical design of integrated circuits in which natural topological feature clusters are discovered and exploited during the placement process is disclosed. Topo-clusters drive initial placement, with all of the gates of a topo-cluster being placed initially in a single bin of the placement layout or within a group of positionally-related bins. An iterative placement refinement process is done using a technique referred to as Dual Geometrically-Bounded FM (GBFM). GBFM is applied on a local basis to windows encompassing a number of bins. From iteration to iteration, windows may shift position and vary in size. When a region bounded by a window meets a specified cost threshold in terms of a specified cost function, that region stops participating. Following the foregoing global placement process the circuit is then ready for detailed placement in which cells are assigned to placement rows.
Inventors
- 👤 Majid Sarrafzadeh
- 👤 Lawrence Pileggi
- 👤 Sharad Malik
- 👤 Feroze Peshotan Taraporevala
- 👤 Abhijeet Chakraborty
- 👤 Gary K. Yeap
- 👤 Salil R. Raje
- 👤 Lilly Shieh
- 👤 Douglas B. Boyle
- 👤 Dennis Yamamoto
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 17:10
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
142 words
A method of placing circuit elements on an integrated circuit design layout comprising the steps of: grouping circuit elements into clusters based on topological relatedness of the circuit elements of a cluster; placing circuit elements by cluster within bins defined on the circuit design layout wherein, for a first cluster, said placing circuit elements by cluster includes repeatedly placing circuit elements from said first cluster in to a centralized bin until the centralized bin reaches capacity and placing remaining circuit elements from said first cluster into a bin which is located in a predetermined spiral order to the centralized bin until all circuit elements of said first cluster have been placed; defining a continuous region specified by said bins; and applying a placement refinement technique to said continuous region to produce a placement that is improved as measured by a cost function.
Claim 2
Independent Claim
142 words
A method of placing circuit elements on an integrated circuit design layout comprising the steps of: grouping circuit elements into clusters based on topological relatedness of the circuit elements of a cluster; placing circuit elements by cluster within bins defined on the circuit design layout wherein, for a first cluster, said placing circuit elements by cluster includes repeatedly placing circuit elements from said first cluster in to a centralized bin until the centralized bin reaches capacity and placing remaining circuit elements from said first cluster into a bin which is located in a predetermined spiral order to the centralized bin until all circuit elements of said first cluster have been placed; defining a continuous region specified by said bins; and applying a placement refinement technique to said continuous region to produce a placement that is improved as measured by a cost function.
Claim 3
Dependent Claim
26 words
The method of claim 1 , wherein said placement refinement technique comprises moving at least one of circuit elements and clusters between bins within a region.
Claim 4
Dependent Claim
21 words
The method of claim 2 , wherein within at least some regions both circuit elements and clusters are moved between bins.
Claim 5
Dependent Claim
21 words
The method of claim 3 , wherein clusters are moved between bins first, and circuit elements are moved between bins afterward.
Claim 6
Dependent Claim
50 words
The method of claim 3 , comprising the further steps of: shifting a set of windows by a program-controlled shift amount relative to the integrated circuit design layout to thereby define a set of different regions; and applying said placement refinement technique to at least some of said different regions.
Claim 7
Dependent Claim
22 words
The method of claim 5 , comprising the further steps of repeating said shifting and applying steps a program-controlled number of times.
Claim 8
Dependent Claim
94 words
The method of claim 6 , comprising the further steps of, for each of a plurality of iterations: defining a plurality of regions using a set of windows of a program-controlled size; applying said placement refinement technique to at least some of said regions; shifting the set of windows by a program-controlled shift amount relative to the integrated circuit design layout to thereby define a set of different regions; applying said placement refinement technique to at least some of said different regions; and repeating said shifting and applying steps a program-controlled number of times.
Claim 9
Dependent Claim
37 words
The method of claim 1 , comprising the further steps of: quadrisecting said bins; defining a plurality of different regions; and again applying said placement refinement technique to at least some of the plurality of different regions.
Claim 10
Dependent Claim
30 words
The method of claim 8 , comprising repeating the steps of quadrisection and again applying said placement refinement technique until each bin contains at most a predetermined number of gates.
Claim 11
Dependent Claim
16 words
The method of claim 9 , wherein said predetermined number of gates is less than thirty.
Claim 12
Dependent Claim
17 words
The method of claim 1 , wherein grouping circuit elements comprises grouping circuit elements by similar function.
Claim 13
Dependent Claim
17 words
The method of claim 1 , wherein grouping circuit elements comprises grouping circuit elements by netlist proximity.
Claim 14
Dependent Claim
33 words
The method of claim 1 , wherein grouping including the steps of: creating a first planar subgraph; creating a second planar subgraph; repeating the preceding steps until all the nets have been removed.
References Cited (Backward Citations)
US5526517A
Cited
US5491641A
Cited
US5495419A
Cited
US5557533A
Cited
US5636125A
Cited
US5682322A
Cited
US5903461A
Cited
US5682321A
Cited
US5748844A
Cited
US5838585A
Cited
US5661663A
Cited
US5699265A
Cited
US5712793A
Cited
US5909376A
Cited
US5854752A
Cited
US6030110A
Cited
US6067409A
Cited
US5955776A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-08-26 | 2006-02-25 | 2006-08-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-08-26 | 2010-02-25 | 2010-08-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-08-26 | 2014-02-25 | 2014-08-27 | $7700.00 | Window Closed / Lapsed |