在SSE/AVX中选择唯一/重复数据删除

Question

问题
是否有任何计算上可行的方法来使用x86 SIMD指令对一组整数进行寄存器重复数据删除？

示例
我们有一个4元组寄存器R1 = {3,9,2,9},并希望获得寄存器R2 = {3,9,2,NULL}.

限制
稳定性.保存输入顺序没有意义.

输出.但是,任何删除的值/ NULL必须位于寄存器的开头和/或末尾:

• {null,1,2,3} - 好的
• {1,2,null,null} - 好的
• {null,2,null,null} - 好的
• {null,2,null,1} - 订单无效
• {null,null,null,null} - 输出无效

如果知道产生一种特定的输出格式,这显然是一个奖励.请假设NULL有效地表示0(零).

一般性.必须能够容忍没有重复项,并且在这种情况下产生相当于输入寄存器的输出.

指令集.我正在寻找以下任何或所有解决方案:SSE2-SSSE3; SSE4.x; AVX,AVX2

Answer 1

解

建议的解决方案始终将所有独特元素放在输出的下半部分,按第一次出现的顺序排列.较高的部分归零.通过修改LUT很容易改变放置策略:将元素放到较高的部分,或者颠倒它们的顺序.

static __m128i *const lookup_hash = (__m128i*) &lookup_hash_chars[0][0];
static inline __m128i deduplicate4_ssse3(__m128i abcd) {
    __m128i bcda = _mm_shuffle_epi32(abcd, _MM_SHUFFLE(0, 3, 2, 1));
    __m128i cdab = _mm_shuffle_epi32(abcd, _MM_SHUFFLE(1, 0, 3, 2));
    uint32_t mask1 = _mm_movemask_epi8(_mm_cmpeq_epi32(abcd, bcda));
    uint32_t mask2 = _mm_movemask_epi8(_mm_cmpeq_epi32(abcd, cdab));
    uint32_t maskFull = (mask2 << 16U) + mask1;
    //Note: minimal perfect hash function here
    uint32_t lutIndex = (maskFull * 0X0044CCCEU) >> 26U;
    __m128i shuf = lookup_hash[lutIndex];
    return _mm_shuffle_epi8(abcd, shuf);
}

完整代码(带测试)可在此处获得.

我还通过对5个比较器的网络进行排序,然后对连续元素进行序列比较,实现了一个简单的标量解决方案.我在两个处理器上使用MSVC2013:Core 2 E4700(Allendale,2.6 Ghz)和Core i7-3770(Ivy Bridge,3.4 Ghz).以下是2 ^ 29个电话的时间秒数:

// Allendale
SSE:    time =  3.340    // ~16.2 cycles (per call)
Scalar: time = 17.218    // ~83.4 cycles (per call)
// Ivy Bridge
SSE:    time =  1.203    // ~ 7.6 cycles (per call)
Scalar: time = 11.673    // ~73.9 cycles (per call)

讨论

请注意,结果必须包含两种类型的元素:

1. 输入向量中的元素,
2. 零.

但是,必要的改组掩码是在运行时以非常复杂的方式确定的.所有SSE指令只能处理立即(即编译时常量)混洗掩码,除了一个.它是_mm_shuffle_epi8SSSE3的内在特征.为了快速获得混洗掩码,所有掩码都存储在查找表中,由一些位掩码或散列索引.

为了获得给定输入向量的混洗掩码,有必要收集关于其中相等元素的足够信息.请注意,完全足以知道哪些元素对相等,以确定如何对它们进行重复数据删除.如果我们想要对它们进行额外排序,那么我们还需要知道不同元素如何相互比较,这会增加信息量,并随后查找表.这就是为什么我会在没有排序的情况下显示重复数据删除的原因.

所以我们在XMM寄存器中有四个32位元素.它们总共构成六对.由于我们一次只能比较四个元素,因此我们至少需要进行两次比较.实际上,很容易进行两次XMM比较,因此每对元素至少进行一次比较.之后,我们可以通过使用_mm_movemask_epi8它们并将它们连接成一个32位整数来提取16位比特掩码.注意,每个4位块肯定包含相同的位,并且最后两个4位块不是必需的(它们对应于过度比较).

理想情况下,我们需要从这个位掩码中提取恰好位于编译时已知位置的6位.使用_pext_u32BMI2指令集可以很容易地实现它.结果,我们有一个包含6位的[0..63]范围内的整数,每个位显示相应的元素对是否相等.然后我们从预先计算的64条目查找表中加载一个shuffling掩码,然后使用输入向量进行混洗_mm_shuffle_epi8.

不幸的是,BMI指令是相当新的(Haswell和更高版本),我没有它们=)为了摆脱它,我们可以尝试为所有64个有效位掩码创建一个非常简单和快速完美的散列函数(召回该位掩码是32位).对于类中的散列函数,f(x) = (a * x) >> (32-b)通常可以构造一个相当小的完美散列,具有2x或3x内存开销.由于我们的情况很特殊,因此可以构造一个最小的完美散列函数,以便查找表具有最少的64个条目(即大小= 1 KB).

对于8个元素(例如XMM寄存器中的16位整数),相同的算法是不可行的,因为有28对元素,这意味着查找表必须包含至少2 ^ 28个条目.

对YMM寄存器中的64位元素使用这种方法也存在问题._mm256_shuffle_epi8内在没有帮助,因为它只是执行两个独立的128位shuffle(从不跨越通道)._mm256_permutevar8x32_epi32内部执行32位块的任意改组,但它不能插入零.为了使用它,您还必须在LUT中存储多个独特元素.然后你必须手动将零写入寄存器的较高部分.

更新:删除哈希/ BMI

我已经意识到使用BMI2进行位提取或完美散列函数不是必需的,我们可以简单地_mm_movemask_ps用来提取32位掩码.这种方法可能会遇到轻微的延迟问题,因为我们混合了INT和FP计算,但它在实践中运行得更快.

static __m128i *const lookup_direct_offset = lookup_direct - 0xC0U;
static inline __m128i deduplicate4_ssse3_direct(__m128i abcd) {
    __m128i bcda = _mm_shuffle_epi32(abcd, _MM_SHUFFLE(0, 3, 2, 1));
    __m128i cdcd = _mm_shuffle_epi32(abcd, _MM_SHUFFLE(3, 2, 3, 2));
    uint32_t mask1 = _mm_movemask_ps(_mm_castsi128_ps(_mm_cmpeq_epi32(abcd, bcda)));
    uint32_t mask2 = _mm_movemask_ps(_mm_castsi128_ps(_mm_cmpeq_epi32(abcd, cdcd)));
    uint32_t maskFull = 16U * mask2 + mask1;
    //Note: use index directly
    uint32_t lutIndex = maskFull;
    __m128i shuf = lookup_direct_offset[lutIndex];
    return _mm_shuffle_epi8(abcd, shuf);
}

将完整的代码太更新.这会导致性能略有改善:

// Ivy Bridge
new: Time = 1.038   (782827520)    // ~ 6.6 cycles (per call)
old: Time = 1.169   (782827520)    // ~ 7.4 cycles (per call)

Answer 2

朴素的解决方案

基于 Max() 操作的粗略伪代码。评论跟踪第一次迭代的数据。

A = RIN //{3, 9, 2, 9}

For i = 0 .. 3:

  B = Rotate(A, 1) //{9, 2, 9, 3}
  C = Rotate(A, 2) //{2, 9, 3, 9}
  D = Rotate(A, 3) //{9, 3, 9, 2}

  RMAX = Max(A,B) //{9, 9, 9, 9}
  RMAX = Max(RMAX, C) //{9, 9, 9, 9}
  RMAX = Max(RMAX, D) //{9, 9, 9, 9}

  ROUT[i] = RMAX[0] //ROUT = {9, null, null, null}

  TMP  = A
  MASK = Equality(RMAX, TMP) //MASK = {0, 1, 0, 1}
  MASK = Invert(MASK) //MASK = {1, 0, 1, 0}
  Clear(A)
  A = MoveMasked(TMP, MASK) //A = {3, null, 2, null}

一些想法：

A = RIN //{3, 9, 2, 9}

B = Rotate(A, 1) //{9, 2, 9, 3}
C = Rotate(A, 2) //{2, 9, 3, 9}
D = Rotate(A, 3) //{9, 3, 9, 2}

maskA = cmpeq(A,B) //{0,  0,  0,  0}
maskB = cmpeq(A,C) //{0, -1,  0, -1}
maskC = cmpeq(A,D) //{0,  0,  0,  0}

indexA = horSum( { 1,2,4,8 } * maskA ) // 0
indexB = horSum( { 1,2,4,8 } * maskB ) // 10
indexC = horSum( { 1,2,4,8 } * maskC ) // 0

// The problem is this function here
// Of the 4096 possible indexABC only a subset will occur
// Based on an enumeration of all possible indexes a pattern
// for an lookup table could possibly be found
shuffleConst = lookupShuffle( indexA, indexB, indexC )

shuffle(A, shuffleConst)