ITTAGE 间接分支预测器
原文由 Nelson Elhage 于 发布，订阅该博客
在研究新的 Python 3.14 尾调用解释器性能的过程中，我（通过 Sam Gross 这条信息量极大的评论）了解到一个对我而言很新鲜的性能冷知识：现代 CPU 在预测“常规”字节码解释器循环中用于字节码分发的间接跳转时，已经基本不再吃力。在稳态下，只要字节码本身足够稳定，现代 CPU 即使面对最普通的 while / switch 风格解释器循环，也能以极高的准确率预测分发跳转1！
出于好奇，我花了一些时间去了解分支预测器究竟是如何做到这一点的。我觉得答案相当迷人，所以想在这里分享一下我所理解的关键要点，以及由此联想到的一些有趣联系和想法。
先做个小小的免责声明：我不是硬件工程师也不是 CPU 设计师，接下来主要会聚焦在我觉得有意思的一些高层思路上，难免会有错误之处。如果你想看真正懂行的人写的分支预测入门介绍，可以参考Dan Luu 关于该主题的文章。
TAGE 与 ITTAGE 分支预测器
一般来说，现代顶尖的 CPU 似乎并不会公开太多关于其分支预测器的细节，所以我们并不清楚——至少我没能轻易查到——最前沿的 CPU 内部的分支预测究竟是什么样子。不过，至少有一种已公开的、既实用又能预测字节码解释器循环的算法——ITTAGE 间接分支预测器——而这正是我要讨论的对象。该预测器的作者撰写了一篇论文，研究了在字节码解释器上的预测效果，发现他的 ITTAGE 表现与 Intel Haswell CPU 相当，并推测后者使用了其某个变体，但我们并不能确定。
ITTAGE 是 TAGE 预测器的一个变体；TAGE 用于预测条件分支的跳转与否，而 ITTAGE 则用于预测间接跳转的目标地址。两者的结构非常相似，所以在本文的大部分内容中我会把它们放在一起讨论。
简要预览
在深入细节之前，我先简要概括一下本文的脉络。TAGE 和 ITTAGE 都是：
- 通过建立 (PC，PC 历史) -> 过去行为 的映射来预测分支行为，并寄希望于未来会重现过去。
- 保存多张这样的表，使用一组按几何级数递增的历史长度
- 尝试为每个分支动态选择合适的表（历史长度）。
- 通过在预测出错时自适应地转向更长的历史，并采用精心的替换策略来优先保留有用的表项来实现。
接下来是更详细的版本！如果你觉得这些就够了，也可以直接跳到后文关于我为何觉得这个话题有意思的思考和相关联系的部分。
动态分支预测 101
许多动态分支预测算法都基于一个简单的假设：维护一张某种形式的历史数据表，当需要预测分支时，就查找“上一次”发生了什么，并假定历史会重演。用带点 C++ 味道的伪代码来理解，我倾向于把这种思路建模为：
struct BranchDetails {
// The information we use to identify a branch
};
struct BranchHistory {
// The information we store about eaach branch
// Predict the outcome of a branch based on past state
bool predict() const { /* ... */ };
// Update our state based on a resolved branch
void update(bool taken) { /* ... */ };
};
// We store a mapping from one to the other. This is a fixed-size chunk of
// hardware, so it stores a fixed number of entries. We'll talk a bit about
// replacement strategy and some details later on.
using PredictorState = FixedSizeMap<BranchDetails, BranchHistory>;
void on_resolve_branch(PredictorState &pred, BranchDetails &branch, bool taken) {
pred[branch].update(taken);
}
bool predict_branch(PredictorState &pred, BranchDetails &branch) {
return pred[branch].predict();
}那么，我们该用什么作为 BranchDetails 和 BranchHistory 呢？也许最简单的选择——也被一些早期 CPU 所采用——就是直接用分支地址来标识分支——本质上是为程序文本中的每条分支指令维护状态——而历史信息只用一位：
struct BranchDetails { uintptr_t addr; };
struct BranchHistory {
bool taken_;
bool predict() { return taken_; }
void update(bool taken) { taken_ = taken; }
};再稍微复杂一点的策略，是把每个分支的 bool 状态换成一个小计数器（最少 2 位即可），从而获得一定的迟滞效果。我们在分支解析时递增或递减计数器，并用其符号位来做预测。事实证明，大多数分支都强烈偏向某一边——例如，分支跳转率为 10% 或 90% 的情况远比 50% 常见——而少量的迟滞就能让我们在不忘掉已学到知识的前提下，容忍偶尔的异常行为：
struct BranchHistory {
int2_t counter_;
bool predict() { return counter_ >= 0; }
void update(bool taken) {
saturating_increment(&counter_, taken ? 1 : -1);
}
};超越单纯的 PC
仅用 PC 来索引分支简单高效，但也有局限。许多分支表现出与动态数据相关的行为，如果想获得更高的准确率，我们就需要以更细的粒度来区分它们。
由于分支预测器位于 CPU 前端，必须在指令真正执行——甚至完全译码——之前就做出预测，因此它们能用于预测的 CPU 状态非常有限。不过，有一种上下文它们几乎可以“免费”获取：程序计数器和最近分支的历史，因为这些历史本来就是靠预测器一步步生成的！
因此，分支预测器可以维护一个固定大小的循环缓冲区，以某种形式保存滚动的“分支历史”或“PC 历史”，并利用这些状态来区分不同的分支。在最简单的情况下，我们可以为之前的每条分支保存一位，用“1”表示已跳转、“0”表示未跳转。在更复杂的预测器中，我们可能会包含无条件分支，或将 PC 值的若干位写入历史：
constexpr int history_length = ...;
struct BranchDetails {
uintptr_t pc;
bitarray<history_length> history;
}如何确定分支历史的长度
该用多长的历史呢？是不是越长越好？
更长的历史让我们能学习到更多的模式，以及更复杂的模式。对于行为稳定的程序，在稳态下，更长的历史可能让我们学习到程序的更多行为，并更精细地区分不同情形。
然而，更长的历史意味着我们需要用表中的更多空间来学习简单模式，也可能需要更多时间，因为我们有更多可能的状态，需要分别遇到每一种状态才能学会。想象一个简单的函数如下：
bool logging_active;
void log(const char *msg) {
if (logging_active) {
printf("%s\n", msg);
}
}假设这个函数没有被内联，并且在可执行文件的多处被调用。
假设 logging_active 在运行时是静态的或基本静态的，那么这个分支是高度可预测的。一个简单的仅用 PC 的预测器应该能达到近乎完美的准确率。然而，如果我们同时考虑分支历史，预测器就不再把这个分支看作单一实体；而是需要为每一条到达该分支指令的路径分别进行跟踪。在最坏情况下，如果我们保存 k 位历史，这个分支就可能需要占用 2^k 个不同的表项！更糟的是，我们需要逐一遇到每种状态，而且不同路径之间无法相互“学习”。
TAGE 算法：核心思想
有了这些背景，我们现在可以勾勒出 TAGE 预测器的大致轮廓。
TAGE 会像我上面描述的那样跟踪分支历史，但与更简单的预测器不同，它会跟踪数百甚至数千位的历史，从而有可能学习到跨越很长距离的模式。
为了在不引起状态爆炸的前提下利用如此多的历史，TAGE 存储了多张历史表（数量可能在 10 到 20 张左右），分别按几何级数的历史长度进行索引（即第 N 张表使用的历史长度 \( L_n ≈ L_0\cdot{}r^n \) ，其中 \(r\) 为某个比值）。然后，TAGE 会尝试为每个分支自适应地选择足以做出良好预测的最短历史长度（及对应的表）。
它是怎么做到的呢？以下是核心思路（据我的理解）。稍后我会给出一些论文和代码链接，供想深入细节的读者参考！
每张表中的标签位
到目前为止，我完全回避了这些查找表究竟如何实现的问题，特别是我们如何具体实现“查找具有给定键的表项”。
在许多简单的分支预测器中，历史表“不知道”自己存储的是哪些键，而只是直接基于键的若干位来做索引。
例如，对于一个以 PC 索引的预测器，我们可能只是拥有一组 \(2^k\) 个计数器，并用 PC 的低 \(k\) 位来选择表项。如果两个分支的地址对 \(2^k\) 取模后相同，它们就会冲突并共用同一个表项，而我们不会去检测这种冲突或做特殊处理。这种选择让表的实现极其廉价高效，而且在许多情况下是一种很好的权衡。直观上，我们本来就必须处理分支预测错误的情况，而这类冲突只是导致错误的另一种原因；检测和应对冲突需要更多的硬件和存储，而事实证明，把这些资源用在以其他方式降低错误率上更为划算。
然而，TAGE 存储了多张表，需要为不同分支使用不同的表，这就要求知道哪些表真正为给定键存储了信息，哪些只是冲突的键。因此，除了其他有效载荷外，每个表项还会存储一个标签，其中包含描述该表项所存储键的额外元数据。
给定一个 (PC, 分支历史) 元组 T，TAGE 会为每张表使用两个不同的哈希函数 H_index 和 H_tag。分支状态 T 会被存储在表中索引为 H_index(T) 的位置，标签值为 H_tag(T)。查找时，我们检查 H_index(T) 位置的值，并将标签与 H_tag(T) 进行比较。
- 如果标签不一致，说明该表项当前存储的是关于另一条分支的信息，我们不会使用它（但可能会决定覆盖它）
- 如果标签一致，我们就认为该状态与我们的分支匹配，并使用和/或更新它。注意我们仍然只检查了哈希值，因此仍有可能与另一条分支在两个哈希上都发生冲突，但我们会设计哈希函数并选择合适的大小，使这种情况在实践中足够罕见。
这些标签位赋予了 TAGE 名字中的“TA”；而“GE”则来自几何级数的历史长度。
基本预测算法
有了这样的设定，TAGE 的基本预测算法就相当简单了。每个表项都存储一个计数器（在论文中称为 ctr），如上所述——在“分支已跳转”时递增，在“未跳转”时递减。
要做出预测，TAGE 会使用相应的历史长度检查每一张表。它会考虑所有标签匹配的表项，并采用其中历史长度最长的那个匹配表项的预测。
基础预测器——在最简单的情况下，就是一张仅以 PC 索引的表——不使用标签位，因此总会匹配，并在没有更长历史匹配时作为后备。
预测错误时转向更长的历史
一旦分支解析完成、我们知道了正确答案，就需要更新预测器。
TAGE 总是会更新用于做出预测的那个表项的 ctr 字段。然而，如果预测错误，它还会尝试在采用更长历史长度的表中分配一个新的表项。这样做的目标是动态地尝试越来越长的历史，直到找到能奏效的长度。
跟踪表项的有用程度
由于表项是带标签的，我们需要一种方式来决定何时替换某个表项并将其重用于新的分支。为了让预测器良好工作，我们的目标是保留那些未来可能做出有用预测的表项，而丢弃那些不会的。
为了逼近这一目标，TAGE 会跟踪哪些表项最近是有用的。除了标签和计数器外，每个表项还有一个 u（“有用”）计数器（通常只有 1 或 2 位），用于记录该表项最近是否产生过有用的预测。
当我们如上所述分配新表项时，只会覆盖 u=0 的槽位，并且新槽位会以 u=0 初始化；因此，新表项必须证明自己的价值，否则就有被替换的风险。
每当某个表项同时满足以下条件时，u 计数器就会递增：
- 被用于一次预测，且
- 该预测被证明是正确的，且
- 该表项给出的预测与历史次长的匹配表项给出的预测不同。
因此，仅仅给出正确预测还不够；它还必须给出一个在反事实情况下本会出错的正确预测。
此外，u 计数器会以某种形式被周期性地衰减（或直接清零），以防止表项永远驻留。不同已发表版本中的具体算法差异很大。
从 TAGE 到 ITTAGE
我一直在描述 TAGE 的行为，它为条件分支预测一位信息（跳转/不跳转）。而 ITTAGE 用于预测间接分支的目标地址（这也是我写这套系统的初衷！），它几乎完全相同；主要变化只有：
- 每个表项还存储一个预测的目标地址
- ctr 计数器被保留，但变成了“置信度”计数器。在“预测正确”时递增，在“预测错误”时递减。在预测错误时，仅当 ctr 已处于最小值时，我们才会将预测目标更新为新值。因此，ctr 跟踪的是我们对这个特定目标地址的置信度，而 u 跟踪的是整个表项在整个预测器上下文中的有用程度。
事实上，同样的表可以合并为一个联合预测器，在论文中被称为“COTTAGE”（见该论文）。
参考资料
关于 TAGE 和 ITTAGE 的资料并不算多，但我会在这里列出我找到的最好的几个链接，供好奇想深入细节的读者参考！阅读这些论文时，让我印象深刻的是，光有正确的高层思路是远远不够的；一个高性能的 TAGE 或 ITTAGE（或任何分支预测器）实现，既需要好的设计，也需要大量的细致调优和权衡。链接如下：
- A case for (partially) tagged geometric history length branch prediction
- 据我所知，这就是提出 TAGE 和 ITTAGE 的那篇论文
- The L-TAGE Branch Predictor
- 为 2007 年分支预测竞赛（“CBP-2”）实现的 TAGE 版本。
- A 64 Kbytes ISL-TAGE branch predictor
- 为后续竞赛（2011 年的“CBP-3”）更新版本的说明。
- A 64-Kbytes ITTAGE indirect branch predictor
- 为同一竞赛中间接分支赛道设计的 ITTAGE 预测器的说明。
- The program for JWAC2, which hosted the CBP-3 competition
- 其中尤其包含了提交给该竞赛的 TAGE 和 ITTAGE 实现的源代码链接（在微架构模拟器中）。
- BOOM (Berkeley Out Of Order Machine)’s documentation on their TAGE implementation
- BOOM 是一个面向微架构研究的开源 RISC-V 核心。
我为何觉得 ITTAGE 有意思
一方面，我觉得 ITTAGE 有意思，是因为我偶尔需要思考解释器循环或类似软件的性能，而它代表了我对此类场景推理方式的一次重要更新。非常具体地说，它影响了我上一篇中的 CPython 基准测试。
不过，我也因为一些更广泛的原因，以及它与其他一些感兴趣领域的联系而觉得它很迷人。
我过去写过一类软件工具（包括覆盖率引导的模糊测试器和跟踪式 JIT），它们很大程度上通过观察程序计数器随时间的行为来理解程序行为，也写过这些工具——以相关的方式——在解释器及类似软件上举步维艰的原因，这类软件的程序状态“隐藏在数据中”，仅靠控制流远不足以代表“有趣的”状态。
我在那篇文章中没有提到这个联系，但我一直认为分支预测器也是这类工具中的一员。如上文所述，它们同样主要通过“一系列程序计数器取值”这一视角来理解程序执行，而且它们——至少在历史上——在解释器循环上也表现不佳。
因此，了解到 ITTAGE 及其在预测解释器行为上的成功，很自然地在我心中引出了一个问题：能否从 ITTAGE 算法中学到一些东西，并应用到那些其他工具上？
特别是，我在思考……
ITTAGE 能用于覆盖率引导的模糊测试与程序状态探索吗？
如我在那篇旧文中所概述的，覆盖率引导的模糊测试是一种尝试自动探索目标程序行为的技术，它通过生成候选输入，然后观察哪些输入在程序中产生了“新的”行为。
为了让这个循环运转起来，我们需要某种方式来刻画或归类程序行为，以便判断什么算是“新的”或“有趣的”行为，什么又属于已经观察过的行为。我承认我对该领域当前的前沿并不熟悉，但历史上一直是这样做的：使用类似“覆盖率”的指标，统计 PC 取值或分支（本质上是 (PC, PC’) 二元组）的出现次数。这些计数可能会被分桶，我们则通过执行过程中生成的 [(PC, bucketed_count)] 列表来为执行过程“打指纹”。
这种方法在实践中极为有效。然而，它在某些形态的程序上会遇到困难——其中经常包括解释器——在这些程序中，“有趣的”状态无法很好地映射到程序计数器或分支的集合上。我最喜欢的例证之一是 IJON 论文，它展示了一些具体问题，并通过人工添加注解来解决这些问题。
那么，我的问题就是：类似 TAGE/ITTAGE 的方法能否帮助覆盖率引导的模糊测试器更好地探索解释器及类似解释器的程序的状态空间？例如，我们能否在现有语料库上训练一个类似 TAGE 的预测器，然后根据候选变异体的预测错误率来对其进行优先级排序？这是否能让模糊测试器（例如）仅通过注解解释器，就有效地探索以解释型语言编写的代码的状态空间？
存在大量实际挑战，但在原理上，这似乎可能让状态空间的探索更加细腻，并发现那些只能通过长程关联和模式才能识别的“新颖行为”。
我要指出的是，TAGE/ITTAGE 专门是围绕硬件性能特征和权衡来设计与调优的；在软件中，性能格局截然不同，因此如果这类想法确实可行，我猜其细节会相当不同，并且会针对高效的软件实现进行优化，不过，在我看来，借鉴“为每个分支动态选择历史长度”这一核心思想，仍有其价值所在。
一个更异想天开的想法是直接利用硬件分支预测器本身。现代 CPU 允许你通过硬件性能计数器来观察分支预测的准确率，我们可以设想先用现有样例的语料库来训练分支预测器，然后将实际的硬件误预测计数作为新颖性信号。这种方法同样面临大量挑战，部分原因在于硬件分支预测器的不透明性以及无法显式控制它；不过，它的好处可能是比软件预测器便宜得多。这让我不禁好奇，是否有 CPU 能够显式暴露分支预测器的状态——哪怕是以“保存或恢复预测器状态”操作的形式——这似乎会让这类方法可行得多。
如果你知道有哪个项目尝试过类似的东西——或者受此启发想去实验一番——请务必告诉我。
好奇心与强化学习
如上一节所概述的，我能想到的将类似 TAGE/ITTAGE 的算法应用于模糊测试的方法，就是把“预测错误”当作奖励信号，并将时间花在预测错误率高的输入上。
当我思考这个想法时，我意识到它听起来很熟悉，因为在某种抽象层面上，这正是强化学习领域的一个经典思路！
也许最值得一提的是，2018 年 OpenAI 发表了两篇关于“好奇心驱动学习”的论文，探索了通过增加鼓励探索的奖励项、即使在没有来自环境奖励信号的情况下也促进强化学习的技术。这两篇论文在具体方法上有所不同，但基本思想相同：除了决定行动的策略网络之外，你还会训练一个预测网络，它会尝试预测环境的某些特征或你行动的结果。然后，你会奖励那些发现了高预测误差的行动或状态的策略模型，如果一切顺利，这将鼓励对环境中新颖部分的探索。
据我所知，这项技术效果相当不错；第二篇论文在 Montezuma's Revenge 上取得了当时最先进的成绩，这是一款对强化学习算法而言 notoriously 困难的 Atari 游戏，因为它需要在获得任何分数之前进行大量的探索以及对钥匙和装备的操作。不过，至于这项工作及其方法的后续发展如何，我目前还不太清楚。
我当时就关注过这些论文，也跟进了这项工作，但在脑海中尝试把“ITTAGE”和“覆盖率引导的模糊测试”拼在一起时，并没有有意识地想到它们。这种殊途同归让我觉得这里面或许真有点东西；不过，与此同时，在 2025 年，直接向这个问题抛一个神经网络，或许比用一个专门设计和调优的预测算法更容易！
评论
登录后参与讨论