在SSE/AVX中选择唯一性/去重

Question

在SSE/AVX中选择唯一性/去重

algorithmassemblyssesimdavx

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的解决方案。

- awdz9nld

例如，在SSE4中，我们可以迭代使用RMAX = _mm_max_epi32，并且仅在RMAX！= RMAX_PREV时有条件地从RMAX写入输出寄存器？ - awdz9nld

假设这是作业：您应该查看pshufd和pcmpeqd指令。 - Gunther Piez

哈哈，不，这不是作业。 ;) - awdz9nld

2个回答

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)

- awdz9nld

MoveMasked 函数是做什么用的？如果它只是移动掩码值，那么这个例程只会移除最大值。 - Gunther Piez

好的，我现在明白了。我认为可以使用比较相等来代替最大值。需要枚举所有带有重复整数的模式，并使用从比较生成的掩码计算索引，该索引可用于查找表以获取洗牌常量。 - Gunther Piez

可能对于查找表，可以使用pshufb指令 - 前提是表的大小不超过16个元素。这样一来，所有数据都将保留在寄存器中。我不确定这是否可行。 - Gunther Piez

我明白我们可以使用Shuffle()代替Rotate()，但我不太确定如何用Max()代替Shuffle()? 你愿意写些伪代码吗？ :) - awdz9nld

你可以使用MOVMSKPS(int _mm_movemask_ps(__m128 a))指令来代替horSum(a * b)。但我感觉这个问题并不适合使用向量指令。 - Norbert P.

显示剩余4条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- stgatilov · Accepted Answer

解决方案

提出的解决方案始终将所有唯一元素放置在输出的下部，并按首次出现的顺序排序。上部分被清零。可以通过修改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)

讨论

请注意，结果必须由两种类型的元素组成：

来自输入向量的元素，
零。

然而，必要的洗牌掩码是在运行时以非常复杂的方式确定的。所有SSE指令都只能处理立即（即编译时常数）洗牌掩码，除了一个。它是SSSE3中的_mm_shuffle_epi8内部函数。为了快速获取洗牌掩码，所有掩码都存储在查找表中，由一些位掩码或哈希索引。

为了获得给定输入向量的洗牌掩码，有必要收集关于其中相等元素的足够信息。请注意，仅知道哪些元素对相等就足够确定如何去重。如果我们还想将它们排序，那么我们还需要知道不同的元素彼此比较的方式，这增加了信息量，并随后增加了查找表。这就是为什么我在这里展示不进行排序的去重。

因此，我们在XMM寄存器中有四个32位元素。它们总共组成了六对。由于我们一次只能比较四个元素，所以我们至少需要进行两次比较。实际上，很容易进行两个XMM比较，这样每对元素都会被比较至少一次。之后，我们可以使用_mm_movemask_epi8提取比较的16位掩码，并将它们连接成一个单独的32位整数。请注意，每个4位块肯定包含相同的位，并且最后两个4位块不是必需的（它们对应于过多的比较）。

理想情况下，我们需要从这个掩码中提取出位于编译时已知位置的6位。可以使用BMI2指令集中的_pext_u32内部函数轻松实现。结果，我们得到一个范围在[0..63]之间的整数，其中每个位表示相应的元素对是否相等。然后，我们从预先计算的64项查找表中加载一个洗牌掩码，并使用_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（从不跨越通道进行 shuffle）。_mm256_permutevar8x32_epi32 内置函数可以任意地对 32 位块进行 shuffle，但它不能插入零。为了使用它，您还需要在 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)