循环展开没有为浮点点积提供预期的加速

Question

 /* Inner product. Accumulate in temporary */
  void inner4(vec_ptr u, vec_ptr v, data_t *dest)
{
     long i;
     long length = vec_length(u);
     data_t *udata = get_vec_start(u);
     data_t *vdata = get_vec_start(v);
     data_t sum = (data_t) 0;

        for (i = 0; i < length; i++) {
                 sum = sum + udata[i] * vdata[i];
       }
  *dest = sum;
 }

写出上述问题中描述的内积程序的一个版本使用 6 × 1a 循环展开。 对于 x86-64，我们对展开版本的测量整数数据的 CPE 为 1.07，但浮点数据的 CPE 仍为 3.01。

我的 6*1a 版循环展开代码

 void inner4(vec_ptr u, vec_ptr v, data_t *dest){
       long i;
       long length = vec_length(u);
       data_t *udata = get_vec_start(u);
       data_t *vdata = get_vec_start(v);
       long limit = length -5;
       data_t sum = (data_t) 0;

      for(i=0; i<limit; i+=6){
             sum = sum +
                   ((udata[ i ] * vdata[ i ]
                  + udata[ i+1 ] * vdata[ i+1 ])
                  + (udata[ i+2 ] * vdata[ i+2 ]
                  + udata[ i+3 ] * vdata[ i+3 ]))
                   + ((udata[ i+4 ] * vdata[ i+4 ])
                  + udata[ i+5 ] * vdata[ i+5 ]);
      }
     for (i = 0; i < length; i++) {
             sum = sum + udata[i] * vdata[i];
   }
  *dest = sum;
      
 }

问题：解释为什么英特尔酷睿 i7 Haswell 处理器上的内积过程运行的任何（标量）版本无法实现低于 1.00 的 CPE。

知道如何解决这个问题吗？

Answer 1

您的展开对 FP 延迟瓶颈没有帮助：

sum + x + y + z 没有 -ffast-math 与 sum += x; sum += y; 的操作顺序相同......所以你没有对单一依赖链做任何事情运行通过所有 + 操作。循环开销（或 front-end 吞吐量）是不是瓶颈，它是 Haswell 上 addss 的 3 周期延迟，所以这个展开基本上没有区别。

可行的是 sum += u[i]*v[i] + u[i+1]*v[i+1] + ... 作为一种无需多个累加器即可展开的方法，因为 那么每组元素的总和是独立的。

这种方式的数学运算成本略高，例如以 mul 开始并以 add 结束，但如果您使用 -march=haswell 进行编译，中间的运算仍然可以缩减为 FMA。有关 GCC 将 sum += u0*v0; sum += u1*v1 之类的简单展开转换为 sum += u0*v0 + u1*v1; 的示例，请参阅关于 AVX performance slower for bitwise xor op and popcount 的评论。在那种情况下，问题略有不同：像 sum += (u0-v0)**2 + (u1-v1)**2; 这样的平方差之和，但它归结为最终进行一些乘法和加法的相同延迟问题。

另一种解决问题的方法是使用多个累加器，允许所有操作都是 FMA。但是 Haswell 有 5 个周期的延迟 FMA 和 3 个周期的延迟 addss，所以自己做 sum += ... 添加，而不是作为 FMA 的一部分，实际上有助于解决 Haswell 的延迟瓶颈（不像在 Skylake add/sub/mul 上都是 4 周期延迟）。以下所有内容都显示了多个累加器的展开，而不是像第一个那样将组加在一起进行成对求和：

When, if ever, is loop unrolling still useful?
Loop unrolling to achieve maximum throughput with Ivy Bridge and Haswell

FP 数学指令吞吐量 不是现代 CPU 上大点积的瓶颈，只有延迟。或者，如果展开足够多，则加载吞吐量。

Explain why any (scalar) version of an inner product procedure running on an Intel Core i7 Haswell processor cannot achieve a CPE less than 1.00.

每个元素需要 2 个负载，并且只有 2 个负载端口，这是一个严重的吞吐量瓶颈。 (https://agner.org/optimize/ / https://www.realworldtech.com/haswell-cpu/5/)

我假设您将一个“元素”算作一个 i 值，一对浮点数，每个来自 udata[i] 和 vdata[i]。 Haswell 上的 FP FMA 吞吐量瓶颈也是 2/时钟（无论它们是标量、128 位还是 256 位向量），但是 点积每个 FMA 需要 2 个负载 。理论上，即使是 Sandybridge 甚至 K8 也可以实现每个时钟 1 个元素，使用单独的 mul 和 add 指令，因为它们都支持每个时钟 2 个加载，并且具有足够宽的管道以通过管道获得加载/mulss/addss 一些有余地。

循环展开没有为浮点点积提供预期的加速

loop unrolling not giving expected speedup for floating-point dot product

c

x86-64

cpu-architecture

dot-product

loop-unrolling