Data processing: structural design – modeling – simulation – and em – Emulation – Of instruction
Reexamination Certificate
2000-02-22
2003-12-30
Broda, Samuel (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Emulation
Of instruction
C703S022000, C712S216000, C712S242000, C714S039000
Reexamination Certificate
active
06671664
ABSTRACT:
TECHNICAL FIELD
The technical field is design verification of central processing units that execute programs according to Instruction Set Architectures.
BACKGROUND
Instruction set architectures (ISA) specify how central processing units (CPU) execute programs. The programs include instructions stored in memory. Instructions are typically simple, primitive operations such as add, branch on condition, load from memory, and store to memory.
To provide for software compatibility with legacy computer systems, modem CPUs should adhere to the ISA with minimal defects. To achieve this goal, computer designers could verify the correct behavior of each kind of instruction in isolation. However, this may not be sufficient because, in an effort to improve performance, modem CPUs may overlap the execution of numerous instructions. In this environment, some defects may be exposed only when specific combinations of instructions are executed in sequence. Thus, the designer may desire to test every combination or sequence of instructions. However, modem CPUs typically execute over 100 instructions, each of which can include numerous options. Mechanically enumerating all of these possible instructions sequences may not feasible. Even if all possible instruction sequences were enumerated, the designer's test regime may be insufficient because many defects require more than just a specific sequence of instructions. In particular, additional events, such as operand data patterns, memory address collisions between instructions, the state of CPU structures such as cache memories, and stimulus received by the CPU can pre condition defects.
One of the most important tools used by a CPU designer to address these challenges is a Random Code Generator (RCG). The RCG creates a random software program that is used during the CPU design and prototype verification process to generate billions of random instructions to test the CPU.
The RCG creates the initial state of the CPU for each random software program. The initial state includes instructions in memory, and data used by these instructions. The data can be located in memory or CPU structures like registers and caches. An expected final state is also required to check the actual final state created by running the random program on the CPU. The expected final state can be created by the RCG. Alternatively, the expected final state can be obtained by running the random software program on a separate CPU reference emulator.
The RCG maintains two models of the state of the CPU registers: the initial state and the current state. The CPU registers and memory are collectively referred to as data locations. In operation, a typical RCG operation creates random values for all data locations and stores them in the initial and current states. The RCG then loops until a desired program length is achieved. A typical random software program length may be 100 instructions or more. A program counter is used to track the instructions in the random software program. If the program counter points to an uninitialized instruction memory, the RCG generates a random instruction and stores the initial and current states. Next, the instruction pointed to by the program counter is emulated, updating the current state. The program counters then increments and the next instruction is examined.
This method may work in some cases, but is often insufficient for generating high quality random software programs in many other cases. Examples of these cases include: 1) when it is desirable for addresses used by load/store instructions to contend for the same cache locations; 2) when it is desirable to avoid instruction operands that result in an excessive number of traps; 3) when it is desirable to select branch target addresses that cause different parts of the program to contend for the same cache locations; and 4) when it is desirable to avoid instruction operands that the ISA specifies are illegal or that may cause unpredictable results.
In current systems, the RCG can set aside a sub set of the registers for specific use such as memory addressing for load and store instructions. Instead of being given random values, these registers can be given desirable values. But these registers cannot be changed by the random software program because they would be overwritten with random values. This makes it impossible for the random software program to test use of these registers after an earlier modification of the registers. This situation provides unacceptable coverage holes.
In other current systems, when the RCG first selects the operands registers for an instruction, and those registers hold values that are undesirable, the RCG may repeat the selection one or more times until more suitable registers are found. The problem is that the requirements for a register value to be desirable are often very specific. Further, no desirable registers may be available. If a desirable register is available, this approach would tend to select the desirable register a disproportionate number of times, thereby reducing the quality of the test coverage.
SUMMARY
A method and an apparatus make available uncommitted register values during the random code generation process. When there is a need for a register to contain a specific (desirable) value, then the register value is committed to that value at that point. Uncommitted values can propagate through one or more previous instructions. All registers and memory begin the test program in the uncommitted state. When the random code generators is done generating the test program, if any uncommitted values remain, then the uncommitted values are committed to arbitrary values.
As an example, if a random code generator is in the process of generating instruction
2
:
1. r
1
=r
2
+3
2. Load memory at r
1
into r
3
:
The values r
1
and r
2
are uncommitted. The RCG desires to commit r
1
to a specific desirable value 1024. The RCG can do this, but this has implications for r
2
, since r
1
=r
2
+3. The RCG must also therefore commit r
2
to 1021.
In an embodiment, the RCG generates random programs by determining a plurality of data locations, with each of the data locations given an unassigned initial content, assigning an initial content to one or more data locations of the plurality of data locations, the assignment occurring exactly once during a random program generation, processing a plurality of instructions, one instruction at a time, in a program execution order, until a desired random program length is achieved, with the processing providing the data locations with current values. The processing includes computing a current content of each of the plurality of data locations, the current content depends on functions of previously processed instructions, and wherein the current content may be unknown when the current content depends on an unassigned initial content of one or more data locations. The processing continues with generation of a random instruction, and, if a current content of a data location consumed by the random instruction depends on an unassigned initial content of at least one data location, the initial content is assigned to the at least one data location that optimizes an effectiveness of the random instruction. Finally, an instruction opcode is assigned to an initial content of a data location pointed to by a program counter, and a program counter is advanced.
REFERENCES:
patent: 5748936 (1998-05-01), Karp et al.
patent: 5881280 (1999-03-01), Gupta et al.
patent: 5926832 (1999-07-01), Wing et al.
patent: 6011908 (2000-01-01), Wing et al.
patent: 6031992 (2000-02-01), Cmelik et al.
Broda Samuel
Hewlett-Packard Development Copany, L.P.
Phan T.
LandOfFree
Management of uncommitted register values during random... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Management of uncommitted register values during random..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Management of uncommitted register values during random... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3094704