计算机组成原理之高速缓冲存储器（Cache）
概述
问题的提出
由上一篇计算机组成原理之主存储器中的存储器分层结构图可知，CPU（寄存器）和主存（DRAM）之间存在速度的差异，由于主存的速度很慢，在CPU访存时，就会出现CPU的“空等”现象，造成CPU资源的极大浪费。
为了解决这个问题，我们在CPU和主存之间加入了一级高速缓冲存储器Cache（SRAM），称为缓存。Cache的速度要高于主存，但容量比较小（价位比较高的原因）
要避免CPU的“空等”现象，这意味着CPU运行所需要的的大部分数据和指令都要在缓存中取到，不然还要频繁的访问主存，Cache就白加了，但是缓存的容量远小于主存，如何保证CPU使用的数据和指令都在缓存中得到？这就运用了计算机中一个很重要的原理：程序访问的局部性原理。
程序访问的局部性原理：
- 时间上的局部性：当前正在使用的指令和数据，在不久的将来还会被使用到
- 空间上的局部性：当前正在使用一个指令或数据，那么在不久的将来，相邻的指令或数据就会被使用到
根据程序的局部性原理，在缓存中存储的应该是当前使用的指令和数据以及它们相邻的指令和数据。因此缓存和主存之间数据交换的单位就是块，块中存放有当前使用的指令和数据以及相邻的指令和数据，块的大小（即一次性取出多少相邻的指令和数据）可以由实验获得。
Cache的工作原理
主存和缓存的编址
主存和Cache被分为大小一样的块，主存有M块，Cache有C块，M>>C，此时，主存内的地址可被分为两个部分，高位为块号，低位为块内偏移地址，体现了块的大小，如果块内地址有5位，则块的大小为2^5=32个字节；同样，Cache的地址也被分为块号和块内地址两部分。
然而实际上，Cache的地址并没有什么用，原因在于主存块和缓存块大小是一样的，而且在传输中又是以块为整体进行传输的，因此，缓存的块内地址和主存的块内地址是完全相同的，而且缓存中在每个块的开始部位还有标记，这个标记会注明当前的缓存块是来自于主存中的哪个块，并将主存块号存在标记中，当CPU给出一个主存的地址时，首先会在缓存中寻找有没有这个地址所在的主存块，此时就是比较主存块号和缓存中的标记位是否有相同的，如果找到，就直接拿主存地址的块内地址部分去用作缓存的块内地址，进而找到想要的数据，因此，Cache地址没有用武之地。
命中与未命中
- 命中：当CPU要读取主存中的数据或指令时，如果所需要的的数据或指令已经在Cache中，可以直接访问Cache获得想要的数据或指令，这种情况称为缓存命中，主存与缓存建立了对应关系，用标记记录了建立对应关系的主存块号
- 未命中：当CPU要读取主存中的数据或指令时，如果所需要的的数据或指令没有在Cache中，CPU必须访问主存才能获得想要的数据或指令，这种情况称为缓存未命中，主存与缓存没有建立对应关系
命中率
我们希望每次CPU想要的数据或指令都能在Cache中获得，也就是每次都能命中，这样就很大的减少了CPU的"空等"，采用命中率来评价Cache的性能。
命中率：CPU欲访问的信息在Cache中的比率
命中率与Cache的容量与块长有关。容量越大，同时存储的主存块数越多，命中率自然就高；块长如果比较小，CPU没执行几次指令，块中的指令就被用完了，还要去主存中取，没有充分利用程序的局部性原理，块太大的话，块中只有部分数据被CPU用到，浪费了Cache的空间。
块长一般可取4~8个字。实际上块长的取值与一个存取周期可以从主存取出的信息的长度有关（提高访存速度的多体交叉）。
Cache-主存系统的效率
效率e与命中率有关，命中率越高，效率就越高。
Cache的基本结构
Cache由Cache存储体、地址映射变换机构、Cache替换机构几大模块组成。
- Cache存储体：以块为单位与主存交换信息，为了加速Cache与主存之间的调动，主存多采用多体结构，且Cache访存的优先级最高
- 地址映射变换机构：将CPU送来的主存地址转换为Cache地址。前面已经分析过，主存地址和缓存地址的块内地址部分相同，因此，地址变换主要是主存块号与Cache块号间的转换，具体的转换规则与地址映射函数有关。
- Cache替换机构：如果Cache已满，无法接受来自主存块的信息时，就由Cache内的替换机构按照一定的替换算法确定应该从Cache内移除哪个块返回主存，而把新的主存块调入Cache中。
注意：Cache对用户是透明的，用户在编程时用到的是主存地址，用户根本不知道这些主存块是否已经调入Cache，将主存块调入Cache的任务是硬件自动完成的。
Cache的读写操作
读操作：很简单，按照流程来就可以
写操作：要注意主存与Cache的一致性问题，对Cache块内写入的信息，必须与被映象的主存块内的信息完全一致。
- 写直达法：写操作时数据即写入Cache，又写入主存。写操作的时间就是访问主存的时间，Cache块退出时，不需要对主存执行写操作，更新策略容易实现
- 写回法：写操作时只把数据写入Cache而不写入主存，当Cache数据被替换出去时才写回主存。写操作的时间就是访问Cache的时间，速度快，但是在并行计算机中，多个CPU会有多个Cache，会导致同一主存块在多个Cache中不一致的问题
Cache的改进
- 增加Cache的级数，片内缓存为第一级，片外缓存为第二级，现代计算机一般都有三级Cache
- 统一缓存和分离缓存
统一缓存是指指令和数据都存放在同一缓存内的Cache；分离缓存是指指令和数据分别存放在两个缓存中，一个叫指令Cache，一个叫数据Cache
统一缓存还是分离缓存的选用主要考虑一下两个因素：
- 主存结构。如果计算机的主存是统一的（指令、数据存放在同一主存内），相应的Cache就是统一缓存，否则就，Cache就是分离缓存
- 机器对指令执行的控制方式。采用超前控制或者流水线控制方式时，一般都采用分离缓存
超前控制：在当前指令的执行过程尚未结束时，就提前将下一条准备执行的指令取出，即超前取指或叫指令预取。
流水线控制：实质上是多条指令同时执行，又可视为指令流水。
Cache-主存的地址映射
所谓的地址映射就是主存中的任意一块，如果要加载到Cache中，可以放到Cache中的哪些块。根据映射方式的不同，可分为直接映射（固定的映射关系）、全相联映射（灵活性很大的映射关系）和组相联映射（前两种映射的折衷）。
直接映射
主存当中任意一个给定的块只能映射到指定的Cache块当中。
映射关系式i = j mod C,或者i = j mod 2^C，其中i为缓存块号，j为主存块号，C为缓存块数，映射结果表明每个缓存块对应若干个主存块。实际上就是将主存划分为若干个区，每个区的大小与Cache的大小一致，每个区内的主存块与Cache内的块是一一对应的。
这种方式的优点是实现简单，前面我们知道主存地址可以分为块号地址和块内地址，根据直接映射，主存的块号地址又可以被分为两个部分，低位是Cache字块地址，高位是主存的字块标记，被记录在建立了对应关系的缓存块的“标记”位中。当Cache接到CPU送来的主存地址后，只需要根据中间的Cache字块地址找到对应的Cache字块，然后根据“标记”是否与主存地址中的主存字块标记相符来判断缓存是否命中。
直接映射的缺点是不够灵活，每个主存块只能固定的对应某个Cache块，即使Cache中还空着很多位置也不能占用，使缓存的空间得不到充分利用，而且如果程序恰好要重复访问对应同一Cache块的不同主存块，就要不停的进行替换，降低了命中率。
全相联映射
全相联映射允许主存中的每一字块映射到Cache中的任意一块位置上。这种方式可以从已被占满的Cache块中替换出任一旧字块。
全相联方式的优点是灵活，命中率高，缩小了块冲突率。与直接映射相比，每次访问Cache时，要将主存字块标记与所有Cache的“标记”位进行比对，速度比较慢，而且比对的位数由直接映射的t位增加到了t+c位，使得“Cache”的位数增多。
组相联映射
组相联映射是对直接映射和全相联映射的一种折衷。把Cache分为Q组，每组有R块，按公式i = j mod Q将主存映射到一个缓存组中，其中i为缓存的组号，j为主存的块号，即某一湻村块按模Q将其映射到缓存的第i组内。
假设将Cache分为16个组，则主存的第0，16，32，…字块可映射到Cache第0组2个字块中的任一字块，主存的第15，31，47，…字块可映射到Cache第15组2个字块中的任一字块。显然，主存的第j块会映射到Cache的第i组，两者之间一一对应，属于直接映射，另外，主存的第j块可以映射到Cache第i组内的任意一块，又体现了全相联映射i当Cache每组内只有1个字块时，就是直接映射方式，当Cache只有1个组时，就是全相联映射方式。
替换算法
当新的主存块要加载到Cache当中，而Cache的可用空间又被占满时，就需要替换算法。常用的两者算法是：先进先出算法和近期最少使用算法。
- 先进先出（FIFO）算法
FIFO的原则是将最先调入Cache的字块替换出来，不需要计算字块的使用情况，所以容易实现，开销小，但缺点是可能会把经常使用的程序块替换出去 - 近期最少使用（LRU）算法
LRU是将近期最少使用的块替换出来。它需要随时记录Cache中各块的使用情况，以便确定哪个字块时近期最少使用的字块。LRU比较充分的应用了程序的局部性原理，LRU的平均命中率要比FIFO高，尤其是组相联映射时更能提高LRU的命中率。
本片文章就分享到这了，有任何问题可以在下方评论。
更多关于内容可以移步我的博客，热爱生活，分享知识。