Method and Apparatus for Embedding Operand Synthesizing Sequences in Randomly Generated Tests

The invention pertains to computer implemented methods and apparatus for embedding one or more operand synthesizing sequences in a randomly generated test. More particularly, the invention pertains to a flexible queue which enables the synthesis of useful operands during the simulation (or execution) of a randomly generated test.

A random test generator (also known as a "random vector generator" or "random code generator") is often used to verify the operation of a processor. Such a generator randomly generates tests comprising add, load, store, and system configuration instructions. These tests tend to exercise a processor's control paths more fully than typical program code, which for performance reasons often deliberately avoids doing things which it is known are difficult for a processor to do.

Typically, a random test generator comprises a generator and a simulator. The generator computes the initial state for a device under test (DUT), loads that state into a simulator, and then enters a main loop. The DUT may be a model of a processor or a processor prototype (i.e., prototype silicon).

In its main loop, the generator generates random instruction(s), loads them into a simulator's memory, and then causes the instruction(s) to be simulated. The simulator, which may be integrated into the generator or provided by some other means, provides an architectural model of the DUT, and allows the generator to track the architecturally visible state of the DUT and respond appropriately as instructions are generated and simulated.

When a sufficient number of instructions have been generated, the generator exits its main loop. At this point, the generator will have created a "testcase", which comprises both an initial state (in the case of a microprocessor, this initial state comprises values for register files, translation lookaside buffers (TLBs), caches, memory, etc.) and an expected final state (obtained from the simulator) for a DUT.

After compiling a testcase, the initial state of the testcase is loaded onto a DUT and a test is launched. When the test is completed, the resulting state of the DUT is compared against that of the testcase's expected final state, and discrepancies are flagged as errors.

An engineer asserts a certain degree of control over a generator's actions by providing the generator with a configuration file. The programmable configuration file is used to indicate types and frequencies of instructions to be generated, data reference locations, etc.

Although randomly generated tests are very useful in exercising a DUT, certain tests may be skewed away from their intended focus if their instructions cannot consume specific values (sometimes referred to herein as "useful data" or "useful operands").

For example, an engineer may wish to test whether a processor correctly responds to changes in system configuration registers. Because such registers are often privileged (i.e., only usable by operating system code), it is assumed that a programmer understands the ramifications of writing an invalid configuration value into one of these registers, and will not do so. However, random test generators, which typically generate random values that are useless for configuration purposes, must somehow test the DUT's response to changes in configuration. Writing a random value to a configuration register may result in undesirable behavior (i.e., an exception or unpredictable behavior), and cause a test to become erroneous and useless.

Also by way of example, an engineer may wish to generate specific memory addresses for register loads and stores (data references). Careful selection of these addresses is required to fully exercise the features of a processor's memory hierarchy. The generation of entirely random values for these addresses may skew a test away from exercising a memory hierarchy's features.

A variety of techniques have been developed to deal with a random test generator's inability to generate specific values. For example, one conventional technique comprises initializing one or more registers with specific values. However, after doing so, the one or more initialized registers cannot be overwritten and are essentially "used up". As a result, these registers cannot be fully exercised by a random test generator (e.g., the generation of a value cannot interact with consumption of the value). Furthermore, the existence of useful data throughout the duration of a test can preempt the occurrence of certain events (e.g., a bypass).

Another conventional technique for loading useful data into a processor comprises loading data into a register just prior to a point in a test wherein the data is needed. This technique dispenses with a need to dedicate certain registers to the storage of useful data, and allows all registers to be fully exercised. However, a down side of this technique is that one or more load sequences (e.g., "direct loads" or "load immediates") must be repeatedly initiated. Even the simplest load sequences comprise three to six instructions. When these three to six instructions are issued repeatedly, and simulated in generation order, a randomly generated test quickly becomes highly structured and ordered, once again leading to a less than optimum exercise of processor control paths. For example, consider a test wherein a specific value must be loaded into memory after the execution of every tenth instruction. The repetitive issuance of a three instruction load sequence (sometimes referred to herein as a type of "synthesizing sequence") leads to redundancies in 30% of a test's code. In addition to the code redundancy, the repeated use of a single pattern has a calming effect on a test, allowing a DUT to settle down while the value is being synthesized.

The inadequacies of the above techniques are becoming evermore apparent with the advent of superscalar RISC (reduced instruction set computer) processors. For example, in the past, a two way superscalar microprocessor might have had a five stage pipeline with up to ten instructions in the process of execution ("in flight") at any given instant. Such a processor could be exercised with tests of forty to fifty instructions. Current superscalar, out of order execution processors may have fifty or more instructions in flight. This greatly increases the necessary lengths of tests. In recent tests of Hewlett Packard's PA-RISC microprocessor architecture, tests of 150-400 instructions were common, and some tests exceeded 1000 instructions in length. Due to the high number of instructions being generated in such tests, useful data is consumed rather quickly, and either 1) many instructions of a test do not have access to useful data and are merely wasted, or 2) numerous repetitions of a synthesizing sequence are repeated in an effort to continually generate useful data (thereby eliminating much of the test's randomness).

It is therefore a primary object of this invention to provide a flexible queue which enables the synthesis of useful operands in randomly generated tests.

It is a further object of this invention to provide a means for embedding synthesizing sequences in randomly generated tests.

It is yet another object of this invention to provide methods and apparatus which fully exercise and test of all of a processor's control paths.

In the achievement of the foregoing objects, the inventor has devised a flexible queue which enables the synthesis of useful operands in randomly generated microprocessor tests.

As used herein, a queue is defined as comprising an instruction list, plus all of the functions used to manipulate the instruction list; an instruction list is defined as the data component of a queue; and an instruction is defined as a string of data bits which may be consumed by a microprocessor.

In a conventional random test generator, instructions are generated, and then pushed onto a queue in generation order. The following methods and apparatus describe a means of associating a delay with each generated instruction. Instructions are therefore popped off the queue in conformance with their associated delay, rather than in generation order. In this manner, three instructions corresponding to a synthesizing sequence (perhaps a load) might be associated with delays of zero, three and seven. As a result, the first instruction may be immediately popped from the queue and consumed. The second instruction is not popped from the queue until the first instruction and two "other instructions" have been popped from the queue and consumed. The third instruction is not popped from the queue until the first instruction, two "other instructions", the second instruction, and an additional three "other instructions" have been popped from the queue and consumed. The "other instructions" may be any instructions generated by the random test generator after, and without knowledge of, the instructions comprising the synthesizing sequence (which have already been pushed onto the queue).

It should be noted that this method is not the same as storing instructions of the synthesizing sequence in memory addresses M›PC!, M›PC+3!, and M›PC+7! (where PC is some base memory address). If this were the case, restrictions would have to be placed on the "other instructions" to ensure that there were no transfers of flow control (e.g., a taken branch or exception), or there would be no guarantee that the synthesizing sequence would be fully executed. The method described herein guarantees that the synthesizing sequence will be executed regardless of flow control changes caused by the "other instructions".

Since the delay associated with each instruction of a synthesizing sequence is randomly generated, the synthesizing sequence may be generated numerous times, yet never appear as the same sequence of instructions to a DUT. Furthermore, no register is reserved for a special purpose. As a result, the disadvantages of conventional instruction generating techniques are overcome.

These and other important advantages and objectives of the present invention will be further explained in, or will become apparent from, the accompanying description, drawings and claims.

An illustrative and presently preferred embodiment of the invention is illustrated in the drawings in which:

FIG. 1 is a flow chart highlighting the steps performed by a random test generator;

FIG. 2 illustrates a first embodiment of an instruction queue;

FIG. 3 illustrates a second embodiment of an instruction queue;

FIG. 4 illustrates a third embodiment of an instruction queue;

FIG. 5 illustrates a fourth embodiment of an instruction queue;

FIG. 6 illustrates a fifth embodiment of an instruction queue;

FIG. 7 is a flow chart illustrating a method of embedding synthesizing sequences in randomly generated tests; and

FIGS. 8-12 illustrate preferred C++ coding for implementing apparatus which embeds synthesizing sequences in randomly generated tests.

Methods 700 and apparatus for embedding synthesizing sequences in randomly generated microprocessor tests, thereby providing for the synthesis of useful operands, are pictured in FIGS. 1-12. In accordance with these figures, and the following description, apparatus for embedding synthesizing sequences in randomly generated tests may comprise one or more computer readable storage mediums, and a body of computer readable program code 800, 900, 1000, 1100, 1200 stored in the one or more computer readable storage mediums. The computer readable program code 800, 900, 1000, 1100, 1200 may comprise a first portion of code for generating and associating a delay for/with each instruction of a randomly generated test. A second portion of the code 1100 may be directed to pushing each instruction of the randomly generated test, along with its associated delay, onto a queue. A third portion of the code 1204 might allow for determining whether an instruction comprising a head element of the queue (i.e., the first element in the queue) has an associated delay which allows it to be presently popped from the queue. A fourth portion of the code 1202 might provide for popping each instruction of the randomly generated test off of the queue.

Also in accordance with FIGS. 1-12 and the following description, a computer implemented method 700 for embedding synthesizing sequences in randomly generated tests and then executing the randomly generated tests in a device under test, may comprise the following steps. A first step 702 comprises generating and associating a delay for/with each instruction of a randomly generated test. A second step 704 comprises pushing each instruction of the randomly generated test, along with its associated delay, onto a queue. A third step 706 comprises determining whether an instruction comprising a head element of the queue has an associated delay which allows it to be presently popped from the queue. A fourth step 708 comprises popping each instruction of the randomly generated test off of the queue. A fifth step 710 comprises executing each instruction popped off of the queue in a device under test. The device under test may be either a pre-silicon model or silicon prototype of a processor. Although the above steps are sequentially numbered, the numbering is not indicative of any kind of execution order.

Having generally described methods 700 and apparatus for embedding synthesizing sequences in randomly generated tests, thereby enabling the synthesis of useful operands during the simulation or execution of a randomly generated test, the methods 700 and apparatus will now be described in further detail.

The flow chart 100 of FIG. 1 illustrates steps that might be performed by a random test generator implementing the program code 800, 900, 1000, 1100, 1200 illustrated in FIGS. 8-12. First, the random test generator computes 102 an initial value of the program counter PC. The random test generator then checks 104 the contents of M›PC! (a memory address determined by the value of PC) to determine whether an instruction is currently stored at that address. If an instruction is found at M›PC!, the instruction is simulated 112, and the program counter's value is recomputed 102 (e.g., incremented or decremented).

If at some point M›PC! is found to be empty, the random test generator determines 106 whether an instruction can be "popped" from an instruction "queue". If an instruction can be popped, it is popped and written 114 to memory address M›PC!, and then simulated 112 within a simulator. If an instruction cannot be popped, and additional instructions remain to be generated 108, one or more additional instructions are generated and pushed 110 onto the queue. The queue is then checked 106 again to determine whether an instruction in the queue can be popped. If not, more instructions are generated and pushed 110 onto the queue. At some point, an instruction is popped 114 from the queue, written 114 to memory, and simulated 112.

If an instruction cannot be popped from the queue, and no additional instructions remain to be generated 108, the queue is checked 116 to determine whether it is devoid of instructions. As defined in this description, a queue is "empty" if an instruction cannot currently be popped from the queue. A queue is "devoid" of instructions if no instructions remain in the queue. As will be further explained later in this description, each instruction in the queue is associated with a delay. In this manner, it is possible that a queue might appear to be "empty" (because no instruction is associated with a delay which is less than or equal to zero), but not be "devoid" of instructions. If the queue is not devoid of instructions, instructions remaining in the queue are sequentially popped 118 from the queue, written 118 to memory, and simulated 118. At this point, the queue will be devoid of instructions, and the generation/simulation will come to an end 120.

As earlier summarized, an instruction queue (as defined herein) comprises a list of pending instructions (data) and all of the functions used to manipulate the list. The queue described herein is prioritized, meaning that instructions are inserted and removed ("pushed" and "popped") from the queue in a predetermined order. By way of example, the C++ computer code of FIGS. 8-12 implements a LIFO (last in first out) queue (denoted in the code as a "flexqueue" 802, 902). However, the queue could also have been implemented as a FIFO (first in first out) queue or other prioritized queue.

A very unique aspect of the flexqueue 802, implemented in FIGS. 8-12 is that each instruction of the queue 802, (or element of the queue) is associated with a delay 804. By default, an instruction is associated with a delay of zero 806 and then pushed onto the queue 802. If two or more instructions are pushed onto the queue 802 with associated delays which differ, they will be prioritized within the queue 802 so that the instruction associated with least delay will be popped from the queue 802 prior to the instruction or instructions associated with greater delays. If two or more randomly generated instructions are simultaneously pushed onto the queue 802 with identical delays, they will be prioritized based on their age (i.e., in a LIFO queue, the instruction which was generated last will be given a priority within the queue 802 which causes it to be popped from the queue 802 before the instruction which was generated first).

The flexqueue 802 of FIGS. 8-12 is implemented as a number of elements 202-208 comprising a list of pending instructions 200, wherein each element 202-208 of the list 200 (but for the NULL element) comprises a pointer 210-214 to a "next" element in the list. See, for example, elements A 202, B 204 and C 206 of FIG. 2. In this manner, an element which is next in line to be popped from the queue 802 may be designated as the "head element" 202. The head element 202 points to an element 204 which is next in the pending instruction list 200, and so on. A NULL element 208 designates the end of the pending instruction list 200, and when encountered, signals that there are no more instructions to be popped from the queue 802.

In FIG. 2, element A 202 is the head element, and is associated with a delay of zero. Element A 202 is followed by elements B 204 and C 206 (with respective delays of three and seven). Bringing up the end of the list is the NULL element 208. Note that each element 202-206, but for the NULL element 208, is associated with a "next" or "child" pointer 210-214.

As additional instructions are pushed onto the queue 802 and added to the list 200, child pointers 210-214 are adjusted accordingly.

The operation of the above apparatus and methods 700 may be better understood with respect to the following example.

A C++ implementation of blocks 106, 114, 112 and 110 of the FIG. 1 flow diagram 100 might appear as follows:

Consider the following sequence of PA-RISC instructions, which it might be necessary to consume in sequence order so as to induce the occurrence of a given condition (e.g., load or synthesize a useful operand):

Although these instructions are specific to the PA-RISC microprocessor architecture, other microprocessor architectures require the loading of similar instruction sequences.

At some point during a simulation, the queue 802 from which instructions are being consumed will become empty 1204 (either because the queue 802 is devoid of instructions, or because the queue 802 comprises a head element 202, 904 with other than a zero delay), and the above sequence of instructions will be pushed 1102 onto the queue 802. Given a library function rand(x), which returns a random value between 1 and x, the code which effects this push might appear as:

Note that the order of the synthesizing sequence is preserved as the synthesizing sequence is pushed onto the queue. However, if the above code segment were to be executed twice, the first execution might associate delays of zero, four, and six with the pushed instructions, and the second execution might associate the pushed instructions with delays of zero, three, and seven. Also note that the length of the synthesizing sequence (as determined by the delays associated with its instructions) may vary from three to eleven. This presents quite a large number of possible delay combinations. When "other instructions" (i.e., those not forming a part of the recently pushed synthesizing sequence) are pushed onto the queue in between the instructions of a particular synthesizing sequence, a nearly infinite number of synthesizing sequence permutations become possible.

Assuming that the first of the above instructions (instruction A) is pushed onto the queue with an associated delay of zero, the second instruction (instruction B) is pushed on with an associated delay of three, and the third instruction (instruction C) is pushed on with an associated delay of seven, a list 200 of pending elements 202-208 might appear as shown in FIG. 2.

Since the first instruction (element A) was pushed onto an empty queue, and is associated with zero delay, it is assigned as the head element 202, and may be immediately popped from the queue 802 and consumed (i.e, stored to memory and then simulated). After its consumption, the head pointer 216 is assigned to the next element 204 of the queue 802, and the list of pending instructions 200 is "walked" (i.e., each element 202-208 is examined in turn). In walking the list 200, the delay associated with each element 202-208 is decremented by one. In this manner, the pending list 300 of FIG. 3 is achieved.

When the above calling routine again checks to see if the queue 802 is empty 1204, it will return a flag indicating that the queue 802 is empty. Although the queue 802 is not devoid of instructions, it appears empty because the head element 302 is associated with a delay which is greater than zero. Additional instructions must therefore be generated and pushed onto the queue 802.

If a next generated instruction is associated with a delay of three, the list of pending instructions 300 will again be walked, and an element (element D 404 in FIG. 4) embodying the new instruction will be inserted into the list in accordance with its associated delay. See FIG. 4. The list 400 may then be checked once again to determine if it is empty, and again, a flag will be returned which indicates that the list 400 is empty.

Now assume that an instruction with an associated delay of zero is generated. This element (element E 502 in FIG. 5) will be inserted at the beginning of the list, and the head pointer 504 will be reassigned to point to the list's new head element 502. See FIG. 5. At this point, element E 502 may be immediately popped from the list. However, assume that another instruction with zero delay (embodied in element F 602) is pushed onto the list at the same time element E 502 is pushed onto the list. See FIG. 6. Since the queue 802 is preferably implemented with LIFO priority, the last instruction to be generated is given priority in the queue 802 based on its age of creation. Assuming that element E 502 is generated first, element F 602 will be pushed onto the queue before element E 502. After element F 602 is popped from the queue, each remaining element 502, 302, 402, 304 will have its associated delay decreased by one, leaving element E 502 with a delay of negative one (-1), and in position to be popped from the queue 802 next since its delay is now less than or equal to zero.

As earlier mentioned, the default delay 806 associated with an instruction is zero. However, an optional delay 804 allows synthesizing sequences to be pushed onto a queue 802 in what appears to a DUT to be an entirely random order (when in fact, the order of a synthesizing sequence is not random, but only appears to be random due to the spacing of its instructions in the queue). In its preferred embodiment, the queue 802 of FIGS. 8-12 associates an integer delay of between zero and eight with each instruction of a synthesizing sequence, and associates a delay of zero with all other instructions. Again, note that even when the same synthesizing sequence is pushed onto the queue 802 with equal amounts of delay separating its instructions, the two synthesizing sequences will appear different to a DUT due to the randomness of instructions pushed onto to the queue "in between" the instructions of the synthesizing sequence. For example, assume that the synthesizing sequence pushed onto the queue 802 in the above example is pushed onto a queue 802 several times, and each time, a delay of three separates the first two instructions, and a delay of two separates the second two instructions. Since additional randomly generated instructions will be pushed onto the queue 802 in between the instructions of the synthesizing sequence, the content of the additional randomly generated instructions insures that repetition of a code segment is highly unlikely.

A simple queue might only comprise a single list (i.e., a list of pending elements 200) wherein elements added to the list must first be created, and elements deleted from the list must be destroyed. However, to save the time of element creation and deletion, an additional list 906 may be maintained within the queue 802. This additional list 906 has been implemented in the code of FIGS. 8-12, and is termed a "freelist". The freelist 906 comprises a number of elements which are invisible to routines which query the pending list (also referred to in the code as a "linked list" 1004). When an element needs to be added to the pending list 1004, an element is merely re-allocated from the freelist 906 to the pending list 1004, and when an element of the pending list 1004 needs to be deleted, it is merely re-allocated to the freelist 906. In this manner, the more time-consuming steps of creating and deleting elements are saved.

Use of a freelist 906 complicates the coding of the queue 802 to a certain degree. However, a random test generator will typically maintain a queue 802 which oscillates around a certain length (probably one pending element), and instructions are therefore pushed onto the queue 802 and immediately popped off. As a result, a freelist 906 imparts a significant performance advantage throughout the majority of a test.

When using both a freelist and pending list, a queue 802 may be reset 1002 by appending its pending list 802 onto its freelist 906.

An additional feature which may be embodied in the above apparatus is a means to flush all instructions out of the queue 802 at the close of a test. For example, consider the existence of a list 300 such as that shown in FIG. 3, and assume that no more instructions remain to be generated. In order to complete a test, the instructions remaining in the queue 802 must be consumed, irregardless of the fact that the queue 802 appears empty. The queue 802 may be emptied by querying it for its size 1206. If its size is other than zero, the delay associated with each element 302, 304 is ignored so that remaining instructions are sequentially popped from the queue 802, stored to memory, and then simulated.

While illustrative and presently preferred embodiments of the invention have been described in detail herein, it is to be understood that the inventive concepts may be otherwise variously embodied and employed and that the appended claims are intended to be construed to include such variations except insofar as limited by the prior art.