c - "Blocking"使代码缓存友好的方法

Question

嘿，所以我正在查看矩阵移位代码，并且需要使其缓存友好(尽可能少的缓存未命中)。代码如下所示:

int i, j, temp;
for(i=1;, i< M; i++){
    for(j=0; j< N; j++){
        temp = A[i][j];
        A[i][j] = A[i-1][j];
        A[i-1]][j] = temp;
    }
}

假设 M 和 N 是函数的参数，注意 M 是行数，N 是列数。现在为了使缓存更友好，本书给出了两个优化问题。当矩阵为4x4时，s=1，E=2，b=3，当矩阵为128x128时，s=5，E=2，b=3。(s = # of set index bits (S = s^2 is the number of sets, E = number of lines per set, and b = # of block bits (so B = b^2 is block size))

因此使用分块方法，我应该按 block 大小访问矩阵，以避免丢失，并且缓存必须从更高级别的缓存中获取信息。所以这就是我的假设:

每个 block 大小为 9 个字节

对于 4x4 矩阵，均匀地适合一个 block 的元素数量为: block 大小*(列数/ block 大小) = 9*(4/9) = 4因此，如果每一行都适合一个 block ，为什么缓存不友好？

对于 128x128 矩阵，使用与上述相同的逻辑，每个 block 将包含 (9*(128/9)) = 128。

很明显，经过计算，这个等式是错误的。我正在查看此页面中的代码 http://csapp.cs.cmu.edu/public/waside/waside-blocking.pdf

一旦我达到这一点，我就知​​道我迷路了，这就是你们进来的地方!是否就像说每个 block 包含 9 个字节一样简单，而 8 个字节(两个整数)是均匀地放入其中的？抱歉，这些东西真的让我很困惑，我知道我到处都是。需要明确的是，这些是我的担忧:

您如何知道一个 block 中可以容纳多少个元素？行数或集合数会影响这个数字吗？如果是这样，如何？对链接页面上发布的代码的任何深入解释。

真的只是想了解这一点。

更新:好的，这就是我要处理 4x4 矩阵的地方。

我一次可以读取8个字节，也就是2个整数。原始函数将有缓存未命中，因为 C 加载到行优先顺序，所以每次它想要 A[i-1][j] 时它都会丢失，并加载包含 A[i-1][j] 的 block 要么是 A[i-1][0] 和 A[i-1][1]，要么是 A[i-1][2] 和 A[i-1][3]。

因此，解决这个问题的最佳方法是创建另一个临时变量，并执行 A[i][0] = temp、A[i][1] = temp2，然后加载 A[i-1] [0] A[i-1][1] 并将它们设置为 temp，以及 temp2 并将循环设置为 j<2？对于这道题，专门针对描述的矩阵；我知道这不适用于所有尺寸。

Answer 1

这个问题的解决方案是以列主序而不是行主序来考虑矩阵。

希望这对将来的人有所帮助。感谢@Michael Dorgan 让我思考。

128x128 矩阵的最终结果:原文:16218未命中优化:8196 次未命中