用不同的值SIMD移动4个整数

Question

SSE没有提供一种以可变数量移动打包整数的方法(我可以使用任何AVX和更旧的指令).你只能做统一的轮班.我试图为向量中的每个整数实现的结果是这个.

i[0] = i[0] & 0b111111;
i[1] = (i[1]>>6) & 0b111111;
i[2] = (i[2]>>12) & 0b111111;
i[3] = (i[3]>>18) & 0b111111;

本质上是尝试在每个整数中隔离不同的6位组.

那么什么是最佳解决方案？

我想到的事情:你可以模拟一个变量右移,左移和左移一致.我想过将打包的整数乘以不同的量(因此模拟左移).然后结果,你可以做一个统一的右移得到答案.这个问题我会用乘法的具体运会_mm_mullo_epi32,其中有令人失望的等待时间(10个循环的Haswell),并给予我的程序那就要等待结果造成这个特殊的结果是下一个指令的依赖.总的来说,我认为这种方法只比蛮力方法快一点,后者是解包,使用标量指令进行移位,然后重新打包向量,我认为这需要大约20个周期.

Answer 1

如果AVX2可用,则只需要一条有效的指令.例如__m128i _mm_srlv_epi32 (__m128i a, __m128i count)(vpsrlvd)和256位版本.左对齐,右对齐和右对齐可以通过相应的计数元素对32位和64位元素进行可变移位.(64位元素大小不能使用算术右移.)

AVX512BW增加了16位可变频率.

在没有AVX2的情况下模拟它:

这部分依赖链是什么类型的？你可以展开和交错,这样两个向量一次在飞行中吗？并行的两个长dep链比一个long dep链要好得多,如果它太长以至于无序窗口在下一个循环迭代中看不到下一个dep链.

可能值得制作一个单独的AVX2版本的功能,用于Haswell和后来的CPU(你可以使用变速).如果这样做,您的函数将只在最有效的CPU上使用vpmultishiftqb(pmulld).(即你mullo_epi32在AVX2 CPU上避免使用SSE4.1 ,因为事实证明那些CPU使得该指令变慢了.)

mullo_epi32 看起来我们可以做到最好的吞吐量和融合域uop计数,即使在Haswell.

在SnB/IvB上,它是矢量整数乘法单元的单个uop,整个函数只有2 uops/6个周期延迟/每1c吞吐量一个.(这比我使用shift/blend更糟糕,所以你只想使用pmulld吞吐量/代码大小完全重要,并且你不会仅仅因为延迟而受到瓶颈.例如,在展开之后.)

如果您的移位计数是常数,并且您的寄存器顶部有备用位,则可以乘以2的幂,然后使用固定的右移. 将__m128i中的每个DW向右移动不同的量.敲掉高位对于你的位字段提取不是一个问题,因为你正在进行AND运算以保持只有低位.

// See the godbolt link below for a version of this with more comments
// SnB/IvB: 6c latency, 2 fused-domain uops.
__m128i isolate_successive_6bits_mul (__m128i input)
{
  // We can avoid the AND if we shift the elements all the way to the left to knock off the high garbage bits.
  // 32 - 6 - 18 = 8 extra bits to left shift
    __m128i mul_constant = _mm_set_epi32(1<<(0+8), 1<<(6+8), 1<<(12+8), 1<<(18+8));
    __m128i left_vshift = _mm_mullo_epi32(input, mul_constant);
    __m128i rightshifted = _mm_srli_epi32(left_vshift, (18+8));
    return rightshifted;
}

一种巧妙的混合方式:

(遗憾的是,我们没有AVX2可pmulld用于在任何端口上运行的高效双字混合. vpblendd仅限于Intel CPU上的端口5. pblendw可能有利于吞吐量(在任何端口上运行)但可能在整数指令之间引入旁路延迟.)

移动和混合使每个元素以正确的总移位数结束.

在将所有内容组合到一个向量之后,对低6位进行AND屏蔽.

与英特尔CPU上的暴力方式(见下文)相同的延迟,以及更好的吞吐量(因为更少的微量).只有两个立即混合使用port5很不错.(AVX2 blendps可以在任何端口上运行,但我们只是使用它vpblendd.)

// seems to be optimal for Intel CPUs.
__m128i isolate_successive_6bits (__m128i input)
{ // input =   [ D      C      B     A ]
  // output =  [ D>>18  C>>12  B>>6  A ] & set1(0b111111)
    __m128i right12 = _mm_srli_epi32(input, 12);
    __m128i merged = _mm_blend_epi16(input, right12, 0xF0);  // copy upper half, like `movhps` (but don't use that because of extra bypass delay)
    // merged = [ D>>12  C>>12  B>>0  A>>0 ]
    __m128i right6 = _mm_srli_epi32(merged, 6);
    merged = _mm_blend_epi16(merged, right6, 0b11001100);    // blend in the odd elements
    // merged = [ D>>(12+6)  C>>12  B>>(0+6)  A>>0 ]        
    return _mm_and_si128(merged, _mm_set1_epi32(0b111111));  // keep only the low 6 bits
}

我把两个版本放在Godbolt编译器资源管理器上.

这个版本只有5 uops,用gcc 5.3编译vpsrlvd:

    # input in xmm0, result in xmm0
isolate_successive_6bits:
    vpsrld          xmm1, xmm0, 12                # starts on cycle 0, result ready for the start of cycle 1
    vpblendw        xmm0, xmm0, xmm1, 240         # cycle 1
    vpsrld          xmm1, xmm0, 6                 # cycle 2
    vpblendw        xmm0, xmm0, xmm1, 204         # cycle 3
    vpand           xmm0, xmm0, XMMWORD PTR .LC0[rip] # cycle 4, result ready on cycle 5
    ret

每条指令都依赖于前一条指令,因此它具有5c延迟.SnB/IvB/HSW/BDW CPU只有一个移位端口,因此它们无法利用更强力版本中的并行性(可以使用不同的移位计数进行三次移位).Skylake可以,但随后两个混合周期吃掉了改进.

"蛮力"方式:

三个移位三个不同的移位计数,并使用三个立即混合(-O3 -march=ivybridge)将四个向量组合成一个具有每个所需元素的向量.

// same latency as the previous version on Skylake
// slower on previous Intel SnB-family CPUs.
isolate_successive_6bits_parallel:
    vpsrld          xmm1, xmm0, 6            # cycle 0.   SKL: c0
    vpsrld          xmm2, xmm0, 12           # cycle 1 (resource conflict on pre-Skylake).  SKL: c0
    vpblendw        xmm1, xmm0, xmm1, 12     # cycle 2 (input dep).  SKL: c1
    vpsrld          xmm3, xmm0, 18           # cycle 2.  SKL: c1
    vpblendw        xmm0, xmm2, xmm3, 192    # cycle 3 (input dep). SKL: c2
    vpblendw        xmm0, xmm1, xmm0, 240    # cycle 4 (input dep). SKL: c3
    vpand           xmm0, xmm0, XMMWORD PTR .LC0[rip]  # cycle 5 (input dep). SKL: c4.
    ret

使用线性依赖关系链而不是树进行合并意味着合并可以在最后一个转换结果准备好后立即完成:

isolate_successive_6bits_parallel2:
    vpsrld          xmm1, xmm0, 6          # c0.  SKL:c0
    vpsrld          xmm2, xmm0, 12         # c1.  SKL:c0
    vpblendw        xmm1, xmm0, xmm1, 12   # c2.  SKL:c1
    vpblendw        xmm1, xmm1, xmm2, 48   # c3.  SKL:c2
    vpsrld          xmm0, xmm0, 18         # c2.  SKL:c1
    vpblendw        xmm0, xmm1, xmm0, 192  # c4.  SKL:c3 (dep on xmm1)
    vpand           xmm0, xmm0, XMMWORD PTR .LC0[rip] # c5.  SKL:c4
    ret

嗯,不,没有帮助.SnB到BDW或SKL的延迟没有增加.第一次合并只能在一次移位后发生,因为未移位的输入是我们对一个元素所需要的.如果元素0需要非零移位计数,这种方式对于SKL之前将具有优势,并且可能是SKL的劣势.