Patent US5818729A successfully refreshed from Google Patents.
US5818729A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for placing cells using quadratic placement and a spanning tree model
Assignee: Synopsys Inc
•
Filing: 1996-05-23
•
Granted: 1998-10-06
•
Expires: 2016-05-23
Abstract
Abstract A system and method for placement of elements within an integrated circuit design using a spanning tree model and a quadratic optimization based placement. The system utilizes a conjugate-gradient quadratic formula based placement system (e.g., GORDIAN) which inputs an integrated circuit design in a netlist form and generates a connectivity matrix for each multi-pin net within the design. The quadratic placement system performs global optimization using a conjugate gradient solution to minimize wire lengths of cells in nets. Partitioning is also performed. The system and method herein utilizes a clique model of a multi-pin net to generate first connectivity matrices for the multi-pin nets which are run through the global optimization processes. This first run provides a rough placement of the elements of the multi-pin nets. A spanning tree process is then run on the initial cell placement and subsequent connectivity matrices are constructed using the spanning tree model, not the clique model for multi-pin nets within a defined size range. Although biased toward the initial placement, the overall placement process as described herein is more physically realistic and efficient using the spanning tree model which requires much less data for storage and processing thus allowing faster convergence. A placed netlist is the product.
Inventors
- 👤 Chi-Hung Wang
- 👤 Dwight D. Hill
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 14:05
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
180 words
A computer controlled method for placing cells of an integrated circuit design represented as an unplaced netlist comprising the computer implemented steps of: (a) generating first connectivity matrices for each net of said netlist utilizing clique models to represent spatial affinities for cells within each multi-pin net wherein said first connectivity matrices contain non-zero entries representing spatial affinities between cells of each net; (b) performing global quadratic optimization based placement on said design utilizing said first connectivity matrices to produce a rough placement of said cells of said netlist; (c) generating spanning tree connectivity relationships for multi-pin nets of said netlist by performing a spanning tree procedure on said multi-pin nets utilizing cell locations of said rough placement of said cells of said netlist; (d) generating second connectivity matrices for each multi-pin net of said netlist utilizing said spanning tree connectivity relationships wherein said second connectivity matrices contain non-zero entries representing spatial affinities between cells of each net; and (e) performing said global quadratic optimization based placement on said design utilizing said second connectivity matrices to produce a placed netlist.
Claim 2
Dependent Claim
180 words
A computer controlled method for placing cells of an integrated circuit design represented as an unplaced netlist comprising the computer implemented steps of: (a) generating first connectivity matrices for each net of said netlist utilizing clique models to represent spatial affinities for cells within each multi-pin net wherein said first connectivity matrices contain non-zero entries representing spatial affinities between cells of each net; (b) performing global quadratic optimization based placement on said design utilizing said first connectivity matrices to produce a rough placement of said cells of said netlist; (c) generating spanning tree connectivity relationships for multi-pin nets of said netlist by performing a spanning tree procedure on said multi-pin nets utilizing cell locations of said rough placement of said cells of said netlist; (d) generating second connectivity matrices for each multi-pin net of said netlist utilizing said spanning tree connectivity relationships wherein said second connectivity matrices contain non-zero entries representing spatial affinities between cells of each net; and (e) performing said global quadratic optimization based placement on said design utilizing said second connectivity matrices to produce a placed netlist.
Claim 3
Dependent Claim
136 words
A method as described in claim 1 further comprising the steps of: (f) partitioning said placed netlist into regions and defining partition constraints for cells of each region; (g) generating revised spanning tree connectivity relationships for said multi-pin nets by performing said spanning tree procedure on said multi-pin nets based on cell locations of said placed netlist; (h) revising said second connectivity matrices for each multi-pin net utilizing said revised spanning tree connectivity relationships; (i) performing said global quadratic optimization based placement utilizing revised second connectivity matrices and utilizing said partitioning constraints to produce a revised placed netlist; (i) partitioning regions of said revised placed netlist into subregions and defining partition constraints for cells of each subregion; (k) repeating steps (g)-(j) until a predetermined set of cells exist within each subregion of said revised placed netlist.
Claim 4
Dependent Claim
28 words
A method as described in claim 1 wherein said global quadratic optimization based placement utilizes a conjugate gradient procedure to minimize distances between cells having a connectivity relationship.
Claim 5
Dependent Claim
18 words
A method as described in claim 1 wherein said spanning tree procedure is a minimum spanning tree procedure.
Claim 6
Dependent Claim
92 words
A method as described in claim 1 wherein step of (c) generating spanning tree connectivity relationships for multi-pin nets of said netlist by performing a spanning tree procedure on said multi-pin nets utilizing cell locations of said rough placement of said cells of said netlist comprises the steps of: determining those multi-pin nets that fall within a designated range of pin sizes between a minimum pin size and a maximum pin size; and applying said spanning tree procedures only to those multi-pin nets that fall within said designated range of pin sizes.
Claim 7
Dependent Claim
52 words
A method as described in claim 1 wherein said unplaced netlist comprises a list of cells of said design and a list of input and output nets associated with each cell and wherein said placed netlist comprises contents of said unplaced netlist and two dimensional coordinates of each cell of said design.
Claim 8
Dependent Claim
70 words
A method as described in claim 1 wherein said step of (a) generating first connectivity matrices for each net of said netlist utilizing clique models to represent spatial affinities for cells within each multi-pin net comprises the step of storing only said non-zero entries of said first connectivity matrices into a computer memory unit wherein each non-zero entry contains a connection value and a pointer to a next non-zero entry.
Claim 9
Dependent Claim
222 words
A computer controlled method for placement of cells of an integrated circuit design represented as an unplaced netlist having cells and connections between cells, said method comprising the computer implemented steps of: (a) placing said cells of said netlist utilizing connectivity relationships based on clique models that represent spatial affinities for cells of multi-pin nets of said design and generating a rough placement of said cells; and (b) performing second and subsequent processes on said cells of said netlist to determine and revise a second placement of said cells of said netlist, said step (b) comprising the further steps of: (1) generating spanning tree connectivity relationships for multi-pin nets of said netlist by performing a spanning tree procedure on said multi-pin nets utilizing cell locations determined in said rough placement of said cells of said netlist; (2) placing said cells of said netlist utilizing said spanning tree connectivity relationships to represent spatial affinities for cells of said multi-pin nets wherein said spanning tree connectivity relationships require less memory for storage than said connectivity relationships based on clique models; (3) revising said spanning tree connectivity relationships for multi-pin nets of said netlist by performing a spanning tree procedure on said multi-pin nets utilizing cell locations determined in step (2); and (4) repeating steps (2) and (3) until a final placed netlist is performed.
Claim 10
Dependent Claim
222 words
A computer controlled method for placement of cells of an integrated circuit design represented as an unplaced netlist having cells and connections between cells, said method comprising the computer implemented steps of: (a) placing said cells of said netlist utilizing connectivity relationships based on clique models that represent spatial affinities for cells of multi-pin nets of said design and generating a rough placement of said cells; and (b) performing second and subsequent processes on said cells of said netlist to determine and revise a second placement of said cells of said netlist, said step (b) comprising the further steps of: (1) generating spanning tree connectivity relationships for multi-pin nets of said netlist by performing a spanning tree procedure on said multi-pin nets utilizing cell locations determined in said rough placement of said cells of said netlist; (2) placing said cells of said netlist utilizing said spanning tree connectivity relationships to represent spatial affinities for cells of said multi-pin nets wherein said spanning tree connectivity relationships require less memory for storage than said connectivity relationships based on clique models; (3) revising said spanning tree connectivity relationships for multi-pin nets of said netlist by performing a spanning tree procedure on said multi-pin nets utilizing cell locations determined in step (2); and (4) repeating steps (2) and (3) until a final placed netlist is performed.
Claim 11
Dependent Claim
48 words
A method as described in claim 8 wherein said step of (2) placing said cells of said netlist utilizing said spanning tree connectivity relationships to represent spatial affinities for cells of said multi-pin nets comprises the step of using quadratic optimization based placement with a conjugate gradient procedure.
Claim 12
Dependent Claim
76 words
A method as described in claim 9 wherein said step of (2) placing said cells of said netlist utilizing said spanning tree connectivity relationships to represent spatial affinities for cells of said multi-pin nets further comprises the steps of: generating connectivity matrices based on said spanning tree connectivity relationships for each multi-pin net of said design; storing non-zero entries of said connectivity matrices into a computer memory unit; and partitioning regions of said design into subregions.
Claim 13
Dependent Claim
72 words
A method as described in claim 10 wherein said step of (4) repeating steps (2) and (3) until a final placed netlist is performed comprises the steps of: determining a fixed number of cells within each subregion of said design; comparing said fixed number of cells with a predetermined number of cells; and repeating steps (2) and (3) while said fixed number of cells is larger than said predetermined number of cells.
Claim 14
Dependent Claim
18 words
A method as described in claim 9 wherein said spanning tree procedure is a minimum spanning tree procedure.
Claim 15
Dependent Claim
80 words
A method as described in claim 9 wherein step of (3) revising said spanning tree connectivity relationships for multi-pin nets of said netlist by performing a spanning tree procedure on said multi-pin nets comprises the steps of: determining those multi-pin nets that fall within a designated range of pin sizes between a minimum pin size and a maximum pin size; and applying said spanning tree procedure only to those multi-pin nets that fall within said designated range of pin sizes.
Claim 16
Dependent Claim
231 words
A computer system including a processor coupled to bus and a memory unit coupled to said bus, said system programmed to include placement logic for placing cells of an integrated circuit design represented as an unplaced netlist having cells and connections between cells, said placement logic comprising: (a) first matrix logic generating first connectivity matrices for each net of said netlist utilizing clique models to represent spatial affinities for cells within each multi-pin net wherein said first connectivity matrices contain non-zero entries representing spatial affinities between cells of each net; (b) first placement logic coupled to said first matrix logic performing global quadratic optimization based placement on said design utilizing said first connectivity matrices to produce a rough placement of said cells of said netlist; (c) spanning tree logic generating spanning tree connectivity relationships for multi-pin nets of said netlist by performing spanning tree procedures on said multi-pin nets utilizing cell locations of said rough placement -of said cells of said netlist; (d) second matrix logic coupled to said spanning tree logic and generating second and subsequent connectivity matrices for each multi-pin net utilizing said spanning tree connectivity relationships wherein said second and subsequent connectivity matrices contain non-zero entries representing spatial affinities between cells of each net; and (e) second placement logic performing said global quadratic optimization based placement utilizing said second and subsequent connectivity matrices to produce a placed netlist.
Claim 17
Dependent Claim
231 words
A computer system including a processor coupled to bus and a memory unit coupled to said bus, said system programmed to include placement logic for placing cells of an integrated circuit design represented as an unplaced netlist having cells and connections between cells, said placement logic comprising: (a) first matrix logic generating first connectivity matrices for each net of said netlist utilizing clique models to represent spatial affinities for cells within each multi-pin net wherein said first connectivity matrices contain non-zero entries representing spatial affinities between cells of each net; (b) first placement logic coupled to said first matrix logic performing global quadratic optimization based placement on said design utilizing said first connectivity matrices to produce a rough placement of said cells of said netlist; (c) spanning tree logic generating spanning tree connectivity relationships for multi-pin nets of said netlist by performing spanning tree procedures on said multi-pin nets utilizing cell locations of said rough placement -of said cells of said netlist; (d) second matrix logic coupled to said spanning tree logic and generating second and subsequent connectivity matrices for each multi-pin net utilizing said spanning tree connectivity relationships wherein said second and subsequent connectivity matrices contain non-zero entries representing spatial affinities between cells of each net; and (e) second placement logic performing said global quadratic optimization based placement utilizing said second and subsequent connectivity matrices to produce a placed netlist.
Claim 18
Dependent Claim
32 words
A computer system as described in claim 14 wherein said second placement logic further comprises partitioning logic partitioning said placed netlist into regions and defining partition constraints for cells in each region.
Claim 19
Dependent Claim
31 words
A computer system as described in claim 14 wherein said second placement logic comprises conjugate gradient logic using a conjugate gradient procedure to minimize distances between cells having a connectivity relationship.
Claim 20
Dependent Claim
19 words
A computer system as described in claim 14 wherein said spanning tree procedure is a minimum spanning tree procedure.
Claim 21
Dependent Claim
61 words
A computer system as described in claim 14 wherein said spanning tree logic comprises: determining logic determining those multi-pin nets that fall within a designated range of pin sizes between a minimum pin size and a maximum pin size; and application logic applying said spanning tree procedures only to those multi-pin nets that fall within said designated range of pin sizes.
Claim 22
Dependent Claim
53 words
A computer system as described in claim 14 wherein said unplaced netlist comprises a list of cells of said design and a list of input and output nets associated with each cell and wherein said placed netlist comprises contents of said unplaced netlist and two dimensional coordinates of each cell of said design.
Claim 23
Dependent Claim
49 words
A computer system as described in claim 14 wherein said second matrix logic comprises storing logic storing only said non-zero entries of said second and subsequent connectivity matrices into a computer memory unit wherein each non-zero entry contains a connection value and a pointer to a next non-zero entry.
References Cited (Backward Citations)
US4908772A
Cited
US4918614A
Cited
US5119317A
Cited
US5267176A
Cited
US5309370A
Cited
US5349536A
Cited
US5566078A
Cited
US5638293A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-10-05 | 2002-04-06 | 2002-10-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-10-05 | 2006-04-06 | 2006-10-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-10-05 | 2010-04-06 | 2010-10-06 | $7700.00 | Window Closed / Lapsed |