[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

Jacob Lifshay <programmerjake at gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|CONFIRMED                   |IN_PROGRESS

--- Comment #7 from Jacob Lifshay <programmerjake at gmail.com> ---
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.

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

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)

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