US6327552B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for determining optimal delay allocation to datapath blocks based on area-delay and power-delay curves
Assignee: Intel Corp
•
Filing: 1999-12-28
•
Granted: 2001-12-04
•
Expires: 2019-12-28
Abstract
Abstract A method, system and computer program product for automatically determining optimal design parameters of a subsystem to meet design constraints. The subsystem comprises a plurality of circuits. The optimal design parameters are determined by performing a parameter-delay curve optimization of the subsystem design parameters. Specifically, an embodiment of the present invention provides a method and/or computer program product for determining optimal values for the design parameters of a circuit block, which result in optimally assigned delay targets for datapath blocks at the minimum power/area point. The problem/solution space is extended to solve the problem of figuring out the best possible implementation, for example, static vs dynamic, for each datapath block. Based on parameter functions, which relate to the design parameters for circuits in the circuit block, the design parameters are optimized to satisfy the design constraints. In one embodiment, the design parameters include power and delay and the parameter functions are power-delay curves.
Inventors
- 👤 Mahadevamurty Nemani
- 👤 Franklin Baez
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 21:29
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/32; G06F30/327; G06F2119/00; G06F2119/06
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
309 words
A method for automatically determining optimal design parameters of a subsystem to meet design constraints, the subsystem comprising a plurality of circuits, the method comprising: performing a parameter-delay curve optimization of the subsystem design parameters to determine the optimal design parameters, wherein the parameter-delay curve is selected from the group comprising power-delay curves and area-delay curves; wherein performing a parameter-delay curve optimization of the subsystem design parameters to determine the optimal design parameters comprises: receiving a macro graph description of the subsystem; extracting all possible paths through the macro graph; generating all possible candidate binding solutions for the macro graph; determining which of the possible candidate binding solutions are feasible; generating constraints for each of the feasible candidate binding solutions; and solving all constraints for each of the feasible candidate binding solution to determine the optimal solution; and wherein said extracting all possible paths through the macro graph comprises: determining each unique pathway from each input datapath block to each output datapath block in the macro graph; and wherein said generating all possible candidate binding solutions for the macro graph comprises: determining an implementation for each datapath block in a pathway; and associating each of the datapath blocks into a candidate binding solution for the pathway; and wherein said associating each of the datapath blocks into a candidate binding solution for the pathway comprises: creating a piecewise linear approximation for each feasible candidate binding solution; and wherein the piecewise linear approximation includes either of the following representative expressions: a i,11 A i +a i,21 D i ≧1 a i,12 A i +a i,22 D i ≧1 . . . a i,1n A i +a i,2n D i ≧1, or a i,11 A i +a i,21 P i ≧1 a i,12 A i +a i,22 P i ≧1 . . . a i,1n A i +a i,2n P i ≧1.
Claim 2
Independent Claim
309 words
A method for automatically determining optimal design parameters of a subsystem to meet design constraints, the subsystem comprising a plurality of circuits, the method comprising: performing a parameter-delay curve optimization of the subsystem design parameters to determine the optimal design parameters, wherein the parameter-delay curve is selected from the group comprising power-delay curves and area-delay curves; wherein performing a parameter-delay curve optimization of the subsystem design parameters to determine the optimal design parameters comprises: receiving a macro graph description of the subsystem; extracting all possible paths through the macro graph; generating all possible candidate binding solutions for the macro graph; determining which of the possible candidate binding solutions are feasible; generating constraints for each of the feasible candidate binding solutions; and solving all constraints for each of the feasible candidate binding solution to determine the optimal solution; and wherein said extracting all possible paths through the macro graph comprises: determining each unique pathway from each input datapath block to each output datapath block in the macro graph; and wherein said generating all possible candidate binding solutions for the macro graph comprises: determining an implementation for each datapath block in a pathway; and associating each of the datapath blocks into a candidate binding solution for the pathway; and wherein said associating each of the datapath blocks into a candidate binding solution for the pathway comprises: creating a piecewise linear approximation for each feasible candidate binding solution; and wherein the piecewise linear approximation includes either of the following representative expressions: a i,11 A i +a i,21 D i ≧1 a i,12 A i +a i,22 D i ≧1 . . . a i,1n A i +a i,2n D i ≧1, or a i,11 A i +a i,21 P i ≧1 a i,12 A i +a i,22 P i ≧1 . . . a i,1n A i +a i,2n P i ≧1.
Claim 3
Dependent Claim
71 words
The method of claim 1 , wherein said determining all feasible candidate binding solutions comprises: obtaining a first parameter-delay curve for each of the datapath blocks in the candidate binding solution; combining values from the first parameter-delay curves for the datapath blocks; and comparing the combined values against a delay constraint value, wherein the candidate binding solution is feasible if the combined values are not greater than the delay constraint value.
Claim 4
Dependent Claim
26 words
The method of claim 2 , wherein said delay constraint value comprises: summing a datapath block delay constraint value for each datapath block in the pathway.
Claim 5
Dependent Claim
33 words
The method of claim 3 , wherein said generating constraints for each of the feasible candidate binding solutions comprises: creating constraints for each of the feasible candidate binding solutions using a specified delay.
Claim 6
Dependent Claim
79 words
The method of claim 4 , wherein said solving all constraints for each of the feasible candidate binding solutions to determine the optimal solution comprises: associating each of the piecewise linear approximations and the constraints for each feasible candidate binding solution in a linear program; and solving the linear program to determine the optimal solution, wherein the optimal solution produces a minimal delay value for the subsystem and provides an optimal delay value for each of the datapath blocks.
Claim 7
Dependent Claim
319 words
A computer-readable medium having stored therein a computer program for automatically determining optimal design parameters of a subsystem to meet design constraints, the subsystem comprising a plurality of circuits, said computer program, when executed: performs a parameter-delay curve optimization of the subsystem design parameters to determine the optimal design parameters, wherein the parameter-delay curve is selected from the group comprising power-delay curves and area-delay curves; and wherein performing a parameter-delay curve optimization of the subsystem design parameters to determine the optimal design parameters comprises: receiving a macro graph description of the subsystem; extracting all possible paths through the macro graph; generating all possible candidate binding solutions for the macro graph; determining which of the possible candidate binding solutions are feasible; generating constraints for each of the feasible candidate binding solutions; and solving all constraints for each of the feasible candidate binding solution to determine the optimal solution; and wherein said extracting all possible paths through the macro graph comprises: determining each unique pathway from each input datapath block to each output datapath block in the macro graph; and wherein said generating all possible candidate binding solutions for the macro graph comprises: determining an implementation for each datapath block in a pathway; and associating each of the datapath blocks into a candidate binding solution for the pathway; and wherein said associating each of the datapath blocks into a candidate binding solution for the pathway comprises: creating a piecewise linear approximation for each feasible candidate binding solution; and wherein the piecewise linear approximation includes either of the following representative expressions: a i,11 A i +a i,21 D i ≧1 a i,12 A i +a i,22 D i ≧1 . . . a i,1n A i +a i,2n D i ≧1, or a i,11 A i +a i,21 P i ≧1 a i,12 A i +a i,22 P i ≧1 . . . a i,1n A i +a i,2n P i ≧1.
Claim 8
Dependent Claim
319 words
A computer-readable medium having stored therein a computer program for automatically determining optimal design parameters of a subsystem to meet design constraints, the subsystem comprising a plurality of circuits, said computer program, when executed: performs a parameter-delay curve optimization of the subsystem design parameters to determine the optimal design parameters, wherein the parameter-delay curve is selected from the group comprising power-delay curves and area-delay curves; and wherein performing a parameter-delay curve optimization of the subsystem design parameters to determine the optimal design parameters comprises: receiving a macro graph description of the subsystem; extracting all possible paths through the macro graph; generating all possible candidate binding solutions for the macro graph; determining which of the possible candidate binding solutions are feasible; generating constraints for each of the feasible candidate binding solutions; and solving all constraints for each of the feasible candidate binding solution to determine the optimal solution; and wherein said extracting all possible paths through the macro graph comprises: determining each unique pathway from each input datapath block to each output datapath block in the macro graph; and wherein said generating all possible candidate binding solutions for the macro graph comprises: determining an implementation for each datapath block in a pathway; and associating each of the datapath blocks into a candidate binding solution for the pathway; and wherein said associating each of the datapath blocks into a candidate binding solution for the pathway comprises: creating a piecewise linear approximation for each feasible candidate binding solution; and wherein the piecewise linear approximation includes either of the following representative expressions: a i,11 A i +a i,21 D i ≧1 a i,12 A i +a i,22 D i ≧1 . . . a i,1n A i +a i,2n D i ≧1, or a i,11 A i +a i,21 P i ≧1 a i,12 A i +a i,22 P i ≧1 . . . a i,1n A i +a i,2n P i ≧1.
Claim 9
Dependent Claim
72 words
The computer-readable medium of claim 6 , wherein said determining all feasible candidate binding solutions comprises: obtaining a first parameter-delay curve for each of the datapath blocks in the candidate binding solution; combining values from the first parameter-delay curves for the datapath blocks; and comparing the combined values against a delay constraint value, wherein the candidate binding solution is feasible if the combined values are not greater than the delay constraint value.
Claim 10
Dependent Claim
26 words
The computer-readable medium of claim 7 , wherein said delay constraint value comprises: a sum of each specified datapath block delay constraint value for the pathway.
Claim 11
Dependent Claim
34 words
The computer-readable medium of claim 6 , wherein said generating constraints for each of the feasible candidate binding solutions comprises: creating constraints for each of the feasible candidate binding solutions using a specified delay.
Claim 12
Dependent Claim
80 words
The computer-readable medium of claim 9 , wherein said solving all constraints for each of the feasible candidate binding solutions to determine the optimal solution comprises: associating each of the piecewise linear approximations and the constraints for each feasible candidate binding solution in a linear program; and solving the linear program to determine the optimal solution, wherein the optimal solution produces a minimal delay value for the subsystem and provides an optimal delay value for each of the datapath blocks.
Claim 13
Independent Claim
260 words
A method for automatically determining an optimal delay allocation for datapath blocks of a subsystem, the subsystem comprising a plurality of circuits, the method comprising: receiving a macro graph description of the subsystem; extracting all possible paths through the macro graph; generating all possible candidate binding solutions for the macro graph; determining which of the possible candidate binding solutions are feasible; generating constraints for each of the feasible candidate binding solutions; and solving all constraints for each of the feasible candidate binding solution to determine the optimal solution; and wherein said extracting all possible paths through the macro graph comprises: determining each unique pathway from each input datapath block to each output datapath block in the macro graph; and wherein said generating all possible candidate binding solutions for the macro graph comprises: determining an implementation for each datapath block in a pathway; and associating each of the datapath blocks into a candidate binding solution for the pathway; and wherein said associating each of the datapath blocks into a candidate binding solution for the pathway comprises: creating a piecewise linear approximation for each feasible candidate binding solution; and wherein the piecewise linear approximation includes either of the following representative expressions: a i,11 A i +a i,21 D i ≧1 a i,12 A i +a i,22 D i ≧1 . . . a i,1n A i +a i,2n D i ≧1, or a i,11 A i +a i,21 P i ≧1 a i,12 A i +a i,22 P i ≧1 . . . a i,1n A i +a i,2n P i ≧1.
Claim 14
Independent Claim
260 words
A method for automatically determining an optimal delay allocation for datapath blocks of a subsystem, the subsystem comprising a plurality of circuits, the method comprising: receiving a macro graph description of the subsystem; extracting all possible paths through the macro graph; generating all possible candidate binding solutions for the macro graph; determining which of the possible candidate binding solutions are feasible; generating constraints for each of the feasible candidate binding solutions; and solving all constraints for each of the feasible candidate binding solution to determine the optimal solution; and wherein said extracting all possible paths through the macro graph comprises: determining each unique pathway from each input datapath block to each output datapath block in the macro graph; and wherein said generating all possible candidate binding solutions for the macro graph comprises: determining an implementation for each datapath block in a pathway; and associating each of the datapath blocks into a candidate binding solution for the pathway; and wherein said associating each of the datapath blocks into a candidate binding solution for the pathway comprises: creating a piecewise linear approximation for each feasible candidate binding solution; and wherein the piecewise linear approximation includes either of the following representative expressions: a i,11 A i +a i,21 D i ≧1 a i,12 A i +a i,22 D i ≧1 . . . a i,1n A i +a i,2n D i ≧1, or a i,11 A i +a i,21 P i ≧1 a i,12 A i +a i,22 P i ≧1 . . . a i,1n A i +a i,2n P i ≧1.
Claim 15
Dependent Claim
71 words
The method of claim 11 , wherein said determining all feasible candidate binding solutions comprises: obtaining a first parameter-delay curve for each of the datapath blocks in the candidate binding solution; combining values from the first parameter-delay curves for the datapath blocks; and comparing the combined values against a delay constraint value, wherein the candidate binding solution is feasible if the combined values are not greater than the delay constraint value.
Claim 16
Dependent Claim
34 words
The method of claim 12 , wherein obtaining the first parameter-delay curves comprises: selecting the first parameter-delay curve for each of the datapath blocks from the group consisting of power-delay curves and area-delay curves.
Claim 17
Dependent Claim
33 words
The method of claim 11 , wherein said generating constraints for each of the feasible candidate binding solutions comprises: creating constraints for each of the feasible candidate binding solutions using a specified delay.
Claim 18
Dependent Claim
79 words
The method of claim 11 , wherein said solving all constraints for each of the feasible candidate binding solutions to determine the optimal solution comprises: associating each of the piecewise linear approximations and the constraints for each feasible candidate binding solution in a linear program; and solving the linear program to determine the optimal solution, wherein the optimal solution produces a minimal delay value for the subsystem and provides an optimal delay value for each of the datapath blocks.
References Cited (Backward Citations)
US5555201A
Cited
US5500805A
Cited
US5612892A
Cited
US5917729A
Cited
US5880967A
Cited
US5619420A
Cited
US5926396A
Cited
US5774367A
Cited
US5666228A
Cited
US5910898A
Cited
US5867397A
Cited
US5838947A
Cited
US5835380A
Cited
US5768145A
Cited
US5889685A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-12-03 | 2005-06-04 | 2005-12-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-12-03 | 2009-06-04 | 2009-12-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-12-03 | 2013-06-04 | 2013-12-04 | $7700.00 | Window Closed / Lapsed |