有效地计算 arm neon 中 16 字节缓冲区中不同值的数量

Efficiently count number of distinct values in 16-byte buffer in arm neon

下面是计算缓冲区中不同值数量的基本算法:

unsigned getCount(const uint8_t data[16])
{
    uint8_t pop[256] = { 0 };
    unsigned count = 0;
    for (int i = 0; i < 16; ++i)
    {
        uint8_t b = data[i];
        if (0 == pop[b])
            count++;
        pop[b]++;
    }
    return count;
}

这能否通过载入 q-reg 并施展魔法,以某种方式在 neon 中有效地完成?或者,我可以有效地说 data 具有相同的所有元素,还是只包含两个或两个以上不同的值?

例如,使用 vminv_u8vmaxv_u8 我可以找到最小和最大元素,如果它们相等,我知道 data 具有相同的元素。如果不是,那么我可以 vceq_u8 最小值和 vceq_u8 最大值然后 vorr_u8 这些结果并比较我在结果中有所有 1-s。基本上,在霓虹灯中,它可以通过这种方式完成。有什么想法可以让它变得更好吗?

unsigned getCountNeon(const uint8_t data[16])
{
    uint8x16_t s = vld1q_u8(data);
    uint8x16_t smin = vdupq_n_u8(vminvq_u8(s));
    uint8x16_t smax = vdupq_n_u8(vmaxvq_u8(s));
    uint8x16_t res = vdupq_n_u8(1);
    uint8x16_t one = vdupq_n_u8(1);

    for (int i = 0; i < 14; ++i) // this obviously needs to be unrolled
    {
        s = vbslq_u8(vceqq_u8(s, smax), smin, s); // replace max with min
        uint8x16_t smax1 = vdupq_n_u8(vmaxvq_u8(s));
        res = vaddq_u8(res, vaddq_u8(vceqq_u8(smax1, smax), one));
        smax = smax1;
    }
    res = vaddq_u8(res, vaddq_u8(vceqq_u8(smax, smin), one));
    return vgetq_lane_u8(res, 0);
}

通过一些优化和改进,或许可以用 32-48 条 neon 指令处理一个 16 字节的块。这可以在手臂上做得更好吗?不太可能

我问这个问题的一些背景知识。当我在研究一种算法时,我正在尝试不同的方法来处理数据,但我不确定最后我会使用什么。可能有用的信息:

所以,我正在尝试一些东西,在我使用任何方法之前,我想看看该方法是否可以得到很好的优化。例如,每个块的平均值基本上是 arm64 上的 memcpy 速度。

如果您期望有很多重复项,并且可以有效地使用vminv_u8获得水平最小值,这可能比标量更好。或者不是,也许 NEON->ARM 因循环条件而停顿杀死它。 >.< 但是应该可以通过展开来缓解这种情况(并在寄存器中保存一些信息以计算出超出的范围)。

// pseudo-code because I'm too lazy to look up ARM SIMD intrinsics, edit welcome
// But I *think* ARM can do these things efficiently, 
// except perhaps the loop condition.  High latency could be ok, but stalling isn't

int count_dups(uint8x16_t v)
{
    int dups = (0xFF == vmax_u8(v));   // count=1 if any elements are 0xFF to start
    auto hmin = vmin_u8(v);

    while (hmin != 0xff) {
        auto min_bcast = vdup(hmin);  // broadcast the minimum
        auto matches = cmpeq(v, min_bcast);
        v |= matches;                 // min and its dups become 0xFF
        hmin = vmin_u8(v);
        dups++;
    }
    return dups;
}

这会将唯一值变成 0xFF,一次重复一组。

通过v/hmin循环携带的dep链留在向量寄存器中;只有循环分支需要 NEON->integer.


最小化/隐藏 NEON->integer/ARM 惩罚

hmin 上没有分支的情况下按 8 展开,将结果留在 8 个 NEON 寄存器中。然后转移这8个值; back-to-back transfers of multiple NEON registers to ARM only incurs one total stall(Jake 测试的任何 14 个周期。)乱序执行也可能隐藏此停顿的一些惩罚。然后用完全展开的整数循环检查这 8 个整数寄存器。

将展开因子调得足够大,这样您通常就不需要对大多数输入向量进行另一轮 SIMD 运算。如果几乎所有向量最多有 5 个唯一值,则展开 5 而不是 8。


与其将多个 hmin 结果转换为整数,不如将它们计算在 NEON 中。如果您可以使用 ARM32 NEON 部分寄存器技巧将多个 hmin 值免费放入同一个向量中,那么将其中的 8 个值洗牌到一个向量中并比较不等于 [=16 只是多一点工作=].然后水平添加该比较结果以获得 -count.

或者,如果您在单个向量的不同元素中具有来自不同输入向量的值,则可以使用垂直运算一次为多个输入向量添加结果,而无需水平运算。


几乎肯定有优化空间,但我不太了解 ARM,或 ARM 性能细节。 NEON 很难用于任何条件,因为 NEON-> 整数的性能损失很大,这与 x86 完全不同。 Glibc has a NEON memchr 在循环中使用 NEON->integer,但我不知道它是否使用它或者它是否比标量更快。


加速对标量 ARM 版本的重复调用:

每次都将 256 字节的缓冲区清零会很昂贵,但我们不需要这样做。 使用序列号以避免需要重新设置:

  • 在每组新元素之前:++seq
  • 对于集合中的每个元素:

    sum += (histogram[i] == seq);
    histogram[i] = seq;     // no data dependency on the load result, unlike ++
    

您可以将直方图设为 uint16_tuint32_t 的数组,以避免在 uint8_t seq 回绕时需要重新归零。但是它需要更多的缓存空间,所以也许每 254 个序列号重新归零是最有意义的。