Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital logic testing
Reexamination Certificate
1999-12-17
2004-01-13
Ton, David (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital logic testing
C714S738000
Reexamination Certificate
active
06678853
ABSTRACT:
TECHNICAL FIELD
The invention relates generally to random code generation for testing the operation of an integrated circuit design and, more particularly, to a system for improving the ability of a random test generator to produce effective test cases by controlling the randomness of the generated test code through the addition of a further level of user controlled randomness.
BACKGROUND OF THE INVENTION
In verifying microprocessors, random code generators, also called random generators, are used frequently. (The use of the term “random” herein is intended to include the cases of pseudo-random random and truly random.) Random code generators offer the advantage of producing code for test cases much faster than a human can write them by hand, and they can be steered around known problems more easily than adapting existing hand written code. Random code generators can also generate a staggering variety of test cases by randomizing the initial state, the instruction mix, and many other parameters.
In order to generate code, the user supplies the random code generator with some parameters, typically a set of probabilities and a random seed, along with other miscellaneous information such as how many codesets to generate, how long to make each codeset, etc.
Random code generators are typically controlled with a probability file, or control file, which typically contains a list of parameters and values. Such parameters typically control the distribution of instructions (e.g., loads, stores, adds, etc.) and the probability of other events (like initializing data in a cache). By adjusting the settings in the control file, the generator can be steered into specific areas of the test space, or steered away from certain areas of the test space.
For example, if the probability file consists of the following parameters and settings:
load
25
store
25
add
25
branch
25
The generator might, if asked to generate a case with 100 instructions, generate 25 loads, 25 stores, 25 adds, and 25 branches. The instructions may be in any mixture; only the approximate relative likelihoods of each kind of instruction is specified.
By setting the “Load” parameter to 0, the user can prevent the generation of load instructions altogether, enabling testing of a microprocessor on which loads are known to be a problem. This is a very desirable feature for a variety of reasons. First, the user can focus on specific areas known to be at risk. Second, if testing multiple prototypes of a processor, each prototype may have different characteristics electrically. For example, one may have a problem where the processor cannot execute loads at a certain clock frequency, or another processor may execute loads but be incapable of performing adds. The control file allows users to generate specific cases for specific circumstances.
One of the important tradeoffs in designing and implementing a random code generator is determining how much control to give the user over the generator. While the ability to steer a generator into or away from a certain part of the test space is invaluable, it does not come without some conflicts. On one hand, the user wants enough control to be able to steer the generator into some parts of the test space, or steer it away from some parts of the test space (to avoid known difficulties). On the other hand, the user would like to generate a significant variety of cases from a specific control file. As a result, some random code generators have few or no controls, and other code generators have many control parameters to enable careful steering. However, having a large number of control parameters leads to the control files becoming unwieldy and difficult to use simply because of the sheer number of controls. Another even more difficult problem is that with a large number of parameters, the control file often essentially completely describes the test cases it produces, effectively leaving little randomness remaining in the test cases.
A generator with few or no controls tends to require modifications (e.g., source code changes) to the code generator to work around problems encountered in the test cases, or they focus on a particular part of the test space to the exclusion of others. This becomes problematic when several users may need slightly different versions of the code generator, which creates a lot of work for the person developing and maintaining the random code generators.
Long control files also create difficulties. First, such control files are unwieldy and can become difficult for a casual user to write. Second, a long and detailed control file can place so much constraint on the resulting test cases that all codesets arising from a given set of controls look essentially alike. This in turn means that such a control file is only useful to generate a few cases from a given set of controls. And this in turn means users must generate many unique control files for all of their tests. Since control files can be unwieldy and time consuming to write completely by hand, practitioners in the art have generally used computer programs to generate control files, including the use of random code generators to generate completely random control files. However, these machine-generated control files often produce cases of dubious quality because it is difficult to maintain useful correlations between a large number of controls.
Further background on random code generation can be found in U.S. Pat. No. 5,729,554, Weir et al.; U.S. Pat. No. 5,771,241, Brummel; and U.S. Pat. No. 5,784,550, Brockmann et al., each of which is incorporated herein by reference.
SUMMARY OF THE INVENTION
In one respect, the invention describes a method of producing random computer code. The method comprises the steps of generating a random weight for an instruction type, and then generating randomly determined computer code wherein a statistical likelihood of generating the instruction type in the code is based on the random weight for the generated instruction type.
In another respect, the invention is an apparatus for use in producing random computer code consisting of code instructions. The apparatus comprises a random value generator and a random code generator that is connected to the random value generator. The random code generator produces an output file in which the proportion of at least one computer instruction type is related to a random number produced by the random value generator.
In yet another respect, the invention is a form of computer software embedded on a computer readable medium. The software includes the instructions necessary to perform the steps of generating a random weighting factor for a predetermined instruction type, and to generate computer code randomly in approximate proportion by instruction type to its assigned weighting factor.
In comparison to random code generators using purely predetermined control parameters or random code generators using purely random control parameters, certain embodiments of the present invention are capable of achieving certain advantages, including the following:
(1) The ability to generate a large variety of codesets from a single control file;
(2) The ability to generate a large variety of codesets using a small set of control types;
(3) The ability to effectively and precisely steer a code generator if desired; and
(4) The combined advantages of large code variety and precise steerability together.
REFERENCES:
patent: 4688223 (1987-08-01), Motika et al.
patent: 4801870 (1989-01-01), Eichelberger et al.
patent: 5455891 (1995-10-01), Hirotsu et al.
patent: 5455938 (1995-10-01), Ahmed
patent: 5485471 (1996-01-01), Bershteyn
patent: 5729554 (1998-03-01), Weir et al.
patent: 5771241 (1998-06-01), Brummel
patent: 5784550 (1998-07-01), Brockmann et al.
patent: 5859999 (1999-01-01), Morris et al.
patent: 5860017 (1999-01-01), Sharangpani et al.
patent: 5913064 (1999-06-01), Chen
Wolfe, A., “Patents shed light on Merced's Innards”, Electronic Engineering Times, Feb. 15, 1999.
Hewlett--Packard Development Company, L.P.
Ton David
LandOfFree
Method and apparatus for generating random code does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for generating random code, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating random code will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3193604