[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 #41 from Jacob Lifshay <programmerjake at gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #39)
> we *do* actually have to think through, from the implementor's persective,
> if the Software API (aka SV) is actually viable. but - butbutbut - not
> from just ONE implementation but ***ALL*** possible implementations.

yes, which is why I think we should design it so if some implementation decides
it likes some other multiplication algorithm and wants to translate, it isn't
required to produce some other expensive outputs that basically no software
will care about, but are practically required for correctness -- the
temporaries.

if the cpu has to look 3000 instructions into the future to see that the
temporary is ultimately overwritten, no reasonable cpu for a very long time
will be able to do that, so will be required to compute the temporary values
which are quite expensive.

from a SV consistency point of view, we can't just declare the temporaries as
undefined (since there isn't a good reason why a simple loop over scalar
multiplies should suddenly be allowed to give arbitrary random results),
so the next best option is to have a cheap simple instruction to clear the
temporaries after -- unless we can come up with a bigint mul algorithm that
naturally overwrites all temporaries (e.g. the only things changed are the
product's registers), or where the values left in the temporaries are cheap to
compute.

obviously if you're using a simple scalar cpu, you can omit the
clear-temporaries instruction, but if you could be using a high-end cpu, imo
it's worth having.

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