Chapter 02 : Memory Hierarchy Design¶

约 8281 个字 41 行代码 27 张图片预计阅读时间 42 分钟

Main Memory¶

主存储器（Main Memory）是缓存和服务器之间的 I/O 接口
输入的数据被放在主存储器中，然后被处理器读取输出

性能指标：
- 延迟（Latency）：接收到块的第一个字的时间
  - 对于缓存来说很重要
  - 比较难优化
  - 分为获取时间（Access Time）和循环时间（Cycle Time）
    - 获取时间：发送读请求到字到达需要的时间
    - 循环时间：不相关的内存请求需要的最小时间，即获取开始和下一次获取开始之间的最小时间
- 吞吐率（Bandwidth）：接收剩下块的时间
  - 对于多核处理器、I/O 和 Blocks 比较大的缓存
  - 重新组织能更简单优化

一般来说，SRAM 为缓存，DRAM 为主存

SRAM¶

SRAM（Static Random Access Memory）
- 每比特六个晶体管，以防止信息在读取时受到干扰
- 不需要刷新，因此访问时间非常接近循环时间
- 有关缓存的内容可以看计组

DRAM¶

DRAM（Dynamic Random Access Memory）
- 每比特一个晶体管、定期刷新
- 读操作会破坏信息
- 循环时间>访问时间
- 由一个个库（Bank）组成，每个库由一系列行组成，每个行由一系列列组成
  - RAS（Row Address Strobe）：行地址闸门
  - CAS（Column Address Strobe）：列地址闸门
  - 大体如下图所示：其中 Pre（pre.charge）命令控制库的开与关；Act（Activate）命令传输行地址，拿到行后放进缓冲器，最后由特定的列地址决定数据
DRAM Improvements¶

对于 DRAM 来说也有一些改进方法：

定时信号（Timing Signals）：允许重复访问行缓冲器，不需要重复访问行地址
利用空间局部性（Leverage Spatial Locality）：每个阵列将为每次访问缓冲 1024~4096 位
时钟信号（Clock Signal）：添加到 DRAM 接口，这样重复传输就不会涉及与存储控制器同步的开销
同步 DRAM（SDRAM）
更宽的 DRAM（Wider DRAM）：为了更高的带宽让 DRAM 更宽
DDR SDRAM（Double Data Rate Synchronous DRAM）：在时钟的上升和下降沿都传输数据
多个库（Multiple Banks）：将 DRAM 分成 2～8 个库，让它们能独立工作

GDRAM¶

DRAM 还针对图形处理器（GPU）有 GDRAM（Graphics DRAM）和 GSDRAM（Graphics Synchronous DRAM）两种，以便为 GPU 提供更高的带宽

更宽的接口：32 位
更高的最大时钟频率、GDRAM 直接与 GPU 相连

Stacked / Embedded DRAM¶

HBM（High Bandwidth Memory）：将多个 DRAM 以堆叠或相邻的方式嵌入与处理器相同的封装中
更低的访问时延
通过允许更多更快的处理器和 DRAM 之间的连接来提高带宽

Flash Memory¶

一种电子可擦除可编程只读存储器（EEPROM）
只读但是可以被擦除
非易失性（Nonvolatile）：断电后数据不会丢失
作为 PMD 的主存

和 DRAM 的区别：

在块被复写之前必须擦除
非易失性且耗能更小
对于任意一个块，具有有限的写入周期数
- 写入均衡技术：确保写入块在整个内存中均匀分布
比 SDRAM 更便宜但是比磁盘更贵
比 SDRAM 更慢但是比磁盘更快

Phase-Change Memory¶

无需在写入前擦除页面
与 NAND 相比
- 写入性能提高 10 倍
- 读取延迟降低 2～3 倍
与 Flash 相比
- 读取延迟降低 2～3 倍
适用于固态硬盘（Solid State Drive, SSD）

Memory Dependability¶

内存在使用过程中可能会发生如下错误：

软错误/永久性故障
- 对存储单元内容的更改，而不是电路的更改
硬错误/瞬态故障
- 对一个或多个存储单元的操作作发生永久性变化

检测和修复的方法有：

仅奇偶校验
- 只需一个 bit 开销即可检测 Sequence 中的单个错误;
- 例如，每 8 个数据位 1 个奇偶校验位
仅限纠错码（Error-Correcting Code, ECC）
- 检测出两个错误并纠正一个错误，每 64 个数据位具有 8 位开销
Chipkill
- 类似于 RAID，在多个内存芯片之间分配数据和 ECC;
- 处理单个存储芯片的多个错误和完全故障;

Cache¶

Cache Performance¶

我们可以用 CPU 执行时间的计算公式用于评估缓存的性能，但是需要额外加上存储器停顿周期数：

\[ \text{CPU Execution Time} = (\text{CPU Clock Cycles} + \text{Memory Stall Cycles}) \times \text{Clock Cycle Time} \]

而存储器停顿周期数由缺失数和缺失损失（Miss Penalty）共同决定：

\[ \begin{aligned} \text{Memory Stall Cycles} &= \text{Numbers of Misses} \times \text{Miss Penalty}\\ &= \text{IC} \times \frac{\text{Misses}}{\text{Instruction}} \times \text{Miss Penalty}\\ &= \text{IC} \times \frac{\text{Memory Accesses}}{\text{Instruction}}\times \text{Miss Rate} \times \text{Miss Penalty}\\ \end{aligned} \]

此外，缺失损失和缺失率在读和写的情况下会有所不同，所以如有必要可以分开讨论：

\[ \begin{aligned} \text{Miss Stall Clock Cycles} &= \text{IC} \times \text{Reads per Instruction} \times \text{Read Miss Rate} \times \text{Read Miss Penalty}\\ &+ \text{IC} \times \text{Writes per Instruction} \times \text{Write Miss Rate} \times \text{Write Miss Penalty}\\ \end{aligned} \]

事实上，要想评估一个缓存的性能，最好的指标是内存访问时间，其计算公式如下：

\[ \begin{aligned} \text{Average Memory Access Time} &= (1-\text{Miss Rate})\times\text{Hit Time} + \text{Miss Rate} \times \text{Miss Time}\\ &= (1-\text{Miss Rate})\times\text{Hit Time} + \text{Miss Rate} \times (\text{Miss Penalty} + \text{Hit Time})\\ &= \text{Hit Time} + \text{Miss Rate} \times \text{Miss Penalty} \end{aligned} \]

Basic Optimizations¶

根据内存访问时间的计算公式，我们可以得到以下三种提升高速缓存性能的方向，以及对应的优化方法：

降低缺失率：更大的数据块，更大的高速缓存，更高的相联程度
降低缺失损失：多级高速缓存，给予读取更高的优先级
降低命中时间：在索引（动词）高速缓存时避免地址的转换

我们首先对缺失的情况分类（简称 3C 模型）：（该死的计组为什么会考这玩意 x）

强制缺失（Compulsory Miss）：最开始访问高速缓存的数据块时必定出现缺失情况，此时对应的数据块必须先被带入到高速缓存中
- 也称为冷启动缺失（Cold Start Miss）/ 第一次引用缺失（First Reference Miss）
容量缺失（Capacity Miss）：在程序执行的过程中，高速缓存无法包含所有需要的数据块，于是不得不抛弃一些数据块，但之后可能又需要检索这些数据块，此时缺失发生
冲突缺失（Conflict Miss）：对于组相联 / 直接映射而言，由于多个数据块映射到相同的组上，导致较早存入的数据被替换，使得后续访问时发生缺失
- 也称为碰撞缺失（Collision Miss）

容量缺失和冲突缺失有什么区别？

缓存已满时会发生容量缺失，此时不一定会发生冲突缺失
冲突缺失可能会在缓存未被完全占用的情况下发生

下面两张图分别展示了对于不同大小的高速缓存，3C 模型在总缺失率和缺失率分布上的情况：

Larger Block Size¶

降低缺失率的最简单的方法是增大数据块的大小，它借助了空间局部性的优势，可以减少强制冲突的发生

同时，更大的数据块还会提升缺失损失率，因为对于相同大小的高速缓存，数据块的数量会随之减少，从而导致冲突缺失乃至容量缺失的发生（当高速缓存较小时）。有时甚至还会出现缺失损失的提升超过缺失率的降低的情况，那么此时我们就不应该采取这种方法

具体来说，数据块大小的选择需要同时考虑下级存储器的时延和带宽

如果时延和带宽都很大的话，那么考虑使用更大的数据块，因为此时高速缓存在每次缺失中可以得到更多的字节数据，而缺失损失的提升相对较小
但如果时延和带宽都很小的话，则鼓励使用更小的数据块，因为更大的数据块只能节省很少的时间

下图展示了五种不同大小的高速缓存在不同大小的数据块下的缺失率：

Example

给定以上的缺失率，假设内存访问开销需要 80 个时钟周期，需要 2 个时钟周期传输 16 字节的数据，不管块大小为多少命中时间都是 1 个时钟周期，那么对于每一种缓存大小，选择多大的数据块大小可以使得平均内存访问时间最小呢？

Answer

对于一个 4KiB 大小的缓存数据块大小为 16 字节的平均访问时间为：

\[ \text{Average Memory Access Time} = 1 + 8.57\% \times 82 = 8.027\text{ clock cycles} \]

对于一个 256 KiB 大小的缓存数据块大小为 256 字节的平均访问时间为：

\[ \text{Average Memory Access Time} = 1 + 0.49\% \times 112 = 1.549\text{ clock cycles} \]

Larger Cache¶

降低容量缺失的一种方法是增大高速缓存的大小。但这样做的缺点是可能会带来更长的命中时间，以及消耗更高的成本和功率

Higher Associativity¶

在介绍 3C 模型的时候给出了一张相联程度与缺失率之间的关系图，我们可以对此得到：

实际情况下，八路组相联降低缺失的效果近乎等价于全相联的效果
2:1 高速缓存经验法则：（对于 128KiB 以下的高速缓存）对于大小为 N 的直接映射的高速缓存，它的缺失率与大小为 N/2 的二路组相联的高速缓存的缺失率相等

相联程度的提高虽然能够降低缺失率，但代价是增大了命中时间。因此，对于高时钟频率的处理器而言，不建议提升相联程度；而在缺失损失较大的情况下，则鼓励提升相联程度

Example

假设更高的相联程度会导致更高的时钟周期时间：

我们假设命中时间为 1 个时钟周期，缺失损失为 25 个时钟周期，缺失率如下：

那么多大的缓存大小能分别使得下列选项为正确？

Answer

例如，对于一个 512KB，8 相联的缓存来说，平均内存访问时间为：

\[ \text{Average Memory Access Time} = 1.52\times 1 + 0.6\% \times 25 = 1.66\text{ clock cycles} \]

Multilevel Caches¶

引入多级缓存的概念，我们既可以让高速缓存的速度变得更快，以跟上处理器的速度；也可以让高速缓存变得更大，以克服处理器和内存之间不断变宽的鸿沟

我们先考虑最简单的情况——两级高速缓存：

第一级高速缓存（以下简称 L1）可以足够小，以跟上处理器的时钟周期
- 所以 L1 的速度将影响处理器的时钟频率
第二级高速缓存（以下简称 L2）可以足够大，以捕获更多对内存的访问
- 所以 L2 的速度仅对 L1 的缺失损失有影响
- 如果 L2 不够大的话，反而会增加缺失率

引入多级高速缓存后，平均内存访问时间的计算公式变成了：

\[ \begin{aligned} \text{Average Memory Access Time}=\text{Hit Time}_{L1}+\text{Miss Rate}_{L1}\\ \times(\text{Hit Time}_{L2}+\text{Miss Rate}_{L2}\times\text{Miss Penalty}_{L2}) \end{aligned} \]

我们还有每条指令平均内存停顿时间（Stalls）的计算公式：

\[ \begin{aligned} \text{Average Mem Stalls per Instruction} = \text{Misses per Instruction}_{L1} \times \text{Hit Time}_{L2}\\ + \text{Misses per Instruction}_{L2} \times \text{Miss Penalty}_{L2} \end{aligned} \]

为了消除歧义，有必要在这里对“缺失率”做进一步的阐述：

局部缺失率（Local Miss Rate）= 在某个高速缓存的缺失次数 / 在该高速缓存中总的存储器访问次数
- L1 和 L2 的局部缺失率分别为 \(\text{Miss Rate}_{L1},\text{Miss Rate}_{L2}\)
全局缺失率（Global Miss Rate) = 在某个高速缓存的缺失次数 / 来自处理器的总的存储器访问次数
- L1 和 L2 的全局缺失率分别为 \(\text{Miss Rate}_{L1},\text{Miss Rate}_{L1}\times\text{Miss Rate}_{L2}\)

对于一个二级缓存来说，有两种特殊的情况：

多级包含（Multilevel Inclusion）：
- L1 的数据始终存在于 L2 中
- 仅针对 L2 缓存来简化一致性检查
多级排斥（Multilevel Exclusion）：
- L2 略大于 L1
- L1 中的数据不会存在于 L2 中
- L1 未命中会导致 L1 和 L2 之间进行数据块交换

Example

假设有 1000 次存储器访问，在 L1 中有 40 次缺失，L2 中有 20 次缺失，L2 的缺失损失为 200 个时钟周期，L2 的命中时间为 10 个时钟周期，L1 的命中时间为 1 个时钟周期，每条指令需要 1.5 次存储器访问，那么：

计算 L1 和 L2 的缺失率
计算平均内存访问时间
计算每条指令平均内存停顿时间

Answer

Answer 1Answer 2Answer 3

L1 的全局缺失率与局部缺失率相同，都为 \(\frac{40}{1000}=4\%\)
L2 的全局缺失率为 \(\frac{20}{1000}=2\%\)
L2 的局部缺失率为 \(\frac{20}{40}=50\%\)

平均内存访问时间为 \(1+4\%\times(10+50\%\times 200)=1+4\%\times(10+100)=5.4\) 个时钟周期

每条指令平均内存停顿时间为 \((1.5\times\frac{40}{1000})\times 10+(1.5\times\frac{20}{1000}\times 200=6.6\) 个时钟周期

Prioritize Read Misses Over Writes¶

减小缺失率
并不是简单地在遇到读取缺失时等待，直到写缓冲区里没有东西为止，而是在读取缺失时检查写缓冲区的内容，如果没有冲突且存储器系统可用的话，那么就让读取缺失继续下去，这样便让读取操作的优先级高于写入操作

Avoid Address Translation During Indexing Cache¶

高速缓存需要完成从虚拟地址到物理地址的转换

为了加速大概率事件，高速缓存会用到虚拟地址，因为这样会提高命中率，而这样的高速缓存称为虚拟高速缓存（Virtual Caches）（对应传统意义上使用物理地址的物理高速缓存（Physical Caches））

在高速缓存中，我们需要区分两件事：索引高速缓存（即找到对应的组）和比较地址（的标签位）。那么，虚拟地址和物理地址更适合完成这两项任务中的哪一个呢？假如对于索引和标签，全部使用虚拟地址，这样就消除了转换所需的时间。事实上很少会这样做，这是因为：

考虑到虚拟地址转换为物理地址时的页级保护机制
- 通过在缺失时拷贝 TLB 上的保护信息，并用一个字段来保存这个信息，并且在每次访问虚拟高速缓存时进行检查来克服这个问题
每当切换进程时，虚拟地址就会指向不同的物理地址，需要对高速缓存进行清除操作
- 通过增加地址标签位的宽度，作为进程标识符标签（Process-Identifier Tag, PID）使用来解决这个问题。如果操作系统为进程赋予这些标签的话，它只需要清除那些 PID（用于区分高速缓存中的数据是否用于该程序）被回收的标签，避免过多的清除操作，从而降低缺失率：
操作系统和用户程序可能使用两个不同的虚拟地址来指代同一个物理地址
- 这些重复的地址称为同义词（Synonyms）或别名（Aliases）
- 硬件层面上，解决此问题的方法是反别名（Antialiasing）：确保每个高速缓存数据块对应唯一的一个物理地址
- 软件层面上，解决此问题的方法是强迫这些别名共享一些地址位，这种限制称为页着色（Page Coloring），可以看作是组相联在虚拟内存中的应用。该方法能有效提升页偏移量，因为它保证了虚拟地址和物理地址最后的某些位是相同的
I/O 设备

一种可以同时利用虚拟高速缓存和物理高速缓存优势的方法是：使用虚拟地址和物理地址中页偏移量相同的那部分来索引高速缓存，同时在使用该索引读取高速缓存的时候，转换地址的虚拟部分，并且用标签匹配物理地址。该方法实现了立即读取高速缓存的数据，并且仍然使用物理地址进行比较。这种方法称为虚拟索引，物理标签（Virtually Indexed, Physically Tagged）

下图展示了从虚拟地址到 L2 高速缓存访问的存储器层级原理图：

Advanced Optimizations¶

在高级优化方法中，我们除了考虑平均内存访问时间公式中的三个因素外，还要考虑高速缓存的带宽和功耗问题

根据上面提到的 5 个因素，我们将高级的优化方法分个类：

减少命中时间：小而简单的一级高速缓存，路预测（Way-Prediction）。这两种方法还能降低功率。
增加高速缓存带宽：流水线高速缓存（Pipelined Caches），多分区高速缓存 (multibanked caches)。这两种方法对功率的影响视具体情况而定
减少缺失损失：关键字优先，合并写缓冲区。这两种方法略微提升功率
减少缺失率：编译器优化。任何在编译时的提升能够降低功率
通过并行减少缺失损失或缺失率：硬件预取，编译器预取。这两种方法都会提升功率，很可能是因为预取的数据没有被用到

Small and Simple First-Level Caches¶

减小一级高速缓存（以下简称 L1）的大小，或者降低 L1 的相联程度都有助于减小命中时间和功耗

减小一级缓存的大小可以支持更快的时钟周期，从而降低功耗
降低 L1 的相联程度由于一个组中只有一个数据块，所以可以将标签检查和传输数据并在一块，减少命中时间和功耗

下面的两张图展现了相联程度对命中时间和功耗的影响：

Way Prediction¶

路预测（Way-Prediction）：在高速缓存中保留额外的位（称为数据块预测位，Block Predictor Bit），用于预测下一次可能被访问的数据块。

如果预测正确，高速缓存的访问时延就是很快的命中时间
如果预测失败，那么就要尝试下一个数据块，改变预测者的内容，并且会有一个额外的时钟周期时延

路预测多用于多路组相联的高速缓存中

Pipelined Access and Multibanked Caches¶

使高速缓存访问流水线化以及采用多个分区（Banks）加宽高速缓存都能提升高速缓存的带宽。这些优化方法主要针对的是 L1，因为它的访问带宽会限制指令的吞吐量。但多个分区的做法同样可以用于 L2 和 L3 高速缓存中，但主要作为功率管理技术

使高速缓存访问流水线化：带来更高的时钟周期数，代价是提升了时延
- 使指令高速缓存流水线化可以有效提升流水线 CPU 的阶段数量，但这样会导致更大的分支预测错误损失
- 使数据高速缓存流水线化可以在发射加载指令和使用数据之间增加更多的时钟周期数
- 指令高速缓存的流水线化相比数据高速缓存更为简单
采用多个分区加宽高速缓存：高速缓存被分为独立的分区，每个分区支持独立的访问
- 当访问在这些分区中平均分布时，这种方法的表现最好，因此如何将地址映射到分区会影响到存储器系统的行为
- 一种简单的映射方法是按顺序将地址平均分配给每个分区，这样的方法称为顺序交错（Sequential Interleaving）
Nonblocking Caches¶

乱序执行的流水线 CPU 不会在数据高速缓存缺失时停顿，比如它在等待获取缺失数据的同时还能继续从指令高速缓存中获取指令。而非阻塞的高速缓存（Nonblocking Caches）允许数据高速缓存在缺失发生时继续提供命中，从而发挥出乱序流水线 CPU 的潜在优势。这种 "Hit Under Miss" 的优化方法能够降低缺失损失

一种更复杂，但能进一步降低缺失损失的方法是 "Hit Under Multiple miss" 或 "Miss Under Miss"，即将多个缺失重叠在一起

Example

假设有一个 32KiB 的 L1 缓存，它到 L2 的缺失损失为 10 个时钟周期，L2 的缺失损失也为 10 个时钟周期，缺失率如下表所示：

那么使用两路组相联还是使用“Hit Under Miss”的方法能提高更多？

Answer

对于整数来说：

\[ \begin{aligned} \text{Miss Time}=\text{Miss Rate}_{\text{DM}}\times\text{Miss Penalty}=3.5\%\times 10=0.35\\ \text{Miss Time}=\text{Miss Rate}_{\text{2-way}}\times\text{Miss Penalty}=3.2\%\times 10=0.32\\ \end{aligned} \]

因此对于两路组相联来说提高了 \(\frac{0.03}{0.35}=9\%\)，而根据下面的图，Hit Under Miss 的提升也为 \(9\%\)

对于浮点数来说：

\[ \begin{aligned} \text{Miss Time}=\text{Miss Rate}_{\text{DM}}\times\text{Miss Penalty}=5.2\%\times 10=0.52\\ \text{Miss Time}=\text{Miss Rate}_{\text{2-way}}\times\text{Miss Penalty}=4.9\%\times 10=0.49\\ \end{aligned} \]

因此对于两路组相联来说提高了 \(\frac{0.03}{0.52}=6\%\)，而根据上图，Hit Under Miss 的提升为 \(12.5\%\)，所以使用“Hit Under Miss”方法更好

Critical Word First and Early Restart¶

关键字优先（Critical Word First）：从内存中请求缺失的字数据，一旦获取数据后便立即发送给处理器，并让处理器在填充数据块剩余字数据的同时继续执行指令
早启动（Early Restart）：按正常顺序获取字数据，但一旦获取到所需的字数据，就将其发送给处理器并让处理器继续执行指令

这两种优化方法仅在高速缓存数据块较大的情况下有明显的好处。它们带来的好处还取决于访问数据块中未获取的部分的可能性

Merging Write Buffer¶

合并写缓冲区（Merging Write Buffer）：在写入数据时，允许将多个写入操作合并成一个操作，这样可以减少内存访问的次数

如果写缓冲区是空的，那么数据和完整的地址都会被写入到缓冲区中
如果缓冲区包含一些被修改的数据块，那么就要检查一下地址，看这些新数据的地址是否与某个有效的写缓冲区项匹配，如果匹配的话，就将新数据并入到这个项里。这种优化方法称为写合并（Write Merging）
但如果写缓冲区是满的，且没有任何地址匹配，那么高速缓存（和处理器）必须等待，直到写缓冲区有一个空的项
这种优化方法能够更加高效地利用内存，因为一次写入多个字数据通常比一次写一个字数据的速度更快；并且也能减少停顿次数
下图比较了未使用写合并的写缓冲区和使用写合并的写缓冲区：

Compiler Optimizations¶

上面所介绍的都是硬件层面的优化方法，下面介绍一些软件/编译器层面的优化方法

循环交换（Loop Interchange）：通过交换内层循环和外层循环，使得访问数据的顺序更符合存储数据的顺序。这种方法通过改进空间局部性来减少缺失率

Example

假定有一个二位数组，规模为 [5000, 100]，且 x[i, j] 和 x[i, j+1] 两个元素是相邻的（行优先）。那么对于下面两个嵌套循环，更推荐使用第二个循环：

/* Before */
for (j = 0; j < 100; j++)
    for (i = 0; i < 5000; i++)
        x[i][j] = 2 * x[i][j];

/* After */
for (i = 0; i < 5000; i++)
    for (j = 0; j < 100; j++)   
        x[i][j] = 2 * x[i][j];

分块（Blocking）：将大的数组划分一块块小块（Block），通过分别解决每个小块来解决整个数组。该方法同时利用了空间和时间的局部性。典型的例子就是矩阵乘法：

Example

给定两个规模均为 \(N\times N\) 的矩阵 \(y,z\)，计算 \(x=y\times z\)

for (i = 0; i < N; i++)
    for (j = 0; j < N; j++) {
        r = 0;
        for (k = 0; k < N; k++)
            r = r + y[i][k] * z[k][j];
        x[i][j] = r;
    }

在最坏情况下，\(N^3\) 次运算需要访问 \(2N^3+N^2\) 个内存字数据

下图展示了某个时间段内矩阵的运算情况，其中深灰色表示最近访问的元素，浅灰色表示之前访问的元素，白色表示尚未访问的元素

如果高速缓存空间有限，这样做显然是不行的。所以在计算前，需要将矩阵划分为 \(B\times B\) 大小（\(B\) 称为分块因子，Blocking Factor）的子矩阵，逐个计算子矩阵乘法的结果。此时所需的内存字数据个数为 \(2\frac{N^3}{B}+N^2\)，节省了高速缓存的空间，从而减少容量失效的发生。代码为：

for (jj = 0; jj < N; jj += B)
    for (kk = 0; kk < N; kk += B)
        for (i = 0; i < N; i++)
            for (j = jj; j < min(jj + B, N); j++) {
                r = 0;
                for (k = kk; k < min(kk + B, N); k++)
                    r = r + y[i][k] * z[k][j];
                x[i][j] += r;
            }

下图展示了某个时间段内矩阵的运算情况：

Hardware Prefetching¶

另一种减小失效损失的方法是在处理器请求指令或数据之前，将这些指令或数据预取（Prefetch）出来，放在高速缓存或其他外部缓冲区内

指令预取往往是在高速缓存外进行的。通常，处理器在失效时会获取两个块，一个请求块，以及连续的下一个块。当请求块返回时，它会被放在指令高速缓存内，并且把预取块放在指令流缓冲区内。如果请求块出现在指令流缓冲区内，那么原来的高速缓存请求就会取消，这个块就会从流缓冲区中读出，并且启动下一个预取请求
相同的方法可用于数据访问中

Compiler Prefetching¶

编译器预取是编译器在需要数据之前插入预取指令获得数据，分为两种形式：

寄存器预取（Register Prefetch）：加载数据值到寄存器中
缓存预取（Cache Prefetch）：加载数据值到高速缓存中

Example

假设有如下程序：

for (i = 0; i < 3; i = i + 1)
    for (j = 0; j < 100; j = j + 1)
        a[i][j] = b[j][0] * b[j + 1][0];

如果我们的数据块为 16 字节大小，a 与 b 的元素大小为 8 字节，采用写回策略，对于 a 来说，\(a[0][0]\) 缺失，那么拷贝 \(a[0][0],a[0][1]\) 作为一整个数据块到缓存中（包含两个数据）

那么对于 a 会出现 \(3\times 100/2=150\) 次缺失，对于 b 来说，会出现 0～100 共 101 次缺失，如果我们插入预取指令：

for (j = 0; j < 100; j = j + 1){
    prefetch(b[j + 7][0]); /* 7 misses: b[0][0] - b[6][0] */
    /* b(j, 0) for 7 iterations later */
    prefetch(a[0][j + 7]); /* 4 misses: 1/2 of a[0][0] - a[0][6] */
    /* a(0, j) for 7 iterations later */
    a[0][j] = b[j][0] * b[j + 1][0];
}
for (i = 1; i < 3; i = i + 1)
    for (j = 0; j < 100; j = j + 1){
        prefetch(a[i][j + 7]); /* 8 misses: a[1][0]-a[1][6], a[2][0]-a[2][6] */
        /* a(i, j) for 7 iterations */
        a[i][j] = b[j][0] * b[j + 1][0];
    }

最后的缺失次数变为了 19 次，如果原来的循环每次迭代需要 7 个时钟周期，第一个预取循环每次迭代需要 9 个时钟周期，第二个预取循环每次迭代需要 8 个时钟周期，缓存缺失损失为 100 个时钟周期，那么优化前消耗的时钟周期数为 \(300\times 7+251\times 100=27200\text{ Cycle}\)

优化之后消耗的时钟周期数为 \(100\times 9+ 11\times 100+ 200\times 8+ 8\times 100=440\text{ Cycle}\)

HBM¶

我们使用高带宽内存（High Bandwidth Memory，HBM）作为 L4 缓存

HBM 特别用于标签（Tags）量非常大的情况
- 例如 L4 缓存大小为 1GiB，如果数据块大小为 64B，那么标签量为 96MiB；如果数据块为 4KiB，那么标签量为 1MiB
需要在每次 L4 访问时对 DRAM 进行两次访问
- 一次访问标签（转译地址），一次访问数据（标签比对）
通过加快缺失检测来减少缺失时间
- 使用一个 map 来记录数据块在缓存的位置
- 使用内存访问预测器和访问记录来预测可能的缺失情况

我们有如下优化方法：

将标签和数据放在同一行中
- 尽管这样需要很长的时间开放某一行，但是我们只需要 ⅓ 的时间来访问一个已经开放的行
- 先访问标签，如果标签命中再访问数据
合金缓存（Alloy Cache）
- 将标签和数据拼在一起
- 使用直接映射缓存结构
- 每次访问的 HBM 周期：直接索引 HBM 缓存并执行标签和数据的突发传输

Virtual Memory¶

虚拟内存（Virtual Memory）将物理内存划分为块，并且将其分配到不同的进程中。下图展示了虚拟地址到物理地址的映射情况：

Four Memory Hierarchy Questions¶

怎么样来放置数据块？——全相联
- 理由：虚拟内存的缺失损失相当相当大（数百万个时钟周期数），因此需要尽可能地降低缺失率，而全相联的缺失率最低
如何找到数据块——通过页 / 段编号来索引对应的页 / 段
- 通常使用页表（Page Table）这一数据结构来存储虚拟内存数据块的物理地址（段的话还要存储偏移量），作为虚拟地址转换为物理地址的参照依据
- 访问内存两次：一次访问 PTE（Page Table Entry）地址，一次使用物理地址来访问数据
- 如果 vpn->ppn 没有找到（Valid Bit），那么就造成了页缺失（Page Fault），这就需要从磁盘中读取数据到内存中，更新页表
- 页表的大小就是虚拟地址空间中的页数量。有些计算机为了减小这一数据结构大小，会对虚拟地址采用哈希函数，使得其大小等于内存中物理页的数量，这种数据结构称为逆页表（Inversed Page Table）
- 如何替换数据块——LRU
- 具体会用到一个使用位 / 引用位（Use/Reference Bit）。操作系统会周期性地清除使用位，随后又添上去，这样便可以记录一段时间内页的访问情况。
- 写入策略用什么——写回
- 理由：内存和处理器访问时间的巨大差异，所以不可能使用写穿策略
- 虚拟内存系统用到 1 个脏位（Dirty Bit），允许数据块在因从硬盘读取而被改变的时候写入到硬盘中
Address Translation¶

由于页表很大，所以一般被存在内存中，甚至有时候页表自己也要分页。而分页意味着逻辑上内存访问需要分两步走：首先需要找到物理地址，然后再根据物理地址找找到数据。为了避免额外的内存访问，我们可以借助局部性原则，将部分地址的翻译保留到一个特殊的缓存中，这样的缓存就是我们熟知的 TLB

TLB 的结构类似高速缓存：它的标签位用于保存虚拟地址，而数据位用于保存物理页编号，保护字段，合法位，以及可能的使用位和脏位

如果要改变页表中的物理页编号和保护信息，那么操作系统必须将 TLB 中的对应部分给清掉。
这里的“脏位”表示对应的页是不是“脏”的，而不是表示 TLB 中的地址翻译或数据缓存的特定的数据块是不是脏的。
操作系统通过改变页表中的值，以及使 TLB 中对应的项无效化来实现对这些位的重置

下图展示了在地址转换中，TLB 内发生的操作：

Page Size¶

在以下情况，我们倾向于使用更大的页：

由于页表的大小和页的大小成反比，因此内存（或其他存储页表的资源）可以通过增大页的大小来节省空间
更大的页可以使用更大的高速缓存，以达到更快的命中时间
在二级存储器，或者在网络中传输更大的页，相比传输更小的页更有效
更大的页意味着更多的内存能被有效映射，因此减少了 TLB 缺失的情况

而当需要保留存储空间，或者希望启动进程的速度更快时，我们更倾向于使用更小的页

当然，我们也可以两者都取，即采用多种页面大小，当下的微处理器已经支持多个页面大小
- 对于某些程序，TLB 未命中对 CPI 的影响可能与高速缓存未命中一样重要

Chapter 02 : Memory Hierarchy Design¶

Main Memory¶

SRAM¶

DRAM¶

DRAM Improvements¶

GDRAM¶

Stacked / Embedded DRAM¶

Flash Memory¶

Phase-Change Memory¶

Memory Dependability¶

Cache¶

Cache Performance¶

Basic Optimizations¶

Larger Block Size¶

Larger Cache¶

Higher Associativity¶

Multilevel Caches¶

Prioritize Read Misses Over Writes¶

Avoid Address Translation During Indexing Cache¶

Advanced Optimizations¶

Small and Simple First-Level Caches¶

Way Prediction¶

Pipelined Access and Multibanked Caches¶

Nonblocking Caches¶

Critical Word First and Early Restart¶

Merging Write Buffer¶

Compiler Optimizations¶

Hardware Prefetching¶

Compiler Prefetching¶

HBM¶

Virtual Memory¶

Four Memory Hierarchy Questions¶

Address Translation¶

Page Size¶

评论