使用AVX内在函数计算允许标量值为0,1和2的向量的内积

Question

我正在做成两万维的内在产品,成千上万.值只能是0,1或2.因此可以将它们存储为字符.如果要在具有avx标志的CPU上进行矢量化计算,我预计它会快〜32倍.但问题是乘法会自动将字符转换为整数,即4个字节.因此,可以获得仅速度的最大8倍.可以达到32倍的速度吗？

顺便说一句,我使用的是Linux(Fedora 22迄今为止)和g ++ 5.1.

Answer 1

假设你有AVX2(不仅仅是AVX,它只是浮​​点数),那么你可以使用vpmaddubsw内在的指令:

__m256i _mm256_maddubs_epi16 (__m256i a, __m256i b)

这将执行8位x 8位乘法(带符号x无符号,但这对您的情况无关紧要),然后添加相邻项对,以得到16位结果.[1]这有效地在一条指令中提供32 x 8 x 8位的乘法.

如果您没有AVX2,则可以使用128位SSE版本(_mm_maddubs_epi16)在一条指令中获得16 xx 8 x 8位的乘法.

请注意,对16位项进行水平求和可能需要多个指令,但由于输入范围非常小,因此您只需要相对不频繁地执行此水平求和.一种可能的方法(对于SSE):

v = _mm_madd_epi16(v, _mm_set1_epi16(1));       // unpack/sum 16 -> 32
v = _mm_add_epi32(v, _mm_srli_si128(v, 8));     // shift and add 32 bit terms
v = _mm_add_epi32(v, _mm_srli_si128(v, 4));
sum = _mm_cvtsi128_si32(v);                     // extract sum as scalar

上面的AVX2实现留给读者练习.

Answer 2

看起来AVX指令集没有8位乘法,只有加法.英特尔内部指南不包含任何以8位开头的操作_mm_mul*.(编辑:实际上有一个8位乘法,但它有一个误导性的名称 - 见@PaulR的回答)

但是,还有另一种方法.由于唯一允许的值为0,1和2,并且您正在计算内积,因此可以使用位运算而不是乘法运算.

在第一个向量中A,使用以下编码:

0 = 0b00000000 = 0x00
1 = 0b00010011 = 0x13
2 = 0b00001111 = 0x0F

在第二个向量中B,使用以下编码:

0 = 0b00000000 = 0x00
1 = 0b00011100 = 0x1C
2 = 0b00001111 = 0x0F

现在计算popcount(A & B).AND-ing将使相应的8位单元设置为0,1,2或4位,popcount并将它们加在一起.您可以为每5位整数打包一个值,因此如果您可以使用256位整数,则可以获得高51倍的吞吐量.