为什么矩阵乘法算法中的循环顺序会影响性能？

  • Z时代
  • 2024-01-10
  • 分类：问答

为查找两个矩阵的乘积提供了两个函数：

 void MultiplyMatrices_1(int **a, int **b, int **c, int n){
      for (int i = 0; i < n; i++)
          for (int j = 0; j < n; j++)
              for (int k = 0; k < n; k++)
                  c[i][j] = c[i][j] + a[i][k]*b[k][j];
  }
 void MultiplyMatrices_2(int **a, int **b, int **c, int n){
      for (int i = 0; i < n; i++)
          for (int k = 0; k < n; k++)
              for (int j = 0; j < n; j++)
                  c[i][j] = c[i][j] + a[i][k]*b[k][j];
 }

我使用运行和分析了两个可执行文件gprof，每个可执行文件的功能相同，但功能相同。对于大小为2048 x

2048的矩阵，这些中的第二个显着快（大约5倍）。为什么？

回答：

我相信您正在查看的是计算机内存层次结构中引用局部性的影响。

通常，计算机内存被分为具有不同性能特征的不同类型（通常称为

）。最快的内存位于处理器的寄存器中，通常可以在一个时钟周期内对其进行访问和读取。但是，通常这些寄存器中只有少数几个（通常不超过1KB）。另一方面，计算机的主内存很大（例如8GB），但访问速度却慢得多。为了提高性能，计算机通常在物理上构造为具有多个缓存级别在处理器和主内存之间。这些高速缓存比寄存器慢，但比主存储器快得多，因此，如果您执行在高速缓存中查找某些内容的内存访问，它往往比必须访问主存储器要快得多（通常在5-25倍之间）快点）。访问内存时，处理器先检查内存高速缓存中的该值，然后再返回主内存以读取该值。如果您始终访问高速缓存中的值，则最终的性能将比跳过内存更好。内存，随机访问值。

大多数程序都是以以下方式编写的：如果将内存中的单个字节读入内存，程序随后也会从该内存区域中读取多个不同的值。因此，通常设计这些缓存，以便当您从内存中读取单个值时，该单个值周围的内存块（通常在1KB到1MB之间）也会被拉到缓存中。这样，如果您的程序读取附近的值，则它们已经在缓存中，您不必进入主内存。

现在，最后一个细节-在C / C

++中，数组以行优先顺序存储，这意味着矩阵的单行中的所有值都彼此相邻存储。因此，在内存中，数组看起来像第一行，然后是第二行，然后是第三行，依此类推。

鉴于此，让我们看一下您的代码。第一个版本如下所示：

  for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
          for (int k = 0; k < n; k++)
              c[i][j] = c[i][j] + a[i][k]*b[k][j];

现在，让我们看一下最里面的代码行。在每次迭代中，k的值都在增加。这意味着，在运行最内部的循环时，循环的每次迭代在加载的值时都可能会发生缓存未命中的情况b[k][j]。这样做的原因是因为矩阵是按行优先顺序存储的，所以每次增加k时，就跳过了矩阵的整行，并跳入了内存，甚至远远超过了缓存的值。但是，查找时不会遗漏c[i][j]（因为i和j相同），也不可能会遗漏a[i][k]，因为这些值是以行优先的顺序排列的，并且如果的值a[i][k]是从先前的迭代中缓存的，则a[i][k]在此迭代中读取的是从相邻存储器位置读取的。因此，在最内层循环的每次迭代中，您可能都会遇到一个缓存未命中的情况。

但是考虑第二个版本：

  for (int i = 0; i < n; i++)
      for (int k = 0; k < n; k++)
          for (int j = 0; j < n; j++)
              c[i][j] = c[i][j] + a[i][k]*b[k][j];

现在，由于j每次迭代都在增加，所以让我们考虑一下最里面的语句可能有多少个高速缓存未命中。由于这些值按行优先顺序排列，因此的值c[i][j]很可能在高速缓存中，因为c[i][j]前一次迭代的值也很可能也已缓存并且可以读取。同样的，b[k][j]可能是缓存，并且因为i和k不改变，没准a[i][k]会被缓存为好。这意味着在内部循环的每次迭代中，您很可能没有缓存未命中。

总体而言，这意味着第二个版本的代码不太可能在循环的每次迭代中出现缓存丢失，而第一个版本几乎肯定会。因此，如您所见，第二个循环可能比第一个循环快。

有趣的是，许多编译器已开始具有原型支持，以检测第二版本的代码比第一版本的代码更快。有些人会尝试自动重写代码以最大程度地提高并行度。如果您有《紫龙书》的副本，则第11章将讨论这些编译器的工作方式。

此外，您甚至可以使用更复杂的循环来进一步优化此循环的性能。例如，一种称为“

阻塞

”的技术可用于通过将阵列拆分为可以在缓存中保留更长时间的子区域，然后对这些块执行多次运算来计算总体结果，从而显着提高性能。

希望这可以帮助！

以上是 为什么矩阵乘法算法中的循环顺序会影响性能？ 的全部内容， 来源链接： utcz.com/qa/427756.html

回到顶部