第五章 存储系统
5.1 存储系统的层次结构
5.1.1 存储系统的层次结构
人们对计算机系统结构指标的要求：容量大、速度快、价格低
三个要求相互矛盾：
速度越快，每位价格就越高；
容量越大，每位价格就越低；
容量越大，速度越慢。
追求“容量大，价格低”需要采用大容量存储技术；
追求高性能访存速度需要采用价格昂贵的快速存储器；
程序访问的局部性原理：
对于绝大多数程序，它们所访问的指令和数据在地址上不是均匀分布的，而是相对簇聚的。
程序访问的局部性包含两个方面:
时间局部性：程序马上将要用到的信息很可能就是现在正在使用的信息。（如循环逻辑）
空间局部性：程序马上将要用到的信息很可能与现在正在使用的信息在存储空间上是相邻的。（如顺序存放、顺序访问）
解决方法：采用多种存储器技术，构成多级存储层次结构:
整个存储系统要达到的目标：从CPU来看，该存储系统的速度接近于\(M_1\)的，而容量和每位价格都接近于\(M_n\)的。
为了达到这一目标就要做到存储器越靠近CPU，则CPU对它的访问频度越高，而且最好大多数的访问都能在\(M_1\)完成。
5.1.2 存储层次的性能参数
下面仅考虑由\(M_1\)和\(M_2\)构成的两级存储层次：
\(M_1\)的参数：\(S_1\)，\(T_1\)，\(C_1\)
\(M_2\)的参数：\(S_2\)，\(T_2\)，\(C_2\)
1.存储容量\(S\)
一般来说，整个存储系统的容量即是第二级存储器\(M_2\)的容量，即\(S=S_2\)。
2.每位价格\(C\)
\(C= \frac{C_1S_1+C_2S_2}{S_1+S_2}\)
当\(S_1<<S_2\)时，\(C \approx C_2\)
3.命中率\(H\)和不命中率\(F\)
命中率：CPU访问存储系统时，在\(M_1\)中找到所需信息的概率。
\(H=\frac{N_1}{N_1+N_2}\)
\(N_1\) ── 访问\(M_1\)的次数
\(N_2\) ── 访问\(M_2\)的次数
不命中率(失效率) ：\(F＝1－H\)
4.平均访问时间\(T_A\)
分两种情况来考虑CPU的一次访存：
当命中时，访问时间即为\(T_1\)（命中时间）
当不命中时，情况比较复杂。
不命中时的访问时间为：
\(T_1＋T_2＋T_B＝T_1＋T_M\)
\(T_M＝T_2＋T_B\)
不命中开销\(T_M\)：从向\(M_2\)发出访问请求到把整个数据块调入\(M_1\)中所需的时间。
传送一个信息块所需的时间为\(T_B\)。
所以\(T_A＝ HT_1＋(1－H)(T_1＋T_M)\)
\(~~~~~~~~~~~＝ T_1＋(1－H)T_M\)
或 \(T_A ＝ T_1＋FT_M\)
5.1.3 三级存储系统
三级存储系统：
Cache（高速缓冲存储器）
主存储器
磁盘存储器（辅存）
可以看成是由“Cache—主存”层次和“主存—辅存”层次构成的系统。
从主存的角度来看：
“Cache－主存”层次：弥补主存速度的不足
“主存－辅存”层次： 弥补主存容量的不足
5.1.4 存储层次的四个问题
映像规则：当把一个块调入高一层(靠近CPU)存储器时，可以放在哪些位置上?
查找算法：当所要访问的块在高一层存储器中时，如何找到该块?
替换算法：当发生不命中时，应替换哪一块？
写策略：当进行写访问时，应进行哪些操作?
5.2 Cache基本知识
5.2.1 基本结构和原理
Cache是按块进行管理的。
Cache和主存均被分割成大小相同的块。信息以块为单位调入Cache。
主存块地址（块号）用于查找该块在Cache中的位置。
块内位移用于确定所访问的数据在该块中的位置。
5.2.2 映像规则
全相联映像 （fully associative）：主存中的任一块可以被放置到Cache中的任意一个位置。
特点：空间利用率最高，冲突概率最低，实现最复杂。
直接映像（directly associative）：主存中的每一块只能被放置到Cache中唯一的一个位置。
特点：空间利用率最低，冲突概率最高，实现最简单。
组相联映像（set associative）：主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置。
组相联是直接映像和全相联的一种折中。
n 路组相联：每组中有n个块(n＝M/G )。
相联度越高，Cache空间的利用率就越高，块冲突概率就越低，不命中率也就越低。
块冲突：向cache内调入主存块时，对应的位置已被占用。
绝大多数计算机采用直接映像或 n ≤4的组相联
全相联仅适用于小容量Cache
5.2.3 查找算法
目录表的结构
每一个cache块对应有一个目录表项
主存块的块地址的高位部分，称为标识
每个主存块能唯一地由其标识来确定
并行查找的实现方法
相联存储器
单体多字存储器＋比较器
5.2.4 Cache的工作过程
5.2.5 替换算法
主要的替换算法有三种
随机法 优点：实现简单
FIFO先进先出法
LRU最近最少使用法
5.2.6 写策略
两种写策略
写策略是区分不同Cache设计方案的一个重要标志。
1.写直达法（也称为存直达法）：
执行“写”操作时，不仅写入Cache，而且也写入下一级存储器。
2.写回法（也称为拷回法） ：
执行“写”操作时，只写入Cache。仅当Cache中相应的块被替换时，才写回主存。 (设置“修改位”)
两种写策略的比较
写回法的优点：速度快，提高主存写效率，所使用的存储器带宽较低。
写直达法的优点：易于实现，一致性好。
采用写直达法时，若在进行“写”操作的过程中CPU必须等待，直到“写”操作结束，则称CPU写停顿。
减少写停顿的一种常用的优化技术：采用写缓冲器
“写”不命中时两种策略
按写分配(写时取)：
先把所写单元所在的块调入Cache，再行写入。
不按写分配(绕写法)：
写不命中时，直接写入下一级存储器而不调块。
5.2.7 Cache的性能分析
1.不命中率
优点：评价方便
缺点：
与硬件速度无关
容易产生一些误导
2.平均访存时间(更好，但仍是间接评价)
平均访存时间 ＝ 命中时间＋不命中率×不命中开销
3.程序执行时间 （最直接的评价）
CPU时间＝（CPU执行周期数+存储器停顿周期数）× 时钟周期时间
假设：所有的访存停顿都是由Cache不命中引起的
其中：
存储器停顿时钟周期数＝“读”的次数×读不命中率×读不命中开销＋“写”的次数×写不命中率×写不命中开销
存储器停顿时钟周期数＝访存次数×不命中率×不命中开销
5.2.8 改进Cache的性能
可以从三个方面改进Cache的性能：
1.降低不命中率
2.减少不命中开销
3.减少Cache命中时间
下面介绍17种Cache优化技术
8种用于降低不命中率 \(~~~~~\) 5.3节
5种用于减少不命中开销 \(~~\) 5.4节
4种用于减少命中时间 $~~~~~~$5.5节
5.3 降低Cache不命中率
5.3.1 三种类型的不命中
三种类型的不命中:
强制性不命中(冷启动不命中，首次访问不命中）
当第一次访问一个块时，该块不在Cache中，需从下一级存储器中调入Cache，这就是强制性不命中。
容量不命中：
如果程序执行时所需的块不能全部调入Cache中，则当某些块被替换后，若又重新被访问，就会发生不命中。这种不命中称为容量不命中。
冲突不命中(碰撞不命中，干扰不命中):
在组相联或直接映像Cache中，若太多的块映像到同一组(块)中，则会出现该组中某个块被别的块替换(即使别的组或块有空闲位置)，然后又被重新访问的情况。这就是发生了冲突不命中。
5.3.2 增加Cache块大小----最简单
5.3.3 增加Cache的容量----最直接
5.3.4 提高相联度
2:1 Cache经验规则： 容量为N的直接映像Cache的不命中率和容量为N/2的两路组相联Cache的不命中率差不多相同。
5.3.5 伪相联 Cache (列相联 Cache )
基本思想及工作原理
在逻辑上把Cache的空间上下平分为两个区。对于任何一次访问，伪相联Cache先按直接映像Cache的方式去处理。若命中，则其访问过程与直接映像Cache的情况一样。（快）
若不命中，则再到另一区相应的位置去查找。若找到，则发生了伪命中，否则就只好访问下一级存储器。（慢）
伪相联Cache的优点：
命中时间小
不命中率低
缺点：多种命中时间，增加流水线设计复杂度，常被用在离CPU较远的Cache中。
5.3.6 硬件预取
5.3.7 编译器控制的预取
在编译时加入预取指令，在数据被用到之前发出预取请求。
编译器控制预取的目的：使执行指令和读取数据能重叠执行。
按照预取数据所放的位置，可把预取分为两种类型：
寄存器预取：把数据取到寄存器中。
Cache预取：只将数据取到Cache中。
按照预取的处理方式不同，可把预取分为：
故障性预取：在预取时，若出现虚地址故障或违反保护权限，就会发生异常。
非故障性预取：在遇到这种情况时则不会发生异常，因为这时它会放弃预取，转变为空操作。
5.3.8 编译器优化
基本思想：通过对软件进行优化来降低不命中率。（特色：无需对硬件做任何改动）
编译优化技术包括：
数组合并
循环融合
内外循环交换
分块
5.3.9 “牺牲” Cache
基本思想
在Cache和它下一级存储器的数据通路之间设置一个全相联的小Cache，称为“牺牲”Cache。
作用
对于减小冲突不命中很有效，特别是对于小容量的直接映像数据Cache，作用尤其明显。
减少不命中率方法中伪相联、预取技术、牺牲cache同时也会减少不命中开销。