A project log for Libre Gates

A Libre VHDL framework for the static and dynamic analysis of mapped, gate-level circuits for FPGA and ASIC. Design For Test or nothing !

Yann Guidon / YGDESYann Guidon / YGDES 09/03/2020 at 16:170 Comments

As I try to integrate the Backwards component, I see no place where I could easily change a few lines of code to make it work (although the principle itself is quite simple, right ?). Instead I am facing a big plate of spaghetti, not with the code itself (which is rather good, thanks) but with the data structures that are interwoven and the naming that might not be reflecting the function (which has certainly evolved since their creation). Oh and I didn't log much about the internals, so that genius pile of code is hard to re-architect easily.

Of course there are good and great things that I want to keep. However I see that my initial technique for netlist extraction is quite under-efficient in the case of large designs : it works for small systems but I'm evaluating how it will scale to much larger circuits and I face a O(n²) vs O(n×log(n)) problem. If I ever have one million gates, the setup phase will be ... loooong.

So I have to redesign some parts. This affects only 2 files : VectGen.vhdl and Gates_lib.vhdl, but the data structure depend a lot on the algorithms and I'm going to significantly change the latter. I must re-engineer the former... And this time I must document them ! In essence, I must rewrite just after the first routine :

-- the main sequence of VectGen.vhdl:
GetVectorsSize; -- probing the inputs and outputs
GetNetList;     -- actively probing the gates
FixSinklist;    -- post-processing, no gate activity

GetVectorsSize is alright so far (though it might be re-designed one day, but it's another story). GetNetList however is a big offender and needs a replacement, and the change in algorithm could lead to a change in data structures, that will affect the next procedures : FixSinklist and FixDepthList. This is where I can check for "zombies" and/or take Backwards into account. Changing GetNetList will probably lead to the redesign of FixSinklist and others as well...

The basic idea is that of drivers and sinks, as anywhere. A net is all the connections between the driver and all the sinks, so the "net" is practically described by the driver (we don't play with tristates here). So a "netlist" is just a list of drivers, with sublists of respective sinks.

But a complete digital circuit must have input ports and output ports, not just logic gates, so the main database is (as already described in 1. First upload):

The port sizes are determined by GetVectorsSize after a number of clock cycles.

-- allocate some memory for the descriptors
output_records := new input_records_array(0 to VectOutMax);
 input_records := new output_record_array(0 to VectInMax);

And this is only now that I realise I shouldn't have called it "input_records_array" but "sink_records_array" because it adds to the confusion...

So what are those sinks and drivers, what do they contain and how are they implemented ? In fact there are two versions of the story : the ugly and the tidy:

The memory footprint must also be carefully considered. To save space, a new compact representation is introduced :

It's a hack but at least I managed to encode everything in a single integer. Clarity dictates that these addresses should be subtypes of integer, to prevent any confusion and bug. Indeed : you can not directly compare a sink number and a driver number anymore ! The code below is added to Gates_lib.vhdl, it's just added syntax but at least it's not a record and the coding intention is more explicit (there are already so many integers here and there).

type gate_port_number_type is range 0 to 3;
type sink_number_type is range integer'range;
type driver_number_type is range integer'range;

At minimum, sinks only need to point to the driver. The linked list could be temporarily stored in an external array of integ... of numbers.

The drivers must also store the fanout : the number of sinks. There is nothing else that strictly belongs to the driver definition, so a driver is simply a record with 2 fields. The 2nd field is either a pointer to a first sink, or to an array.

The previous version of the code would "recompile" each linked list and allocate a new array, each with it housekeeping data. Considering that the meta-information of the array easily outsizes the contents if the fanout is small (1, 2 or 3 sinks is the majority of the cases), this might not have been the wisest and most efficient (fast and compact) organisation for FixSinklist and others.

All those tiny arrays could be merged into a large vector/array, and the driver contains either:

Both are integer numbers so there is no need to make 2 versions of the record, or a "union" (which VHDL doesn't support).

type driver_record is
    sink_address : integer; -- can be either:
       -- * when fanout > 1 : an index in the unified sinks table
       -- * when fanout < 2 : a sink_number_type
    fanout : integer;
  end record;

This already reduces the complexity and confusion created by the previous input_address_record and input_record_type.

I mentioned a large array of sink_number_type and in first approximation, the size could be gate_instance_counter*4. Let's not forget the output ports, of course. But that number can be refined to a more accurate value because gate_instance_counter is computed with all the calls to the census functions and they can be extended with an argument, which is the inputs count. Then, when GetVectorsSize returns, it is easy to allocate the right amount of memory. Because, you know, when you have to deal with a million gates, this is the kind of detail that starts to matter.

shared variable total_sinks_count : integer := 0;
impure function Gate_Census(sinks: integer) return integer;

Of course this breaks the PA3_gategen.vhdl code, which is now updated as well...

To complete the picture, here is the (partial) definition of a gate :

type Gate_Descriptor is
    -- general info:
    gate_kind  : enum_gate_kind; -- boolean, DFF or backwards ?
    gatename   : line;           -- full path & name of the gate
    -- Lookup & histograms :
    -- for the probe:
    sinks    : sink_number_array(0 to 3);
    driver   : driver_record;
  end record;

The initial netlist is made of:

shared variable GateList : Gate_Desc_Access;  -- The array that contains all the gates
shared variable sinks_lists, -- dynamic array with total_sinks_count entries, essential part of the netlist
       output_sinks : sink_number_array_ptr; -- the dynamic array of descriptors of the output port
shared variable input_drivers : driver_record_array_access; -- array of the descriptors of the input port

You see the first mention of sinks_list, the main array that contains the lists of sinks (with the index and length given by the driver records).

It is complemented by global variables for the size of each array:

GateList       => gate_instance_counter
sinks_lists    => total_sinks_count
output_sinks   => VectOutMax
input_drivers  => VectInMax
indexPtr       => registered_instance_counter

By the way : indexPtr is simply an array of gate numbers that have more than 1 input and where it is worth it to collect the histogram data (it's a subset of the GateList but the eventual confusion is worth clearing).