深入理解CPU Cache：从基础到高级概念

需积分: 15 106 浏览量更新于2024-07-17 2 收藏 4.15MB PDF 举报

"本文档是关于CPU缓存(Cache)系统的详细介绍，由Wang Qi、Yang Xi和Zhu Yuhao共同编写。文档涵盖了Cache的基本概念、工作原理、组成结构、一致性与一致性问题、多级Cache层次结构以及数据预读技术等内容，旨在深入理解CPU缓存对性能的影响和优化策略。" 在计算机系统中，CPU Cache是提升处理器性能的关键组件。Cache的工作原理基于局部性原理，即程序在执行时往往倾向于重复访问同一组数据或指令。Cache通过存储最近频繁访问的数据，减少了CPU等待主内存响应的时间，从而显著提高处理速度。 **第1章有关Cache的思考** 本章探讨了Cache的重要性，指出Cache的存在是应对CPU与内存速度差距日益增大的必然选择。"Crime and Punishment"部分可能讨论了缓存未命中带来的性能损失及其解决方案。 **第2章 Cache的基础知识** 1. **Cache的工作原理**：Cache通过快速的存储单元存储数据，分为L1、L2、L3等层次，当CPU需要数据时，首先在Cache中查找，称为缓存命中；如果未找到，则需要从主内存中获取，称为缓存未命中。 2. **Cache的组成结构**：包括数据存储阵列、地址映射逻辑和替换策略三部分。地址映射决定了数据如何存储，替换策略处理缓存空间不足时的选择。 3. **为何关注索引感知**：索引感知指的是在设计Cache时考虑数据在Cache块中的位置，有助于优化访问效率。 4. **CacheBlock的替换算法**：常见的有LRU(最近最少使用)、LFU(最不经常使用)等，用于决定何时将数据从Cache移出。 5. **指令Cache**：专门存储指令的Cache，加速指令的获取，提高执行速度。 **第3章 Coherency and Consistency** 这部分讨论了多处理器系统中，多个Cache如何保持数据的一致性。Cache一致性协议如MESI（Modified、Exclusive、Shared、Invalidated）保证了不同Cache之间数据的有效性和同步。 **第4章 Cache的层次结构** 1. **Cache层次结构的引入**：随着CPU速度提升，多层次Cache架构成为必要，以平衡性能和成本。 2. **存储器读写指令的发射与执行**：描述了从高层Cache到低层Cache的读写操作流程。 3. **CacheController的基本组成部件**：控制器负责管理缓存的读写、替换、一致性等操作。 4. **是否包含的问题**：讨论了是否要使较低层Cache包含较高层Cache的数据，即是否实现包容性Cache。 5. **超越MOESIF**：可能涉及其他一致性协议或Cache组织结构的探讨。 6. **Cache Write Policy**：讲述了不同的写入策略，如Write-Through和Write-Back，以及它们对性能的影响。 **第5章 Data Prefetch** 数据预读是预测并提前加载未来可能需要的数据，以减少延迟。本章可能介绍了软件和硬件预读方法，如基于流的缓冲区(Stream Buffer)等技术，以进一步优化性能。总结，本文档详尽地阐述了CPU Cache的各个方面，从基础理论到实际应用，对于理解和优化计算机系统性能具有重要价值。通过深入学习，我们可以更好地理解计算机系统的运行机制，提高程序执行效率。

1.4 Crime and Punishment

很多时候，一个架构师选择 Load/Store Speculation 的终极方法是掷硬币，只是在用一只

很有技巧的手去投掷这个硬币。这切猜测是无限追求完美的人群，在屈服于最终的命运安排

之后使用的赌徒方式。有人质疑这种掷硬币和闭着眼睛猜有什么区别。闭着眼睛猜确实是一

种办法，只是当你睁开双眼发现迷失后，知道归时之路。

Load/Store Speculation 的结果可能正确，也可能错误。如果最终结果是正确的，是一次

成功的投机，如果错误会带来一定的惩罚。如果一次投机将导致不可收拾的系统惩罚，其最

终结果不如不进行这些猜测。片面追求投机而忽略惩罚只是莽夫所为。合理的预测执行与失

败后可以承担的惩罚是一个大的权衡。投机是人类与生俱来的。在投机的成功率越高，相应

的惩罚越低时，这个天性就更加容易暴露。

Speculation 策略需要在成功率和惩罚间进行取舍。让我无限制的悔棋，从理论上说我可

以战胜一切对手。只是这个对手如果是李昌镐，至死我也下不完一盘棋，所以我将目标设为

悔棋十步，去挑战那位每次只能胜我一目半目的邻居。采用十步悔棋规则后，那位邻居每次

战至中盘，即与我签订城下之盟。

溯本求源，我们重新讨论为什么会出现 Load/Store Speculation。为简化起见，我们仅在

此讨论 Load Speculation 而忽略 Store Speculation。在现代处理器系统中，存储器 Load 请求

所需的 Latency 相对于 CPU 的主频在不断提高，使得存储器瓶颈问题更加突出一些。使用 Load

Speculation 的主要原因是为了掩盖这些 Load Latency，尽量的让执行延时较长的存储器读指

令笨鸟先飞早入林。如何决定让那只笨鸟先飞是一个较为复杂的预测过程。在讲述这些预测

之前，我们首先讨论这些预测的基本实现机制和预测失败的后继处理方法。

我们简单回顾 Confidence Counter 机制，Confidence Counter 是一种常用的，判断是否应

该进行预测的加权处理方式。除了 Load/Store Speculation 实现之外，Confidence Counter 也

广泛应用于 Branch Prediction 领域，是一种已经得到证明的，行之有效的方式。其实现机制

与 N-bit Saturating Counter(Bimodal Predictor)类似。Confidence Counter 由 Saturation，Predict

Threshold，Misprediction Penalty 和 Increment for Correct Prediction 四个参数[14][15]组成。

我们以{31(Saturation), 30(Threshold), 15(Penalty), 1(Increment)}为例简要说明 Confidence

Counter 的使用方法。假设在一个应用中，Confidence Counter 的初值为 29，此时指令流水

线将不会进行 Load Speculation 操作。如果指令流水线发现执行的最终结果为真时，

Confidence Counter 将加 1(Increment)；当 Confidence Counter 的值等于或者超过 Threshold

时，指令流水线开始进行 Load Speculation；如果 Confidence Counter 的值为 31(Saturation)

时，结果为真时也保持不变；如果预测失败后，Confidence Counter 将一次减去 15(Penalty)，

直到逐步加 1 到达 Threshold 后才能触发 Load Speculation。

在 Branch Prediction 中也使用了 Confidence Counter 机制。假设在一个分支预测系统中，

使用 2-b Confidence Counter，而且 Strongly Taken, Weekly Taken, Weekly not Taken 和 Strongly

not Taken 这状态位为 3，2，1 和 0 时，Taken 路径使用的 Confidence Counter 为{3, 2, 1, 1}， Not

Taken 路径使用的 Confidence Counter 为{0, 1, -1, -1}。

大多数 Load Prediction 算法使用 Confidence Counter 作为是否进行预测的基本分析工具。

在 Load Speculation 失败后，指令流水线大多使用两种机制进行恢复操作，分别为 Squash 和

Reexecution 机制[14][15]。

Squash 指当某条 Load 指令预测失败后，将 ROB 中在其之后的指令抛弃，并重新从指令

Cache 中 Fetch 指令。这种方式与 BTB 预测失败后采取的方式类似。Reexecution 指当某条 Load

指令预测失败后，仅仅重新执行与此指令直接或者间接相关的指令。

从直觉上看，采用 Reexecution 比 Squash 机制的效率高出许多。但是我们依然不能依次

得出 Reexecution 一定优于 Squash 机制的结论。在体系结构设计中，更多要考虑的依然是权

衡。Reexecution 机制需要使用更多的逻辑和数据缓冲也是不争的事实。

在已知的指令流水线设计中，Load Speculation 主要有四种算法实现，分别是 Dependency

Prediction，Address Prediction，Value Prediction 和 Memory Renaming。这些 Prediction 的实

现机理依然是猜测，并借用 Confidence Counter 机制和以往的经验尝试。Load Speculation 与

Brach Prediction 的实现有类似之处，本质上是一个机器的自学习过程。

其中 Dependence Prediction 算法的实现机制较为简单。对于现代处理器，能够精确判断

存储器读写指令间的依赖关系至关重要。在一些支持读写指令的乱序执行的微架构中，在这

些处理器中通常使用 LSQ 支持多条存储器读写执行的并发执行，以提高指令执行的并行度。

为确保正确处理读写指令间依赖关系，万无一失的方法是每一条 Load 指令在乱序发射之前，

遍历在 LSQ 中的 Store 指令，确保与其不发生依赖关系。如果在 LSQ 没有发现依赖关系，这

条 Load 指令才可以被乱序执行。

采用这种方法虽然保证了存储器读写指令的正确执行，却带来了较大的系统延时。Store

指令在执行到一定阶段时，Load 指令才能精确地判断这种相关性，在 LSQ 中的 Store 指令并

不都是准备就绪的。Dependence Prediction 算法就是为了取消这类等待延时的一种方法。该

算法有 Blind Prediction，Wait Dependency Predictor 和 Store Sets 等实现策略。

最简单的策略莫过于 Blind Prediction。所谓 Blind Prediction，指 Load 指令仅检查在 LSQ

中准备就绪的 Store 指令，如果没有发生相关性，即可提前执行，如果在 LSQ 发现了 Store Alias，

则直接从 Store Queue 中获取数据。对于没有就绪的 Store 指令，Blind Prediction 认为不存在

相关性。如果最后的执行结果证明确实两者之间存在相关性，被错误执行的 Load 指令，将

采用 Squash 或者 Reexecution 方式恢复。

Alpha 21264 采用了 Wait Dependency Predictor 策略[18]进行 Load Speculation。其实现机

制是在指令 Cache 中的每一条指令加入一个 Wait 位，当 Load 指令的 EA 计算完毕后，而且

相应的 Wait 位为 0 时，这条 Load 指令可以 Speculation，否则需要等待。当发生预测失败后，

相应的 Wait 位需要置 1 以避免进一步的预测失败。全部 Wait 位在 100,000 个 Cycle 后将自

动清零，以避免因为多次预测失败造成很多 Wait 位都置 1 的情况发生。当发生指令 Cache

Miss 的时候，Wait 位将清零。

Store Set 是另一种 Dependence Prediction 实现策略。其实现机制是使用 Store Set ID 连

接对同一个地址的存储器读写访问，并将这些 ID 存放在 SSIT(Store Set Identiﬁer Table)中。在

存储器读写指令预取之后，使用 PC 作为 Index 索引 SSIT 后获得对应的 ID，这个 ID 指向另一

张表 LFST(Last Fetched Store Table)。在 LFST 中记录了已经访问相同地址的 Store 指令，并使

用这种方法判断读写指令之间的依赖关系，没有发现依赖关系的 Load 指令，将可以进行后

续的 Speculation。

以上这几种策略的相同点是利用读写指令间存在的依赖关系，提高 Load Prediction 的预

测成功率。使用这类方法时，存储器读写指令都需要获得 EA 后，才能进行进行相应的预测。

采用 Address Prediction 算法更加 Aggressive 一些，这类算法的本质是在存储器读写指令计算

EA 之前，预测这个 EA 的值，从而实现计算 EA 与实际访问存储器操作的并行执行。处于 Critical

Patch 的存储器访问操作，其 EA 不但可以预测，而且成功率很高。

Address Prediction 算法的常用实现策略有 LVP(Last Value Prediction)，Stride 和 Context。

使用 LVP 策略时，下一次存储器访问的预测地址是上一次刚刚访问过的地址；使用 Stride 策

略时，预测地址是上一次刚刚访问过的地址加上某个偏移；Context 策略更具智慧，采用这

一策略时，可以利用存储器访问过的历史信息 VHT，形成一个 Pattern，之后计算出一个合

适的值索引另一张表 VPT，以获得策略的地址，这一方法与 BTB 中常用的 gshare 机制类似。

对于不同的应用，LVP，Stride 和 Context 策略的预测成功率并不相同，Context 策略貌

似最优，但依然存在一些应用使用 LVP 和 Stride 策略预测成功率更高一些。因此在一个微架

构的具体实现中可以使用不同权值的 Confidence Counter 混合使用 LVP，Stride 和 Context 策

略，以获得更优的结果。

Value Prediction 算法与 Address Prediction 算法的实现策略类似。其不同之处是一个预测

的是将要使用的地址，一个预测的是最终数据。显然 Value Prediction 算法更加 Aggressive 一

些。Value Prediction 与 Address Prediction 的实现策略较为一致，也使用了 LVP，Stride 和 Context

策略，策略的实现方法也几乎一致。

Value Prediction 算法并不能避免存储器读操作最终穿越 Cache Hierarchy，并不能避免任

何 Bus Traffic 的出现。指令流水在获得数据之后，需要进行 Check-Load 操作，确定是否发生

了 Misprediction，但是采用这种算法使得指令流水可以更早的获得 Load 操作的结果，从而

使其后的指令可以在猜测中继续执行。

在存储器瓶颈愈发严重的今天，Value Prediction 算法曾被多次提及。Andy Glew 有一个

非常 Crazy 非常大胆的想法，他设想了一个可以容纳几千条并发执行的单发射的微架构，使

用各类耸人听闻的技术，包括 Value Prediction 进一步优化 MLP(Memory-Level Parallelism)[22]。

以个人浅见，使用一个更大规模，比如几百兆的最后一级 Cache 也比这些想法有实现的可能。

当芯片制作工艺到达 10nm 时，处理器系统包含一个几百兆的 EDRAM 应该不是什么难事。

可能在 14nm 工艺之下就可以实现这样容量的 LLC。

最后需要说明的是 Memory Renaming 算法。研究发现 Store 和 Load 指令对存储器的访

问可以由硬件精确预测[19][21]，使用 Confidence Counter 即可方便地实现这一目标。当 Store

和 Load 指令建立了确定的关系之后，Load 指令不必每一次都从存储器子系统中获得数据，

因为 Store 指令可以将数据直接送至建立映射关系的 Load 指令。这一方法相当于指令流水

将已经与 Store 指令确立关系的 Load 指令的存储器器访问，转化为对 LSQ 进行访问，这也

是 Renaming 的由来。Memory Renaming 技术也有一些具体的实现策略，而且这些策略依然

可以混合使用。在此不再一一述说。

在一个微架构中可以同时使用这四大类算法，也可以只使用部分。在这四大类算法中，

都有各自的实现策略，这些策略可以混合使用。Confidence Counter 使用的不同参数也决定

了预测的成功率。预测失败的恢复手段还有两种选择。

这使得在一个 Load/Store Speculation 设计中有非常多的选择。在其他领域的实现中，系

统设计者也会遇到许多选择。过多的选择经常令人无所适从。系统设计者很难从公说公有理

婆说婆有理的，甚至有意无意去误导的各类量化分析结果中得出精确结论，做出最正确的选

择。他们最后的选择是去掷硬币

①

。

“掷硬币”是面对过多选择的无奈。一个是非的结果很难只有是与非这样简单。有些选

择是单纯的也是幸运得几乎不存在的，他们一次就认定了是与非。更多的是经历了大是大非，

在是是非非中反复后的是与非。是可以倾听自己心跳声的人绞尽最后一滴脑汁后的感觉。

许多设计都存在这样的是非，即便这些设计出自最权威系统架构师之手。这些不可知引

发了一个讨论，是否有哪怕是特定应用之下，最优微架构的存在。我们很难确定在一个具体

的实现中，O(n×Log

n)一定优于 O(N

)的复杂读，在一个实现中 N 是有限的，不是理论上的

无限，而且不同的算法使用的实现时间并不相同。

即便使用相同的算法，具体实现依然有优劣之分。我有些机会体验过这些糟糕的实现。

这些实现不仅出现在入门级别的公司，也出现在国内顶级的公司。最初对这些实现是惊讶的，

在习以为常后只剩下是无奈。而后发现就是这些实现战胜了由常青藤组成的个体，团队，帝

国。明白这些人更加懂得，什么是权衡，什么是掣肘，什么是地处中国的不得已。

①

国内的许多公司也将这个方法称为拍脑门。

第2章 Cache 的基础知识

很多程序员认为 Cache 是透明的，处理器可以很聪明地安排他们书写的程序。他们非常

幸运，可以安逸着忽略 Cache，也安逸着被 Cache 忽略，日复一日，年复一年，机械地生产

着各类代码。All of them are deceived。

貌似并不存在的 Cache，有意无意地制造了，正在制造，并必会制造着各类陷阱。也许

在历经了各类苦难后，有些人能够发现 Cache 的少些特性，却愈发不可控制。掌握 Cache 的

细节知识并不困难，只要能够真正做到静如止水。

2.1 Cache 的工作原理

处理器微架构访问 Cache 的方法与访问主存储器有类似之处。主存储器使用地址编码方

式，微架构可以地址寻址方式访问这些存储器。Cache 也使用了类似的地址编码方式，微架

构也是使用这些地址操纵着各级 Cache，可以将数据写入 Cache，也可以从 Cache 中读出内

容。只是这一切微架构针对 Cache 的操作并不是简单的地址访问操作。为简化起见，我们忽

略各类 Virtual Cache，讨论最基础的 Cache 访问操作，并借此讨论 CPU 如何使用 TLB 完成虚

实地址转换，最终完成对 Cache 的读写操作。

Effective Page Number Cache Line Number Byte in Line

Effective Page to Virtual Page

Number

TLB ...

Compare Addresses & Select Data

To Main Memory

Real Address data

Byte Select and Align

Data Out

Address Data line

Cache

图 2-1 典型的 Cache 结构

①

Cache 的存在使得 CPU Core 的存储器读写操作略微显得复杂。CPU Core 在进行存储器

方式时，首先使用 EPN(Effective Page Number)进行虚实地址转换，并同时使用 CLN(Cache Line

Number)查找合适的 Cache Block。这两个步骤可以同时进行。在使用 Virtual Cache 时，还可

以使用虚拟地址对 Cache 进行寻址。为简化起见，我们并不考虑 Virtual Cache 的实现细节。

EPN 经过转换后得到 VPN，之后在 TLB 中查找并得到最终的 RPN(Real Page Number)。如

果期间发生了 TLB Miss，将带来一系列的严重的系统惩罚，我们只讨论 TLB Hit 的情况，此

时将很快获得合适的 RPN，并依此得到 PA(Physical Address)。

①

该图源自[23]的 Figure 2. A typical cache and TLB design，拷贝后过于模糊，重画这个示意图，并有所改动。

剩余111页未读，继续阅读

haoyz001

粉丝: 0
资源: 1

深入理解CPU Cache：从基础到高级概念

expresscache 64位

绿茶出的cache软件

简要介绍一下Page Size Aware Cache Prefetching的主要内容

[ ] ARM errata: Cache maintenance by set/way operations can execute out of order 介绍

cache 技术手册

[*] Enable the L2x0 outer cache controller 内核配置项介绍

cache coherence white paper pdf

CacheCloud详细介绍，用法，用处

Linux clear cache

浅谈cache memory 王齐 pdf

最新资源