CSAPP | Lab5-Cache Lab 深入解析
CacheLab
文章目录
- CacheLab
- 实验概述
- 一些前置准备
- Part A
- 实验预览
- 思路
- 数据结构
- 创建高速缓存
- 从命令行中读取参数信息
- 初始化高速缓存
- 代码
- 读入内存操作
- 指令解析
- 地址映射
- 代码
- 模拟高速缓存
- 代码
- 释放内存
- 代码
- 主函数
- 代码
- Part B
- 实验预览
- 32×32
- 优化——分块8×8
- 代码
- 优化——分块8×8+使用局部变量
- 代码
- 64×64
- 优化——分块8×8
- 优化——分块4×4
- 代码
- 优化——对8×8的块用4×4的方式处理1.0
- 代码
- 优化——对8×8的块用4×4的方式处理2.0
- 代码
- 61×67
- 评分
“All problems in computer science can be solved by another level of indirection”
实验概述
实验分为两部分：Part A要求编写一个高速缓存模拟器（csim.c），Part B要求优化矩阵转置函数，最小化高速缓存的不命中的次数（trans.c）
这个实验设计得很好，恰好涵盖了书上第6章的两个核心部分：理解高速缓存的工作方式，以及编写高速缓存友好的代码，同时还应用到了p450页介绍的分块技术。建议先阅读以下的资料，再进行实验
CMU课件，最后有对Cache Lab的一些提示：rec07.pdf (cmu.edu)
分块技术的介绍：waside-blocking.pdf (cmu.edu)
讲解分块技术的博客：[读书笔记]CSAPP：16[VB]高速缓存存储器 - 知乎 (zhihu.com)
一些前置准备
按照实验说明，解压cachelab-handout.tar，创建出一个名为cachelab-handout的目录，这是我们Part A和Part B的工作目录，Part A对应的文件是csim.c，Part B对应的文件是trans.c
进到目录后先输入命令：make clean && make，这将会编译csim.c,trans.c,test-trans.c等文件
Part A
实验预览
Part A要求在csim.c文件中编写一个高速缓存模拟器，traces目录下的5个.trace文件是模拟器要执行的内存操作
老师提供了一个可供参考的缓存模拟器：csim-ref，这个模拟器有6个参数：
Usage: ./csim-ref [-hv] -s -E -b -t • -h: Optional help flag that prints usage info • -v: Optional verbose flag that displays trace info • -s : Number of set index bits (S = 2^s is the number of sets) • -E : Associativity (number of lines per set) • -b : Number of block bits (B = 2b is the block size) • -t : Name of the valgrind trace to replay和书上使用的参数一致：s是组索引位数，E是每个组包含的高速缓存行的个数，b是块偏移位数，除此之外，参数v表示要详细输出每次内存执行时，高速缓存的模拟情况（命中、不命中、替换）；参数t是用于模拟内存操作的.trace文件名，举个例子：
./csim-ref -v -s 2 -E 2 -b 3 -t traces/yi.trace
这表示用csim-ref模拟一个高速缓存，执行traces/yi.trace的内存操作。我们设定这个高速缓存有4个组，每个组有2个高速缓存行，每个高速缓存块有8个字节
查看一下yi.trace中的内存操作：
L 10,1 M 20,1 L 22,1 S 18,1 L 110,1 L 210,1 M 12,1
内存操作的格式为：[space]operation address, size，operation 有 4 种：
- I表示加载指令，表示从内存中读取指令内容
- L 加载数据，表示程序从某个内存地址加载了数据。（缓存命中、不命中、执行替换策略）
- S存储数据，表示程序向某个内存地址存储了数据。（写回、写分配）
- M 修改数据，表示程序对某个内存地址的数据进行了修改。
不需要考虑加载指令I,M指令相当于先进行L再进行S，模拟器要做出的反馈有 3 种：
- hit：命中，表示要操作的数据在对应组的其中一行
- miss：不命中，表示要操作的数据不在对应组的任何一行
- eviction：驱逐，表示要操作的数据的对应组已满，进行了替换操作，这个实验的驱逐策略是LRU，选择最后被访问的时间距现在最远的块（CSAPP p423页）
Part A要做什么： 编写csim.c，这个程序的执行效果要与csim-ref相同，能够模拟一个高速缓存器（参数自定义），执行traces/xx.trace中的内存操作过程。这个模拟器不需要真的存储数据，只是计算traces/xx.trace的内存操作过程中，缓存的命中、不命中、LRU替换的数量，然后将这些参数作为答案，传给printSummary函数
如何检验模拟器的正确性： 首先编译csim.c文件，命令为：gcc -o csim csim.c cachelab.c -lm，这将创建可执行文件csim，也就是你的模拟器
有两种检验方法：
- 使用csim-ref作为参考。设定相同的参数，分别用csim-ref和csim作为模拟器，读取同一个.trace文件的内存操作过程，比对两个模拟器输出的hit、miss、eviction的值
- 使用评分程序test-csim，命令为：./test-csim，这个程序将会使用不同的参数设定你的模拟器，并让模拟器执行目录traces中所有的.trace文件，满分是27
思路
我将整个高速缓存模拟器的实现分为3个部分：
- 创建高速缓存：这包括从命令行中读取参数信息，初始化缓存
- 读入内存操作：就是读取xx.trace文件中每行的内容
- 根据读入的内存操作，模拟高速缓存的行为：核心代码，这包括在高速缓存中查找地址所指示的字，对不命中的处理（是加载到一个空的缓存行还是需要执行LRU替换策略）。每次执行一次缓存(caching)，就更新缓存(cache)信息（有效位、标志位、时间戳），同时统计hit、miss、eviction
数据结构
根据CMU课件的提示，我使用二维结构体数组实现cache。结构体定义如下：
typedef struct { bool valid; //有效位 unsigned long tag; //标志位 int timestamp; //时间戳 }cache_line; //一个高速缓存行定义二维结构体数组为cache_line** cache，这个数组的大小是S×E，cache[i]是高速缓存组i，cache[i][j]是高速缓存组i中的高速缓存行j，cache[i][j]中包含有效位（valid）、标志位（tag）、时间戳（timestamp，记录这个高速缓存行最后被访问的时间），由于不需要存储数据，就没有定义高速缓存块
创建高速缓存
从命令行中读取参数信息
由于s、E、 b是由命令行参数设定的，所以要先读取命令行中的参数，可以使用课件中提示的getopt函数，参考getopt(3) - Linux manual page (man7.org)
为了便于访问参数s、E、b，我使用全局变量定义这些参数，简化代码。同时，我使用变量verbose来标识是否需要详细输出缓存过程
这里说一个小坑，getopt函数中，没有参数的选项不带":"，如果你写成了v:s:E:b:t，即不带参数的-v有了":"，那么getopt就会等待参数的输入。当opt为s时，会将读到的参数optarg给v，而不是后出现的s，这就是说，-v将-s的参数作为自己的参数，-s就直接被跳过了，然后后面就正常读了，所以E、b、t都没问题，只有s为0（花费我1h用gdb来回调试才发现的bug😢，这样的细节很要命）
初始化高速缓存
为结构体数组分配空间： 相应的，二维结构体数组的空间也是动态分配的。根据读入的参数s、E、b，使用malloc分配内存
初始化高速缓存： 将cache[i][j]的有效位（valid）设置为0，表示这是一个空的高速缓存行；时间戳（timestamp）设置为0
代码
实现的代码如下：
cache_line** create_cache(int argc, char** argv) { int opt; while(-1 != (opt = getopt(argc, argv, "vs:E:b:t:"))) { switch(opt) { case 'v': verbose = 1; //设置verbose为1，表示要详细输出缓存过程 break; case 's': s = atoi(optarg); break; case 'E': E = atoi(optarg); break; case 'b': b = atoi(optarg); break; case 't': strcpy(t, optarg); break; default: break; //程序健壮性检验，如果不是一个合法的参数，就会退出switch,继续while读取 } } //申请内存，创建高速缓存，组数为2^s,每一组高速缓存行总数为E个。即创建一个行为2^s,列为E的二维结构体数组 int row = pow(2, s); int col = E; cache_line** cache = (cache_line**)malloc(row*sizeof(cache_line*)); if(cache == NULL) { printf("Failed to allocate memory!\n"); exit(1); } for(int i=0; i cache[i] = (cache_line*)malloc(col*sizeof(cache_line)); if(cache[i] == NULL) { printf("Failed to allocate memory!\n"); exit(1); } } //初始化高速缓存，设置有效位为0，时间戳为0 for(int i=0; i for(int j=0; j cache[i][j].valid = 0; //有效位 置0 cache[i][j].timestamp = 0; } } return cache; } FILE *fp = fopen(t, "r"); if(fp == NULL) { perror("Error opening file"); exit(1); } char operation; unsigned long addr; int bytes; //地址映射的组号和标志位 int set; unsigned long tag; while(fscanf(fp, " %c %lx,%d", &operation, &addr, &bytes) == 3) { set = (addr>b) & (unsigned long)((1 (b+s); switch(operation) { case 'L': case 'S': if(verbose) printf("%c %lx,%d ", operation, addr, bytes); cache_simulate(cache, set, tag); if(verbose) printf("\n"); break; case 'M': if(verbose) printf("%c %lx,%d ", operation, addr, bytes); cache_simulate(cache, set, tag); cache_simulate(cache, set, tag); if(verbose) printf("\n"); break; default: break; } } }模拟高速缓存
根据从内存操作中由地址映射的组索引set、标记tag，模拟缓存过程
为了简化参数，我使用一个数组result[3]来存放hit、miss、eviction的次数。
为了记录缓存行cache[i][j]最后被执行的时间，即设置时间戳cache[i][j].timestamp，我使用一个全局变量T作为整体的时间。初始 T设置为0，每当进行一次缓存(caching)，就要对T加1，这样当需要进行LRU替换时，我们遍历查找这个组，驱逐时间戳最小的缓存行。恰好我们在每一次缓存(caching)后，使用update函数更新缓存(cache)的信息，所以当调用update函数时，就意味着进行了一次缓存(caching)，因此可以在update函数中对T加1，更新整体的时间
模拟高速缓存的整体逻辑是：
- 首先在高速缓存组cache[set]中进行行匹配：遍历检查缓存行cache[set][j]的有效位和标记位，以确定地址中的字是否在缓存中。如果找到了一个有效的行cache[set][pos]，它的标记与地址中的标记tag相匹配，则缓存命中；若遍历了所有的行都不匹配，则为缓存不命中
- 若缓存命中，则直接调用update函数，更新时间戳：cache[set][pos].timestamp = T，并统计hit：result[HIT]++（这里我使用了枚举）
- 若缓存不命中，则需要判断这个组cache[set]是否满了，一种方法是维护一个数组occupancy，它记录了各个组中有效位为1的有效行个数，初始置为0。比较occupancy[set]（有效行个数）与E（行总数），判断缓存组cache[set]中是否还有空行
- 若occupancy[set]
- 若occupancy[set] == E，则没有空行，需要执行LRU替换策略。调用函数LRU_replace，遍历整个组cache[set]，找到时间戳最小的缓存行，返回这个缓存行的位置pos，然后调用update函数，更新cache[set][pos]（同上），并统计eviction：result[eviction]++
代码
//核心代码 void cache_simulate(cache_line** cache, int set, unsigned long tag) { bool find = false; //标识是否命中 int col = E; int pos = 0; for(int j=0; j //命中了(有效位为1，且与某一个高速缓存行的标志位匹配上了) if(cache[set][j].valid == 1 && cache[set][j].tag == tag) { pos = j; //对高速缓存行j进行更新 update(cache[set], HIT, pos, tag); find = true; break; } } //如果没有命中，则先检验这个组是否满了,通过维护一个数组occupancy，可以获得组set中有效缓存行的数量 if(!find) { //如果还有空的缓存行，则直接将内存块存放到这个空白行中 if(occupancy[set] != E) { occupancy[set]++; //要加载内存块到一个空缓存行中，占用量+1 for(int j=0; j if(cache[set][j].valid == 0) { pos = j; update(cache[set], MISS, pos, tag); break; } } }else //如果整个组都满了，没有空白行，则此时需要用LRU策略替换掉一个缓存行 { pos = LRU_replace(cache[set]); //获取要被替换的行号 update(cache[set], MISS, pos, tag); update(cache[set], EVICTION, pos, tag); //更新 } } } //更新 void update(cache_line* cache_set, enum Category category, int pos, int tag) { void update(cache_line* cache_set, enum Category category, int pos, int tag) { result[category]++; //统计相应的缓存情况（命中、不命中、替换） printf("%s ", category_string[category]); cache_set[pos].tag = tag; //更新标志位 cache_set[pos].valid = 1; //更新有效位 cache_set[pos].timestamp = T; //更新时间戳 T++; //每次更新，都要增加时间T } } //LRU替换,暴力搜索时间戳最小的缓存行，返回行号pos int LRU_replace(cache_line* cache_set) { int min = cache_set[0].timestamp; int pos = 0; for(int j=1; j if(cache_set[j].timestamp
