What is an instruction stream generator?

Newsletter · Original Contribution Joined: Dec 08, 2003 Posts: 1107

(Originally from Issue 4.2, Item 8.0)

From: Wilger

I'm a final year student studying computer science at the University
of Bristol, England. For my final year project I have been assigned
the task of "writing an instruction stream generator for a DUV". I've
searched all over the Internet and I can't find a formal description
of an instruction stream generator any where.

Can anybody out there help me please?

Newsletter · Original Contribution Joined: Dec 08, 2003 Posts: 1107

(Originally from Issue 4.3, Item 2.0)

From: Jeff Cartwright

RAVEN (Obsidian), Genesys (IBM), Raptor (Motorola), Verity-CPU
(Veritable) and others are all examples of random test
generators. RTG's generate random streams of assembly instructions
used for verifying processors. Perhaps this is what your instructor
meant.

http://www.obsidiansoft.com/whitepapers.htm has a tutorial on RTG and
a Theory of Operation on how RAVEN works. Perhaps, this could
help. Other pages on the site include User Manual, and a
tutorial. IBM's link is
http://www.haifa.il.ibm.com/projects/verification/genesys.html. It
also has some good stuff. Last time I looked, there wasn't much on
Raptor or Verity-CPU.

Languages like Vera, e and others include the concept of an
irritator. An irritator generates streams of user defined data. For
simple processors, irritators can generate adequate instruction
streams.

A DUT is a common term for a device under test. I have no idea what a
DUV is (device under verification??).

Basically, you want to be able to generate combinations of instruction
mnemonics and addresses. Any of the tools listed above can generate
instruction streams. The better tools generate correct tests, connect
to an instruction set simulator to track state information, model
internal structures such as caches, and provide various levels of
control to the user. This is probably a bit more than you can do in a
class project.

- Jeff Cartwright, Obsidian Software

Newsletter · Original Contribution Joined: Dec 08, 2003 Posts: 1107

(Originally from Issue 4.3, Item 2.1)

From: Alain Raynaud

I'm not sure what a "DUV" is, but if you are looking for an
instruction stream generator for a processor, I can help you.

The goal of such a beast, as the name implies, is to generate streams
of instructions, while achieving two goals:

1) Generate assembly code that makes sense. In other words, that is
close enough to what actual humans coding in assembly could
write. For instance, you don't use memory locations before you
assign them a value, you don't use uninitialized registers, etc...

2) Cover as many different combinations as possible, with the
objective to test the processor and exercise as many corner cases
as possible. For instance, (Intel would kill for that one), did you
try all kinds of division instructions? Did you try all reasonable
sequences of loads and stores to memory? And so on...

There are commercial tools that can help you do this. I can think of
Vera, which has some built-in capability in that regard and will let
you do pretty much anything you want as long as it's template-based,
or Obsidian Software if you want a solution for a specific processor.

If you are trying to write such a tool yourself, you'll have to look
into many topics: randomness, register allocation, templates, etc...

Newsletter · Original Contribution Joined: Dec 08, 2003 Posts: 1107

(Originally from Issue 4.3, Item 2.2)

From: Michael Vinov

The answer to your question depends on the domain you are focusing. I
may offer you an answer in the domain of simulation based processor
functional verification.

Functional verification validates the correctness of a design with
respect to its specification. Simulation based functional processor
verification validates the design behavior by running large number of
stimuli test programs against the design. This approach requires a
mean to produce large quantity of test programs with high
quality. Test programs are mostly generated by Test Program
(Instruction Stream) Generators.

Test Generators are software tools that generate test programs for
simulation in accordance to a given design specification. Test
generators can sometimes determine expected results to be compared
with the behavior of the design.

I am from IBM Research Lab in Haifa, Israel, and belong to the
Verification Technologies department. The department specializes in
all aspects of simulation-based and formal verification. One of the
department areas is development of test generation technologies for
high-end processor designs. Genesys -- a pseudo-random model-based
test generator -- is the tool developed by this department.

For further details and information you may visit Genesys URL page:
http://www.haifa.il.ibm.com/projects/verification/genesys.html

- Michael Vinov, IBM Research Lab

Newsletter · Original Contribution Joined: Dec 08, 2003 Posts: 1107

(Originally from Issue 4.3, Item 2.3)

From: Andrew Piziali

An instruction stream generator is responsible for producing a
sequence of processor instructions which are able to exercise most --
if not all -- of a processor implementation. It is considered a
subset of an instruction set architecture (ISA) generator because an
ISA generator generates all processor input stimuli, including
interrupts.

An instruction generator may be classified according to several
schemas. First, it may be an active or reactive generator. An active
generator pre-generates an instruction stream before a simulation is
started. A reactive generator produces instructions in response to
processor instruction fetch requests. I wrote such a generator in the
late 80s which replaced a processor instruction cache. Operating in
both non-volatile and volatile memory modes, it seriously stressed all
units of the processor.

A second way of classifying an instruction stream generator is by the
generated instruction format, assembly language or machine code. The
former is usually employed by an active generator for pre-generating
an assembly language test. The latter is employed by a reactive
generator because it is returning instructions directly to the
processor during simulation. This is much more powerful and leads to
much higher functional coverage density than pre-generated assembly
language programs. (Functional coverage density refers to the number
of functional coverage points of a coverage model traversed per
simulation cycle.)

I hope this answers your specific question and leads to further
exploration of published papers on the subject. Several commercial
ISA generators are available as well as HVLs well-suited to ISA
generator implementation.

PS. Janick and I both prefer the acronym "DUV" (device under
verification) to "DUT" because in the 21st century we verify
designs, we don't test them.

Newsletter · Original Contribution Joined: Dec 08, 2003 Posts: 1107

(Originally from Issue 4.3, Item 2.4)

From: Sergio Marchese

I cannot help you about formal description of an ISG, yet I have been
working on writing an ISG for an Infineon microprocessor core (TriCore
2), using Specman.

Our ISG is a pretty smart tool, and I believe most of the problems we
have faced are common to any ISG. As I work at Infineon Bristol, we
could meet and have a chat if you wish.

- Sergio Marchese, Infineon

Newsletter · Original Contribution Joined: Dec 08, 2003 Posts: 1107

(Originally from Issue 4.4, Item 5.0)

From: Anonymous

I am kind of surprised nobody mentionned the Vera Sequence Generator
for this task, randseq. This is my favorite Vera construct.

Randseq as its names suggests generates random sequences of
instructions (actually *weighted* random sequences), and removes the
burden off the designer's should of having to specify thousands of
corner cases when properly used and given enough time to run. It is
also more powerful than nested for loops as you can spawn multiple
short lived random simulations instead of one super long nested loop
simulation than never seems to end.

To see how randseq works, examine the following code snippet. Let's
just say we want to create random sequences of instructions that we
just wish to push on a list and will be later injected in a BFM which
will convert it to 0s and 1s signals for the DUV:

randseq (product_seq_type_A) {

product_seq_type_A: &(choice1_w) C1
|&(choice2_w) C2;

C1: {list.push(INSTR1);
list.push(INSTR2);
} WRAP_UP1;

WRAP_UP1: { list.push(INSTR3); };

C2: &(burst_c2_w) DO_C2 C2
|&(close_c2_w) WRAP_UP2;

DO_C2: {list.push(INSTR4); };

WRAP_UP2: { list.push(INSTR5); };
}

Randseq is a bit like a case statement, but instead of relying on a
single fixed value to select which branch to execute, it relies on
weights to chain "case" branches together.

In the example above, variables ending in _w are "weights". When
entering the randseq, there is a (choice1_w/(choice1_w+choice2_w))
percent chance for the program to continue with the code in the "C1
case" of the randseq. If that is what happens, then the final result
of executing the randseq will be the execution of these lines:

list.push(INSTR1);
list.push(INSTR2);
list.push(INSTR3);

So our list will contain three instructions.

On the other hand, if the C2 branch is selected, the list of
instructions will be quite different, and as you can see, could loop
around C2 a few times. A possible outcome is:

list.push(INSTR4); // DO_C2 selected
list.push(INSTR4); // DO_C2 selected
list.push(INSTR4); // DO_C2 selected
list.push(INSTR5); // WRAP_UP2 selected

So as long as DO_C2 is selected, you would get a stream if INSTR4.

You should see by now that the possibilities are quite
interesting. You could loop back to C1 inside of C2, and other various
things. The hardest part is to define what kind of sequences you would
like. I hope this is clear.

- Anonymous, Not from Synopsys

Newsletter · Original Contribution Joined: Dec 08, 2003 Posts: 1107

(Originally from Issue 4.4, Item 5.1)

From: Simon Bates

> PS. Janick and I both prefer the acronym "DUV" (device under
> verification) to "DUT" because in the 21st century we verify
> designs, we don't test them.

hmm - for the sake of my 21st century car's anti-lock braking system I
hope its verified *and* tested.

- Simon Bates, ARM Ltd