Random code generation using genetic algorithms

• US 20050223346A1
• Filed: 05/31/2005
• Published: 10/06/2005
• Est. Priority Date: 07/16/2002
• Status: Abandoned Application

• Current Assignee: David Albert Heckman, Lee Becker, Zachary Steven Smith
• Original Assignee: David Albert Heckman, Lee Becker, Zachary Steven Smith
• Inventors: Smith, Zachary Steven, Becker, Lee, Heckman, David Albert
• Application Number:
  US11/141,480
• Publication Number:
  US 20050223346A1
• Time in Patent Office: Days
• US Class Current: 716/102
• 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 configuration files, the plurality of configuration files including a plurality of knobs having a plurality of values specifying a plurality of probability distributions of a plurality of circuit input vectors, a method comprising steps of:

(A) initializing a synthesized configuration file;

(B) selecting a first subset of the plurality of configuration files as a potential parent pool; and

(C) for each knob K_P included in at least one of the plurality of configuration files in the potential parent pool, providing a synthesized value for knob K_P in the synthesized configuration file based on at least one value of knob K_P in the plurality of configuration files in the potential parent pool.

2. The method of claim 1, wherein the plurality of configuration files are associated with a plurality of fitness values, and wherein the step (B) comprises steps of:

(B)(1) selecting as the first subset the plurality of configuration files having the highest fitness values in the plurality of configuration files.

3. The method of claim 1, further comprising a step of:

(D) prior to the step (C), replacing the plurality of configuration files in the potential parent pool with a subset of the plurality of configuration files in the potential parent pool.

4. The method of claim 3, wherein the step (D) comprises a step of replacing the plurality of configuration files in the potential parent pool with a randomly-selected subset of the plurality of configuration files in the potential parent pool.

5. The method of claim 1, wherein the step (C) comprises a step of:

(C)(1) for each knob K_P included in at least one of the plurality of configuration files in the potential parent pool, selecting the synthesized value for knob K_P in the synthesized configuration file from among the at least one value of knob K_P in the plurality of configuration files in the potential parent pool.

6. The method of claim 1, wherein the step (B) comprises steps of:

(B)(1) for each knob K_P which is included in all of the plurality of configuration files in the potential parent pool, selecting the synthesized value for knob K_P from the at least one value of knob K_P in the plurality of configuration files in the potential parent pool; and

(B)(2) for each knob K_P which is not included in all of the plurality of configuration files in the potential parent pool, performing steps of;

(B)(2)(a) identifying the ratio of the number of configuration files in the potential parent pool which include the knob K_P to the number of configuration files in the potential parent pool; and

(B)(2)(b) determining whether to provide the synthesized value for knob K_P in the synthesized configuration file based on the ratio.

7. The method of claim 6, wherein the step (B)(2)(b) comprises steps of:

(B)(2)(b)(i) randomly selecting a number x₁; and

(B)(2)(b)(ii) deciding to provide the synthesized value for knob K_P in the synthesized configuration file only if x₁ is less than the ratio.

8. 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 for execution on the microprocessor design.

9. A system comprising:

a circuit design;

a plurality of configuration files, the plurality of configuration files including a plurality of knobs having a plurality of values specifying a plurality of probability distributions of a plurality of circuit input vectors;

means for initializing a synthesized configuration file;

first selection means for selecting a first subset of the plurality of configuration files as a potential parent pool; and

synthesizing means for providing a synthesized value in the synthesized configuration file for each knob K_P included in at least one of the plurality of configuration files in the potential parent pool based on at least one value of knob K_P in the plurality of configuration files in the potential parent pool.

10. The system of claim 9, wherein the plurality of configuration files are associated with a plurality of fitness values, and wherein the first selection means comprises:

second selection means for selecting as the first subset the plurality of configuration files having the highest fitness values in the plurality of configuration files.

11. The system of claim 9, further comprising:

means for replacing the plurality of configuration files in the potential parent pool with a subset of the plurality of configuration files in the potential parent pool prior to execution of the synthesizing means.

12. The system of claim 11, wherein the means for replacing the plurality of configuration files comprises means for replacing the plurality of configuration files in the potential parent pool with a randomly-selected subset of the plurality of configuration files in the potential parent pool.

13. The system of claim 9, wherein the synthesizing means comprises:

means for selecting, for each knob K_P included in at least one of the plurality of configuration files in the potential parent pool, the synthesized value for knob K_P in the synthesized configuration file from among the at least one value of knob K_P in the plurality of configuration files in the potential parent pool.

14. The system of claim 9, wherein the first selection means comprises:

means for selecting, for each knob K_P which is included in all of the plurality of configuration files in the potential parent pool, the synthesized value for knob K_P from the at least one value of knob K_P in the plurality of configuration files in the potential parent pool; and

inclusion determination means for performing the following steps for each knob K_P which is not included in all of the plurality of configuration files in the potential parent pool;

(a) identifying the ratio of the number of configuration files in the potential parent pool which include the knob K_P to the number of configuration files in the potential parent pool; and

(b) determining whether to provide the synthesized value for knob K_P in the synthesized configuration file based on the ratio.

15. The system of claim 14, wherein the inclusion determination means comprises:

means for randomly selecting a number x₁; and

means for deciding to provide the synthesized value for knob K_P in the synthesized configuration file only if x₁ is less than the ratio.

16. 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 for execution on the microprocessor design.

17. In a system including a circuit design and a plurality of configuration files, the plurality of configuration files including a plurality of knobs having a plurality of values specifying a plurality of probability distributions of a plurality of circuit input vectors, a method comprising steps of:

(A) initializing a synthesized configuration file;

(B) selecting a subset of the plurality of configuration files having the highest fitness values as a potential parent pool;

(C) randomly selecting a subset of the potential parent pool as a plurality of direct parents;

(D) for each knob K_P included in at least one of the direct parents, providing a synthesized value for knob K_P in the synthesized configuration file based on at least one value of knob K_P in the plurality of direct parents.

18. The method of claim 17, wherein step (D) comprises steps of:

(D)(1) determining whether knob K_P is included in all of the direct parents;

(D)(2) selecting the synthesized value for knob K_P from among the at least one value of knob K_P in the plurality of direct parents if it is determined that knob K_P is included in all of the direct parents; and

(D)(3) if it is determined that knob K_P is not included in all of the direct parents, performing steps of;

(D)(3)(a) selecting a probability p₁ that the synthesized value for knob K_P will not be included in the synthesized configuration file;

(D)(3)(b) randomly selecting a number x₁; and

(D)(3)(c) including the synthesized value for knob K_P in the synthesized configuration file only if x₁ is less than p₁.

19. The method of claim 18, wherein the step (D)(3)(a) comprises a step of selecting as the probability p₁ the ratio of the number of direct parents which include the knob K_P to the number of direct parents.

20. The method of claim 18, wherein the step (D)(2) comprises steps of:

(D)(2)(a) selecting a probability p₂;

(D)(2)(b) randomly selecting a number x₂;

(D)(2)(c) selecting the synthesized value for knob K_P from among the at least one value of knob K_P in the direct parents if x₂ is greater than p₂; and

(D)(2)(d) if x₂ is not greater than p₂, performing steps of;

(D)(2)(d)(i) identifying a range R_P of values of knob K_P in the direct parents; and

(D)(2)(d)(ii) selecting the synthesized value for knob K_P from within the range R_P.

21. The method of claim 20, further comprising a step of:

(D)(2)(d)(iii) expanding the range R_P to generate an expanded range R_E; and

wherein the step (D)(2)(d)(ii) comprises a step of selecting the synthesized value for knob K_P from within the expanded range R_E.

22. The method of claim 17, wherein the circuit design comprises a microprocessor design and wherein the plurality of circuit input vectors comprises a plurality of test instructions for execution on the microprocessor design.

23. A system comprising:

a circuit design;

a plurality of configuration files, the plurality of configuration files including a plurality of knobs having a plurality of values specifying a plurality of probability distributions of a plurality of circuit input vectors;

means for initializing a synthesized configuration file;

means for selecting a subset of the plurality of configuration files having the highest fitness values as a potential parent pool;

means for randomly selecting a subset of the potential parent pool as a plurality of direct parents;

synthesizing means for providing, for each knob K_P included in at least one of the direct parents, a synthesized value for knob K_P in the synthesized configuration file based on at least one value of knob K_P in the plurality of direct parents.

24. The system of claim 23, wherein synthesizing means comprises:

means for determining whether knob K_P is included in all of the direct parents;

selection means for selecting the synthesized value for knob K_P from among the at least one value of knob K_P in the plurality of direct parents if it is determined that knob K_P is included in all of the direct parents; and

means for performing the following steps if it is determined that knob K_P is not included in all of the direct parents;

(a) selecting a probability p₁ that the synthesized value for knob K_P will not be included in the synthesized configuration file;

(b) randomly selecting a number x₁; and

(c) including the synthesized value for knob K_P in the synthesized configuration file only if x₁ is less than p₁.

25. The system of claim 24, wherein the means for selecting the probability p₁ comprises means for selecting as the probability p₁ the ratio of the number of direct parents which include the knob K_P to the number of direct parents.

26. The system of claim 24, wherein the selection means comprises:

means for selecting a probability p₂;

means for randomly selecting a number x₂;

means for selecting the synthesized value for knob K_P from among the at least one value of knob K_P in the direct parents if x₂ is greater than p₂; and

means for performing the following steps if x₂ is not greater than p₂;

(i) identifying a range R_P of values of knob K_P in the direct parents; and

(ii) selecting the synthesized value for knob K_P from within the range R_P.

27. The system of claim 26, further comprising:

means for expanding the range R_P to generate an expanded range R_E; and

wherein the selecting the synthesized value for knob K_P from within the range R_P comprises means for selecting the synthesized value for knob K_P from within the expanded range R_E.

28. The system of claim 23, wherein the circuit design comprises a microprocessor design and wherein the plurality of circuit input vectors comprises a plurality of test instructions for execution on the microprocessor design.

29. In a system including a circuit design and a plurality of configuration files, the plurality of configuration files including a plurality of knobs having a plurality of values specifying a plurality of probability distributions of a plurality of circuit input vectors, a method comprising steps of:

(A) generating a first synthesized configuration file based on the plurality of configuration files, the first synthesized configuration file specifying a first synthesized probability distribution of a first subset of the plurality of circuit input vectors;

(B) using the first synthesized configuration file to generate a first test case comprising the first subset of the plurality of circuit input vectors;

(C) providing the first subset of the plurality of circuit input vectors as inputs to the circuit design;

(D) generating a fitness value based on at least one event counter in the microprocessor design, the at least one event counter comprising a count of at least one occurrence of at least one event in the microprocessor design in response to provision of the first subset of the plurality of circuit input vectors;

(E) generating a graded configuration file including the synthesized configuration file and the fitness value; and

(F) adding the graded configuration file to the plurality of configuration files.

30. The method of claim 29, further comprising steps of:

(G) after the step (F), generating a second synthesized configuration file based on the plurality of configuration files, the second synthesized configuration file specifying a second synthesized probability distribution of a second subset of the plurality of circuit input vectors;

(H) using the second synthesized configuration file to generate a second test case comprising the second subset of the plurality of circuit input vectors; and

(I) providing the second subset of the plurality of circuit input vectors as inputs to the circuit design.

31. The method of claim 29, wherein the circuit design comprises a microprocessor design and wherein the plurality of circuit input vectors comprises a plurality of test instructions for execution on the microprocessor design.

32. A system comprising:

a circuit design;

a plurality of configuration files, the plurality of configuration files including a plurality of knobs having a plurality of values specifying a plurality of probability distributions of a plurality of circuit input vectors;

means for generating a first synthesized configuration file based on the plurality of configuration files, the first synthesized configuration file specifying a first synthesized probability distribution of a first subset of the plurality of circuit input vectors;

means for using the first synthesized configuration file to generate a first test case comprising the first subset of the plurality of circuit input vectors;

means for providing the first subset of the plurality of circuit input vectors as inputs to the circuit design;

means for generating a fitness value based on at least one event counter in the microprocessor design, the at least one event counter comprising a count of at least one occurrence of at least one event in the microprocessor design in response to provision of the first subset of the plurality of circuit input vectors;

means for generating a graded configuration file including the synthesized configuration file and the fitness value; and

means for adding the graded configuration file to the plurality of configuration files.

33. The system of claim 32, further comprising:

means for generating a second synthesized configuration file based on the plurality of configuration files, the second synthesized configuration file specifying a second synthesized probability distribution of a second subset of the plurality of circuit input vectors;

means for using the second synthesized configuration file to generate a second test case comprising the second subset of the plurality of circuit input vectors; and

means for providing the second subset of the plurality of circuit input vectors as inputs to the circuit design.

34. The system of claim 32, wherein the circuit design comprises a microprocessor design and wherein the plurality of circuit input vectors comprises a plurality of test instructions for execution on the microprocessor design.