基于AVX-2的32-1024位定点向量运算

Question

对于mandelbrot生成器，我希望在放大时使用从32到1024位的定点算术。

现在，普通的SSE或AVX是没有帮助的，因为缺少进位的加法，做正常的整数运算更快。但在我的例子中，我有数百万个像素都需要计算。所以我有一个巨大的值向量，所有这些值都需要反复使用相同的迭代公式超过一百万次。

所以我不是在单个值上做定点加/减/mul，而是在巨大的向量上做。我希望对于这样的向量操作，尽管缺少本机的进位加法，AVX/AVX2仍然可以用来提高性能。

任何人都知道一个向量定点算术库或一些示例代码如何在AVX/AVX2上进行进位模拟加法。

Answer 1

FP扩展精度在每个时钟周期提供更多位(因为在英特尔CPU上，double FMA吞吐量为2个/时钟，而在英特尔CPU上为32x32=>64位，为1或2个/时钟)；请考虑使用Prime95对FMA使用的相同技巧进行整数计算。如果小心，可以使用FPU硬件进行精确的整数运算。

对于你的实际问题:因为你想并行地对多个像素做同样的事情，所以你可能想在不同的向量中的相应元素之间进行进位，所以一个__m256i包含4个单独的大整数的64位块，而不是4个相同整数的块。

对于使用此策略的非常宽的整数，寄存器压力是一个问题。也许您可以通过在比较结果上使用vpmovmskb在每次相加后生成进位输出，来有效地转移到没有超过块的第四个或第六个向量的进位传播。无符号加法具有a+b < a的进位(无符号比较)

但是AVX2只有带符号的整数比较(对于大于)，没有无符号的。使用carry-in时，可以使用b=carry_in=0或b=0xFFF实现(a+b+c_in) == a ...和carry_in=1，所以生成进位输出并不简单。

要解决这两个问题，请考虑使用手动包装为60位或62位的块，这样就可以保证它们是有符号正的，因此加法进位显示在完整的64位元素的高位中。(您可以使用vpsrlq ymm, 62将其提取出来，以便添加到下一个更高的块的向量中。)

甚至63位的块也可以在这里工作，因此进位出现在最上面的位，vmovmskpd可以检查是否有任何元素产生进位。否则，vptest可以使用正确的掩码来做到这一点。

这是一种巧妙的头脑风暴答案；我没有任何计划将其扩展为详细的答案。如果任何人想要在此基础上编写实际的代码，请发布您自己的答案，以便我们可以对其进行投票(如果它被证明是一个有用的想法)。

Answer 2

为了方便起见，您可以通过查看输入和输出值的高位来提取加法的进位位，而不是声称这实际上是有用的。

unsigned result = a + b + last_carry;  // add a, b and (optionally last carry)

unsigned carry = (a & b)  // carry if both a AND b have the upper bit set
                 |        // OR
                 ((a ^ b) // upper bits of a and b are different AND
                  & ~r);  // AND upper bit of the result is not set
carry >>= sizeof(unsigned)*8 - 1; // shift the upper bit to the lower bit

对于SSE2/AVX2，这可以通过两次加法、4次逻辑运算和一次移位来实现，但适用于任意(支持)整数大小(uint8、uint16、uint32、uint64)。使用AVX2，你需要7uops才能获得4个64位进位进位和进位输出的加法。

特别是因为倍增64x64-->128也是不可能的(但需要4个32x32-->64产品--以及一些添加或3个32x32-->64产品，甚至更多的添加，以及特殊情况处理)，您可能不会比使用mul和adc (可能除非寄存器压力是您的瓶颈)的效率更高

正如Peter和Mystical建议的那样，使用较小的肢体(仍然存储在64位中)可能是有益的。一方面，通过一些技巧，您可以对52x52-->104产品使用FMA。而且，在需要携带前一个分支的高位之前，您实际上可以添加64-k位的2^k-1个数字。