为什么循环次序效应在矩阵乘法中运行时间？

Question

我正在写一个C程序来计算两个矩阵的乘积.问题我注意到for循环的顺序很重要.例如:

对于N = 500

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      for (int k = 0 ; k < N; ++k) {
       C[i*N+j]+=A[i*N+k] * B[k*N+j];
       }
     }
   }

执行时间(秒): 1.1531820000

   for (int j = 0; j < N; ++j) {
     for (int k = 0 ; k < N; ++k) {
       for (int i = 0; i < N; ++i) {
       C[i*N+j]+=A[i*N+k] * B[k*N+j];
       }
     }
   }

执行时间(秒): 2.6801300000

矩阵声明:

      A=(double*)malloc(sizeof(double)*N*N);
      B=(double*)malloc(sizeof(double)*N*N);
      C=(double*)malloc(sizeof(double)*N*N);

我运行测试5次比计算平均值.任何人都知道为什么会这样？

Answer 1

在第二个循环中，当您在内循环中增加 i 并在较小程度上增加 k 时，您会一直进行许多大的跳跃。缓存可能对此不太满意。第一个循环更好，实际上，如果颠倒 j 和 k 的顺序，效果会更好。

这本质上是一个数据局部性的问题。在现代架构中，对主内存的访问非常慢，因此您的 CPU 将保留最近访问的内存的缓存，并尝试预取接下来可能访问的内存。这些缓存在加速分组在同一小区域中的访问或遵循可预测模式的访问方面非常有效。

在这里，我们转变了一种模式，其中 CPU 会在内存中进行大幅跳转，然后返回到一个良好的大部分顺序模式，从而实现加速。