从我关于"Using SIMD AVX SSE for tree traversal" ive的另一个问题中，我得到了这个试图进行基准测试的代码。之前我没有对SIMD做任何事情，所以我对这种排列方式有点陌生。首先，让我们看下面的代码:
__m256i const perm_mask = _mm256_set_epi32(7, 6, 3, 2, 5, 4, 1, 0);
// compare the two halves of the cache line.
__m256i cmp1 = _mm256_load_si256(&node->m256[0]);
__m256i cmp2 = _mm256_load_si256(&node->m256[1]);
cmp1 = _mm256_cmpgt_epi32(cmp1, value); // PCMPGTD
cmp2 = _mm256_cmpgt_epi32(cmp2, value); // PCMPGTD
// merge the comparisons back together.
//
// a permute is required to get the pack results back into order
// because AVX-256 introduced that unfortunate two-lane interleave.
//
// alternately, you could pre-process your data to remove the need
// for the permute.
__m256i cmp = _mm256_packs_epi32(cmp1, cmp2); // PACKSSDW
cmp = _mm256_permutevar8x32_epi32(cmp, perm_mask); // PERMD
// finally create a move mask and count trailing
// zeroes to get an index to the next node.
unsigned mask = _mm256_movemask_epi8(cmp); // PMOVMSKB
return _tzcnt_u32(mask) / 2; // TZCNT
作者Cory Nelson试图用评论解释它。但是，我并没有真正了解这种排列的工作方式以及为什么它最终会从结果向量中“提取”出所需的信息。
有人可以帮助我了解一下此代码中如何使用TZCNT的排列，移动掩码以及在这种情况下“打包/拆包”的含义吗？对于您可能拥有的任何资源，我将不胜感激-谷歌对这个非常特殊的主题很有帮助。
最佳答案
英特尔的instruction set manuals对您学习SIMD至关重要。它详细解释了这些指令中的每一个。
SSE/AVX中的“打包”基本上是两个寄存器的向下转换和合并。 PACKSSDW将两个寄存器中的32位有符号整数打包为一个寄存器中的16位有符号整数，并使值饱和(因此， 32767的值将设置为32767)
置换是一种对寄存器中的值进行重新排序的方法。掩码寄存器中的每个值都指定了到源的索引。这是必需的，因为AVX256稍有“欺骗”，并将其大多数混合指令作为两个128位“ channel ”来处理。
PACKSSDW的128位版本执行以下操作:
r0 := SignedSaturate(a0)
r1 := SignedSaturate(a1)
r2 := SignedSaturate(a2)
r3 := SignedSaturate(a3)
r4 := SignedSaturate(b0)
r5 := SignedSaturate(b1)
r6 := SignedSaturate(b2)
r7 := SignedSaturate(b3)
您希望256位版本保持相同的自然顺序，所有“A”在前，而“B”在第二位，如下所示:
r0 := SignedSaturate(a0)
r1 := SignedSaturate(a1)
r2 := SignedSaturate(a2)
r3 := SignedSaturate(a3)
r4 := SignedSaturate(a4)
r5 := SignedSaturate(a5)
r6 := SignedSaturate(a6)
r7 := SignedSaturate(a7)
r8 := SignedSaturate(b0)
r9 := SignedSaturate(b1)
r10 := SignedSaturate(b2)
r11 := SignedSaturate(b3)
r12 := SignedSaturate(b4)
r13 := SignedSaturate(b5)
r14 := SignedSaturate(b6)
r15 := SignedSaturate(b7)
但是，实际上它是做什么的:
r0 := SignedSaturate(a0) // lane one, the low 128 bits.
r1 := SignedSaturate(a1)
r2 := SignedSaturate(a2)
r3 := SignedSaturate(a3)
r4 := SignedSaturate(b0)
r5 := SignedSaturate(b1)
r6 := SignedSaturate(b2)
r7 := SignedSaturate(b3)
r8 := SignedSaturate(a4) // lane two, the high 128 bits.
r9 := SignedSaturate(a5)
r10 := SignedSaturate(a6)
r11 := SignedSaturate(a7)
r12 := SignedSaturate(b4)
r13 := SignedSaturate(b5)
r14 := SignedSaturate(b6)
r15 := SignedSaturate(b7)
结果是，当比较整齐排列的值的数组时，128位版本将它们保持有序，而256位版本将它们混合在一起。置换使它们恢复原状。
正如我在文章中提到的那样，您可以通过预处理节点的数组使其具有逆函数来摆脱此代码中的置换，从而使256位op的“混合”结果按顺序排列:
void preprocess_avx2(bnode* const node)
{
__m256i const perm_mask = _mm256_set_epi32(3, 2, 1, 0, 7, 6, 5, 4);
__m256i *const middle = (__m256i*)&node->i32[4];
__m256i x = _mm256_loadu_si256(middle);
x = _mm256_permutevar8x32_epi32(x, perm_mask);
_mm256_storeu_si256(middle, x);
}
排序很重要，因为下一步会做什么。
比较适用于16个32位值，但所有值都为0x0000或0xFFFF。实际上，您只有16位信息-每个值均处于关闭或打开状态。
PMOVMSKB将输入视为32个8字节值，并将每个的高位(由于所有位都相同，所以我们只需要它们)打包成32位int。TZCNT对那个int中的尾随零位进行计数，这为具有设置位的第一个位置提供索引:该SIMD寄存器中第一个字节的索引，大于。(有趣的是:
TZCNT是对现有BSF指令的Haswell改进，实际上与它共享一种编码。唯一的区别是TZCNT在其输入为0时具有定义的寄存器输出-您需要分支到BSF )关于permutation - 为什么在并行SIMD/SSE/AVX中需要置换？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20918987/