US6415425B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for analytical placement of cells using density surface representations
Assignee: Xilinx Inc
•
Filing: 1999-03-04
•
Granted: 2002-07-02
•
Expires: 2019-03-04
Abstract
Abstract A method for analytical placement of cells using density surface representations. The placement of the cells is characterized as density surface fun which is two-dimensional and continuous. The cells are iteratively moved from areas having higher densities of placed cells to areas having lower densities of placed cells using the density surface function.
Inventors
- 👤 Kamal Chaudhary
- 👤 Sudip K. Nag
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 14:20
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
50 words
A method for placing cells on an integrated circuit, comprising: characterizing a placement of cells as a density surface function that is continuous and differentiable; and moving the cells from areas having higher densities of placed cells to areas having lower densities of placed cells using the density surface function.
Claim 2
Independent Claim
50 words
A method for placing cells on an integrated circuit, comprising: characterizing a placement of cells as a density surface function that is continuous and differentiable; and moving the cells from areas having higher densities of placed cells to areas having lower densities of placed cells using the density surface function.
Claim 3
Dependent Claim
18 words
The method of claim 1 , further comprising minimizing wire lengths connecting the cells while moving the cells.
Claim 4
Dependent Claim
16 words
The method of claim 1 , wherein the density surface function is a discrete cosine transform.
Claim 5
Dependent Claim
49 words
The method of claim 1 , wherein the density surface function is represented as a polynomial function of the form: Φ = ∑ i = 1 R - 1 ∑ j = 1 R - 1 a ij x i y i .
Claim 6
Dependent Claim
106 words
The method of claim 1 , further comprising: generating a connectivity matrix, A, and an anchoring vector, B; wherein the density surface function is Φ = ∑ k = 1 N Φ x k y k , where N is the number of movable cells; and minimizing the function x T Ax−Bx+λΦ, where: x=[x 1 , x 2 , x 3 , . . . , x N , y 1 , y 2 , y 3 , . . . , y N ] T , and λ is a scaling factor indicative of relative importance of density to wire-length.
Claim 7
Dependent Claim
57 words
The method of claim 5 , further comprising: identifying an area of the circuit having a maximum number of cells; repeating minimization of the function x T Ax−Bx+λΦ, and computing a new density surface value, and identifying the area with a maximum number of cells until the maximum number of cells is less than a predetermined value.
Claim 8
Dependent Claim
59 words
The method of claim 5 , further comprising: identifying a plurality of areas of the circuit having greatest numbers of cells; repeating minimization of the function x T Ax−Bx+λΦ, and computing a new density surface value, and identifying areas with greatest numbers of cells until an average of the greatest numbers of cells is less than a predetermined value.
Claim 9
Dependent Claim
21 words
The method of claim 1 , wherein some of the cells are movable and some of the cells have fixed placements.
Claim 10
Dependent Claim
107 words
The method of claim 8 , further comprising: generating a connectivity matrix, A, and an anchoring vector, B; wherein the density surface function is Φ = ∑ k = 1 N Φ x k y k , where N is the number of movable cells; and minimizing the function x T Ax−Bx+λΦ, where x=[x 1 , x 2 , x 3 , . . . , X N , y 1 , y 2 , y 3 , . . . , y N ] T , and λ is a scaling factor indicative of relative importance of density to wire-length minimization.
Claim 11
Dependent Claim
26 words
The method of claim 9 , wherein the connectivity matrix has weighted values of magnitudes dependent on timing criticality of respective pairs of connected movable cells.
Claim 12
Dependent Claim
28 words
The method of claim 10 , wherein the anchoring vector has weighted values of magnitudes dependent on timing criticality of respective pairs of connected movable and fixed cells.
Claim 13
Dependent Claim
25 words
The method of claim 9 , wherein the connectivity matrix has weighted values of magnitudes dependent on fanout of respective pairs of connected movable cells.
Claim 14
Dependent Claim
27 words
The method of claim 10 , wherein the anchoring vector has weighted values of magnitudes dependent on fanout of respective pairs of connected movable and fixed cells.
Claim 15
Dependent Claim
34 words
The method of claim 9 , further comprising repeating minimization of the function x T Ax−Bx+λΦ until a change in x from one minimization to a successive minimization is less than a predetermined value.
References Cited (Backward Citations)
US6155725A
Cited
US6067409A
Cited
US5943243A
Cited
US6182271B1
Cited
US6068662A
Cited
US6192508B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-07-01 | 2005-12-31 | 2006-07-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-07-01 | 2009-12-31 | 2010-07-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-07-01 | 2013-12-31 | 2014-07-02 | $7700.00 | Window Closed / Lapsed |