为什么并行SIMD/SSE/AVX需要置换？

Question

从我的另一个问题"使用SIMD AVX SSE进行树遍历"我得到了这个代码,我试图进行基准测试.我之前没有做任何关于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以及在这种情况下"打包/解包"意味着什么？我会感谢您提供有关它的任何资源 - 谷歌aint对这个非常特殊的主题有所帮助.

Answer 1

英特尔的指令集手册对于您学习SIMD非常宝贵.它详细解释了每条指令的作用.

SSE/AVX中的"打包"基本上是两个寄存器的向下和合并.PACKSSDW在一个寄存器中将来自两个寄存器的32位有符号整数打包成16位有符号整数,并使这些值饱和(因此值<-32768将设置为-32768,而> 32767将设置为32767)

置换是一种重新排序寄存器中值的方法.掩码寄存器中的每个值都指定源的索引.这是必需的,因为AVX256稍微"作弊"并将其大部分混音指令处理为两个128位"通道".

128位版本的PACKSSDW执行此操作:

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位运算的"混合"结果就会按顺序排列:

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你需要分支时有一个定义的寄存器输出.)