9

问题
是否有任何计算上可行的方法来使用 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

4

2 回答 2

5

解决方案

建议的解决方案总是将所有独特元素放在输出的下部，按第一次出现的顺序排列。较高的部分归零。通过修改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 比较，以便每对元素至少比较一次。之后，我们可以通过使用提取比较的 16 位位掩码_mm_movemask_epi8并将它们连接成一个 32 位整数。请注意，每个 4 位块肯定包含相同的位，最后两个 4 位块不是必需的（它们对应于过多的比较）。

理想情况下，我们需要从这个位掩码中准确提取位于编译时已知位置的 6 位。它可以通过_pext_u32BMI2 指令集中的内在函数轻松实现。结果，我们有一个范围为[0..63]的整数，包含 6 位，每个位显示对应的元素对是否相等。然后我们从预先计算的 64 项查找表中加载一个混洗掩码，并使用_mm_shuffle_epi8.

不幸的是，BMI 指令是相当新的（Haswell 和更高版本），我没有它们 =）为了摆脱它，我们可以尝试为所有 64 个有效位掩码创建一个非常简单且快速的完美哈希函数（回想一下位掩码是 32 位的）。对于类中的散列函数，f(x) = (a * x) >> (32-b)通常可以构造一个相当小的完美散列，具有 2 倍或 3 倍的内存开销。由于我们的情况比较特殊，可以构造一个最小完美散列函数，使得查找表最少有 64 个条目（即 size = 1 KB）。

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

对 YMM 寄存器中的 64 位元素使用这种方法也是有问题的。_mm256_shuffle_epi8内在没有帮助，因为它只是执行两个单独的 128 位随机播放（从不跨通道随机播放）。_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)
于 2015-08-03T13:52:54.197 回答
0

天真的解决方案

基于 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)
于 2012-05-25T19:58:27.477 回答