高速缓存 Cache
目前现代的超标量处理器都是哈佛结构，为了让高速处理器匹配低速的存储器，通常采用的多级 Cache 结构。其中，L1 Cache 通常分为 ICache 与 DCache ，分别用于指令和数据。ICache 的设计一般只需要考虑读取的情况，而 DCache 还需要考虑写入的情况。而本次实验是为了实现一个兼具读写的 Cache ，可以看作为一个 DCache 。
Cache 由两部分组成：Tag 与 Data，其中 Data 部分用来保存一片连续地址的数据，而 Tag 部分则存储这片连续数据的公共地址，一个 Tag 与其对应的 Data 构成的一行称为一个 Cache Line **，而 Cache Line 中的数据部分称为数据块（Data Block），如果一个数据可以存储在 Cache 中的多个地方（一般是多路设计的情况下），**这些被同一个地址找到的多个 Cache Line 称为一个 Cache Set。
Cache 分为三种主要的实现方式：
- 直接映射（Direct-mapped） Cache
- 组相连（Set-associative） Cache
- 全相连（Fully-associative） Cache 。
直接映射 Cache
这种结构的 Cache 是最容易实现的一种 Cache ，可以认为是只有一个 Way 的组相连 Cache ，处理器访问存储器的地址会被分为三个部分：Tag、Index 以及 Block Offset，结构如下图所示：
其之所以被称作直接映射，是因为地址中的 Index 字段直接作为 Cache Line 地址，这样，对于所有 Index 相同的存储器地址，都会寻址到同一个 Cache Line ，这就产生了冲突，这也是直接映射结构 Cache 的一大缺点。这种结构甚至简单到不需要替换算法，但是其执行效率也是最低的，现代处理器中很少会使用这种方式了。
组相连 Cache
这种方式的提出是为了解决直接映射 Cache 最大的一个问题：Index 相同的数据只能放在一个 Cache Line 中。
组相连 Cache 使用了 Cache Set的概念，一个 Cache Set 包含多个 Cache Line ，这些 Cache Line 的 Index 都相同。当一个 Cache Set 中的某一个 Cache Line 被占用，而另一个 Cache Line 空闲时，就不必踢掉已有的数据，而是使用空闲的槽位，这样就大大降低了缺失率，而一个 Cache Set 所包含的 Cache Line 就被成为这个 Cache 的相连度。例如，若一个 Cache Set 包含两个 Cache Line ，则这个 Cache 称为 2 路组相连 Cache ，结构如下图所示：
上图中可以看到， Cache 被分成了两个存储区域。其中，一个存储区域叫做一“路”。
可以看到，由于需要从多个 Cache Line 中选择一个匹配的结果，因此这种实现方式相对于直接映射结构的 Cache 而言延迟会更大，有时候甚至需要将其访问过程流水化，以减少对处理器频率的影响，这样会导致 load 指令的延迟（Latency）增大，一定程度上影响了处理器的执行效率，但是这种方式的优点在于，它可以显著地减少 Cache 缺失发生的频率，因此在现代的处理器中得到了广泛的应用。
在实际实现中，Tag 和 Data 部分实际上是分开的，分别叫做 Tag SRAM 和 Data SRAM。对于这种实现，可以采用并行访问（即同时访问 Tag SRAM 和 Data SRAM）及串行访问（即先访问 Tag SRAM 再访问 Data SRAM）方法。
Note
在本次实验中，Tag 和 Data 均采用 BRAM 并行访问实现
对于并行访问方法而言，在读取 Tag 的同时，需要将每一路 Index 对应的的 Data 部分全部读取出来，然后送到多路选择器上，这个多路选择器受到 Tag 比较结果的控制，选出对应的 Data Block，然后根据存储器地址中 Block Offset 的值，选择出合适的字节，一般将选择字节的这个过程称为数据对齐（Data Alignment）
Note
本次实验仅考虑并行访问的实现，如果命中 Cache 只需要一个周期就可以将对应数据读出。而串行访问的实现效率较低，不予考虑。
全相连 Cache
这种 Cache 实际上可以认为是只有一个 Set 的组相连 Cache ，在这种 Cache 中，存储器地址中将不再有 Index 部分，因为数据可以放在任何一个 Cache Line 中，这实际上就是一个内容寻址的存储器（Content Address Memory，CAM），在实际设计中，通常采用 Tag CAM + Data SRAM 的结构，以减少 CAM 过大所引起的走线延迟问题，并因此导致这种结构的 Cache 一般容量都不会太大，多见于 TLB 的设计中。
Cache 的写入策略
由于一般 ICache 不会被直接写入内容，即使有自修改（Self-modifying），也通常是借助 DCache 实现的，因此，这里仅讨论 DCache 的写入策略。
DCache 的写入策略可以总结为写通（Write Through）和写回（Write Back）。所谓写通是指，对 Dache 的所有写入操作会被同时在其下级存储器上执行，但由于下级存储器的访问时间一般来说比较长，而 store 指令在程序中出现的频率又比较高，这样必然会导致处理器的执行效率下降；所谓写回则是指，数据写到 DCache 后，对应的 Cache Line 会被标记为 Dirty，只有当这个 Cache Line 被替换时，其数据才会写入下级存储器，这种方式会大大提升处理器的执行效率，但是会造成 DCache 与下级存储器的数据不一致（Non-consistent）问题。
上面的讨论都是假设在写 DCache 时，要写入的地址已经存在与 DCache 中，但事实上这个地址有可能并不存在于 DCache 中，这就发生了写缺失（Write Miss），这种情况的处理策略也可以总结为两种：Non-Write Allocate 与 Write Allocate。所谓 Non-Write Allocate 是指，直接将数据写到下级存储器中，而并不写到 DCache 中；所谓 Write Allocate 是指，首先将写入地址对应的整个数据块取回 DCache 中，然后再将写入到 DCache 中的数据合并到这个数据块中，之所以需要先取回，是因为一次写操作的数据量远远小于一个数据块的大小，如果不进行取回则直接写入 DCache 并标记 Dirty，后期写回处理器时，必然会造成其周围的数据被破坏。一般来说，写通总是配合 Non-Write Allocate 使用，而 Write Back 则通常和 Write Allocate 配合使用。可以看出，Write Back 与 Write Allocate 配合的方式设计复杂度是最高的，但是其效率也是最好的。
Note
本次实验给出的直接映射 Cache 就是采用的写回写分配的写入策略。
Cache 的替换策略
首先，只有组相连和全相连 Cache 才需要考虑替换策略，其次，只有当一个 Cache Set 对应的所有的 Cache Line 都用完（对于组相连）或所有 Cache Line 都用完（对于全相连）时，才需要考虑替换策略（否则直接将数据填到空闲 Cache Line 即可，不需要做替换），这里介绍几种最常用的替换算法。
近期最少使用法（LRU）
这种方法会选择最近被使用次数最少的 Cache Line ，为此，需要给每个 Cache Line 设置一个年龄（Age）字段，每当一个 Cache Line 被访问时，其他 Cache Line 的年龄都会加一，而被访问的 Cache Line 的年龄会被清零，每次替换年龄最大的那一行 Cache Line 。这种方法的优点在于，它可以保证被频繁访问的数据不会被替换，因此，LRU替换策略的缺失率理论上是最低的。
但是，随着 Cache 相关度的增加，这种策略实现非常昂贵，因此，对于相关性很高的 Cache ，通常都是使用伪 LRU 方法，即将所有的 way 进行分组，每一组使用一个1bit的年龄部分，同时采用树状方式多级分组，通常采用二叉树结构。例如对于一个8路组相连 Cache ，采用如下方式实现伪 LRU：
Note
本次实验实现的 LRU 替换策略不限制是否采用伪 LRU（伪 LRU 实现起来性能更好但是需要详细解释原理）
先进先出法（FIFO）
FIFO 替换算法是一种简单而直观的替换策略。它基于先进先出的原则，即最先进入 Cache 的数据最先被替换出去。
在 FIFO 替换策略中，每个 Cache Line 都会有一个进入时间戳（或者称为访问序列编号），表示该 Cache Line 最近进入 Cache 的时间。当需要替换 Cache Line 时，选择进入时间戳最早的那个 Cache Line 进行替换。
实现 FIFO 替换策略的一种常见方式是使用一个队列数据结构。每当一个 Cache Line 被填入 Cache 时，就将其加入队列的尾部。当需要替换 Cache Line 时，直接选择队列头部的 Cache Line 进行替换。
FIFO 替换策略的优点在于简单易实现，并且不需要额外的硬件支持。但是，它可能会导致低效的缓存利用，因为有可能会将刚刚被频繁访问的数据替换出去，而这些数据可能在未来还会被再次访问。
随机替换
由于 Cache 的替换算法一般使用硬件实现，因此不可能做的很复杂。这种方法不需要记录每个 way 的年龄信息，而是顾名思义，随机选择一个 way 进行替换。
尽管相比于 LRU 替换而言，这种方式发生缺失的频率会更高一些，但随着 Cache 容量的增大，这个差距是越来越小的。事实上，在实际的设计中很难实现严格的随机，而是使用时钟算法（Clock Algorithm）来实现近似的随机。
所谓时钟算法，就是使用一个计数器，每替换一次 Cache Line ，这个计数器就加一，利用计数器当前的值，从被选定的 Cache Set 中找到要替换的 Cache Line 。这是一种不错的折中方法。
Note
不限制随机选择的产生方式，但是需要阐述清楚替换原理。