06-存储器的层次结构

在计算机系统模型中，CPU执行指令，而存储器系统为CPU存放指令和数据。实际上，存储器系统（memory system）是由不同容量、成本和访问时间的存储设备组成的层次结构。在这个层次结构中：CPU寄存器保存最常用的数据。靠近CPU的小的、 快速的高速缓存存储器作为相对慢速的主存储器中数据和指令的缓冲区域，下图将高速缓存又分为三个层级L1，L2，L3。主存又作为容量较大、速度较慢的磁盘上数据的缓冲区域。而磁盘又可以作为通过网络中其他机器上数据的缓冲区域。

存储器层次结构对应用程序的性能有者巨大的影响。假如数据存储在寄存器中，那么0个时钟周期内就能访问到它们；如果存储在高速缓存中，则需要4∼75个周 期；如果存储在主存中，需要上百个周期；如果存储在磁盘上，则需要约几千万个周期。之所以会有这样的差异，是由于不同存储器中使用的存储技术不同。基本的存储技术包括SRAM存储器、DRAM存储器、ROM存储器、旋转硬盘以及固态硬盘。

计算机程序的一个基本属性称为局部性。具有良好局部性的程序倾向于一次又一次地访问相同的数据项集合，或是倾向于访问邻近的数据项集合。具有良好局部性的程序比局部性差的程序更多地倾向于从存储器层次结构中较高层次处访问数据项，因此运行得更快。就比如二维数组按行读取比按列读取速度要快。

随机访问存储器
随机访问存储器（ Random-Access Memory,RAM）分为两类：静态的和动态的。静态RAM（SRAM）比动态RAM（DRAM）更快，但也贵得多。SRAM用来作为高速缓存存储器。DRAM用来作为主存以及图形系统的帧缓冲区。

静态RAM（SRAM）
SRAM将每个位存储在一个双稳态的（bistable）存储器单元里。每个单元是用一个六晶体管电路来实现的。这个电路有这样一个属性，它可以无限期地保持在两个不同的电压配置（configuration）或状态（state）之一。其他任何状态都是不稳定的，在不稳定状态时，电路会迅速转移到两个稳定状态的一个。由于SRAM存储器单元的双稳态特性，只要有电，它就会永远地保持它的值。即使有干扰（例如电子噪音）来扰乱电压，当干扰消除时，电路就会恢复到稳定值。

动态RAM（DRAM）：
DRAM将每个位存储为对一个电容的充电。DRAM存储器可以制造得非常密集。每个单元由一个电容和一个访问晶体管组成。但是，与SRAM不同，DRAM存储器单元对干扰非常敏感，当电容的电压被扰乱之后，它就永远不会恢复了。暴露在光线下会导致电容电压改变。下表总结了SRAM和DRAM存储器的特性。只要有供电，SRAM就会保持不变。与DRAM不同，它不需要刷新。SRAM的存取比DRAM快。SRAM对诸如光和电噪声这样的干扰不敏感。代价是SRAM单元比DRAM单元使用更多的晶体管，因而密集度低，而且更贵，功耗更大。

传统DRAM：

上图展示了一个\(16\times 8\)的DRAM芯片的组织，有\(d=16\)个超单元，每个超单元有\(w=8\)位，\(r=4\)行，\(c=4\)列。信息通过引脚的外部连接器流入和 流出芯片。每个引脚携带一个1位的信号。图中展示了两组引脚：8个data引脚， 用于传送一个字节到芯片或从芯片传出一个字节；2个addr引脚，用于携带2位的`行和列单元地址。

磁盘存储

前面介绍的随机访问存储器RAM必须在有电的时候才能存取数据，而磁盘则能够永久存储大量的数据。不过，从磁盘上读信息的时间为毫秒级，比从DRAM读数据慢了10万倍，比从SRAM读数据慢100万倍。

磁盘结构包括：磁头（head）、 磁道（track）、 柱面（cylinder）、扇区（sector）、 圆盘（platter）。那么这些都代表着什么呢？

磁盘由盘片（platter）和可以旋转的主轴（spindle）构成。每个盘片都有两个表面，上面覆盖着磁性记录材料。主轴使盘片能以固定的旋转速率旋转，通常为5400∼15000转每分钟（"转每分钟"也作为单位，RPM）。磁盘盘片的表面由一组磁道（track）的同心圆组成。每条磁道由存储数据的扇区（sector）和标识扇区的间隙（gap）构成。其中每个扇区包含相等的数据位（通常为512字节），而间隙仅用于标识扇区的格式化位，并不存储数据。磁盘由一个或多个叠放的盘片组成，并被封装在一个密封的包装里。整个装置称为磁盘驱动器（disk drive），简称为磁盘。通常磁盘又被称为旋转硬盘（rotating disk）或机械硬盘。

磁盘通过读写头（read/write head）来读写存储在磁性表面的位，而读写头连接到一个传动臂（actutaor arm）一端。通过沿着半径方向移动传动臂，驱动器可以将读写头定位在盘片的任何磁道上。在这个过程中读写头垂直排列，一致行动。

一般而言，高速缓存（cache）是作为更大、更慢的存储设备的一个缓冲区域，它相对而言更小、更快速。存储器层次结构的中心思想是，对于每个k，位于k层的更快更小的存储设备作为位于k+1层更大更慢的存储设备的缓存。

在存储器层次结构中，第k+1层的存储器被划分成连续的数据对象组块（chunk），称为块（block）。每个块都有一个唯一的地址或名字。通常块的大小是固定的，但也可能是可变的（例如存储在Web服务器上的远程HTML文件）。在第k层中，存储器被划分成较少的块的集合，其中每个块的大小与k+1层中的块的大小相同。这样，数据就以块大小为传送单元在第k层和k+1层之间来回复制。

多级缓存之间的配合工作

缓存和内存之间的映射有三种：

1. 直接映射
2. 全相连映射
3. 组相连映射

缓存命中：当程序需要第k+1层的某个数据对象d时，它首先在当前存储在第k层的一个块中查找d。如果d刚好缓存在第k层中，那就称为缓存命中，这时程序直接从第k层读取d。由于第k层相对于k+1层来说是更块的存储设备，因此读取速度比从第k+1层读取更快。

缓存不命中：如果第k层中没有缓存数据对象d，那么就是我们所说的缓存不命中（cache miss）。当发生缓存不命中时，第k层的缓存从第k+1层缓存中取出包含d的那个块，如果第k层的缓存已经满了，可能就会覆盖现存的一个块。（缓存的替换策略：随机替换替换策略，最少被使用（LRU）替换策略）

覆盖一个现存块的过程称为替换或驱逐这个块。决定该替换哪个块是由缓存的替换策略（replacement policy）控制的。例如，随机替换策略会随机替换一个块；而LRU替换策略会选择替换最后被访问的时间距现在最远的块。

缓存不命中种类：
区分不同种类的缓存不命中有时候是很有帮助的。如果第k层的缓存是空的，那么对任何数据对象的访问都会不命中。一个空的缓存有时被称为冷缓存（cold cache），此类不命中称为强制性不命中（compulsory miss）或冷不命中（cold miss）。冷不命中很重要，因为它们通常是短暂的事件，不会在反复访问存储器使得缓存暖身（warmed up）之后的稳定状态中出现。如果发生了不命中，那么第k层的缓存就必须执行某个放置策略（placement policy），来确定把从第k+1层中取出来的块放在哪里。最灵活的替换策略是允许来自第k+1层的任何块放在第k层的任何块中。

CPU要访问的数据在cache中有缓存，称为“命中” (hit)，反之则称为“缺失” (miss)。多级cache之间是如何配合工作的呢？我们假设现在考虑的系统只有两级cache。

当CPU试图从某地址load数据时，首先从L1 cache中查询是否命中，如果命中则把数据返回给CPU。如果L1 cache缺失，则继续从L2 cache中查找。当L2 cache命中时，数据会返回给L1 cache以及CPU。如果L2 cache也缺失，很不幸，我们需要从主存中load数据，将数据返回给L2 cache、L1 cache及CPU。这种多级cache的工作方式称之为inclusive cache。某一地址的数据可能存在多级缓存中。与inclusive cache对应的是exclusive cache，这种cache保证某一地址的数据缓存只会存在于多级cache其中一级。也就是说，任意地址的数据不可能同时在L1和L2 cache中缓存。

直接映射缓存（Direct mapped cache）

我们继续引入一些cache相关的名词。cache的大小称之为cahe size，代表cache可以缓存最大数据的大小。我们将cache平均分成相等的很多块，每一个块大小称之为cache line，其大小是cache line size。例如一个64 Bytes大小的cache。如果我们将64 Bytes平均分成64块，那么cache line就是1字节，总共64行cache line。如果我们将64 Bytes平均分成8块，那么cache line就是8字节，总共8行cache line。现在的硬件设计中，一般cache line的大小是4-128 Byts。为什么没有1 byte呢？原因我们后面讨论。

这里有一点需要注意，cache line是cache和主存之间数据传输的最小单位。什么意思呢？当CPU试图load一个字节数据的时候，如果cache缺失，那么cache控制器会从主存中一次性的load cache line大小的数据到cache中。例如，cache line大小是8字节。CPU即使读取一个byte，在cache缺失后，cache会从主存中load 8字节填充整个cache line。又是因为什么呢？后面说完就懂了。

我们假设下面的讲解都是针对64 Bytes大小的cache，并且cache line大小是8字节。我们可以类似把这块cache想想成一个数组，数组总共8个元素，每个元素大小是8字节。就像下图这样。

现在我们考虑一个问题，CPU从0x0654地址读取一个字节，cache控制器是如何判断数据是否在cache中命中呢？cache大小相对于主存来说，可谓是小巫见大巫。所以cache肯定是只能缓存主存中极小一部分数据。我们如何根据地址在有限大小的cache中查找数据呢？现在硬件采取的做法是对地址进行散列（可以理解成地址取模操作）。我们接下来看看是如何做到的？

我们一共有8行cache line，cache line大小是8 Bytes。所以我们可以利用地址低3 bits（如上图地址蓝色部分）用来寻址8 bytes中某一字节，我们称这部分bit组合为offset。同理，8行cache line，为了覆盖所有行。我们需要3 bits（如上图地址黄色部分）查找某一行，这部分地址部分称之为index。现在我们知道，如果两个不同的地址，其地址的bit3-bit5如果完全一样的话，那么这两个地址经过硬件散列之后都会找到同一个cache line。所以，当我们找到cache line之后，只代表我们访问的地址对应的数据可能存在这个cache line中，但是也有可能是其他地址对应的数据。所以，我们又引入tag array区域，tag array和data array一一对应。每一个cache line都对应唯一一个tag，tag中保存的是整个地址位宽去除index和offset使用的bit剩余部分（如上图地址绿色部分）。tag、index和offset三者组合就可以唯一确定一个地址了。因此，当我们根据地址中index位找到cache line后，取出当前cache line对应的tag，然后和地址中的tag进行比较，如果相等，这说明cache命中。如果不相等，说明当前cache line存储的是其他地址的数据，这就是cache缺失。在上述图中，我们看到tag的值是0x19，和地址中的tag部分相等，因此在本次访问会命中。由于tag的引入，因此解答了我们之前的一个疑问“为什么硬件cache line不做成一个字节？”。这样会导致硬件成本的上升，因为原本8个字节对应一个tag，现在需要8个tag，占用了很多内存。

我们可以从图中看到tag旁边还有一个valid bit，这个bit用来表示cache line中数据是否有效（例如：1代表有效；0代表无效）。当系统刚启动时，cache中的数据都应该是无效的，因为还没有缓存任何数据。cache控制器可以根据valid bit确认当前cache line数据是否有效。所以，上述比较tag确认cache line是否命中之前还会检查valid bit是否有效。只有在有效的情况下，比较tag才有意义。如果无效，直接判定cache缺失。

上面的例子中，cache size是64 Bytes并且cache line size是8 bytes。offset、index和tag分别使用3 bits、3 bits和42 bits（假设地址宽度是48 bits）。我们现在再看一个例子：512 Bytes cache size，64 Bytes cache line size。根据之前的地址划分方法，offset、index和tag分别使用6 bits、3 bits和39 bits。如下图所示。

直接映射缓存的优缺点

直接映射缓存在硬件设计上会更加简单，因此成本上也会较低。根据直接映射缓存的工作方式，我们可以画出主存地址0x00-0x88地址对应的cache分布图。

我们可以看到，地址0x00-0x3f地址处对应的数据可以覆盖整个cache。0x40-0x7f地址的数据也同样是覆盖整个cache。我们现在思考一个问题，如果一个程序试图依次访问地址0x00、0x40、0x80，cache中的数据会发生什么呢？首先我们应该明白0x00、0x40、0x80地址中index部分是一样的。因此，这3个地址对应的cache line是同一个。所以，当我们访问0x00地址时，cache会缺失，然后数据会从主存中加载到cache中第0行cache line。当我们访问0x40地址时，依然索引到cache中第0行cache line，由于此时cache line中存储的是地址0x00地址对应的数据，所以此时依然会cache缺失。然后从主存中加载0x40地址数据到第一行cache line中。同理，继续访问0x80地址，依然会cache缺失。这就相当于每次访问数据都要从主存中读取，所以cache的存在并没有对性能有什么提升。访问0x40地址时，就会把0x00地址缓存的数据替换。这种现象叫做cache颠簸（cache thrashing）。针对这个问题，我们引入多路组相连缓存。我们首先研究下最简单的两路组相连缓存的工作原理。

两路组相连缓存（Two-way set associative cache）

我们依然假设64 Bytes cache size，cache line size是8 Bytes。什么是路（way）的概念。我们将cache平均分成多份，每一份就是一路。因此，两路组相连缓存就是将cache平均分成2份，每份32 Bytes。如下图所示。

cache被分成2路，每路包含4行cache line。我们将所有索引一样的cache line组合在一起称之为组。例如，上图中一个组有两个cache line，总共4个组。我们依然假设从地址0x0654地址读取一个字节数据。由于cache line size是8 Bytes，因此offset需要3 bits，这和之前直接映射缓存一样。不一样的地方是index，在两路组相连缓存中，index只需要2 bits，因为一路只有4行cache line。上面的例子根据index找到第2行cache line（从0开始计算），第2行对应2个cache line，分别对应way 0和way 1。因此index也可以称作set index（组索引）。先根据index找到set，然后将组内的所有cache line对应的tag取出来和地址中的tag部分对比，如果其中一个相等就意味着命中。

因此，两路组相连缓存较直接映射缓存最大的差异就是：第一个地址对应的数据可以对应2个cache line，而直接映射缓存一个地址只对应一个cache line。那么这究竟有什么好处呢？

两路组相连缓存优缺点

两路组相连缓存的硬件成本相对于直接映射缓存更高。因为其每次比较tag的时候需要比较多个cache line对应的tag（某些硬件可能还会做并行比较，增加比较速度，这就增加了硬件设计复杂度）。为什么我们还需要两路组相连缓存呢？因为其可以有助于降低cache颠簸可能性。那么是如何降低的呢？根据两路组相连缓存的工作方式，我们可以画出主存地址0x00-0x4f地址对应的cache分布图。

我们依然考虑直接映射缓存一节的问题“如果一个程序试图依次访问地址0x00、0x40、0x80，cache中的数据会发生什么呢？”。现在0x00地址的数据可以被加载到way 1，0x40可以被加载到way 0。这样是不是就在一定程度上避免了直接映射缓存的尴尬境地呢？在两路组相连缓存的情况下，0x00和0x40地址的数据都缓存在cache中。试想一下，如果我们是4路组相连缓存，后面继续访问0x80，也可能被被缓存。

因此，当cache size一定的情况下，组相连缓存对性能的提升最差情况下也和直接映射缓存一样，在大部分情况下组相连缓存效果比直接映射缓存好。同时，其降低了cache颠簸的频率。从某种程度上来说，直接映射缓存是组相连缓存的一种特殊情况，每个组只有一个cache line而已。因此，直接映射缓存也可以称作单路组相连缓存。

全相连缓存（Full associative cache）

既然组相连缓存那么好，如果所有的cache line都在一个组内。岂不是性能更好。是的，这种缓存就是全相连缓存。我们依然以64 Byts大小cache为例说明。

由于所有的cache line都在一个组内，因此地址中不需要set index部分。因为，只有一个组让你选择，间接来说就是你没得选。我们根据地址中的tag部分和所有的cache line对应的tag进行比较（硬件上可能并行比较也可能串行比较）。哪个tag比较相等，就意味着命中某个cache line。因此，在全相连缓存中，任意地址的数据可以缓存在任意的cache line中。所以，这可以最大程度的降低cache颠簸的频率。但是硬件成本上也是更高。

一个四路组相连缓存实例问题

考虑这么一个问题，32 KB大小4路组相连cache，cache line大小是32 Bytes。请思考一下问题：

1. 多少个组？
2. 假设地址宽度是48 bits，index、offset以及tag分别占用几个bit？

总共4路，因此每路大小是8 KB。cache line size是32 Bytes，因此一共有256组（8 KB / 32 Bytes）。由于cache line size是32 Bytes，所以offset需要5位。一共256组，所以index需要8位，剩下的就是tag部分，占用35位。这个cache可以绘制下图表示。

Cache分配策略（Cache allocation policy）

cache的分配策略是指我们什么情况下应该为数据分配cache line。cache分配策略分为读和写两种情况。

1. 读分配（read allocation）：当CPU读数据时，发生cache缺失，这种情况下都会分配一个cache line缓存从主存读取的数据。默认情况下，cache都支持读分配。
2. 写分配（write allocation）：当CPU写数据发生cache缺失时，才会考虑写分配策略。当我们不支持写分配的情况下，写指令只会更新主存数据，然后就结束了。当支持写分配的时候，我们首先从主存中加载数据到cache line中（相当于先做个读分配动作），然后会更新cache line中的数据。

Cache更新策略（Cache update policy）

cache更新策略是指当发生cache命中时，写操作应该如何更新数据。cache更新策略分成两种：写直通和回写。

• 写直通（write through）：当CPU执行store指令并在cache命中时，我们更新cache中的数据并且更新主存中的数据。cache和主存的数据始终保持一致。
  

• 写回（write back）：当CPU执行store指令并在cache命中时，我们只更新cache中的数据。并且每个cache line中会有一个bit位记录数据是否被修改过，称之为dirty bit（翻翻前面的图片，cache line旁边有一个D就是dirty bit）。我们会将dirty bit置位。主存中的数据只会在cache line被替换或者显示clean操作时更新。因此，主存中的数据可能是未修改的数据，而修改的数据躺在cache line中。

同时，为什么cache line大小是cache控制器和主存之间数据传输的最小单位呢？这也是因为每个cache line只有一个dirty bit。这一个dirty bit代表着整个cache line时候被修改的状态。

实例

假设我们有一个64 Bytes大小直接映射缓存，cache line大小是8 Bytes，采用写分配和写回机制。当CPU从地址0x2a读取一个字节，cache中的数据将会如何变化呢？假设当前cache状态如下图所示。

根据index找到对应的cache line，对应的tag部分valid bit是合法的，但是tag的值不相等，因此发生缺失。此时我们需要从地址0x28地址加载8字节数据到该cache line中。但是，我们发现当前cache line的dirty bit置位。因此，cache line里面的数据不能被简单的丢弃，由于采用写回机制，所以我们需要将cache中的数据0x11223344写到地址0x0128地址（这个地址根据tag中的值及所处的cache line行计算得到）。这个过程如下图所示。

当写回操作完成，我们将主存中0x28地址开始的8个字节加载到该cache line中，并清除dirty bit。然后根据offset找到0x52返回给CPU。

cache与内存之间的映射转载自蜗窝科技：http://www.wowotech.net/memory_management/458.html