News for hackers. Stuff that matters.
Re:Some small suggestions for the Intel instruction set by pascal_cuoq on Sunday May 18, 2014 @01:57AM (#7762315)
> What's crazy about this is that we're limited to multiplying integers

> of about 25 bits [...]

> Why? Because the multiplier insists on rounding

> its low output bits rather than giving them back to the programmer.

> Why? Because the multiplier is buried inside the floating-point unit.

The reference to the 25-bit success makes it seem like the author is thinking of bits 53-105 of the 106-bit result of multiplying two 53-bit inputs.

The multiplier is not going to “give them back” to the programmer because it never computed them in the first place. Floating-point 53x53->53 multiplication is implemented with a couple of guard bits, the last of which is “sticky”. The multiplier the author is asking for is not “buried”, it does not exist in the processor.

I am not sure why integer multiplication is not preferred. It goes up to 64x64->128, if the author wants all the bits of the product.

> A 53-bit multiplier producing a full 106-bit product won't be much larger than a 53-bit multiplier producing a correctly rounded 53-bit floating-point result.

Yes, it will. It will have to be 106-bit wide instead of 56-bit wide.

Re:Some small suggestions for the Intel instruction set by nkurz on Sunday May 18, 2014 @04:16AM (#7762512)
I am not sure why integer multiplication is not preferred. It goes up to 64x64->128, if the author wants all the bits of the product.

I'm a little confused by this also, but given the level of detail in the linked paper (http://eprint.iacr.org/2014/134.pdf) it's definitely not just an oversight. The issue may be that he's aiming for fastest possible performance on Sandy Bridge (AVX), and 256-bit integer vector multiplication wasn't added until Haswell (AVX2). And even then, 64-bit integer elements can only be done one at a time. But since he's suggesting instruction set changes, he's clearly not thinking only of backwards compatibility.

Re:Some small suggestions for the Intel instruction set by makomk on Sunday May 18, 2014 @07:23AM (#7762737)
I think the design of his Curve25519 elliptic curve assumes 25-bit integers implemented using floating point arithmetic and requires them for maximum performance. I certainly haven't seen any fast integer-only implementations of it.
Re:Some small suggestions for the Intel instruction set by stromgo on Sunday May 18, 2014 @04:22AM (#7762524)
How do you correctly round, say, 6172293634027511 * 7059478094414279 / 2^53 = 4837593847918366.50000000000000011102 without essentially computing the full 106-bit product?
Re:Some small suggestions for the Intel instruction set by nwhitehead on Sunday May 18, 2014 @01:54PM (#7763722)
The idea is that you can use guard digits instead of full products and get correct rounding (as if to infinite precision). For IEEE-754 math you need 3 guard digits, typically named Guard, Round, and Sticky. The trick at the hardware level is that Sticky represents the OR of a bunch of bits. Instead of keeping the full 106 bit partial product at each step you only need to keep the 53+3 bit product. As you shift+add the partial products you use special rules to keep track of the Sticky bit and you will still get the right answer.
Re:Some small suggestions for the Intel instruction set by fdej on Sunday May 18, 2014 @04:27PM (#7764290)
I'm aware of the 53+3 bit algorithm for addition and subtraction, but I don't see how this could possibly work for multiplication. Could you please point me to a paper that explains how to compute a correctly rounded 53-bit product without computing the full 106-bit product?
Re:Some small suggestions for the Intel instruction set by pascal_cuoq on Monday May 19, 2014 @03:21AM (#7766127)
I can't find a handy reference, but here is a 5x5 multiplication:

     1XXXX
   * 1XXXX
 _________
     XXXXX
    XXXXX
   XXXXX
  XXXXX
 1XXXX
Using a sticky bit means computing the logical-or of all the bits that are sufficiently far to the right in all these partial results, instead of computing them individually and summing them.

Like for addition, the idea is that the result you obtain is different from the exact result, but rounds the same. The sticky bit only serves to round (midpoint + a small quantity) correctly up.

Re:Some small suggestions for the Intel instruction set by stromgo on Monday May 19, 2014 @12:39PM (#7768345)
Let's say that the full product in your example is

  1XXXXYZZZZ
To round it we need:

(1) the X bits for our answer

(2) the Y bit for rounding

(3) the logical-or of the Z bits for rounding

Ok so there might be a trick to compute (3) without computing ZZZZ, but we still want to know how to compute 1XXXXY without computing ZZZZ.

Re:Some small suggestions for the Intel instruction set by pascal_cuoq on Monday May 19, 2014 @02:23PM (#7768939)
Perhaps a better way to describe it is that during the additions, the accumulator only ever needs to be shifted right in order to be aligned with the next number to add, never left. So the accumulator can be 53+3-bit wide and carry at each step the 53+3-bit representation of the partial sum already computed, and this is enough to produce the correctly rounded result after all numbers have been added.

This explanation assumes that the N partial products are added sequentially. I don't know what techniques are used to achieve the 4- or 5-cycle latencies of modern desktop processors. Implementations with more parallelism and/or that are part of an FMA unit have it harder, but I still expect that they don't naively compute a full width partial result before rounding it (in the case of the FMA, it would be impractical as the partial result could be thousands of bits wide)

Re:Some small suggestions for the Intel instruction set by stromgo on Monday May 19, 2014 @03:15PM (#7769213)
Looks like you're actually computing the full product. The only optimization you're doing is forgetting the low order bits as soon as you're done with them. The author is asking to keep them, which sounds reasonable. You initially claimed they were "never computed in the first place", and we're asking you to back up that claim if you still think it's true.
Re:Some small suggestions for the Intel instruction set by pascal_cuoq on Monday May 19, 2014 @03:27PM (#7769272)
I see what you mean now. I agree that each of the low-order bits of the 106-bit product is available at some point. Not necessarily simultaneously, but yes, it seems like little additional effort for processor designers to keep these somewhere and assemble them in another register or something.

For some reason (maximum depth reached?) there is no “reply” link at the bottom of the post of yours at which I understood, so I am replying here.

Re:Some small suggestions for the Intel instruction set by dragontamer on Sunday May 18, 2014 @10:26AM (#7763149)
IEEE Floating point rounds numbers in binary, not in decimal. So it is trivial by simply having a 54-bit register to hold the 53-bit mantissa.

So the answer to your question is... Floating Point numbers "don't round correctly". They're actually quite complicated, and require careful study.

Re:Some small suggestions for the Intel instruction set by stromgo on Sunday May 18, 2014 @12:06PM (#7763401)
My example has nothing to do with decimal rounding. It's an example of a product (6172293634027511 * 7059478094414279) whose result is extremely close to the fence between two representable numbers (4837593847918366.5 * 2^53). If the 106-bit product happened to be 2 units smaller, then the rounded result would change.
Re:Some small suggestions for the Intel instruction set by dragontamer on Sunday May 18, 2014 @01:29PM (#7763635)
As stated before, Floating Point numbers "don't round correctly" according to IEEE Floating Point arithmetic.

There are very simple rules on how to round. This makes calculation of errors a bit complicated. http://en.wikipedia.org/wiki/IEEE_floating_point#Rounding_ru...

At best, Intel at one point provided 80-bit rounding (ie: 68-bit mantissa). That is, if you use the x87 floating-point coprocessor. But these technically do not match IEEE specifications for rounding.

Re:Some small suggestions for the Intel instruction set by fdej on Sunday May 18, 2014 @01:37PM (#7763666)
Er, what? Floating point numbers do "round correctly" (in binary) -- that's pretty much the whole point of the IEEE standard.

In particular, to compute a product of two 53-bit floating-point numbers with correct rounding (as the standard mandates), it is certainly not sufficient in general to compute just a 54-bit approximation and round that.

Re:Some small suggestions for the Intel instruction set by fdej on Sunday May 18, 2014 @09:09AM (#7762957)
Could you point to a paper that shows how to compute a correctly rounded 53-bit floating-point product without computing all 106 bits?