Solutions for constraint satisfaction problems requiring multiple constraints
First Claim
1. A method comprising:
- identifying a plurality of circuit parameters, the parameters specifying different aspects of a design for an electronic circuit, each parameter having a plurality of different possible values;
sorting a set of constraints based on weights associated with each constraint, the constraints being capable of being satisfied based on values selected for corresponding associated parameters, the constraints limiting possible values for the corresponding associated parameters;
selecting a constraint that is unsatisfied and that has the greatest weight;
selecting parameters associated with the constraint and finding parameter values to satisfy the constraint;
after satistying the selected unsatisfied constraint, selecting a further unsatisfied constraint having the next greatest weight and finding values for associated parameters to satisfy the further constraint;
repeating the selecting of further constraints and the finding of values for associated parameters; and
defining the electronic circuit using the found parameter values.
1 Assignment
0 Petitions
Accused Products
Abstract
In one embodiment, the invention includes sorting a set of constraints based on weights associated with each constraint, the constraints being capable of being satisfied based on values selected for corresponding associated parameters, selecting a constraint that is unsatisfied and that has the greatest weight, selecting parameters associated with the constraint and finding parameter values to satisfy the constraint, after satisfying the selected unsatisfied constraint, selecting a further unsatisfied constraint having the next greatest weight and finding values for associated parameters to satisfy the further constraint, and repeating the selecting of further constraints and the finding of values for associated parameters.
-
Citations
30 Claims
-
1. A method comprising:
-
identifying a plurality of circuit parameters, the parameters specifying different aspects of a design for an electronic circuit, each parameter having a plurality of different possible values; sorting a set of constraints based on weights associated with each constraint, the constraints being capable of being satisfied based on values selected for corresponding associated parameters, the constraints limiting possible values for the corresponding associated parameters; selecting a constraint that is unsatisfied and that has the greatest weight; selecting parameters associated with the constraint and finding parameter values to satisfy the constraint; after satistying the selected unsatisfied constraint, selecting a further unsatisfied constraint having the next greatest weight and finding values for associated parameters to satisfy the further constraint; repeating the selecting of further constraints and the finding of values for associated parameters; and defining the electronic circuit using the found parameter values. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A machine-readable medium having stored thereon data representing instructions which, when executed by a machine, cause the machine to perform operations comprising:
-
identifying a plurality of circuit parameters, the parameters specifying different aspects of a design for an electronic circuit, each parameter having a plurality of different possible values; sorting a set of constraints based on weights associated with each constraint, the constraints being capable of being satisfied based on values selected for corresponding associated parameters, the constraints limiting possible values for the corresponding associated parameters; selecting a constraint that is unsatisfied and that has the greatest weight; selecting parameters associated with the constraint and finding parameter values to satisfy the constraint; after satisfying the selected unsatisfied constraint, selecting a further unsatisfied constraint having the next greatest weight and finding values for associated parameters to satisfy the further constraint; repeating the selecting of further constraints and the finding of values for associated parameters; and defining the electronic circuit using the found parameter values. - View Dependent Claims (12, 13, 14, 15, 16)
-
-
17. An apparatus comprising:
-
a memory containing information regarding a plurality of circuit parameters, the parameters specifying different aspects of a design for an electronic circuit, each parameter having a plurality of different possible values, a set of constraints, the constraints being associated with weights, and the constraints being capable of being satisfied based on values selected for corresponding associated parameters; and a processor to solve a constraint satisfaction problem by; sorting the set of constraints based on the weights associated with each constraint; selecting a constraint that is unsatisfied and that has the greatest weight; selecting parameters associated with the constraint and finding parameter values to satisfy the constraint; after satisfying the selected unsatisfied constraint, selecting a further unsatisfied constraint having the next greatest weight and finding values for associated parameters to satisfy the further constraint; repeating the selecting of further constraints and the finding of values for associated parameters; and defining the electronic circuit using the found parameter values. - View Dependent Claims (18, 19, 20, 21)
-
-
22. A system comprising:
-
an I/O interface to receive metadata regarding a plurality of circuit parameters, the parameters specifying different aspects of a design for an electronic circuit, each parameter having a plurality of different possible values and regarding a set of constraints, the constraints being associated with weights, the constraints limiting possible values for the corresponding associated parameters, and the constraints being capable of being satisfied based on values selected for corresponding associated parameters; a compiler to convert the metadata into operable information; a constraint softer to sort the set of constraints based on the weights associated with each constraint, and to repeat the sorting of constraints upon the satisfaction of a constraint; a constraint selector to select a constraint that is unsatisfied and that has the greatest weight, and after the selected unsatisfied constraint is satisfied, selecting a further unsatisfied constraint having the next greatest weight; and a parameter selector to select parameters associated with selected constraint and find parameter values to satisfy the constraints, and to thereby define the electronic circuit using the found parameter values. - View Dependent Claims (23, 24, 25)
-
-
26. A method comprising:
-
selecting a set of circuit parameters to specify different aspects of a design of an electronic circuit, where each parameter has a plurality of different possible values; defining domains for each of the parameters; establishing constraints to limit possible values of the parameters; applying a weight to each constraint, the weight being related to the priority of the constraint; setting relationships between the parameters and the constraints; and solving for an optimal set of parameter values to define the electronic circuit. - View Dependent Claims (27, 28, 29, 30)
-
Specification