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

Question

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

示例
我们有一个四元组的寄存器R1 = {3，9，2，9}，并希望获得寄存器R2 = {3，9，2，NULL}。

限制
稳定性。保留输入顺序没有任何意义。

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

{null，1，2，3}-OK

{1，2，null，null}-OK

{null，2，null，null}-OK

{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);
}

完整代码(带有测试)可在here中获得。

我还通过对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]的整数，其中包含6个位，每个位都显示相应的元素对是否相等。然后，我们从预先计算的64项查找表中加载混洗掩码，并使用_mm_shuffle_epi8混洗输入向量。

不幸的是，BMI指令是相当新的(Haswell和更高版本)，但我没有它们=)为了摆脱它，我们可以尝试为所有64个有效位掩码创建一个非常简单快速的perfect hash function(回想一下，这些位掩码是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位随机播放(从不跨 channel 随机播放)。 _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);
}

full code也将更新。这会导致轻微的性能改进:

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