[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 #9 from Luke Kenneth Casson Leighton <lkcl at lkcl.net> ---
(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?


> https://git.libre-soc.org/?p=openpower-isa.git;a=blob;f=src/openpower/test/
> bigint/powmod.py;h=73d87b35dd8df841596fff4f5153464362882917;
> hb=a3c1930de7990c8babcb3908ed7650e1d08eafb6#l102

please remove this:
 105     # run this file in a debugger to see all the intermediate values.

(use log statements instead)

> python version:
>     y = [0] * (a_sz + b_sz)
>     ca = 0
>     for i in range(a_sz * b_sz):
>         # no need to clear ca between ai outer loops, since the partial
>         # products can't get big enough to have a carry out, so ca will
>         # always be zero when (i % b_sz == 0).
>         # That said, hardware will probably want to pattern-match this to
>         # remove the unnecessary dependency through ca.
>         y[a_plus_b_idx[i]], t = maddedu(
>             a[a_idx[i]], b[b_idx[i]], y[a_plus_b_idx[i]])
>         y[a_plus_b_plus_1_idx[i]], ca = adde(
>             y[a_plus_b_plus_1_idx[i]], t, ca)

reduce these variable names down to fit on one line.

e.g. ab1i then add a comment on initialisation.

i'll take a closer look, as it will take some time for the impact to
sink in.

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)

https://git.libre-soc.org/?p=openpower-isa.git;a=blob;f=src/openpower/decoder/isa/remap_fft_yield.py;h=a15c5bf7871507b34a6e2a043e73284e60e22bec;hb=a3c1930de7990c8babcb3908ed7650e1d08eafb6#l85

that's the next code-morph step.

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