Mengzelev's Blog

Lab4 实验报告

Word count: 2,224 / Reading time: 9 min
2018/12/29 Share

实验进度描述

我已完成所有内容。

以下是可以忽略的碎碎念:

  • 实验开始一小时:写代码;实验开始两小时推翻前一个小时写的代码;实验开始四小时:推翻前两小时写的代码……
  • 会发生上面的情况其实是因为写cache_read的时候觉得调入调出可以封装为函数,写到cache_write的时候觉得cache_read里的寻找比对、缺失处理都可以封装成函数。在写PA的时候深受Copy-paste其害,所以想把能共享的代码都尽量封装成函数,减轻debug的痛苦
  • 测试的时候曾经出现过写过的地址从cache调出之后回写到内存不成功。加了回写检查函数check_write_back()依然没有定位错误。出去吹了冷风突然意识到可能是回写的内存地址算错了。回去一看发现是cache装入的时候tag没有更新。结论:吹冷风调试法真有用
  • 一开始在虚拟机里用vim写的时候,为了区分变量,都取了超长的名字,打起来很累,后来无奈先在windows里用CLion打开写了基本框架再放到Linux里进行调试(因为虚拟机里开CLion会卡爆)。CLion写代码真的是体验极佳,下学期OSLab双系统走起了
  • 我个**!!!第一遍做完数据没用给定的trace!第二遍做的数据被我一个手抖永久删除了!!!excel还没办法脚本导入!!!一个数据做了3遍!!!

代码解释

为了提高代码的复用率、降低debug负担,我封装了很多API。

  • 为了模拟cache结构定义了如下结构体
1
2
3
4
5
6
struct CacheLine {
bool valid; //有效位
bool dirty; //脏位
uint32_t tag; //标记位
uint32_t data[16]; //一行64B数据
}line[1024];
  • 定义了如下全局变量来记录cache的相关信息
1
2
3
4
5
6
/* cache info */
int ass_width; //关联宽度
int total_width; //总宽度
int group_width; //组宽度(指cache组号在主存地址中的位数)
#define NR_ASS exp2(ass_width) //宏定义,组内行数
#define OFFSET 0x3f //与操作后可以取出块内偏移量

将以下功能封装为了API。因为宏定义会涉及到加括号等问题,怕出现奇奇怪怪的bug,所以并没有使用宏定义,而是直接用函数代替

1
2
3
4
5
6
7
8
9
uint32_t get_tag(uintptr_t addr) {
//获得一个内存地址的tag字段
return (addr >> (group_width + BLOCK_WIDTH));
}

uint32_t get_group(uintptr_t addr) {
//获得一个内存地址的cache组号字段
return ((addr >> BLOCK_WIDTH) & mask_with_len(group_width));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void move_in(uintptr_t addr, int line_num) {
//将主存中某一块调入cache中
assert(line[line_num].valid == false);
uint32_t block_num = addr >> BLOCK_WIDTH;
mem_read(block_num, (uint8_t*)(line[line_num].data));
line[line_num].valid = true;
line[line_num].dirty = false;
line[line_num].tag = get_tag(addr);
}

void move_out(int group_num, int line_num) {
//将cache的某一行调回到主存中,同时判断dirty bit并写回
assert(line[line_num].valid == true);
assert(line_num < 1024);
line[line_num].valid = false;
if(line[line_num].dirty) {
uintptr_t block_num = (line[line_num].tag << group_width) + group_num;

mem_write(block_num, (uint8_t*)line[line_num].data);
line[line_num].dirty = false;
//write back
}
}
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
int find_in_group(uintptr_t addr, int group_num) {
//在某一组寻找找某主存地址对应的行,返回其所在行号,缺失则返回-1
int group_start = group_num * NR_ASS;
int group_end = group_start + NR_ASS;
uint32_t tag = get_tag(addr);
for(int i = group_start; i < group_end; ++i) {
if(line[i].valid && line[i].tag == tag) {
cycle_increase(1);
hit_visit ++;
return i;
}
}
return -1;
}

int replace_in_group(uintptr_t addr, int group_num) {
//将主存地址对应的主存块调入cache中
miss_visit ++;
int group_start = group_num * NR_ASS;
int group_end = group_start + NR_ASS;
for(int i = group_start; i < group_end; ++i) {
if(!line[i].valid) {
move_in(addr, i);
return i;
}
}
//如果组内有空行,则直接放入空行中
int line_out = group_start + choose(NR_ASS);
assert(line_out < group_end);

move_out(group_num, line_out);
move_in(addr, line_out);
//否则随机替换一行
return line_out;
}
1
2
3
4
5
6
void write_in_line(int line_num, int index, uint32_t data, uint32_t wmask) {
//将数据写入cache某一行的某个index中
line[line_num].dirty = true;
line[line_num].data[index] &= (~wmask);
line[line_num].data[index] |= (data & wmask);
}
  • 这样一来需要实现的3个函数只需要调用以上API即可
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
void init_cache(int total_size_width, int associativity_width) {
/*设置cache的一系列参数*/
total_width = total_size_width;
assert(total_width <= 14);
ass_width = associativity_width;
group_width = total_width - ass_width - BLOCK_WIDTH;
/*初始化用于统计的变量*/
cycle_cnt = 0;
total_visit = hit_visit = miss_visit = 0;
/* set all the valid bits and dirty bits to invalid */
for(int i = 0; i < NR_LINE; ++i) line[i].valid = line[i].dirty = false;
}

uint32_t cache_read(uintptr_t addr) {
total_visit ++;
uint32_t group_num = get_group(addr);
uint32_t index = (addr & OFFSET) / sizeof(int); //index in group

int line_num = find_in_group(addr, group_num);
if(line_num >= 0) return line[line_num].data[index];
//hit则直接读出

int line_out = replace_in_group(addr, group_num);
return line[line_out].data[index];
//否则从主存调入cache
}

void cache_write(uintptr_t addr, uint32_t data, uint32_t wmask) {
total_visit++;
uint32_t group_num = get_group(addr);
uint32_t index = (addr & OFFSET) / sizeof(int); //index in group

int line_num = find_in_group(addr, group_num);
if(line_num >= 0)
write_in_line(line_num, index, data, wmask);
//hit则直接写入
else {
int line_out = replace_in_group(addr, group_num);
write_in_line(line_out, index, data, wmask);
}//否则写分配
}

cache性能测试

运行时间测算

  • 框架代码已经给内存的读写赋好了相应的时钟周期数,所以我很自然地想到通过统计时钟周期数来统计运行的时间
  • 关于怎么对cache读写操作的时钟周期测算,讲义说可以建立关于关联度的带参数的模型,但是我回想起来课本上讲过,组相联组内是用了很多比较器进行并行比较的。所以我认为读写的时钟周期数应该和关联度以及cache容量关系不大,所以将读写的时钟周期都设置为1。>可能也有想省事的惰性成分在里面
  • 除时钟周期数外,还衡量一个缺失率。由于主存读写比cache读写慢得多,读写命中率也能表征cache的性能

声明了一些用于统计的变量

1
2
3
4
/* statistics */
uint64_t total_visit = 0;
uint64_t hit_visit = 0;
uint64_t miss_visit = 0;
  • 测算方法:控制变量法,控制组相联度或cache总宽度其中一个量不变,改变另外一个量。每种配置测量3次后取平均。根据结果使用excel作图,得到如下结果。【数据已经放在打包上传的.xlsx文件中】





从以上数据和图表中可以看出:

  • cache容量越大,缺失率越低,花费的总时钟周期数也越少。这是因为cache容量大了以后,能装入更多的主存块,缺失率就会相应地降低,需要进行替换的次数也会变少。但是cache大就意味着高昂的造价,而且SDRAM的材质(?)决定了cache不可能做到很大。而且由图中可以看出,当cache容量增大到一定大小时,其性能增长就很不明显了,因此一般会选择比较中等的大小。
  • 缺失率与组相联度似乎并不是呈单调关系。原理上分析,组相联度越大,同一组内发生冲突的概率就越低,需要调出的次数也会越低。但有可能microbench-test中的访存顺序会导致某些经常访问的块,在相联度较小时被放到了不同的组中,而相联度较大时被放到了同一组中,导致发生冲突的次数增加。而且越高的组相联度,意味着越多的比较器,意味着更大的体积和更高的造价。

  • 综上,对于microbench-test下的workload,我认为最佳的组相联宽度是2(4路组相联)。如果有钱任性,cache容量越大越好;如果要省钱经济,12或13的容量宽度(4KB或8KB的容量)是比较理想的。

思考题

数据对齐和存储层次结构

  • 如果没有对齐,同一个数据可能会被分配再两个主存块的交界处,读取这个数据的时候发生cache miss的概率更大,cache miss后可能需要调入两个主存块,代价更大,运行速度会大大降低。

不知道cache的复杂性对频率的影响?

  • 我不是很看得懂这里的建模的意思。我认为$ak^2+b$中%a,b$只是两个参数,考察它们对cache性能的影响是没有意义的,而是应该固定$a,b$,考察组相联度和cache容量对cache性能的影响。但是我已经在上文提到了我并没有把这两者与cache的读写速度关联起来。所以我没有建立带参数的模型。

Acknowledgements

  • 感谢不水的正经学习群的朋友们当我的小黄鸭,帮我调试
  • 感谢*的自己,因为一系列\*行为,成功锻炼了心理承受能力
CATALOG
  1. 1. 实验进度描述
  2. 2. 代码解释
  3. 3. cache性能测试
  4. 4. 运行时间测算
  5. 5. 思考题
  6. 6. 数据对齐和存储层次结构
  7. 7. 不知道cache的复杂性对频率的影响?
  8. 8. Acknowledgements