[Libre-soc-bugs] [Bug 1044] SVP64 implementation of pow(x,y,z)

[bugzilla-daemon at libre-soc.org]

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

Jacob Lifshay <programmerjake at gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://bugs.libre-soc.org/
                   |                            |show_bug.cgi?id=973

--- Comment #35 from Jacob Lifshay <programmerjake at gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #33)
> (In reply to Jacob Lifshay from comment #32)
> 
> >     add WIP knuth algorithm D python implementation
> 
> nice. clear.
> 
>    362    if qhat * vn[n - 2] > (rhat << word_size) + un[j + n - 2]:
> 
> can use 1<<r3 on that, where r3=j, temporarily, rather than Indexed
> REMAP. but really, Indexed REMAP is a necessity here.

actually, I think using svoffset is a much better idea. (we need a dynamic
instruction to set svoffset for dynamic bigint shifts anyway, bug #973)
> 
> 
>    380             # subfe
>    381             t += ~product[i] + un[j + i]
> 
> just sv.subfe!

yup!

> but you need Indexed REMAP on un[j+i]
> and can replace it later with Bigmul (rhombic) REMAP.
> 
> ultimately though this *is* going to need Vertical-First,
> with the "svstep." notification, as the loops j and i are
> nested.

I disagree, this algorithm isn't very suitable for vertical-first, because it
has both operations in one and two loop nesting levels:

e.g.:
for j in ...:
    qhat = ...  # scalar here
    for i in ...:  # vector here
        mul/add/sub
    for i in ...:  # more vector here with different offsets
        mul/add/sub


this makes it not really work with rhombic REMAP.

another reason vertical-first isn't very suitable: several sections are
necessary for correctness but extremely rarely run (for random inputs on the
order of 1 in 2^64), such as the qhat overflow and add-back sections.

Therefore I'm planning on writing it to use horizontal-first with svoffset.

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