c++ - 为什么阻塞技术减少分支指令？

Question

我分析了 block 矩阵乘法随着 block 大小的增加分支指令数量的减少。 在 Image1 盒装组中有 450 万条分支指令，但在其他组中大约有 1700 万条分支指令，这是为了防止只有循环顺序发生变化。据我所知，分支指令取决于代码或其机器代码中使用的任何分支指令(有条件或无条件)，但我无法弄清楚循环重新排序如何改变分支量。尽管循环重新排序阻塞技术也会影响分支指令的数量。

操作系统是 linux x86_64 Ram 4G l1 缓存 32k 64Byte 行大小 L2 缓存 2048k 64Byte 行大小 4 路关联。使用 papi_library 配置文件

kij算法

For (k=0;k<n;k++)
For(i=0;i<n;i++){
    r=A[i][k];
  For (j=0;j<n;j++)
      C[i][j]+=r*B[k][j] 
}

ikj算法

For (i=0;i<n;i++)
 For(k=0;k<n;k++){
  r=A[i][k];
  For (j=0;j<n;j++)
       C[i][j]+=r*B[k][j] 
}   

我的阻塞代码不在手头，但使用 1 级阻塞。

图 1(图表按对数比例缩放，可能所有组看起来都一样但值是真实的)

问题:

1- 为什么循环重新排序或阻塞可以减少或增加分支指令的数量？

谢谢

Answer 1

循环重新排序是代码块重新排序优化之一，它改变了程序中基本 block 的顺序，以减少条件分支并改进 locality of reference .

为了简单地描述分支缩减，假设您有这样的代码:

void foo(bool is_enabled) {
  for (int i = 0; i < 10000; ++i) {
    if (is_enabled) {
      data[i].enable();
    } else {
      data[i].disable();
    }
  }
}

鉴于不需要一直检查is_enabled，编译器可能会决定这样做:

void foo(bool is_enabled) {
  if (is_enabled) {
    for (int i = 0; i < 10000; ++i) {
      data[i].enable();
    }
  } else {
    for (int i = 0; i < 10000; ++i) {
      data[i].disable();
    }
  }
}

...因此减少了 9999 个分支数量(只有一次检查 is_enabled 而不是 10000)。

在您拥有的代码片段中，由于对硬件更友好的内存访问模式，这更像是一个引用优化的位置，可以很好地与内存预取器和 CPU 缓存配合使用。