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

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我可以找到min和max元素,如果它们相等,我知道data具有相同的元素。如果不是,那么我可以用最小值的vceq_u8和用最大值的vceq_u8,然后vorr_u8这些结果,并比较结果中是否有全1。基本上,在 NEON 中可以通过这种方式完成。任何想法如何使它变得更好?
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字节的块。可以更好地做到这一点吗?不太可能

为什么我问这个问题有一些背景。当我在研究算法时,我正在尝试不同的方法来处理数据,但我不确定到底会用到什么。可能有用的信息:
  • 每16个字节块中不同元素的计数
  • 每个16字节块重复最多的
  • 每块平均值
  • 每块位数
  • 光速?..这是个 Jest ,它不能以16字节块的 NEON 来计算:)

  • 因此,我正在尝试一些东西,在使用任何方法之前,我想先看看该方法是否可以很好地优化。例如,平均每个块将基本上是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链保留在 vector 寄存器中;只有循环分支需要NEON-> integer。

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

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

    调整展开因子足够大,以使您通常不需要为大多数输入 vector 进行另一轮SIMD操作。如果几乎所有 vector 最多具有5个唯一值,则将其展开5而不是8。

    而不是将多个hmin结果转换为整数,而是将其计入NEON 中。如果您可以使用ARM32 NEON部分寄存器技巧将多个hmin值免费放入同一 vector 中,则将其中的8个随机化为一个 vector 并比较与0xFF不相等只是更多的工作。然后水平添加该比较结果以获得-count

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

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

    加快对标量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个序列号重新置零才最有意义。

    10-05 22:55
    查看更多