practical BigNum AVX/SSE possible?

by

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

More Related Contents:

  1. SIMD math libraries for SSE and AVX
  2. How to solve the 32-byte-alignment issue for AVX load/store operations?
  3. What are the best instruction sequences to generate vector constants on the fly?
  4. How to efficiently perform double/int64 conversions with SSE/AVX?
  5. Loading 8 chars from memory into an __m256 variable as packed single precision floats
  6. Fast vectorized rsqrt and reciprocal with SSE/AVX depending on precision
  7. How to sum __m256 horizontally?
  8. Convention for displaying vector registers
  9. Fastest way to do horizontal vector sum with AVX instructions [duplicate]
  10. Find the first instance of a character using simd
  11. print a __m128i variable
  12. Vectorizing with unaligned buffers: using VMASKMOVPS: generating a mask from a misalignment count? Or not using that insn at all
  13. SIMD prefix sum on Intel cpu
  14. What’s missing/sub-optimal in this memcpy implementation?
  15. Simd matmul program gives different numerical results
  16. What’s the difference between logical SSE intrinsics?
  17. How to efficiently convert an 8-bit bitmap to array of 0/1 integers with x86 SIMD [duplicate]
  18. Loop unrolling to achieve maximum throughput with Ivy Bridge and Haswell
  19. Fastest Implementation of the Natural Exponential Function Using SSE
  20. Fast counting the number of set bits in __m128i register
  21. The Effect of Architecture When Using SSE / AVX Intrinisics
  22. Do I get a performance penalty when mixing SSE integer/float SIMD instructions
  23. cpu dispatcher for visual studio for AVX and SSE
  24. Which versions of Windows support/require which CPU multimedia extensions? (How to check if SSE or AVX are fully usable?)
  25. Using ymm registers as a “memory-like” storage location
  26. How to determine if memory is aligned?
  27. Transpose an 8×8 float using AVX/AVX2
  28. Efficient sse shuffle mask generation for left-packing byte elements
  29. Mathematical functions for SIMD registers
  30. inlining failed in call to always_inline ‘_mm_mullo_epi32’: target specific option mismatch

Leave a Comment