practical BigNum AVX/SSE possible?

Question

SSE/AVX registers could be viewed as integer or floating point BigNums. That is, one could neglect that there exist lanes at all. Does there exist an easy way to exploit this point of view and use these registers as BigNums either singly or combined? I ask because from what little I've seen of BigNum libraries, they almost universally store and do arithmetic on arrays, not on SSE/AVX registers. Portability?

Example:

Say you store the contents of a SSE register as a key in a std::set, you could compare these contents as a BigNum.

Of course it's possible, just insanely inconvenient, inefficient and slow. When you do addition with arrays of limbs (32/64-bit words), it's easy to use the x86 Carry flag to propagate the carry bit. The lanes of SSE registers do not have carry flags, which means overflow must be detected in a different way (more computationally intense), and even if you did detect overflow you have then the problem of complicated SSE/AVX shuffles to move up the carries, and you have to do this N-1 times for N-limb bignums. Then what happens if you need to extend a bignum beyond 128-bit/256-bits...? — Iwillnotexist Idonotexist
You join 2 or more of the registers together, using gcc/clang/icc vector extensions. You can write an answer, why you think it would be impractical. The thing is, I think gcc maps arrays to SIMD registers badly, but it maps SIMD registers in the reverse direction readily and w/o any problems. — user1095108
What you've linked to is not a way to dynamically extend a bignum at runtime. What you linked to is a method to declare limited- and fixed-size vectors (with lanes) at compile time. You still have exactly the same problems I've listed above, and you still cannot easily detect and propagate carries from the lower to the upper limbs using those extensions. — Iwillnotexist Idonotexist

Z boson Z boson · Accepted Answer · 2015-01-16T05:52:39

I think it may be possible to implement BigNum with SIMD efficiently but not in the way you suggest.

Instead of implementing a single BigNum using a SIMD register (or with an array of SIMD registers) you should process multiple BigNums at once.

Let's consider 128-bit addition. Let 128-bit integers be defined by a pair of high and low 64-bit values and let's assume we want to add a 128-bit integer (y_low, y_high) to a 128-bit integer (x_low, x_high). With the scalar 64-bit registers this requires only two instructions

add rax, rdi // x_low  += y_low;
adc rdx, rsi // x_high += y_high + (x_low < y_low);

With SSE/AVX the problem, as others have explain, is that there is no SIMD carry flags. The carry flag has to be calculated and then added. This requires a 64-bit unsigned comparison. The only realistic option for this with SSE is from the AMD XOP instruction vpcomgtuq

vpaddq      xmm2, xmm0, xmm2 // x_low  += y_low;
vpcomgtuq   xmm0, xmm0, xmm2 // x_low  <  y_low
vpaddq      xmm1, xmm1, xmm3 // x_high += y_high
vpsubq      xmm0, xmm1, xmm0 // x_high += xmm0

This uses four instructions to add two pairs of 128-bit numbers. With the scalar 64-bit registers this requires four instructions as well (two add and two adc).

With AVX2 we can add four pairs of 128-bit numbers at once. But there is no 256-bit wide 64-bit unsigned instruction from XOP. Instead we can do the following for a<b:

__m256i sign64 = _mm256_set1_epi64x(0x8000000000000000L);
__m256i aflip = _mm256_xor_si256(a, sign64);
__m256i bflip = _mm256_xor_si256(b, sign64);
__m256i cmp = _mm256_cmpgt_epi64(aflip,bflip);

The sign64 register can be precomputed so only three instructions are really necessary. Therefore, adding four pairs of 128-bit numbers with AVX2 can be done with six instructions

vpaddq
vpaddq
vpxor
vpxor
vpcmpgtq 
vpsubq

whereas the scalar registers need eight instructions.

AVX512 has a single instruction for doing 64-bit unsigned comparison vpcmpuq. Therefore, it should be possible to add eight pairs of 128-bit numbers using only four instructions

vpaddq
vpaddq
vpcmpuq
vpsubq

With the scalar register it would require 16 instructions to add eight pairs of 128-bit numbers.

Here is a table with a summary of the number of SIMD instructions (called nSIMD) and the number of scalar instructions (called nscalar) necessary to add a number of pairs (called npairs) of 128-bit numbers

              nSIMD      nscalar     npairs
SSE2 + XOP        4           4           2
AVX2              6           8           4
AVX2 + XOP2       4           8           4
AVX-512           4          16           8

Note that XOP2 does not exist yet and I am only speculating that it may exist at some point.

Note also that to do this efficiently the BigNum arrays needs to be stored in an array of struct of array (AoSoA) form. For example using l to mean the lower 64-bits and h to mean the high 64-bits an array of 128-bit integers stores as an array of structs like this

lhlhlhlhlhlhlhlh

should instead be stored using an AoSoA like this

SSE2:   llhhllhhllhhllhh
AVX2:   llllhhhhllllhhhh
AVX512: llllllllhhhhhhhh

practical BigNum AVX/SSE possible?

3 Answers