[Libre-soc-dev] adding PartitionedSignal support to nmigen's If/Switch/Case

lkcl luke.leighton at gmail.com
Tue Sep 21 15:38:44 BST 2021

i checked the notes in the bugreport,

tracked through the original conversation with whitequark:

i'm going to write out what i can remember.  it's written as "statements". however *please automatically assume* that it is perfectly fine to say "that's wronggg... because".

also "screaming and running away in horror at the inefficiency" is perfectly fine.

the logic is as follows:

* with the "rules" established by PartitionedMux being that ALL bits are set in a given partition, the "if" statements, which ordinarily and conceptually think if themselves as "single bit" and comprise exclusively the use of AND, OR, NOT, and MUX, all abstract perfectly to a multi-bit context, producing HDL statements that result in a multi-bit boolean not a single-bit boolean.

* thus any given m.If test needs zero code-conversion, the ONLY thing needed is for all use of Mux(a, b, c) to be redirected to a.Mux(b, c) which is trivial to do.  AND and OR etc *already* do that (Value.__and__ overloaded at PartitionedSignal)

* a parallelised Switch Statement may therefore (at line 447 above) be a trivial and independent for-loop, creating *multiple independent* switch statements, partitioning the results by their respective partition.

(is this "efficient"? probably not. as a first pass that allows forward progress, do we care if it is efficient? absolutely not.  can we *AFTER* finding that out and having concrete information put in well-informed Grant requests? yes we can)

* assuming there are 64 bit PartitionedSignals and 7 partition points to create QTY 8of 8-bit independent partitions, and that PartitionedBool is also a PartitionedSignal of width 8-bit where again it *also* is subdivided into single independent bits per partition...

... the subdivision by the above for-loop into *multiple* switch statements (QTY 8of when there are 7 partition  points) result in:

* the first byte of any 64 bit signal being assigned to its respective destination (also a first byte) based on the first bit of the m.If test being passed to the first (of 8) switch statements
* the first *bit* of any 8 bit PartitionedBool aka 8-wide PartitionedSignal *also* being likewise assigned.

this role can in fact be handled completely by a Partition-aware Part function, leveraging it to:
* break down pieces of all m.If, all inputs, and all output
* perform "reconstruction" of outputs from all 8 separate switch statements

(temporary Signals may help here)

* a Partition-aware Part Function may abstract out in exactly the same way, Part(a, b, ....) --> a.Part(b, ...)

* with that Part function now being an object-operator (similar to __add__) we return to the for-loop switch statement back at line 447 of dsl.py and *replace* that line with a call to a function.

that function is a member of Value and has an exact copy of what is performed at line 447.

* in the OVERRIDE of that function, in PartitionedSignal, the for-loop is performed which then uses PartitionedSignal.Part to *reconstruct* and amalgamate the 8 independent partitioned results.

the end result is a huge code-duplication of the switch statement logic (8 times) which if that turns out to be seriously problematic can be reduced by restricting the permitted range of supported Partitions:

* 1x 64
* 2x 32
* 4x 16
* 8x 8

which will halve the number of duplicated switch statements.

nested switch statements and nested If/Else statements will result in a combinatorial explosion *and we still don't care* as a "first pass".

as a "first pass" it is "good enough" (i.e. is functional) such that we can make forward progress and have valuable working knowledge sufficient to put in clear Grant requests with confidence.

right now i have *no idea* what is in yosys so cannot even begin to write such a Grant application.

incremental development.


More information about the Libre-soc-dev mailing list