Close

DepthLists

A project log for VHDL library for gate-level verification

Collection of ASIC cells and ProASIC3 "tiles" in VHDL so I can design and verify optimised code without the proprietary libraries

Yann Guidon / YGDESYann Guidon / YGDES 12/24/2019 at 22:167 Comments

v2.6 is looking good !

I already have the gatelist which is, as the name implies, the list of gates, and their connections are working well. It is now supplemented by the "depthlist", a 2D array of gate references. It simplifies the design of algorithms that scan forward or backward in the circuit.

Here is the new display for the INC8 unit :

  ************ DEPTHLIST ************
  
 - Input #0 : fanout=4
      1 : Gate #1(0) - inc8):dut@inc8(tiles):e_r0b@inv(trace):lut2
      2 : Gate #2(0) - inc8):dut@inc8(tiles):e_r1b@xor2(trace):lut4
      3 : Gate #3(0) - inc8):dut@inc8(tiles):e_r2b@ax1c(trace):lut8
      4 : Gate #4(0) - inc8):dut@inc8(tiles):e_r3a@and3(trace):lut8
  
 - Input #1 : fanout=3
      1 : Gate #2(1) - inc8):dut@inc8(tiles):e_r1b@xor2(trace):lut4
      2 : Gate #3(1) - inc8):dut@inc8(tiles):e_r2b@ax1c(trace):lut8
      3 : Gate #4(1) - inc8):dut@inc8(tiles):e_r3a@and3(trace):lut8
  
 - Input #2 : fanout=2
      1 : Gate #3(2) - inc8):dut@inc8(tiles):e_r2b@ax1c(trace):lut8
      2 : Gate #4(2) - inc8):dut@inc8(tiles):e_r3a@and3(trace):lut8
  
 - Input #3 : fanout=4
      1 : Gate #5(0) - inc8):dut@inc8(tiles):e_r3b@xor2(trace):lut4
      2 : Gate #6(0) - inc8):dut@inc8(tiles):e_r4a@and2(trace):lut4
      3 : Gate #7(1) - inc8):dut@inc8(tiles):e_r4b@ax1c(trace):lut8
      4 : Gate #8(0) - inc8):dut@inc8(tiles):e_r5a@and3(trace):lut8
  
 - Input #4 : fanout=3
      1 : Gate #6(1) - inc8):dut@inc8(tiles):e_r4a@and2(trace):lut4
      2 : Gate #7(2) - inc8):dut@inc8(tiles):e_r4b@ax1c(trace):lut8
      3 : Gate #8(1) - inc8):dut@inc8(tiles):e_r5a@and3(trace):lut8
  
 - Input #5 : fanout=3
      1 : Gate #9(2) - inc8):dut@inc8(tiles):e_r5b@ax1c(trace):lut8
      2 : Gate #10(1) - inc8):dut@inc8(tiles):e_r6a@and3(trace):lut8
      3 : Gate #8(2) - inc8):dut@inc8(tiles):e_r5a@and3(trace):lut8
  
 - Input #6 : fanout=2
      1 : Gate #11(2) - inc8):dut@inc8(tiles):e_r6b@ax1c(trace):lut8
      2 : Gate #10(2) - inc8):dut@inc8(tiles):e_r6a@and3(trace):lut8
  
 - Input #7 : fanout=2
      1 : Gate #12(2) - inc8):dut@inc8(tiles):e_r7a@and3(trace):lut8
      2 : Gate #13(2) - inc8):dut@inc8(tiles):e_r7b@ax1c(trace):lut8
 
 Depth 1 : 6 gates.
 - Gate #1 : fanout=1  Depth min=1  max=1  LUT="10" - inc8):dut@inc8(tiles):e_r0b@inv(trace):lut2
      1 : Output #0
 - Gate #2 : fanout=1  Depth min=1  max=1  LUT="0110" - inc8):dut@inc8(tiles):e_r1b@xor2(trace):lut4
      1 : Output #1
 - Gate #3 : fanout=1  Depth min=1  max=1  LUT="01010110" - inc8):dut@inc8(tiles):e_r2b@ax1c(trace):lut8
      1 : Output #2
 - Gate #4 : fanout=6  Depth min=1  max=1  LUT="00000001" - inc8):dut@inc8(tiles):e_r3a@and3(trace):lut8
      1 : Gate #5(1) - inc8):dut@inc8(tiles):e_r3b@xor2(trace):lut4
      2 : Gate #7(0) - inc8):dut@inc8(tiles):e_r4b@ax1c(trace):lut8
      3 : Gate #9(0) - inc8):dut@inc8(tiles):e_r5b@ax1c(trace):lut8
      4 : Gate #11(0) - inc8):dut@inc8(tiles):e_r6b@ax1c(trace):lut8
      5 : Gate #12(0) - inc8):dut@inc8(tiles):e_r7a@and3(trace):lut8
      6 : Gate #13(0) - inc8):dut@inc8(tiles):e_r7b@ax1c(trace):lut8
 - Gate #6 : fanout=2  Depth min=1  max=1  LUT="0001" - inc8):dut@inc8(tiles):e_r4a@and2(trace):lut4
      1 : Gate #10(0) - inc8):dut@inc8(tiles):e_r6a@and3(trace):lut8
      2 : Gate #9(1) - inc8):dut@inc8(tiles):e_r5b@ax1c(trace):lut8
 - Gate #8 : fanout=1  Depth min=1  max=1  LUT="00000001" - inc8):dut@inc8(tiles):e_r5a@and3(trace):lut8
      1 : Gate #11(1) - inc8):dut@inc8(tiles):e_r6b@ax1c(trace):lut8
 
 Depth 2 : 5 gates.
 - Gate #5 : fanout=1  Depth min=1  max=2  LUT="0110" - inc8):dut@inc8(tiles):e_r3b@xor2(trace):lut4
      1 : Output #3
 - Gate #7 : fanout=1  Depth min=1  max=2  LUT="01010110" - inc8):dut@inc8(tiles):e_r4b@ax1c(trace):lut8
      1 : Output #4
 - Gate #10 : fanout=2  Depth min=1  max=2  LUT="00000001" - inc8):dut@inc8(tiles):e_r6a@and3(trace):lut8
      1 : Gate #12(1) - inc8):dut@inc8(tiles):e_r7a@and3(trace):lut8
      2 : Gate #13(1) - inc8):dut@inc8(tiles):e_r7b@ax1c(trace):lut8
 - Gate #9 : fanout=1  Depth min=1  max=2  LUT="01010110" - inc8):dut@inc8(tiles):e_r5b@ax1c(trace):lut8
      1 : Output #5
 - Gate #11 : fanout=1  Depth min=1  max=2  LUT="01010110" - inc8):dut@inc8(tiles):e_r6b@ax1c(trace):lut8
      1 : Output #6
 
 Depth 3 : 2 gates.
 - Gate #12 : fanout=1  Depth min=1  max=3  LUT="00000001" - inc8):dut@inc8(tiles):e_r7a@and3(trace):lut8
      1 : Output #8
 - Gate #13 : fanout=1  Depth min=1  max=3  LUT="01010110" - inc8):dut@inc8(tiles):e_r7b@ax1c(trace):lut8
      1 : Output #7
  ************ END OF DEPTHLIST ************
  
  Fanout:  Count:  .........|.........|.........|.........|.........|
      1 :     10 - **********                                        
      2 :      5 - *****                                             
      3 :      3 - ***                                               
      4 :      2 - **                                                
      5 :      0 -                                                   
      6 :      1 - *                                                 
  
   Depth:  Gates:  .........|.........|.........|.........|.........|
      0 :      8 - ********                                          
      1 :      6 - ******                                            
      2 :      5 - *****                                             
      3 :      2 - **                                              

I added some histograms at the end to provide a slightly more "graphical" overview of the circuit. At this point, depth=0 means the input vector.

Going further is going to be harder, because so far it's been easy and the algorithms are not too hard. I solved the problems of depth rather quickly but the generation of the test vectors creates new kinds of challenges, that I can't tackle upfront.

When I face difficulties, my mind wanders and gets distracted by crazy stuff. For example I was wondering if I could directly import EDIF netlists with my system...

Or create a GUI to explore the circuit as a schematic... 

I should also add better support for the gates that are part of a loop, and therefore have no depth. More tests and case studies would be great !


However time is short. I give myself about 2 weeks to generate the test vectors because the holiday vacations end on jan. 6th. The algorithmic challenge is quite hard because of the many possible cases and I haven't figured out yet if there is a higher-level approach that addresses every case with a unified idea.

Discussions

Thomas wrote 12/24/2019 at 22:21 point

The distractions that mentioned are like the sugar topping on a cake: the cake wouldn't be half as good without it but it's better to eat all the cake than only the topping :-)

  Are you sure? yes | no

Yann Guidon / YGDES wrote 12/24/2019 at 23:16 point

hmmmm I'm not sure I grasp the subtleties of your remark but ... merry Xmas ;-)
I'm glad you follow this adventure and I'd like to wrap it up ASAP ! ;-)

  Are you sure? yes | no

Thomas wrote 12/25/2019 at 06:40 point

Joyeux Noël :-)

Don't ask me about the role of the periaqueductal gray in ludic hacking if you want to avoid more subtleties regarding principled research and serendipity :D

  Are you sure? yes | no

Yann Guidon / YGDES wrote 12/28/2019 at 13:05 point

Thanks Thomas :-)
No worries, I'll be fine ;-)

  Are you sure? yes | no

Yann Guidon / YGDES wrote 12/09/2020 at 19:31 point

One year later, I'm still on it and rewriting the whole thing :-D
And no sign of a vector generation.

  Are you sure? yes | no

Thomas wrote 12/10/2020 at 06:22 point

Too much topping I guess - and more topping elsewhere. The thing you're working on has a lot in common with other areas where humans apparently have an ability that's difficult to grasp (i.e. describe in a way that makes it possible to derive an algorithm). In this case my hunch is that your approach is pretty close to how humans do it (see patterns at a glance), and the general algorithm for describing this "pattern-ness" is elusive. I have an hypothesis what that capability is from an adjacent field of technology.

  Are you sure? yes | no

Yann Guidon / YGDES wrote 12/10/2020 at 11:32 point

@Thomas  that's one of the many aspects...

This project almost reaches the complexity of a compiler (I'm continuing at https://hackaday.io/project/174585-libre-gates/log/186869-depthlist-v2 ) and I haven't touched yet the vector generator.

I'm trying as much as possible to describe what I do and how and why because, as shown in this post, there are decisions that need a lot of context to understand, and sometimes subtle interactions that must be documented, because I might have to return to the code later. The code gets quite sophisticated in appearance yet the "idea" is simple. A little change in one of the assumptions can completely change the implementation, and I need to understand what I had in mind at the moment when I wrote the previous code...

I also try to make more illustrations because they are more powerful, but that takes much more efforts than writing...

  Are you sure? yes | no