学习计时：共8小时
读书：3小时
代码：1小时
作业：2小时
博客：2小时
第六章 存储器层次结构
简单的计算机系统模型：CPC执行指令
存储器系统为CPU存放指令和数据
存储器系统是一个具有不同容量、成本和访问时间的存储设备的层次结构
高速缓存存储器存储在相对慢速的主储存器中的缓存区域
局部性：具有良好局部性，一次又一次访问相同的数据项集合
6.1 存储技术
6.1.1 随机访问存储器
分为静态和动态
- 静态RAM
SRAM将每个位存储在一个双稳态的存储器单元里。
它可以无限期地保持在两个不同的电压配置或状态之一
亚稳态
- 动态RAM
DRAM将每个位存储为对一个电容的充电。
每个单元由一个电容和一个访问晶体管组成
只要有供电，SRAM就会保持不变。DRAM需要刷新
- 传统的DRAM
分为d个超单元，每个超单元由w个DRAM单元组成，一个d*w单元共存储dw位信息
超单元被组织成r行c列的长方形阵列，rc=d
每个超单元有形如（i，j）的地址，i表示行，j表示列
每个DRAM芯片被连接到某个称为存储控制器的电路
- 存储器模块
DRAM芯片包装在存储器模块中，插在主板的扩展槽上
常见：双列直插存储器模块，单列直插存储器模块
通过将多个存储器模块连接到存储控制器，能够聚合主存
- 增强的DRAM
快页模式DRAM（FPM DRAM）
扩展数据输出DRAM（EDO DRAM）
同步DRAM（SDRAM）
双倍数据速率同步DRAM（DDR DRAM）
Rambus DRAM（RDRAM）
视频RAM（VRAM）
- 非易失性存储器
DRAM和SRAM断电后会丢失信息，是易失的，非易失性存储器断电后依然保存着信息
ROM：只读存储器
PROM（可编程ROM）：只能被编程一次
可擦写可编程ROM（EPROM）：能够被擦除和重编程的次数的数量级可达1000次
闪存：基于闪存的磁盘驱动器——固态硬盘
存储在ROM中的程序通常称为固件。
- 访问主存
数据流通过总线传播
总线事务：读事务：从主存传送数据到CPU 写事务：从CPU传送数据到主存
总线是一组并行的导线，能携带地址、数据和控制信号
系统总线：连接CPU和I/O桥
存储器总线：连接I/O桥和主存
读事务和写事务都有三个基本步骤
6.1.2 磁盘存储
磁盘是保存大量数据的存储设备
- 磁盘构造
由盘片构成，每个盘片有两个表面，表面覆盖着磁性记录材料
盘片中央有一个可以旋转的主轴，使盘片以固定的旋转速率旋转，通常5400~15000转每分钟
每个表面都由一个称为磁道的同心圆组成，每个磁道被划分为一组扇区，每个扇区包括相等数量的数据位，扇区之间由一些间隙分隔开
整个装置通常称为磁盘驱动器
- 磁盘容量
一个磁盘可以记录的最大位数称为它的最大容量
记录密度：磁盘一英寸的段中可以放入的位数
磁道密度：从盘片中心出发半径上一英寸的段内可以有的磁道数
面密度：记录密度和磁道密度的乘积
磁盘容量=字节数/扇区*平均扇区数/磁道*磁道数/表面*表面数/盘片*盘片数/磁盘
- 磁盘操作
磁盘用读/写头来读写存储在磁性表面的位，而读写头连接到一个传动臂的一端。
寻道：通过沿着半径轴前后移动这个传动臂，驱动器可以将读/写头定位在盘面上的任何磁道上
对扇区的访问时间三部分：
寻道时间：移动传动臂所需的时间称为寻道时间
旋转时间：Tmax=1/RPM*60secs/1min，平均旋转时间是它的一半
传送时间：一个扇区的传送时间依赖于旋转速度和每条磁道的扇区数目
- 逻辑磁盘块
逻辑盘控制器：维护着逻辑块号和实际磁盘扇区之间的映射关系
控制器上的固件执行一个快速表查找，将一个逻辑块号翻译成一个（盘面，磁道，扇区）三元组，唯一的标识了对应的物理扇区
- 连接到I/O设备
输入/输出（I/O设备），通过I/O总线连接到CPU和主存
I/O总线比系统总线和存储器慢，但可以容纳种类繁多的第三方I/O设备
通用串行总线控制器：连接到USB总线的设备的中转机构
图形卡（适配器）：包含硬件和软件逻辑，代表CPU在显示器上画像素
主机总线适配器：将一个或多个磁盘连接到I/O总线，使用主机总线接口定义的通信协议
- 访问磁盘
CPU使用一种称为储存器映射I/O的技术来向I/O设备发出命令
地址空间中有一块地址是为与I/O设备通信保留的
每个这样的地址称为I/O端口
CPU通过执行三个存储指令，发起磁盘读
第一条指令：发送一个命令字，告诉磁盘发起一个读，同时还发送了其他的参数
第二条指令：指明应该读得逻辑块号
第三条指令：指明应该存储磁盘扇区内容的主存地址
- 商用磁盘的剖析
第一列给出区号，区0在最外面，区14在最里面
第二列给出该区每条磁道中包含的扇区数
第三列显示分配给区的柱面数量
第四列给出了分配给每个区的逻辑块总数
靠外面的区比靠里面的区有更多的扇区
每个区有比逻辑块更多的扇区，备用扇区形成了一个备用柱面池
6.1.3 固态硬盘
固态硬盘（SSD）是一种基于闪存的存储技术
一个SSD包由一个或多个闪存芯片和删除翻译层组成
比起旋转磁盘，SSD有很多优点：
由半导体存储器构成，没有移动部件，因而随机访问时间比旋转磁盘要快，能耗更低，也更结实
缺点：容易磨损，贵
6.1.4 存储技术趋势
不同的存储技术有不同的价格和性能折中
不同存储技术的价格和性能属性以截然不同的速率变化着
DRAM和磁盘的性能滞后于CPU的性能
6.2 局部性
局部性原理：倾向于引用邻近于其他最近引用过的数据项的数据项
两种形式：时间局部性，空间局部性
一般而言，有良好局部性的程序比局部性差的程序运行得更快
6.2.1 对程序数据引用的局部性
顺序访问一个向量每个元素的函数，具有步长为1的引用模式。
在一个连续向量，每隔k个元素进行访问，就被称为步长为k的引用模式
随着步长的增加，空间局部性下降
双重嵌套循环按照行优先顺序读数组的元素
6.2.2 取指令的局部性
代码区别于程序数据的一个重要属性是在运行时它是不能被修改的
6.2.3 局部性小结
重复引用同一个变量的程序有良好的时间局部性
对于具有步长为k的引用模式的程序，步长越小，空间局部性越好。具有步长为1的引用模式的程序有很好的空间局部性。在存储器中以大步长跳来跳去的程序空间局部性会很差
对于取指令来说，循环有好的时间和空间局部性。循环体越小，循环迭代次数越多，局部性越好
6.3 存储器层次结构
存储技术：不同存储技术的访问时间差异很大。速度较快的技术每字节的成本要比速度较慢的技术高，而且容量较小。CPU和主存之间的速度差距在增大
计算机软件：一个编写良好的程序倾向于展示出良好的局部性
存储器层次结构见p405图6-23
6.3.1 存储器层次结构中的缓存
高速缓存是一个小而快速的存储设备，使用高速缓存的过程称为缓存
中心思想：对于每个k，位于k层的更快更小的存储设备作为位于k+1层的更大更慢的存储设备的缓存
块：连续的数据对象片
数据总是以块大小为传送单元在第k层和第k+1层之间来回拷贝
- 缓存命中
当程序需要第k+1层的某个数据对象d时，它首先在当前存储在第k层的一个块中查找d，而d刚好在k层
- 缓存不命中
第k层没有缓存数据对象d
如果缓存不命中，第k层的缓存从第k+1层缓存中取出包含d的那个块，如果第k层的缓存已经满了的话，可能会覆盖现存的一个块，这个过程称为替换或驱逐，被驱逐的块称为牺牲块，决定该替换哪个块是由缓存的替换策略来控制的
- 缓存不命中的种类
一个空的缓存有时称为冷缓存，此类不命中称为强制性不命中或冷不命中
冲突不命中：数据对象映射到同一个缓存块
容量不命中：工作集大小超过缓存大小
- 缓存管理
将缓存划分成块，在不同的层之间传送块，判定是命中还是不命中，并处理它们
管理缓存可以是硬件、软件，或两者结合
6.3.2 存储器层次结构概念小结
利用时间局部性：同一数据对象可能会被多次使用。一个数据对象在第一次不命中时被拷贝到缓存中，期望后面对该目标有一系列的访问命中
利用空间局部性：块通常包括多个数据对象。由于空间局部性，期望后面对该块中其他对象的访问能够补偿不命中后拷贝该块的花费
6.4 高速缓存存储器
早期计算机系统的存储器层次结构只有三层：CPU寄存器，DRAM主存储器，磁盘存储
由于CPU和主存之间逐渐增大的差距，在寄存器文件和主存间插入了SRAM高速缓存存储器
6.4.1 通用的高速缓存存储器结构
存储器地址m位，S=2的s次方个高速缓存组，每个组包含E个高速缓存行，每个行由B=2的b次方字节的数据块组成
一个有效位指明这个行是否包含有意义的信息，还有t=m-（b+s）个标记位
描述：元组（S,E,B,m）
高速缓存的大小C指的是所以块的大小的和，C=S*E*B
详见p410图6-28
6.4.2 直接映射高速缓存
每个组只有一行（E=1）的高速缓存称为直接映射高速缓存
高速缓存确定一个请求是否命中，然后抽取出被请求的字的过程，分为三步：1）组选择 2）行匹配 3）字抽取
- 直接映射高速缓存中的组选择
高速缓存从w的地址中间抽取出s个组索引位
- 直接映射高速缓存中的行匹配
确定是否有字w的一个拷贝存储在组i包含的一个高速缓存行中
- 直接映射高速缓存中的字选择
确定所需要的字在块中从哪里开始
- 直接映射高速缓存中不命中时的行替换
如果缓存不命中，那么它需要从存储器层次结构中的下一层取出被请求的块
- 综合：运行中的直接映射高速缓存
标记位和索引位连起来唯一的标识了存储器中的每个块
多个块映射到同一个高速缓存组（即它们有相同的组索引）
映射到同一个高速缓存组的块由标记位唯一的标识
- 直接映射高速缓存中的冲突不命中
抖动：高速缓存反复地加载和驱逐相同的高速缓存块的组
修正抖动的方法：在每个数组的结尾放B字节的填充
6.4.3 组相联高速缓存
每个组都保存有多于一个的高速缓存行
- 组相联高速缓存的组选择
与直接映射高速缓存的组选择一样。
- 组相联高速缓存中的行匹配和字选择
一个相联的存储器是一个（key，value）对的数组，以key为输入，返回value值，key是标记和有效位，value就是块的内容
- 组相联高速缓存中不命中时的行替换
如果有空行则替换空行
最简单的替换策略是随机选择要替换的行
6.4.4 全相联高速缓存
一个全相联高速缓存由一个包含所有高速缓存行的组（E=C/B）组成
- 全相联高速缓存中的组选择
只有一个组
- 全相联高速缓存中的行匹配和字选择
与组相联高速缓存中的是一样的
6.4.5 有关写的问题
直写：立即将w的高速缓存块写回到紧接着的低一层中
缺点：每次写都会引起总线流量
写回：尽可能推迟存储器更新，只有当替换算法要驱逐更新过的块时，才把它写到紧接着的低一层中
缺点：增加了复杂性，必须为每个高速缓存行维护一个额外的修改位
处理写不命中：
写分配：加载相应的低一层中的块到高速缓存中，然后更新这个高速缓存块
非写分配：避开高速缓存，直接把这个字写到低一层中
6.4.6 一个真实的高速缓存层次结构的解剖
高速缓存既保存数据，也保存指令
只保存指令的高速缓存称为i-cache，只保存程序数据的高速缓存称为d-cache
既保存指令又保存数据的高速缓存称为统一的高速缓存
6.4.7 高速缓存参数的性能影响
不命中率：存储器引用不命中的比率：不命中数量/引用数量
命中率：命中的存储器引用比率，它等于1-不命中率
命中时间：从高速缓存传送一个字到CPU所需的时间，包括组 选择、行确认和字选择的时间
不命中处罚：由于不命中所需要的额外的时间
- 高速缓存大小的影响
较大的高速缓存可能会提高命中率，使大存储器运行得更快较难
较大的高速缓存可能会增加命中时间
但芯片上的L1高速缓存命中时间必须短
- 块大小的影响
块越大就意味着高速缓存行数越少
对命中率和不命中处罚有负面影响
- 相联度的影响
较高的相联度优点是降低了高速缓存由于冲突不命中出现抖动的可能性
但会造成较高的成本
- 写策略的影响
直写高速缓存比较容易实现
能使用独立于高速缓存的写缓存区，用来更新存储器
6.5 编写高速缓存友好的代码
1） 让最常见的情况运行得快
2） 在每个循环内部缓存不命中数量最小
重要问题：
对局部变量的反复引用是好的，因为编译器能够将它们缓存在寄存器文件中（时间局部性）
步长为1的引用模式是好的，因为存储器层次结构中所以层次上的缓存都是将数据存储为连续的块（空间局部性）
6.6 综合：高速缓存对程序性能的影响
6.6.1 存储器山
一个程序从存储系统中读数据的速率称为读吞吐量，有时称为读带宽
读带宽的时间和空间局部性的二维函数，称为存储器山
垂直于size轴的是四条山脊，分别对应L1高速缓存，L2高速缓存，L3高速缓存和主存内的时间局部性区域
6.6.2 重新排列循环以提高空间局部性
6.6.3 在程序中利用局部性
有良好局部性的程序从快速的高速缓存存储器中访问它的大部分数据
局部性差的程序从相对慢速的DRAM主存中访问它的大部分数据
参考资料：《深入理解计算机系统》
问题：1.重新排列循环以提高空间局部性这一段没太看懂
2.综合：运行中的直接映射高速缓存中读地址的地方有点不懂
心得：这一章的内容看起来比较容易理解，但还是会有些不懂的地方，而且习题也不算简单，不过已经渐渐感觉看书没有以前那么辛苦了。