Solutions for constraint satisfaction problems requiring multiple constraints

• US 7,260,562 B2
• Filed: 06/30/2003
• Issued: 08/21/2007
• Est. Priority Date: 06/30/2003
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Czajkowski, Greg, Miller, Mike F.
• Primary Examiner(s): Starks, Jr.; Wilbert L.
• Application Number:
  US10/609,794
• Publication Number:
  US 20050010922A1
• Time in Patent Office: 1,513 Days
• Field of Search: 382/156, 704/8, 706/46, 706/13, 707/6, 716/1, 716/4, 716/8, 703/6, 703/14
• US Class Current: 706/46
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

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.

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.

2. The method of claim 1, wherein repeating comprises repeating the selecting of further constraints and the finding of values for associated parameters until the set of constraints is satisfied.

3. The method of claim 1, further comprising evaluating satisfied constraints after finding values for parameters associated with an unsatisfied constraint and, if a satisfied constraint is not satisfied using the found parameter values, ten designating the constraint as unsatisfied.

4. The method of claim 1, wherein finding parameter values comprises perforthing a depth first walk of each selected associated parameter.

5. The method of claim 1, wherein finding parameter values comprises selecting parameters associated with a different constraint, finding parameter values to satisfy the different constraint, and then finding parameter values for the selected constraint.

6. The method of claim 1, further comprising tagging satisfied parameters as unsatisfied after finding parameter values to satisfy the different constraint.

7. The method of claim 1, wherein the parameters correspond to different data types.

8. The method of claim 1, wherein the different data types comprise numbers and strings.

9. The method of claim 1, wherein the parameters are further defined by domains and the domains include numerical ranges and lists.

10. The method of claim 1, further comprising deriving weights for association with constraints using at least one of parameter weights and parameter domain weights.

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.

12. The medium of claim 11, wherein the instructions for repeating comprise instructions which, when executed by the machine, cause the machine to perform further operations comprising repeating the selecting of further constraints and the finding of values for associated parameters until the set of constraints is satisfied.

13. The medium of claim 11, wherein the instructions for finding parameter values comprise instructions which, when executed by the machine, cause the machine to perform further operations comprising selecting parameters associated with a different constraint, finding parameter values to satisfy the different constraint, and then finding parameter values for the selected constraint.

14. The medium of claim 11, wherein the parameters correspond to different data types.

15. The medium of claim 11, wherein the parameters are further defined by domains, the domains are associated with weights, and the domains include numerical ranges and lists.

16. The medium of claim 11, further comprising instructions which, when executed by the machine, cause the machine to perform further operations comprising deriving weights for association with constraints using at least one of parameter weights and parameter domain weights.

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.

18. The apparatus of claim 17, wherein repeating comprises repeating the selecting of further constraints and the finding of values for associated parameters until the set of constraints is satisfied.

19. The apparatus of claim 17, wherein the processor further solves the constraint satisfaction problem by evaluating satisfied constraints after finding values for parameters associated with an unsatisfied constraint and, if a satisfied constraint is not satisfied using the found parameter values, then designating the constraint as unsatisfied.

20. The apparatus of claim 17, wherein the information is stored as metatext in a markup language.

21. The apparatus of claim 17, wherein the metatext defines different data types.

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.

23. The system of claim 22, wherein the constraint selector selects further constraints and the parameter selector finds further values for associated parameters until the set of constraints is satisfied.

24. The system of claim 22, wherein the constraint sorter evaluates satisfied constraints after values for parameters associated with an unsatisfied constraint are found and, if a satisfied constraint is not satisfied using the found parameter values, then designates the constraint as unsatisfied.

25. The system of claim 22, wherein the metatext defines different data types.

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.

27. The method of claim 26, further comprising expressing the domains as metatext and expressing the constraints in a higher level language.

28. The method of claim 26, further comprising assigning weights to each of the parameters.

29. The method of claim 26, further comprising assigning weights to possible value for at least some of the parameters.

30. The method of claim 26, wherein establishing constraints comprises defining relationships among the parameters.