A[i]+=A[i+1] 是一种循环中的数据依赖吗？可以向量化吗？

Question

据我所知，A[i] += A[i-1] 等具有串行数据依赖性的循环无法向量化。

但我不确定 A[i] += A[i+1] 是否是原始数据依赖项以及此循环是否可以向量化？

for(i = 0; i < n - 1; i++) {
    A[i] += A[i + 1];
}

Answer 1

您的循环计数器正在增加 (i++)，因此您正在前方和 A[i+1]，而不是落后。 这意味着您只是读取相同的原始输入元素两次，而不是重新读取任何最近的输出。因此没有串行依赖性。

只需使用编译器尝试一下，就会看到向量加载/存储而不是标量。（在为 x86 编译时，很容易区分整数而不是 FP）。例如在 https://godbolt.org/ 上使用 gcc 或 clang -O3

在具有高效未对齐加载的机器上（如现代 x86），您的编译器可能只会执行 A[ i +0..3] 和 A[ i+1 + 0..3 ] 的加载，但另一个选项是改组以创建偏移向量，例如使用专为此设计的 x86 SSSE3 palignr，对 Core 2 非常有帮助（没有具有高效的 SIMD 未对齐加载）。

GCC 和 clang 都使用 SSE2（这是 x86-64 的基线）为 x86-64 对其进行矢量化 https://godbolt.org/z/HdNsvC - 用于 x86-64 的 GCC9.1（默认 -mtune=generic 且仅 SSE2 可用）选择执行 2x 加载 + 添加 + 存储。 clang8.0 选择展开（像往常一样）并从 A[i+1 +4*unroll + 0..3] 加载并使用 shufps 创建 A[i + 0..3] 向量。中端优化器可能使用了一个适用于 palignr 的配方，但是一旦它进入代码生成阶段并且只有 SSE2，没有 SSSE3，就必须模拟它。此外，输入指针很可能是 16 字节对齐的，因此从相对于它的 16*n + 4 字节加载向量是不幸的。无论如何它都会在最近的 Intel CPU 上对洗牌吞吐量造成瓶颈。

使用 AVX1 而不是 AVX2（例如 -march=sandybridge）的 Clang 搞得一团糟：在多个步骤中使用 256 位 FP 随机播放来模拟 256 位 palignr，但随后解包为 128-整数 SIMD vpaddd（打包的 32 位加法）的位向量，然后 vinsertf128 返回 256 位以用于 256 位存储。 SnB 甚至没有 256 位 load/store 单位，因此这些 uops 需要 2 个周期才能达到运行，并且对未对齐数据的惩罚比通常大得多。

A[i] += A[i-1] 更难矢量化 ，但是通过高效的洗牌可以实现加速，尤其是对于串行依赖的延迟伤害更大的浮点.

SIMD prefix sum on Intel cpu
parallel prefix (cumulative) sum with SSE

或者一般来说，如果有一个封闭形式的公式用于向前迈进 n 步，您可以运行在 SIMD 向量的元素中并行，例如

Answer 2

下面的循环可以矢量化。

for(i = 0; i < n - 1; i++) {
    A[i] += A[i + 1];
}

我们可以把操作写成另一种方式：

Vector A = ...;           // 1, 2, 3, 4, 5
Vector B = ShiftLeft(A);  // 2, 3, 4, 5, 0 you dont create new array, no performance loss
Vector C = A + B;         // 3, 5, 7, 9, 5

矢量化并不难，所以.. 作为彼得科德斯，什么？？嗨，彼得 ^^。正如 Peter 所说 A[i] += A[i - 1]; 更难并且会是一个不同的场景。

A[i]+=A[i+1] 是一种循环中的数据依赖吗？可以向量化吗？

Is A[i]+=A[i+1] kind of data dependency in a loop ? Can it be vectorized?

c

simd

vectorization

auto-vectorization