CSAPP Cache Lab

Cache Lab 的内容有两部分,分别是实现一个 LRU 缓存,另一部分是通过 Blocking 方法优化矩阵转置算法。

Part A

调用getopt解析参数,然后用链表实现 LRU 即可,由于不关心复杂度,所以实现方式比较自由。主要是注意M操作的处理,指导书里有提及。

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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <getopt.h>
#include "cachelab.h"

typedef struct row
{
int tag;
struct row *next;
} Row;

typedef struct set
{
int count;
struct row *head;
} Set;

int s, E, b, v;
int hits, misses, evictions;
Set *sets;
FILE *file;

void parseArguments(int argc, char *argv[]);
void init();
void work();
Row *find(Row *head, int tag);
void del(Row **phead, Row *row);
void insert(Row **phead, int tag);

int main(int argc, char *argv[])
{
parseArguments(argc, argv);
init();
work();
printSummary(hits, misses, evictions);
fclose(file);
return 0;
}

void parseArguments(int argc, char *argv[])
{
char c;
while ((c = getopt(argc, argv, "vs:E:b:t:")) != -1)
{
switch (c)
{
case 'v':
v = 1;
break;
case 's':
s = atoi(optarg);
break;
case 'E':
E = atoi(optarg);
break;
case 'b':
b = atoi(optarg);
break;
case 't':
file = fopen(optarg, "r");
break;
case '?':
default:
break;
}
}
}

void init()
{
sets = calloc(1 << s, sizeof(Set));
for (int i = 0; i < (1 << s); ++i)
{
sets[i].count = 0;
sets[i].head = NULL;
}
}

void work()
{
char *line = calloc(30, sizeof(char));
int s_mask = (1 << s) - 1;
while (fgets(line, 29, file) != NULL)
{
if (line[0] != ' ')
continue;
line[strlen(line) - 1] = ' ';
if (v)
printf("%s", line + 1);
int loc;
sscanf(line + 3, "%x", &loc);
int loc_s = (loc >> b) & s_mask, loc_t = loc >> (b + s);
Row *row = find(sets[loc_s].head, loc_t);
if (row)
{
if (line[1] == 'M')
{
hits += 2;
if (v)
printf("hit hit");
}
else
{
hits++;
if (v)
printf("hit");
}
del(&sets[loc_s].head, row);
insert(&sets[loc_s].head, loc_t);
}
else
{
misses++;
if (v)
printf("miss ");
if (sets[loc_s].count == E)
{
evictions++;
if (v)
printf("eviction ");
del(&sets[loc_s].head, NULL);
--sets[loc_s].count;
}
insert(&sets[loc_s].head, loc_t);
++sets[loc_s].count;
if (line[1] == 'M')
{
if (v)
printf("hit");
hits++;
}
}
if (v)
printf("\n");
}
}

Row *find(Row *head, int tag)
{
while (head != NULL)
{
if (head->tag == tag)
return head;
head = head->next;
}
return NULL;
}

void del(Row **phead, Row *row)
{
while (*phead != row && (*phead)->next != NULL)
phead = &(*phead)->next;
Row *temp = (*phead)->next;
free(*phead);
*phead = temp;
}

void insert(Row **phead, int tag)
{
Row *row = calloc(1, sizeof(Row));
row->tag = tag;
row->next = *phead;
*phead = row;
}

Part B

给出\(s=5,E=1,b=5\)的直接映射缓存,给出三种大小的矩阵转置:

  • \(N=32,M=32\),miss 在 300 次以内满分。
  • \(N=64,M=64\),miss 在 1300 次以内满分。
  • \(N=61,M=67\),miss 在 2000 次以内满分。

数据 1

观察到一个缓存块的大小为 8 字节,因此划分出\(8\times 8\)的 block 进行矩阵转置即可。

但是直接这样做的话会发现还是超过 300 次 miss,究其原因在于对角线上的 block,\(B\)矩阵和\(A\)矩阵相同的行共用一块 cache,直接转置会不断地来回替换 cache,导致 evictions 特别多,除去循环变量的话我们可以定义 8 个临时变量,刚好存下一个缓存块中的数字。因此可以先读出\(A\)中一个缓存块中的数字,再一次性替换\(B\)矩阵中的一列,可以使对角线上一个 block 的 miss 次数为\(8+7+8=23\)

剩余一个块的 miss 次数为\(16\),因此总的 miss 次数大约为\(23*4+16*3*4=284\)

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
if (N == 32)
{
for (x = 0; x < N; x += 8)
for (y = 0; y < M; y += 8)
{
if (x != y)
for (i = x; i < x + 8; ++i)
for (j = y; j < y + 8; ++j)
B[j][i] = A[i][j];
else
{
for (i = x; i < x + 8; ++i)
{
x1 = A[i][y];
x2 = A[i][y + 1];
x3 = A[i][y + 2];
x4 = A[i][y + 3];
x5 = A[i][y + 4];
x6 = A[i][y + 5];
x7 = A[i][y + 6];
x8 = A[i][y + 7];
B[y][i] = x1;
B[y + 1][i] = x2;
B[y + 2][i] = x3;
B[y + 3][i] = x4;
B[y + 4][i] = x5;
B[y + 5][i] = x6;
B[y + 6][i] = x7;
B[y + 7][i] = x8;
}
}
}
}

数据 2

首先观察到每隔 4 行的相同列共用一个缓存块,因此划分\(8\times8\)的 block 的话,\(B\)的部分会高强度 eviction,把 block 改成\(4\times4\)也拿不到满分。

想一下怎么样一个在\(8\times8\)的 block 中对\(4\times4\)的 4 个小块的读取顺序做优化。首先必须保证每一行仅进入 cache 一次,即使一个\(8\times8\)的块多 4 次 miss,最后总的 miss 数也达到了 1280,不可能满分。

因此尝试找一次扫描就完成\(8\times8\)的 block 的转置。分成三个步骤:

第一步,首先读\(A\)矩阵中的前四行,转置存到\(B\)矩阵的前四行(注意还是用 8 个临时变量一遍扫完再存,这样就不用再特殊处理对角线 block 的情况了):

此时\(A\)的前四行就可以退出 cache 了,但是\(B\)中右上角的\(4\times4\)的部分应该在左下角。

第二步直接让\(A\)的后四行进 cache,但是\(B\)的后四行不能一次性直接进,要把右上角一行的四个字母放进临时变量里,才能用新的行替换之前的一行,具体步骤如下:

  1. 竖着扫描\(A\)的左下角一列,存到四个临时变量x1~x4中,此时\(A\)的后四行进 cache;
  2. 取出\(B\)右上角的一行,放到另外四个临时变量x5~x8中;
  3. x1~x4放到\(B\)右上角的行中。
  4. 再把x5~x8放进左下角对应的行中,此时该行替换 cache。

第三步直接转置右下角的矩阵即可,用到四个临时变量。

总的 miss 次数在 1180 以内。

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
else if (N == 64)
{
for (x = 0; x < N; x += 8)
for (y = 0; y < M; y += 8)
{
for (i = x; i < x + 4; ++i)
{
x1 = A[i][y];
x2 = A[i][y + 1];
x3 = A[i][y + 2];
x4 = A[i][y + 3];
x5 = A[i][y + 4];
x6 = A[i][y + 5];
x7 = A[i][y + 6];
x8 = A[i][y + 7];
B[y][i] = x1;
B[y + 1][i] = x2;
B[y + 2][i] = x3;
B[y + 3][i] = x4;
B[y][i + 4] = x5;
B[y + 1][i + 4] = x6;
B[y + 2][i + 4] = x7;
B[y + 3][i + 4] = x8;
}
for (j = y; j < y + 4; ++j)
{
x1 = A[x + 4][j];
x2 = A[x + 5][j];
x3 = A[x + 6][j];
x4 = A[x + 7][j];
x5 = B[j][x + 4];
x6 = B[j][x + 5];
x7 = B[j][x + 6];
x8 = B[j][x + 7];
B[j][x + 4] = x1;
B[j][x + 5] = x2;
B[j][x + 6] = x3;
B[j][x + 7] = x4;
B[j + 4][x] = x5;
B[j + 4][x + 1] = x6;
B[j + 4][x + 2] = x7;
B[j + 4][x + 3] = x8;
}
for (i = x + 4; i < x + 8; ++i)
{
x1 = A[i][y + 4];
x2 = A[i][y + 5];
x3 = A[i][y + 6];
x4 = A[i][y + 7];
B[y + 4][i] = x1;
B[y + 5][i] = x2;
B[y + 6][i] = x3;
B[y + 7][i] = x4;
}
}
}

数据 3

由于一行不是几个完整的 block,所以随便试,试到\(17\times17\)的 block 效果最好,miss 数为 1950.

1
2
3
4
5
6
7
8
9
10
11
12
else
{
for (x = 0; x < N; x += 17)
for (y = 0; y < M; y += 17)
{
x1 = (N < x + 17) ? N : (x + 17);
x2 = (M < y + 17) ? M : (y + 17);
for (i = x; i < x1; ++i)
for (j = y; j < x2; ++j)
B[j][i] = A[i][j];
}
}

总结

最难的部分就是发现数据 2 的扫描一遍替换算法,其他的部分难度还可以,做完以后再也不想看 cache 了……

作者

xqmmcqs

发布于

2022-01-31

更新于

2022-06-09

许可协议

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×