矩阵乘法：为什么非阻塞优于阻塞？

Question

我正在尝试通过阻塞循环来提高缓存性能来加速矩阵乘法算法，但无论矩阵大小、块大小如何，非阻塞版本仍然明显更快（我已经尝试了很多介于两者之间的值2 和 200，2 和其他的势）和优化级别。

非阻塞版本：

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

被阻止的版本：

  for(size_t kk = 0; kk < n; kk += BLOCK)
  {
    for(size_t jj = 0; jj < n; jj += BLOCK)
    {
      for(size_t i = 0; i < n; ++i)
      {
        for(size_t k = kk; k < kk + BLOCK; ++k)
        {
          int r = a[i][k];
          for(size_t j = jj; j < jj + BLOCK; ++j)
          {
            c[i][j] += r * b[k][j];
          }
        }
      }
    }
  }

我也有一个 bijk 版本和一个 6 循环 bikj 版本，但它们都被非阻塞版本超越，我不明白为什么会这样。我遇到的每篇论文和教程似乎都表明被阻止的版本应该明显更快。如果重要的话，我运行在 Core i5 上。

Answer 1

尝试仅在一个维度上进行阻塞，而不是在两个维度上进行阻塞。

矩阵乘法详尽地处理来自两个矩阵的元素。左矩阵上的每个行向量被重复处理，进入右矩阵的连续列。

如果矩阵不能同时放入缓存，某些数据最终将不可避免地被多次加载。

我们可以做的是分解操作，以便我们一次处理大约缓存大小的数据量。我们希望缓存来自左操作数的行向量，因为它会重复应用于多个列。但是我们应该只获取足够的列（一次）以保持在缓存的限制内。例如，如果我们只能获取 25% 的列，则意味着我们将不得不传递四次行向量。我们最终从内存中加载左矩阵四次，而右矩阵只加载一次。

（如果要多次加载任何东西，应该是左边的行向量，因为它们在内存中是平坦的，这得益于突发加载。许多缓存架构可以从内存执行突发加载到相邻的缓存行比随机访问加载更快。如果正确的矩阵以列优先顺序存储，那会更好：然后我们在平面数组之间进行叉积，它可以很好地预取到内存中。）

我们也不要忘记输出矩阵。输出矩阵也在缓存中占用space。

我怀疑 2D 分块方法的一个缺陷是输出矩阵的每个元素都依赖于两个输入：左矩阵中的整行和右矩阵中的整列。如果按块访问矩阵，则意味着每个目标元素都被多次访问以累积部分结果。

如果我们做一个完整的行-列点积，我们不必多次访问c[i][j]；一旦我们将列 j 放入行 i，我们就完成了 c[i][j]。

矩阵乘法：为什么非阻塞优于阻塞？

Matrix-Multiplication: Why non-blocked outperforms blocked?

c

caching

cpu-architecture

matrix-multiplication