1

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

操作系统是 linux x86_64 Ram 4G l1 cache 32k 64Byte line size L2 cache 2048k 64Byte line size 4-way associative。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-为什么循环重新排序或阻塞会减少或增加分支指令的数量？

谢谢

4

2 回答 2

1

循环重排序是代码块重排序优化之一，它改变程序中基本块的顺序，以减少条件分支并提高引用的局部性。

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

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 缓存一起使用，因为内存访问模式对硬件更友好。

于 2013-10-14T15:18:00.417 回答
0

我认为循环重新排序不会影响为您的示例代码生成的分支指令的数量，因为它在循环内没有条件测试，并且所有循环的长度都相同。

如果在编译时块大小是已知的，那么您的编译器可能会为每个块展开循环。

您应该真正查看编译器的程序集输出。

于 2013-10-14T15:20:37.900 回答