Open urain39 opened 1 year ago
CPU 中的 Cache 一般由缓存行（Cache Line）、缓存集（Cache Set）组成。缓存行是由 2^B 个连续字节组成的缓存的基本单位；而缓存集则是一组缓存行的容器。
B 的取值范围一般是 5~8。
CPU 中的 Cache 查找是通过拆分地址实现的。一般情况下，地址会拆分为 TAG、INDEX、OFFSET 三个部分。
首先 Cache 会使用 INDEX 索引地址所在的缓存集；然后使用 TAG 找到准确的地址；最后使用 OFFSET 获取到实际值。
INDEX 的作用是为了优化查询。正是因为它的存在，我们才能将 C 个缓存行的查找范围缩小到 C / S 次（S 是缓存集数量）。
理论可行，但实际不行。使用高位作为 INDEX 会导致我们在访问固定地址段的内存时，不能最大化利用缓存容量（都映射到同一缓存集里了）。
我居然真的在网上看到有些文章把 TAG 和 INDEX 搞反了！
如果缓存集的容量为 N，那么我就叫其 N 路（N-way）。如缓存集中有8个缓存行，那么我们就将其叫做8路。
N-way 全称是 N-way set associative（N 路缓存集关联）。
当 N 为1时，我们将其称为直接映射（Direct Mapped）。这种情况下的查找效率最高，但灵活性较差（无法引入替换策略）。
还有个全关联（fully associative）的概念。它没有 INDEX，查找效率非常低。你可以看作是只有一个缓存集的情况。这里就不细讲了。
仅仅了解 CPU 中的 Cache 组成和查找过程是远远不够的。我们还需要学习一个非常重要的概念——替换策略（Replacement Policy）。
缓存的大小是固定的，它肯定也会有写满的时候。如果此时有新数据写入，那么我们就不得不从已使用的缓存中选择一块区域使用。
这个过程完全取决于替换策略。常见的实现按命中率从低到高主要有 FIFO、Random、Pseudo-LRU 三种。
替换策略只针对缓存集。这是因为引入 INDEX 对查找优化后，缓存行都被拆散在缓存集里了。当然，没有 INDEX 另说。
使用哪种替换策略取决于预算成本。对于高性能 CPU，我推荐使用 Pseudo-LRU；对于入门级 CPU 我推荐 Random；实在不行再使用 FIFO。
我听说 MIPS 好像很喜欢用 Random 替换策略……另外真的有人使用 FIFO 替换策略吗？
6502 是70年代中期到80年代末期最成功的 CPU 之一。它的字长为 8-bit，拥有 16-bit 长的地址总线，可寻址 64 KiB 空间。
在添加缓存前，我们需要先确定缓存大小。一般而言，通过地址总线折半算法可以直接得到这个值。即 16-bit 折半为 8-bit，得到缓存大小为 256 字节。
64-bit 之后，这个方法就不好用了。因为我们的内存并没有真的利用上这么长的地址总线。最多也只是利用到了 40-bit 左右。
缓存大小确定后，我们也就能依此确定 INDEX、OFFSET的长度。我们依据上面的 Cache 组成，可以得到缓存大小的公式为N * 2^(INDEX + OFFSET)。N 为 N 路缓存。
N * 2^(INDEX + OFFSET)
我们将实际值代入，可以得到方程N * 2^(INDEX + OFFSET) = 256。这个方程并没有固定解，我们按需求分配就行。我使用的解是 N=4, INDEX=2, OFFSET=4。剩下的部分全分给 TAG。
N * 2^(INDEX + OFFSET) = 256
考虑到 8-bit CPU 的特殊性，我们不建议 TAG、INDEX、OFFSET 任意一个长度大于8。上面的设计换算后，TAG=10，就已经超出这个值了。
要解决这个问题，我们就必须扩大缓存大小或者缩小缓存集容量。如扩大缓存，那么可以将解改成 N=2, INDEX=2, OFFSET=6（512字节缓存）；或者缩小缓存集容量，将解改成 N=1, INDEX=2, OFFSET=6（256字节直接映射缓存）。
参考/引用：
基础知识点
Cache 的组成
CPU 中的 Cache 一般由缓存行（Cache Line）、缓存集（Cache Set）组成。缓存行是由 2^B 个连续字节组成的缓存的基本单位；而缓存集则是一组缓存行的容器。
Cache 查找过程
CPU 中的 Cache 查找是通过拆分地址实现的。一般情况下，地址会拆分为 TAG、INDEX、OFFSET 三个部分。
首先 Cache 会使用 INDEX 索引地址所在的缓存集；然后使用 TAG 找到准确的地址；最后使用 OFFSET 获取到实际值。
为什么要有 INDEX？
INDEX 的作用是为了优化查询。正是因为它的存在，我们才能将 C 个缓存行的查找范围缩小到 C / S 次（S 是缓存集数量）。
INDEX 能放到 TAG 前面吗？
理论可行，但实际不行。使用高位作为 INDEX 会导致我们在访问固定地址段的内存时，不能最大化利用缓存容量（都映射到同一缓存集里了）。
N 路缓存集关联
如果缓存集的容量为 N，那么我就叫其 N 路（N-way）。如缓存集中有8个缓存行，那么我们就将其叫做8路。
当 N 为1时，我们将其称为直接映射（Direct Mapped）。这种情况下的查找效率最高，但灵活性较差（无法引入替换策略）。
进阶知识点
引入替换策略
仅仅了解 CPU 中的 Cache 组成和查找过程是远远不够的。我们还需要学习一个非常重要的概念——替换策略（Replacement Policy）。
缓存的大小是固定的，它肯定也会有写满的时候。如果此时有新数据写入，那么我们就不得不从已使用的缓存中选择一块区域使用。
这个过程完全取决于替换策略。常见的实现按命中率从低到高主要有 FIFO、Random、Pseudo-LRU 三种。
选择合适的替换策略
使用哪种替换策略取决于预算成本。对于高性能 CPU，我推荐使用 Pseudo-LRU；对于入门级 CPU 我推荐 Random；实在不行再使用 FIFO。
如何设计缓存
给 6502 添加缓存！
在添加缓存前，我们需要先确定缓存大小。一般而言，通过地址总线折半算法可以直接得到这个值。即 16-bit 折半为 8-bit，得到缓存大小为 256 字节。
缓存大小确定后，我们也就能依此确定 INDEX、OFFSET的长度。我们依据上面的 Cache 组成，可以得到缓存大小的公式为
N * 2^(INDEX + OFFSET)。N 为 N 路缓存。我们将实际值代入，可以得到方程
N * 2^(INDEX + OFFSET) = 256。这个方程并没有固定解，我们按需求分配就行。我使用的解是 N=4, INDEX=2, OFFSET=4。剩下的部分全分给 TAG。吹毛求疵（选读）
考虑到 8-bit CPU 的特殊性，我们不建议 TAG、INDEX、OFFSET 任意一个长度大于8。上面的设计换算后，TAG=10，就已经超出这个值了。
要解决这个问题，我们就必须扩大缓存大小或者缩小缓存集容量。如扩大缓存，那么可以将解改成 N=2, INDEX=2, OFFSET=6（512字节缓存）；或者缩小缓存集容量，将解改成 N=1, INDEX=2, OFFSET=6（256字节直接映射缓存）。
参考/引用：