Re: [f-cpu] random number generator

[Yann Guidon <whygee@f-cpu.org>]

hello,

ben franchuk wrote:

> Yann Guidon wrote:
>
> > i understand, but the worry is to make
> > a really efficient benchmark that requires relatively
> > few patterns to cover most bugs.
> I am confused here. What kind of bugs do you wish to uncover? 
if i knew, then there would be no point in using a sophisticated
search for improbable combinations.

i see two kinds of "bugs", that is : special cases that don't
give the expected results. There are "simple" problems,
such as wrong or incomplete carry routing, or things like that.
it's either a copy-paste error, or a syntax/semantic error
that is not detected at first read and it results in a signal being
not used correctly. A LFSR is a predictibly efficient
mean to generate the test patterns, it can be used during
design, verification and for production tests.

The others are more subtile, less easy to uncover
and are, indeed, the ones that are not typical, or specific
to unknown data sets .... the point is that we don't know
what it is, so we know what it is not : correllated.
LFSRs have a low entropy and are not adapted.
Here, the target is much more complex coding problems
or misunderstanding of the problem's definition,  a higher
level of debugging. Because of the low entropy of LFSR,
it would take too much time to find a pattern that shows
an error, so a less correllated pattern generator has more
chances to find ery complex errors with less tests.

OTOH, because a LFSR can startup with strings of 0s and 1s,
and progressively make more complex patterns, it is well
suited to find small coding errors, boundary condition effects
or rounding problems with much less computational efforts
than a real random pattern. Hence the recommendation
to use both methods, LFSR to start and X thousands of
"uncorrellated" tests.

> If you did the hardware design correctly it would have no bugs. 
but there can be traps in other places, such as langage and
the widely varying VHDL support from different compilers/synthesisers....

> The corect way to design the hardware is to have redundant
> test logic for hardware bugs or design testing. This
> I don't think is possble yet using a high level design
> langauge becuase the macro blocks are not designed for this
> redundant logic or the compiler removes the redudant logic.
unless you do it on a higher level that the compiler is not
able to "simplify" without changing the circuit's behaviour.

> > For example, MR's mltiplier is a really heavy stuff
> > that could run tens of hours, while a few minutes
> > are only available in common cases, and there are
> > other units to test.
> I keep thinking of the pentium math bug!
the 'P5 FDIV bug" is the kind of problem that
is addressed by the second "uncorrellated" test :
it was an incomplete lookup table, not a functional
or hardware flaw. This flaw is not possible to find
with basic techniques because the problem was the
very definition of the unit, not how it was implemened.


> > low-entropy data can be used first to check
> > dumb errors, ie using a very simple polynomial LFSR.
> > Then the rest (like rounding error behaviour and more
> > sophisticated stuffs including statistical measures) will
> > need a high entropy pseudo-random generator.
> Good for quick testing but the hardware needs to be built first.
it can be "built" if it is coded and Gaetan is doing that, indeed.

Concerning the testing time : the issue comes from running
the "full build and test" script at home whenever a change
is made on other units. At the end of the development of a particular
unit, it is possible for someone to run a very long test,
feeding the design with millions of test patterns.
The computer could run a few days, just to be sure.
Others would not be required to do this,
only to run the test with a few thousands of patterns.
In fact, it's as simple as a compilation parameter
that says how much tests should be done, the less the faster.

YG

*************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe f-cpu       in the body. http://f-cpu.seul.org/