将 4 个整数右移不同的值 SIMD
Shifting 4 integers right by different values SIMD
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，它具有令人失望的延迟（haswell 为 10 个周期），并且给定我的程序它必须等待结果，因为这个特定结果是下一条指令的依赖性。总的来说，我认为这种方法只会比蛮力法快一点，后者是解包，使用标量指令移位，然后重新打包向量，我认为这需要大约 20 个周期。
如果 AVX2 可用，这只需要一条高效指令。例如__m128i _mm_srlv_epi32 (__m128i a, __m128i count) (vpsrlvd) 和 256 位版本。 32 位和 64 位元素按相应计数元素的可变移位可用于左、右算术和右逻辑。 （算术右移不适用于 64 位元素大小。）
AVX512BW 添加 16 位可变移位.
AVX512VBMI 有 vpmultishiftqb bitfield-extract within each qword. There's an example of using it for 。为此，您可以在它后面加上一个 AND 掩码，因为它以 8 位块的形式获取数据（但从不必与字节边界对齐的源位置）。
在没有 AVX2 的情况下模拟它：
这部分属于哪种依赖链？你能展开并交错，让两个向量同时飞行吗？两个平行的长 dep 链比一个长 dep 链要好得多，如果它太长以至于乱序 window 在下一个循环迭代中看不到下一个 dep 链。
可能值得为您的函数制作一个单独的 AVX2 版本，以便在 Haswell 和更高版本的 CPU 上使用（您可以在其中使用 a variable-shift）。如果这样做，您的函数将仅在效率最高的 CPU 上使用 pmulld (mullo_epi32)。 （即您避免在 AVX2 CPU 上使用 SSE4.1 mullo_epi32，因为事实证明这些 CPU 使该指令变慢了。）
pmulld 看起来是我们在吞吐量和融合域 uop 计数方面所能做的最好的事情，即使在 Haswell 上也是如此。
在 SnB/IvB 上，它是向量整数乘法单元的单个微指令，整个函数仅为 2 微指令/6 周期延迟/每 1c 吞吐量一个。 （这比我用 shift/blend 管理的更糟糕，所以如果 throughput/code-size 很重要，你只想使用 pmulld，而且你不会纯粹因为延迟而成为瓶颈。例如展开后.)
如果你的移位计数是常量，并且你的寄存器顶部有空闲位，你可以乘以 2 的幂，然后使用固定的右移 . 。删除高位对于您的位域提取不是问题，因为无论如何您都只保留低位。
// 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 vpblendd 可以在任何端口上 运行 进行高效的双字混合。pblendw 仅限于英特尔 CPU 上的端口 5。blendps 可能对吞吐量有好处（运行s 在任何端口上）但会在整数指令之间引入旁路延迟。）
移动并混合，使每个元素最终都具有正确的总移动计数。
将所有内容组合成一个向量后，AND 屏蔽低 6 位。
与 Intel CPU 上的暴力方式（见下文）相同的延迟，以及更好的吞吐量（因为更少的 uops）。只有两个直接混合绑定端口 5 很好。 （AVX2 vpblendd 可以 运行 在任何端口上，但我们只使用 vpsrlvd。）
// 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
}
我放both versions on the Godbolt compiler explorer.
这个版本只有5 uops，用gcc 5.3编译-O3 -march=ivybridge:
# 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 可以，但是之后的两个混合周期会吃掉改进。
"brute force"方式:
对三个不同的移位计数进行三次移位，并使用三个立即混合 (pblendw) 将四个向量组合成一个包含每个所需元素的向量。
// 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 需要一个非零移位计数，这种方式对 pre-SKL 有利，对 SKL 可能不利。
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，它具有令人失望的延迟（haswell 为 10 个周期），并且给定我的程序它必须等待结果，因为这个特定结果是下一条指令的依赖性。总的来说，我认为这种方法只会比蛮力法快一点，后者是解包，使用标量指令移位，然后重新打包向量，我认为这需要大约 20 个周期。
如果 AVX2 可用，这只需要一条高效指令。例如__m128i _mm_srlv_epi32 (__m128i a, __m128i count) (vpsrlvd) 和 256 位版本。 32 位和 64 位元素按相应计数元素的可变移位可用于左、右算术和右逻辑。 （算术右移不适用于 64 位元素大小。）
AVX512BW 添加 16 位可变移位.
AVX512VBMI 有 vpmultishiftqb bitfield-extract within each qword. There's an example of using it for
在没有 AVX2 的情况下模拟它：
这部分属于哪种依赖链？你能展开并交错，让两个向量同时飞行吗？两个平行的长 dep 链比一个长 dep 链要好得多，如果它太长以至于乱序 window 在下一个循环迭代中看不到下一个 dep 链。
可能值得为您的函数制作一个单独的 AVX2 版本，以便在 Haswell 和更高版本的 CPU 上使用（您可以在其中使用 a variable-shift）。如果这样做，您的函数将仅在效率最高的 CPU 上使用 pmulld (mullo_epi32)。 （即您避免在 AVX2 CPU 上使用 SSE4.1 mullo_epi32，因为事实证明这些 CPU 使该指令变慢了。）
pmulld 看起来是我们在吞吐量和融合域 uop 计数方面所能做的最好的事情，即使在 Haswell 上也是如此。
在 SnB/IvB 上，它是向量整数乘法单元的单个微指令，整个函数仅为 2 微指令/6 周期延迟/每 1c 吞吐量一个。 （这比我用 shift/blend 管理的更糟糕，所以如果 throughput/code-size 很重要，你只想使用 pmulld，而且你不会纯粹因为延迟而成为瓶颈。例如展开后.)
如果你的移位计数是常量，并且你的寄存器顶部有空闲位，你可以乘以 2 的幂，然后使用固定的右移 .
// 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 vpblendd 可以在任何端口上 运行 进行高效的双字混合。pblendw 仅限于英特尔 CPU 上的端口 5。blendps 可能对吞吐量有好处（运行s 在任何端口上）但会在整数指令之间引入旁路延迟。）
移动并混合，使每个元素最终都具有正确的总移动计数。
将所有内容组合成一个向量后，AND 屏蔽低 6 位。
与 Intel CPU 上的暴力方式（见下文）相同的延迟，以及更好的吞吐量（因为更少的 uops）。只有两个直接混合绑定端口 5 很好。 （AVX2 vpblendd 可以 运行 在任何端口上，但我们只使用 vpsrlvd。）
// 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
}
我放both versions on the Godbolt compiler explorer.
这个版本只有5 uops，用gcc 5.3编译-O3 -march=ivybridge:
# 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 可以，但是之后的两个混合周期会吃掉改进。
"brute force"方式:
对三个不同的移位计数进行三次移位，并使用三个立即混合 (pblendw) 将四个向量组合成一个包含每个所需元素的向量。
// 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 需要一个非零移位计数，这种方式对 pre-SKL 有利，对 SKL 可能不利。