Part A: 缓存模拟
第一个任务是要模拟缓存，首先用一个结构体定义缓存的结构
缓存结构
1
2
3
4
5
6
7
8
| typedef struct {
bool vaild;
uint64_t tag;
uint64_t time_counter;
}line;
typedef line *entry_of_lines;
typedef entry_of_lines *entry_of_sets;
|
处理输入
我们需要在 main 函数中处理输入的指令，这里需要用到 getopt() 函数， getopt 的使用方法在这里
我们要为 cache 申请内存空间，这里使用 calloc 而不是 malloc，两者的区别在这里
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| entry_of_sets InitializeCache (uint64_t S, uint64_t E) {
entry_of_sets cache;
if ((cache = calloc(S, sizeof(entry_of_lines))) == NULL) {
perror("Failed to calloc entry_of_sets");
exit(EXIT_FAILURE);
}
for (int i = 0; i < S; i++) {
if ((cache[i] = calloc(E, sizeof(line))) == NULL) {
perror("Failed to calloc line in sets");
exit(EXIT_FAILURE);
}
}
return cache;
}
|
首先根据 S 申请一个数组，数组的元素是指向 lines 的指针，然后循环 S 次，每次申请 E 个 line
既然申请了内存就要记得释放
1
2
3
4
5
6
7
| void ReleaseMemory (entry_of_sets cache, uint64_t S, uint64_t E) {
for (uint64_t i = 0; i < S; i++) {
free(cache[i]);
}
free(cache);
}
|
模拟缓存
主要的工作是处理 tracefile 中的三个指令， L S M，分别对应着读取、写入、读取后写入
不过首先应该获得到 line tag block
- line 的获取方式使用了演码
- tag 和 block 只需要位操作就可以了
1
2
3
| uint64_t set_index_mask = (1 << s) - 1;
uint64_t set_index = (address >> b) & set_index_mask;
uint64_t tag = (address >> b) >> s;
|
然后就可以计算 hit 和 miss 了
但是当我们遇到 miss 的时候，应该更新缓存，这里使用的是 LRU，就是遇到 miss 时，更改时间戳最久远的 cache 中的内容
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
| if (!hit_flag) {
if (verbose) printf("miss");
Result.miss++;
uint64_t i;
for (i = 0; i < E; i++) {
if (search_line[i].time_counter < oldest_time) {
oldest_time = search_line[i].time_counter;
oldest_block = i;
}
if (search_line[i].time_counter > youngest_time) {
youngest_time = search_line[i].time_counter;
}
}
search_line[oldest_block].time_counter = youngest_time + 1;
search_line[oldest_block].tag = tag;
if (search_line[oldest_block].vaild) {
if (verbose) printf("and eviction\n");
Result.eviction++;
} else {
if (verbose) printf("\n");
search_line[oldest_block].vaild = true;
}
}
|
原始代码在这里
Part B:矩阵转制优化
使用 Blocking 的方法，提高 Cache 命中率
直接上代码在这