[Libre-soc-bugs] [Bug 745] OP_TERNARY instruction

[bugzilla-daemon at libre-soc.org]

https://bugs.libre-soc.org/show_bug.cgi?id=745

--- Comment #7 from Jacob Lifshay <programmerjake at gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #5)
> (In reply to Jacob Lifshay from comment #4)
> > Added formal test for BitwiseLut:
> > https://git.libre-soc.org/?p=nmutil.git;a=commitdiff;
> > h=878e4c6776203e12abb4cf4e78f6d251121418c1
> 
> excellent.  btw the convention for those is that they go
> in a directory named "formal" rather than a directory named
> "test".

k, i put them in the test file cuz I already had it open...didn't think about
that. Also, I rely on the formal proof to ensure complete coverage since there
are too many cases to check in a unit test.
> 
> (In reply to Jacob Lifshay from comment #2)
> > updated the plan https://bugs.libre-soc.org/show_bug.cgi?id=745#c0
> > also, ternary is not a very good name (too generic), imho a better name
> > would be ternlog (like x86's instruction) or lut3
> 
> lut3's good.  using x86 names... hmmm.

the benefit of using x86's name is someone who has seen the x86 instruction
before will know exactly what it does, without having to look it up. The other
names are worse cuz they don't indicate that the operation is bitwise... the
log in ternlog indicates bitwise logic.

> (In reply to Jacob Lifshay from comment #3)
> > Added BitwiseLut, which is a generic n-ary bitwise lut -- ternary is just
> > BitwiseLut(input_count=3, width=64)
> > 
> > https://git.libre-soc.org/?p=nmutil.git;a=commitdiff;
> > h=3e45917af6e91df910b6fc77d031ee3a656c4116
> 
> +                for i in range(self.input_count):
> +                    if sel_values[i]:
> +                        lut_index |= 2 ** i]
> 
> that could simply be done in one line as:
> 
>      lut_index.eq(Cat(*sel_values)

no, it can't cuz sel_values is a tuple of bools and lut_index is an int, they
are not nmigen Values.
> 
> also... i'm not really sure this is a correct implementation.  there
> are 256 unit tests required: one for each and every 4th input, because
> the 4th input (lut) is 8-bit wide and therefore there are 256 possible
> values.

there's actually 2^56 possible input values cuz 3 * 16-bit inputs + 8-bit lut.
I decided that was too many to test all of, so I rely on the formal proof for
complete coverage and just pick 100 pseudorandom cases (using sha256 for
reproducibility) to test in the unit test.

> also, i'm surprised it works without using Array()
> (yes there are shorter ways to do this):
> 
> self._lut_underlying_signal = Signal(8)
> lut_bits = []
> for i in range(len(self._lut_underlying_signal)):
>     lut_bits.append(self.lut_underlying_signal[i])
> self.lut = Array(lut_bits)
> 
> without that dynamic indexing i would not expect it to work,
> at all [Array creates a pmux at the back-end].
> 
> if it does work then i expect that what you've written is
> a re-implementation of pmux (Array) using a lot more lines of
> code than is necessary (30 instead of 2)
> 
> the whole module should be literally this - really not kidding,
> only around 4 lines:
> 
>     lut = Array([lut_input[i] for i in range(lut_width)])
>     for i in range(input_width):
>         output[i].eq(lut[Cat(in1[i], in2[i], in3[i])])
> 
> that's it.  that's the entire implementation.
> 
> 
> also, what is the Repl() for?
well, the way I implemented it is by building a binary tree of output-width
wide BitwiseMux selecting based on the inputs, where each Signal in the tree is
output-width wide -- the Repl is to splat each lut bit into an output-width
wide value so the BitwiseMux tree has all the right input bits. if you use
yosys show, you should get a good idea of the structure:

       output
          |
     /----+----\
in0-/ mux_0bxxx \
   /--0-------1--\
      |       |
      +---+   +-------------+
          |                 |
     /----+----\       /----+----\
in1-/ mux_0bxx0 \ in1-/ mux_0bxx1 \
   /--0-------1--\   /--0-------1--\
      |       |         |       |
      |       |         |       +-------------------------------+
      |       |         +---------------------+                 |
      +---+   +-------------+                 |                 |
          |                 |                 |                 |
     /----+----\       /----+----\       /----+----\       /----+----\
in2-/ mux_0bx00 \ in2-/ mux_0bx10 \ in2-/ mux_0bx01 \ in2-/ mux_0bx11 \
   /--0-------1--\   /--0-------1--\   /--0-------1--\   /--0-------1--\
      |       |         |       |         |       |         |       |
    splat   splat     splat   splat     splat   splat     splat   splat
      |       |         |       |         |       |         |       |
    lut[0]  lut[4]    lut[2]  lut[6]    lut[1]  lut[5]    lut[3]  lut[7]

-- 
You are receiving this mail because:
You are on the CC list for the bug.