[Libre-soc-bugs] [Bug 1155] O(n^2) multiplication REMAP mode(s)

[bugzilla-daemon at libre-soc.org]

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

--- Comment #10 from Jacob Lifshay <programmerjake at gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #9)
> (In reply to Jacob Lifshay from comment #7)
> > I came up with a somewhat different bigint mul remap algorithm, it has a few
> > issues though...I also rebased the branch on latest master.
> > 
> > commit a3c1930de7990c8babcb3908ed7650e1d08eafb6
> > Author: Jacob Lifshay <programmerjake at gmail.com>
> > Date:   Thu Dec 21 21:10:11 2023 -0800
> > 
> >     tests/bigint/powmod: initial version of bigint multiply remap
> >     
> >     it has some issues around being able to encode scalar RS but
> >     vector RT, and doesn't match the scalar * vector multiplication
> >     pattern, but is quite compact.
> 
> i was expecting / anticipating use of vertical-first, this is
> different / cool, how does it work?

it is vertical first.

basically, I realized that, if you do it in the right sequence, you can compute
a[:] * b[:] by just computing each partial product a[ai] * b[bi] and adding
each one in the right place in the final result:

y = [0] * ...
for ai, bi in right_sequence():
    partial_product = a[ai] * b[bi]
    y += partial_product << (word_size * (ai + bi))

this becomes a vertical first loop:
loop:
    sv.maddedu *y, *a, *b, *y  # RS is stored in scalar t
    sv.adde *(y + 1), *(y + 1), t
    svstep.
    sv.bdnz ... loop


> if done as a "yielder" i think i will get it immediately.
> like this (which is entirely standalone executable, *no*
> use of *any* externl modules, this is very deliberate)

well, notice it builds the list of remap indexes, and then the loop that
actually operates on the data just goes through those indexes in sequence,
doing (combination python and sv asm syntax):
*y, t = maddedu(*a, *b, *y)
*(y + 1), ca = adde(*(y + 1), t, ca)

so the "yielder" (if you mean the code that produces remap indexes) is just the
loops building the indexes, with:
some_list.append(the_index)

replaced with:
yield the_index.

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