Project --- A Branch Predictor Evaluator

The case studies of Chapters Chapter 63 and Chapter 64 examined branch predictors in the abstract. Both Intel Golden Cove and AMD Zen 4 are described in public sources as TAGE-class predictors with statistical correctors and indirect target predictors, but the exact configurations are not published. Reading and trusting the disclosed numbers is one side of microarchitecture research. Building a predictor from scratch and measuring it on standard traces is the other side.

This project chapter walks the reader through building three branch predictors in C++ and evaluating them on standard benchmark traces. The first predictor is McFarling’s gshare, the classic correlated baseline. The second is a perceptron predictor in Jimenez and Lin’s original formulation. The third is TAGE-SC-L, the production state-of-the-art represented (in simplified form) in modern P-cores. The reader will report the MPKI of each predictor on a curated set of Championship Branch Prediction traces and analyze the storage-versus-accuracy trade-off.

The project sits in the same shape as the cache simulator of Chapter 47. First, the Setup and Installation section walks through getting a C++ toolchain on macOS, Linux, and Windows. Then the project skeleton and the build system. Then the predictor interface, and each predictor in turn, in increasing complexity order. Then the trace reader. Finally, the evaluation harness and the MPKI report. The chapter ends with worked examples and exercises.

01.Setup and Installation

The project requires four tools: a C++17-or-later compiler (clang or gcc), the CMake build system, Python 3 (for the trace post-processing and plotting scripts), and xz for decompressing the CBP trace files. The C++ standard library is the only third-party dependency, by design. The evaluator does not pull in any external libraries to keep the build reproducible.

macOS (Homebrew)

macOS setup via Homebrew

Verify each tool after installation:

Verify macOS installations

The Apple-supplied clang++ from Xcode Command Line Tools also works for the project. The Homebrew LLVM is the canonical choice when newer C++20 features (such as std::span on older toolchains) are needed.

Linux (Arch as canonical)

Arch Linux setup

For Debian or Ubuntu, replace pacman with apt:

Debian/Ubuntu alternative

For Fedora:

Fedora alternative

Windows (ArchWSL)

The recommended path on Windows is ArchWSL, the Arch Linux distribution for WSL2. Once ArchWSL is installed, the setup is identical to the Arch Linux instructions above. The project source tree should live inside the WSL2 filesystem (~/projects/bpeval) rather than on a Windows-mounted drive, since the trace files are several hundred megabytes each and the I/O path is markedly faster on the native WSL2 file system.

Windows setup via ArchWSL

02.Project Skeleton

The project tree is small. The predictors share a common abstract base class. The evaluator drives the predictors against a trace.

Project layout

The build file declares one executable, bpeval, plus the shared predictor library.

CMakeLists.txt

Build:

Build the evaluator

03.Predictor Interface

The three predictors share an abstract base class so the evaluator can drive any of them through a common interface.

Predictor.hpp

The interface treats each branch as a separate predict-then- update transaction. The evaluator calls predict, compares the prediction to the ground truth, increments the misprediction counter if they disagree, and calls update with the ground truth.

04.The gshare Predictor

The gshare predictor is the simplest of the three. It maintains a single table of 2-bit saturating counters and a global history register (GHR). The table is indexed by the XOR of the branch PC and the GHR. The prediction is the high bit of the counter at that index.

The predictor’s storage cost is exactly $2 \cdot 2^N$ bits for a table of $2^N$ entries. With $N = 14$, the table holds 16384 counters costing 32768 bits, which is exactly 4 KiB, plus the 14-bit GHR. The total is just over 4 KiB. CBP submissions often use $N$ between 13 and 15.

Gshare.hpp

Gshare.cpp

The implementation is intentionally compact. Each counter is stored as a single byte (8 bits) for ease of access, even though only 2 bits per counter are architecturally used. The storage_bits method reports the 2-bit-per-counter budget that a hardware implementation would actually use.

05.The Perceptron Predictor

The perceptron predictor takes a different mathematical approach. Each branch PC indexes a row of weights $w_0, w_1, \ldots, w_H$, where $H$ is the history length. The prediction is the sign of: $y = w_0 + \sum_{i=1}^{H} w_i \cdot h_i,$ where $h_i \in \{-1, +1\}$ is the $i$-th outcome in the global history (the $-1$ encoding is for not-taken and the $+1$ encoding is for taken). If $y \geq 0$, predict taken, otherwise predict not-taken. The bias term $w_0$ captures the branch’s overall bias.

Training, on a misprediction or when $|y|$ is below a threshold, updates each weight by the rule: $w_i \gets w_i + t \cdot h_i,$ where $t \in \{-1, +1\}$ is the actual outcome. Weights are clamped to a saturating range, typically $[-128, +127]$ for 8-bit signed weights.

Perceptron.hpp

Perceptron.cpp

A typical configuration uses 1024 rows, 36-bit history, and $\theta = 14$ for the training threshold. The storage cost is $8 \cdot 1024 \cdot 37 = 303{,}104$ bits, or roughly 37 KiB. The gshare table at the same storage budget would hold roughly 150K counters (about $N = 17$).

06.The TAGE-SC-L Predictor

TAGE is the production state of the art. The Statistical Corrector and Loop extensions add accuracy on the hardest benchmarks. The implementation here is a simplified TAGE-SC-L with five tagged tables, geometric history lengths, and a small SC component.

The TAGE predictor maintains a base predictor (a bimodal table) plus $N$ tagged tables of increasing history length. On a prediction lookup, all $N$ tables are consulted in parallel. Each tagged table either hits (its tag matches) or misses. The predictor uses the highest-history-length hit as the prediction. On a misprediction, the predictor allocates a new entry in a higher-history table.

The geometric history lengths are 5, 13, 33, 70, and 140 for a typical 5-table configuration. The 5-table TAGE captures correlations across both short-history patterns and long-history patterns. Empirically, the longer-history tables are sparse but contribute most of the accuracy gain over gshare.

TageSCL.hpp

The implementation file is substantially longer. The key methods are the index and tag hash functions and the allocation policy on misprediction. The hash is a folded XOR of the relevant GHR bits with the PC, masked to the table-index width.

TageSCL.cpp index and tag hash

The prediction proceeds as follows. The base bimodal predictor produces a default prediction. The five tagged tables are consulted in order of decreasing history length, longest first. The highest-history table that hits supplies the prediction (provider_). If no tagged table hits, the base predictor’s output is used.

TageSCL.cpp predict

The update logic is the most subtle part of TAGE. On every resolved branch the provider’s counter is moved one step toward the outcome, saturating at the ends of its range, and the usefulness counter is raised when the provider’s prediction beat the alt provider’s and lowered when it lost to it. On a misprediction, an allocation attempt is made in the first higher-history table whose entry is not useful.

TageSCL.cpp update

The total storage budget for the configuration above is approximately: $4096 \cdot 2 + 5 \cdot 4096 \cdot (3 + 8 + 2) + 1024 \cdot 8 = 8192 + 266240 + 8192 = 282624 \text{ bits},$ or roughly 35 KiB. The simplified TAGE-SC-L achieves competitive MPKI, though at that size it sits slightly above the 32 KB CBP budget category and would need a modest trim to enter it.

07.Trace Reader

The trace reader consumes the CBP trace format. The CBP trace is a sequence of fixed-size records, optionally xz-compressed. Each record contains the branch PC, the branch type, the outcome, and the target for taken branches.

Trace.hpp

Trace.cpp

08.Evaluator Driver

The main driver opens a trace, instantiates the selected predictor, runs the predict-update loop to exhaustion, and prints the MPKI plus the storage cost.

main.cpp

Run the evaluator:

Run on a sample trace

09.Evaluation and MPKI Results

The CBP-5 (2016) traces include over 200 benchmark workloads covering SPEC CPU 2006 and CPU 2017 plus several industry traces. The published winning entries achieve MPKI in the range of 2 to 8 on most of the suite, with the easiest workloads falling below 1 and the hardest running above 10.

The expected MPKI for the three predictors on a representative sample of workloads is shown in the table below. The values are illustrative ranges from the published CBP-5 results [1] and from re-implementations in academic comparison papers. Exact numbers depend on the configuration of each predictor and the trace selection.

The pattern across the table is consistent. gshare delivers respectable MPKI at the smallest storage budget. The perceptron catches up significantly on most benchmarks, with the geometric-mean improvement around 20%. TAGE-SC-L wins on most benchmarks, with the geometric-mean MPKI 40% to 50% below gshare’s. On a few benchmarks (notably namd, where the mispredict rate is already very low), the three predictors converge.

10.Storage vs Accuracy

A useful exercise is to sweep the storage budget for each predictor and plot the resulting MPKI. The shape of the curve reveals the marginal accuracy gain per added storage bit.

For gshare, MPKI drops as the table grows until aliasing stops being the dominant error source, after which the curve flattens. The knee is typically at 16 to 64 KiB.

For perceptron, MPKI drops with the history length up to the point where the per-branch weight vector saturates the training rate. The knee is typically at history length 30 to 40.

For TAGE-SC-L, the curve has multiple knees. Doubling the number of tagged tables produces an MPKI drop until the geometric history coverage is dense enough. Adding the SC component costs about 3% more storage in the configuration built here, and produces a measurable MPKI drop on the hardest benchmarks. Production SC components are proportionally larger, closer to 10% of the budget. Further additions show diminishing returns.

The general lesson is that the trade-off curves are predictor-specific. A 32 KB TAGE-SC-L is meaningfully better than a 32 KB gshare. A 4 KB gshare may outperform a 4 KB TAGE-SC-L because TAGE’s tables overhead is not amortized at small budgets.

11.Worked Examples

12.Exercises

References

1. [1]Hennessy, John L. and Patterson, David A. (2019). “Computer Architecture: A Quantitative Approach.” Morgan Kaufmann.