Random code generation using genetic algorithms

• US 6,918,098 B2
• Filed: 07/16/2002
• Issued: 07/12/2005
• Est. Priority Date: 07/16/2002
• 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: Becker, Lee, Heckman, David Albert, Smith, Zachary Steven
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): Kik, Phallaka
• Application Number:
  US10/195,993
• Publication Number:
  US 20040015791A1
• Time in Patent Office: 1,092 Days
• Field of Search: 716/4, 716/18, 703/16, 703/26, 703/28, 702/118, 714/28, 714/33, 714/39, 714/728, 714/735, 714/739
• US Class Current: 716/106
• CPC Class Codes: G01R 31/318307 computer-aided, e.g. automatic test program generator [ATPG], program translations, test program debugging
• CPC Class Codes: G01R 31/318357 Simulation computer simulation of digital circuits G06F30/3308
• CPC Class Codes: G01R 31/318385 Random or pseudo-random test pattern
• CPC Class Codes: G06F 30/33 Design verification, e.g. functional simulation or model checking

Abstract

Techniques are disclosed for automatically generating test instructions for use in testing a microprocessor design. A configuration file includes a plurality of knobs which specify a probability distribution of a plurality of microprocessor instructions. A random code generator takes the configuration file as an input and generates test instructions which are distributed according to the probability distribution specified by the knobs. The test instructions are executed on the microprocessor design. The microprocessor behaviors that are exercised by the test instructions are measured and a fitness value is assigned to the configuration file using a fitness function. The configuration file and its fitness value are added to a pool of configuration files. A configuration file synthesizer uses a genetic algorithm to synthesize a new configuration file from the pool of existing configuration files. This process may be repeated to generate configuration files which increasingly exercise microprocessor behaviors which are of interest.

Claims

1. In a system including a circuit design and a plurality of circuit input vectors which have been applied to the circuit design to produce at least one occurrence of each of a plurality of events within the circuit design, a method comprising:

(A) identifying a plurality of counter values indicating a number of occurrences of each of the plurality of events;

(B) initializing an aggregate fitness value; and

(C) performing the following for each event e in the plurality of events;

(C) (1) identifying a counter value indicating a number of occurrences of event e;

(C) (2) applying a counter fitness function to the counter value identified in (C) (1) to produce a counter fitness value; and

(C) (3) applying a combination function to the aggregate fitness value and the counter fitness value to produce a new value for the aggregate fitness value.

2. The method of claim 1, wherein the counter fitness function comprises a function f₁(c_i)=c_i, wherein c_i comprises the counter value, and wherein the combination function comprises a function f₂(V, V_i)=V+V_i, wherein V comprises the aggregate fitness value and wherein V_i comprises the counter fitness value.

3. The method of claim 1, wherein the counter fitness function comprises a function f₁(c_i)=1+A+B*log(c_i), wherein c_i comprises the counter value, and wherein the combination function comprises a function f₂(V, V_i)=V+V_i, wherein V comprises the aggregate fitness value and wherein V_i comprises the counter fitness value, wherein A and B are constant weighting factors.

4. The method of claim 3, wherein the value of A is zero and the value of B is one.

5. The method of claim 1, wherein the circuit design comprises a microprocessor design and wherein the plurality of circuit input vectors comprises a plurality of test instructions which have been executed on the microprocessor design.

6. The method of claim 1, wherein the circuit design comprises a physical microprocessor.

7. The method of claim 1, wherein the circuit design comprises a software model of a microprocessor.

8. The method of claim 1, wherein the at least one event comprises at least one event monitored by a performance monitoring unit associated with the circuit design.

9. A system comprising:

a circuit design;

a plurality of circuit input vectors which have been applied to the circuit design to produce at least one occurrence of a plurality of events within the circuit design;

counter value identification means for identifying a plurality of counter values indicating a number of occurrences of each of the plurality of events;

means for initializing an aggregate fitness value; and

fitness calculation means for performing the following for each event e in the plurality of events;

(1) identifying a counter value indicating a number of occurrences of event e;

(2) applying a counter fitness function to the counter value identified in (1) to produce a counter fitness value; and

(3) applying a combination function to the aggregate fitness value and the counter fitness value to produce a new value for the aggregate fitness value.

10. The system of claim 9, wherein the counter fitness function comprises a function f₁(c_i)=c_i, wherein c_i comprises the counter value, and wherein the combination function comprises a function f₂(V, V_i)=V+V_i, wherein V comprises the aggregate fitness value and wherein V_i comprises the counter fitness value.

11. The system of claim 9, wherein the counter fitness function comprises a function f₁(c_i)=1+A+B*log(c_i), wherein c_i comprises the counter value, and wherein the combination function comprises a function f₂(V, V_i)=V+V_i, wherein V comprises the aggregate fitness value and wherein V_i comprises the counter fitness value, wherein A and B are constant weighting factors.

12. The system of claim 11, wherein the value of A is zero and the value of B is one.

13. The system of claim 9, wherein the circuit design comprises a microprocessor design and wherein the plurality of circuit input vectors comprises a plurality of test instructions which have been executed on the microprocessor design.

14. The system of claim 9, wherein the circuit design comprises a physical microprocessor.

15. The system of claim 9, wherein the circuit design comprises a software model of a microprocessor.

16. The system of claim 9, wherein the at least one event comprises at least one event monitored by a performance monitoring unit associated with the circuit design.