如何通过按行或按列设置连续块来优化矩阵计算中的内存命中

Question

我期待通过如何存储二维矩阵的内存来优化内存命中。我打算将二维矩阵折叠成一维连续的块，并想知道将数据作为连续的块按行还是按列存储会更有意义。我正在考虑的操作类型是更昂贵的操作，例如乘法和SVD。请注意，我正在考虑在C++中的实现。

上配置

澄清连续的行或列，我指的是以下内容。考虑一个3×3矩阵

[a11 a12 a13] 
[a21 a22 a23] 
[a31 a32 a33] 

会更有意义由

行

[[a11 a12 a13] [a21 a22 a23] [a31 a32 a33]] 

，然后在[I，J]将被作为访问的每个元素到矩阵存储[I * NCOL + j]的并且任何元素a [i，j]在内存中更接近[i，j + 1]而不是[i + 1，j]

[[a11 a21 a31] [a12 a22 a32] [a13 a23 a33]] 

，然后在每个元素[I，J]将被作为访问[J * nRow + i]和任何元件的[I，J]为在存储器更接近第[i + 1，j]的比[i，j + 1]

现在说我们有一个缓存，一次只加载三个双打的块。在第一种情况下，访问a11，a12和a13需要加载一个块。在第二种情况下，访问a11，a13和a13需要加载三个块。这对于3x3矩阵来说可能不是问题，因为这两种情况都需要加载三个块来完成计算，并且三者都可以很容易地适合我们的缓存内容，但这可能会成为一个问题，因为当我们有非常大的矩阵时无法一次将整个矩阵放入缓存中。

直觉反应

我已经做了一些研究，存储二维矩阵作为一维数组如：

• 1d-or-2d-array-whats-faster

而且也对参与矩阵的运营商乘法如

• Wikipedia article on Matrix Multiplication

和相关的斯特拉森算法。

看来，由于矩阵乘法的性质，你遍历一个矩阵的行和另一个列。直觉上来说，我认为在这个特定的操作中，将数据存储在另一个配置中会带来什么性能损失。

即。考虑乘以两个2×2矩阵C = AB，其中A是N×M的，B是MXL

c[i,k] = sum(a[i,m] * b[m,k]) for m = [1...M] 

您正在访问的数据行的左矩阵，并在正确的矩阵列，所以你没有优势将数据存储在一起，因为对一个矩阵来说更好的是对另一个来说更糟糕。

考虑到矩阵上运算量大的操作，这些配置之一在内存访问方面会更好吗？或者考虑到实际的大规模矩阵乘法是在GPU或类似的配置上完成的，这是否是一个非问题？还是加载其他内容遮蔽的内存块的代价？

Answer 1

建模非稀疏矩阵的标准方法是使用连续内存块的。

你偏离的地方在于你试图从头开始建立一个你自己的矩阵类。我建议你使用一个已建立的库，比如BLAS（你可以把它作为一个boost包）。除非你有很多空闲时间，否则你不可能击败图书馆所做的优化。

正如您正确指出的那样，矩阵乘法本身就是这样的，以至于排列连续内存将有利于左或右矩阵。行列式评估类似。真的，推迟这样的考虑到第三方，经过充分测试的图书馆。