学习公开课CMU-15-213Labs

Cachelab理论分析

文章目录
  1. 1. Part A 模拟 cache
  2. 2. Part B
    1. 2.1. 分块大小的确定
    2. 2.2. 初版代码
    3. 2.3. 分析 64x64 矩阵的 miss 次数
    4. 2.4. 对 64x64 矩阵的第一次优化——1699
    5. 2.5. 对 64x64 矩阵的第二次优化——1411
    6. 2.6. 对 64x64 矩阵的第二次优化——1179
  3. 3. Future work

先放一个最终结果在这里

Part A 模拟 cache

用时 3h.

一开始因为 16 进制踩了坑。我第一个看的 trace 文件是 yi.trace，我把里面的地址当成了十进制，分析了半天总感觉不对，后来惊醒这是十六进制。

part A 不难，正常模拟一遍就好。由于 handout 里说，“you should assume that memory accesses are aligned properly, such that a single memory access never crosses block boundaries”，所以对每行记录，我们只要考虑其指令类型和地址即可，不必考虑操作大小。我使用了这样的数据结构：

1
2
3
4
5
6
7
8
9
10
11
typedef struct {
    int valid;
    unsigned long lineTag;
    int lruCount; // 记录上一次访问到现在的时间
} CacheLine;

typedef struct {
    CacheLine *lines;
} CacheSet;

CacheSet *sets = malloc((1 << s)* sizeof(CacheSet));

在核心循环里，对某个给定的 set，我们在遍历过程中从前往后填充每个 set 的 line，思路如下：

对每个地址，用位运算得到其 setIdx 和 tag，然后找到对应的 set，遍历里面的所有 line. 如果找到了空 line，直接填充进去；如果找到了对应的 tag，就 hit 了；如果没找到对应 tag，说明需要驱逐某个 line，找到 lru 最大的 line（即最久没有访问过的 line）并把它换掉即可。

注意正确更新遍历的 set 里的每个 line 的 lruCount.

用下面的位运算就能得到 setIdx 和 tag：

1
2
3
4
unsigned long mask = -1;
mask = ~(mask << s); // 000...11 (s 个 1)
unsigned long setIdx = (address >> b) & mask;
unsigned long tag = address >> (b + s);

还有一个小 trick 是可以用这样的写法来简化代码，毕竟我们并不关心操作在类型上的差异，只关心操作的地址：

1
2
3
4
5
6
7
8
9
10
switch (operation) {
    case 'M':
        // M = L + S, 其 'S' 总会命中
        hits++;
        // fall through
    case 'L':
        // fall through
    case 'S':
        // 真正的工作
}

Part B

用时 7 h，拼尽全力也只能把 64x64 拿到 1411 miss，上网找了找别人的思路，最后得到了 1179 miss. 最后结果如下：

Points Max pts Misses
Trans perf 32x32 8.0 8 287
Trans perf 64x64 8.0 8 1179
Trans perf 61x67 10.0 10 1997

我参考的文章是这篇： CSAPP - Cache Lab 的更(最)优秀的解法 - 知乎，作者直接拿到了 64x64 的理论最优解，非常强大。不过我没有在对角线上做微调，而是只参考了作者对一般块的读写顺序。

我的三个转置都没有特别考虑对角线的情况。一方面是因为嫌麻烦，另一方面是因为我觉得这种“两个内存块位置恰好差 2 的幂次导致缓存抖动”的事情太特殊，所以没额外处理。

分块大小的确定

首先，分块优化是一定要做的。但分成多大的块呢？最朴素的想法是，我们希望块尽可能大来装满 cache，但不要太大以至于 cache 装不下。

我们有 $2^5 = 32$ 个 sets，每个 set 一个 line，每个 line 存 8 个 int，也就是说，我们最多能存 $32*8 = 256 = 2^8$ 个 int. 我们希望同时把 A 的块和 B 的块放到 cache 中，两个块大小应当相同，所以每个块可以放 $256/2 = 128$ 个 int. 128 不是完全平方数，所以我们可以分块成 8x8.

初版代码

回到之前的 8x8 分块的讨论上来。总之，我写出了我的初版代码。思路就是分块，然后把 A 的块存到 tmp 数组里，然后复制到 B 里。为什么要用 tmp 做中转呢？答案是为了避免缓存冲突：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
    int blockSize = 8;
    int rowBlock, colBlock, i, j;
    // 向上取整, 计算出总 block 数.
    // 可能会含有不是正方形的 block
    int rowBlocks = (N + blockSize - 1) / blockSize;
    int colBlocks = (M + blockSize - 1) / blockSize;
    int tmp[blockSize][blockSize]; // cachelab不允许开数组

    for (rowBlock = 0; rowBlock < rowBlocks; rowBlock++) {
        for (colBlock = 0; colBlock < colBlocks; colBlock++) {
            for (i = rowBlock * blockSize; i < (rowBlock + 1) * blockSize && i < N; i++) {
                for (j = colBlock * blockSize; j < (colBlock + 1) * blockSize && j < M; j++) {
                    tmp[j - colBlock * blockSize][i - rowBlock * blockSize] = A[i][j];
                }
            }
            for (j = colBlock * blockSize; j < (colBlock + 1) * blockSize && j < M; j++) {
                for (i = rowBlock * blockSize; i < (rowBlock + 1) * blockSize && i < N; i++) {
                    B[j][i] = tmp[j - colBlock * blockSize][i - rowBlock * blockSize];
                }
            }
        }
    }
}

结果很不错：

Cache Lab summary:
Points Max pts Misses
Trans perf 32x32 8.0 8 261
Trans perf 64x64 8.0 8 1029
Trans perf 61x67 10.0 10 1725

正当我觉得 cachelab 不过如此的时候，忽然发现 handout 里写了不允许开数组（哈哈，你想得到的 cmu 老师想不到吗），于是被迫手动展开了 j 循环，使用 8 个变量来读取每行的值。这就得到了下面的结果：

Cache Lab summary:
Points Max pts Misses
Trans perf 32x32 8.0 8 287
Trans perf 64x64 0.0 8 4611
Trans perf 61x67 10.0 10 1997

也还算不错吧，毕竟 32x32 和 61x67 都满分了。唯一的问题是 64x64 的性能奇差无比。

分析 64x64 矩阵的 miss 次数

这时候就要理论分析了。对 64x64 的矩阵，按我们之前的做法，每个 8x8 的块大约发生了多少次 miss 呢？

答案是 72 次。A 提供了 8 次 miss，B 提供了 64 次 miss

验证一下结果对不对：64x64 的矩阵共有 64 个 8x8 的块，64 个块每个块 72 次 miss，总计约 $64*72=4608$ 次 miss，和结果 4611 次 miss 相差无几。

这个 miss 是怎么算出来的呢？让我们看看下图：

对 64x64 的矩阵来说，B[x][y] 和 B[x+4][y] 的 setIdx 相同，这就导致我们之前的方法不断驱逐旧 line. 定量地说，每读 A 的块的一行，大约是 1 个 miss，A 的块共有 8 行，所以 A 的每个块提供 8 次 miss；每对 B 的块写入一个值，都驱逐了一次旧 line（因为 B[x+4][y] 会驱逐 B[x][y]），所以 B 的每个块提供 64 次 miss.

之后的工作就是找到方法来避免这种驱逐了。

对 64x64 矩阵的第一次优化——1699

一开始我的思路是直接用 4x4 的块，这确实有不小优化，但离满分还很远。读者可以试着做一个理论分析看看 4x4 的结果大概是多少 miss。我分析出来会得到 1536 个 miss，实际结果是 1699 个 miss，也差不多吧。

好吧，这个理论分析看起来值得详细讲解一下。不过在写之前，希望读者自己分析一下，看看得到的结果是不是 2048，并想想哪里出错了：

如果块的大小是 4x4，每个块发生 4 次 miss，每个矩阵 256 个块，一共 2048 次 miss，看起来很合理。但这是理论最优解，为什么理论最优（2048）比实际结果（1699）还差呢？难道说数学的大厦崩塌了？

并非如此。事实上，在我们把某个 4x4 的块放入 cache 时，我们也同时把它的右边的那个 4x4 的块放入了 cache。这是因为 cache 的每个 line 能装 8 个 int.

也就是说，我们可以认为我们实际上是在处理 4x8 的块。对每个 4x8 的块，A 提供了 4 次 miss，B 提供了 8 次 miss，总计 $64 * 4 + 64 * 8 = 1536$ 次 miss.

对 64x64 矩阵的第二次优化——1411

分析了那么多，还是没拿到满分。我的后续思路是把 8x8 的块再分成四个小块，并按下面的顺序来写入 B：

理论分析一下，把 A1 写入 B1 时，A miss 4 次，B miss 4 次；

把 A2 写入 B2 时，A miss 4 次，B 没有 miss（因为写入 B1 时把 B2 放进了 cache）；

把 A3 写入 B3 时，A 没有 miss，B miss 4 次；（因为读 A2 时把 A3 放入了 cache）；

把 A4 写入 B4 时，A miss 4 次，B 没有 miss（因为写入 B3 时把 B4 放进了 cache）

总计 20 次 miss，理论最优解 1280，实际结果 1411，我猜问题出在对角线上，我也懒得在这个基础上继续优化了。优化对角线这种事情看起来就很麻烦，而且感觉现实里几乎不会遇见这种情况。

对 64x64 矩阵的第二次优化——1179

没什么好说的，直接看 CSAPP - Cache Lab 的更(最)优秀的解法 - 知乎 和代码吧。这篇文章的作者拿到了 64x64 的理论最优解，非常强大。不过我没有在对角线上做微调，而是只参考了作者对一般块的读写顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
void transpose_submit_64x64(int M, int N, int A[N][M], int B[M][N])
{
    int blockSize = 8;
    int rowBlock, colBlock, i, j;
    int rowBlocks = (N + blockSize - 1) / blockSize;
    int colBlocks = (M + blockSize - 1) / blockSize;
    int tmp0, tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7;

    for (rowBlock = 0; rowBlock < rowBlocks; rowBlock++) {
        for (colBlock = 0; colBlock < colBlocks; colBlock++) {
            // A上
            for (i = rowBlock * blockSize; i < rowBlock * blockSize + blockSize / 2 && i < N; i++) {
                // 读取A的一行
                tmp0 = A[i][colBlock * blockSize];
                tmp1 = A[i][colBlock * blockSize + 1];
                tmp2 = A[i][colBlock * blockSize + 2];
                tmp3 = A[i][colBlock * blockSize + 3];
                tmp4 = A[i][colBlock * blockSize + 4];
                tmp5 = A[i][colBlock * blockSize + 5];
                tmp6 = A[i][colBlock * blockSize + 6];
                tmp7 = A[i][colBlock * blockSize + 7];

                // 填充B左上
                B[colBlock * blockSize][i] = tmp0;
                B[colBlock * blockSize + 1][i] = tmp1;
                B[colBlock * blockSize + 2][i] = tmp2;
                B[colBlock * blockSize + 3][i] = tmp3;
                // 填充B右上, 这一部分未来会被放到B左下
                B[colBlock * blockSize][i + blockSize / 2] = tmp4;
                B[colBlock * blockSize + 1][i + blockSize / 2] = tmp5;
                B[colBlock * blockSize + 2][i + blockSize / 2] = tmp6;
                B[colBlock * blockSize + 3][i + blockSize / 2] = tmp7;
            }
            // A左下, 注意这里按列遍历
            for (j = colBlock * blockSize; j < colBlock * blockSize + blockSize / 2 && j < M; j++) {
                // 读取 A 的左下小块的一列
                tmp0 = A[rowBlock * blockSize + blockSize / 2][j];
                tmp1 = A[rowBlock * blockSize + blockSize / 2 + 1][j];
                tmp2 = A[rowBlock * blockSize + blockSize / 2 + 2][j];
                tmp3 = A[rowBlock * blockSize + blockSize / 2 + 3][j];
                // 读取 B 的右上小块的一行
                tmp4 = B[j][rowBlock * blockSize + blockSize / 2];
                tmp5 = B[j][rowBlock * blockSize + blockSize / 2 + 1];
                tmp6 = B[j][rowBlock * blockSize + blockSize / 2 + 2];
                tmp7 = B[j][rowBlock * blockSize + blockSize / 2 + 3];

                // 把从 A 左下读到的内容写到 B 右上
                B[j][rowBlock * blockSize + blockSize / 2] = tmp0;
                B[j][rowBlock * blockSize + blockSize / 2 + 1] = tmp1;
                B[j][rowBlock * blockSize + blockSize / 2 + 2] = tmp2;
                B[j][rowBlock * blockSize + blockSize / 2 + 3] = tmp3;
                // 把 B 右上的内容写到 B 左下
                B[j + blockSize / 2][rowBlock * blockSize] = tmp4;
                B[j + blockSize / 2][rowBlock * blockSize + 1] = tmp5;
                B[j + blockSize / 2][rowBlock * blockSize + 2] = tmp6;
                B[j + blockSize / 2][rowBlock * blockSize + 3] = tmp7;
            }
            // A右下
            for (i = rowBlock * blockSize + blockSize / 2; i < (rowBlock + 1) * blockSize && i < N; i++) {
                // 读取A的一行
                tmp0 = A[i][colBlock * blockSize + blockSize / 2];
                tmp1 = A[i][colBlock * blockSize + blockSize / 2 + 1];
                tmp2 = A[i][colBlock * blockSize + blockSize / 2 + 2];
                tmp3 = A[i][colBlock * blockSize + blockSize / 2 + 3];

                // 填充B
                B[colBlock * blockSize + blockSize / 2][i] = tmp0;
                B[colBlock * blockSize + blockSize / 2 + 1][i] = tmp1;
                B[colBlock * blockSize + blockSize / 2 + 2][i] = tmp2;
                B[colBlock * blockSize + blockSize / 2 + 3][i] = tmp3;
            }
        }
    }
}

Future work

写文章的时候突然想到我们似乎可以分长方形的 16x8 的块，因为 $1682 = 256$ 可以完全填满 cache. 简单写了下代码得到了下面的结果：

[16x8]
Points Max pts Misses
Trans perf 32x32 8.0 8 287
Trans perf 61x67 10.0 10 1811
看起来效果出乎意料地不错？甚至比我的 8x8 分块效果更好。这里没有放进来 64x64 转置的结果，因为我没有做分小块的优化。所以说，这种方法说不定还有不小探索空间？

下面是我的 8x8 分块的结果，可以用来和上面的结果做比较。两个代码都只用了简单的分块和 8 个 tmp 变量，没有额外优化。

[8x8]

Points Max pts Misses
Trans perf 32x32 8.0 8 287
Trans perf 61x67 10.0 10 1997

这里是我使用的 16x8 的分块代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
    int blockRow = 16;    // 块的行数
    int blockCol = 8;   // 块的列数
    int rowBlock, colBlock, i, j;
    // 向上取整, 计算出总 block 数
    int rowBlocks = (N + blockRow - 1) / blockRow;
    int colBlocks = (M + blockCol - 1) / blockCol;

    int tmp0, tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7;

    for (rowBlock = 0; rowBlock < rowBlocks; rowBlock++) {
        for (colBlock = 0; colBlock < colBlocks; colBlock++) {
            for (i = rowBlock * blockRow; i < (rowBlock + 1) * blockRow && i < N; i++) {
                // 展开j循环，每次处理8个元素
                j = colBlock * blockCol;
                if (j < M) tmp0 = A[i][j];
                if (j + 1 < M) tmp1 = A[i][j + 1];
                if (j + 2 < M) tmp2 = A[i][j + 2];
                if (j + 3 < M) tmp3 = A[i][j + 3];
                if (j + 4 < M) tmp4 = A[i][j + 4];
                if (j + 5 < M) tmp5 = A[i][j + 5];
                if (j + 6 < M) tmp6 = A[i][j + 6];
                if (j + 7 < M) tmp7 = A[i][j + 7];

                // 写入B矩阵
                if (j < M) B[j][i] = tmp0;
                if (j + 1 < M) B[j + 1][i] = tmp1;
                if (j + 2 < M) B[j + 2][i] = tmp2;
                if (j + 3 < M) B[j + 3][i] = tmp3;
                if (j + 4 < M) B[j + 4][i] = tmp4;
                if (j + 5 < M) B[j + 5][i] = tmp5;
                if (j + 6 < M) B[j + 6][i] = tmp6;
                if (j + 7 < M) B[j + 7][i] = tmp7;
            }
        }
    }
}