Chapter 6. The Memory Hierarchy¶

Random Access Memory¶

随机访问存储器 (RAM) 分为两类：

• Static RAM (静态RAM，SRAM)
• Dynamic RAM (动态RAM，DRAM)

其中 SRAM 将每个 bit 位的信息存储在一个双稳态的存储器单元内，每个存储单元需要六个晶体管来实现。正是由于 SRAM 双稳态的特性，只要有电，就能够一直保持存储的数据。

与 SRAM 相比，DRAM 采取电容充电方式存储信息。DRAM 的存储单元对干扰十分敏感，当电容的电压被扰乱之后，就再也无法恢复到干扰之前。

虽然 SRAM 的速度要比 DRAM 更快，但是价格更贵。综合以上考虑，处理器芯片内的高速缓存 (cache) 采用 SRAM ，而内存采用 DRAM

细节请参考 CH 7. Memory Basics - Nimisora's Notes ，我不再重复搬运了

机械磁盘¶

机械磁盘，也称旋转磁盘。它主要依靠盘片来存储数据，盘片表面涂有磁性的记录材料，盘片正反两面都可以用来存储数据。通常情况下，磁盘由一个或多个盘片组成，这些盘片被固定在一个可以旋转的主轴上，主轴带动盘片以固定速率进行高速旋转。

其中盘片表面被划分为一圈一圈的磁道（tracks），每个磁道又被划分为多个扇区（sectors），通常情况下每个扇区可以存储 512 字节的数据。扇区与扇区之间又存在间隙 （gaps），用来存放扇区的标识信息

磁盘通过读写头来读写磁盘数据，盘片的每个表面都对应着一个独立的读写头，所有的读写头都连接到一个传动臂上，通过传动臂在 半径方向 上的移动，读写任意磁道上的数据，这种机械运动也被称为寻道。读写头固定为一个磁道后，通过配合盘片旋转完成对目标扇区的读写操作

除了容量之外，磁盘的读写速度也是一个非常重要的指标，对扇区的访问时间主要分为三部分，分别是寻道时间、旋转时间以及传送时间

• Seek time 寻道时间
  • 当目标扇区所处磁道与当前读写头所处磁道不同时，传动臂需要将读写头移动到目标扇区所在磁道，传动臂移动所需时间即寻道时间
  • 寻道时间取决于读写头当前所在位置与目标位置的距离
  • 通过对随机扇区的访问测试，通常平均寻道时间为 3~9ms 左右
• Rotation latency 旋转时间
  • 目标扇区的第一个数据位旋转到读写头下所需的时间
  • 这个过程由当前读写头所在扇区位置跟目标扇区的位置以及盘片旋转速度来决定
• Transfer time 传送时间
  • 一个扇区的传送时间依赖于旋转速度以及每条磁道的扇区数目，即读写头经过该扇区所需要的时间

固态硬盘¶

相比机械硬盘使用传动臂加盘片这种机械式的工作方式，固态硬盘由一个或多个闪存芯片构成。除此之外，固态硬盘还包括一个闪存转换层（flash translation layer,FTL），它的功能和磁盘控制器类似，都是将操作系统对逻辑块的请求翻译成对底层物理设备的访问，不同的是闪存芯片是基于 Nand Flash 实现的

闪存芯片的内部结构组成：

• 每个闪存芯片是由一个或多个 Die 组成，每个 Die 可以分为多个 plane，每个 plane 包含多个 block，block 内部被分为了多个 page
• 对于固态硬盘，数据都是以 page 为单位进行读写的
• 与机械磁盘每个扇区都为 512 字节相比，对于不同规格的闪存芯片，其中的 page 大小可能不尽相同
• 固态硬盘除了读、写两个基本操作外，还多了一个 擦除 操作
  • 由于技术限制，写入操作 只能将 1 改成 0
  • 所以一个 page 在写入数据前，所有的存储位都为 1
  • 在写入 page 之前，需要先擦除整个 block ，不能直接覆盖
    • 换句话说，写入操作以 page 为单位；擦除操作以 block 为单位

比起机械硬盘，固态硬盘有很多优点。由于它是由半导体构成的，没有移动的机械部件，因此随机访问时间比机械磁盘要快，功耗也更低，同时也更抗摔。缺点就是固态硬盘的价格较贵。

程序的局部性¶

对于现代存储科技，DRAM 和磁盘的性能滞后于 CPU 性能，如果考虑多核技术，CPU 与存储设备的性能差距会进一步增大。为了弥补处理器与内存的差距，处理器芯片中使用了大量基于 SRAM 的高速缓存 cache，其降低 CPU 的访存延迟的原因之一为应用程序具有局部性的特点

局部性通常有两种不同表现形式，分别是时间局部性和空间局部性。

如果被引用过的数据在将来一段时间还会被多次引用，可以说程序具有良好的时间局部性；

如果一个内存位置被引用了一次，那么程序很可能在将来一段时间引用来自附件的一个内存位置，可以说程序具有良好的空间局部性。

有一对向量元素求和的函数 sumvec :

1
2
3
4
5
6

int sumvec(int v[N]){
    int i, sum = 0;
    for(i = 0; i < N;i++)
        sum += v[i];
    return sum;
}

其中变量 sum 在每次循环中都被引用一次，因此对于 sum 来说有好的时间局部性；

另一方面，由于 sum 是个标量，不存在空间局部性的特点，但是对于向量 v ，读取顺序与存储在内存的顺序是一致的，函数有良好的空间局部性。

缓存¶

• Cache Hit 缓存命中
  • 当程序需要第 k+1 层的数据 d 时，它首先从第 k 层的数据块中检索是否包含目标数据 d 的副本。
  • 如果目标数据 d 刚好缓存在第 k 层，这种情况即称为缓存命中
  • 另一方面，如果第 k 层没有缓存数据 d ，这种情况称为缓存不命中 (Cache Miss)
    • 发生缓存不命中的时候，且如果第 k 层缓存已满，其中一个数据块会被替换为带有数据 d 的块，被替换的块也被称为牺牲块

基于 SRAM 的cache 的内部结构：

• 整个 cache 被划分成一个或多个 set，每个 set 包含一个或多个 cache line (高速缓存行) ，每个 cache line 由有效位 (valid) 、标记 (tag) 以及数据块 (cache block) 三部分组成
  • 其中有效位长度为 1 bit，它表示当前 cache line 存储信息是否有效
  • 标记用来确定目标数据是否存在于当前 cache line 中
• 通常，cache 的结构可以用元组 (S,E,B,m) 来描述，其中 S 指 set 的个数，E 指 cache line 的行数，B 指 cache bliock 的位数，m 指 valid,tag,cache block 位数和
• cache 的大小指所有数据块的和，其中不包括有效位和标记位，即 S*E*B

目标数据的地址划分如下：

1
2
3

+---+---------+------------+
|Tag|Set index|Block Offset| Address
+---+---------+------------+

CPU 从缓存中请求目标数据，Cache 根据 Set index 选择对应的 set ，对 Tag 进行匹配找到对应的 cache line ，最后再根据 Block Offset 取出目标数据

根据每个 set 所包含 cache line 的行数不同，cache 被分为不同的类：

• 当每个 set 只有一个 cache line ，这种结构的 cache 被称为直接映射 cache
• 与直接映射不同，组相连 cache 的每个 set 允许包含多个 cache line
• 整个 cache 只有一个 set 的缓存称为全相连 cache，具体行数 E = C/B
  • 由于全相连 cache 只有一个 set ，其不再需要组索引位进行选择
  • 全相连 cache 只适合做容量较小的高速缓存

事实上，在直接映射 cache 中经常发生一种名叫 冲突不命中 的现象，即通过交替引用反复更新某一 cache line ，导致性能奇妙地下降

接下来，举一个有着良好的局部性，当时会发生冲突不命中的代码例子：

1
2
3
4
5
6
7

float dotprod(float x[8], float y[8]){
    float sum = 0.0;
    int i = 0;
    for(i=0;i<8;i++)
        sum += x[i]*y[i];
    return sum;
}

假设数组 x 的第一个元素位于地址 0 处，且 y 数组在地址上紧接 x 数组的最后一个元素后面，那么该程序地址分配如下：

取极端例子，选择一个只有两个 set 的 直接映射 cache，其结构如下：

1
2
3

+---------+---------+------------+
|1 bit Tag|1 bit Set|4 bit Offset| Address
+---------+---------+------------+

由于 32 = 10 0000 ，y[0] 开始的数据的 Set index 为 0 ，和 x[0] 相同

那么每次循环，都会先调用 x[i] ，再调用 y[i] ，且二者调用同一个 cache line，导致每次读取数据都有缓存不命中 (Cache Miss) ，这种现象也被称为 抖动 ，这种抖动的出现可能会导致运行速度下降2到3倍

不过，如果程序云意识到这种抖动的存在，可以通过修改内存分配情况来解决这个问题。例如此题，可以把数组 x 的长度由 8 变成 12，使得数组 y 的 Set index 与 x 完全错开：