1

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

但我不确定这A[i] += A[i+1]是否是原始数据依赖关系，如果这个循环可以向量化？

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

2 回答 2

2

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

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

在具有高效未对齐负载的机器（如现代 x86）上，您的编译器可能只会加载A[ i +0..3]and A[ i+1 + 0..3 ]，但另一个选项是改组以创建偏移向量，例如使用palignr为此设计的 x86 SSSE3，它对 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 上成为 shuffle 吞吐量的瓶颈。

使用 AVX1 而不是 AVX2 的 Clang （例如-march=sandybridge）会造成可笑的混乱：在多个步骤中使用 256 位 FP shuffle 来模拟 256-bit palignr，然后解包为整数 SIMD 的 128 位向量vpaddd（打包的 32 位加法），然后vinsertf128返回256 位存储到 256 位。SnB 甚至没有 256 位加载/存储单元，因此这些微指令需要 2 个周期才能运行，并且对未对齐数据的惩罚比通常要大得多。

A[i] += A[i-1]更难矢量化，但是通过有效的洗牌可以加快速度，特别是在浮点数的情况下，串行依赖的延迟会受到更大的伤害。

n或者一般来说，如果有一个用于向前迈出的封闭式公式，您可以在 SIMD 向量的元素中并行运行它，例如在计算中是否可以在串行依赖上使用 SIMD，例如指数移动平均筛选？

于 2019-08-08T11:17:26.483 回答
0

下面的这个循环可以向量化。

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

所以矢量化并不难。作为彼得科德斯，什么？嗨彼得^^。正如彼得所说A[i] += A[i - 1];的那样更难，而且情况会有所不同。

于 2019-08-16T12:55:52.930 回答