代码之家 › 专栏 › 技术社区 › Pavel P

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

neon intrinsics arm c++

Pavel P · 技术社区 · 6 年前

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

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

在neon中,通过加载到q-reg并执行一些小魔术,可以有效地做到这一点吗?或者,我可以有效地这样说吗 data 是否所有元素都相同,或仅包含两个不同的值或两个以上的值?

例如,使用 vminv_u8 和 vmaxv_u8 我可以找到最小和最大元素,如果它们相等,我知道 数据 具有相同的元素。如果没有,那么我可以 vceq_u8 最小值和 vceq\U 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字节的块。这在arm中能做得更好吗?不大可能发生的

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

每16字节块的不同元素计数
每16字节块重复次数最多的值
每个区块的平均值
每个区块的中值
光速?。。这是一个笑话,它不能用neon从16字节块计算:)

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

1 回复 | 直到 6 年前

Peter Cordes 6 年前

如果你希望有很多重复的 ,并且可以 有效地 使用获得水平最小值 vminv_u8 ,这可能比标量更好。或者不是,也许是霓虹灯->手臂因循环条件而暂停,杀死它><但通过展开(并将一些信息保存在寄存器中,以计算出超出的程度)应该可以缓解这种情况。

// 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链保留在向量寄存器中;只有环路分支需要霓虹灯->整数

最小化/隐藏霓虹灯->整数/ARM惩罚

展开8,无分支打开 hmin ,将结果保留在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个值混洗到一个向量中并比较是否不等于 0xFF 。然后水平添加该比较结果以获得 -count 。

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

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

加快对scalar ARM版本的重复调用:

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

在每一组新元素之前: ++seq ;

对于集合中的每个元素:

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

您可以将直方图设置为 uint16_t 或 uint32_t 避免在以下情况下需要重新归零 uint8_t seq 包裹。但是这样做需要更多的缓存占用空间,所以也许每254个序列号重新归零最有意义。