计算机组成原理学习笔记——Cache 相关知识

• 现在计算机系统中通才都是采用由“Cache-主存”层次和“主存和辅存”层次构成的存储体系，这是为了有效提高存储系统的频宽，因为大多数程序的转移概率不会低且数据分布离散。

一、程序的局部性原理

• 也就是程序访问的局部性原理，包括时间局部性和空间局部性，前者指最近的未来要用到的信息，很可能现在正在使用的信息，因为程序存在循环；后者指最近的未来要用带的信息，很可能与现在正在使用的信息在存储空间上是临近的，因为指令通常是顺序存放、顺序执行的，数据一般也是以向量、数组等形式簇聚地存储在一起的。
• 基于局部性原理，可以将程序正在使用的部分存放在一个高速的、容量小的 Cache中，从而提高程序执行速度。
• 例题：

  //程序A：
  int sumarrayrows(int a[10][10])
  {
  	int  x, y, sum=0;
  	for( x=0; x<10; x++)
  		for( y=0; y<10; y++)
  			sum += a[x][y];
  	return sum;
  }
  
  //程序B：
  int sumarraycols(int a[10][10])
  {
  	int  x, y, sum=0;
  	for( y=0; y<10; y++)
  		for( x=0; x<10; x++)
  			sum += a[x][y];
  	return sum;
  }
  

• 这两个程序从局部性原理上进行分析，谁会执行更快呢？答案是程序 A。
• 这是因为程序 A 访问数组时是按照数组的存放顺序访问的，空间局部性好；而程序 B 则每次都要跳过 10 个数组元素，当主存与 Cache 的交换单位小于这 10 个元素的大小时，则每次访问一个元素都需要装入一个主存块到 Cache 中，没有空间局部性。
  由此，也应该认识到，平时遍历数组时，在无特殊要求的情况下，数组的访问顺序应该和数组的存放顺序一样。

二、Cache 工作原理

• Cache通常用 SRAM制造，基本结构如上。
• Cache 和主存划分成等大的块，Cache 块称作 Cache 行，由若干字节组成，块的长度称为块长或Cache 行长，由于空间有限 Cache 块远少于主存的，因此仅保存主存中最活跃的若干块的副本。
• 带有 Cache 的数据读写操作一般如下步骤：
• 读操作：
• 首先 CPU 发出读请求，若访存地址在 Cache 中命中，直接将地址转换为 Cache 地址并从 Cache 中进行读操作，无需访问主存；若 Cache 不命中，则访问主存并将数据对应的主存块放入 Cache，主存块调入 Cache 中又分为两种情况：
• a、Cache 未满，直接调入；
• b、Cache 已满，使用某种替换算法，用调入的块替换 Cache 中原有的某块。
• 注意：
• CPU 与 Cache 之间以字为单位交换数据，Cache 与主存之间以 Cache 块为单位交换数据。
• 某些计算机采用 Cache 和主存同时访问的方式，当 Cache 命中则主存的访问停止，否则继续访问主存并将数据调入 Cache。
• 写操作：
• CPU 发出写请求，若 Cache 命中则使用一定的写策略开始写入数据，若 Cache 不命中则直接到主存中进行操作

命中率

• CPU 欲访问的信息已在 Cache 中的比率称之为命中率。在一个程序执行期间，Cache 的总命中次数为 Nc，访问主存的次数为 Nm，则命中率 H 为：
  H = Nc / （Nc + Nm）

• H 越接近 1 越好。设 Tc 为命中时 Cache 访问时间，Tm 为未命中时的访问时间，1-H 表示未命中率，则 Cache-主存系统的平均访问时间 Ta 为：
  Ta = HTc + ( 1 - H)Tm。

• 例题：

• 设有 Cache 是主存速度的 5 倍，Cache 命中率为 95%，则采用 Cache 比没用 Cache，存储器的性能提高多少？

• 解：

  • 设 Cache 存取周期为 t，则主存的为 5t，存储器平均访问时间为：
    Ta = 0.95*t + 0.05*5t = 1.2t
  • 则性能为原来的 1.2t/5t 约为 4.17 倍，即提高了 3.17 倍。

三、Cache 的映射方式

• Cache 中的信息都是主存中的副本，所以，通常 Cache 块中都有一个用于指明当前块是主存中哪一块的副本的标记，同时也有一个用于确定当前 Cache 是否有效的有效位。
• 地址映射是指把主存地址空间映射到 Cache 地址空间，这和地址变换（指 CPU 访存时，将主存地址按映射规则换算成 Cache 地址的过程）不同，常用的地址映射方法有：
• 直接映射、全相联映射和组相联映射。

1、直接映射

• 主存块只能装入 Cache 中的唯一位置，若位置上已有内容，则块冲突那么直接将原有信息无条件替换出去。
• 优点是实现简单，缺点是不够灵活，块冲突率高，空间利用率低。
• 直接映射的关系定义为：
  j = i mod 2^c
• j 表示 Cache 的块号，I 是主存的块号，2^c 是Cache 中的总块数。主存块号的低 c 位正好是它要装入的 Cache 行号。
• 给每个 Cache 行设置一个长为 t = m - c 的标记 tag，当主存某块调入 Cache 后，就将其块号的高 t 位设置在对应 Cache 行的标记中。
  
• 直接映射的地址结构为：
  
• CPU 访存过程如下：
  
• 先根据地址中间的 c 位，找到对应 Cache 行并用主存地址高 t 位与 Cache 行标记进行比较，若相等且有效位为 1，则访问 Cache “命中”，此时根据主存地址中低位的块内地址在对应 Cache 行读取信息；若不相等或有效位为 0，则“不命中”，此时 CPU 从主存读出该地址所在的一块信息并调入对应的 Cache 行中，将有效位置 1，并将标记设置为地址的高 t 位，同时将该地址中的内容送入 CPU。

2、全相联映射

• 全相联映射地规则：主存中地每一块可以装入 Cache 中地任何位置，每行地标记用于指出该行取自主存地哪一块，所以 CPU 访存时需要与所有 Cache 行标记进行比较。
• 优点是比较灵活，Cache 块冲突概率小，空间利用率高，命中率也高。
• 缺点就是比较速度较慢，实现成本较高，通常需采用昂贵地按内容寻址地相联存储器进行地址映射，如下：
  
• 其地址结构如下：
  

3、组相联映射

• 组相联映射地规则：将 Cache 空间分成大小相同地组，主存地一个数据块可以装入一组内地任何一个位置，即组间采取直接映射，组内用全相联映射：
  
• 组相联映射是上面两种映射方式的一种折中，组相联映射的关系定义如下：
  j=i mod Q
• j 是 Cache 行组号，I 是主块的块号， Q 是 Cache 组数。当 Q = 1 时，就是全相邻映射，当 Q 是 Cache 块数就是直接映射。若每组有 r 个 Cache 行，则称为 r 路组相联，路数越大，即每组 Cache 行的数量越大，块冲突概率越小，但相联比较电路也越复杂，因此选定适当数量，可使组相联映射成本接近于直接映射，而性能接近全相联映射。
• 组相联映射地址结构如下：
  
• 访存过程如下：
• 先根据访存地址的组号找到对应 Cache 组，再在组内对所有 Cache 行进行高位标记比较，若有一个相等且有效位为 1，则命中，再根据主存地址中的块内地址，在对应 Cache 行读取信息；若不想等或相等但有效位为 0，则不命中，此时访问主存块并将主存块的信息调入对应 Cache 组的任意一个 Cache 空闲行，将有效位置 1，同时将信息送往 CPU。

4、例题

• 若计算机主存地址空间大小为 256MB，按字节编址，其数据 Cache 有 8 行，行长 64B，则：
• 1）采用直接映射方式，Cache 总容量是多少？
• 2）在直接映射方式下，主存地址为 3200（十进制）的主存块对应的 Cache 行号是多少？若采用二路组相联映射呢？
  解：
• 1）每个 Cache 行由有效位（1bit）和标记位、数据位构成，由于主存地址 28 位，其中 6 位为块内地址，3 位为行号，剩余的高位 28 - 6 - 3 = 19 位就是标记位，所以 Cache 总容量 8*(1 + 19 + 512) = 4,256 位。
• 2）直接映射方式下，主存依照 Cache 行大小进行划分，则主存地址 3200 对应的字块号为 3200B / 64B = 50；Cache 有 8 行，50 mod 8 = 2，因此对应的 Cache 行号为 2.
• 二路相联组映射，即将两个 Cache 行合并，组内全相联映射，组间直接映射，所以 50 mod 4 = 2 , 对应的组号为 2，即对应的 Cache 行号为 4 或 6.

5、总结

• 三种映射方式，直接映射的每个主存块只能映射到 Cache 中的某一固定行，全相联映射可以映射到所有 Cache 行，N 路组相联映射可以映射到 N 行。若 Cache 大小、主存块大小一定时：
• 1）直接映射的命中率最低，全相联映射的命中率最高；
• 2）直接映射的判断开销最小、所需时间最短，全相联映射的判断开销最大、所需时间最长；
• 3）直接映射标记所占的额外空间最小，全相联映射标记所占的额外空间开销最大

四、Cache 块替换算法

• 在全相联映射和组相联映射方法中，信息从主存调入 Cache 中时都要用到 Cache 块替换算法，常用的 Cahce 块替换算法有：随机（RAND）算法、先进先出（FIFO）算法、近期最少使用（LRU）算法和最不经常使用（LFU）算法。

1、RAND 算法

• 随机确定替换的 Cache 块，实现比较简单，但是为依据程序访问的局部性原理，因此命中率较低。

2、FIFO 算法

• 选择最早调入的行进行替换，较容易实现，但同样没有依据程序访问的局部性原理，命中率也不高。

3、LRU 算法

• 依据程序访问局部性原理，选择近期内长久没有访问过的 Cache 行作为替换的行，平均命中率高于上面的 FIFO 算法，是堆栈类算法。具体操作是：
• 对每个 Cache 行设置一个计数器，计数值表示主存块的使用情况，根据计数值决定淘汰哪一块，计数值的位数与 Cache 组大小有关，两路一位 LRU 位，四路两位 LRU 位，N 路 log(N) 位 LRU 位。
• 以 4 路为例，主存块 5 个：{1，2，3，4，5}，访问序列：{1，2，3，4，1，2，5，1，2，3，4，5}，则 LRU 算法替换过程如下：
  

计数器变化规则：

• a、命中时，所命中的行的计数器清零，比其低的计数器加 1，其余不变；
• b、未命中且还有空闲行时，新装入的行的计数器置零，其余全部加 1；
• c、未命中且无空闲行时，计数值为 Cache 行总数-1 的行的信息块被淘汰，新装行的块计数器置零，其余全部加 1。 使用 LRU 算法，有时可能出现一种叫做抖动的现象，具体就是集中访问的存储区超过 Cache 组的大小，命中率变得很低。

4、LFU 算法

• 将一段时间内访问次数最少的存储行换出，同样的，每行设置一个计数器，新行建立后从 0 开始计数，每访问一次被访问的行计数器加 1，需要替换时，只需找到计数值最小的行换出。

五、Cache 写策略

• 因为 Cache 中的内容都是主存的块的副本，当对 Cache 中的内容进行更新时，需要用写操作策略来使 Cache 内容和主存内容保持一致，写策略针对命中和未命中两种情况分别提供了全写法、写回法和写分配法、非写分配法。

1、写命中（write hit）

1.1、全写法（写直通法，write-through）

• 当 CPU 对 Cache 写命中，必须把数据同时写入 Cache 和主存；当某一块需要替换时，不必把这一块写回主存，用新调入的块直接覆盖即可。
• 优点是实现简单，能随时保持主存数据的正确性。
• 缺点是增加访存次数，降低 Cache 效率
• 通常为了减少全写法直接写入主存的时间损耗，在 Cache 和主存之间增设一个写缓冲（Write Buffer），CPU 同时写数据到 Cache 和写缓冲中，写缓冲在控制将内容写入主存；写缓冲是一个FIFO 队列，写缓冲解决速度匹配问题，但是若频繁写时，可能出现写缓冲饱和和溢出。
  

1.2、写回法（write-back）

• 当 CPU 对 Cache 写命中时，只修改 Cache 的内容，不立即写入主存，只有当此块被替换出时才写回主存。
• 优点是减少访存次数，但存在隐患；每个 Cache 行必须增设一个标志位（脏位），用于反映该块是否被修改过。

2、写不命中

2.1、写分配法（write-allocate）

• 加载主存中块到 Cache 中，然后更新这个块，缺点就是每次不命中都要从主存中读取一块。

2.2、非写分配法（not-write-allocate）

• 只写入主存，不进行调块。
• 全写法通常与非写分配法配合，写分配法和写回法配合。
• 现代计算机通常设立多级 Cache，3 级缓存比较多。在多级缓存中，离处理器越远速度越慢，容量越大，按离处理器远近依次命名 L1Cache、L2Cache……，指令 Cache 和数据 Cache 分离一般在 L1 级，此时采用写分配法和写回法配合。
• 以两级 Cache 为例：
  
• L1Cache 对 L2Cache 采用全写法，L2Cache 对主存使用写回法，相比一级 Cache 系统，这种结构可以避免因为频繁写造成的写缓冲饱和和溢出。

上一篇