CSAPP第六章 - 存储器层次结构

这里仅保留了 Cache Lab 的内容，其他更多内容搬到了 https://www.caiwen.work/post/408-cs-storage

1. Cache Lab

1.1 Part A

第一部分要求我们手动实现一个缓存的模拟器，还是比较简单的：

c
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include "cachelab.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef unsigned long long u64;

typedef struct {
    int valid, last_time;
    u64 tag;
} CacheRow;

typedef struct {
    CacheRow *rows;
} CacheGroup;

int s, E, b, time_stamp, group_cnt, hit_cnt, miss_cnt, eviction_cnt;
char *file_name;
CacheGroup *groups;

int str2int(char *str) {
    int len = strlen(str);
    int res = 0;
    for (int i = 0; i < len; i ++){
        res *= 10;
        res += str[i] - '0';
    }
    return res;
}
// int hex2int(char *str) {
//     int len = strlen(str);
//     int res = 0;
//     for (int i = 0; i < len; i ++) {
//         res *= 16;

//     }
//     return res;
// }
void parseArguments(int argc, char* argv[]) {
    for (int i = 1; i < argc; i += 2) {
        if (argv[i][1] == 't') {
            file_name = argv[i + 1];
        } else {
            int val = str2int(argv[i + 1]);
            switch (argv[i][1]) {
                case 's':
                    s = val;
                    break;
                case 'E':
                    E = val;
                    break;
                case 'b':
                    b = val;
                    break;
            }
        }
    }
    group_cnt = 1 << s;
}
void initCache() {
    groups = malloc(sizeof(CacheGroup) * group_cnt);
    for (int i = 0; i < group_cnt; i ++) {
        CacheRow *rows = malloc(sizeof(CacheRow) * E);
        for (int j = 0; j < E; j ++) {
            rows[j].valid = 0;
        }
        groups[i].rows = rows;
    }
}
void touchCache(u64 group_index, u64 tag) {
    time_stamp ++;
    CacheRow *rows = groups[group_index].rows;
    for (int i = 0; i < E; i ++) {
        if (rows[i].valid && rows[i].tag == tag) {
            hit_cnt ++;
            rows[i].last_time = time_stamp;
            return;
        }
    }
    miss_cnt ++;
    for (int i = 0; i < E; i ++) {
        if (!rows[i].valid) {
            rows[i].valid = 1;
            rows[i].tag = tag;
            rows[i].last_time = time_stamp;
            return;
        }
    }
    eviction_cnt ++;
    int eviction_target = 0;
    for (int i = 1; i < E; i ++) {
        if (rows[i].last_time < rows[eviction_target].last_time) {
            eviction_target = i;
        }
    }
    rows[eviction_target].tag = tag;
    rows[eviction_target].last_time = time_stamp;
}
void readTrace() {
    FILE *file = fopen(file_name, "r");
    char line[256];
    while (fgets(line, sizeof(line), file)) {
        if (line[0] == 'I') continue;
        int len = strlen(line);
        char op = line[1];
        u64 addr = 0;
        for (int i = 3; i < len; i ++) {
            if (line[i] == ',') break;
            addr *= 16;
            if (line[i] <= '9') addr += line[i] - '0';
            else addr += line[i] - 'a' + 10;
        }
        //u64 block_index = addr & (((u64)1 << b) - 1);
        u64 group_index = (addr >> b) & (((u64)1 << s) - 1);
        u64 tag = addr >> (b + s);
        if (op == 'L' || op == 'S') touchCache(group_index, tag);
        else if (op == 'M') touchCache(group_index, tag), touchCache(group_index, tag);
    }
}
int main(int argc, char* argv[])
{
    parseArguments(argc, argv);
    initCache();
    readTrace();
    printSummary(hit_cnt, miss_cnt, eviction_cnt);
    return 0;
}

1.2 Part B

这一部分要求我们去优化一个矩阵转置函数，使其缓存的不命中次数尽可能少。输入的矩阵大小只有 $32\times 32$ 、$64\times 64$、$61\times 67$ 三种，允许我们针对这三种特定情况进行优化。

为了方便观察内存地址的访问情况，我写了个 rust 程序，可以将 trace 中每个地址的标记、组索引、块偏移计算出来：

rust
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
use std::io::BufRead;

fn main() {
    let mut lines = vec![];
    let mut max_line_len = 0;
    for line in std::io::stdin().lock().lines() {
        let line = line.unwrap();
        if !line.starts_with('L') && !line.contains('S') {
            continue;
        }
        max_line_len = max_line_len.max(line.len());
        lines.push(line);
    }
    max_line_len += 2;
    for line in lines {
        let part: u64 = line
            .split_ascii_whitespace()
            .filter(|s| s.len() >= 2)
            .collect::<Vec<_>>()
            .join("")
            .split(',')
            .next()
            .unwrap()
            .chars()
            .map(|c| c.to_digit(16).unwrap() as u64)
            .fold(0u64, |acc, d| acc * 16 + d) as u64;
        let block_index = part & ((1 << 5) - 1);
        let group_index = (part >> 5) & ((1 << 5) - 1);
        let tag = part >> 10;
        println!("{}{}{:015b} {:05b} {:05b}\ttag={},group={}", line, " ".repeat(max_line_len - line.len()), tag, group_index, block_index, tag, group_index);
    }
}

然后我们可以这么运行：

bash
1
2
3
make
./test-trans -N 32 -M 32
./csim-ref -v -s 5 -E 1 -b 5 -t trace.f1 | cargo run > trace_fmt

然后在 trace_fmt 文件中就可以看到相应的信息了：

1.2.1 32 x 32

上图展示了最朴素的转置函数的缓存命中情况。从第六行开始应该是和转置函数有关。其中 L 开头的应该是访问数组 A，S 开头的应该是访问数组 B。我们发现后者基本从来没命中过缓存，而前者缓存命中率很高。

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
 * trans - A simple baseline transpose function, not optimized for the cache.
 */
char trans_desc[] = "Simple row-wise scan transpose";
void trans(int M, int N, int A[N][M], int B[M][N])
{
    int i, j, tmp;

    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) {
            tmp = A[i][j];
            B[j][i] = tmp;
        }
    }

}

原因也很明显，对 A 的访问是连续的，但是由于对 B 的访问是跳行的，所以 B 一次的访问根本用不到上次的访问时加载的缓存。

实验的文档中给了个提示，说是分块技术可能对实验有帮助。我没仔细看，只是大概了解了一下分块的思想，并想到了优化方案。由于缓存的块偏移有 $b=5$ 位，int 大小为 4 字节，所以每个缓存行可以缓存 $\frac{2^5}{4} = 8$ 个元素。我们按 $8\times8$ 的分块大小将 $32\times 32$ 的矩阵划分成 $4\times 4$ 部分。对于一个块的全部元素进行置换，被置换的元素仍在 B 中的某个块中。

对于一个块，我们先把他一行的全部元素进行读取，存到变量中。然后我们再按列方向，把置换后的元素写入 B 的对应位置，由于是按列，缓存可能全没有命中（比如第一次时），但是此时 B 的块中的每一行都被载入缓存了。然后我们再从 A 中读取下一行，因为缓存仍未命中，于是将这一行加入缓存（假设加入了缓存组 $x$），然后再把这一行元素全部读取到变量。接下来在 B 中按列方向进行写入时，由于上一次已经把 B 的块中的每一行载入缓存了，所以大部分的缓存都是命中的，唯独缓存组 $x$ 对应的那个行，被 A 中元素覆盖了，未命中缓存。这样一来，我们的缓存命中次数会很高。

c
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
/*
 * transpose_submit - This is the solution transpose function that you
 *     will be graded on for Part B of the assignment. Do not change
 *     the description string "Transpose submission", as the driver
 *     searches for that string to identify the transpose function to
 *     be graded.
 */
char transpose_submit_desc[] = "Transpose submission";
void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
    int col, row, p, e1, e2, e3, e4, e5, e6, e7, e8;

    for (row = 0; row < N; row += 8) {
        for (col = 0; col < M; col += 8) {
            for (p = 0; p < 8; p ++) {
                e1 = A[row + p][col];
                e2 = A[row + p][col + 1];
                e3 = A[row + p][col + 2];
                e4 = A[row + p][col + 3];
                e5 = A[row + p][col + 4];
                e6 = A[row + p][col + 5];
                e7 = A[row + p][col + 6];
                e8 = A[row + p][col + 7];
                B[col][row + p] = e1;
                B[col + 1][row + p] = e2;
                B[col + 2][row + p] = e3;
                B[col + 3][row + p] = e4;
                B[col + 4][row + p] = e5;
                B[col + 5][row + p] = e6;
                B[col + 6][row + p] = e7;
                B[col + 7][row + p] = e8;
            }
        }
    }
}

测试的 misses 只有 288

1.2.2 64 x 64

当矩阵大小为 $64\times 64$ 时，上面的优化方案竟然和朴素做法相差不大。

实际上，$32\times 32$ 时，每个元素会存放到的缓存组分布如下：

Unknown
1
2
3
4
5
6
7
8
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 0
1  2  3  4

其中每行代表一个元素，每列代表 8 个元素。

而 $64\times 64$ 时，则为：

Unknown
1
2
3
4
5
6
7
8
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 0  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 0  1  2  3  4

前者 $8\times 8$ 的一个块中，列方向有 $8$ 个不同的缓存组。而后者只有 $4$ 个不同的缓存组。在按列方向写 B 时，后 4 行会因为与前 4 行共用了一个缓存组，导致缓存命中率很低（甚至根本无法命中）

一个方案是我们改成 $4\times 4$ 分块。但是这样做 misses 还是有 1700，无法获得满分

我们在列方向上最多只能反复写 $4$ 行，不然缓存就会不断地载入又被驱逐

所以一个想法是使用 $8\times 4$ 的分块，这样做 misses 有 1600 多。随后我加了一点优化：

我们按绿色箭头的方向进行读取，而不是一律从上到下进行读取。因为读完最后一个的时候，整个行上的 $8$ 个元素都载入到缓存了，这样做可以增大缓存的利用率。

同时，我考虑每次读两行，这样可能能够减少缓存不命中。于是有了如下代码：

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
for (row = 0; row < N; row += 8) {
    now = 0;
    for (col = 0; col < row; col += 4) {
        for (now? (p = 8 - 1) : (p = 0); now? (p >= 0) : (p < 8); now? (p -= 2) : (p += 2)) {
            e1 = A[row + p][col];
            e2 = A[row + p][col + 1];
            e3 = A[row + p][col + 2];
            e4 = A[row + p][col + 3];
            e5 = A[row + p + (now? -1:1)][col];
            e6 = A[row + p + (now? -1:1)][col + 1];
            e7 = A[row + p + (now? -1:1)][col + 2];
            e8 = A[row + p + (now? -1:1)][col + 3];
            B[col][row + p] = e1;
            B[col + 1][row + p] = e2;
            B[col + 2][row + p] = e3;
            B[col + 3][row + p] = e4;
            B[col][row + p + (now? -1:1)] = e5;
            B[col + 1][row + p + (now? -1:1)] = e6;
            B[col + 2][row + p + (now? -1:1)] = e7;
            B[col + 3][row + p + (now? -1:1)] = e8;
        }
        now = 1 - now;
    }
}

这样做的 misses 为 1412，距离满分还差一点距离。

后续实验就遇到了瓶颈。经过观察，我们发现，如果把 $64\times 64$ 的矩阵按 $8\times 8$ 划分之后

非对角线上，置换前后位置使用的是不同的缓存组，而对角线上则相反。因此，很多 misses 是由于对角线上置换导致的冲突不命中。

一个对角线块上，会进行两次对于 $8\times 4$ 分块的运算。每次处理 $8\times 4$ 分块都会带来大约 $(4 + 1) + (1 + 1) \times 7=19$ 的缓存不命中次数。那么一个对角线块就产生 $38$ 次缓存不命中。

接下来的关注点就在于如何科学地处理对角线块。中间我试了很多种神奇的处理方式，但经过计算和代码验证都不如目前的 $8\times 4$ 分块。

想了很久之后我突然有一个想法，我们能否把一个对角线块置换后的结果先放入 B 中的一个区域中，然后再把这个区域复制到其正确的位置上。这个区域就充当一个中转功能，并且由于使用和对角线块不同的缓存组，缓存的冲突不命中次数将会很低。

后来经过尝试发现，我们不能直接把对角线块的置换结果放入中转区域，因为我们按行读对角线块的时候，中转区域是按列方向，反复对 $8$ 行进行写入，这会和 $8\times 8$ 分块一样带来严重的冲突不命中。

不过后续我很快想到了解决方案，我们可以选定两个 $4\times 8$ 的中转区域，然后把对角线块按 $4\times 4$ 划分成四个区域，将置换结果放入中转区域中。这样做的话，对于每个对角线块，我们只会带来 $8+8+8=24$ 个缓存不命中。实际上，由于我们会反复利用同一个中转区域，后续由于写中转区域所带来的缓存不命中基本没有。同时我们合理调整写入顺序的话，缓存不命中次数还能更少。

这里我选择前 $4$ 行最靠右的两个区域作为中转区域：

注意转置的时候我们是一行一行的来，因为 AB 和 CD 之间的使用同一个缓存组。从中转区域复制回来的时候要先复制下面一行，因为我们之前是后处理下面一行的，这样还能利用上之前的缓存。

不过这样会有个问题，就是当处理倒数两个对角线块的时候，对角线块使用的缓存组和中转区域的缓存组冲突，会导致严重的冲突不命中。所以我们需要特殊处理，改为选用别的中转区域来处理最后两个对角线块

c
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
    int col, row, now = 0, p, e1, e2, e3, e4, e5, e6, e7, e8;
    // 单独处理对角块
    // 我们选择前 8 行的后 16 列作为中转块
    for (p = 0; p < N - 16; p += 8) {
        // 左上
        for (row = p; row < p + 4; row ++) {
            for (col = p; col < p + 4; col ++) {
                now = A[row][col];
                B[col - p][row - p + 48] = now;
            }
        }
        // 右上
        for (row = p; row < p + 4; row ++) {
            for (col = p + 4; col < p + 8; col ++) {
                now = A[row][col];
                B[col - p - 4][row - p + 48 + 4] = now;
            }
        }
        // 左下
        for (row = p + 4; row < p + 8; row ++) {
            for (col = p; col < p + 4; col ++) {
                now = A[row][col];
                B[col - p][row - p + 56 - 4] = now;
            }
        }
        // 右下
        for (row = p + 4; row < p + 8; row ++) {
            for (col = p + 4; col < p + 8; col ++) {
                now = A[row][col];
                B[col - p - 4][row - p + 56] = now;
            }
        }
        // 然后复制回来
        // B
        for (row = 0; row < 4; row ++) {
            for (col = 48 + 4; col < 48 + 8; col ++) {
                now = B[row][col];
                B[row + p + 4][col - 48 + p - 4] = now;
            }
        }
        // D
        for (row = 0; row < 4; row ++) {
            for (col = 56 + 4; col < 56 + 8; col ++) {
                now = B[row][col];
                B[row + p + 4][col - 56 + p] = now;
            }
        }
        // A
        for (row = 0; row < 4; row ++) {
            for (col = 48; col < 48 + 4; col ++) {
                now = B[row][col];
                B[row + p][col - 48 + p] = now;
            }
        }
        // C
        for (row = 0; row < 4; row ++) {
            for (col = 56; col < 56 + 4; col ++) {
                now = B[row][col];
                B[row + p][col - 56 + p + 4] = now;
            }
        }
    }
    // 最后两个对角线需要再特殊处理一下
    for (p = N - 16; p < N; p += 8) {
        // 左上
        for (row = p; row < p + 4; row ++) {
            for (col = p; col < p + 4; col ++) {
                now = A[row][col];
                B[col - p][row - p + 8] = now;
            }
        }
        // 右上
        for (row = p; row < p + 4; row ++) {
            for (col = p + 4; col < p + 8; col ++) {
                now = A[row][col];
                B[col - p - 4][row - p + 8 + 4] = now;
            }
        }
        // 左下
        for (row = p + 4; row < p + 8; row ++) {
            for (col = p; col < p + 4; col ++) {
                now = A[row][col];
                B[col - p][row - p + 16 - 4] = now;
            }
        }
        // 右下
        for (row = p + 4; row < p + 8; row ++) {
            for (col = p + 4; col < p + 8; col ++) {
                now = A[row][col];
                B[col - p - 4][row - p + 16] = now;
            }
        }
        // 然后复制回来
        // B
        for (row = 0; row < 4; row ++) {
            for (col = 8 + 4; col < 8 + 8; col ++) {
                now = B[row][col];
                B[row + p + 4][col - 8 + p - 4] = now;
            }
        }
        // D
        for (row = 0; row < 4; row ++) {
            for (col = 16 + 4; col < 16 + 8; col ++) {
                now = B[row][col];
                B[row + p + 4][col - 16 + p] = now;
            }
        }
        // A
        for (row = 0; row < 4; row ++) {
            for (col = 8; col < 8 + 4; col ++) {
                now = B[row][col];
                B[row + p][col - 8 + p] = now;
            }
        }
        // C
        for (row = 0; row < 4; row ++) {
            for (col = 16; col < 16 + 4; col ++) {
                now = B[row][col];
                B[row + p][col - 16 + p + 4] = now;
            }
        }
    }
    for (row = 0; row < N; row += 8) {
        // 对角线之前
        now = 0;
        for (col = 0; col < row; col += 4) {
            for (now? (p = 8 - 1) : (p = 0); now? (p >= 0) : (p < 8); now? (p -= 2) : (p += 2)) {
                e1 = A[row + p][col];
                e2 = A[row + p][col + 1];
                e3 = A[row + p][col + 2];
                e4 = A[row + p][col + 3];
                e5 = A[row + p + (now? -1:1)][col];
                e6 = A[row + p + (now? -1:1)][col + 1];
                e7 = A[row + p + (now? -1:1)][col + 2];
                e8 = A[row + p + (now? -1:1)][col + 3];
                B[col][row + p] = e1;
                B[col + 1][row + p] = e2;
                B[col + 2][row + p] = e3;
                B[col + 3][row + p] = e4;
                B[col][row + p + (now? -1:1)] = e5;
                B[col + 1][row + p + (now? -1:1)] = e6;
                B[col + 2][row + p + (now? -1:1)] = e7;
                B[col + 3][row + p + (now? -1:1)] = e8;
            }
            now = 1 - now;
        }
        // 对角线之后
        for (col = row + 8; col < M; col += 4) {
            for (now? (p = 8 - 1) : (p = 0); now? (p >= 0) : (p < 8); now? (p -= 2) : (p += 2)) {
                e1 = A[row + p][col];
                e2 = A[row + p][col + 1];
                e3 = A[row + p][col + 2];
                e4 = A[row + p][col + 3];
                e5 = A[row + p + (now? -1:1)][col];
                e6 = A[row + p + (now? -1:1)][col + 1];
                e7 = A[row + p + (now? -1:1)][col + 2];
                e8 = A[row + p + (now? -1:1)][col + 3];
                B[col][row + p] = e1;
                B[col + 1][row + p] = e2;
                B[col + 2][row + p] = e3;
                B[col + 3][row + p] = e4;
                B[col][row + p + (now? -1:1)] = e5;
                B[col + 1][row + p + (now? -1:1)] = e6;
                B[col + 2][row + p + (now? -1:1)] = e7;
                B[col + 3][row + p + (now? -1:1)] = e8;
            }
            now = 1 - now;
        }
    }

misses 只有 1268，获得满分

1.2.3 61 x 67

感觉这种情况下，矩阵每个位置使用的缓存组很没有规律。我甚至还用 react 画了一下分布情况：

果然很没有规律。

我考虑直接沿用之前的 $8\times 8$ 的分块，之后整个矩阵还有最右边和最下面有一块没有覆盖到。再单独开一个循环处理。处理最右边的部分时我们逐行处理，处理最下面的部分时我们逐列处理。这样做的 misses 为 2066，很接近满分。

于是我又试了一下其他大小的分块，效果都没有 $8\times 8$ 的好。考虑到目前已经开了 $11$ 个变量，于是打算把 $12$ 个变量的限制用满，再开一个变量，搞个 $9\times 9$ 的分块：

c
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
const int BLOCK_N = 9;
const int BLOCK_M = 9;
const int LIMIT_N = 61 / BLOCK_N * BLOCK_N;
const int LIMIT_M = 67 / BLOCK_M * BLOCK_M;
//const int REM_N = 61 - LIMIT_N;
//const int REM_M = 67 - LIMIT_M;
int col, row, p, e1, e2, e3, e4, e5, e6, e7, e8, e9;
for (row = 0; row < LIMIT_N; row += BLOCK_N) {
    for (col = 0; col < LIMIT_M; col += BLOCK_M) {
        for (p = 0; p < BLOCK_N; p ++) {
            e1 = A[row + p][col];
            e2 = A[row + p][col + 1];
            e3 = A[row + p][col + 2];
            e4 = A[row + p][col + 3];
            e5 = A[row + p][col + 4];
            e6 = A[row + p][col + 5];
            e7 = A[row + p][col + 6];
            e8 = A[row + p][col + 7];
            e9 = A[row + p][col + 8];
            B[col][row + p] = e1;
            B[col + 1][row + p] = e2;
            B[col + 2][row + p] = e3;
            B[col + 3][row + p] = e4;
            B[col + 4][row + p] = e5;
            B[col + 5][row + p] = e6;
            B[col + 6][row + p] = e7;
            B[col + 7][row + p] = e8;
            B[col + 8][row + p] = e9;
        }
    }
}
for (row = 0; row < N; row++) {
    for (col = LIMIT_M; col < M; col++) {
        B[col][row] = A[row][col];
    }
}
for (col = 0; col < LIMIT_M; col ++){
    for (row = LIMIT_N; row < N; row++) {
        B[col][row] = A[row][col];
    }
}

结果 misses 直接到 1992，直接满分，比想象的简单（）

（后来发现做反了，应该是 67 行，61 列，但是做法还是正确的）