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

下面的循环可以矢量化。

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 Cordes，什么？？嗨，彼得^ ^。正如彼得所说，A[i]=A[i-1] 更难，可能是另一种情况。

Answer 2

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

只需使用编译器进行尝试，就可以看到向量加载/存储，而不是标量。（在为x86编译时，很容易用整数而不是FP来区分差异）。e、 g.开启https://godbolt.org/带gcc或clang<代码>-O3<代码>

在具有高效未对齐加载的机器上（如现代x86），编译器可能只会加载a[i 0..3]和a[i 0..3]，但另一个选项是无序移动以创建偏移向量，例如使用x86 SSSE3palignr，这是为此而设计的，在Core 2上非常有用（它没有高效的SIMD未对齐加载）。

GCC和clang都使用SSE2对x86-64进行矢量化（SSE2是x86-64的基线）https://godbolt.org/z/HdNsvC-GCC9。1对于x86-64（默认值为-mtune=generic，只有SSE2可用）选择执行2倍的加载添加存储。叮当声8。0选择展开（像往常一样）并从A[i 1 4*展开0..3]加载，然后使用shufps创建向量。中间端优化器可能使用了一个配方，该配方在palignr方面很好，但一旦达到代码gen，就必须对其进行仿真，并且只有SSE2，而不是SSSE3。此外，输入指针很可能是16字节对齐的，因此从与之相关的16*n 4字节加载向量是不幸的。但无论如何，它都会在最近的Intel CPU上造成洗牌吞吐量瓶颈。

使用AVX1而不是AVX2（例如，march=sandybridge）会造成一个搞笑的混乱：使用256位FP洗牌分多个步骤模拟256位的换行符，然后将整数SIMD解包为128位向量（压缩32位add），然后将vinsertf128解包为256位存储。SnB甚至没有256位的加载/存储单元，因此这些UOP需要2个周期才能运行，并且对未对齐数据的惩罚比通常的要大得多。

A[i]=A[i-1]更难矢量化，但使用高效的洗牌可以加速，尤其是使用浮点，其中串行依赖的延迟会造成更大的伤害。

>

Intel cpu上的SIMD前缀和

带SSE的并行前缀（累计）和

或者通常，如果前面有一个跨步的封闭式公式，您可以在SIMD向量的元素中并行运行该公式，如中，是否可以在计算中对串行依赖项使用SIMD，如指数移动平均滤波器？