last day (14 days later) » 

7:44 PM
10
Q: Can I use the AVX FMA units to do bit-exact 52 bit integer multiplications?

BeeOnRopeAXV2 doesn't have any integer multiplications with sources larger than 32-bit. It does offer 32 x 32 -> 32 multiplies, as well as 32 x 32 -> 64 multiplies1, but nothing with 64-bit sources. Let's say I need an unsigned multiply with inputs larger than 32-bit, but less or equal to 52-bits - can I...

 
Good question. You should be good to go, as the FMA instructions are equivalent to IEEE 754 double-precision arithmetic (with only one rounding stage at the end). Anything you can do with a double should be achievable.
 
Yeah, I probably put too much emphasis on FMA - it could be a plain vectorized MUL too. The question should is will the result be bit-exact equivalent to an integer multiply for all integers up to 2^52-1?
 
Yes, you will get exact integer arithmetic, provided that you never have intermediate results that fall outside that range. I've encountered software that took advantage of this, using double types when more-than-32-bit integer operations were needed (said software was written before 64-bit processors became mainstream, so processors with good FPUs could have better double-precision speed versus emulating a 64-bit integer operation in software).
 
Prime95 version 28 uses AVX2 + FMA if available, since apparently that's faster than whatever they used before in version 27 (and definitely makes more heat, so it's a tougher stability-test for your hardware). I don't know how they use it, but prime-testing is inherently an integer problem, so it's worth looking into, since the source is available with apparently few restrictions on reuse: mersenne.org/download/#source
Fun fact: AVX-512 IFMA adds two instructions designed to make this easier: 52-bit low and high integer multiplies. This is obviously designed to take advantage of existing multiply hardware, not because anyone really wants a 52-bit-only multiply.
 
What about using FMA for 106-bit integers stackoverflow.com/a/31072201/2542702
 
7:44 PM
@JasonR - and for a straight MUL (rather than FMA) there will never be any intermediate result, right? Same (effectively) for FMA with addend zero?
@Zboson - your link made me realize that (a) maybe I actually want a 106 bit product or that perhapsa (b) I actually wanted the low 52/53 bits of a product that may have some higher bits too, and a 106 bit solution would include that. I added a paragraph to the question starting with "How about the more general..." - and perhaps your answer there can be applicable here too (and I have some questions...).
 
@PeterCordes No special tricks. They use FFTs to perform the large integer multiplication. And FFTs are entirely floating-point operations.
@BeeOnRope On recent processors, pmulld is actually half the throughput of pmuldq. So this cancels out the "half rate" that you're observing. The most plausible reason for this is that the hardware consists of one 52 x 52 -> 104-bit multiplier per 64-bit SIMD lane. By suppressing the correct carry-propagation lanes, it can double as a pair of 23 x 23-bit -> 46-bit multipliers for single precision.
For pmuldq, you have one operation per 64 bits. So you simply zero-pad the 32-bit inputs and truncate the 102-bit output down to 64 bits. For pmulld, you have two 32-bit multiplies per 64-bits of data. 32 is too large to fit into the single-precision multiply. So you must run it through the full 52-bit multiplier. But you must do it twice since you only have half as many multipliers as you have operands. Therefore pmulld has double the latency and half the throughput.
 
@Mysticial - yes, that makes a lot of sense, especially given, for example, that PMULLD and fiends send 2 uops to either p0 or p1 - that really looks like doing the operation twice, once for half of the entries each time. What's interesting is that the latency (Skylake) is fully 10 - 2x the 5 cycle mul latency, whereas I'd expect it could be 6 (i.e., the two halves are independent, so start the second half in the second cycle).
I guess maybe it was easily just to do it that way so you could do the second mul with the first half results already sitting in the alternate words, since the parallel approach would require some kind of final blend.
 
I don't think it's been mentioned yet but AVX512 has 64x64 -> 64 with vpmullq (_mm512_mullo_epi64). @Mysticial suspects this will be slow. In any case I have AVX512 hardware (but KNL which are low power Silvermont cores so perhaps not reflective of high power cores) to test this now...If I find time.
 
Are there Skylake Xeons shipping with AVX-512 yet?
 
Not that I am aware of. I don't think they will appear until after summer. Facebook and Google have them I think though (which has angered a lot of other server users). I think they will show up after AMD Ryzen or whatever they call it now.
 
7:44 PM
@Zboson Without knowing much about Skylake Purley, I'm putting my money on vpmullq being a 3-uop instruction with a latency no more than 12 or 15 cycles.
 
@Zboson - in case it wasn't clear above, I'm kind of nudging you to post an answer based on your earlier note about using FMA for 106 bit integers. At some point, I'll do it if you don't, but I want to ask some questions and it's weird to ask questions on my question :)
 
@BeeOnRope, I already started looking into it. I have not worked with double-double in several months so I am rusty. I think the main problem is that with integer multi-word arithmetic multiplication is complex but addition is simple whereas with double-double it's the other way around. I think this means that you have to move back and forth between integer128 and double-double. This requires a lot of bit manipulation which I have not worked out yet and I'm not even sure it will be efficient. It looks like with AVX512 they do this for you.
 
@BeeOnRope, You can use 2 vectors one for 0-31 bits and another for 32-51 bits that obviously adding them needs some efforts. after that do the 32->64 multiplication for both vectors and add the results in an appropriate way. then you have a 52->64 multiplication that the source is 2 separated 32 bits included one full 32 bits and one 20 bits used. thats it no need for any FP just separate them multiply and shift left the second vector results for generating the ultimate results on 52->64 multiplication and if you want more use 2 duplicated vectors for simulating all multiplications
 
@Zboson - at first I thought your answer on the other linked question solved all my problems (efficient computation of 52/53 low-bits of an integer multiply), but after re-reading it I became confused and asked you a ?n over there.
 
7:44 PM
@BeeOnRope have you tried implementing it yet? You can start with scalar code using fma from math.h. E.g. int64_t ai = (1LL<<40)-1, bi = (1LL<<40)-1; double a = ai, b = bi; double p = a*b, e = fma(a,b,-p);. And then look at p and e. Try different values of ai and bi.
@BeeOnRope, well based on Mysticial's comments here he has already done it. It's probably mostly useful for education. If I work it out I will post an answer.
 
@Zboson I'll do it if I have time. But the problem with the approach is that there are too many loose corners. The "optimal" answer will vary drastically depending on what your want the inputs and outputs to be. (integers? doubles? scaled doubles?) The explosion of solutions basically boils down to the large number of ways to merge it with the scaling and the fast double<->int64 trick. Not to mention different scaling values depending on what range of inputs you want to support. And then you have the issue where the lower word may be negative...
@Zboson And I forgot to mention that some the solutions may break with -ffast-math. So they're pretty flaky to begin with (even if provably correct on paper). At least that was the case under ICC. I know GCC does some fast-math optimizations with intrinsics. But I don't know if it does it enough to break these methods.
 

last day (14 days later) »