Project Logs

Collapse

• ALI definition

  Yann Guidon / YGDES • 05/29/2023 at 13:54 • 0 comments

  So the idea is simple, I need an intermediate file format to define the logic gates of a library.

  Doing a direct translation from Liberty or other formats to VHDL would be too complex so I do in two steps, the first being the refactoring of the existing tool.

  The constraint is to KISS : keep it simple and even stupid, and a lot of complexity comes from parsers. The XML parser in bash is an example of overly crazy code that breaks and must be maintained in synch with the tool that generates the XML. But GHDL doesn't evolve fast and there is only one tool to read from. For Liberty, it's a totally different beast... Too many origins, too many tools, too many options and variations... I have collected a few .lib files from different origins and I welcome new ones to test my system.

  But first I must define what the .lib parser must output, which should be as easy as possible to process on my side. The format is a text using a widely used function syntax, instead of a JSON or XML format, because I can directly process it in VHDL, C, JS, you name it. It gets parsed by the interpreter or the compiler, so that's as much I don't have to do.

  First, define the library name:

  define_library_name("somenamewithoutspace");

  It must be called first and only once.

  Then more calls are needed to define each cell/gate, which is either a combinatorial gate (could be a buffer too), a synchronous FlipFlop or an asynchronous Set/Reset latch.
  

  define_combinatorial_cell("AND", "A and B", "Y", "A", "B");
  define_sequential_cell("DFF", "Q", "D", "CLK", "CLR");
  define_asynchronous_cell("RSLATCH", "Q", "S", "R");

  The calling convention is still preliminary and will evolve. But the syntax follows the classic conventions and the calls end with a ";" (strip it if you want to use Python)
  

  So far the limits are the multi-output cells (such as HAX1 and FAX1 of OSU) and the translation of AND, XOR and OR from the weird conventions of the Liberty format, as defined p96, section 4-36:
  

  function : "Boolean expression" ;
  
  The precedence of the operators is left to right,
  with inversion performed first, then XOR, then AND, then OR.
  
  Table 4-6 : Valid Boolean Operators in the function Attribute Statement
  
  Operator Description
    ’      Invert previous expression
    !      Invert following expression
    ^      Logical XOR
    *      Logical AND
    &      Logical AND
  space    Logical AND
    +      Logical OR
    |      Logical OR
    1      Signal tied to logic 1
    0      Signal tied to logic 0
  

  So the Liberty parser's role is to deal with this mish-mash and output VHDL-correct boolean expressions. We'll see that later.
  

  For now the idea for the flow is

  1. get the .ali file with all the calls
  2. script to add "decoration" to the list and create a function out of the file, following the language's conventions.
  3. The target language will also have definitions of the functions.
  4. The target language then call the custon function, that calls the subfunctions with the user's data/parameters.

  For the VHDL version, the gate functions will be called twice : for the declaration then the definition. The gate functions must know which phase they are called from so they output the right text. And since they could be called in any order (you never know, bugs happen) they must also check it too.

  The first thing to do now is to convert the A3P (and maybe OSU and others) libs to the ALI format, by hand, and see how to refarctor the tools to accept these.
  

• ALIberty

  Yann Guidon / YGDES • 05/28/2023 at 23:01 • 0 comments

  More discussions and looking around later, it appears that Liberty files, created back in the 80s by Synospsys, contain a field that might be an afterthought but is critical for my purpose, and Liberty files are the standard way to exchange ASIC cell characteristics. Here is how one cell is described :

  /* --------------- *
   * Design : AND2X1 *
   * --------------- */
  cell (AND2X1) {
  area : 72;
    cell_leakage_power : 0.12537;
    pin(A)  {
      direction : input;
      capacitance : 0.0181648;
      rise_capacitance : 0.0181286;
      fall_capacitance : 0.0181648;
    }
    pin(B)  {
      direction : input;
      capacitance : 0.0178174;
      rise_capacitance : 0.0178174;
      fall_capacitance : 0.0176984;
    }
    pin(Y)  {
      direction : output;
      capacitance : 0;
      rise_capacitance : 0;
      fall_capacitance : 0;
      max_capacitance : 0.497268;
      function : "(A B)";
      timing() {
        related_pin : "A";
        timing_sense : positive_unate;
        cell_rise(delay_template_5x5) {
          index_1 ("0.01, 0.025, 0.05, 0.15, 0.3");
          index_2 ("0.06, 0.18, 0.42, 0.6, 1.2");
  .......

  This is from osu025_stdcells.lib (TSCM 0.25µ library). This open directory also provides the VHDL VITAL model, where the logic gates are described in great detail for the timing in particular. But that's not what I'm here for : I work at the earlier stages in the boolean domain. VITAL simulations will be useful later for detailed simulation, after all the fault injections have been dealt with.
  

  Liberty is probably the most popular format for a SDK to provide timing characteristics. Most EDA prefer Verilog and as highlighted above, the gates contain the function, which I could extract. I could reenact my feat as I did with the custom XML parser (written in bash) but I have cold feet as the XML parser is only intended to read from one tool in particular, with a very specific format, while Liberty is used and generated by a wide variety of tools that I hope to interface with. I don't know yet what I am facing.
  

  I only need to regenerate the basic gate function, so I just want inputs pins, output pin, and a boolean function between them. All the rest is then processed by LibreGates. Meanwhile I realise that my system (like so many others) only handles gates with one output.
  

  There are some useful resources online, such as the Synopsys document for the format and a Python parser. Extracting the gate names, functions, pin names will not be too hard. However I need to make it work with the existing code so I consider using an intermediate file format that will make the VHDL generation easier and more modular. It will hopefully split the complexity between the Liberty filter and the VHDL metaprogramming mess.

  One of the little issues I'll have to deal with is the description of the boolean equations of the Liberty format : AND has no operator sign...

  The other issue will be with the sequential gates, as they are way more diverse than the boolean gates.

  I think I have an idea for the intermediary format, using function calls to be directly executed and cut down the parsing requirements.
  

• Update 20230528

  Yann Guidon / YGDES • 05/28/2023 at 00:35 • 0 comments

  The new version is here !

  I mostly solved some bash script hiccups. I haven't even started implementing the ALI or the VHDL netlist analyser. I just wanted it to work with the newer versions of Bash and GHDL (I have only v1.0 on Fedora, while v3 is already out, I know...)
  

  This is some warmup and I also test my new platform : 6 cores and SSDs, so the 5 tests complete in only about 18s now, down from 42s.

  ...

  Oh wait now it doesn't work with the older version 0.35 :-/

  So I put a bit more effort in the XML parser (written in bash) so it understands references. LibreGates_20220528-1.tbz has the updated files.

  ....

  Oh and I missed a year, we're already in 2023 it seems.
  

• Meanwhile, GHDL...

  Yann Guidon / YGDES • 05/26/2023 at 19:04 • 1 comment

  ... evolves !

  
  I did a lot of work and dev using the 2015 tarball version (0.35-dev packaged by RedHat in 2017) and today Fedora 38 has v1.0-dev, while v3.0 has been released a few weeks ago. I'd like to get it on my computer but there is no .RPM yet.
  

  This breaks some scripts and I'll have to hack and reverse-engineer more to get the scripts functional again. This would enable me to resume work on some borked/incomplete parts of the tools...

  I haven't touched the codebase in 2 years now and it's getting a bit dusty :-/
  

• More async

  Yann Guidon / YGDES • 05/26/2023 at 11:06 • 10 comments

  @SHAOS  made me discover the "C-element" in his log Trying other ways to make chips. I don't know why I hadn't heard about it yet. It's something to keep in mind for when I have resurrected the project and after I added the ALI. The tools have a setback for a few reasons, one of them being the need to support asynchronous logic and clock domain crossings... This way I'll be able to fully characterise the debug interface of the #YGREC8.
  

• Custom mode with arbitrary ALI

  Yann Guidon / YGDES • 04/07/2023 at 13:00 • 0 comments

  LibreGates is an abstraction and generalisation of a "PDK" or gates library originated in #VHDL library for gate-level verification. As such it is useful as a "design space exploration" tool for top-down optimisation. It started as a simple alternative barebones library for distribution of Libre designs targeted at the now obsolete Actel ProASIC3 FPGA, helping to keep the optimised designs alive despite vendor lock-ins.
  

  So the original library grew to a general, multipurpose one with bells & whistles, trying to provide all the possible functions one might desire or need. It can be used as a generic collection of gates for prototyping, without thinking too much about logic optimisation or platform limitations at first. Only once the design space is explored and constrained, one commits to the chosen technology, its PDK and its specific list of gates and functions, then maps the gates. But this might not be convenient. For Libre projects, it is desirable to be able to provide a dumb gates library along with the design source files, for when the PDK is not available. So far only the full generic LibreGates definition file is provided.
  

  Or, one might start from a given PDK but the gates names and pin assignments do not match the gates that LibreGates defines. Talking with @alcim.dev, something became apparent :

  Software stacks use API and ABI so why not create an ALI ?

  After all, each PDK and logic device forces its own Application Logic Interface to the user through a selected list of allowed logic functions. So far all these types of applications are siloed, entrenched. They barely talk to each other and any choice will overly specialise an optimised design to the selected technology. And LibreGates tries to bridge them all for design portability so we need a formal definition of the ALI.

  So the TODO list gets a new item : after I finish the code for the backwards gates, I'll add the support for an external definition file (.ALI) that will enable LibreGates to define and regenerate any desired subset of gates. Any PDK or platform can thus be distilled down to a language independent file.
  

  For now I consider customising:

  • Library name
  • gate name
  • mapping to the internal LibreGates name
  • pin assignment / swap (later)
  • fanout/drive ? (for later)

  Note : other extra analog data such as per-input delays are irrelevant so far. Parametric values might be unavailable or ignored for now as it is too high level for these shenanigans.
  

  The format will be crude at first so I don't need to rewrite Flex and Bison in VHDL. So maybe I'll have to write a JSON parser in VHDL someday.
  

  This way, anybody can generate their own VHDL library (or other language later, like Verilog ?) with their own namespace, and distribute the generated library file in the same AGPL licence as the rest. (Why AGPL and not LGPL ? Because the library is not meant to be part of a shipped product since it is a temporary substitute to the final gates lib).
  

  This is a big deal because so far, we speak of "technology" as both the physical parameters and implementation (think : discrete transistors, TTL, NMOS, PMOS, IIL, CMOS, ECL, FPGA, you name it) and the "logic language", the available set of boolean operations permitted by said technology. The huge driving force for designing LibreGates is the ability to port and refine a circuit, from TTL to FPGA and from ECL to NMOS. Or simply map a high-level circuit to any of these. And since now @alcim.dev wants to port his LogiLib, more flexibility is required, without touching the core source files of LibreGates. 
  

  So for example an ALI for discrete CDC-style gates (implemented with discrete saturated transistors) would contain half a dozen gates only, with mainly NOT, NOR2, NOR3, NOR4 and latches. ECL ALI would have these and some more others like XOR. TTL ALI gets NAND2, NOR2, XOR and the likes (though LibreGates is limited to 4 inputs). The OSU FreePDK defines only 33 gates. No need to modify any internal code or gate...

  Read more »

• Better detection of driver conflicts

  Yann Guidon / YGDES • 12/16/2020 at 04:03 • 0 comments

  The new netlist probe algo has a better inherent sensitivity to driver conflicts, which should not occur in normal netlists but VHDL usually favors the std_logic type, which is a resolved version of std_ulogic that has less adoption despite its inherent ability to detect these driver conflicts.

  The netlist probe detects a conflict because a resolved value is "likely" to differ from a valid signal signature. To ensure some margin, the signature is given by a simple polynomial using the driver's number : a multiplier and an offset, both of which are primes.

    -- The polynomial parameters:
    shared variable Poly_factor : integer := 13;
    shared variable Poly_offset : integer :=  5;
    -- Ideally, choose both as prime numbers, and the
    -- offset MUST be less than the factor (one half is good).
    -- The compromise is between execution speed (each
    -- factor of 8 adds another probe cycles) and
    -- error discrimination (fewer chances of coincidence).
  

  I have enabled the test of this features in test4_cornercases:
  

  The gates clf1, cfl2 and cfl3 detect a driver conflict on an output port and a gate input. But it didn't work immediately: this depends on the polynomial factors, and some (which ?) will work and others not. 17-7 didn't work for this test, but 13-5 did, YMWV.
  

  At first glance, the chance of detection will increase with the poly factor, but this also increases the number (and runtime) of the probe.

  • If you are sure there is no conflict, use 1-0 to save time, particularly for huge netlists.
  • 7-3 adds 1 probe cycle
  • 61-23 will add 2 probe cycles
  • 499-257 will add 3 probe cycles (new safe default)
  • You could run the probe several times with various factors but it is more efficient to use larger factors. Help yourself.

  Those values should be configurable with a generic one day.

  The first version of the netlist probe was also able to identify the drivers of a conflict, now it's only possible to show the sink, but at least it's faster.
  

  Each driver conflict is counted as an unconnected input and will abort the probe. It wouldn't make sense otherwise. Floating nodes are handled inside the gates.
  

• Depthlist v2

  Yann Guidon / YGDES • 12/09/2020 at 22:08 • 0 comments

  One year after 27. DepthLists and I'm back on the subject. The old code is being replaced with new, better data structures, thanks to the hindsight gained since the first version. The basic principle doesn't change much but it now includes the outputs of the backwards and the DFF gates at the level 0. I also want to use a more unified memory allocation approach, similar to what I used for the sinklist, with a large chunk of memory containing all the lists in a compact sequential way.

  I can ensure that the lists are well sorted by using "insertion sort" with linked lists for example, then the linked lists are transformed into normal lists. It's easy because we already know the number of gates and input ports. We don't know the maximum depth in advance though and temporary dynamic allocation seems necessary.

  A new subtlety appears with the DFF and backwards gates : although they are counted as drivers along with the inputs, they are also sinks and should be considered as such as well. We want to know how many gates are traversed before reaching the DFF's input and this sink gate appears at the end side of the depthlist.

  ...

  Some coding and thinking brought a new fresh idea and structure to the "depthlist" complex:

  • Level 0 is the list of the input ports and a new list that contains the DFF and backwards gates (it's called pseudo_drivers_list, with pseudo_drivers_count elements)
  • The other levels are stored in a large array that contains DutVectOut_length + gate_instance_counter elements, called depth_lists. The trick is that since it is some some sort of permutation of the original array, we can store the lists starting from index 0, while also fit the rolling list of gates to propagate/check at the top end. The array can be allocated early.
  • The depth is not easy to get and must be allocated dynamically. There are two values to store for each index (starting at 1 because 0 is implicitly a different kind of data) : the count of elements in the current level, and the starting index in the depth_lists array. Once again it's redundant because it's another "prefix sum".
    A nice solution is to "over-allocate" the depth-lists (by how much ?) and store the individual list sizes just before the given list. A final step will simply scan the lists and compute the prefix sum to store it in a normal array, when its size is known.

  The good news is I got rid of the linked lists ! Though this makes deletion/insertion less convenient.
  

  ...
  

  (tbc)
  

• Skipping the preflight check

  Yann Guidon / YGDES • 12/07/2020 at 23:17 • 0 comments

  The last log Plot twist explains the "shadowing flaw" in the new net probing algorithm. A solution was proposed and this log tries to get the details straight.

  Inspired from the CORS nomenclature, the previous solution runs a first round of checks before starting the main loop, so it's called the "preflight check".

  Instead of serialising the driver's identifier, the signal sends a value that encodes the type of the driver, so 'U' would naturally mean "unconnected". This then helps the next phase to send data when partial inputs are available.

  A new code path must be added, by using a special value of 0 for the shared variable multiply_pass.

  Fine so far but...
  

  Why did I go from "OR" to "AND" logic to propagate the update event ? It simplifies the logic because I don't have to check if the output value has already been sent.
  

  This is because now, setting the output also modifies the "decumulator" and it would be out of sync if more than one event triggers it.
  

  In fact the "preflight check" can be skipped if each input and output has a flag to indicate that the corresponding signal has been processed (accumulated or decumulated). I know it would take a bit more room but... It's only 5 bits for the LUT4 and the previously proposed solution would use more. The output port is scanned manually at the end of each cycle so it's not affected, unlike when a preflight check is used.

  There are two new challenges to solve : how/where to solve the flags, and when/how to toggle them.

  • There are 5 flags (max.) to store for each gate (as noted above, the output ports are explicitely scanned so don't need a flag). These flags fit nicely in the bulky histogram array.
  • Each flag is set on the first valid condition, but reset is not as obvious because there is the risk to fall back into the same trap as before (the reset ending up not being propagated due to AND/OR logic corner cases). The solution seems to be a simple shared flag "probe_phase" that alters the algorithm depending on what is required.
    • When "probe_phase = 0" then all the flags are cleared (if already set) and the output is set to 'U'. That's it. At this point it is possible to add a warning that an input is not connected but this is not critical for this algorithm.
    • When "probe_phase = 1" then
      • if output is not already set, set it and set the flag
      • if each input is not already flagged, register it and set the corresponding flag

  That should work...

  .

  .

  .

  AAaaaannnd... It works ! Amazingly with pretty few hicups and few compile errors on the first try. Go get it : LibreGates_20201209.tbz !

  The probe is enabled for 4 out of the 6 tests and even spotted a flaw in the BigLFSR one (which I will leave for the lulz because it doesn't really matter). I should benchmark its performance now. The next step will be to reimplement the depthlist system.

• Plot twist

  Yann Guidon / YGDES • 12/06/2020 at 13:45 • 0 comments

  The new probe system works nicely ! Except when it doesn't... This happens when any sign of backwards connection appears, even when a backwards gate is inserted !
  

  This is caused by the limitations in the way one can drive an entity's output : it has to be triggered by at least a change of one input. The new probe algorithm takes a "safety shortcut" by changing the output only when all the inputs have a valid value. This effectively prevents the gate's output from propagating the "toggle signal" when one input is tied to a backwards gate, which has not yet received the toggle signal...

  It's a chicken&egg problem that would not exist if a gate's output was directly controllable by an external code. But the other cause is the AND condition for the new algorithm. It is required to ensure the speed in most circumstances and it performs great in the pure-boolean INC8 and ALU8 units. The "corner cases" test miserably fails though. Worse : all the logic cone after the first gate that receives a backwards signal is also "shadowed" because the trigger signal can't propagate.

  And because of the "shadow", it's not possible to know if a "disconnected" gate is really disconnected, receives a backwards signal OR is in the shadow of a backwards-fed gate.

  The answer to this question can come from a "preliminary pass" that scans/propagates through all the circuit but instead of sending a chunk of the driving gate's number, it sends the type of the driving gate: input, boolean, backwards... This first pass will already solve the question of which inputs are not connected, so these gates can still propagate other trigger signals during the main probing algorithm.

  The new pre-pass requires storage of (temporary ?) extra data for each input (gate & output port), which can be :

  • not connected - 'U'
  • input port
  • gate
  • backwards
  • (eventually a sequential gate ?)

  This can be a single std_logic variable, but it must be allocated somewhere. It can be temporary because unconnected inputs cause the rest of the program to fail, and once the netlist is built, checking the type of the driver is easy :

  • input ports are non-positive driver numbers,
  • gates, including backwards, have a positive driver number,
  • gates have a enum_gate_kind that can be looked up.

  (to be continued)

View all 26 project logs