这是计算缓冲区中不同值数量的基本算法:
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_u8
和vmaxv_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字节的块。可以更好地做到这一点吗?不太可能
为什么我问这个问题有一些背景。当我在研究算法时,我正在尝试不同的方法来处理数据,但我不确定到底会用到什么。可能有用的信息:
因此,我正在尝试一些东西,在使用任何方法之前,我想先看看该方法是否可以很好地优化。例如,平均每个块将基本上是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_t
或uint32_t
的数组,以避免在uint8_t seq
换行时需要重新调零。但是,这会占用更多的缓存空间,因此也许每254个序列号重新置零才最有意义。