实验答案托管在我的GitHub上
考完试之后一直比较颓废，本来想看完《深入理解计算机系统》的第5章——优化程序性能之后就赶快来做实验的，后来发现无论是Cache Lab还是Performance Lab都需要第6章——存储器层次结构的知识。看了几天的书，又磨蹭了几天，终于把Cache Lab的Part A写完了，总结如下。
实验简介
Cache Lab - Understanding Cache Memories主要是有关缓存的实验，对应于书本的第6章：存储器层次结构。主要阐明了缓存对于C语言程序的性能影响。
本实验主要分为两个部分。第一个部分要求完成一个C语言程序用来模拟缓存的行为；而第二个部分要求优化一个小的矩阵变换函数，使其具有尽可能小的缓存不命中率。
关于本实验的具体介绍详见实验讲义。
实验介绍
实验讲义中的traces子文件夹下包含了一组reference trace files，用来作为评估Part A中缓存模拟器正确性的样例数据。这些文件是由valgrind生成的。
Valgrind是一个用于内存调试，内存泄露以及性能分析的软件。例如，我们输入如下的命令：1
linux> valgrind --log-fd=1 --tool=lackey -v --trace-mem=yes ls -l
valgrind会在命令行中执行ls -l命令并且按照顺序记录该命令的每一次内存访问，并且将其输出到标准输出流中。
下面是一个valgrind的输出样例：1
2
3
4I 0400d7d4,8
M 0421c7f0,4
L 04f6b868,8
S 7ff0005c8,8
每一行的基本格式如下：1
[空格]操作 地址,大小
操作代表了内存访问的种类，'I'代表的是指令加载，'L'代表的是数据加载，'S'代表的是数据存储，'M'代表的是数据修改（如一条数据加载之后紧跟着数据存储）。在'I'之前永远没有空格，而其他的操作前必定有前置空格。
地址代表的是一个64位的16进制内存地址。
大小指明了该次内存访问涉及的字节数。
实验要求 - Part A
在Part A中你需要在csim.c中实现一个LRU驱逐机制的缓存模拟器，该模拟器接收valgrind的trace作为输入，模拟一个缓存在该情况下的命中/不命中情况，并且输出所有的命中，不命中以及驱逐的次数。
本实验已经提供了一个用来参考的缓存模拟器csim-ref，其使用方式以及输出如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20Usage: ./csim-ref [-hv] -s <s> -E <E> -b <b> -t <tracefile>
• -h: Optional help flag that prints usage info
• -v: Optional verbose flag that displays trace info
• -s <s>: Number of set index bits (S = 2 s is the number of sets)
• -E <E>: Associativity (number of lines per set)
• -b <b>: Number of block bits (B = 2 b is the block size)
• -t <tracefile>: Name of the valgrind trace to replay
linux> ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace
hits:4 misses:5 evictions:3
linux> ./csim-ref -v -s 4 -E 1 -b 4 -t traces/yi.trace
L 10,1 miss
M 20,1 miss hit
L 22,1 hit
S 18,1 hit
L 110,1 miss eviction
L 210,1 miss eviction
M 12,1 miss eviction hit
hits:4 misses:5 evictions:3
对于Part A有以下的要求和限制：
- 所写的程序编译时不能有任何的警告
- 能应对不同s，E和b的缓存生成对应的结果，这要求使用malloc来为你的数据结构分配空间
- 不需要考虑指令加载的缓存情况
- 调用printSummary打印最终的结果
- 假定数据已经适当对齐，不会出现一次数据加载跨区块的情况。这样，你可以忽略trace中的大小
除此以外，实验的自学者讲义中还包含了一些提示，这里就不再赘述。
完成了Part A之后，可以用make clean && make进行编译，并且用./test-csim进行自动评分，总共有8组样例，共27分满分。
实验过程 - Part A
实验思路
整个模拟器在思路上可以进行如下的拆分：
1.命令行参数解析
由于该模拟器是命令行程序并且接受命令行参数，因此需要能对命令行参数进行解析和处理，这里推荐使用getopt进行参数的解析。并且根据不同的参数执行不同的控制流，并且处理一些基本的错误如参数缺失以及参数类型错误。
2.数据结构
这是整个模拟器最基本的部分。我们需要创建合适的数据结构来模拟缓存，该数据结构不仅要能模拟缓存的数据的实际组织方式（有效位，标志位以及行和块等等），还需要考虑到LRU的驱逐机制。
3.文件中内存访问记录的处理和解析
这个是模拟器中核心的部分。模拟器的功能就是从文件中接收内存访问记录，并且根据这些记录来模拟缓存的行为，操作我们所设计的缓存的数据结构。
实验代码
该代码仅供参考，很可能并不是一个非常好的解法。如果你也在面对同样的实验，请不要抄袭，毕竟抄袭是不会使你变得更强的:)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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361/* include necessary headers */
/* cache struct definition */
typedef struct CSim_Cache_Entry {
char valid_bit;
uint64_t tag_bit;
}CSim_Cache_Entry;
typedef struct CSim_Cache_Set{
CSim_Cache_Entry * entries;
}CSim_Cache_Set;
typedef struct CSim_Cache {
/* basic arguments */
int block_offset;
int set_number;
int line_number;
/* masks and offsets */
int tag_offset;
int set_offset;
uint64_t tag_mask;
uint64_t set_mask;
/* cache */
CSim_Cache_Set * sets;
}CSim_Cache;
/* simulation result definition */
typedef struct CSim_Cache_Result {
int hit;
int miss;
int evict;
}CSim_Cache_Result;
/* operation type definition */
typedef enum CSIM_OPERATION_TYPE {
CSIM_OPERATION_TYPE_NONE,
CSIM_OPERATION_TYPE_MODIFY,
CSIM_OPERATION_TYPE_LOAD,
CSIM_OPERATION_TYPE_STORE,
}CSIM_OPERATION_TYPE;
/* operation result definition */
typedef enum CSIM_OPERATION_RESULT {
CSIM_OPERATION_RESULT_MISS,
CSIM_OPERATION_RESULT_HIT,
CSIM_OPERATION_RESULT_MISS_EVICTION,
}CSIM_OPERATION_RESULT;
/* error definition */
typedef enum CSIM_ERROR {
CSIM_OK = 0,
CSIM_ERROR_INVALID_OPTION,
CSIM_ERROR_MISSING_ARGUMENT,
CSIM_ERROR_FILE_CANNOT_OPEN,
CSIM_ERROR_OUT_OF_MEMORY,
}CSIM_ERROR;
/* macro definition for get a value given mask and offset */
/* function list */
/* message print functions */
void csim_print_help_info();
void csim_error_missing_argument();
void csim_error_file_cannot_open();
void csim_error_out_of_memory();
/* cache structure related functions */
CSim_Cache * csim_construct_cache(int set_number, int line_number, int block_offset);
void csim_deconstruct_cache(CSim_Cache ** pcache);
/* cache simulation function */
CSim_Cache_Result csim_parse_trace_file(CSim_Cache * cache, FILE * file_pointer, char verbose_flag);
/* global variable */
char * program_name = NULL;
void csim_print_help_info() {
printf("Usage: ./csim [-hv] -s <num> -E <num> -b <num> -t <file>\n");
printf("Options:\n");
printf(" -h Print this help message.\n");
printf(" -v Optional verbose flag.\n");
printf(" -s <num> Number of set index bits.\n");
printf(" -E <num> Number of lines per set.\n");
printf(" -b <num> Number of block offset bits.\n");
printf(" -t <file> Trace file.\n\n");
printf("Examples:\n");
printf(" linux> ./csim -s 4 -E 1 -b 4 -t traces/yi.trace\n");
printf(" linux> ./csim -v -s 8 -E 2 -b 4 -t traces/yi.trace\n");
}
void csim_error_missing_argument() {
printf("%s: Missing required command line argument\n", program_name);
csim_print_help_info();
}
void csim_error_file_cannot_open() {
printf("%s: No such file or directory\n", program_name);
}
void csim_error_out_of_memory() {
printf("%s: Out of memory\n", program_name);
}
CSim_Cache * csim_construct_cache(int set_number, int line_number, int block_offset) {
/* memory allocation */
CSim_Cache * cache = malloc(sizeof(CSim_Cache));
if (cache == NULL) {
csim_error_out_of_memory();
exit(CSIM_ERROR_OUT_OF_MEMORY);
}
/* configure basic arguments */
cache->set_number = set_number;
cache->line_number = line_number;
cache->block_offset = block_offset;
/* caculate masks and offsets */
cache->tag_mask = ((uint64_t)0xFFFFFFFFFFFFFFFF) << (block_offset + set_number);
cache->tag_offset = block_offset + set_number;
cache->set_mask = ((((((uint64_t)0xFFFFFFFFFFFFFFFF) << (64 - cache->tag_offset)) >> (64 - cache->tag_offset)) >> block_offset) << block_offset);
cache->set_offset = block_offset;
/* memory allocation for cache */
cache->sets = calloc((1 << set_number), sizeof(CSim_Cache_Set));
if (cache->sets == NULL) {
csim_error_out_of_memory();
exit(CSIM_ERROR_OUT_OF_MEMORY);
}
for (int index = 0 ; index < (1 << set_number) ; ++index) {
(cache->sets)[index].entries = calloc(line_number, sizeof(CSim_Cache_Entry));
if ((cache->sets)[index].entries == NULL) {
csim_error_out_of_memory();
exit(CSIM_ERROR_OUT_OF_MEMORY);
}
}
return cache;
}
void csim_deconstruct_cache(CSim_Cache ** pcache) {
/* release cache according to construct function */
CSim_Cache * temp = *pcache;
int set_number = temp->set_number;
for (int index = 0 ; index < set_number ; ++index) {
free((temp->sets)[index].entries);
}
free(temp->sets);
free(temp);
*pcache = NULL;
}
CSim_Cache_Result csim_parse_trace_file(CSim_Cache * cache, FILE * file_pointer, char verbose_flag) {
/* file I/O related */
char line[80];
char * line_pointer = NULL;
/* cache type and cache result */
CSIM_OPERATION_TYPE type;
CSIM_OPERATION_RESULT result;
/* address and set index & tag bis from it */
int address = 0;
int set = 0, tag = 0;
/* line number */
int line_number = cache->line_number;
/* simulation result */
CSim_Cache_Result summary = {0, 0, 0};
/* parsing process */
while (fgets(line, 80, file_pointer), feof(file_pointer) == 0) {
line_pointer = line;
type = CSIM_OPERATION_TYPE_NONE;
/* exclude instrction load */
if (*line_pointer++ == ' ') {
switch(*line_pointer++) {
case 'L':
type = CSIM_OPERATION_TYPE_LOAD;
if (verbose_flag) {
putchar('L');
}
break;
case 'S':
type = CSIM_OPERATION_TYPE_STORE;
if (verbose_flag) {
putchar('S');
}
break;
case 'M':
type = CSIM_OPERATION_TYPE_MODIFY;
if (verbose_flag) {
putchar('M');
}
break;
default:
type = CSIM_OPERATION_TYPE_NONE;
break;
}
result = CSIM_OPERATION_RESULT_MISS_EVICTION;
sscanf(line_pointer, "%x", &address);
if (verbose_flag) {
while ((*line_pointer) != '\n') {
putchar(*line_pointer++);
}
}
/* separate set and tag according to mask and offset */
set = csim_get_value(address, cache->set_mask, cache->set_offset);
tag = csim_get_value(address, cache->tag_mask, cache->tag_offset);
/* determine the cache result */
CSim_Cache_Entry * pentry = (cache->sets)[set].entries;
int index;
CSim_Cache_Entry temp;
for (index = 0; index < line_number ; ++index) {
if (!pentry[index].valid_bit) {
result = CSIM_OPERATION_RESULT_MISS;
break;
}
if (pentry[index].tag_bit == tag) {
result = CSIM_OPERATION_RESULT_HIT;
break;
}
}
/* simulate according to the result of cache behavior */
switch(result) {
case CSIM_OPERATION_RESULT_MISS:
if (verbose_flag) {
printf(" miss");
}
pentry[index].valid_bit = 1;
pentry[index].tag_bit = tag;
summary.miss++;
break;
case CSIM_OPERATION_RESULT_MISS_EVICTION:
if (verbose_flag) {
printf(" miss eviction");
}
pentry[0].tag_bit = tag;
temp = pentry[0];
for (index = 0 ; index < line_number - 1 ; ++index) {
pentry[index] = pentry[index + 1];
}
pentry[index] = temp;
summary.miss++;
summary.evict++;
break;
case CSIM_OPERATION_RESULT_HIT:
if (verbose_flag) {
printf(" hit");
}
temp = pentry[index];
for ( ; (index < line_number - 1) && (pentry[index + 1].valid_bit) ; ++index) {
pentry[index] = pentry[index + 1];
}
pentry[index] = temp;
summary.hit++;
break;
}
if (type == CSIM_OPERATION_TYPE_MODIFY) {
if (verbose_flag) {
printf(" hit");
}
summary.hit++;
}
if (verbose_flag) {
putchar('\n');
}
}
}
return summary;
}
int main(int argc, char *argv[]) {
/* variables for argument parsing */
char h = 0, v = 0, s = 0, E = 0, b = 0, t = 0;
int opt;
/* cache arguments */
int set_number = 0, line_number = 0, block_offset = 0;
/* cache */
CSim_Cache * cache = NULL;
/* file path */
char file_path[80];
/* verbose flag */
char verbose_flag = 0;
/* summary */
CSim_Cache_Result summary = {0, 0, 0};
/* pre-operation */
program_name = argv[0];
/* argument parsing */
while ((opt = getopt(argc, argv, "hvs:E:b:t:")) != -1) {
switch(opt) {
case 'h':
h = 1;
break;
case 'v':
v = 1;
verbose_flag = 1;
break;
case 's':
set_number = atoi(optarg);
if (set_number == 0) {
csim_error_missing_argument();
return CSIM_ERROR_MISSING_ARGUMENT;
}
s = 1;
break;
case 'E':
line_number = atoi(optarg);
if (line_number == 0) {
csim_error_missing_argument();
return CSIM_ERROR_MISSING_ARGUMENT;
}
E = 1;
break;
case 'b':
block_offset = atoi(optarg);
if (block_offset == 0) {
csim_error_missing_argument();
return CSIM_ERROR_MISSING_ARGUMENT;
}
b = 1;
break;
case 't':
t = 1;
strcpy(file_path, optarg);
break;
default:
csim_print_help_info();
return CSIM_ERROR_INVALID_OPTION;
break;
}
}
if (h == 1) {
csim_print_help_info();
return CSIM_OK;
}
if (v == 1) {
verbose_flag = 1;
}
if (!(s == 1 && E == 1 && b == 1 && t == 1)) {
csim_error_missing_argument();
return CSIM_ERROR_MISSING_ARGUMENT;
}
/* file processing */
FILE * file_pointer = fopen(file_path, "r");
if (file_pointer == NULL) {
csim_error_file_cannot_open(file_path);
return CSIM_ERROR_FILE_CANNOT_OPEN;
}
/* cache construction */
cache = csim_construct_cache(set_number, line_number, block_offset);
/* trace file parsing */
summary = csim_parse_trace_file(cache, file_pointer, verbose_flag);
/* summary */
printSummary(summary.hit, summary.miss, summary.evict);
/* post operations */
csim_deconstruct_cache(&cache);
fclose(file_pointer);
return CSIM_OK;
}
实验结果
自动评分脚本给出的输出如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14user@blackdragon ~/C/C/cachelab-handout> ./test-csim
Your simulator Reference simulator
Points (s,E,b) Hits Misses Evicts Hits Misses Evicts
3 (1,1,1) 9 8 6 9 8 6 traces/yi2.trace
3 (4,2,4) 4 5 2 4 5 2 traces/yi.trace
3 (2,1,4) 2 3 1 2 3 1 traces/dave.trace
3 (2,1,3) 167 71 67 167 71 67 traces/trans.trace
3 (2,2,3) 201 37 29 201 37 29 traces/trans.trace
3 (2,4,3) 212 26 10 212 26 10 traces/trans.trace
3 (5,1,5) 231 7 0 231 7 0 traces/trans.trace
6 (5,1,5) 265189 21775 21743 265189 21775 21743 traces/long.trace
27
TEST_CSIM_RESULTS=27
实验总结
由于在寒假的课程设计中已经使用过了命令行参数解析以及复杂的数据结构设计与实验，Part A总体上来说不是很难，我主要的精力花费在代码风格上，希望代码能尽量具有良好的架构以及可读性。
本部分中犯的错误有，直接根据s设置缓存的组数，而实际上的组数是2^s个。循环中由于手误导致出现死循环。没有搞清楚inline static关键字而导致的编译错误等等。存在知识的盲区也存在着粗心导致的错误，以后还需要更加注意。
