存储器层次结构

Posted May 30, 2024

By Yuhang Peng 27 min read

前言

存储，一直是计算机领域的一个核心问题，计算机有着各种各样的存储单元，比如说前面我们介绍的寄存器，内存，还有家喻户晓的磁盘、固态硬盘等等，这些存储单元都有着怎样的性质呢？另外，它们是如何在一起协同工作的呢？这是这篇文章要讨论的重点。

存储技术

随机访问存储器（RAM）

随机访问存储器（Random Access Memory）分成两种，静态的（Static Random Access Memory，SRAM）和动态的（Dynamic Random Access Memory，DRAM）。这两种存储器需要通上电才能工作，并且断电后内部存放的数据会消失。

SRAM

静态随机访问存储器依赖的是纯硬件单元，它不需要刷新电路就能保存它内部的存储数据。SRAM 是利用硬件的单元的二级性来存储数据：

因为硬件材料的性质，加上没有过多的软件依赖，SRAM 的速度非常快，从 SRAM 中存储数据只需要个位数的时钟周期。但是 SRAM 的缺点是造价昂贵，SRAM 常被用作 CPU 的高速缓存，镶嵌在 CPU 的主板上。

DRAM

我们平时所说的内存一般指的就是 DRAM，动态随机访问存储器。DRAM 的大致结构如下图所示：

DRAM 存储单元被设计成一个矩阵的形式，每个位置（supercell）可以存放单个 bit 的数据。你可能会觉得好奇，为什么还要弄出个矩阵这么麻烦，直接一维线性的数组不好吗？其中一个原因就是设计成二维的数组能够降低地址的大小，可以减少一些硬件上面的消耗。

DRAM 的读取方式也比较特殊，它是依照先行再列的读取方式：

如上图所示，内存控制单元现将行号通过硬件接口传给 DRAM 芯片，DRAM 内部将整行的数据拷贝并存放在内部的 buffer 中，紧接着控制单元再传送列号给 DRAM 芯片，DRAM 就将对应的数据返回。这好理解，但是费了这半天的力，才获取单个 bit 的信息，但是我们也知道我们的 64 位的系统，每次寻址都是 64 个 bit，这是如何实现的呢？这其实是从多个 DRAM 单元并行获取得到的：

当然了，我们这里介绍的 DRAM 仅仅是一个最基础的版本。基于这个版本，其实还有很多的优化，演变出了很多不同版本的 DRAM：

Fast page mode DRAM（FPM DRAM）：普通的 DRAM 发送一次行请求（RAS）和一次列请求（CAS）只能获取到单个 bit 的数据，这非常的低效。FPM DRAM 在这一点上进行改进，允许一次行请求和一次列请求后紧跟着三次列请求，这样获取同样的数据所需的请求次数变少，从而增加了效率。
Extended data out DRAM（EDO DRAM）：这个版本的 DRAM 在 FPM DRAM 的基础上进行改良，让列请求的速度更快，缩短两个列请求之间的时间间隙。
Synchronous DRAM (SDRAM)：这个版本的 DRAM 在控制单元上进行优化，让控制逻辑更加的高效。
Double Data-Rate Synchronous DRAM (DDR SDRAM)：这个版本继续优化控制单元，让控制信号基于上下时钟周期变化，而不是单个时钟周期，等于说是把控制单元的速度翻倍

DDR SDRAM 其实就是我们现在主要在用的内存，但是关于 DRAM 这项技术也一直还在优化。

知道了 DRAM 的内部运作机制，还有一个问题是，CPU 是如何与 DRAM 进行合作的呢？答案是通过 总线（Bus）。

对 DRAM 的操作无非两个——读和写。我们先来看看读，因为每个数据都有地址，读取的时候 CPU 会先将地址通过总线发送给 DRAM：

然后 DRAM 将对应的数据读取出来，通过总线发给 CPU：

写也是一样的道理，一开始都是发送地址，但不同的是，发完地址后，CPU 把数据传送给 DRAM：

磁盘

上面我们说完了内存技术，我们接着来看看其他的存储技术。磁盘（Disk）对每个人来说应该都不陌生，我记得我小时候在用磁盘的时候，总是好奇这里面的声音，每次计算机启动，磁盘总是第一个 “发声” 的，听着就好像里面有个风扇在转似的。有时候计算机卡了，磁盘也开始转，而且声音非常的大，我当时总担心是不是磁盘旧了，需要更换了，现在回想起来也是好玩。。。

扯远了，回到正题，磁盘是由一个旋转的主轴（Spindle）和许多盘片（platter）构成，每个盘片有两个面（surface）。每个表面是由一组磁道（track）的同心圆组成的，每个磁道被划分为一组扇区（sector），每个扇区包含相等数量的 bits（通常是 512 字节），扇区和扇区之间有空隙（gap）：

另外，磁盘的盘面是一个同心圆，磁道是围着同心圆的圆环，这就有一个问题，靠近圆心的磁道肯定比远离圆心的磁道要短，短意味着磁道上可存放的扇区要少，但是为了统一，我们需要保证每个磁道上的扇区数量是一样的，如果是这样的话，外围的磁道上的多余空间不就白白浪费了吗？

为了解决这个问题，我们引入了柱面（cylinder）和区域（zone）两个概念。柱面是所有盘面上到圆心的距离相等的磁道的集合，而区域指的是一组连续的柱面。这样，我们只需要保证在一个区域中，磁道上的扇区数量需要一致，而不需要保证整个磁盘上的磁道上的扇区数量一致，大大增加了磁盘的空间利用率。

一个盘面的容量可以由下面的公式计算得出：

\[Capacity = \frac{\# bytes}{sector} \times \frac{average \# sectors}{track} \times \frac{\# track}{surface} \times \frac{\# surface}{platter} \times \frac{\# platter}{disk}\]

比如说，假设一个磁盘有 5 个盘面（platter），每个面上有 20000 个磁道（track），每个磁道上有 300 个扇区（sector），每个扇区上存放着 512 字节的数据，那么这个磁盘的总容量就是 30.72 GB：

\[Capacity = \frac{512 bytes}{sector} \times \frac{300 sectors}{track} \times \frac{20000 track}{surface} \times \frac{2 surface}{platter} \times \frac{5 platter}{disk} = 30,720,000,000 \ bytes = 30.72 \ GB\]

这里说一下存储单位，按照惯例，对于 I/O 设备来说，存储单位通常以十进制为基准，比如 $K = 10^3$, $M = 10^6$, $G = 10^9$, $T = 10^{12}$。但是对于像是前面介绍的 DRAMs 或是 SRAMs，会略有不同，单位以二进制为基准，$K = 2^{10}$, $M = 2^{20}$, $G = 2^{30}$, $T = 2^{40}$。二者虽有差别，但是差别不大。

由此我们可以知道磁盘的最小单位是扇区，每个扇区上存放着一个区块（block）的数据，这个大小在同一个磁盘上是固定的，我们前面也说了通常是 512 字节，从磁盘中获取的最小单位也是 block，也就是说即使你只需要某个 bit 或者某个 byte 的信息，你还是需要将整个 block 从磁盘中读取出来。

那磁盘是如何运作的呢？当主轴转动时，机械手臂（arm）就会在盘片的一个面上移动来读取信息：

这个过程中，机械手臂头会在对应的盘面上移动。并且，同一时间下，所有的机械手臂头会停留在同一个柱面。磁盘的搜索时间可以分成如下三部分：

寻道时间（seek time）：将机械手臂头移到指定的磁道上，这个时间一般是 3 ～ 9 ms
旋转时间（rotational latency）：磁盘转动中，机械手臂头等待着对应的扇区到来
传送时间（transfer time）：将对应的扇区的信息读取出来，或者将数据写入到对应的扇区中

具体的读取和存储时间可以通过磁盘的旋转速度，还有每个磁道上的扇区的数量，计算得出，这里就不细说了。磁盘的时间是毫秒级别的，而前面我们说的 RAM 则是纳秒级别的，可见二者在速度上的差别是非常悬殊的。

磁盘在使用之前都需要格式化，格式化所做的事情就是在每个扇区前面的空隙加入识别信息，也会进行分区，以及相关的备份，比如说一个区域中的柱面坏掉了的话，可以使用备份的柱面。

另外，和之前的内存不同，磁盘被归为 I/O 设备，并且 CPU 不直接对磁盘进行存取操作，以读取某个扇区的数据为例，我们可以大致看看这个过程。首先 CPU 发出读取的请求，附带着还有内存的地址：

磁盘控制单元在收到请求后，将数据读取出来后直接放到了内存的指定地址上，这种绕过 CPU，直接访问内存的方式被称为 direct memory access（DMA）：

当 DMA 完成后，磁盘控制单元通过中断机制告知 CPU：

整个过程到此就结束了，至于说后面发生的事就是我们之前将的 CPU 去到内存中进行读取，为什么这么费劲还有放到内存中呢？这个跟整个的存储器的层次结构有关，我们后面会说，这里就先放一放。

固态硬盘（SSD）

近些年来，固态硬盘（Solid State Disks）成为替代磁盘的选项，其速度比磁盘要快，但是价格要比磁盘贵 30 倍。

固态硬盘的数据也是存放在数据块（block）当中，但是 block 并不是最小单位，block 下的 page 是读取和写入的最小单位，一个 page 能够被写入的前提条件是其所在的 block 被重置，也就是 block 中的所有的 bits 都被设置成 1。

SSD 大致结构如下：

但是固态硬盘有一个潜在的问题就是，它的闪存是有寿命的，也就是并不能无限次数的写，写的次数越多寿命就越少。但是作为一般使用，我们并不需要过于担心这个寿命问题。

层次结构

上面我们列出了不同的存储技术，你会发现，速度越快的存储单元，造价也会更高，因此容量会更少，反过来，容量大的存储单元速度又不尽人意。可以说它们优缺点明显且相互对立，那有没有什么办法可以让它们协同工作呢？答案就是分层管理，如下图所示：

之前在计算机的机器级指令中我们也展示了这张图，但是当时仅仅是为了讲解寄存器。

金字塔顶尖是寄存器，数据的存取基本上在一个时钟周期内就可以完成，但是它只有 KB 级的容量。然后下来是 CPU 内的三级缓存，都是用的 SRAM 技术，数据的存取可以在个位数或几十个时钟周期内完成，容量是 MB 级。再下来就是我们熟悉的内存，数据的读取需要去到上百个时钟周期，容量是 GB 级。内存下面是本地磁盘，数据的存取需要在百万个时钟周期，容量可以到 TB 级，再往后就是网络了，延迟会更大，当然容量也会更多。

这里的核心思想是，每一层的存储单元会作为下一层存储单元的缓存。基于这一点，我们还可以衍生出其他的点：

每层存储单元的数据块（block）大小是固定的，但是不同层大小是不一样的，一般来说，越远离 CPU 的存储单元，因为数据的获取时间较长，数据块的大小就会越大，这样一次可以多获取些数据
因为容量的限制，每一层都会考虑数据的更替，也就是会用下一层获取到的新数据把旧的、不常用的数据覆盖，考虑到这个覆盖机制的实施本身也有时间开销，所以，一般来说，越往上的存储单元，趋向于用越简单的替换机制
编译器管理的是寄存器，这是最高层级的存储单元

上面这张图是整个计算机的存储层次结构，CPU 内部也有层次结构，Intel Core i7 的结构如下图所示：

可以看到的是，一级和二级缓存是在每个 CPU 核内，而三级缓存是针对所有的核的，另外，一级缓存还对数据和指令做了区分，这是因为数据会被经常更改，而指令不会被经常更改，因为二者的读写频率有很大区别，所以区分开来效果更优。

代码的局部性

知道了计算机存储结构，以及一些存储单元的特性，对我们写代码有何借鉴呢？根据缓存的特性，如果是近期刚使用过的数据，那么它在缓存中的概率会更高，而如果我们去读取那些很久没有读取的数据，它在缓存中的概率就会更低，这意味着需要去更低层次的存储单元去读取，当然时间开销也就更大。另外还有一点非常重要的，数据的读取的单位是数据块，如果你所需要的数据都在一个块中的话，缓存命中的几率也会更大。

依照这两点，我们可以得出两个局部性（Locality）的定义：

时间局部性（Temporal Locality）：具有良好时间局部性的程序，被引用过一次的存储器位置很可能在不远的将来继续被多次引用
空间局部性（spatial locality）：具有良好空间局部性的程序，如果一个存储器位置被引用了一次，那么不久的将来，附近的存储器位置很可能被引用

拥有好的局部性的程序的运行效率通常会更高。我们还是通过一个实际的例子来说明一下，假设我们要对一个二维数组里面的所有元素做求和操作，有以下两种不同的遍历方式：

  
int sumarrayrows(int a[M][N]) {
    int i, j, sum = 0;
    for (i = 0; i < M; i++)
        for (j = 0; j < N; j++)
            sum += a[i][j];
    return sum;
}

int sumarraycols(int a[M][N]) {
    int i, j, sum = 0;
    for (j = 0; j < N; j++)
        for (i = 0; i < M; i++)
            sum += a[i][j];
    return sum;
}

上面两种方式很好地说明了空间局部性，我们知道数组是一段连续的存储区间，而二维数组则是多个一维数组拼接而成，所以数据在存储单元中的存放顺序是 $a_{00},a_{01},a_{02},…,a_{10},a_{11},a_{12},…$。

第一种逐行遍历方式的顺序就是跟上面元素的排列排序一致，因此有较好的空间局部性，程序运行效率也更高。反观第二种逐列的遍历方式，遍历顺序为 $a_{00},a_{10},a_{20},…,a_{01},a_{11},a_{21},…$，当数组足够大，每次去到存储单元中读取的数据块都和前面读去过的数据块不一样，因此都需要重新去到下一层存储结构中获取数据并把之前存放的数据替换掉，但是这些被替换掉的数据在循环遍历中还会频繁访问到，这就是程序低效的根源。

因此，在以后写程序，特别是写循环语句时，保证循环中引用数据的局部性是性能的关键，需要注意这一点。

存储器山

要想更好地理解局部性，我们继续看一个复杂点的例子——矩阵的乘法，下图列出了六种不同的实现方法：

上面的程序的缓存 miss 的几率如下表所示：

可以看到，最后两种的缓存命中率更高，因而效率也会更高，下图表示的是不同数组大小下的运行时间：

图中显示，最快的版本和最慢的版本的时间差别可以去到大几十倍。这里有一点很有意思，有些版本的单次循环的时间开销会在数组大小到达一定的时候猛增，这个现象是和存储单元的块大小有关。当数组大小特别小的时候（上图中没显示），所有的数据都可以放在一个数据块内，那么不管如何遍历，除第一次读取以外，其余的读取均会命中缓存，而当数组大小变大时，好的局部性的代码会更好地利用缓存，缓存命中率更高。

性能和局部性的关系并不是线性的，它们的关系可以由下图说明：

图中的 Stride 表示每次读取数据之间的间隔，间隔越小空间局部性越好，另外决定性能的一个因素是我们前面讨论的块大小，引用数据的块大小过大会导致当前的存储单元无法存放，因此计算机会去到更低层次的存储单元中获取，这会大大影响效率。

能够给到我们的建议就是：

写程序的时候重点关注内层循环，聚焦在计算和内存的引用
尽量使用不久前引用过的数据，这可以增大时间局部性
尽量挨个遍历，这可以增大空间局部性

日志, 计算机理论知识

计算机理论知识

This post is licensed under CC BY 4.0 by the author.