The ITTAGE indirect branch predictor

2025-07-05

ITTAGE 間接分支預測器

原文由 Nelson Elhage 于 2025-07-05 發布，訂閱此部落格

在研究效能的過程中，針對新的 Python 3.14 尾呼叫直譯器，我（透過 Sam Gross 這則非常有資訊量的留言）學到了一件對我而言很新的效能冷知識：現代 CPU 大多已經不再難以預測「傳統」位元組碼直譯器迴圈中、用於位元組碼分派的間接跳躍。在穩定狀態下，只要位元組碼本身夠穩定，現代 CPU 即使面對最單純的 while / switch 風格直譯器迴圈，也能以非常高的準確率預測分派¹！

出於好奇，我花了一點時間研究分支預測器究竟是如何達成這件事的。我覺得答案相當迷人，所以想試著分享一下我所理解的主要重點，以及過程中浮現的一些有趣的關聯與想法。

先快速說明一下：我不是硬體工程師或 CPU 設計師，接下來主要會聚焦在我覺得有趣的一些高層次概念。我很可能會弄錯一些地方。如果你想看真正懂行的人所寫的 CPU 分支預測入門，請參考 Dan Luu 的這篇文章。

TAGE 與 ITTAGE 分支預測器

一般來說，現代最先進的 CPU 似乎不太會公開太多關於分支預測器的細節，所以我們並不清楚——或者至少，我沒辦法輕易查到——最頂尖的 CPU 實際上的分支預測是什麼樣子。不過，至少有一個已公開、既實用又能預測位元組碼直譯器迴圈的演算法——也就是 ITTAGE 間接分支預測器——而這就是我要談的主題。這個預測器的作者曾寫過一篇論文，探討在位元組碼直譯器上的預測表現，並發現他的 ITTAGE 表現與 Intel Haswell CPU 相近，因而推測 Haswell 使用了類似的變體，但我想我們並無法確定。

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; }
};

再稍微複雜一點的策略，則是把每個分支的一個位元狀態，換成一個小的計數器（最少只要 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」in the paper。

參考資料

關於 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 的演算法應用於模糊測試，最可能的方式就是把「預測錯誤」當作獎勵訊號，並花更多時間在預測錯誤率高的輸入上。

當我在思考這個想法時，我意識到它聽起來很熟悉，因為在某種抽象層次上，這正是強化學習領域中的一個經典概念！

最值得注意的或許是，OpenAI 在 2018 年發表了兩篇關於「好奇心驅動學習」的論文，探討透過加入鼓勵探索的獎勵項來增強強化學習的技術，即使在環境沒有給予獎勵訊號的情況下也是如此。這兩篇論文在細節上有所不同，但共享同一個基本想法：除了決定行動的策略網路之外，你還會訓練一個預測網路，嘗試預測環境的某些特徵或行動的結果。然後，你會獎勵策略模型去發現那些預測誤差高的行動或狀態，如果一切順利，這將鼓勵對環境中新奇部分的探索。

就我所知，這項技術效果相當不錯；第二篇論文在《魔境歷險》（Montezuma's Revenge）這款雅達利遊戲上達到了當時最先進的表現，而這款遊戲對強化學習演算法來說向來非常困難，因為它需要在獲得任何分數之前，進行大量的探索並操作鑰匙與裝備。然而，就我目前所知，我不太清楚這項工作與這個方法後續的發展如何。

我當時有關注那些論文，也追蹤了相關工作，但在腦中把「ITTAGE」與「覆蓋率導向模糊測試」拼湊起來之前，我並沒有有意識地想到它們。這種匯合確實讓我覺得這裡面可能有點東西；不過同時，在 2025 年，直接丟一個神經網路來解決問題，或許反而比一個精心設計與調校的預測演算法來得更簡單！

「執行緒化」風格的直譯器將分派邏輯複製到每個操作碼中，仍然是一種效能上的勝利，但遠不如在舊款 CPU 上那麼顯著；如今的獲益大多只是因為執行的指令總數更少，尤其是分支更少。我的前一篇文章中有更多討論。 ↩︎