冲突检测指令如何使循环向量化更容易？

Question

AVX512CD指令族包括：VPCONFLICT、VPLZCNT和VPBROADCASTM。

维基百科关于这些指令的部分说:

AVX-512冲突检测（AVX-512CD）中的指令旨在帮助有效地计算循环中无冲突子集的元素，而这些元素通常不能安全地进行矢量化处理。

有哪些示例可以展示这些指令在矢量化循环中的实用性？如果答案包括标量循环及其矢量化对应项将会很有帮助。

谢谢！

- zr.

---

什么是AVX-512，为什么英特尔要放弃它？ 林纳斯·托瓦兹：我希望AVX-512能够痛苦地消失。 基于冲突检测的运行长度编码——AVX-512 CD指令集的实际应用。 - Richard Chambers

Answer 1

CD指令可能有用的一个例子是直方图。对于标量代码，直方图就像这样一个简单的循环：

load bin index
load bin count at index
increment bin count
store updated bin count at index

通常情况下，无法对直方图进行矢量化处理，因为在矢量中可能会有多个相同的箱索引 - 你可能会尝试类似于这样的方法：

load vector of N bin indices
perform gathered load using N bin indices to get N bin counts
increment N bin counts
store N updated bin counts using scattered store

但如果向量中的任何索引相同，则会发生冲突，并且导致的二进制更新将不正确。

因此，CD指令来解救:

load vector of N bin indices
use CD instruction to test for duplicate indices
set mask for all unique indices
while mask not empty
    perform masked gathered load using <N bin indices to get <N bin counts
    increment <N bin counts
    store <N updated bin counts using masked scattered store
    remove non-masked indices and update mask
end

实际上，这个例子非常低效，不比标量代码更好，但有其他更计算密集的例子，在使用CD指令时似乎是值得的。通常这些将是模拟，在这些模拟中，数据元素将以非确定性方式更新。其中一个例子（来自LAMMPS分子动力学模拟器）在Jeffers等人的KNL书中被提到。

- Paul R

---

参见Kirill Yukhin 2014年幻灯片第50页。我在一个最近的问题中发布了一些关于如何使用/不使用AVX512CD加速直方图类型问题的内容（链接）。通常的技巧是克隆您的bin并在最后进行总计，这有助于避免冲突（即使对于标量也可以存储转发数据依赖瓶颈）。 - Peter Cordes

谢谢Peter - 我之前没有看过那些幻灯片 - 里面有一些有趣的小知识点... - Paul R

Intel 优化手册 的 "16.2.3 使用 AVX-512CD 指令" 章节中详细描述了这一点。请参考示例 "Example 16-4. Vectorized Histogram Update Using AVX-512CD"。你是从那里得到这个想法的吗？你怎么知道它不比标量更好？你在 KNL 上实践过吗？ - Z boson

也许你可以把你的代码放在这里吗？我正在考虑尝试使用KNL实现这个。你什么时候获得了KNL的访问权限？ - Z boson

一个小测试表明，它使用最后一个元素的值，就像你期望的那样，如果你按顺序写入同一地址。例如，如果你有一个数组 a = {0,1,2,3} 并将其加载到一个 SSE 寄存器 va = _mm_load_epi32(a)，然后将其散布到相同的地址，该地址将包含 3。 - Z boson