Systems and methods for determining costs associated with a selected objective

• US 20050204320A1
• Filed: 03/11/2004
• Published: 09/15/2005
• Est. Priority Date: 03/11/2004
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Chen, Thomas W., McGuffin, Tyson R.
• Granted Patent: US 7,139,986 B2
• Time in Patent Office: Days
• US Class Current: 716/54
• CPC Class Codes: G06F 30/00 Computer-aided design [CAD]

Abstract

Systems and methods associated with costs of a selected objective are disclosed. One embodiment of a system may comprise a constraint evaluator that evaluates a value set associated with a plurality of objectives to determine if a non-selected objective has violated at least one constraint. The system may further comprise a cost function configurable to evaluate a cost associated with the value set at a first cost range if the value set violates the at least one constraint associated with the non-selected objective, and to evaluate a cost associated with the value set at a second cost range associated with the selected objective if the value set does not violate the at least one constraint associated with the non-selected objective, such that the second cost range is different from the first cost range.

Claims

1. A system for determining a cost associated with a selected objective from a plurality of objectives, the system comprising:

a constraint evaluator that evaluates a value set associated with a plurality of objectives to determine if a non-selected objective has violated at least one constraint; and

a cost function configurable to evaluate a cost associated with the value set at a first cost range if the value set violates the at least one constraint associated with the non-selected objective, and to evaluate a cost associated with the value set at a second cost range associated with the selected objective if the value set does not violate the at least one constraint associated with the non-selected objective, the second cost range being different from the first cost range.

2. The system of claim 1, further comprising a genetic algorithm that generates at least one generation of chromosomes from parent chromosomes selected from a chromosome pool of value sets and associated costs determine by the cost function, the genetic algorithm selecting parent chromosomes with lower costs from the chromosome pool.

3. The system of claim 1, wherein the constraint evaluator evaluates the value set to determine if at least one additional non-selected objective has violated at least one constraint, the cost function being configurable to evaluate a cost associated with the at least one additional non-selected objective at at least one additional cost range.

4. The system of claim 1, further comprising an analysis tool that generates parameters based on a value set solution, the parameters being associated with the selected objective and the non-selected objective.

6. The system of claim 1, wherein the cost function is configurable to evaluate costs associated with the non-selected objective at the first cost range, and to evaluate costs associated with the selected objective at the second cost range, the first cost range being substantially higher than the second cost range.

7. The system of claim 6, wherein the value set solution is associated with a circuit design configuration.

8. The system of claim 7, wherein the non-selected objective is timing constraints associated with at least one cell block of the circuit design configuration, and the selected objective is power associated with the circuit design configuration, the system evaluating costs at the first cost range if the circuit design configuration violates timing constraints associated with at least one cell block and the system evaluating costs at the second cost range if the circuit design configuration does not violate timing constraints associated with the at least one cell block.

9. The system of claim 8, wherein the timing constraint comprise slack constraints.

5. The system of claim 5, the analysis tool being a circuit design analysis tool and the value set solution being a circuit design description.

10. A system for selecting a value set based on a cost associated with a selected objective, the system comprising:

a first cost function that evaluates costs of a value set associated with a non-selected objective if the value set does not meet at least one constraint associated with the non-selected objective;

a second cost function that evaluates costs of the value set associated with the selected objective if the value set does meet the at least one constraint associated with the non-selected objective; and

a genetic algorithm that selects chromosomes with lower costs from chromosomes created from value sets and associated costs evaluated by the first and second cost functions to generate value set variations.

11. The system of claim 10, further comprising a constraint evaluator that selects between the first cost function and the second cost function, the first cost function determines cost at a first cost range and the second cost function determines cost at a second cost range, wherein the first cost range is substantially higher than the second cost range.

12. The system of claim 11, wherein the constraint evaluator further selects between the first cost function and the second cost function for value set variations generated by the genetic algorithm.

13. The system of claim 12, further comprising a chromosome pool that retains value sets and value set variations and associated costs represented as chromosomes, the genetic algorithm selecting chromosomes with lower associated costs from the chromosome pool to generate value set variations.

14. The system of claim 10, wherein the value set is associated with a circuit design configuration.

15. The system of claim 14, wherein the non-selected objective is slack constraints associated the circuit design configuration, and the selected objective is power associated with the circuit design configuration, the system evaluating costs based on slack if the value set violates at least one slack constraint associated with the circuit design configuration and the system evaluating costs based on power if slack constraints associated with the circuit design configuration are met.

16. A system for minimizing a cost associated with a selected objective from a multi-objective cost function, the system comprising:

means for generating parameters associated with the selected objective and a non-selected objective from a value set;

means for determining if parameters associated with the non-selected objective meet at least one non-selected objective constraint; and

means for configuring a multi-objective cost function to evaluate costs at a first cost range if parameters associated with the non-selected objective do not meet the at least one non-selected objective constraint and evaluating costs at a second cost range if parameters associated with the non-selected objective do meet the at least one non-selected objective constraint.

17. The system of claim 16, further comprising means for generating value set variations based on value sets with associated lower costs.

18. The system of claim 16, wherein the first cost range is substantially higher than the second cost range, such that the means for generating value set variations converge to value set variations in the second cost range.

19. The system of claim 16, wherein the value set is a circuit design configuration, the non-selected objective is slack constraints associated the circuit design configuration, and the selected objective is power associated with the circuit design configuration.

20. A method for determining a cost associated with a selected objective from a plurality of objectives, the method comprising:

generating a cost for a value set based on a non-selected objective if the value set does not meet constraints associated with the non-selected objective, and on the selected objective if the value set does meet constraints associated with the non-selected objective;

generating at least one value set variation based on value sets with lower costs; and

repeating the generating of a cost based on one of the non-selected objective and the selected objective for the at least one value set variation.

21. The method of claim 20, wherein the generating a cost for a value set based on a non-selected objective is in a first cost range and the generating a cost for a value set based on a selected objective is in a second cost range, wherein the first cost range is substantially higher than the second cost range.

22. The method of claim 20, wherein the generating at least one value set variation based on value sets with lower costs comprising executing a genetic algorithm on at least one value set to generate the at least one value set variation.

23. The method of claim 20, further comprising repeating generating at least one value set variation based on value sets with lower costs and the repeating the generating of a cost based on one of the non-selected objective and the selected objective for the at least one value set variation, until a value set variation with an acceptable selected objective cost is achieved.

24. The method of claim 20, the value set and at least one value set variation corresponding to different circuit design configurations.

25. The method of claim 24, the constraints associated with the non-selected objective being timing constraints and the selected objective being power.

26. A computer readable medium having computer executable instructions for performing a method comprising:

generating a first set of parameters associated with a non-selected objective and a second set of parameters associated with a selected objective, the first and second set of parameters being based on a value set;

generating costs at a first cost range based on the first set of parameters if the first set of parameters do not meet constraints associated with the non-selected objective; and

generating costs at a second cost range based on the second set of parameters if the first set of parameters do not meet constraints associated with the non-selected objective, the first cost range being substantially higher than the second cost range.

27. The computer readable medium having computer executable instructions for performing the method of claim 26, further comprising:

storing value sets and associated costs as chromosomes in a chromosome pool; and

executing a genetic algorithm on the stored value sets to generate value set variations based on chromosomes in the chromosome pool with lower costs.

28. The computer readable medium having computer executable instructions for performing the method of claim 27, further comprising repeating generating costs, storing value sets and executing the genetic algorithm, until a desirable value set variation is determined to have an acceptable cost based on the selected objective.

29. The computer readable medium having computer executable instructions for performing the method of claim 28, the value set and value set variations corresponding to different circuit design configurations.

30. The computer readable medium having computer executable instructions for performing the method of claim 29, the constraints associated with the non-selected objective being timing constraints and the selected objective being power.