«

Marcus Harnisch <> writes:

> Kai,
>
> Kai Harrekilde-Petersen <> writes:
>
>> Of course. All lossless computations are deterministic (lossy
>> compression isn't, but I can't think of a lossless computation that
>> doesn't include a true random input, which is nondeterministic).
>
> How does determinism come into play here? Every algorithm is
> deterministic by definition, no?

No. Lossy compression algorithms (e.g. JPEG, MPEG, MP3) are *NOT*
necessarily deterministic in what they throw away. Two compliant
implementations may choose to discard different infortmation.

>> In you case, I'd use the knowledge of the highly regular ALU
>> structure, ie: there are known pathological cases, such as ~0
>> + 1 doing a full carry, etc.
>
> Why is a full carry more important than others?

Because it tests that all the full adders can correctly do a carry at
the same time. Hence, you don't need to test the carry chain
again. The morale is that _Not All Test Vectors Are Created Equal_.

Some test vectors add very little coverage; others add a lot of coverage.

> I don't see a way to
> avoid an exhaustive test. Consider the pathologic case that the ALU is
> implemented as lookup table.

That makes no diffence. The basic functionality is the same; 3 bit
opcode, A input, B input, and Carry_in input.

But if you change to, say, an 8 bit wide implementation (e.g. using
CLA logic), things change.

Look, why don't you look up some text books about testing and test
vector generation? I seems to me that you aren't very familiar with
the basics here.

>> Also, if the ALU is designed as a smaller fundamental structure which
>> is replicated (not uncommon), why not test the fundamental block
>> first, and then add a few test vectors to ensure that the
>> interconnection is done correctly?
>
> Yes -- if you can make that assumption.

Only you can decide that - you're the one implementing it, right?

>> No, but using a LFSR is one hell of an effective way of generating
>> those vectors automatically and efficiently.
>
> You mean as opposed to walking through the numbers by incrementing
> them? What is the benefit of using an LFSR here?

An LFSR costs much less logic that an incrementer. For some HW, that's
important.

Regards,


Kai

Kai,

Kai Harrekilde-Petersen <> writes:
>> Every algorithm is deterministic by definition, no?
>
> No. Lossy compression algorithms (e.g. JPEG, MPEG, MP3) are *NOT*
> necessarily deterministic in what they throw away. Two compliant
> implementations may choose to discard different infortmation.

I think we are not on the same page here. These standards allow some
variation between different implementations. Each implemented
algorithm however is deterministic. It is indeed non-deterministic
which implementation was chosen in a particular case.

But don't let this carry us away from the OP's ALU issue.

>> I don't see a way to avoid an exhaustive test. Consider the
>> pathologic case that the ALU is implemented as lookup table.
>
> That makes no diffence. The basic functionality is the same; 3 bit
> opcode, A input, B input, and Carry_in input.

The functionality is the same. But in a LUT each entry has an equal
probability of being wrong. There is no way to find a single test
vector that will verify more than a single LUT entry. Thus you need
the full set of vectors.

> Only you can decide that - you're the one implementing it, right?

Wrong! I am the one *verifying* it. Once I put my verification hat on,
I could care less about the implementation. It all depends at which
granularity you want to consider something a black-box.

You are making assumptions about the internal structure of the
ALU. That maybe completely valid in a given scenario. But if someone
approaches me asking me to verify an ALU, I don't necessarily know
these internals.

> An LFSR costs much less logic that an incrementer. For some HW, that's
> important.

Verification is typically done in software though. I bet an addition
costs less processor cycles than all the logical operations in an
LFSR. But that's not even my point. My point is that it is (currently)
more effort to use an LSFR from within VHDL than using an incrementer.
I don't see any technical advantage in using random vectors to verify
a stateless circuit.

The effort of using random vectors approaches zero if you have the
chance to use one of the popular HVLs with built-in PRNGs (in which
case you might also consider switching to some sort of assertion
language which often comes with an HVL).

Best regards,
Marcus

--
Marcus Harnisch | Mint Technology, a division of LSI Logic
| 200 West Street, Waltham, MA 02431
Tel: +1-781-768-0772 | http://www.lsilogic.com

Marcus Harnisch <> wrote in message news:<>...

> Kai Harrekilde-Petersen <> writes:

> > An LFSR costs much less logic that an incrementer. For some HW, that's
> > important.
>
> Verification is typically done in software though. I bet an addition
> costs less processor cycles than all the logical operations in an
> LFSR. But that's not even my point. My point is that it is (currently)
> more effort to use an LSFR from within VHDL than using an incrementer.
> I don't see any technical advantage in using random vectors to verify
> a stateless circuit.
>
> The effort of using random vectors approaches zero if you have the
> chance to use one of the popular HVLs with built-in PRNGs (in which
> case you might also consider switching to some sort of assertion
> language which often comes with an HVL).
>
> Best regards,
> Marcus

One possible advantage of an LFSR over incrementing a counter is that
if there is a bug affecting a m out of n states, but those states are
clumped together, an LFSR is likely to hit one of those in the first
n/m states that it tries, but a counter is likely to go through n/2 of
the states before it hits any bad ones. A PRNG shares this advantage.
This only matters if it takes a long time to try all states.

One possible advantage of an LFSR over a PRNG is that an LFSR won't
repeat any states. If you want to cover all n states, an LFSR will do
it in n tries, but a PRNG has to try nlog(n) times before it probably
hit every state, and even then it's only "probably". A counter shares
this advantage.

Hi Bob,

(Bob Jenkins) writes:

> One possible advantage of an LFSR over incrementing a counter is that
> if there is a bug affecting a m out of n states, but those states are
> clumped together, an LFSR is likely to hit one of those in the first
> n/m states that it tries, but a counter is likely to go through n/2 of
> the states before it hits any bad ones. A PRNG shares this advantage.
> This only matters if it takes a long time to try all states.

But until after you actually tried all vectors, there is no way to
tell you are done. How about these error cases happened to be clumped
together so that they'd be caught by the incrementer -- or by a
different LFSR polynomial? Equal chances, I'd say.

The sequence generated by an LFSR shares some important
characteristics with a counter:

1. The sequence is deterministic

2. It has a period of 2^n cycles

3. Each generated value is unique

You could probably say that the sequence generated by a counter is a
special case of an LFSR sequence.

> One possible advantage of an LFSR over a PRNG is that an LFSR won't
> repeat any states. If you want to cover all n states, an LFSR will do
> it in n tries, but a PRNG has to try nlog(n) times before it probably
> hit every state, and even then it's only "probably". A counter shares
> this advantage.

Good point! That is my standard argument if certain vendors (the usual
suspects) try telling me that there is nothing but random simulation
(plus coverage).

AFAIK, Testbuilder (and likely SystemC) provide a PRNG that guarantees
that each generated number is unique. Other HVLs could be prevented
from running forever, e.g. by using functional coverage data as
feedback for the stimulus. In Specman/e you could also generate a list
containing all numbers from 0 to 2^20-1 (after you changed the
max. list size). Then you would use the PRNG to generate a second list
with the constraint that both lists must have the same set of values
(there is always more than one way to do things). Which brings us back
to the argument whether this complexity is really necessary for our
ALU case.

2^20 input vectors generated by either a counter or an LFSR would have
long finished while we are still babbling

Best regards,
Marcus

--
Marcus Harnisch | Mint Technology, a division of LSI Logic
| 200 West Street, Waltham, MA 02431
Tel: +1-781-768-0772 | http://www.lsilogic.com

Marcus Harnisch <> writes:

> The sequence generated by an LFSR shares some important
> characteristics with a counter:
>
> 1. The sequence is deterministic
>
> 2. It has a period of 2^n cycles

Erh, only if you go out of your way to make it that. "Standard"
maximum-length LFSR have a period of 2^n - 1 cycles (the zero vector
is normally not included).

> Good point! That is my standard argument if certain vendors (the usual
> suspects) try telling me that there is nothing but random simulation
> (plus coverage).

At work, we use a combination of directed non-random tests that
targets known corner-cases, and the use of randomizing seeds to data
generators etc for almost everything. The motto goes: when in doubt,
make it random.


--Kai

Kai Harrekilde-Petersen <> writes:
> Erh, only if you go out of your way to make it that. "Standard"
> maximum-length LFSR have a period of 2^n - 1 cycles (the zero vector
> is normally not included).

That is true. So we'd need to make sure that special case is covered
separately.

> The motto goes: when in doubt, make it random.

Correct. Start out with a random framework and maintain different sets
of constraints (down to directed application of certain vectors)
depending on the application.

Best regards,
Marcus

--
Marcus Harnisch | Mint Technology, a division of LSI Logic
| 200 West Street, Waltham, MA 02431
Tel: +1-781-768-0772 | http://www.lsilogic.com

Kai Harrekilde-Petersen <> wrote in message news:<>...

> At work, we use a combination of directed non-random tests that
> targets known corner-cases, and the use of randomizing seeds to data
> generators etc for almost everything. The motto goes: when in doubt,
> make it random.

Often there are a dozen or more independent variables. Bug
descriptions usually don't mention ten variables, usually two or three
will do. Testing all settings of all pairs or triples of variables
will catch most bugs.

A single test that sets n variables randomly will test (n choose 2)
pairs of variables and (n choose 3) triples of variables. The number
of tests you need to cover all settings of all pairs or all triples of
variables grows with the log of the number of variables. There are
tools for trying to minimize the number of tests for this (allpairs,
aetg, jenny). But random settings will also do the job in about the
log of the number of variables. So would an LFSR.

A counter, on the other hand, will cover all exponentially many
settings of earlier variables before it changes later variables. So
any bug in the last variable gets hit after exp(n-1) tests instead of
within log(n) tests. If n is big, the random approach scales nicely,
but the counter never finishes.

I suspect that that explains the strength of random tests.

The case at hand had 3 variables and a feasible number of states; the
counter approach is fine for that.