pred

pred — Branch Prediction

The pred/ module implements gem5’s modular branch prediction framework. It provides a BPredUnit wrapper that orchestrates the Branch Target Buffer (BTB), conditional direction predictor, indirect branch predictor, and Return Address Stack (RAS). Multiple predictor algorithms are available — from Atomic and Timing Simple CPUs — gem5 Wiki" href="../simple/index.html">simple 2-bit counters to state-of-the-art TAGE-SC-L — allowing researchers to study branch prediction accuracy and its impact on pipeline performance.

⚙ 8+ Algorithms 🔨 TAGE-SC-L 🚀 Modular Design 🎯 Perceptron

📚 What is this module?

Every time a processor encounters a branch instruction (if/else, loops, function calls), it must predict whether the branch will be taken and where it will go — before the branch is actually resolved. A wrong prediction causes a pipeline flush (squash), wasting 10–20+ cycles of work. Modern branch predictors achieve 95–99% accuracy, making them critical for performance. The pred/ module lets researchers implement and compare different prediction strategies.

💡 Real-world analogy: GPS Navigation

Think of branch prediction like a GPS that tries to guess your route at every intersection before you signal. The BTB is like the GPS’s map of known intersections — it remembers where you turned last time. The conditional predictor (TAGE, tournament, etc.) is the pattern-matching algorithm that says “you turned left here the last 7 out of 8 times, so probably left again.” The RAS is like the GPS knowing that after you enter a building (function call), you’ll come back out the same door (return address). When the GPS gets it wrong, you have to make a U-turn (pipeline squash) and go back to the right intersection. The better the GPS algorithm, the fewer U-turns you make — and the faster you reach your destination.

Predictor Algorithms

Source Files

12K

Lines of Code

TAGE-SC-L

State of Art

Prediction Architecture

The branch prediction system has a layered architecture. BPredUnit is the top-level wrapper that coordinates three sub-predictors: the BTB for target addresses, a conditional predictor for direction (taken/not-taken), and a RAS for return addresses. The IndirectPredictor handles indirect branches (jumps through registers) separately.

flowchart TD
    subgraph BPredUnit["BPredUnit (bpred_unit.hh)"]
        PREDICT["predict(PC, inst)"]
        UPDATE["update(PC, taken, target)"]
        SQUASH["squash(seqNum)"]
    end
    subgraph Conditional["Conditional Predictors"]
        TWOBIT["LocalBP\n2bit_local.hh"]
        TOURN["TournamentBP\ntournament.hh"]
        BIMODE["BiModeBP\nbi_mode.hh"]
        GSHARE["GShareBP\ngshare.hh"]
        TAGE["TAGE\ntage.hh"]
        TAGESCL["TAGE_SC_L\ntage_sc_l.hh"]
        PERCEPT["MultiperspectivePerceptron\n*.hh"]
        LTAGE["LTAGE\nltage.hh"]
    end
    subgraph Target["Target Predictors"]
        BTB["BTB\nbtb.hh"]
        SBTB["SimpleBTB\nsimple_btb.hh"]
        IND["IndirectPredictor\nindirect.hh"]
        SIND["SimpleIndirectPredictor\nsimple_indirect.hh"]
    end
    subgraph Stack["Return Stack"]
        RAS["RAS\nras.hh"]
    end

    PREDICT --> BTB
    PREDICT --> TWOBIT
    PREDICT --> RAS
    PREDICT --> IND
    TWOBIT -.-> TOURN
    TOURN -.-> BIMODE
    BIMODE -.-> GSHARE
    GSHARE -.-> TAGE
    TAGE -.-> TAGESCL
    TAGESCL -.-> PERCEPT
    TAGE -.-> LTAGE
    BTB -.-> SBTB
    IND -.-> SIND

Prediction Flow

When the Fetch stage encounters a branch instruction, it queries BPredUnit::predict(). The prediction flow involves multiple lookups happening in parallel:

sequenceDiagram
    participant FE as Fetch Stage
    participant BPU as BPredUnit
    participant BTB as BTB
    participant COND as ConditionalPredictor
    participant RAS as RAS
    participant IND as IndirectPredictor

    FE->>BPU: predict(PC, staticInst)
    BPU->>BTB: lookup(PC)

    alt BTB hit — known branch
        BTB-->>BPU: target address, branch type
        alt Conditional branch
            BPU->>COND: lookup(PC, branchHistory)
            COND-->>BPU: taken / not-taken
        else Return instruction
            BPU->>RAS: pop()
            RAS-->>BPU: return address
        else Call instruction
            BPU->>RAS: push(PC + instSize)
            BPU->>COND: lookup(PC, branchHistory)
            COND-->>BPU: taken (calls usually taken)
        else Indirect jump
            BPU->>IND: lookup(PC, history)
            IND-->>BPU: predicted target
        end
    else BTB miss — unknown branch
        BTB-->>BPU: no entry
        Note over BPU: Predict not-taken (fall through)
    end

    BPU-->>FE: prediction result (taken, target)
    Note over FE: Store prediction in predHist for later update

    Note over FE,BPU: Later, when branch resolves at Commit:
    FE->>BPU: update(PC, actualTaken, actualTarget)
    BPU->>BTB: update(PC, target)
    BPU->>COND: update(PC, taken, history)

Key Classes

Class	Header	Responsibility
`BPredUnit`	`pred/bpred_unit.hh`	Top-level branch predictor wrapper. Coordinates BTB, conditional predictor, RAS, and indirect predictor. Maintains prediction history for speculative updates and rollback on squash.
`BTB`	`pred/btb.hh`	Branch Target Buffer: set-associative Cache Hierarchy \| gem5 Wiki" href="../../mem_doc/cache/index.html">cache mapping branch PCs to target addresses and branch types. Uses `BTBEntry` with tag, target, and type fields.
`SimpleBTB`	`pred/simple_btb.hh`	Simple BTB implementation: direct-mapped or set-associative lookup of branch targets.
`ConditionalPredictor`	`pred/conditional.hh`	Abstract base class for direction predictors. Defines `lookup()`, `update()`, and `squash()` interface.
`LocalBP`	`pred/2bit_local.hh`	Simple 2-bit saturating counter predictor indexed by PC. The simplest direction predictor — good for loops but poor on correlated branches.
`TournamentBP`	`pred/tournament.hh`	Hybrid predictor combining local and global history predictors with a choice table. Inspired by Alpha 21264. Adaptively selects the better predictor per branch.
`BiModeBP`	`pred/bi_mode.hh`	Bi-mode predictor that reduces aliasing by splitting branches into “taken-biased” and “not-taken-biased” groups.
`GShareBP`	`pred/gshare.hh`	GShare predictor: XORs global branch history with PC to index a table of 2-bit counters. Simple but effective global correlation predictor.
`TAGE`	`pred/tage.hh`	TAgged GEometric history length predictor. Uses multiple tables indexed by geometrically increasing history lengths. State-of-the-art accuracy.
`TAGEBase`	`pred/tage_base.hh`	Core TAGE algorithm implementation with provider/alternate selection and useful bit management.
`LTAGE`	`pred/ltage.hh`	Loop-TAGE: extends TAGE with a loop predictor that detects and predicts loop iteration counts.
`LoopPredictor`	`pred/loop_predictor.hh`	Loop iteration counter used by LTAGE. Detects loop exit patterns and predicts the last iteration.
`TAGE_SC_L`	`pred/tage_sc_l.hh`	TAGE with Statistical Corrector and Loop predictor. Championship-winning predictor (CBP-5). Highest accuracy available in gem5.
`StatisticalCorrector`	`pred/statistical_corrector.hh`	Corrects TAGE predictions using additional bias tables. Reduces systematic prediction errors.
`MultiperspectivePerceptron`	`pred/multiperspective_perceptron.hh`	Neural branch predictor using perceptron weights trained on multiple history features. Championship-class predictor.
`MultiperspectivePerceptronTAGE`	`pred/multiperspective_perceptron_tage.hh`	Hybrid combining multiperspective perceptron with TAGE tables for even higher accuracy.
`RAS`	`pred/ras.hh`	Return Address Stack: hardware stack that predicts return addresses by pushing on call and popping on return.
`IndirectPredictor`	`pred/indirect.hh`	Abstract base for indirect branch target predictors (e.g., virtual function dispatch, switch-case jump tables).
`SimpleIndirectPredictor`	`pred/simple_indirect.hh`	Tagged indirect predictor using global path history to predict indirect jump targets.

Predictor Algorithm Comparison

Algorithm	Type	History	Typical Accuracy	Storage Cost
`LocalBP`	Local	Per-branch 2-bit counter	~85–90%	Low (2 bits/entry)
`GShareBP`	Global	GHR XOR PC → counter table	~92–95%	Low–Medium
`TournamentBP`	Hybrid	Local + Global + Choice	~94–96%	Medium
`BiModeBP`	Global	Bi-modal split by bias direction	~93–95%	Medium
`TAGE`	Tagged geometric	Multiple geometric history lengths	~96–98%	Medium–High
`LTAGE`	TAGE + Loop	TAGE + loop iteration counter	~96.5–98%	Medium–High
`TAGE_SC_L`	TAGE + SC + Loop	TAGE + statistical corrector + loop	~97–99%	High
`MultiperspectivePerceptron`	Neural	Perceptron weights on multi-feature history	~96.5–98%	High

Cross-Module Interactions

Interaction	Pred Component	External Module	Mechanism
Fetch prediction	BPredUnit	o3::Fetch	`predict()` called each cycle for fetched branches
Commit update	BPredUnit	o3::Commit	`update()` with actual outcome when branch retires
Squash recovery	BPredUnit	o3::Commit	`squash()` to roll back speculative predictor state
Minor Fetch2	BPredUnit	minor::Fetch2	Same predict/update interface for in-order pipeline
Simple CPU	BPredUnit	BaseSimpleCPU	Optional predictor for accuracy measurement only
Pipeline — gem5 Wiki" class="xref">Statistics	BPredUnit	base/ stats	Tracks lookups, correct predictions, mispredictions, BTB hits/misses

Deep-Dive Topics

TAGE Geometric History

TAGE uses N tagged tables, each indexed by a different history length following a geometric series (e.g., 5, 10, 20, 40, 80, 160 bits). Longer histories capture far-reaching correlations, while shorter histories handle recent patterns. The provider component with the longest matching history wins.

Statistical Corrector

The SC in TAGE-SC-L is a secondary predictor that corrects systematic errors in the TAGE prediction. It uses additional small tables indexed by different features (bias, local history, global history) and adjusts the TAGE output when confidence is low.

Perceptron Learning

The multiperspective perceptron uses a vector of integer weights trained with a simple perceptron learning rule. The dot product of weights and history features determines the prediction. Weights are incremented/decremented based on correct/incorrect predictions.

Speculative State Management

Branch predictors maintain speculative state (global history register, RAS pointer). On a squash, this state must be rolled back. BPredUnit maintains a predHist deque that stores prediction records keyed by sequence number for rollback.

BTB Organization

The BTB is a set-associative cache with configurable sets and ways. Each entry stores the branch PC tag, target address, and branch type (conditional, unconditional, call, return, indirect). BTB misses cause the predictor to default to “not taken.”

Return Address Stack

The RAS is a circular stack that pushes the return address on function calls and pops on returns. Speculative calls/returns modify the RAS speculatively; the RAS checkpoint mechanism allows rollback on misprediction.

Directory Map

pred/ source tree

pred/
├── bpred_unit.hh / bpred_unit.cc                     ← BPredUnit: top-level predictor wrapper
├── btb.hh / btb.cc                                   ← BTB: branch target buffer
├── btb_entry.hh                                      ← BTBEntry: per-entry data structure
├── simple_btb.hh / simple_btb.cc                     ← SimpleBTB: basic BTB implementation
├── conditional.hh / conditional.cc                   ← ConditionalPredictor base class
├── branch_type.hh                                    ← Branch type classification enum
├── ras.hh / ras.cc                                   ← RAS: return address stack
├── indirect.hh / indirect.cc                         ← IndirectPredictor base class
├── simple_indirect.hh / simple_indirect.cc           ← Simple indirect branch predictor
├── 2bit_local.hh / 2bit_local.cc                     ← LocalBP: 2-bit saturating counters
├── gshare.hh / gshare.cc                             ← GShareBP: GHR XOR PC predictor
├── tournament.hh / tournament.cc                     ← TournamentBP: local/global hybrid
├── bi_mode.hh / bi_mode.cc                           ← BiModeBP: bi-modal direction split
├── tage_base.hh / tage_base.cc                       ← TAGEBase: core TAGE algorithm
├── tage.hh / tage.cc                                 ← TAGE predictor integration
├── ltage.hh / ltage.cc                               ← LTAGE: TAGE + loop predictor
├── loop_predictor.hh / loop_predictor.cc             ← Loop iteration predictor
├── tage_sc_l.hh / tage_sc_l.cc                       ← TAGE_SC_L: championship predictor
├── tage_sc_l_8KB.hh / .cc                            ← TAGE-SC-L 8KB budget variant
├── tage_sc_l_64KB.hh / .cc                           ← TAGE-SC-L 64KB budget variant
├── statistical_corrector.hh / .cc                    ← Statistical corrector tables
├── multiperspective_perceptron.hh / .cc              ← Base perceptron predictor
├── multiperspective_perceptron_8KB.hh / .cc          ← Perceptron 8KB variant
├── multiperspective_perceptron_64KB.hh / .cc         ← Perceptron 64KB variant
├── multiperspective_perceptron_tage.hh / .cc         ← Perceptron + TAGE hybrid
├── multiperspective_perceptron_tage_8KB.hh / .cc     ← Perceptron-TAGE 8KB
├── multiperspective_perceptron_tage_64KB.hh / .cc    ← Perceptron-TAGE 64KB
├── BranchPredictor.py                                ← Python configuration classes
└── SConscript                                        ← Build definitions

Configuration Parameters

Parameter	Predictor	Default	Description
`localPredictorSize`	LocalBP	2048	Number of 2-bit counters in local predictor table
`globalPredictorSize`	TournamentBP	8192	Entries in global predictor table
`choicePredictorSize`	TournamentBP	8192	Entries in local/global choice table
`localHistoryTableSize`	TournamentBP	2048	Per-branch local history table entries
`nHistoryTables`	TAGE	7	Number of tagged history tables
`minHist`	TAGE	5	Minimum history length (shortest table)
`maxHist`	TAGE	130	Maximum history length (longest table)
`tagTableTagWidths`	TAGE	[0,9,9,10,10,11,11,12]	Tag width per table for aliasing reduction
`numEntriesRAS`	BPredUnit	16	Return Address Stack depth
`BTBEntries`	BTB	4096	Number of BTB entries
`BTBTagSize`	BTB	16	BTB tag width in bits
`indirectBranchPred`	BPredUnit	SimpleIndirectPredictor	Indirect branch predictor implementation

Code Example: BPredUnit Predict

// Simplified view of BPredUnit::predict() from pred/bpred_unit.cc
bool BPredUnit::predict(const StaticInstPtr &inst, InstSeqNum seqNum,
                        PCStateBase &pc, ThreadID tid)
{
    BranchType brType = getBranchType(inst);
    bool btb_hit = btb->lookup(pc.instAddr(), brType, tid);

    bool pred_taken = false;
    const PCStateBase *target = nullptr;

    if (btb_hit) {
        target = btb->getTarget(pc.instAddr(), tid);

        if (inst->isReturn()) {
            // Use RAS for return prediction
            target = ras->pop(tid);
            pred_taken = true;
        } else if (inst->isCondCtrl()) {
            // Query conditional predictor
            pred_taken = condPredictor->lookup(pc.instAddr(),
                                                branchHistory);
        } else if (inst->isIndirectCtrl()) {
            // Query indirect predictor
            target = indirectPredictor->lookup(pc.instAddr(),
                                                branchHistory);
            pred_taken = true;
        } else {
            pred_taken = true;  // Unconditional branch
        }
    }

    if (inst->isCall())
        ras->push(pc.instAddr() + inst->size(), tid);

    // Record prediction for later update/squash
    predHist[tid].emplace_front(seqNum, pred_taken,
                                 condPredictor->getState(), ...);
    return pred_taken;
}