Data processing: measuring – calibrating – or testing – Testing system – Of circuit
Reexamination Certificate
2001-09-28
2004-04-27
Hoff, Marc S. (Department: 2857)
Data processing: measuring, calibrating, or testing
Testing system
Of circuit
C702S120000, C702S122000, C702S123000
Reexamination Certificate
active
06728654
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computer programs that use sequences of pseudo-randomly generated numbers. More specifically, the present invention provides a method to access a sequence of pseudo-randomly generated numbers to insure that each number generated and used in response to each specific call for a number in a software routine is repeatable and predictable from software version to software version.
2. Description of the Related Art
Random test generation programs have been around since the early days of microprocessor verification. These programs automate the complex job of creating large test suites necessary for the functional verification of computer systems by using random number generators to, among other things, generate test stimuli, initialize registers, pre-load caches, select operands, and the like. Those skilled in the art are well aware that the verification of modern circuit designs, especially that of large complex sequential logic designs such as a processor or an entire computer system, often takes the greater part of the resources during a design process. Design verification can be a significant bottleneck, greatly impacting the design cycle and the overall time-to-market of a new design.
In the past, processors and other complex sequential logic circuits were statically verified, meaning that verification tests were assembled from instructions, control flags, and data selected from pre-prepared tables without regard for the intermediate machine states of the processor during the execution of the test. These static tests included some degree of randomness, to increase the number of test cases and to achieve a greater degree of test coverage. For example, a test-case generator might choose a random mix of hand-generated fixed scripts, and insert random parameter values in the scripts. However, static verification methods required painstaking human composition and verification of long, multilevel queries, so they were extraordinarily time-consuming. Even with random selection of scripts and random values for script parameters, the inability to take into account intermediate processor states meant that certain real-life combinations simply went untested. As processors became more complex, the effort required to design and conduct static verification testing increased exponentially, even as the achievable test coverage declined dramatically.
Consequently, the industry has moved toward the use of dynamically generated, biased pseudo-random test patterns, which can automatically and quickly create an efficient, robust test environment for complex sequential circuits such as processors. In dynamic testing, instructions are generated, all processor resources and facilities needed for executing the instruction are identified and initialized if required, the execution of the instruction is simulated on a model of the design under test, and state is updated to reflect the execution results. The process then iterates, and each instruction generated at the beginning of each iteration is generated with knowledge of the processor state that resulted from the last step executed. Although there are differences in the details of how instructions are generated from test method to test method, in general, instructions are selected for generation using some version of a pseudo-random number generator. Those skilled in the art are generally familiar with the various current methods used to generate and use pseudorandom numbers to support functional verification of complex circuits using dynamically generated biased psuedo-random test patterns.
The relative ease of creating dynamically generated random test programs, combined with the potential for verification bottlenecks, has led logic designers to initiate design verification efforts early in the design process. However, developing appropriate tests using a test generator early, while the design effort is still progressing, requires a significant degree of design flexibility and documentary discipline. Frequent changes to both the test generator and the simulation model are typical, because the system architecture may not be firm, and because implementation-specific details of the test programs are ordinarily decided as the system design progresses. When either the test generator or simulation model is modified, designers typically perform some degree of regression testing, wherein past test patterns are regenerated, rerun, and the results compared, to ensure that no new problems are created by the updates. Also, designers may find it useful to maintain and rerun certain highly successful test patterns from time to time, particularly when a test pattern has been generated that specifically targets a certain function, or is exceptionally complex, or has been determined to provide exceptionally good coverage. Consequently, test patterns must be stored in a library to support regression testing and ongoing design verification efforts.
Rather than storing an entire test pattern, which would require significant storage space, test patterns are saved by storing their control parameters and past results. Control parameters associated with a particular test pattern will typically include some sort of identifying indicia for handling the test pattern in the test library, comments explaining the purpose of the test, the starting seed for the random number generator, and any other externally provided initial conditions to regenerate the program when required. Ordinarily, saving the control parameters of a test pattern is sufficient to assure that the test pattern can be faithfully recreated when required.
However, problems may arise when a test generator, or the simulation model that the generator is using, includes multiple calls to a random number generator for random numbers to perform various aspects of the test generation. In order for a specific test identified by specific control parameters to be repeatable, the random numbers supplied to the test generator must be supplied identically, in response to the same call from the generator or the model every time the test is initiated. Consequently, either the specific order of the test generator's calls for random numbers must be maintained across generator/model software versions, or the specific number that is supplied to the test generator or model in response to each specific call must be maintained across software versions. Absent one of these controls, a particular test identified by certain control parameters may not be repeatable in a test generator that includes multiple calls for random numbers if new calls are inserted. This occurs because the number generator will always generate the same sequence of numbers in the same order in response to the seed contained within the test control parameters.
To illustrate the problem, assume a test generator generating verification tests for a processor under design generates and runs a test pattern P1 that includes random number seed S1. Suppose that the generator first requests a random number to use in selecting an instruction, then a sequence of four random numbers to use in initializing four registers, then a sequence of five random numbers that it uses to preload the cache. Thereafter, the test generator generates the instruction, simulates its execution on the model, and updates state. Table 1 below shows the sequence of random numbers as they are generated and supplied to the various functions of the test generator.
TABLE 1
Generator Request
Random number supplied
Random number use
Request 1
R1
Selecting instruction
for generation
Request 2
R2-R5
Initializing registers 1-4
Request 3
R6-R10
Initializing cache
Assume now that the design is modified to include an additional four registers, triggering a test generator update to initialize those additional four registers. As modified, the generator now first requests a random number to use in selecting an instruction, then a sequence of eight random numbers to use in initializing eight registers, then a sequence
Booth Matthew J.
Booth & Wright LLP
Hoff Marc S.
Intrinsity, Inc.
Suarez Felix
LandOfFree
Random number indexing method and apparatus that eliminates... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Random number indexing method and apparatus that eliminates..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random number indexing method and apparatus that eliminates... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3244695