课程主页：http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/schedule.html

课程资料：https://github.com/EugeneLiu/translationCSAPP

课程视频：https://www.bilibili.com/video/av31289365/

这一讲介绍了存储器层次结构。

存储技术和趋势

RAM(随机访问存储器)

  • 主要特点
    • 传统上将RAM封装为芯片。
    • 基本存储单元通常是一个cell（每个cell一比特）。
    • 多个RAM芯片形成一个存储器。
  • RAM有两种：
    • SRAM（静态RAM）
    • DRAM（动态RAM）

两者的性能对比如下：

非易失性存储器
  • DRAM和SRAM是易失性存储器
    • 如果关闭电源，则会丢失信息。
  • 非易失性存储器即使断电也能保存存储的值
    • 只读存储器（ROM）：在生产期间进行编程
    • 可编程ROM（PROM）：可以编程一次
    • 可擦除的PROM（EPROM）：可以批量擦除（UV，X射线）
    • 电可擦除PROM（EEPROM）：具有电子可擦除功能
    • 闪存：EEPROM。 具有部分（块级）擦除功能
      • 擦除约100,000次后会磨损
  • 非易失性存储器的用途
    • 存储在ROM中的固件程序（BIOS，磁盘控制器，网卡，图形加速器，安全子系统等）
    • 固态硬盘（替换拇指驱动器，智能电话，mp3播放器，平板电脑，笔记本电脑等中的旋转磁盘）
    • 磁盘缓存

传统的总线结构连接，CPU和内存

  • 总线是承载地址，数据和控制信号的并行导线的集合。
  • 总线通常由多个设备共享。

旋转磁盘

旋转磁盘即普通磁盘，这样描述是为了和固态硬盘加以区别。

磁盘构造

  • 磁盘由盘片组成，每个盘片都有两个表面。
  • 每个表面由称为磁道的同心环组成。
  • 每条磁道都由被间隙隔开的扇区组成。
磁盘容量
磁盘访问时间

磁盘访问过程如下：

访问时间如下：

  • 访问某些目标扇区的平均时间，近似为：
    • $\text{Taccess = Tavg seek + Tavg rotation + Tavg transfer }$
  • 寻道时间（$\text{Tavg seek}$）
    • 将磁头定位在包含目标扇区的圆柱体上的时间。
    • 典型的$\text{Tavg seek}$为3-9毫秒
  • 旋转等待时间（$\text{Tavg rotation}$）
    • 等待目标扇区的第一位通过读/写头的时间。
    • $\text{Tavg rotation = 1/2 x 1/RPMs x 60 sec/1 min}$
    • $\text{Typical Tavg rotation = 7200 RPMs}$
  • 转移时间（$\text{ Tavg transfer}$）
    • 读取目标扇区中比特的视角。
    • $\text{Tavg transfer = 1/RPM x 1/(avg # sectors/track) x 60 secs/1 min}$
逻辑磁盘块
  • 现代磁盘为复杂的扇区几何提供了一个更简单的抽象视图：
    • 可用扇区集被建模为一系列b大小的逻辑块(0, 1, 2, …)
  • 逻辑块与实际（物理）扇区之间的映射
    • 由称为磁盘控制器的硬件/固件设备维护。
    • 将对逻辑块的请求转换为（表面，轨道，扇区）三元组。
  • 允许控制器为每个区域预留备用柱面。
    • 解决“格式化容量”和“最大容量”中的差异。

SSD(固态硬盘)

  • 页数：512KB至4KB，块数：32至128页
  • 以页为单位读取/写入的数据。
  • 页只能在其块被擦除后才能写入
  • 重复写入约100,000次后，块耗尽。
性能

SSD vs 旋转磁盘
  • 优点
    • 无移动部分，所以更快，功率更少，更坚固
  • 缺点
    • 有可能磨损
    • 在2015年，每字节价格大约贵30倍
  • 应用
    • MP3播放器，智能手机，笔记本电脑
    • 开始出现在台式机和服务器中

对比

局部引用

局部性

  • 局部性原则：程序倾向于引用邻近于其他最近引用过的数据项和指令。
  • 时间局部性：
    • 最近引用的项可能会在不久的将来再次引用
  • 空间局部性：
    • 地址接近的项往往会在比较接近的时间内被引用

局部性例子

sum = 0;
for (i = 0; i < n; i++)
	sum += a[i];
return sum;
  • 数组$a$有很好的空间局部性，$\text{sum}$有很好的时间局部性

存储器层次结构中的缓存

存储器结构

  • 硬件和软件的一些基本和持久属性：
    • 快速存储技术每字节成本更高，容量更小且需要更多功率（热量！）。
    • CPU和主内存速度之间的差距越来越大。
    • 编写良好的程序倾向于展现良好的局部性。
  • 这些基本特性彼此完美地互补。
  • 他们提出了一种组织内存和存储系统的方法，称为内存层次结构。

缓存

  • 缓存：较小，速度较快的存储设备，可充当较大，较慢的设备中数据子集的暂存区。
  • 存储层次结构的基本思想：
    • 对于每个$k$，级别$k$处更快，更小的设备充当级别$k + 1$处较大，更慢的设备的缓存。
  • 为什么内存层次结构有效？
    • 由于局部性原因，程序倾向于访问级别$k$的数据比访问级别$k + 1$的数据更多。
    • 因此，级别$k + 1$处的存储可能更慢，所以每比特更便宜。
  • 重要构想：内存层次结构创建了一个大型存储池，其成本与底部附近的廉价存储相同，但以顶部附近的快速存储的速率向程序提供数据。

例子

Hit

请求的数据在缓存中：

Miss

请求的数据不在缓存中，所以要将内存中的数据替换缓存中的数据：

常规缓存概念：缓存未命中的类型

  • 冷未命中
    • 由于缓存为空而发生。
  • 冲突未命中
    • 大多数高速缓存将级别$k + 1$的块限制为级别$k$的块位置的一小部分子集。
      • 例如。 第$k + 1$级的块$i$必须放置在第$k$级的块（$i \mod 4$）中。
    • 当级别$k$高速缓存足够大，但是多个数据对象都映射到同一级别$k$块时，就会发生冲突未命中。
      • 例如。 每次引用块0、8、0、8、0、8，…都会未命中。
  • 容量未命中
    • 当活动高速缓存块的集合（工作集）大于高速缓存时发生。

总结

  • CPU，内存和大容量存储之间的速度差距继续扩大。
  • 编写精良的程序具有一种称为局部性的特性。
  • 基于缓存的存储器层次结构通过利用局部性来缩小差距。