存储器层次结构

存储技术

随机访问存储器

随机访问存储器(Random-Access Memory, RAM) 根据存储单元可分为两类: 静态的 RAM(SRAM) 和动态的 RAM(DRAM).

SRAM

SRAM 将每个位存储在一个双稳态(bistable) 的存储单元里. 每个单元用一个六晶体管电路实现. 它可以无限期地保持在两个不同的电压配置或者状态之一, 其他任何状态都是不稳定的, 电路会迅速地转移到两个稳定状态中的一个.

注: 当钟摆在垂直的位置时, 处于亚稳态, 最细微的扰动也能使它倒下, 且无法恢复.

• 特点
  只要有电, 它就能永远保持它的值, 即使有干扰来扰乱电压, 当干扰消除时电路就会恢复到稳定值.

DRAM

DRAM 将每个位存储为对一个电容的充电. 每个单元由一个电容和一个访问晶体管组成.

• 特点:

  • 每个电容非常小, 因此可以 DRAM 存储器可以制造得非常密集.
  • DRAM 存储器对干扰非常敏感, 当电容电压被扰乱后就永远不会恢复了. 暴露在光线中会导致电容电压改变.
  • 很多原因会导致漏电, 使得 DRAM 单元在 10~100 毫秒时间内失去电荷. 因此内存必须周期性地通过读出, 然后重写来刷新内存每一位.

传统的 DRAM 芯片中的单元(位)被分成 \(d\) 个超单元(supercell), 每个超单元都由 \(w\) 个 DRAM 单元组成. 一个 \(d\times w\) 的 DRAM 总共存储了 \(dw\) 位信息. 超单元被组织成一个 \(r\) 行 \(c\) 列长方形阵列, 这里 \(rc=d\). 信息通过称为addr 和 data 引脚(pin)的外部连接器流入和流出芯片.
每个 DRAM 芯片被连接到内存控制器的电路, 这个电路可以一次传送 \(w\) 位到每个 DRAM 芯片或一次从 DRAM 芯片传出 \(w\) 位. 为了读出 (i,j) 的内容, 内存控制器将行地址 i 发送到 DRAM, 然后是列地址 j. DRAM 把超单元 (i,j) 的内容发回给控制器作为相应. 行地址 i 称为RAS(Row Access Strobe), 列地址称为 CAS(Column Access Strobe).

一个 128 位的 \(16\times 8\) 的 DRAM 芯片

有 \(d=16\) 个超单元, 每个超单元存储 \(w=8\) 位信息. 例如我们要取 (2,1) 的内容, 先通过 addr 发送行地址 2, DRAM 会将该行内容复制到一个内部行缓冲区, 接下来发送列地址 1, DRAM 将超单元(2,1) 取出并通过 data 发送回内存控制器.

电路设计者将 DRAM 组织成二维阵列而不是线性数组的一个原因是降低芯片上地址引脚的数量. i.e. \(\max(\lceil \log_2{r} \rceil,\lceil \log_2{c} \rceil)\)

DRAM 芯片封装在内存模块中, 它插到主板的扩展槽上.

8 个 8M\(\times\)8 的 DRAM 组成的内存模块

要从内存地址 A 取一个字, 内存控制器将 A 转化为一个超单元地址 (i,j), 并将它发送到内存模块, 然后内存模块再将 i 和 j 广播到每个 DRAM. 每个 DRAM 输出它的 (i,j) 超单元的 8 位内容, 模块中的电路收集这些输出并将它们合并为一个 64 位的字, 再返回内存控制器.

我们可以将多个内存模块连接到内存控制器, 聚合成主存. 这种情况下内存控制器收到地址 A 时会先找到包含地址 A 的内存模块 A, 然后按照上述步骤得到字.

• 增强的 DRAM
  • 快页模式 DRAM(Fast Page Mode DRAM, FPM DRAM)
    传统的 DRAM 将超单元一整行复制到它的内部行缓冲区, 使用一个然后丢弃剩余的. FPM DRAM 允许对同一行连续地访问可以直接从行缓冲区得到服务.
  • 扩展数据输出的 DRAM(Extended Data Out DRAM, EDO DRAM)
    FPM DRAM 的增强形式, 允许各个 CAS 信号在时间上靠得更紧密一点.
  • 同步 DRAM(Synchronous DRAM, SDRAM)
    他们与内存控制器通信使用一组显式的控制信号(FPM EDO都是异步的), 最终效果是 SDRAM 能比异步的存储器更快地输出超单元的内容.
  • 双倍数据速率同步 DRAM(Double Data-Rate Synchronous DRAM, DDR SDRAM)
    使用两个时钟沿作为控制信号, 从而使 DRAM 的速度翻倍.
  • 视频 RAM(Video RAM, VVRAM)

非易失存储器

如果断电, DRAM 和 SRAM 会丢失他们的信息, 因此他们是易失的(volatile). 而非易失存储器(Nonvolatile Memory) 即使断电也能保存他们的信息, 这类存储器称为只读存储器(Read-Only Memory, ROM).(部分存储器可以读写, 历史原因我们保留名字)

• PROM(Programmable ROM, 可编程ROM): 只能被编程一次, PROM 每个存储器单元都有一种熔丝, 只能用高电流熔断一次.
• 可擦写可编程 ROM(Erasable Programmable ROM, EPROM): 可以批量擦除
• 闪存(Flash Memory): 具有部分(块级)擦除功能, 大约擦除十万次后会耗尽
  存储在 ROM 设备中的程序称为固件(firmware). 当一个计算机系统通电后, 它会运行存储在 ROM 中的固件.

访问主存

数据流通过 总线(bus) 的共享电子电路在处理器和 DRAM 主存之间来回回传递数据. 每次 CPU 和主存之间的数据传送都是通过总线事务(bus transaction)来完成.
总线是一组并行的导线, 能携带地址, 数据和控制信号.

其中 I/O 桥接器中包括内存控制器, 能够将系统总线的电子信号和内存总线的电子信号互相翻译, 也能将系统总线和内存总线连接到I/O总线.

读事务&写事务

从内存中加载数据到寄存器: movq A, %rax

• CPU 将 地址 A 放到系统总线上, I/O 桥将信号传递到内存总线.
• 主存感知到内存总线上的地址信号, 从内存总线读地址, 从 DRAM 取出数据字, 并将数据写到内存总线. I/O 总线将内存总线信号翻译成系统总线信号, 然后沿着系统总线传递.
• CPU 感知到系统总线上的数据, 从总线上读数据, 并将数据复制到寄存器 %rax.
  
  

写内存类似:

磁盘存储

磁盘(disk) 是广为应用的保存大量数据的存储设备, 存储数据的数量级可以达到几百到几千千兆字节.

磁盘构造

磁盘是由 盘片(platter) 构成的, 每个盘片有两个表面. 表面覆盖着磁性记录材料. 盘片中央有一个可以旋转的主轴(spindle), 它使得盘片以固定的旋转速率旋转.
每个表面是由一组 磁道(track) 的同心圆组成的. 每个磁道被划分为一组扇区(sector). 每个扇区包含相等数量的数据位(通常是 512 字节). 扇区之间由一些间隙分隔开, 间隙不存储数据位, 间隙存储用来标识扇区的格式化位.
通常使用 柱面(cyclinder) 来描述多个盘片驱动器的构造, 柱面是所有盘片表面上到主轴中心的距离相等的磁道的集合.

磁盘容量

一个磁盘上可以记录的最大位数称为他的最大容量, 主要由下列技术因素决定:

• 记录密度(位/英寸): 磁道一英寸的段中可以放入的位数.
• 磁道密度(道/英寸): 从盘片中心出发半径上一英寸的段内可以有的磁道数.
• 面密度(位/平方英尺): 记录密度与磁道密度的乘积.

为了保持每个磁道有固定的扇区数, 越往外的磁道扇区隔得越开.
现代大容量磁盘使用一种多区记录的技术, 柱面的集合被分割成不相交的子集合, 称为记录区.
磁盘容量计算公式:

磁盘操作

磁盘用读/写头来读写存储在磁性表面的位, 而读写头连接到一个传动臂一端. 磁盘以扇区大小的块来读写数据, 对扇区的访问时间有三个主要部分组成:

• 寻道时间: 为了读取某个目标扇区的内容, 传送臂首先将读/写头定位到包含目标扇区的磁道上. 移动传送臂的时间称为寻道时间. 寻道时间 \(T_{seek}\) 依赖于读/写头以前的位置和传送臂在盘面上移动的速度.
• 旋转时间: 读/写头到期望的磁道后, 驱动器等待目标扇区的第一个位旋转到读/写头下. 这个步骤的性能依赖于读/写头到达目标扇区盘面的位置以及磁盘的旋转速度.
  最大旋转延迟 \(T_{max_rotation}=\frac{1}{RPM}\times \frac{60s}{1min}\)(整周期), 平均旋转时间是最大延迟的一半.
• 传送时间: 当读/写头处于目标扇区的第一位时, 就可以进行传送了. 一个扇区的传送时间依赖于旋转速度和每条磁道的扇区数目. \(T_{avg\_transfer}=\frac{1}{RPM}\times \frac{1}{平均扇区数/磁道}\times \frac{60s}{1min}\)

我们可以发现, 寻道时间和旋转时间是主要的影响部分, 而且两者大致相等, 可以据此估计使用时间.

逻辑磁盘块

为了对操作系统隐藏复杂性, 现代磁盘将它们的构造呈现为一个简单的视图, 一共 B 个扇区大小的逻辑块的序列, 编号为 \(0,1,\ldots,B-1\). 磁盘封装中有一个小的硬件/固件设备, 称为磁盘控制器, 维护逻辑块号和实际磁盘扇区的映射关系.
当操作系统想要执行一个 I/O 操作时, 如从磁盘读取数据到主存:

• 操作系统发送一个命令道磁盘控制器, 让它读某个逻辑块号.
• 硬盘控制器上的固件执行快速表查找, 使得该逻辑块号翻译成一个三元组 (盘面, 磁道, 扇区) 的三元组
• 磁盘控制器解释三元组信息, 将读/写头移动到对应的扇区
• 将读取到的信息放到磁盘控制器的缓冲区中
• 将缓冲区中的数据复制到主存中

磁盘格式化

磁盘控制器必须对磁盘进行格式化, 然后才能在该磁盘上存储数据.
格式化包括:

• 用标识扇区的信息填写扇区之间的间隙
• 标识出表面有故障的柱面并且不使用他们
• 在每个区中预留出一组柱面作为备用(因此格式化容量比最大容量要小)

连接 I/O 设备

如上图, 图形卡/监视器/鼠标/键盘/磁盘这样的输入/输出(I/O)设备, 都是通过 I/O 总线连接到 CPU 和主存.

• 通用串行(Universal Serial Bus, USB)控制器是一个连接到 USB 总线的设备的中转机构, USB 总线是一个广泛使用的标准, 连接各种外围 I/O 设备.
• 图形卡(或适配器) 包含硬件和软件逻辑, 它们负责代表 CPU 在显示器上面画像素.
• 主机总线适配器将一个或多个磁盘连接到 I/O 总线, 使用的是一个特别的主机总线接口定义的通信协议.
• 网络适配器: 可以通过将适配器插入主板上空的扩展槽中, 从而连接到 I/O 总线.

访问磁盘

CPU 使用一种称为 内存映射I/O 的技术来向 I/O 设备发射命令, 地址空间中有一块地址是为与 I/O 设备通信保留的. 每个这样的地址称为一个 I/O 端口.
设备可以自己执行读或者写总线事务而不需要 CPU 干涉的过程, 称为直接内存访问(Direct Memory Access, DMA), 这种数据传送称为 DMA 传送.

磁盘读取

假设磁盘控制器映射到端口0xa0.

• CPU会通过对地址 0xa0 执行三个存储指令，将地址 0xa0 的内容保存到内存中，完成对磁盘的读取。发送完指令后，由于磁盘读取速度比 CPU 执行速度慢很多，所以 CPU 会先去执行其他工作.

  • 指令1：发送一个命令字，告诉磁盘发起一个 Read
  • 指令2：指明应该读取的逻辑块号
  • 指令3：指明保存的内存地址

• 磁盘控制器接收到Read命令后，会通过上述方法直接将磁盘内容传送到主存中.(DMA 传送)

• 磁盘发送完数据后，会给 CPU 发送一个中断信号，暂停 CPU 正在做的工作，然后将控制返回到 CPU 被中断的地方.

固态硬盘

固态硬盘(Solid State Disk, SSD) 是一种基于闪存的存储技术. SSD 封装插在 I/O 总线上标准硬盘插槽, 行为就和其他硬盘一样.

上图是典型 SSD 的性能特征. 它由闪存和闪存翻译层组成.

• 闪存翻译层: 是一个硬件/固件设备, 扮演与磁盘控制器相同的角色, 将对逻辑块的请求翻译成对底层物理设备的访问.
• 闪存: 闪存的基本属性决定了 SSD 随机读写的性能, 通常由 B 个块的序列组成, 每个块由 P 页组成, 页作为数据的单位进行读写. 通常页大小为 512 字节-4KB，块中包含 32-128 页, 则块的大小有 16KB-512KB.

只有在一页所属的块整个被擦除之后, 才能写这一页. 因此读 SSD 比写要快.
随机写很慢, 因为擦除块需要相对较长的时间, 而且如果写操作试图修改一个包含已经有数据的页 p, 那么这个块种所有带有用数据的页必须被复制到一个新(擦除过的)块.
闪存块会磨损, 所以 SSD 也容易磨损. 闪存翻译层中的平均磨损逻辑试图通过将擦除平均分布在所有的块上来最大化每个块的寿命.

SSD的优缺点：

• 优点: 由于闪存是半导体存储器，没有移动的部件，所以速度比磁盘更快且磨损小，能耗低.
• 缺点: SSD每字节比磁盘贵大约30倍，所以常用的存储容量比磁盘小100倍左右.

存储技术趋势

• 不同的存储技术有不同的价格和性能折中.
  SRAM 比 DRAM 快一点, 而 DRAM 比 磁盘块很多. 另一方面, 快速存储总是比慢速存储要贵的.
• 不同存储技术的价格和性能属性以截然不同的属性变化着

DRAM 和磁盘的性能滞后于 CPU 的性能. 而SRAM的性能虽然也滞后于CPU性能, 但是还保持增长, 所以现代计算机会使用基于SRAM的高速缓存, 来弥补CPU和内存之间的差距.

局部性

具有良好局部性(locality) 的程序, 即它们倾向于引用最近引用过的数据项周围的数据项, 或者最近引用过的数据项, 这被称为局部性原理. 局部性有两种形式:

• 时间局部性(temporal locality): 被引用过一次的内存位置很可能在不远的将来再被多次引用.
• 空间局部性(space locality): 如果一个内存位置被引用了一次, 那么程序很可能在不远的将来引用附近的一个内存位置.

一般而言, 有良好局部性的程序比局部性差的程序运行得更快.

局部性的应用

从硬件到操作系统，再到应用程序，都利用了局部性.

• 硬件: 在处理器和主存之间引入一个小而快速的高速缓存存储器, 来保存最近引用的指令和数据, 从而提高对主存的访问速度.
• 操作系统: 用主存来缓存虚拟空间中最近被引用的数据块.
• 应用程序: 比如Web浏览器会将最近引用的文档放入本地磁盘中, 来缓存服务器的数据.

Example

这个例子中, 变量 sum 每次循环迭代中都会被引用一次, 因此有较好的时间局限性. 因为 sum 是标量所以他没有空间局限性. 对于变量 v 来说有良好的空间局限性, 但时间局限性很差, 因为每个向量元素只能被访问一次. 综上, 我们认为这个函数有良好的局限性.

对于一个向量, 如果每一轮引用的数据项之间在内存空间中相隔 k, 则称该程序具有步长为 k 的引用模式(Stride-k Reference Pattern). 步长 k 越大, 则每一轮引用的数据在内存中间隔很大, 则空间局部性越差.

Example

第一个类似上文的例子. 第二个中变量 v 具有步长为 N 的引用模式, 空间局部性较差.

取指令方面, 因为程序指令是存放在内存中的, CPU 必须取出这些指令, 所以我们也能考虑取指的局限性. for 循环体中的指令是按连续的内存顺序执行的, 因此循环具有良好的空间局限性. 因为循环体会执行多次, 因此他也具有良好的时间局限性.

总的来说:

• 重复引用相同变量的程序有良好的时间局部性.
• 对于具有步长为 k 的引用模式的程序, 步长越小, 空间局部性越好.
• 对于取指令来说, 循环有好的时间和空间局部性. 循环体越小, 循环迭代次数越多, 局部性越好.

存储器层次结构

通过上面两节，我们可以得到存储技术和软件的基本属性：

• 不同存储技术的访问时间相差较大, 速度快的技术每字节的成本比速度慢的技术高, 且容量小. 并且CPU和主存之间的差距在变大.
• 编写良好的程序具有良好的局部性.

我们得到一种组织存储器系统的方法, 称为存储器层次结构(memory hierarchy).

一般而言, 从高层往低层走, 存储设备变得更慢, 更便宜和更大.

缓存

高速缓存(cache) 是一个小而快速的存储设备, 它作为存储在更大, 也更慢的设备中的数据对象的缓冲区域. 使用高速缓存的过程称为缓存(caching).
存储器层次结构的中心思想是: 对于每个 k, 位于 k 层的更快更小的存储设备作为位于 k+1 层的更大更慢的存储设备的缓存.

该结构为什么有效

因为程序的局部性原理. 相比于第k+1层的数据，程序会倾向于访问存储在第k层的数据。如果我们访问第k+1层存储的数据，我们会将其拷贝到第k层，因为根据局部性原理我们很有可能将再次访问该数据，由此我们就能以第k层的访问速度来访问数据。而且因为我们不经常访问第k+1层的数据，我们就可以使用速度更慢且更便宜的存储设备.

第 k+1 层的存储器被划分为连续的数据对象组块(chunk), 称为块(block). 每个块有一个唯一的地址或名字. 块可以是固定大小, 也可以是可变大小.
数据总是以块大小为传送单元在第 k 层和 k+1 层之间来回复制. 层次结构中较低层(离 CPU 较远)的设备的访问时间较长, 为了补偿较长的访问时间, 倾向于使用较大的块.

缓存命中

当程序需要 k+1 层的某个数据对象 d 时, 它首先在当前存储在 k 层的一个块中查找 d. 如果 d 刚好缓存在第 k 层, 那么就是我们所说的缓存命中(cache hit).

缓存不命中

若第 k 层中没有 d, 就是缓存不命中(cache miss). 此时第 k 层的缓存从 k+1 层的缓存中取出包含 d 的那个块. 如果第 k 层的缓存已经满了, 就会覆盖现存的一个块.
覆盖现存块的过程称为替换或驱逐这个块. 被驱逐的块也称为牺牲快(victim block). 决定替换哪个块是由缓存的替换策略控制的.

• 一个空的缓存称为冷缓存(cold cache), 此时的不命中称为强制性不命中或者冷不命中.
• 只要发生了不命中, 缓存就要执行某个放置策略. 但这种限制性的放置策略会引起一中不命中, 即冲突不命中. e.g. 我们将 k+1 层的块 i 放在 k 层的 \(i mod 4\) 的块中. 此时我们如果连续请求块 0 和块 8, 两次引用都会不命中.
• 块的集合称为这个阶段的工作集. 当工作集大小超过缓存的大小时, 缓存会经历容量不命中.

通过以上内容，就能解释局部性好的程序的优势:

• 时间局部性: 当一个数据对象在第一次不命中被复制到缓存中时，我们希望程序的时间局部性好，则在不久的将来就能反复在第k层访问到该块，使得程序运行更快.
• 空间局部性: 由于缓存中一个块包含多个数据对象，我们希望程序的空间局部性好，就可以直接利用第k层的数据块，避免再从第k+1层传输块到第k层.

高速缓存存储器

通用的高速缓存存储器组织架构

考虑一个系统, 每个存储器地址有 m 位, 形成 \(M=2^m\) 个不同的地址. 高速缓存被组织成一个 \(S=2^s\) 个高速缓存组的数组. 每个组有 E 个高速缓存行, 每个行是由一个 \(B=2^b\) 的数据块, 一个有效位, 和 \(t=m-(b+s)\)个标记位组成.
高速缓存的结构可以通过元组 \((S, E, B, m)\) 高速缓存的大小 \(C=S\times E\times B\).

如上图, m 位的地址被分为三部分:

• s 位: 组索引.
• t 位: 每个高速缓存行中有一个 t 位的标记位, 唯一标识数据块. 当我们通过组索引定位到组时, 标记位告诉我们需要组中的哪一行. 只有当地址的标记和行的标记位相同, 而且设置了行的有效位, 才能缓冲命中.
• b 位: 在 B 个字节中的字偏移.

直接映射高速缓存

当 \(E=1\) 时, 高速缓存被称为直接映射高速缓存(direct-mapped cache).

从块中抽取出字的流程:

• 组选择: 从 w 的地址中间抽出 s 个索引位, 这些位被解释位为一个对应组号的无符号整数.
  
• 行匹配: 因为每个组只有一行, 当且仅当设置了有效位, 而且高速缓存行中的标记与 w 地址中的标记相匹配时, 这一行才包含 w 的一个副本.
  
• 字选择: 把块看成一个字的数组, 字节偏移就是这个数组的一个索引.
• 不命中时的行替换: 如果缓存不命中, 它就从存储器层次结构中的下一层取出被请求的块, 然后将新的块存储在组索引位指示的组中的一个高速缓存行中.

直接映射高速缓存中的冲突不命中

当程序访问大小为 2 的幂次的数组时, 通常会发生冲突不命中.

float dotprod(float x[8], float y[8]) {
    float sum = 0.0;
    int i;

    for (i = 0; i < 8; i++)
        sum += x[i] * y[i];
    return sum;
}

假设浮点数是 4 个字节, x 被加载到 0 开始的 32 字节连续内存中, y 从地址 32 开始. 假设一个块是 16 个字节, 由两个组组成. 那么 x[i] 和 y[i] 会被映射到相同的内存组:

这样我们会在 x 和 y 的块之间抖动(thrash), 即高速缓存反复地加载和驱逐相同的高速缓存块的组.
可以发现: 即使程序的局部性良好, 且工作集的大小没有超过高速缓存容量, 但是由于这些数据块都被映射到了相同的高速缓存组中, 且直接映射高速缓存每个组中只有一个高速缓存行, 所以会出现抖动, 不断出现缓存不命中. 我们可以修正抖动问题: 在每个数组的结尾放 B 字节的填充.

为什么用中间的位来做索引

如果用高位做索引, 那么一些连续的内存块就会映射到相同的高速缓冲块. 顺序扫描一个数组的元素, 那么高速缓存只能保存一个块大小的数组内容, 这样的使用效率很低.

级相联高速缓存

直接映射高速缓存中冲突不命中的根源就是每个组只有一行. 级相联高速缓存(set associative cache) 放送了这个限制. 一个 \(1<E<C/B\) 的高速缓存称为 E 路组相联高速缓存.
抽字过程如上. 当缓存不命中时需要缓存行替换. 如果对应高速缓存组中有空行, 直接保存到空行, 否则考虑合适的替换策略.

• 最不常使用(Least-Frequently-Used, LFU): 替换过去某个时间窗口内引用次数最少的一行.
• 最近最少原理(Least-Recently-Used, LRU): 替换最后一次访问时间最久远的那一行.

全相联高速缓存

全相联高速缓存(Full Associative Cache) 是用一个包含所有高速缓存行的组组成的, 其中 \(E=C/B\) 即 \(E=1\).
注意地址中不需要组索引位, 地址只被划分为一个标记和一个块偏移.
因为高速缓存电路必须并行地搜索许多相匹配的标记, 构造一个又大又快的相联高速缓存很困难, 而且很昂贵. 因此全相联高速缓存只适合做很小的缓存.

写操作

当 CPU 想要对地址 A 进行写操作时, 会通过地址 A 判断是否缓存了该地址, 如果缓存了称为写命中(Write Hit),否则称为写不命中(Write Miss).

• 写命中: 高速缓存会先更新在缓存中的版本, 然后采取不同的方法更新下一版本.

  • 直写(write-through): 立即将 w 的高速缓存块写回到紧挨着的低一层中. 缺点是每次写都会引起总线流量.
  • 写回(write-back): 尽可能地推迟更新, 只有当替换算法要驱逐这个更新过的块时才把它写到紧挨着的低一层中. 为此我们要为高速缓存维护一个额外的修改位. 它显著地减少了总线流量, 但缺点是增加了复杂性.

  • 写不命中:

  • 写分配(write-allocate): 加载相应的低一层中的块到高速缓存中, 然后更新这个高速缓存块. 写分配试图利用空间局部性, 但缺点是每次不命中都会导致一个块从低到高的传送.

  • 非写分配: 避开高速缓存, 直接将这个字写到低一层中.

直写高速缓存通常为写不分配的, 写回高速缓存通常为写分配的. 建议采用写回和写分配.

真实的高速缓存层次结构

实际上, 高速缓存既保存数据, 也保存指令

• i-cache: 只保存指令的高速缓存.
• d-cache: 只保存程序数据的高速缓存.
• 统一的高速缓存(unified cache): 既保存指令又保存数据的高速缓存.

这样做的原因:

• 将数据和指令分别保存在两个高速缓存中, 使得处理器可以同时读一个指令字和一个数据字.
• i-cache 通常是只读的, 所以会比较简单.
• 可以针对不同的访问模式优化这两个高速缓存, 使用不同的块大小、相联度和容量.
• 确保数据访问和指令访问之间不形成冲突不命中.

代价就是会导致高速缓存容量变小, 提高出现容量不命中的可能性.

高速缓存参数对性能的影响

衡量高速缓存性能的指标:

• 不命中率: 不命中数量/引用数量
• 命中率: 1 - 不命中率
• 命中时间: 从高速缓存传送一个字到 CPU 所需的时间
• 不命中处罚: 由于不命中所需要的额外的时间

参数	优点	缺点	建议
高速缓存大小(越大)	提高命中率	增加命中时间	L1<L2<L3
块大小(越大)	利用空间局限性, 提高命中率	高速缓存行越少, 损害时间局限性; 对不命中处罚有负面影响, 传送时间越长	现代系统折中设置块包含64个字节
相联度(越高, 即 E 越大)	降低了高速缓存由于冲突不命中出现抖动的可能	较高的成本; 需要更多标记位; 增加命中时间; 增加不命中惩罚	L1 和 L2 使用 8 路组相联, L3 使用 16 路组相联
写策略(直写)	容易实现; 能使用独立于高速缓存的写缓冲区来更新内存;读不命中的开销不大	引起的传送次数多	高速缓存越往下层, 越可能使用写回而不是直写

由此, 编写高速缓存友好的代码需要:

• 让最常见的代码运行得快.

  • 对局部变量的反复引用是好的, 因为编译器能够把它们缓存在寄存器之中(时间局部性).
  • 步长为 1 的引用模式是好的, 因为存储器层次结构中所有层次上的缓存都是将数据缓存为连续的块.(空间局部性)
  • 尽量减少每个循环内的缓存不命中数量, 较高的不命中率队运行时间可以有显著的影响.

存储器山

一个程序从存储器系统中读取数据的速率称为读吞吐量(Read Throughput) 或 读带宽(Read Bandwidth)，单位为MB/s. 我们通过以下代码来衡量空间局部性和时间局部性对程序吞吐量的影响.

通过调整 size(时间局部性. size 小则放进 L1 高速缓存, size 大则放进 L3) 和 stride(空间局部性, 步长) 来度量程序的吞吐量，可以得到以下存储器山(Memory Mountain).

保持 stride 不变, 观察高速缓存大小和时间局部性对性能的影响:

保持工作集为 4MB, 沿着 L3 山脊查看空间局部性对性能的影响:

综上所述：使频繁使用的字从 L1 中取出，还需要利用空间局部性，使得尽可能多的字从一个高速缓存行中读取到.

重新排列循环以提高空间局部性

矩阵乘法

假设两个矩阵都是 n*n 的 double 型数组. sizeof(double) == 8.
只有一个高速缓存, 其块大小为 32 字节.
n 很大以至于矩阵的一行都不能完全装进 L1 高速缓存中.
编译器将局部变量存储到寄存器中, 因此循环内对局部变量的引用不需要任何存储和加载指令.

其结果:(内循环)

使用分块提高时间局部性

评论