Random code generation using genetic algorithms

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.

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 1 ; and    (B)(2)(b)(ii) deciding to provide the synthesized value for knob K P  in the synthesized configuration file only if x 1  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 1 ; and    means for deciding to provide the synthesized value for knob K P  in the synthesized configuration file only if x 1  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 1  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 1 ; and  
 (D)(3)(c) including the synthesized value for knob K P  in the synthesized configuration file only if x 1  is less than p 1 .  
   
   
   
       19 . The method of  claim 18 , wherein the step (D)(3)(a) comprises a step of selecting as the probability p 1  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 2 ;    (D)(2)(b) randomly selecting a number x 2 ;    (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 2  is greater than p 2 ; and    (D)(2)(d) if x 2  is not greater than p 2 , 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 1  that the synthesized value for knob K P  will not be included in the synthesized configuration file; (b) randomly selecting a number x 1 ; and (c) including the synthesized value for knob K P  in the synthesized configuration file only if x 1  is less than p 1 .    
   
   
       25 . The system of  claim 24 , wherein the means for selecting the probability p 1  comprises means for selecting as the probability p 1  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 2 ;    means for randomly selecting a number x 2 ;    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 2  is greater than p 2 ; and    means for performing the following steps if x 2  is not greater than p 2 : (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.