玻尔百科在现代计算中，一个基本的悖论主导着性能：处理器变得惊人地快，但为它们提供数据的主内存却未能跟上步伐。这个日益扩大的鸿沟，通常被称为内存墙，造成了一个关键的瓶颈，世界上最快的 CPU 可能大部分时间都在空闲，仅仅为了等待数据。我们如何解决这个问题？答案不在于单一组件，而在于一个被称为内存层次结构的复杂分层系统。本文将探讨这一基本概念，它对我们使用的几乎所有数字设备的性能都至关重要。
本文的探索将分为两个关键章节。首先，在“原理与机制”中，我们将解构内存层次结构本身。我们将研究使其发挥作用的时间局部性与空间局部性的核心思想，沿着内存金字塔从快速的寄存器到慢速的存储设备一路向下，并剖析构成其核心的高速缓存的复杂工作原理。然后，在“应用与跨学科联系”中，我们将看到这些原理的实际应用。我们将发现内存层次结构如何塑造算法设计、影响数据结构，并在并行计算中产生复杂、有时甚至是令人惊讶的效应，从而证明理解这个系统是释放真正计算能力的关键。
想象一下，你是一位在快如闪电的厨房里工作的大厨。你的双手可以以惊人的速度切菜、搅拌和装盘。但如果你的食材储存在一个街区外的仓库里呢？无论你有多快，你那高超的烹饪速度都因为等待别人取盐而完全浪费了。简而言之，这就是现代计算的核心困境。我们的处理器，即 CPU，就是这位大厨，每秒能够执行数十亿次操作。但所有数据和指令所在的主内存 DRAM，就是那个遥远的仓库。与 CPU 惊人的速度相比，访问它的速度慢得令人痛苦。
我们如何解决这个问题？我们不能把整个仓库都搬进厨房——它太大太笨重了。这个出于天才和必要性而诞生的解决方案，就是内存层次结构。它建立在一个关于工作本质的深刻观察之上：你不需要一次性拿到所有食材，只需要当前正在使用的以及接下来可能需要的那些。
内存层次结构之所以有效，是因为计算机程序就像厨师一样，是习惯的产物。它们表现出一种称为引用局部性的特性，该特性有两种形式：
时间局部性：如果一个程序访问了一块数据，它很可能在不久之后再次访问同一块数据。这就像厨师反复用勺子蘸取同一锅酱汁品尝味道。
空间局部性：如果一个程序访问了一块数据，它很可能在不久之后访问内存中位于其附近的数据。当厨师从一箱洋葱中拿出一个时，他们接下来很可能从同一个箱子里再拿一个洋葱，而不是从房间另一头拿一个菠萝。
整个内存层次结构都是对程序这种可预测的“惰性”的一次精美而复杂的赌注。通过在紧邻 CPU 的一个极小且极快的存储区域中保留少量频繁和最近使用的数据，我们可以几乎瞬间满足 CPU 的大部分请求，从而营造出整个庞大的内存仓库都像我们厨房储藏室一样快的错觉。这个小型、快速的存储区域被称为高速缓存。
内存层次结构最好用金字塔来形象化。在最顶端，最接近 CPU 处理单元的是寄存器。它们就像是砧板——是绝对最快、最小的存储设备，只存放当前纳秒内正在被积极处理的数据。
寄存器下方是高速缓存，通常分为几个级别。一级（L1）高速缓存是最小、最快的，就像炉子旁边的香料架。二级（L2）高速缓存稍大一些，速度也稍慢一些，就像一个近旁的食品储藏室。而三级（L3）高速缓存则更大、更慢，或许像一个井井有条的步入式衣帽间。每个级别都作为其上一级别的后备。这种结构是一系列权衡的结果：随着我们沿着金字塔向下远离 CPU，容量增加，每字节的成本降低，但速度却急剧下降。
高速缓存下方是巨大但迟缓的主内存（DRAM），也就是我们的主仓库。而在最底层是长期存储，如固态硬盘（SSD）或硬盘驱动器——那是深冻档案库，容量巨大但速度要慢上几个数量级。
当 CPU 需要一块数据时，它首先检查 L1 高速缓存。如果数据在那里——即缓存命中——数据只需几个周期就能送达。如果不在那里——即缓存未命中——CPU 就会被阻塞。请求被传递到 L2 高速缓存。如果在那里命中，数据被检索出来（花费稍长的时间），并被复制到 L1 高速缓存中，以预期它可能很快再次被需要（这是对时间局部性的一种利用）。如果 L2 高速缓存也未命中，请求会继续传到 L3，依此类推，如有必要，一直会传到主内存。
整个系统的性能可以通过一个强大指标来概括：平均内存访问时间（AMAT）。它是命中时间和未命中开销的加权平均值：
未命中开销是从更低、更慢的层级获取数据所需的额外时间。由于访问主内存的未命中开销非常巨大（数百个周期！），即使是很小的未命中率也会对性能造成毁灭性的影响。在许多方面，高性能计算的全部博弈都在于最小化这个 AMAT。这涉及到巧妙的工程设计，比如找到最佳的高速缓存大小，以在较低的未命中率和因更大、更复杂的高速缓存而略微增加的命中时间之间取得平衡。
那么，高速缓存到底是如何工作的呢？它不仅仅存储单个字节。为了利用空间局部性，数据以固定大小的块进行移动，这些块被称为缓存行，通常为 64 字节长。当你请求单个字节时，高速缓存会获取它所属的整个 64 字节行，赌你会很快需要相邻的字节。这是一个非常有效的赌注。
但这又带来了一个新问题：新来的缓存行应该放在哪里？如果任何内存地址都可以被缓存在任何地方，那么找到它就会很慢。如果每个内存地址只能去高速缓存中的一个特定位置（直接映射高速缓存），你又会遇到另一个问题。如果一个程序频繁地在两个恰好映射到同一个缓存位置的地址之间交替访问怎么办？它们会不断地将对方踢出缓存，导致一连串的冲突未命中，即使缓存的其余部分是空的。
优雅的解决方案是组相联。高速缓存被分成若干个“组”，一个内存地址映射到一个特定的组。然而，在该组内，数据可以被放置在少数几个“路”（例如，8 路或 16 路）中的任何一个。这提供了足够的灵活性来避免大多数这种不幸的冲突，从而在不使高速缓存过于复杂的情况下，显著减少冲突未命中。
即使采用这种设计，电子设备的物理现实也可能带来麻烦。为了提供高带宽，高速缓存通常被分成多个独立的存储体。如果 CPU 试图在同一个周期内执行两次读取，而两次读取恰好都指向同一个存储体，其中一个就必须等待，从而产生存储体冲突。这会引入微小的停顿，在数十亿次访问中累积起来，就会造成明显的性能损失。层次结构的美妙与复杂一直延伸到这些微观的交通堵塞中。
到目前为止，我们一直专注于读取数据。但写入数据也带来了一系列有趣的挑战。当 CPU 写入一个值时，会发生什么？如果数据的位置已经在高速缓存中（写命中），缓存行会被简单地更新并标记为“脏”，表示它与主内存中的内容不同。
真正的问题是在写未命中时该怎么办。最朴素的方法是写分配：在未命中时，我们首先从主内存中获取整个缓存行（一次“所有权读取”或 RFO），然后在高速缓存中修改其相关部分。但如果你的程序只是在写入一个长的、连续的数据流，比如保存一个视频文件呢？你写入一个内存块，并且不打算在短期内再次读取它。在这种情况下，从内存中获取旧数据纯属浪费。RFO 将一个 64 字节的行带入高速缓存，而你只是覆盖了其中的一部分，获取到的其余数据都未被使用。这就是带宽浪费。
对于这些情况，更智能的策略是非写分配。在写未命中时，高速缓存被完全绕过，数据被直接发送到主内存，通常通过一个小的写合并缓冲区，该缓冲区将较小的写入组合成完整的缓存行写入，以提高效率。这两种策略之间的选择取决于程序的行为。关键因素是重用距离——即在写入一个缓存行和下一次读取该行之间访问了多少其他数据。如果重用距离大于高速缓存的大小，那么该行无论如何都会被驱逐。在这种情况下，写分配策略的初始 RFO 就是完全的浪费，而非写分配会高效得多。
一个至关重要的见解是，内存层次结构不仅仅是一个被动的硬件；它是在与运行其上的软件共舞的积极参与者。一个对层次结构一无所知的算法将表现得非常糟糕。而一个了解它的算法则可以飞速运行。
典型的例子是矩阵乘法。一个针对大矩阵的朴素三层循环实现会频繁地冲击高速缓存，不断地从主内存中获取数据。它变得严重带宽受限，其速度不是由强大的 CPU 决定，而是由与 DRAM 的慢速连接决定。解决方案是缓存分块（或称为 tiling）。程序员重构算法，使其处理小的方形子矩阵，这些子矩阵的大小正好可以放入 L1 高速缓存。通过加载一个小块并在丢弃它之前对其执行所有可能的计算，该算法最大化了数据重用。这将操作从带宽受限转变为计算受限，最终释放了 CPU 这个大厨的全部威力。
这种硬件-软件合作关系一直延伸到操作系统。当你的程序从磁盘上的文件中读取数据时，操作系统并不会为每次小的读取都去访问磁盘。它在主内存中维护一个页缓存，这不过是磁盘数据的一个大规模缓存。同样的原理也适用。如果一个程序对一个巨大的 128 GB 数据集进行真正的随机读取，其工作集将远远超过 4 GB 的页缓存。结果是缓存颠簸，即每次读取都导致一次磁盘访问，并用不会被重用的数据污染了缓存。在这些情况下，精明的程序员可以使用像 [O_DIRECT](/sciencepedia/feynman/keyword/o_direct) 标志或 fadvise(POSIX_FADV_RANDOM) 提示这样的工具来告诉操作系统：“别费心为我缓存这个了；我知道我在做什么。” 这绕过了页缓存，减少了开销，并防止了宝贵的共享资源被污染。
经典的 CPU 内存金字塔并非唯一的设计。不同的计算问题需要不同的解决方案。
图形处理单元（GPU），为大规模并行而设计，拥有独特的层次结构。除了硬件管理的高速缓存外，它们还具有一个关键的、由软件管理的片上内存，称为共享内存。一个线程块可以显式地将一块数据的“瓦片”加载到这个速度极快的暂存器中，以高重用率执行复杂操作，然后将结果写回。这对于科学模拟等任务至关重要，在这些任务中，优化数据移动和管理变量的大量内存占用是首要问题。管理不善可能导致寄存器溢出——当一个线程用尽其私有寄存器并被迫使用慢速的全局内存时，会扼杀性能。
嵌入式系统，如汽车刹车系统中的控制器，优先考虑可预测性而非原始速度。高速缓存命中与未命中的可变延迟可能会在实时控制循环中引入不可接受的抖动。对于这些系统，高速缓存通常被暂存器内存（SPM）所取代或补充——这是一种快速的片上 SRAM，很像 GPU 的共享内存。由于它由软件管理，其时序是完全确定的，为关键任务提供了所需的保障。数据可以使用直接内存访问（DMA）引擎卸载到较慢的内存中，该引擎在后台工作而不会干扰 CPU。
持久性内存（PMem）代表了下一个前沿，它模糊了内存和存储之间的界限。它提供类似 DRAM 的速度，但像 SSD 一样，它是非易失性的——其内容在断电后依然存在。这就产生了一个新的挑战：CPU 高速缓存仍然是易失性的！仅仅写入数据不足以保证其持久性。数据必须被显式地从易失性的 CPU 高速缓存刷新到持久域。不同的平台提供不同的保证。一个ADR（异步 DRAM 刷新）域只保护内存控制器的缓冲区，而一个eADR（扩展 ADR）域还保护 CPU 高速缓存。程序员现在必须使用像 clwb（缓存行写回）和 sfence（存储栅栏）这样的特殊指令，来小心地将他们的数据引导过这个从易失性到持久性的边界，确保在继续操作前，关键更新是真正安全的。
从寄存器闪电般的反应速度到存储设备浩瀚而缓慢的档案库，内存层次结构是对一个基本问题的深刻而优美的解决方案。它是一个分层的、复杂的、不断演进的，基于赌注和预测的系统，是硬件和软件之间的协作，支撑着现代计算的方方面面。理解其原理就像得到了一张通往数字世界隐藏引擎室的地图。
现在我们已经探索了内存层次结构的原理，我们可以开始一段旅程，去看看这些思想在何处真正焕发生机。理解一台机器的蓝图是一回事，而亲眼目睹这种设计如何塑造世界，以一种既微妙、深刻又常常令人惊喜的方式弯曲和引导信息流，则完全是另一回事。你看，内存层次结构不仅仅是计算机工程的一个细节。它是计算世界中的一股基本力量，其影响无处不在，从最简单的算法到科学和经济学的最宏伟挑战。
我们通常被教导通过计算完成任务所需的步骤数来衡量一个算法的优雅程度。我们给它一个花哨的名字，“计算复杂度”，并使用大-表示法来讨论它的扩展性。一个需要 $n^2$ 步的算法被认为比一个需要 $n \ln(n)$ 步的算法效率低。这是一种强大而有用的思维方式，但它只讲述了故事的一半。它衡量的是思考的成本，却完全忽略了记忆的成本。
如果计算机做的最昂贵的事情不是计算本身，而是获取计算所需的数字呢？想象一个算法不是纯粹的思想序列，而是一个才华横溢、快如闪电的处理器与它那庞大而反应迟钝的内存库之间的对话。在这种观点下，从书架上取书的时间很容易超过阅读它们的时间。这就产生了第二种复杂度：I/O 复杂度，它衡量的不是操作的数量，而是在快速的“工作台”（高速缓存）和慢速的“图书馆”（主内存）之间移动的数据量。这两种复杂度可能大相径庭。一个算法可能执行很少的计算，但需要巨大的数据流量，使其“基于浮点运算”的复杂度具有欺骗性的低，而其真实的“基于 I/O”的成本却非常高。这种视角的简单转变——从计算思想到计算对话——是解锁对现实世界性能更深层次理解的关键。
让我们从一个简单的任务开始：将一个巨大的网格（或矩阵）中的所有数字相加。实现这个任务的代码看起来微不足道：一个循环嵌套在另一个循环里。外层循环沿着行向下走，内层循环沿着列横向走。很简单。但这段简单代码的性能可能会因一个看似无关紧要的细节而截然不同：数字网格在计算机线性内存中的实际布局方式。
想象一下数字是逐行存储的，我们称之为“行主序”布局。当我们的代码沿着一行移动时，它访问的是彼此相邻的内存位置。当处理器请求一行中的第一个数字时，内存系统会预判它的需求，不只发送那一个数字，而是发送一整块相邻的数字——一个“缓存行”。处理器在这行上的漫步于是变得无比惬意；每去一次慢速的主内存，它就能得到一整块有用的数字，都在快速缓存中等着它。这是利用空间局部性的一个绝佳例子。
现在，假设网格是逐列存储的（“列主序”），但我们仍然使用相同的代码，即沿着行移动。要从一行中的一个数字移动到下一个数字，计算机现在必须跳过整整一列的数据。这个步幅可能非常大。我们的程序请求的每个数字都位于一个不同的、遥远的内存区域。为第一个数字获取的那个有用的缓存行现在几乎完全无用，因为下一个需要的数字不在其中。几乎对于我们想要相加的每一个数字，我们都必须单独进行一次到主内存的慢速访问，加载一个缓存行却只使用其中的一小部分。结果是一场性能灾难。完全相同的加法次数，可能花费的时间却大相径庭，仅仅因为一种排列方式与内存层次结构“合拍”，而另一种则不然。这是我们的第一个深刻教训：我们如何组织数据与我们如何处理它同样重要。
这个教训引出了一种强大的策略。如果内存层次结构以块为单位工作，也许我们的算法也应该如此。这是缓存感知编程的核心思想，这项技术已经彻底改变了高性能计算。
考虑矩阵乘法，它是科学计算的基石。一个朴素的实现包含三个嵌套循环，这很像我们的列主序遍历，可能会有糟糕的内存访问模式。缓存感知的解决方案很优雅：我们不处理整个矩阵，而是将它们分解成更小的方形瓦片或块。我们选择一个块大小 $b$，使其足够小，以便我们在任何时刻需要处理的三个块——一个来自矩阵 ，一个来自 ，一个来自 ——都能舒适地放在我们的“工作台”——L1 高速缓存上。然后，算法就变成了一组在这些块上进行的循环。通过加载一小组块并在丢弃它们之前对其执行所有可能的计算，我们最大化了数据重用。我们从慢速内存中带来的每个数字都会被使用很多很多次，然后才需要去取另一个。这种策略被称为分块或平铺（tiling），它使我们能够将计算结构化为以矩阵-矩阵运算（三级 BLAS）为主导，这种运算具有最高的算术与数据移动比率。这不仅仅是一个技巧；这是编排数据移动的艺术，是几乎所有现代科学库速度背后的秘密成分。
但这提出了一个难题：我们如何选择块大小 $b$？它取决于高速缓存的大小 $M$，而每台机器的 $M$ 都不同。我们必须为每台计算机编写一个不同版本的代码吗？这引出了一个更美妙的想法。
如果一个算法能够对任何内存层次结构都达到最优效率，而无需知道其任何参数呢？这听起来像魔术，但它却是缓存无关算法的现实。
让我们回到矩阵乘法。我们不把矩阵分解成固定大小的块，而是使用分治法。我们将每个矩阵分成四个象限，并将原始乘法表示为对这些较小象限的八个递归乘法。递归一直持续到矩阵变得非常小为止。
现在，考虑这个算法在一台高速缓存大小为 $M$ 的机器上运行。递归将继续进行，将问题分解成越来越小的部分。在某个时刻，子问题会变得足够小，以至于它们操作的三个子矩阵能够自然地放入高速缓存中。一旦发生这种情况，该子问题的所有后续递归调用都将完全由快速缓存提供服务，不再有慢速内存访问。其美妙之处在于，这个“交叉点”是自动发生的，无论 $M$ 的值是多少。递归结构内在地创建了一种完美适应机器的分块模式。如果有多级高速缓存（L1、L2、L3），同一个递归算法会同时并隐式地为所有级别进行优化！这单一、优雅的递归策略，达到了与精心手动调优的、缓存感知的块状算法相同的渐近 I/O 效率，却无需了解其运行的硬件的任何信息。这是一个深刻的证明，展示了一个简单而强大的数学思想如何能够驾驭物理世界的复杂性。
当我们引入多个并行工作的处理器时，故事变得更加引人入胜。人们可能认为 $p$ 个处理器只会将任务加速 $p$ 倍。然而，内存层次结构引入了离奇而奇妙的效应，挑战了这种简单的直觉。
首先是不谐。想象一个算法，其中 $p$ 个线程被分配工作，每个线程更新数组中自己的私有元素：线程 0 写入 A[0]，线程 1 写入 A[1]，依此类推。在一个像 PRAM 这样的抽象模型中，内存是一个简单、统一的空间，这是一个完全并行且无干扰的任务。但在一个真实的多核处理器上，如果元素 A[0], A[1], ..., A[$p-1$] 恰好位于同一个缓存行上，我们就有问题了。当线程 0 写入 A[0] 时，其核心必须获得整个缓存行的独占所有权。当线程 1 接着尝试写入 A[1] 时，其核心必须夺取所有权，这会使线程 0 缓存中的副本失效。然后线程 2 又把它抢走，使线程 1 的副本失效。单个缓存行在所有核心之间剧烈地“乒乓”传递。我们原以为是独立的写入操作，实际上被一致性协议序列化了。这种现象被称为伪共享，它会导致程序在增加更多处理器时性能急剧下降。算法的逻辑优雅被硬件的物理现实所粉碎。解决方案通常是添加“填充”——浪费内存以确保每个线程的数据都拥有自己的私有缓存行，这感觉上是错误的，但有时为了恢复和谐却是必要的。
但这个交响乐团也能产生令人惊讶的和谐。考虑一个计算经济学问题，其工作数据集太大，无法放入单个处理器的高速缓存中。串行的单核版本运行缓慢，不断地冲击其高速缓存并等待慢速的主内存。现在，让我们在（比如说）8 个核心上并行化它，将数据在它们之间分区。如果每个核心的分区数据现在足够小，可以放入其本地高速缓存中，那么神奇的事情就发生了。这些核心不再受内存限制；它们变成了计算受限。在加载完数据的初始阶段之后，它们几乎完全在其快速缓存中工作。现在每个独立的核心都比原来的串行核心效率高得多。结果呢？8 核版本可能比 1 核版本快 10 倍。这种超线性加速，即 $S(p) > p$，似乎违反常识，但它是内存层次结构一个完全合乎逻辑且美妙的结果。我们不仅仅是划分了工作；我们从根本上改变了它的性质，从一个受通信限制的任务变成了一个受计算限制的任务。
这些原则并不仅限于奇特的科学算法，它们被编织进日常计算的方方面面。
支撑我们软件的数据结构的设计通常受到内存层次结构的指导。在构建数据库索引（如 B 树）时，可以选择树节点的大小恰好等于一个缓存行的大小。这确保了从父节点遍历到子节点尽可能高效，因为获取节点的任何部分都会将整个有用的单元带入缓存。通过这样一个树的搜索变成了一系列 D-cache（数据缓存）行填充，树的每一层对应一次，而树的高度——从而其性能——可以直接从经过缓存优化的分支因子估算出来。
操作系统，作为硬件的总指挥，深切关注一种特殊的高速缓存，称为转译后备缓冲器（TLB），它缓存从虚拟内存地址到物理内存地址的映射。TLB 未命中代价高昂，需要通过内存中的表进行“页表遍历”。操作系统可以实施策略，以确保关键例程（如处理硬件中断的例程）的地址映射在为页表遍历器服务的高速缓存中保持“热”状态。这减少了关键操作的延迟，并使整个系统响应更快。
最后，编译器，我们代码的沉默翻译者，是内存层次结构管理的无名英雄。它执行寄存器分配这一复杂任务，试图将最常用的变量保留在处理器微小、超快的寄存器中。当寄存器用尽时，它必须将一个变量“溢出”到主内存的栈上。编译器知道获取这个溢出变量的成本不是一个固定数字。它是一个期望值，一次概率之旅。该变量可能在 L1 缓存中，也可能在 L2 中，或者可能需要一次漫长而昂贵的、一直到 DRAM 的旅程。编译器的决策是一场复杂的赌博，权衡着由整个内存系统定义的成本和概率。
从单个数组的布局到并行超级计算机的宏伟战略，内存层次结构是引导性能的无形之手。忽视它，就会任由难以捉摸的硬件效应摆布。但理解它，就能在掌控机器方面达到一个新的水平，看到支撑我们数字世界的数据的隐藏之舞，并欣赏其设计中深刻而复杂的美。