Lab4: 缓存模拟器

小实验说明

小实验 (Labs) 是 ICS 这门课程里的一些综合编程题，旨在结合课堂知识解决一些实际中的问题。因为问题来自实际，所以有时候未必能立即在课本上找到相关知识的答案，而是需要 “活学活用”。因此，大家需要利用互联网上的知识解决这些问题，但不要试图直接搜索这些问题的答案，即便有也不要点进去 (也请自觉不要公开发布答案)。

Deadline: 2022 年 12 月 25 日 23:59:59。本实验安排在期末考试前截止，因为本实验内容对期末考试帮助很大：往年每年都会有一道关于 cache 细节的题目，现场查书是来不及的。

1. 背景

(这个实验是 yzh 从旧版PA里摘出来的，所以你们反正是逃不了的。)

怎样优化系统设计和实现让系统/程序运行得更快、怎样查找程序中的 bug 等是计算机系统和软件中的核心研究问题，而在程序运行时记录日志供之后分析是其中很重要的一种技术手段，这里有两个问题：

怎样在程序运行时进行记录？除了手工在程序中添加 printf 之外，我们有很多自动的工具，例如程序插装工具、profiler 等，都能输出某种形式的程序运行日志。例如，function call trace 是函数调用的序列；memory trace 是内存访问的序列 (这个实验中用到)。
在有了程序执行的 trace 之后，怎样用记录的一次程序执行来指导系统的优化或是寻找系统中潜在的bug。

动态分析是计算机系统/软件工程领域非常 active 的研究 topic：怎么又快又好地得到我们想要的日志？怎样从日志中分析出对我们有用的信息，例如性能瓶颈、软件 bug？

2. 实验要求

2.1 实验内容

这个编程实验需要模拟实现一个简单的 cache，并尝试实现各种替换算法来优化程序的性能。所谓模拟，即我们已有所有内存访问的序列，你需要 “模拟” 出 cache 的行为，从而评估不同配置的 cache 对程序运行的影响。

你需要在 cache.c 中实现如下函数：

// 从 cache 中读出 addr 地址处的 4 字节数据
// 若缺失，需要先从内存中读入数据
uint32_t cache_read(uintptr_t addr);

// 往 cache 中 addr 地址所属的块写入数据 data，写掩码为 wmask
// 例如当 wmask 为 0xff 时，只写入低8比特
// 若缺失，需要从先内存中读入数据
void cache_write(uintptr_t addr, uint32_t data, uint32_t wmask);

// 初始化一个数据大小为 2^total_size_width B，关联度为 2^associativity_width 的 cache
// 例如 init_cache(14, 2) 将初始化一个 16KB，4 路组相联的cache
// 将所有 valid bit 置为无效即可
void init_cache(int total_size_width, int associativity_width);

另外 cache 的一些特性如下:

块大小为 64B (见 common.h 中 BLOCK_SIZE 的定义)
替换算法采用随机方式
写回，写分配

mem.c 中提供了如下两个函数，cache 缺失/写回的时候需要用到它们:

// 从块号为`block_num`的内存地址中读出一整个cache块大小的内容到`buf`中
void mem_read(uintptr_t block_num, uint8_t *buf);
// 往块号为`block_num`的内存地址中写入一整个cache块大小的内容`buf`
void mem_write(uintptr_t block_num, uint8_t *buf);

我们已经提供了一份框架代码，工具的命令行格式为：

./cachesim-64 [-r seed] [trace]

其中 seed 是随机种子，可以用于确定性回放帮助调试，缺省时会用系统时间作为种子；trace 是 bz2 压缩格式的访存序列，缺省时会产生随机访存序列来测试。

2.2 (选做，Online Judge 不评测) 理解 cache 的复杂性对频率的影响

我们提供了一个真实的 workload 供大家理解不同 cache 设计对性能产生的潜在影响：microbench-test.log.bz2。

不要解压缩

已有的代码可以通过调用外部命令 (bzcat) 直接读取压缩的日志文件。在一个程序里调用另一个程序似乎还是头一次，大家可以仔细阅读代码，其中使用了 popen 函数 (RTFM)。

在完成实现之后，你就可以观察 cache 的各类性能指标：缓存的缺失率等。在实际的硬件实现中，更复杂的缓存意味着更高的命中率，但也意味着更低的访问速度。虽然流水线技术能降低缓存对处理器频率的影响，复杂的缓存降低了缺失的次数 (提升了性能) 的另一方面也降低了处理器的 IPC (降低了性能)。计算机系统中总是有这样的 trade-offs，使设计高效的系统成为一个很大的挑战。

为了评估一个给定 cache 的性能，你可以对以下几方面进行建模：

cache 的复杂性，具体度量为访问 cache 所需的时间 (ns)。这会降低处理器的频率。
cache miss 时的代价，根据内存访问的时间建模。

尝试修改 cache 的各种参数 (例如把 cache 总大小改成 256B 等)，并为每一个模型估计它的访问时间，然后根据你建立的模型计算给定 workload 的 “运行时间”。根据你对计算机系统的理解，你可能可以给出例如 microbench-test 等 workload 下你认为最佳的 cache 设计。

例如，你可以建立带参数的模型，例如假设 associativity 为 $k$，则访问时间为 $ak^2 + b$。这样你可以考察 $a$, $b$ 对 cache 性能的影响。

日志分析工具的好处在这里体现得淋漓尽致，你可以轻而易举地修改一个 cache 的 “构造”，马上重新开始统计新的数据，而不需要做一个真正的 cache 才开始测试。自从 cache 的概念被提出来，无数的研究者提出了五花八门的 cache。学术界中研究 cache 的论文更是数不胜数，但被工业界采纳的 cache 研究却寥寥无几，究其原因只有一个——纸上谈兵，无法用硬件高效地实现。实际系统中的 cache 和多处理器内存一致性、MMU 等都是紧密耦合的，因此 cache 的实现可能比大家想象得要困难。

2.3 代码获取与提交

Academic Integrity

从网上或别人那里复制几行代码非常简单——但你如果遵守 academic integrity，自己尝试完成，就会遇到巨大的困难 (尤其如果你没有试着用正确的工具、正确的方法诊断问题)。这是我们给你必要的训练。

请使用我们的 Makefile 编译 (在实验目录中执行 make)，确保 Git 记录完整。

在之前实验的 ics-workbench 中，在终端执行

git pull origin lab4

可以获得实验的框架代码。提交方法同之前的 Lab: 在实验的工作目录中执行 make submit。需要设置 STUID (学号) 和 STUNAME (中文姓名) 环境变量。

2.4 评分与正确性标准

我们会用不同的设定测试你的 cache.c 的正确性。只有一个 Easy Test Case。

3. 实验指南

3.1 Cache 的故事

随着集成电路技术的发展，CPU 越来越快；另一方面，DRAM 的速度却受限于它本身的工作原理。我们先简要解释一下这两者的差别。DRAM 的存储空间可以看成若干个二维矩阵 (若干个 bank)，矩阵中的每个元素包含一个晶体管和一个电容，晶体管充当开关的作用，功能上相当于读写使能；电容用来存储一个 bit，当电容的电量大于 50%，就认为是 1，否则就认为是 0。但是电容是会漏电的，如果不进行任何操作的话，电容中的电量就会不断下降，1 最终会变成 0，存储数据就丢失了。

为了避免这种情况，DRAM 必须定时刷新，读出存储单元的每一个 bit，如果表示 1，就往里面充电。DRAM 每次读操作都会读出二维矩阵中的一行，由于电容会漏电的特性，在将一行数据读出之前，还要对这一行的电容进行预充电，防止在读出的过程中有的电容电量下降到 50% 以下而被误认为是 0。

而 CPU 的寄存器采用的是 SRAM，是通过一个触发器来存储一个 bit，具体来说就是 4-6 个晶体管，只要不断电，SRAM 中的数据就不会丢失，不需要定时刷新，也不需要预充电，读写速度随着主频的提升而提升。

由于 RISC 架构的指令少，格式规整，硬件的逻辑不算特别复杂，CPU 做出来之后，芯片上还多出了很多面积。为了把这些面积利用起来，架构师们提出了 cache 的概念，把剩下的面积用于 SRAM，同时也为了弥补 CPU 和 Memory 之前性能的鸿沟。CISC 的运气就没那么好了，指令多，格式不规整，硬件逻辑十分复杂，在芯片上一时间腾不出地方来放 cache，所以你在 i386 手册上找不到和 cache 相关的内容。当 CISC 架构师们意识到复杂的电路逻辑已经成为了提高性能的瓶颈时，他们才向 RISC 取经，把指令分解成微指令来执行：

                              R[EAX] <- M[var]
addl $1, var        =>        R[EAX] <- R[EAX] + 1
                              M[var] <- R[EAX]

这样就减少了硬件的逻辑，让微指令的执行流水化的同时，也可以腾出面积来做 cache 了，不过这些都是后话了。

3.2 Cache 的思想和设计

Fast and Slow Paths

计算机系统中有一个很常见的解决问题的思路，就是把问题分类：对于一个问题，我们存在一个不完美但简单、高效的解决方案 (例如 99.9% 成功率)，而一个完美的解决方案代价很大时，我们不妨先试着用简单分方法做做看 (fast path)，如果不成功再调用完美的方案。人类同样也有这样的系统，大家不妨读一读一本有趣的课外书 “Thinking: Fast and Slow”。

Cache 工作方式实际上是局部性原理的应用：

如果程序访问了一个内存区间，那么这个内存区间很有可能在不久的将来会被再次访问，这就是时间局部性。例如循环执行一小段代码，或者是对一个变量进行读写 (addl $1, var 需要将 var 变量从内存中读出，加 1 之后再写回内存)。
如果程序访问了一个内存区间，那么这个内存区间的相邻区间很有可能在不久的将来会被访问，这就是空间局部性。例如顺序执行代码，或者是扫描数组元素。

相应的：

为了利用时间局部性，cache 将暂时存放从内存读出的数据，当 CPU 打算再次访问这些数据的时候，它不需要去访问内存，而是直接在 cache 中读出即可。就这样把数据一放，那些小循环的执行速度马上提高了数十倍。
为了利用空间局部性，cache 从内存中读数据的时候，并不是 CPU 要多少读多少，而是一次多读点。Cache 向内存进行读写的基本单位是 cache block (块)。现代的 cache 设计还会在空闲的时候进行预取 (prefetch)，当 CPU 一直在计算的时候，cache 会趁这段时间向内存拿点数据，将来 CPU 正好需要的话就不用再花时间拿了。

这听起来很不错，有了 cache，只要 CPU 访问 cache 的时候命中，就不需要把大量时间花费在访存上面了。不过为了保证 cache 的命中率，cache 本身也需要处理很多问题，例如：

一个内存区域可以被映射到多少个 cache block？少了容易冲突，多了电路逻辑和功耗都会上升。对这个问题的回答划分了不同的 cache 组织方式，包括 direct-mapped (直接映射), set associative (组相联) 和 fully associative (全相联)。
冲突的时候，需要替换哪一个 cache block？这个问题的回答涉及到替换算法，最理想的情况是替换那个很长时间都没访问过的 cache block，这就是 LRU 算法。但这对硬件实现来说太复杂了，对于 8-way set associative 来说，每一个 set 中的 8 个 cache block 都有 $8! = 40320$ 种可能的访问情况，编码至少需要 16 个 bit，译码则需要更大的代价，电路逻辑和时延都会上升。因此实际上会采用伪 LRU 算法，近似记录 cache block 的访问情况，从而降低硬件复杂度。也有研究表明，随机替换的效果也不会很差。
写 cache 的时候要不要每次都写回到内存?这个问题涉及到写策略，write through (写通) 策略要求每次 cache 的写操作都同时更新内存，cache 中的数据和内存中的数据总是一致的；write back (写回) 策略则等到 cache block 被替换才更新内存，就节省了很多内存写操作，但数据一致性得不到保证，最新的数据有可能在 cache 中。数据一致性在多核架构中是十分重要的，如果一个核通过访问内存拿到了一个过时的数据，用它来进行运算得到的结果就是错误的。
写缺失的时候要不要在 cache 中分配一个 cache block？分配就更容易引起冲突，不分配就没有用到时间局部性。

这些问题并没有完美的回答，任何一个选择都是 trade-off，想获得好处势必要付出相应的代价，计算机就是这样一个公平的世界。

另一个值得考虑的问题是如何降低 cache 缺失的代价。一种方法是采用多级的 cache 结构，当 L1 cache 发生缺失时，就去 L2 cache 中查找，只有当 L2 cache 也发生缺失时，才去访问内存。L2 cache 通常比 L1 cache 要大，所以查找所花时间要多一些，但怎么说也比访问内存要快。还有一种方法是采用 victim cache，被替换的 cache block 先临时存放在 victim cache 中，等到要访问那个不幸被替换的 cache block 的时候，可以从 victim cache 中找回来。实验数据表明，仅仅是一个大小只有 4 项的 victim cache，对于 direct-mapped 组织方式的 cache 有十分明显的性能提升，有时候可以节省高达 90% 的访存。

上面叙述的只是 CPU cache，事实上计算机世界到处蕴含着 cache 的思想。在你阅读本页面的时候，本页面的内容已经被存放到网页缓存中了；使用 printf 并没有及时输出，是因为每次只输出一个字符需要花很大的代价，因此程序会将内容先放在输出缓存区，等到缓冲区满了再输出，这其实有点 write back 的影子 (实际情况要稍微复杂一些，我们会在《操作系统》课上回到这个话题)。像内存、磁盘这些相对于 CPU 来说的 “低速” 硬件，都有相应的硬件 cache 来提高性能。

再比如，现代的 DRAM 一般都包含以下两种功能：

每个 bank 中都有一个行缓存，读出一行的时候会把数据放到行缓存中，如果接下来的访存操作的目的数据正好在行缓存中，就直接对行缓存进行操作，而不需要再进行预充电。
采用 burst (突发读写) 技术，每次读写 DRAM 的时候不仅读写目的存储单元，把其相邻的存储单元也一同进行读写，这样对于一些物理存储连续的操作 (例如数组)，一次 DRAM 操作就可以读写多个存储单元了。

明白 cache 存在的价值之后，你就不难理解这些技术的意义了。可惜的是，DRAM 仍旧摆脱不了定时刷新的命运。

思考题: 数据对齐和存储层次结构

想一想，为什么编译器为变量分配存储空间的时候一般都会对齐?访问一个没有对齐的存储空间会经历怎么样的过程？

关于 cache 具体如何工作，课上都已经详细讲过，这里就不另外叙述了。值得一提的是维基百科中的 CPU cache 页面，里面除了课堂上讲过的知识，还有诸多延伸，值得仔细琢磨。

3.2 测试你的 Cache 实现

框架代码提供了一套 CPU 接口 cpu_read() 和 cpu_write()，它们会调用你实现的 cache_read() 和 cache_write()。同时框架代码提供了一套 uncache 的接口 cpu_uncache_read() 和 cpu_uncache_write()，用于直接访问另一个独立的内存这样是为了对你的实现进行对比测试，测试的主要思想是 cache 是对 CPU 透明的：从 CPU 端来看，有无 cache 并不影响读数据的结果。因此，框架代码会随机生成一些访存请求，同时输入到两套CPU接口中，并对比读接口的结果。若在某一时刻发现读结果不一致，就会触发 “assertion failed”。

另外为了方便调试，我们允许将随机种子作为参数来运行 cache 程序，如果使用相同的种子多次运行，就会产生一样的随机数序列。