实用BigNumAVX/SSE可能吗？
practical BigNum AVX/SSE possible?
SSE/AVX 寄存器可以被视为整数或浮点 BigNums。也就是说，人们可能会忽略车道的存在。是否存在一种简单的方法来利用这种观点并将这些寄存器单独或组合用作 BigNums？我之所以问，是因为从我对 BigNum 库的了解来看，它们几乎普遍在数组上而不是 SSE/AVX 寄存器上存储和执行算术运算。便携性？
示例：
假设您将 SSE 寄存器的内容作为键存储在 std::set 中，您可以将这些内容作为 BigNum 进行比较。
从上面的评论中移出
可以这样做，但没有这样做，因为在向量寄存器中实现大数不是特别方便。
对于简单的加法任务，使用 x86 EFLAGS/RFLAGS' 寄存器的进位标志从最低 "limb" 向上传播加法的进位是微不足道的（使用 GMP 术语），并遍历放置在数组中的任意数量的肢体。
相反，SSE/AVX 寄存器的通道没有进位标志，这意味着必须以不同的方式检测溢出，包括通过比较来检测环绕，这在计算上更加密集。此外，如果在一个肢体中检测到溢出，则必须通过丑陋的洗牌 "upwards" 传播它，然后添加，并且这种添加可能会导致另一次溢出和结转，最多 N-1 N-limb bignum 的次数。然后，一旦总和带来的 bignum 超过 128-bit/256-bits（或超过 128 位 x # 寄存器），无论如何你都必须将它移动到数组中。
因此，将需要很多特殊情况的代码，而且它不会更快（实际上更慢），只是为了添加。想象一下乘法需要什么？还是喘息，分裂？
有可能，但不实用。
正如我在the other answer中所说，AVX/SSE中没有进位标志，因此不可能有效地进行加减法运算。要进行乘法运算，您需要进行大量改组才能在所需位置获得扩大的乘法结果。
如果允许您使用较新的 Haswell/Broadwell 微体系结构，解决方案将是 BMI2 and in ADX. You can read about them here 中的 MULX。
我认为可以有效地使用 SIMD 实现 BigNum，但不是按照您建议的方式。
与其使用 SIMD 寄存器（或 SIMD 寄存器数组）实现单个 BigNum，不如一次处理多个 BigNums。
让我们考虑 128 位加法。让 128 位整数由一对高位和低位 64 位值定义，假设我们要将 128 位整数 (y_low, y_high) 添加到 128 位整数 (x_low, x_high)。对于标量 64 位寄存器，这只需要两条指令
add rax, rdi // x_low += y_low;
adc rdx, rsi // x_high += y_high + (x_low < y_low);
SSE/AVX 的问题，正如其他人所解释的那样，是没有 SIMD 进位标志。必须计算进位标志，然后添加。这需要 64 位无符号比较。 SSE 的唯一现实选择来自 AMD XOP 指令 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
这使用四个指令来添加两对 128 位数字。对于标量 64 位寄存器，这也需要四个指令（两个 add 和两个 adc）。
借助 AVX2，我们可以一次添加四对 128 位数字。但是 XOP 中没有 256 位宽的 64 位无符号指令。相反，我们可以为 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);
sign64 寄存器可以预先计算，所以只需要三个指令。因此用AVX2将4对128位数相加可以用6条指令完成
vpaddq
vpaddq
vpxor
vpxor
vpcmpgtq
vpsubq
而标量寄存器需要八条指令。
AVX512 有一条指令用于进行 64 位无符号比较 vpcmpuq。因此，只用4条指令就可以将8对128位数字相加
vpaddq
vpaddq
vpcmpuq
vpsubq
使用标量寄存器需要 16 条指令来添加八对 128 位数字。
这里是 table 的摘要，其中包含 SIMD 指令（称为 nSIMD）的数量和添加 128- 对（称为 npairs）所需的标量指令（称为 nscalar）的数量位数
nSIMD nscalar npairs
SSE2 + XOP 4 4 2
AVX2 6 8 4
AVX2 + XOP2 4 8 4
AVX-512 4 16 8
请注意，XOP2 尚不存在，我只是推测它可能在某个时候存在。
另请注意，要有效地执行此操作，BigNum 数组需要存储在数组结构数组 (AoSoA) 形式中。例如，使用 l 表示低 64 位，使用 h 表示高 64 位 128 位整数数组存储为这样的结构数组
lhlhlhlhlhlhlhlh
应该使用像这样的 AoSoA 来存储
SSE2: llhhllhhllhhllhh
AVX2: llllhhhhllllhhhh
AVX512: llllllllhhhhhhhh
SSE/AVX 寄存器可以被视为整数或浮点 BigNums。也就是说，人们可能会忽略车道的存在。是否存在一种简单的方法来利用这种观点并将这些寄存器单独或组合用作 BigNums？我之所以问，是因为从我对 BigNum 库的了解来看，它们几乎普遍在数组上而不是 SSE/AVX 寄存器上存储和执行算术运算。便携性？
示例：
假设您将 SSE 寄存器的内容作为键存储在 std::set 中，您可以将这些内容作为 BigNum 进行比较。
从上面的评论中移出
可以这样做，但没有这样做，因为在向量寄存器中实现大数不是特别方便。
对于简单的加法任务，使用 x86 EFLAGS/RFLAGS' 寄存器的进位标志从最低 "limb" 向上传播加法的进位是微不足道的（使用 GMP 术语），并遍历放置在数组中的任意数量的肢体。
相反，SSE/AVX 寄存器的通道没有进位标志，这意味着必须以不同的方式检测溢出，包括通过比较来检测环绕，这在计算上更加密集。此外，如果在一个肢体中检测到溢出，则必须通过丑陋的洗牌 "upwards" 传播它，然后添加，并且这种添加可能会导致另一次溢出和结转，最多 N-1 N-limb bignum 的次数。然后，一旦总和带来的 bignum 超过 128-bit/256-bits（或超过 128 位 x # 寄存器），无论如何你都必须将它移动到数组中。
因此，将需要很多特殊情况的代码，而且它不会更快（实际上更慢），只是为了添加。想象一下乘法需要什么？还是喘息，分裂？
有可能，但不实用。
正如我在the other answer中所说，AVX/SSE中没有进位标志，因此不可能有效地进行加减法运算。要进行乘法运算，您需要进行大量改组才能在所需位置获得扩大的乘法结果。
如果允许您使用较新的 Haswell/Broadwell 微体系结构，解决方案将是 BMI2 and
我认为可以有效地使用 SIMD 实现 BigNum，但不是按照您建议的方式。
与其使用 SIMD 寄存器（或 SIMD 寄存器数组）实现单个 BigNum，不如一次处理多个 BigNums。
让我们考虑 128 位加法。让 128 位整数由一对高位和低位 64 位值定义，假设我们要将 128 位整数 (y_low, y_high) 添加到 128 位整数 (x_low, x_high)。对于标量 64 位寄存器，这只需要两条指令
add rax, rdi // x_low += y_low;
adc rdx, rsi // x_high += y_high + (x_low < y_low);
SSE/AVX 的问题，正如其他人所解释的那样，是没有 SIMD 进位标志。必须计算进位标志，然后添加。这需要 64 位无符号比较。 SSE 的唯一现实选择来自 AMD XOP 指令 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
这使用四个指令来添加两对 128 位数字。对于标量 64 位寄存器，这也需要四个指令（两个 add 和两个 adc）。
借助 AVX2，我们可以一次添加四对 128 位数字。但是 XOP 中没有 256 位宽的 64 位无符号指令。相反，我们可以为 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);
sign64 寄存器可以预先计算，所以只需要三个指令。因此用AVX2将4对128位数相加可以用6条指令完成
vpaddq
vpaddq
vpxor
vpxor
vpcmpgtq
vpsubq
而标量寄存器需要八条指令。
AVX512 有一条指令用于进行 64 位无符号比较 vpcmpuq。因此，只用4条指令就可以将8对128位数字相加
vpaddq
vpaddq
vpcmpuq
vpsubq
使用标量寄存器需要 16 条指令来添加八对 128 位数字。
这里是 table 的摘要，其中包含 SIMD 指令（称为 nSIMD）的数量和添加 128- 对（称为 npairs）所需的标量指令（称为 nscalar）的数量位数
nSIMD nscalar npairs
SSE2 + XOP 4 4 2
AVX2 6 8 4
AVX2 + XOP2 4 8 4
AVX-512 4 16 8
请注意，XOP2 尚不存在，我只是推测它可能在某个时候存在。
另请注意，要有效地执行此操作，BigNum 数组需要存储在数组结构数组 (AoSoA) 形式中。例如，使用 l 表示低 64 位，使用 h 表示高 64 位 128 位整数数组存储为这样的结构数组
lhlhlhlhlhlhlhlh
应该使用像这样的 AoSoA 来存储
SSE2: llhhllhhllhhllhh
AVX2: llllhhhhllllhhhh
AVX512: llllllllhhhhhhhh