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 !
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...