# Winner scanner

A project log for VHDL library for gate-level verification

Hard macros and tiles of Actel/Microsemi's ProASIC3 so I can design and verify optimised code without the proprietary libraries

Yann Guidon / YGDES 12/03/2019 at 04:1410 Comments

The above picture shows the scanning pattern of the enhanced testbench for INC8. Not that it makes a big difference, since the scan is quite fast (1s on my i7) but for the ALU8, which lasts a few minutes at this moment, the 54% time saved will mean quite a lot...

It works well for the INC8 and the ALU because they rely on carry propagation (of some sort). The algorithm uses a dual loop (outer forward, inner backwards) that "hits" the powers of 2 sooner than a simple linear scan : the index 128 will be reached after 64 iterations, for example. Many "failure modes" appear on powers of two, or the index before (like : 127 and 128) so reaching them faster is good. This results in the "inverse sawtooth" pattern of the above picture.

This is boosted by another trick called "folding" that tests an index and its opposite. This creates the "horizontal mirror" of the picture. The resulting algorithm is a bit subtle but efficient and small:

```-- 1743 cycles vs 3995 in linear mode !
procedure reverse_folding is
variable j : integer := 1;  -- the current power of 2
variable k : integer := 0;  -- the inferior limit for the reverse scan
variable l : integer := 0;  -- the sub-loop counter for reverse scan
begin
loop
l := j;
loop
if (l < 128) then -- 128 appears 2x
test_cycle(    l);
test_cycle(255-l);
end if;
l := l-1;
exit when l < k;
end loop;
k := j+1;
j := j+j;
exit when j > 128;
end loop;
end reverse_folding;```

We'll see soon enough if this cuts the run time of the ALU8 tests !

Well, guess what ?

For the thorough testing of the ALU8,

• 13.248.331 simulation cycles in 383s to check all the faults with linear scanning
• 1.121.723 cycles in 36s with reverse-folding !

so it's roughly a 10x increase in processing efficiency !

20191205 :

down to 34s and only 931.316 cycles with this dumb simple tweak : I swapped the SRI and SND ports !

I don't know how but I'll have to try some bit shufflings. However the search space is out of range : 16! = 20.922.789.888.000...

## Discussions

Yann Guidon / YGDES wrote 12/08/2019 at 02:31 point

Now that I think of it : SAT solver could/might/may be useful as a post-processing step to "pack" the test vectors but I need a much more thorough understanding of this class of algorithms.  So far I consider the use of heuristics to reduce both the packing/run time and the test time. The goal is not to get to the OPTIMALLY BEST solution because the extra benefits are small, but getting the "low hanging fruits" (such as in the case in this log, where I simply swap a few things) is great and not require a PhD. It is meant to be a practical, self-contained, "good enough" tool for everyday use, not an industry-standard that requires a beowulf cluster :-)

I've been planning this and simulating it in my head for a few months now and the "vector packing" (or compression, or compacting, or combining) would be a pretty interesting algorithm to develop, though the exploration space is huge...

Are you sure? yes | no

Thomas wrote 12/03/2019 at 05:30 point

"Test intelligence advocacy" in the maker community - nice :-)

Are you sure? yes | no

Yann Guidon / YGDES wrote 12/05/2019 at 20:41 point

what do you mean ?

Are you sure? yes | no

Thomas wrote 12/05/2019 at 21:10 point

In my professional life I don't see analytical thinking applied to verification methods very often, and I'm glad to see it here.

Are you sure? yes | no

Yann Guidon / YGDES wrote 12/05/2019 at 22:34 point

Yay :-)

I don't have much exposure to "verification" and it's a very niche, hardly ever heard of, domain...

In fact it's often hidden behind ready-made proprietary tools so the strategies and methods are mostly out of sight :-(

I welcome all pointers and references !

Are you sure? yes | no

Thomas wrote 12/06/2019 at 06:21 point

I don't have to tell you about bread-and-butter or fancy test frameworks (e.g. pytest. googletest, JUnit, Spock).

Let's have a look at some interesting stuff...

* formal verification is a large field, tools like Spin are well known:  http://spinroot.com/spin/whatispin.html

* satisfiability methods, e.g. for finding minimal test vectors in hardware V&V. e.g. MINISAT: http://minisat.se/

* Environmental testing, e.g. power supply (I made a demo here: https://hackaday.io/project/19647-low-cost-programmable-power-supply/log/55684-cold-cranking-automotive-ecu-testing-homebrew-style )

* The usual system integration testing, e.g. MIL, HiL, e.g. for system simulation - this one is awesome: https://github.com/nasa/Trick

* behaviour driven testing, e.g. for model testing: https://github.com/AlexandreDecan/sismic

* using virtalization tests can be done with interesting system cuts (e.g.  system integration testing with a virtual CPU here: https://travis-ci.org/TG9541/stm8ef)

There is much more, of course - especially if you not only ask the question "Did I do it right?" (verification) but also "Is it the right thing to do?" (validation).

Are you sure? yes | no

Yann Guidon / YGDES wrote 12/06/2019 at 18:44 point

That's awesome, thanks !
At this point, I focus only on IC EDA DFT "Integrated Circuit / Electronics Design Automation / Design for Test" with the likes of Mentor Graphics, Synopsys, Candence... but they do really expensive stuff that is proprietary...

My system has a "easily manageable" complexity so I can craft custom tools to avoid paying the high fees of these crazy software suites/ecosystems.

Are you sure? yes | no

Thomas wrote 12/07/2019 at 18:23 point

I'm looking forward to reading about your progress - state-of-the-art testing in hobby systems is an interesting challenge.
One more hint: VCD (value change dump) is an old but established standard in VHDL simulation. Maybe it's worthwhile looking for open source tools that use VCD as a keyword.

Are you sure? yes | no

Yann Guidon / YGDES wrote 12/08/2019 at 02:22 point

What I do here is not "state-of-the-art", it's "totally ad-hoc and under-optimal but sufficiently good" :-D

I don't think VCD is relevant because it's too specific. The vectors I'll hopefully export from my system are pretty basic, just pairs of fixed-size bit vectors (no meta-value) that will later be used to drive a SPI-like port... one vector is the injected signal and the other is the expected bistring.

Are you sure? yes | no

Thomas wrote 12/08/2019 at 07:56 point

You're right about VCD if your test problem is on the signal, not the timing level (or if you don't have a time model at this point). Otherwise it's great because there is FOSS for analysis. I find that using formal test methods is a bit of a "secret science", until one just does it, of course. The learning curve is steep.

Are you sure? yes | no