Systems and methods for determining costs associated with a selected objective

• US 7,139,986 B2
• Filed: 03/11/2004
• Issued: 11/21/2006
• Est. Priority Date: 03/11/2004
• Status: Expired due to Fees

• 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.
• Primary Examiner(s): WHITMORE, STACY
• Application Number:
  US10/798,038
• Publication Number:
  US 20050204320A1
• Time in Patent Office: 985 Days
• Field of Search: 716/2, 716 4- 5
• 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 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 for the value set 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;

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

repeating generating costs, storing value sets, and value set variations and executing a genetic algorithm, until a desirable value set variation is determined to have an acceptable cost within the second cost range based on the selected objective.

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

storing value sets and associated costs as chromosomes in a chromosome pool, each value set having an associated cost that is either in the first cost range or the second cost range;

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

generating costs for the value set variations at the 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;

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

storing value set variations and associated costs as chromosomes in a chromosome pool, each value set variation having an associated cost that is either in the first cost range or the second cost range.

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

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

5. The computer readable medium having computer executable instructions for performing the method of claim 1, further comprising generating a third set of parameters associated with at least one additional non-selected objective, and generating costs at a third cost range based on the third set of parameters if the third set of parameters do not meet constraints associated with the at least one additional non-selected objective, the third cost range being substantially greater than the first cost range and being one of substantially greater than the second cost range and substantially less than the second cost range.

6. The computer readable medium having computer executable instructions for performing the method of claim 1, wherein the non-selected objective is slack constraints associated with a circuit design configuration and the selected objective is power constraints associated with the circuit design configuration.

7. The computer readable medium having computer executable instructions for performing the method of claim 6, further comprising evaluating the costs for at least one cell block based on a slack cost function that provides costs at the first cost range if timing parameters do not meet slack constraints and evaluating the costs for the at least one cell block based on a power function that provides cost at the second cost range if the timing parameters do not meet slack constraints.

8. The computer readable medium having computer executable instructions for performing the method of claim 7, wherein the slack cost function is based on evaluating the following equation:

Cost=M+C*(Slack_Actual−

Slack_Max)

where M and C are constants substantially greater than one, Slack_Actual is the actual slack associated with the at least one cell block and Slack_Max is the maximum allowable slack associated with the at least one cell block; and

the power cost function is based on evaluating the following equation;

Cost=Power

where power is equal to the evaluated power of the at least one cell block.

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

storing value sets and associated costs that is in one of the first cost range and the second cost range as chromosomes in a chromosome pool;

executing a genetic algorithm on the stored value sets to generate value set variations based on selecting parent chromosomes in the chromosome pool with lower costs, the genetic algorithm selecting value sets and value set variations from the first cost range if Slack_Actual>

Slack_Max and selecting at least one value set and value set variation from the second cost range upon at least one chromosome having Slack_Actual<

Slack_Max;

generating costs for the value set variations at the 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;

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

storing value set variations and associated costs as chromosomes in a chromosome pool, each value set variation having an associated cost that is in one of the first cost range and the second cost range.