| View previous topic :: View next topic |
| Author |
Message |
Quadibloc
Guest
|
 Posted: Fri Oct 10, 2008 1:06 am Post subject: Usually Fast IEEE-754 Compliant Goldschmidt Division |
 |
|
I read a news item about resarch by Valeria Bertacco and Ilya Wagner
recently. They were proposing a system whereby a microprocessor could
be set up to work normally most of the time, doing the common
operations for which it had been fully validated, and replaced by a
slower, simpler processor whose operation would not have unforeseen
bugs whenever it did the few, rare operations that were not fully
tested.
I suspect that this will turn out to be a "silly idea", in the sense
that it will not really turn out to be possible to employ it in the
specific way planned. However, it is also a brilliant idea - because I
think I can think of a way to employ this principle in a much
*simpler* case where it _is_ pretty well guaranteed to be useful.
The fastest division algorithm known is Goldschmidt division, which
approximates a quotient through multiple iterations of a formula
involving a single multiplication, which doubles the number of known
digits each time.
It is not well-adapted, however, to the requirement of the IEEE-754
standard that each arithmetic operation, including division, return
the best possible rounded answer in all cases. Patented schemes have
been devised to deal with this, but they usually involve doubling the
amount of hardware required, and adding at least one cycle to the
latency of division operations.
But the probabilistic angle that their scheme embodies would be
perfect for resolving the division issue.
Perform Goldschmidt division to yield a result that is, say, 10 bits
longer than the required precision of the quotient. If the guard
digits are not between .499 and .501, (or, actually, 511 and 513)
there is no chance of the rounded-down answer being even slightly
wrong - it is the exact IEEE-754 answer, and nothing more need be
done. But if they are, then in those few cases, the answer from a
slower method, such as SRT division, that only requires a little added
hardware, can be used.
Come to think of it, this is perhaps not a new idea, and may have been
the *first* scheme proposed to resolve the issue - with the other
inventions being devised because deeply pipelined computers may be
intolerant of instructions with even occasionally variable timings.
John Savard |
|
| |
|
 Back to top |
Terje Mathisen
Guest
|
| Posted: Fri Oct 10, 2008 8:23 am Post subject: Re: Usually Fast IEEE-754 Compliant Goldschmidt Division |
|
|
Quadibloc wrote:
| Quote: | Perform Goldschmidt division to yield a result that is, say, 10 bits
longer than the required precision of the quotient. If the guard
digits are not between .499 and .501, (or, actually, 511 and 513)
there is no chance of the rounded-down answer being even slightly
wrong - it is the exact IEEE-754 answer, and nothing more need be
done. But if they are, then in those few cases, the answer from a
slower method, such as SRT division, that only requires a little added
hardware, can be used.
|
If you want to go this route, then you should realize that the added HW
for an SRT divider is almost certainly at least comparable to what you
need to run one more iteration of Goldschmidt.
There is also the small issue of non-predictable timing (but this is
often already an issue for denormal operands and/or results), i.e. when
using this as part of anything crypto-related, you don't want a timing
attack to leak info about the secret key.
| Quote: | Come to think of it, this is perhaps not a new idea, and may have been
the *first* scheme proposed to resolve the issue - with the other
inventions being devised because deeply pipelined computers may be
intolerant of instructions with even occasionally variable timings.
|
That is indeed an issua, but see denormal above.
The problem is often that either you do this in X cycles, or you spend
X+100, because you have to restart the entire pipeline after a hw trap.
Terje
--
- <Terje.Mathisen@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching" |
|
| |
|
| Back to top |
Glen Herrmannsfeldt
Guest
|
| Posted: Mon Oct 27, 2008 1:24 pm Post subject: Re: Usually Fast IEEE-754 Compliant Goldschmidt Division |
|
|
Terje Mathisen wrote:
(snip)
| Quote: | There is also the small issue of non-predictable timing (but this is
often already an issue for denormal operands and/or results), i.e. when
using this as part of anything crypto-related, you don't want a timing
attack to leak info about the secret key.
|
I would not usually do cryptography in floating point.
It is an interesting idea, though.
-- glen |
|
| |
|
| Back to top |
|
