18

我有两个函数来查找两个矩阵的乘积:

 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 倍)快。关于为什么的任何想法?

4

4 回答 4

39

我相信您正在查看的是计算机内存层次结构中参考位置的影响。

通常,计算机内存被分为具有不同性能特征的不同类型(这通常称为内存层次结构)。最快的内存在处理器的寄存器中,(通常)可以在单个时钟周期内访问和读取。但是,这些寄存器通常只有少数几个(通常不超过 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](因为ij相同),也不会错过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 章将讨论这些编译器的工作原理。

此外,您可以使用更复杂的循环进一步优化此循环的性能。例如,一种称为阻塞的技术可用于通过将数组拆分为可以在缓存中更长时间保存的子区域来显着提高性能,然后对这些块使用多个操作来计算整体结果。

希望这可以帮助!

于 2011-09-13T00:42:34.950 回答
6

这很可能是内存局部性。当您重新排序循环时,最内层循环所需的内存更接近并且可以缓存,而在低效版本中,您需要从整个数据集访问内存。

检验这个假设的方法是cachegrind在两段代码上运行一个缓存调试器(如 ),看看它们发生了多少缓存未命中。

于 2011-09-13T00:34:56.260 回答
1

除了内存的局部性,还有编译器优化。矢量和矩阵运算的关键之一是循环展开。

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

你可以在这个内部循环中看到i并且j不要改变。这意味着它可以重写为

for (int k = 0; k < n; k+=4) {
   int * aik = &a[i][k];
   c[i][j] +=
         + aik[0]*b[k][j]
         + aik[1]*b[k+1][j]
         + aik[2]*b[k+2][j]
         + aik[3]*b[k+3][j];
}

你可以看到会有

  • 对 c[i][j] 的循环和访问次数减少了四倍
  • a[i][k] 在内存中被连续访问
  • 内存访问和乘法可以在 CPU 中流水线化(几乎同时)。

如果n不是 4 或 6 或 8 的倍数怎么办?(或编译器决定将其展开的任何内容)编译器会为您处理这些整理。;)

为了更快地加速这个解决方案,您可以b先尝试转置矩阵。这是一些额外的工作和编码,但这意味着对 b-transposed 的访问在内存中也是连续的。(当您将 [k] 与 [j] 交换时)

您可以做的另一件事来提高性能是多线程乘法。这可以将 4 核 CPU 的性能提高 3 倍。

最后,您可能会考虑使用floatordouble您可能认为int会更快,但情况并非总是如此,因为浮点运算可以得到更多优化(在硬件和编译器中)

第二个示例的 c[i][j] 在每次迭代中都会发生变化,这使得优化变得更加困难。

于 2011-09-13T07:58:12.350 回答
0

可能第二个必须在内存中跳过更多才能访问数组元素。它也可能是别的东西——你可以检查编译的代码来看看实际发生了什么。

于 2011-09-13T00:34:45.317 回答