微处理器设计/缓存

微处理器设计

缓存

缓存是一小部分内存，其运行速度快于主内存。数据从主内存移动到缓存，以便可以更快地访问它。现代芯片设计人员将多个缓存放在与处理器相同的芯片上；设计人员通常分配给缓存的芯片面积大于 CPU 本身。提高芯片性能通常是通过提高芯片缓存的速度和效率来实现的。

缓存内存性能是实现高处理器性能的最重要因素。

缓存的工作原理是存储外部内存内容的一个小子集，通常是按其原始顺序存储的。经常使用的数据和指令（例如数据数组或小型指令循环）存储在缓存中，并且可以快速读取，而无需访问主内存。缓存以与处理器其余部分相同的速度运行，这通常比外部 RAM 的运行速度快得多。这意味着如果数据在缓存中，则访问它的速度比访问内存快。

缓存有助于加快处理器的速度，因为它基于局部性原理。

在本章中，我们将讨论几种可能的缓存安排，按复杂度递增的顺序

• 无缓存，单 CPU，物理寻址
• 单级缓存，单 CPU，物理寻址
• 缓存层次结构：L1、L2、L3 等。
• 缓存替换策略：关联性、随机替换、LRU 等。
• 分体缓存：I 缓存和 D 缓存，位于统一缓存层次结构之上
• 使用多个 CPU 进行缓存
• 支持虚拟内存寻址的缓存硬件
• TLB 作为一种缓存
• 单地址空间虚拟内存寻址如何与缓存硬件交互
• 每个进程的虚拟内存寻址如何与缓存硬件交互

无缓存

如今的大多数处理器，例如标准键盘和鼠标内部的处理器，都没有任何缓存。许多历史上重要的计算机，例如 Cray 超级计算机，也没有任何缓存。绝大多数软件既不知道也不关心缓存的具体细节，或者是否存在缓存。

没有缓存的处理器通常受主内存访问时间的限制。如果没有缓存，处理器会一次从主内存中获取每个指令，并且每个 LOAD 或 STORE 都会在执行下一条指令之前转到主内存。

提高性能的一种方法是替换更快的主内存。唉，这通常具有财务限制：几乎没有人愿意为 1GB 的真正快速的内存支付一分钱。

即使金钱不是问题，最终也会达到主内存访问时间的物理限制。即使使用金钱可以买到的最快内存，统一 1GB 主内存的内存访问时间也受到信号从 CPU 传播到内存最远端并返回所需时间的限制。

单级缓存

使用完全相同的技术，信号遍历一小块内存所需的时间比遍历一大块内存所需的时间少。

带有缓存的处理器的性能不再受主内存访问时间的限制。带有缓存的处理器的性能通常受（快得多的）缓存内存访问时间的限制：如果可以减少处理器的缓存访问时间，则处理器的性能会更高。但是，缓存内存通常比主内存更容易加速：当我们只购买少量内存时，真正快速的内存要便宜得多。如果它会显着提高系统的性能，那么很多人愿意为 1KB 的真正快速的缓存内存支付一分钱。

局部性原理

局部性有两种类型，空间和时间。现代计算机程序通常是基于循环的，因此我们有两个关于局部性的规则

空间局部性

当访问数据项时，很可能还会访问顺序内存位置中的数据项。考虑数组的遍历或在栈上存储局部变量的操作。在这些情况下，当访问一个数据项时，最好同时将周围的内存区域加载到缓存中。

时间局部性

当访问数据项时，很可能再次访问相同的数据项。例如，变量通常会快速连续地读取和写入。最好将最近使用过的项目保留在缓存中，并且不要覆盖最近使用过的数据。

命中或未命中

在谈论缓存时，命中是指处理器在缓存中找到它正在查找的数据。未命中是指处理器在缓存中查找数据，但数据不可用。如果发生未命中，缓存控制器单元必须从主内存中收集数据，这可能会花费处理器更多时间。

“命中率”的测量通常是在基准应用程序上执行的。实际的命中率因应用程序而异。特别是，视频和音频流应用程序的命中率通常接近于零，因为流中的每一位数据都会第一次读取（强制未命中），使用，然后不再读取或写入。更糟糕的是，许多缓存算法（特别是 LRU）允许此流数据填充缓存，从而将很快再次使用的信息从缓存中推出（缓存污染）。

缓存性能

带有缓存的处理器首先会在缓存中查找数据（或指令）。如果未命中，处理器就会从主内存中获取数据（或指令）。如果未命中，这个过程会比没有缓存的同等处理器花费 *更长* 的时间。

缓存比没有缓存的处理器提供更好的净性能，主要有三种方式。

• 命中（从缓存读取）的速度比没有缓存的处理器从主内存中获取数据所需的时间快。关键在于设计缓存，使其能够经常命中，从而其性能提升能够弥补偶尔未命中导致的性能下降。（这需要缓存的速度快于主内存）。
• 具有共享主内存的多处理器计算机，在访问主内存时经常会出现瓶颈。当本地缓存成功地满足内存操作而无需一直访问主内存时，主内存带宽就会释放出来供其他处理器使用，并且本地处理器无需等待其他处理器完成其内存操作。
• 许多系统的设计使得处理器能够经常同时从缓存中读取多个项目——无论是用于指令、数据和 TLB 的 3 个独立缓存；还是多端口缓存；或两者兼而有之——这比一次从主内存中读取相同项目花费的时间少。

即使缓存的速度不快于主内存，最后两种方式也能提高整体性能。

没有缓存的处理器的内存引用时间 T 为常数

$T=T_{m}+E$

带有缓存的处理器的平均内存访问时间为

$T=mT_{m}+T_{h}+E$

其中

• m 是未命中率
• T_m 是进行主内存引用的时间
• T_h 是在命中时进行缓存引用的时间
• E 考虑各种次要因素（内存刷新时间、多处理器争用等）

刷新缓存

当处理器需要数据时，它会在缓存中查找。如果数据不在缓存中，它就会去内存中查找数据。来自内存的数据会被移动到缓存中，然后由处理器使用。有时整个缓存包含无用或旧数据，需要将其 **刷新**。当缓存控制器确定缓存包含的潜在未命中次数多于命中次数时，就会发生刷新。刷新缓存需要几个处理器周期，因此很多研究都集中在开发用于保持缓存更新的算法上。

缓存层次结构

缓存通常划分为多个级别。最常见的级别是 L1、L2 和 L3。L1 最小但最快。L3 最大但最慢。许多芯片没有 L3 缓存。一些确实具有 L3 缓存的芯片实际上具有一个外部 L3 模块，该模块位于主板上的微处理器和 RAM 之间。

包含、独占和其他缓存层次结构

当存在多个缓存级别，并且主内存中某个位置的数据已缓存在 L1 缓存中时，L2 缓存中是否还有该数据的副本？

• 否。某些系统设计为具有严格的独占缓存级别：主内存中的任何特定位置最多缓存在一个缓存级别中。

• 是。其他系统设计为具有严格的包含缓存级别：只要主内存中的某个位置缓存在任何一个级别中，该位置也会缓存在所有更高级别中。L2 缓存中的所有数据也都可以 found 在 L3 中（以及主内存中）。

L1 缓存中的所有数据也可以在 L2 和 L3 中 found（以及主内存中）。

• 可能。在某些系统中，例如 Intel Pentium 4，L1 缓存中的一些数据也在 L2 缓存中，而 L1 缓存中的其他数据则不在 L2 缓存中。这种缓存策略还没有流行的名称。

缓存大小

奔腾 Pro 芯片是有史以来制造的最大微处理器之一。它之所以如此之大，是因为它包含当时任何芯片中最大的缓存。

影响芯片上缓存大小的因素有很多。

1. 摩尔定律使得每个芯片上的晶体管数量不断增加。大约在 1989 年之后，每个芯片上可用的晶体管数量超过了设计人员用于制造 CPU 的数量。这些额外的晶体管很容易转换为大型缓存。
2. 随着晶体管尺寸的减小，处理器组件的尺寸也随之减小。这意味着芯片上有更多空间用于添加缓存。
3. 更多的缓存意味着访问数据的延迟更少，因此性能更好。

由于这些因素，芯片缓存的趋势是每一代芯片都越来越大。

缓存标记

缓存可以包含没有特定顺序的非连续数据项。缓存中的内存块可能是空的，根本不包含任何数据。为了使硬件能够检查缓存中条目的有效性，每个缓存条目都需要维护以下信息

1. 一个状态位，用于确定块是空还是满
2. 块中数据的内存地址
3. 指定内存地址中的数据（缓存中的“块”，也称为缓存中的“行”）

当处理器在缓存中查找数据时，它会将内存地址发送到缓存控制器。缓存控制器会将该地址与缓存中所有地址字段进行比较。如果命中，缓存控制器会返回数据。如果未命中，缓存控制器必须将请求传递到下一级缓存或主内存单元。

缓存控制器将有效内存地址（MSB 到 LSB）拆分为标记、索引和块偏移。 一些作者将块偏移简单地称为“偏移” 或“位移”。

显示非连续数据的缓存示意图

缓存中数据的内存地址称为 **标记**。

内存停顿周期

如果缓存未命中，处理器将需要停顿当前指令，直到缓存能够从更高级别获取正确的数据。停顿导致的时间损失取决于许多因素。特定程序中的内存访问次数表示为 A_m；其中一些访问将命中缓存，其余的将未命中缓存。未命中率等于任何特定访问未命中的概率，表示为 r_m。每次未命中导致的平均时间损失称为未命中惩罚，表示为 P_m。我们可以计算因缓存未命中停顿而浪费的时间为

${\mbox{停顿时间}}=A_{m}\times r_{m}\times P_{m}$

同样地，如果我们知道程序中指令的总数 *N*，以及每条指令的平均缺失次数 *MPI*，我们可以计算出损失的时间为：

${\mbox{停顿时间}}=N\times MPI\times P_{m}$

如果我们用损失的周期数来衡量缺失惩罚，而不是损失的时间，那么计算结果将是由于内存停顿而损失的周期数，而不是损失的时间。

读取停顿时间

为了计算由于缓存读取缺失而损失的时间，我们可以执行与上面相同的基本计算。

${\mbox{读取停顿时间}}=A_{r}\times r_{r}\times P_{r}$

*A_r* 是平均读取访问次数，*r_r* 是读取操作的缺失率，*P_r* 是与读取缺失相关的延迟时间或周期数。

写入停顿时间

确定由于写入停顿而损失的时间类似，但需要包含一个额外的加性项，表示写入缓冲区的停顿。

${\mbox{写入停顿时间}}=A_{w}\times r_{w}\times P_{w}+T_{wb}$

其中 *T_wb* 是由于写入缓冲区停顿而损失的时间。当缓存尝试与主存同步时，写入缓冲区可能会停顿。

层次结构停顿时间

在分层缓存系统中，当数据在多个缓存级别中缺失时，缺失惩罚可能会叠加。如果数据在 L1 缓存中缺失，则将在 L2 缓存中查找。但是，如果它也在 L2 缓存中缺失，则将产生双重惩罚。L2 需要从主存（或 L3 缓存，如果系统有 L3 缓存）加载数据，然后将数据加载到 L1。请注意，在两个缓存级别中缺失然后访问主存所需的时间比直接访问内存所需的时间更长。

设计考虑因素

L1 缓存通常旨在最大程度地减少命中所需的时间。如果命中时间足够快，则可以接受相当大的缺失率。L1 中的缺失将重定向到 L2，这仍然比访问主存快得多。L1 缓存往往具有较小的块大小，但在相同空间内可以受益于更多可用的块。为了使 L1 命中时间最小化，L1 通常采用直接映射或甚至狭义的 2 路组相联方式。

另一方面，L2 缓存需要具有较低的缺失率以帮助避免访问主存。访问 L2 缓存的速度比访问内存快得多，因此我们应该尽一切努力确保最大化命中率。出于这个原因，L2 缓存往往采用全相联方式并具有较大的块大小。这是因为内存通常按顺序内存单元读取和写入，因此较大的块大小可以利用这种顺序性。

L3 缓存进一步延续了这一趋势，具有更大的块大小和更低的缺失率。

块大小

非常小的缓存块大小会增加缺失率，因为缺失将每次获取较少的数据。非常大的缓存块大小也会增加缺失率，因为它会导致系统获取大量额外信息，而这些信息的使用频率低于它在缓存中取代的数据。

相联性

为了提高缓存的读取速度，许多缓存设计人员实现了一定程度的**相联性**。相联缓存在原始内存位置和存储该数据的缓存位置之间建立了一种关系。主存地址与数据存储位置之间的关系称为缓存的**映射**。这样，如果数据确实存在于缓存中，则缓存控制器知道它只能位于满足映射的特定位置。

直接映射

直接映射系统使用哈希算法为内存地址分配标识符。此目的的常用哈希算法是模运算。模运算将地址除以某个数 *p*，并将余数 *r* 作为结果。如果 *a* 是主存地址，*n* 是任意非负整数，则哈希算法必须满足以下等式

$a=p\times n+r$

如果设计人员正确选择了 *p*，则数据将均匀分布在整个缓存中。

在直接映射系统中，每个内存地址仅对应一个缓存位置，但单个缓存位置可以对应多个内存位置。上图显示了一个简单的缓存图，其中包含 8 个块。因此，所有内存地址都计算为 *n mod 8*，其中 *n* 是要读入缓存的内存地址。内存地址 0、8 和 16 都将映射到缓存中的块 0。当具有相同哈希值的多个数据项被读取时，缓存性能最差，而当数据项在内存中彼此靠近时（例如程序指令的顺序块或顺序数组），缓存性能最佳。

大多数外部缓存（位于主板上，但位于 CPU 外部）采用直接映射或偶尔采用 2 路组相联方式，因为用标准组件构建更高相联性的缓存很复杂。 如果存在这样的缓存，则通常主板上只有一个外部缓存，由所有 CPU 共享。

直接映射缓存的替换策略是最简单的替换策略：新数据必须进入它对应的一个且仅一个缓存位置。（如果缓存中该位置的旧数据的脏位已设置，则必须首先将其写入主存）。

2 路组相联

在2路组相联缓存系统中，数据值会被哈希，但每个哈希值对应一组缓存块。每个块包含多个数据单元，分配给该块的数据值可以插入到块中的任何位置。读取速度很快，因为缓存控制器可以立即将搜索范围缩小到与地址哈希值匹配的块。

2路组相联缓存的LRU替换策略是最简单的替换策略之一：新数据必须放在2个可能位置之一。这两个位置共享一个LRU位，每当读取或写入其中一个时都会更新该位，指示该组中的两个条目中哪个是最近最少使用的。新数据将放入*另一个*位置（最近最少使用的位置）。（如果缓存中该LRU位置的旧数据其脏位被设置，则必须先将其写入主内存）。

2路倾斜关联

2路倾斜关联缓存是“对于……大小在4K-8K字节范围内的缓存的最佳折衷方案”——André SeznecAndré Seznec. “支持双向倾斜关联缓存的案例”. 检索于 2007-12-13.

全相联

在全相联缓存中，不使用哈希算法，数据可以插入到缓存中任何可用位置。一个典型的算法会将新的数据值覆盖缓存中最早未使用的值。然而，此方案需要存储加载或访问项的时间，这可能需要大量的额外存储空间。

缓存未命中

缓存中主要有三种类型的未命中

1. 冲突未命中
2. 强制未命中
3. 容量未命中

冲突未命中

当两个数据项映射到同一个缓存位置时，在直接映射和2路组相联缓存中会发生冲突未命中。在数据未命中时，最近使用的数据项会被新数据项覆盖。

强制未命中

上图显示了冲突未命中和强制未命中之间的区别。强制未命中是指缓存必须未命中因为它不包含任何数据的情况。例如，当处理器第一次通电时，缓存中没有有效数据，前几次读取总是会未命中。

强制未命中演示了缓存需要区分空闲空间和已用空间的必要性。考虑当我们打开处理器并重置所有地址值到零时，尝试读取哈希值为零的内存位置将命中。如果块为空，我们不希望缓存命中。

容量未命中

当缓存块不足以容纳数据项时，会发生容量未命中。

缓存写策略

数据写入需要与数据读取相同的时间延迟。出于这个原因，缓存系统通常也会将数据写入缓存。但是，写入缓存时，务必确保数据也写入主内存，以免被下一次缓存读取覆盖。如果缓存中的数据在未存储到主内存的情况下被覆盖，则数据将丢失。

缓存必须将数据写入主内存，但何时将数据写入主内存称为写策略。有两种写策略：写通和写回。

写入操作在主内存中执行的时间与读取操作一样长。因此，许多带缓存的处理器除了执行读取操作外，还会执行写入缓存的操作。

写通

当数据写入内存时，写入请求会同时发送到主内存和缓存。这样，结果数据可以在写入（然后从主内存再次读取）之前在缓存中可用。写入缓存时，务必确保主内存和缓存同步，并且它们包含相同的数据。

在写通系统中，写入缓存的数据也会立即写入主内存。如果许多写入需要按顺序指令发生，写缓冲区可能会积压并导致停顿。

写回

在写回系统中，缓存控制器会跟踪哪些数据项已与主内存同步。未同步的数据项称为“脏数据”，缓存控制器会防止脏数据被覆盖。

缓存控制器将在处理器周期中同步数据，在这些周期中没有其他数据被写入缓存。

写旁路

某些处理器会将写入直接发送到主内存，绕过缓存。如果该位置*尚未*被缓存，则无需执行任何其他操作。如果该位置*已*被缓存，则缓存中的旧数据需要标记为“无效”（“陈旧”），因此如果CPU读取该位置，CPU将读取主内存中的最新值，而不是缓存中的某些早期值。

陈旧数据

主内存中的数据可能会被微控制器之外的组件更改。例如，许多计算机系统具有内存映射I/O或可以更改数据的DMA控制器。某些计算机系统具有连接到公共主内存的多个CPU。缓存控制器必须检查缓存中的数据是否正确。缓存中旧且可能不正确的数据称为“陈旧数据”。

处理陈旧数据（“缓存一致性协议”）的三种最流行方法是

• 使用忽略其他CPU正在做什么的简单缓存硬件。
• 将所有缓存设置为写通所有存储（写通策略）。使用额外的缓存硬件在其他设备写入主内存时侦听（“嗅探”），并在其他设备写入主内存中相应缓存位置时使本地缓存行无效。

• 设计缓存以使用MESI协议。

对于忽略其他CPU正在做什么的简单缓存硬件，缓存一致性由操作系统软件维护。操作系统将内存中的每个页面设置为（a）仅供一个特定CPU独占使用（该CPU被允许读取、写入和缓存它）；所有其他CPU都不允许读取、写入或缓存该页面；（b）在CPU之间共享读取/写入，并设置为“不可缓存”，与内存映射I/O设备设置为不可缓存的方式相同；或（c）共享只读；所有CPU都被允许缓存但不能写入该页面。

分离缓存

高性能处理器总是具有2个独立的L1缓存，即指令缓存和数据缓存（I缓存和D缓存）。这种“分离缓存”与统一缓存相比具有几个优点：

• 布线简单：解码器和调度器仅连接到I缓存；寄存器和ALU以及FPU仅连接到D缓存。
• 速度：CPU可以从D缓存读取数据，同时从I缓存加载下一条指令。

多CPU系统通常为每个CPU配备单独的L1指令缓存（L1 I-cache）和L1数据缓存（L1 D-cache），每个缓存都采用直接映射方式以提高速度。

开放性问题：为了加速JVM中Java应用程序的运行（以及类似的解释器和CPU模拟器），是否可以通过使用3个独立的缓存来提高性能——一个由程序计数器PC索引的机器指令缓存、一个由虚拟机指令指针IP索引的字节码缓存，以及一个数据缓存？

另一方面，在高性能处理器中，其他级别的缓存（如果有）——L2、L3等——以及主内存——通常是统一的，尽管也有一些例外（例如Itanium 2 Montecito）。统一缓存（以及统一主内存）的优势有：

• 一些程序大部分时间都在程序的一小部分中处理大量数据。其他程序则对少量数据运行大量不同的子程序。统一缓存会自动平衡用于指令和用于数据的缓存比例——要获得与分离缓存相同的性能，需要更大的缓存。
• 当指令被写入内存时——例如操作系统从存储器加载可执行文件，或即时编译器将字节码转换为可执行代码——分离缓存需要CPU刷新并重新加载指令缓存；而统一缓存则不需要这样做。

错误检测

每个缓存行条目可能都有错误检测位。由于缓存仅保存主内存中信息的副本（写回队列除外），因此当检测到错误时，可以从主内存中重新获取所需的数据——视为一种无效缺失——并且系统可以继续运行，就像没有发生错误一样。一些计算机系统使用汉明纠错来纠正缓存“数据”字段中的单比特错误，而无需返回到主内存。

专用缓存特性

许多CPU对指令缓存和数据缓存使用完全相同的硬件。（当然，在统一缓存中，指令和数据也使用相同的硬件。冯诺依曼体系结构的革命性思想是在主内存本身中对指令和数据使用相同的硬件）。例如，Fairchild CLIPPER使用了2个相同的CAMMU芯片，一个用于指令缓存，另一个用于数据缓存。

由于各种缓存的使用方式略有不同，因此一些CPU设计人员会以不同的方式定制每个缓存。

• 一些CPU设计人员将用于分支预测的“分支历史位”放在指令缓存中。将此类信息添加到仅用于数据的缓存中没有任何意义。
• 许多指令缓存的设计方式使得处理陈旧指令的唯一方法是使整个缓存失效并重新加载。数据缓存通常设计有更细粒度的响应，并配备额外的硬件，可以仅使已过时的特定缓存行失效并重新加载。
• 虚拟到物理地址转换过程通常具有许多与其相关的专用硬件以加快速度——TLB缓存、硬件页面漫游器等。我们将在下一章虚拟内存中更详细地讨论这一点。

进一步阅读

• 并行计算和计算机集群/内存
• 可在马里兰大学：内存系统研究：“计算工件”下载的模拟器可用于衡量微处理器设计的缓存性能和功耗，而无需实际构建它。这使得探索缓存设计中涉及的各种权衡变得更加快捷和经济。（“在芯片尺寸固定的情况下，如果我牺牲一些L2缓存以使L1缓存更大，这会使整体性能更好还是更差？”“使用具有低关联性的极快周期时间缓存更好，还是使用具有较高关联性并提供更好命中率的稍慢周期时间缓存更好？”）