US5359538A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for regular placement of data path components in VLSI circuits
Assignee: NXP BV
•
Filing: 1991-08-20
•
Granted: 1994-10-25
•
Expires: 2011-08-20
Abstract
Abstract In a method for placement of components for a VLSI circuit, control signal connection networks and data signal connection networks are identified. Then, an initial placement of the components for the VLSI circuit is made. This initial placement is iteratively improved. The algorithm used for the iterative improvement has a cost metric in which a horizontal component for length of a connection network and a vertical component for length of the connection network are weighted differently dependent on whether the connection network was identified as a control signal connection network or a data signal connection network. The different weighting results in improved regularity of the placement of data path components and thus a more efficient routing of connection networks between the components.
Inventors
- 👤 Siu-Tong Hui
- 👤 Dale M. Wong
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 09:30
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
107 words
A method for placement of components for a VLSI circuit, the method comprising the steps of: (a) identifying control signal connection networks and data signal connection networks; (b) making an initial placement of the components for the VLSI circuit; and, (c) iteratively improving the initial placement of the components for the VLSI circuit using an algorithm having a cost metric in which a horizontal component for length of a connection network and a vertical component for length of the connection network are weighted differently dependent on whether in step (a) the connection network was identified as a control signal connection network or a data signal connection network.
Claim 2
Independent Claim
107 words
A method for placement of components for a VLSI circuit, the method comprising the steps of: (a) identifying control signal connection networks and data signal connection networks; (b) making an initial placement of the components for the VLSI circuit; and, (c) iteratively improving the initial placement of the components for the VLSI circuit using an algorithm having a cost metric in which a horizontal component for length of a connection network and a vertical component for length of the connection network are weighted differently dependent on whether in step (a) the connection network was identified as a control signal connection network or a data signal connection network.
Claim 3
Dependent Claim
65 words
A method as in claim 1 wherein step (b) is performed using an algorithm having a cost metric in which a horizontal component for length of a connection network and a vertical component for length of the connection network are weighted differently dependent on whether in step (a) the connection network was identified as a control signal connection network or a data signal connection network.
Claim 4
Dependent Claim
151 words
A method as in claim 2 wherein the cost metric used in step (b) has a form Cost.sub.D =Σ.sub.D F(M.sub.1 ·L.sub.vertical +M.sub.2 ·L.sub.horizontal) Cost.sub.C =Σ.sub.C F(N.sub.1 ·L.sub.vertical +N.sub.2 ·L.sub.horizontal) where Cost D is a calculated cost for data signal connection networks, Σ D indicates a sum of all or a selected portion of data signal connection networks, F indicates a function for calculating a cost metric for a single connection network, L vertical is a vertical length of a particular connection network, L horizontal is a horizontal length of the particular connection network, M 1 and M 2 are multipliers respectively of L vertical and L horizontal , Cost C is a calculated cost for control signal connection networks, Σ C indicates a sum of all or a selected portion of control signal connection networks, and N 1 and N 2 are multipliers respectively of L vertical and L horizontal .
Claim 5
Dependent Claim
25 words
A method as in claim 1 wherein in step (a) control signal connection networks and data signal connection networks are identified by a circuit designer.
Claim 6
Dependent Claim
25 words
A method as in claim 4 wherein in step (a) control signal connection networks and data signal connection networks are identified using an extraction algorithm.
Claim 7
Dependent Claim
284 words
A method as in claim 5 wherein in step (a) the extraction algorithm performs in accordance with the following method substeps: (a.1) including in a first set all components of the VLSI circuit; (a.2) selecting a component from the first set to be a first component; (a.3) placing in a first subset, components in the first set which belong to a same component type as the first component and which have an input connected, by an input connection network, to a similar type of input of the first component; ( a.4) if the first subset formed in substep ( a.3) contains more than a single component, identifying as a control signal connection network, an input network which is connected to an input of the first component and a similar type of input of a greatest number of other components in the first subset; (a.5) grouping together the first component and the other components in the first subset which have inputs connected to the control signal connection network identified in substep (a.4); (a.6) removing from the first set the components within the grouping formed in substep (a.5); (a.7) if there are still components in the first set, repeating substeps (a.2) to (a.7); (a.8) forming a second set of all groupings formed in substep (a.5); (a.9) selecting a first grouping from the second set; (a.10) identifying as a data signal connection network each connection network that is connected in a bundled fashion with at least one other connection network between the first grouping and any other grouping in the second set; (a.11) removing the first grouping from the second set; and, (a.12) if there are still groupings in the second set, repeating substeps (a.9) through (a.12).
Claim 8
Dependent Claim
151 words
A method as in claim 1 wherein the cost metric used in step (c) has a form Cost.sub.D =Σ.sub.D F(M.sub.1 ·L.sub.vertical +M.sub.2 ·L.sub.horizontal) Cost.sub.C =Σ.sub.C F(N.sub.1 ·L.sub.vertical +N.sub.2 ·L.sub.horizontal) where Cost D is a calculated cost for data signal connection networks, Σ D indicates a sum of all or a selected portion of data signal connection networks, F indicates a function for calculating a cost metric for a single connection network, L vertical is a vertical length of a particular connection network, L horizontal is a horizontal length of the particular connection network, M 1 and M 2 are multipliers respectively of L vertical and L horizontal , Cost C is a calculated cost for control signal connection networks, Σ C indicates a sum of all or a selected portion of control signal connection networks, and N 1 and N 2 are multipliers respectively of L vertical and L horizontal .
Claim 9
Dependent Claim
25 words
A method as in claim 7 wherein in step (a) control signal connection networks and data signal connection networks are identified by a circuit designer.
Claim 10
Dependent Claim
25 words
A method as in claim 8 wherein in step (a) control signal connection networks and data signal connection networks are identified using an extraction algorithm.
Claim 11
Dependent Claim
283 words
A method as in claim 9 wherein in step (a) the extraction algorithm performs in accordance with the following method substeps: (a.1) including in a first set all components of the VLSI circuit; (a.2) selecting a component from the first set to be a first component; (a.3) placing in a first subset, components in the first set which belong to a same component type as the first component and which have an input connected, by an input connection network, to a similar type of input of the first component; ( a.4) if the first subset formed in substep (a.3) contains more than a single component, identifying as a control signal connection network, an input network which is connected to an input of the first component and a similar type of input of a greatest number of other components in the first subset; (a.5) grouping together the first component and the other components in the first subset which have inputs connected to the control signal connection network identified in substep (a.4); (a.6) removing from the first set the components within the grouping formed in substep (a.5); (a.7) if there are still components in the first set, repeating substeps (a.2) to (a.7); (a.8) forming a second set of all groupings formed in substep (a.5); (a.9) selecting a first grouping from the second set; (a.10) identifying as a data signal connection network each connection network that is connected in a bundled fashion with at least one other connection network between the first grouping and any other grouping in the second set; (a.11) removing the first grouping from the second set; and, (a.12) if there are still groupings in the second set, repeating substeps (a.9) through (a.12).
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-10-24 | 1998-04-25 | 1998-10-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-10-24 | 2002-04-25 | 2002-10-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-10-24 | 2006-04-25 | 2006-10-25 | $7700.00 | Window Closed / Lapsed |