cpumemory.pdf -缓存优化矩阵乘法

Question

我正在阅读Ulrich的cpumemory.pdf，我无法理解第6.2.1章(第49-50页)中关于优化矩阵乘法中的缓存访问的以下部分：

首先给出了矩阵乘法的朴素方法：

for (i = 0; i < N; ++i)
    for (j = 0; j < N; ++j)
        for (k = 0; k < N; ++k)
            res[i][j] += mul1[i][k] * mul2[k][j];

mul2由列访问，因此每列浪费一条缓存行。Ulrich说：

由于大号(双)为8，这意味着，为了充分利用缓存行，我们应该展开8次中间循环。

为了简洁起见，我只展开了2次中间循环。

for (i = 0; i < N; ++i)
    for (j = 0; j < N; j += 2)
        for (k = 0; k < N; ++k) {
            res[i][j+0] += mul1[i][k] * mul2[k][j+0];
            res[i][j+1] += mul1[i][k] * mul2[k][j+1];
        }

现在很明显，如果缓存行宽为2个双值，那么它将得到充分利用。但乌尔里希接着说：

继续这一思想，为了有效地利用res矩阵，即同时写出8个结果，我们还应该展开外循环8次。

为了简洁起见，我只重新展开了2次外循环。

for (i = 0; i < N; i += 2)
    for (j = 0; j < N; j+=2)
        for (k = 0; k < N; ++k) {
            res[i+0][j+0] += mul1[i+0][k] * mul2[k][j+0];
            res[i+0][j+0] += mul1[i+0][k] * mul2[k][j+0];
            res[i+1][j+0] += mul1[i+1][k] * mul2[k][j+0];
            res[i+1][j+1] += mul1[i+1][k] * mul2[k][j+1];
        }

在我看来，这比以前的版本更糟糕，因为现在mul1是由列访问的。请解释一下Ulrich的意思。

Answer 1

缓存中有三个矩阵:左输入、右输入和结果。

左输入被原始代码很好地访问，因为它是行主输入，而最内部的循环增加k，所以它沿着缓存行前进。第二个矩阵被单个展开很好地访问，因为现在缓存行中的所有列都在缓存行被逐出之前被使用。

问题是结果矩阵。它也是主要行，但是缓存行是由j索引的，而不是k。你是对的..。J已经展开，所以它使用结果矩阵中缓存行上的所有元素。因此，第二次展开似乎没有任何收获。它所做的就是增加两个额外的高速缓存线。一个额外的左矩阵和一个额外的结果矩阵！它不能提高任何缓存行的元素的覆盖率！

然而，它确实碰巧重用了正确的矩阵的缓存行两次。这样就减少了需要引入正确矩阵的总次数。而且它不会增加左右矩阵缓存行将被引入的次数。所以，也许整条线的重用就是优势的来源。我想问题是，这是否被正确地阻止到缓存大小，以及缓存的集合相关性是..。如果所有三个矩阵的所有行都保留在缓存中，那么这就没有优势。(但这不会使事情变得更糟！)