0

我正在阅读Ulrich Drepper 的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由列访问，因此对于每一列，一个缓存行被浪费了。乌尔里希 说：

sizeof(double) 为 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是按列访问的。请解释乌尔里希的意思。

4

1 回答 1

1

缓存中包含三个矩阵：左输入、右输入和结果。

原始代码可以很好地访问左侧输入，因为它是行优先的，并且最内层循环递增 k，因此它沿着缓存线行进。第二个矩阵可以通过单次展开很好地访问，因为现在所有列都在在缓存行被驱逐之前使用缓存行..

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

但是，它确实碰巧重用了两次右矩阵的缓存行。这减少了必须引入右矩阵的行的总次数。并且它不会增加左右矩阵缓存的次数行将被引入..所以也许整个行的重用是优势的来源..我想问题是这是否被正确阻止到缓存大小，以及缓存的集合关联性是什么..如果所有三个矩阵的所有行都保留在缓存中，那么这没有任何优势..（但这不会让任何事情变得更糟！）

于 2014-02-04T04:08:30.767 回答