考虑到实验内容的发布早于理论课，因此补充了本章理论介绍的内容，为大家提供一些理论上的参考。

如果阅读完本章仍然有所困惑，可以参考课程教材CSAPP（深入理解计算机系统）的6.2-6.4节。

缓存与局部性原理

存储器层次结构中的缓存

早期计算机系统的存储器层次结构只有三层：CPU寄存器、DRAM主存储器和磁盘存储。不过，由于CPU和主存之间逐渐增大的性能差距，系统设计者被迫在CPU寄存器文件和主存之间插入了一个小的SRAM高速缓存存储器，称为L1高速缓存。SRAM的价格比主存贵，但因其容量远小于主存，因此能很好地解决速度和成本的矛盾。L1高速缓存的访问速度几乎和寄存器一样快，典型的是2~4个时钟周期。

随着CPU和主存之间的性能差距不断增大，系统设计者在L1高速缓存和主存之间又插入了一个更大的高速缓存，称为L2高速缓存，有些现代系统还包括有一个更大的高速缓存，称为L3高速缓存。虽然安排上有很多的变化，但是通用的原则还是一样的，在本实验中，我们可以视为CPU和主存之间只有一个L1高速缓存。

局部性原理

局部性原理是缓存设计所依托的基本思想，大量典型程序的运行情况分析结果表明，无论是存取指令或存取数据所访问的存储单元都趋于聚集在一个较小的连续存储区域中。

局部性原理通常有两种不同的形式：时间局部性和空间局部性。时间局部性可以概括为：刚被访问的存储单元可能不久又将被访问。空间局部性则可以概括为：刚被访问过的存储单元的邻近单位可能不久会被访问。

比如我们访问一个数组的某个内存单元，那么我们很可能紧接着就要访问它相邻的下一个内存单元，或者我们不久之后还要再次访问这一单元，局部性原理正是表达了这样的思想。而进一步地，如果我们能在访问这一内存单元的时候，将它还有与它相邻的一小部分内存单元加入存取速度更高的缓存中，那么在后续访问的过程中，就能够直接到缓存中访问，从而显著加快程序运行的速度，这正体现了缓存设计的基本思想。

通用高速缓存结构

基于以上的介绍，我们对高速缓存（Cache）可以建立起一些抽象的认识：

• 相对大而慢的主存而言，Cache应当是小而快的。
• 对于程序中对某个地址的访问，Cache应当能够获取一个对应的局部块。
• 当程序中对相邻地址继续访问时，可以通过访问Cache来实现，不必再次访问主存。
• Cache应当在程序经常访问的位置发生变化时，腾出空间给新的局部块。

下面我们来详细的介绍通用的Cache的结构：

考虑主存地址为 $n$ 位的计算机系统，主存大小即 $2^n$ 字节，我们取这 $n$ 位中的低 $b$ 位，以 $B=2^b$ 作为一个块的大小，从而将地址空间划分为 $2^{n-b}$ 个块（block）。对应的，地址的低 $b$ 位表示一个字节相对于本块内的位置，我们称为块内偏移（offset），地址的高 $n-b$ 位即表示块号（block number）。其地址格式即如下图所示：

我们可以理解为，Cache在从主存中存取数据时，就是以块为单位进行操作的。相应的，Cache在数据组织的过程中，自然也要以块为基本单元，在存储一个块的同时，Cache也要存储一些与此块相对应的信息，我们将Cache中这样包含了一个块和其相关信息的结构称为行（line）。

主存中有诸多的块，而Cache的大小尽管远小于主存，仍然能存放相当数量的行，我们希望解决从主存的块到Cache的行的映射关系，这里要引入组（set）的概念。我们将主存的所有块分为 $S=2^s$ 组，同时我们将Cache也作对应分组，我们使得主存中同组的那些块仅能映射到Cache中对应组的那些行中。这样我们在拿到一个地址之后，首先分析它所在的分组，再在Cache中对应的分组中查询有没有对应的行，从而降低在Cache中查询的成本。而当Cache同组的所有行都填满之后，我们也只会腾出该组中的行来存放新的数据块，不会影响其他组。

我们希望分组之后相邻的块能被分到不同的组（由于局部性原理，相邻的块也有可能同时需要访问，我们不希望把它们分到同一组来相互挤占有限的Cache资源），因此我们将块号（即内存地址的高 $n-b$ 位）的低 $s$ 位作为组号。而由于主存的分组已经和Cache的分组建立起对应关系，我们在Cache中只需要地址的高 $n-s-b$ 位作为标记（tag），就可以唯一地识别出该组中是否有哪一行存放了我们的想要的主存块。这样划分后的地址格式如下图所示：

相应的Cache结构如下图所示：首先Cache包含 $S=2^s$ 个高速缓存组（set）；每个组包含 $E$ 个高速缓存行（line）；每个行由三部分组成，一个 $B=2^b$ 字节的数据块（block），一个有效位（valid bit）指明这个行保存的信息是否有意义，还有 $t=n-(b+s)$ 个标记位（tag）来唯一地识别组内的某一行。

这样结构的Cache，我们称之为组相联的。

当 $s=0$ ，即组的数量退化为只有一组时， 主存中的任意块都可以映射到Cache中的任意行，这种情况下的Cache我们称为是全相联的。而当 $E = 1$，即Cache中每组的行数退化为只有一行时，这种情况主存中同组的若干块都只能映射到Cache中的特定一行，我们将其称为直接映射。