Cache Lab 分为两部分，编写一个高速缓存模拟器以及要求优化矩阵转置的核心函数，以最小化对模拟的高速缓存的不命中次数。本实验对我这种代码能力较差的人来说还是很有难度的。
在开始实验前，强烈建议先阅读以下学习资料：
实验说明文档：Writeup
CMU 关于 Cache Lab 的 PPT：Cache Lab Implementation and Blocking
CMU 关于分块优化的讲解： Using Blocking to Increase Temporal Locality
本人踩的坑：我的 lab 环境是 Windows11 + wsl2。由于 wsl2 跨 OS 磁盘访问非常慢，而我是将文件放在 Windows 下进行的实验，Part B 部分的测试结果甚至无法跑出来！所以，建议用虚拟机进行实验，如果你也是 wsl2 用户，请将实验文件放在 wsl2 自己的目录下！
Part A: Writing a Cache SimulatorPart A 要求在csim.c下编写一个高速缓存模拟器来对内存读写操作进行正确的反馈。这个模拟器有 6 个参数：
Usage: ./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 = 2s is the number of sets) • -E <E>: Associativity (number of lines per set) • -b <b>: Number of block bits (B = 2b is the block size) • -t <tracefile>: Name of the valgrind trace to replay其中，输入的 trace 的格式为：[space]operation address, size，operation 有 4 种：
I表示加载指令
L 加载数据
S存储数据
M 修改数据
模拟器不需要考虑加载指令，而M指令就相当于先进行L再进行S，因此，要考虑的情况其实并不多。模拟器要做出的反馈有 3 种：
hit：命中，表示要操作的数据在对应组的其中一行
miss：不命中，表示要操作的数据不在对应组的任何一行
eviction：驱赶，表示要操作的数据的对应组已满，进行了替换操作
回顾：Cache 结构
Cache 类似于一个二维数组，它有\(S=2^s\)组，每组有 E 行，每行存储的字节也是固定的。其中，每行都有一个有效位，和一个标记位。想要查找到对应的字节，我们的地址需要三部分组成：
s，索引位，找到对应的组序号
tag，标记位，在组中的每一行进行匹配，判断能否命中
b，块偏移，表明在找到的行中的具体位置。本实验不考虑块便宜，完全可以忽略。
那么，Cache 中的有效位是干什么的呢？判断该行是否为空。这里有一个概念：冷不命中，表示该缓存块为空造成的不命中。而一旦确定不命中不是冷不命中，那么就需要考虑行替换的问题了。我认为，行替换关乎着 Cache 的效率，是 Cache 设计的核心。
回顾：替换策略当 CPU 要处理的字不在组中任何一行，且组中没有一个空行，那就必须从里面选取一个非空行进行替换。选取哪个空行进行替换呢？书上给了我们两种策略：
LFU，最不常使用策略。替换在过去某个窗口时间内引用次数最少的那一行
LRU，最近最少使用策略。替换最后一次访问时间最久远的哪一行
本实验要求采取的策略为 LRU。
那么代码如何实现呢？我的第一反应是实现 S 个双向链表，每个链表有 E 个结点，对应于组中的每一行，每当访问了其中的一行，就把这个结点移动到链表的头部，后续替换的时候只需要选择链尾的结点就好了。但是，为了简单，我还是选择了 PPT 中提示的相对简单的设置时间戳的办法，双向链表以后有时间再写吧。
下面就可以正式开始 Part A 了！我对我写的模拟器的核心部分进行讲解。
数据结构定义了Cache结构体
typedef struct cache_ { int S; int E; int B; Cache_line **line; } Cache;用Cache表示一个缓存，它包括 S, B, E 等特征，以及前面说过的，每一个缓存类似于一个二位数组，数组的每一个元素就是缓存中的行所以用一个line来表示这一信息：
typedef struct cache_line { int valid; //有效位 int tag; //标记位 int time_tamp; //时间戳 } Cache_line;valid以及tag不再赘述，这里的time_tamp表示时间戳，是 LRU 策略需要用到的特征。Cache 初始值设置如下：
void Init_Cache(int s, int E, int b) { int S = 1 << s; int B = 1 << b; cache = (Cache *)malloc(sizeof(Cache)); cache->S = S; cache->E = E; cache->B = B; cache->line = (Cache_line **)malloc(sizeof(Cache_line *) * S); for (int i = 0; i < S; i++) { cache->line[i] = (Cache_line *)malloc(sizeof(Cache_line) * E); for (int j = 0; j < E; j++) { cache->line[i][j].valid = 0; //初始时，高速缓存是空的 cache->line[i][j].tag = -1; cache->line[i][j].time_tamp = 0; } } }注意，时间戳初始设置为0。
LRU 时间戳实现