Method and apparatus for random stimulus generation

• US 6,449,745 B1
• Filed: 04/22/1999
• Issued: 09/10/2002
• Est. Priority Date: 04/22/1999
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Synopsys Incorporated
• Inventors: Chapiro, Daniel Marcos, Meyer, Mary Lynn, Kim, Won Sub
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): Torres, Joseph D.
• Application Number:
  US09/298,981
• Time in Patent Office: 1,237 Days
• Field of Search: 714/724, 714/727, 714/728, 714/738, 714/739
• US Class Current: 714/739
• CPC Class Codes: G01R 31/31813 Test pattern generators
• 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/318385 Random or pseudo-random test pattern

Abstract

The present invention adds capabilities to a Hardware Verification Language (HVL) which facilitate the generation of random test data. Sources of random numbers are easily produced by simply adding a randomness attribute to a variable declaration of a class definition. Such variables are called random variables. A “randomize” method call may be made to an instance of the class definition to produce random values for each random variable. The values assigned to random variables are controlled using constraint blocks, which are part of the class definition. A constraint block is comprised of constraint expressions, where each constraint expression limits the values that can be assigned to a random variable on the left-hand-side (lhs) of the constraint expression. Because random variables may also appear on the right-hand-side (rhs) of a constraint expression there is an ordering in which random variable values must be assigned and this dependency is expressed by directed acyclic graphs (DAGs). A linear ordering for assigning values to the random variables is derived from the DAGs. The constraint expressions constraining each random variable are converted into ranges of permissible values from which a value is chosen at random.

Claims

1. A method for generating values, comprising:

generating a graph data structure representing a dependency relation, determined by at least one declarative constraint, between at least a first and a second value generator;

generating a linear ordering, from the graph data structure, such that the first value generator is ordered before the second value generator if the second value generator depends upon a first value generated by the first value generator; and

generating a first valid-values data structure, containing at least a range of valid values, for the first value generator before generating a second valid-values data structure, containing at least a range of valid values, for the second value generator.

2. The method of claim 1, wherein the graph data structure is a directed acyclic graph.

3. The method of claim 1, wherein the first value generator is constrained by at least a first constraint data structure and the second value generator is constrained by at least a second constraint data structure.

4. The method of claim 3, wherein the second constraint data structure depends on the first constraint data structure.

5. The method of claim 1, wherein the step of generating a first valid-values data structure comprises,

traversing at least a first constraint data structure associated with the first value generator; and

generating at least a range of valid values for the first value generator satisfying at least the first constraint data structure.

6. A data processing system for generating values, comprising:

a circuit configured to generate a graph data structure representing a dependency relation, determined by at least one declarative constraint, between at least a first and a second value generator;

a circuit configured to generate a linear ordering, from the graph data structure, such that the first value generator is ordered before the second value generator if the second value generator depends upon a first value generated by the first value generator; and

a circuit configured to generate a first valid-values data structure, containing at least a range of valid values, for the first value generator before generating a second valid-values data structure, containing at least a range of valid values, for the second value generator.

7. A computer program product comprising:

a computer usable medium having computer readable code embodied therein for causing generation of values, the computer program product including;

computer readable program code devices configured to cause a computer to effect generating a graph data structure representing a dependency relation, determined by at least one declarative constraint, between at least a first and a second value generator;

computer readable program code devices configured to cause a computer to effect generating a linear ordering, from the graph data structure, such that the first value generator is ordered before the second value generator if the second value generator depends upon a first value generated by the first value generator; and

computer readable program code devices configured to cause a computer to effect generating a first valid-values data structure, containing at least a range of valid values, for the first value generator before generating a second valid-values data structure, containing at least a range of valid values, for the second value generator.

8. An electronic data signal representing sequences of instructions which, when executed by a data processing system, cause generation of values by performing the steps of:

generating a graph data structure representing a dependency relation, determined by at least one declarative constraint, between at least a first and a second value generator;

generating a linear ordering, from the graph data structure, such that the first value generator is ordered before the second value generator if the second value generator depends upon a first value generated by the first value generator; and

generating a first valid-values data structure, containing at least a range of valid values, for the first value generator before generating a second valid-values data structure, containing at least a range of valid values, for the second value generator.