c# - 如何使用 SIMD 计算数组中某个字节的出现次数？

Question

给定以下输入字节:

var vBytes = new Vector<byte>(new byte[] {72, 101, 55, 08, 108, 111, 55, 87, 111, 114, 108, 55, 100, 55, 55, 20});

和给定的掩码:

var mask = new Vector<byte>(55);

如何找到字节数 55在输入数组中？

我试过异或 vBytes与 mask :

var xored = Vector.Xor(mask, vBytes);

给出:

<127, 82, 0, 91, 91, 88, 0, 96, 88, 69, 91, 0, 83, 0, 0, 35>

但不知道如何从中得到计数。

为简单起见，我们假设输入字节长度始终等于 Vector<byte>.Count 的大小.

Answer 1

(以下想法的 AVX2 C 内在函数实现，以防具体示例有所帮助:How to count character occurrences using SIMD)

在 asm 中，您希望 pcmpeqb 生成 0 或 0xFF 的向量。被视为有符号整数，即 0/-1。

然后 将比较结果用作整数值 和 psubb 将 0/1 添加到该元素的计数器。 (减 -1 = 加 +1)

这可能会在 256 次迭代后溢出，因此在此之前的某个时候，使用 psadbw 对 _mm_setzero_si128() 将这些无符号字节(无溢出)水平求和为 64 位整数(每组 8 字节一个 64 位整数)。然后 paddq 累加 64 位总数。

溢出前的累加可以通过嵌套循环完成，也可以在常规展开循环的末尾完成。 psadbw 速度很快(因为它是视频编码运动搜索的关键构建 block )，所以每 4 次比较甚至每 1 次累积并跳过 psubb.

参见 Agner Fog's optimization guides有关 x86 的更多详细信息。根据他的指令表，psadbw xmm/vpsadbw ymm 在 Skylake 上以每个时钟周期 1 个向量的速度运行，具有 3 个周期延迟。 (只有1uop的前端带宽。)上面提到的所有指令也是单uop，并且运行在多个端口上(因此吞吐量不一定相互冲突)。他们的 128 位版本只需要 SSE2。

---

如果您真的一次只有一个向量要计算，并且没有在内存中循环，那么可能是 pcmpeqb/psadbw/pshufd (copy high half to low)/padd/movd eax, xmm0 给你 255 * 整数寄存器中的匹配数。一个额外的向量指令(例如从零减去，或与 1 进行与运算，或 pabsb(绝对值)将删除 x255 比例因子。

---

IDK 如何在 C# SIMD 中编写它，但您绝对不想要点积!解包并转换为 FP 将比上面慢 4 倍，这只是因为固定宽度向量比 float 多 4 倍的字节，以及 dpps (_mm_dp_ps) 不快。 4 微指令，Skylake 上每 1.5 个周期吞吐量一个。如果您确实必须对无符号字节以外的内容进行水平求和，请参阅 Fastest way to do horizontal SSE vector sum (or other reduction) (我的答案也包括整数)。

或者如果 Vector.Dot 使用 pmaddubsw/pmaddwd 作为整数向量，那么这可能没有那么糟糕，但是做一个 multi-与 psadbw 相比，比较结果的每个向量的步进水平和是很糟糕的，尤其是与您偶尔只进行水平求和的字节累加器相比。

或者，如果 C# 优化了与 1 的常数向量的任何实际乘法。无论如何，这个答案的第一部分是您希望 CPU 运行的代码。无论您喜欢使用什么源代码来实现这一目标。