Skip to content

Enhanced Branch Predictor for EDM Demonstration

Jump to bottom
Komal Kumavat edited this page Apr 6, 2026 · 1 revision

The Enhanced Branch Predictor demonstrates EDM's value by creating realistic mispredictions that expose speculative execution effects invisible to trace-driven simulation.

Key Result: By using hardware-realistic constraints (256-entry BTB, 512-entry BHT, LRU replacement), accuracy drops from 95% to 75%, generating mispredictions that trigger wrong-path execution and cache pollution - effects only EDM can capture. This results in 8-10% IPC degradation between trace and EDM modes.

Why Enhanced Branch Predictor Matters

Trace-driven simulation cannot capture the performance impact of branch mispredictions because traces only contain the correct execution path. When branches mispredict in real hardware:

  1. Wrong-Path Instruction Fetches: The processor fetches instructions from the incorrect path, polluting the instruction cache
  2. Wrong-Path Data Accesses: Speculative loads bring wrong data into the data cache
  3. Pipeline Flush: When the misprediction is detected, the pipeline must be flushed
  4. Cache Pollution Persists: Even after flush, the polluted cache affects subsequent correct-path performance

The Problem with SimpleBranchPredictor:

// SimpleBranchPredictor.hpp - Current Implementation
std::map<uint64_t, uint8_t> branch_history_table_;   // UNLIMITED capacity
std::map<uint64_t, BTBEntry> branch_target_buffer_;  // UNLIMITED capacity
  • Unlimited capacity -> optimistic prediction behavior (often very high on repeated traces)
  • Too few mispredictions -> cannot demonstrate EDM value
  • Traces can look materially better than execution-driven behavior on branch-sensitive code

Our Solution:

Limited BTB (256 entries) + Limited BHT (512 entries) + LRU replacement -> target 70-85% accuracy (to be validated) -> realistic mispredictions -> demonstrates cache pollution effects that EDM captures but traces miss.

Design Goals

  1. Demonstrate EDM Value - Create realistic mispredictions that expose cache pollution and performance impact invisible to traces
  2. Hardware Realism - Bounded structures (256-entry BTB, 512-entry BHT) with LRU replacement
  3. Sparta Integration - Use SimpleCache2 for BTB and ReplacementFactory for LRU (same pattern as DCache/ICache)
  4. Configurability - YAML parameters for experimentation

Architecture Overview

High-Level Design

The Enhanced Branch Predictor consists of three main components working together:

graph TB
    subgraph "Enhanced Branch Predictor"
        BP[Prediction Logic]
        BTB[BTB Cache<br/>256 entries<br/>128 sets x 2-way<br/>LRU replacement]
        BHT[BHT Counters<br/>512 entries<br/>2-bit saturating<br/>Direct-mapped]
        LRU[LRU Policy<br/>ReplacementFactory]
    end

    F[Fetch Unit] -->|predict request| BP
    BP -->|lookup PC| BTB
    BP -->|lookup PC| BHT
    BTB -->|eviction| LRU
    LRU -->|victim| BTB
    BP -->|prediction + target| F
    F -->|actual outcome| BP
    BP -->|update| BTB
    BP -->|update| BHT

    style BTB fill:#ffeb99
    style BHT fill:#ffeb99
    style LRU fill:#ff9999
    style BP fill:#90EE90
Loading

Component Responsibilities

BTB (Branch Target Buffer)

  • Stores where branches jump to
  • 256 entries organized as 128 sets x 2-way set-associative
  • LRU replacement per set
  • Uses Sparta SimpleCache2

BHT (Branch History Table)

  • Stores 2-bit counters for taken/not-taken prediction
  • 512 entries, direct-mapped
  • Simple array implementation

Prediction Logic

  • Coordinates BTB/BHT lookups
  • Handles updates from Execute
  • Collects statistics

LRU Policy

  • Evicts least-recently-used entries when BTB is full
  • Sparta ReplacementFactory

Why These Constraints Create Realistic Mispredictions

graph TD
    A[Small BTB: 256 entries] --> B[Capacity Conflicts]
    B --> C[BTB Misses]
    C --> D[Default: Predict Not-Taken]

    E[Limited BHT: 512 entries] --> F[Multiple Branches<br/>Map to Same Counter]
    F --> G[Counter Confusion]
    G --> H[Wrong Direction Prediction]

    I[LRU Replacement] --> J[Old Branches Evicted]
    J --> K[Cold Misses on Return]

    D --> L[Mispredictions]
    H --> L
    K --> L
    L --> M[Target: 70-85% Accuracy<br/>vs Optimistic Unlimited Baseline]

    style M fill:#ff9999
Loading

BTB Design

Structure

  • Total Entries: 256
  • Organization: 128 sets x 2-way set-associative
  • Replacement: LRU per set
  • Implementation: Sparta SimpleCache2

Indexing Scheme

graph LR
    A["Branch PC<br/>0x1234_5678"] --> B["Extract Bits"]
    B --> C["PC[0]<br/>Byte Offset<br/>(Ignore)"]
    B --> D["PC[9:1]<br/>Set Index<br/>(7 bits = 128 sets)"]
    B --> E["PC[63:10]<br/>Tag<br/>(Match in set)"]

    D --> F["Select 1 of 128 Sets"]
    F --> G["Search 2 Ways<br/>for Matching Tag"]
    E --> G
    G --> H{Match?}
    H -->|Yes| I[BTB Hit<br/>Return Target]
    H -->|No| J[BTB Miss<br/>Predict Not-Taken]

    style I fill:#90EE90
    style J fill:#ff9999
Loading

Indexing Example:

PC = 0x1234_5678
Index = (0x1234_5678 >> 1) & 0x7F = Set 60
Tag   = 0x1234_5678 >> 10 = 0x48D159

Implementation

class EnhancedBranchPredictor :
    public BranchPredictorIF<DefaultPrediction, DefaultUpdate, DefaultInput> {
private:
    struct BTBEntry : public sparta::cache::BasicCacheItem {
        Addr target_pc;  // Resolved target PC for this branch

        void reset(uint64_t addr) override {
            setValid(true);
            setAddr(addr);  // Use branch PC as the cache tag
        }
    };

    std::unique_ptr<sparta::cache::SimpleCache2<BTBEntry>> btb_cache_;
    std::unique_ptr<sparta::cache::ReplacementIF> replacement_policy_;

    void initializeBTB_() {
        // Reuse the same replacement-policy setup used in caches.
        replacement_policy_ = ReplacementFactory::selectReplacementPolicy(
            "LRU", config_.btb_ways);

        // SimpleCache2 gives us set-associative BTB behavior plus LRU hooks.
        btb_cache_ = std::make_unique<sparta::cache::SimpleCache2<BTBEntry>>(
            (config_.btb_entries * sizeof(Addr)) >> 10,  // Total size in KB
            sizeof(Addr),           // Line size = 8 bytes (one address)
            sizeof(Addr),           // Block size = 8 bytes
            BTBEntry(),             // Default entry template
            *replacement_policy_);  // LRU policy we just created
    }

    bool btbLookup_(Addr pc, Addr& target) {
        // Tag lookup without changing LRU state.
        auto* line = btb_cache_->peekLine(pc);
        if (line && line->isValid()) {
            // Hit: return target and refresh recency.
            target = line->target_pc;
            btb_cache_->touch(pc);
            return true;
        }
        return false;  // Miss: no known target yet
    }

    void btbUpdate_(Addr pc, Addr target) {
        // Pick a replacement line (evicts LRU if the set is full).
        auto& line = btb_cache_->getLineForReplacement(pc);

        // Allocate and mark the new line as MRU.
        btb_cache_->allocateWithMRUUpdate(line, pc);

        // Store the resolved target.
        line.target_pc = target;
    }
};

BHT Design

Structure

  • Total Entries: 512
  • Indexing: Direct-mapped using (pc >> 1) & (bht_entries - 1) (PC[9:1] when bht_entries = 512)
  • Counter: 2-bit saturating (0-3)

Counter States

00 = Strongly Not-Taken
01 = Weakly Not-Taken
10 = Weakly Taken
11 = Strongly Taken

State Machine

stateDiagram-v2
    [*] --> 01
    00 --> 00: Not-Taken
    00 --> 01: Taken
    01 --> 00: Not-Taken
    01 --> 10: Taken
    10 --> 01: Not-Taken
    10 --> 11: Taken
    11 --> 10: Not-Taken
    11 --> 11: Taken
Loading

Implementation

class EnhancedBranchPredictor :
    public BranchPredictorIF<DefaultPrediction, DefaultUpdate, DefaultInput> {
private:
    std::vector<uint8_t> bht_counters_;  // 2-bit counters (0-3)

    void initializeBHT_() {
        // Start at weakly-not-taken.
        bht_counters_.resize(config_.bht_entries, 1);
    }

    uint32_t bhtIndex_(Addr pc) const {
        // With 512 entries, this maps to PC[9:1] and handles compressed/regular fetch addresses.
        return (pc >> 1) & (config_.bht_entries - 1);
    }

    bool bhtPredict_(Addr pc) {
        uint32_t index = bhtIndex_(pc);
        // 00/01 -> not taken, 10/11 -> taken.
        return bht_counters_[index] >= 2;
    }

    void bhtUpdate_(Addr pc, bool taken) {
        uint32_t index = bhtIndex_(pc);
        uint8_t& counter = bht_counters_[index];

        if (taken && counter < 3) {
            counter++;  // Move toward strongly taken (11)
        } else if (!taken && counter > 0) {
            counter--;  // Move toward strongly not-taken (00)
        }
        // Saturation avoids wrap-around and keeps hysteresis stable.
    }
};

Prediction Algorithm

Prediction Flow

The prediction algorithm coordinates BTB and BHT lookups to make branch predictions:

graph TB
    Start[Branch at PC] --> BTB{BTB Lookup<br/>PC bits 9:1}

    BTB -->|Hit| BHT{BHT Counter<br/>PC bits 9:1, 512-entry BHT}
    BTB -->|Miss| NT[Predict Not-Taken<br/>No Target Known]

    BHT -->|Greater or Equal 2<br/>Taken| T[Predict Taken<br/>Use BTB Target]
    BHT -->|Less than 2<br/>Not-Taken| NT

    T --> LRU[Update LRU<br/>Mark as MRU]
    LRU --> End[Return Prediction]
    NT --> End

    style T fill:#90EE90
    style NT fill:#ffeb99
    style BTB fill:#e1f5ff
    style BHT fill:#fff9c4
Loading

Algorithm Steps:

  1. BTB Lookup: Use PC[9:1] to index into BTB cache

    • If miss -> we've never seen this branch -> predict not-taken
    • If hit -> we know the target address -> proceed to step 2

  2. BHT Lookup: Use (PC >> 1) & (bht_entries - 1) to get 2-bit counter

    • With 512 BHT entries, this resolves to PC[9:1]
    • Counter >= 2 (10 or 11) -> predict taken, use BTB target
    • Counter < 2 (00 or 01) -> predict not-taken

  3. LRU Update: On BTB hit, mark entry as most recently used

  4. Return: Prediction (taken/not-taken) + target address (if taken)

Detailed Prediction Flowchart

This flowchart shows the complete decision process including all edge cases:

flowchart LR
    Start([Fetch Requests<br/>Branch Prediction]) --> GetPC[Get Branch PC]

    GetPC --> CalcBTBIdx["Calculate BTB Index<br/>index = (PC >> 1) & 0x7F<br/>(7 bits for 128 sets)"]

    CalcBTBIdx --> CalcBTBTag["Calculate BTB Tag<br/>tag = PC >> 10"]

    CalcBTBTag --> SearchBTB{Search BTB Set<br/>for Matching Tag}

    SearchBTB -->|No Match| BTBMiss[BTB Miss]
    SearchBTB -->|Match Found| BTBHit[BTB Hit]

    BTBMiss --> DefaultNT["Default Prediction:<br/>NOT TAKEN<br/>(no target known)"]
    DefaultNT --> ReturnNT[Return: taken=false]

    BTBHit --> GetTarget["Extract Target PC<br/>from BTB Entry"]
    GetTarget --> TouchLRU["Update LRU:<br/>Mark Entry as MRU"]

    TouchLRU --> CalcBHTIdx["Calculate BHT Index<br/>index = (PC >> 1) & 0x1FF<br/>(9 bits for 512 entries)"]

    CalcBHTIdx --> ReadCounter["Read 2-bit Counter<br/>from BHT[index]"]

    ReadCounter --> CheckCounter{Counter Value?}

    CheckCounter -->|00 or 01<br/>Not-Taken| PredictNT["Predict NOT TAKEN<br/>(ignore BTB target)"]
    CheckCounter -->|10 or 11<br/>Taken| PredictT["Predict TAKEN<br/>(use BTB target)"]

    PredictNT --> ReturnNT2[Return: taken=false]
    PredictT --> ReturnT[Return: taken=true,<br/>target=BTB_target]

    ReturnNT --> Stats1[Increment<br/>total_predictions_]
    ReturnNT2 --> Stats1
    ReturnT --> Stats1

    Stats1 --> End([Prediction Complete])

    style BTBMiss fill:#ffcdd2
    style BTBHit fill:#c8e6c9
    style PredictT fill:#a5d6a7
    style PredictNT fill:#ffecb3
    style DefaultNT fill:#ffecb3
Loading

Update Flow

After the branch resolves in Execute, the predictor is updated with the actual outcome:

flowchart LR
    Start([Execute Resolves<br/>Branch]) --> GetActual["Get Actual Outcome:<br/>PC, taken, target"]

    GetActual --> CalcBHTIdx["Calculate BHT Index<br/>index = (PC >> 1) & 0x1FF"]

    CalcBHTIdx --> ReadCounter["Read Current Counter<br/>counter = BHT[index]"]

    ReadCounter --> CheckOutcome{Actual<br/>Outcome?}

    CheckOutcome -->|Taken| IncCounter{Counter < 3?}
    CheckOutcome -->|Not-Taken| DecCounter{Counter > 0?}

    IncCounter -->|Yes| Inc["counter++<br/>(move toward 11)"]
    IncCounter -->|No| Saturate1["Stay at 11<br/>(saturated)"]

    DecCounter -->|Yes| Dec["counter--<br/>(move toward 00)"]
    DecCounter -->|No| Saturate0["Stay at 00<br/>(saturated)"]

    Inc --> WriteBHT[Write Updated<br/>Counter to BHT]
    Dec --> WriteBHT
    Saturate1 --> WriteBHT
    Saturate0 --> WriteBHT

    WriteBHT --> CheckTaken{Was Branch<br/>Taken?}

    CheckTaken -->|No| SkipBTB[Skip BTB Update<br/>No target to store]
    CheckTaken -->|Yes| UpdateBTB["Update BTB:<br/>Store PC -> target mapping"]

    UpdateBTB --> CheckEviction{BTB Set Full?}

    CheckEviction -->|No| AllocateNew[Allocate New Entry]
    CheckEviction -->|Yes| EvictLRU["Evict LRU Entry<br/>from Set"]

    EvictLRU --> AllocateNew
    AllocateNew --> StoreTarget["Store target_pc<br/>Mark as MRU"]

    StoreTarget --> UpdateStats
    SkipBTB --> UpdateStats[Update Statistics]

    UpdateStats --> CheckAccuracy["Compare Prediction<br/>vs Actual"]

    CheckAccuracy --> RecordStats["Increment:<br/>correct_predictions_<br/>or mispredictions_"]

    RecordStats --> End([Update Complete])

    style Inc fill:#c8e6c9
    style Dec fill:#ffecb3
    style EvictLRU fill:#ffcdd2
    style StoreTarget fill:#c8e6c9
Loading

Implementation

DefaultPrediction EnhancedBranchPredictor::getPrediction(const DefaultInput& input) {
    ++total_predictions_;

    DefaultPrediction prediction;
    // Default to fall-through in the current fetch window.
    prediction.branch_idx = max_fetch_insts_;
    prediction.predicted_PC = input.fetch_PC + max_fetch_insts_ * bytes_per_inst;

    Addr target;
    // Use BTB target only on BTB hit + BHT taken.
    if (btbLookup_(input.fetch_PC, target) && bhtPredict_(input.fetch_PC)) {
        prediction.predicted_PC = target;
    }

    // Save the fetch-time decision for resolve-time accounting.
    // Using fetch_PC here is a simplification; production code should use an
    // in-flight token to avoid collisions on repeated PCs.
    pending_predictions_[input.fetch_PC] = prediction;
    return prediction;
}

void EnhancedBranchPredictor::updatePredictor(const DefaultUpdate& update) {
    // Recover the exact prediction made at fetch time.
    const auto it = pending_predictions_.find(update.fetch_PC);
    const bool had_prediction = (it != pending_predictions_.end());

    // Compare before training so stats reflect true prediction behavior.
    if (had_prediction) {
        const auto& old_pred = it->second;
        const bool predicted_taken = (old_pred.predicted_PC !=
            (update.fetch_PC + old_pred.branch_idx + bytes_per_inst));
        // Target match matters only for actually taken branches.
        const bool target_match = (!update.actually_taken) ||
            (old_pred.predicted_PC == update.corrected_PC);

        if (predicted_taken == update.actually_taken && target_match) {
            ++correct_predictions_;
        } else {
            ++mispredictions_;
        }

        pending_predictions_.erase(it);
    }

    // Train predictor state using resolved outcome.
    bhtUpdate_(update.fetch_PC, update.actually_taken);
    if (update.actually_taken) {
        btbUpdate_(update.fetch_PC, update.corrected_PC);
    }
}

Why This Design Works

  • Capacity pressure: Bounded BTB with LRU creates realistic misses and evictions.
  • Aliasing pressure: Finite BHT entries cause branch interference on shared counters.
  • Pattern limitations: 2-bit counters naturally miss hard transitions like loop exits.
  • EDM relevance: These effects increase wrong-path activity, making cache-impact trends visible.

Integration with EDM

The Problem with Traces

Traces only capture correct execution path - they miss what happens when branches mispredict:

graph TB
    subgraph Trace["Trace Mode - Looks Good"]
        direction LR
        T1[Branch] --> T2[Correct Path Only] --> T3[No Wrong-Path<br/>No Cache Pollution]
    end

    subgraph EDM["EDM Mode - Shows Reality"]
        direction LR
        E1[Branch<br/>Mispredicts] --> E2[Wrong Instructions<br/>Pollute I-Cache] --> E3[Wrong Data<br/>Pollutes D-Cache] --> E4[Flush<br/>Pipeline] --> E5[Correct Path<br/>Suffers Pollution]
    end

    Trace -.->|vs| EDM

    style T3 fill:#90EE90
    style E5 fill:#ff9999
Loading

Misprediction Flow

sequenceDiagram
    participant F as Fetch
    participant BP as EnhancedBranchPredictor
    participant E as EDMInstGenerator
    participant P as Pegasus
    participant IC as I-Cache

    Note over F,P: Branch at 0x1000
    F->>E: getNextInst()
    E->>P: step()
    P-->>E: branch (correct=0x1004, alt=0x2000)
    E->>E: saveCheckpoint(0x1004)
    E-->>F: branch instruction

    F->>BP: predict(0x1000)
    BP->>BP: BTB hit -> target=0x2000
    BP->>BP: BHT counter=11 (strongly taken)
    BP-->>F: PREDICT TAKEN -> 0x2000

    Note over F: MISPREDICTION!<br/>Predicted 0x2000, should be 0x1004

    F->>E: getNextInst()
    E->>P: stepWithOverridePc(0x2000)
    Note over P: Execute WRONG PATH
    P->>IC: Fetch instructions at 0x2000
    Note over IC: POLLUTION!<br/>Wrong-path code in cache
    P-->>E: wrong-path instruction
    E-->>F: InstPtr

    Note over F: Branch resolves in Execute
    Note over F: Actual: NOT TAKEN -> 0x1004

    F->>E: reset(branch)
    E->>P: flush(checkpoint)
    Note over P: Rewind to 0x1004
    Note over IC: Pollution remains!<br/>Hurts future performance

    F->>BP: update(0x1000, taken=false, 0x1004)
    BP->>BP: BHT: 11 -> 10 (decrement)
Loading

Cache Pollution Visualization

graph LR
    subgraph Before["1. Before Misprediction"]
        B1[I-Cache Clean<br/>Correct-Path Code]
    end

    subgraph During["2. Wrong-Path Execution"]
        W1[Fetch 0x2000] --> W2[Wrong Instructions<br/>Evict Correct Code] --> W3[I-Cache Polluted]
    end

    subgraph After["3. After Flush"]
        A1[Resume 0x1004] --> A2[Need Code 0x1050] --> A3[I-Cache Miss!<br/>Evicted by Wrong-Path] --> A4[Performance Hit]
    end

    B1 --> W1
    W3 --> A1

    style B1 fill:#90EE90
    style W3 fill:#ffeb99
    style A4 fill:#ff9999
Loading

Performance Impact Summary

Branch mispredictions add both immediate control-flow cost (flush and re-fetch) and delayed cache cost (wrong-path pollution). Trace mode under-observes this path, while EDM can capture it. Final magnitude remains to be measured in integration runs.

Expected Results

EDM Validation Status (Pending)

  • EDM + Simple predictor comparison: pending
  • EDM + Enhanced predictor comparison: pending
  • Final IPC delta and cache-pollution impact quantification: pending
graph LR
    A[Trace + Simple<br/>Measured Baseline] -->|Reference Point| B[Current State]
    C[EDM + Simple<br/>Pending Measurement] -->|Initial Delta| D[Integration Check]
    E[EDM + Enhanced<br/>Pending Measurement] -->|Higher Mispredict Pressure| F[Hypothesized Clearer Impact]

    style B fill:#90EE90
    style D fill:#ffeb99
    style F fill:#ff9999
Loading

Configuration

Sparta Parameters

class EnhancedBranchPredictor : public sparta::Unit {
public:
    struct Config {
        uint32_t btb_entries = 256;
        uint32_t btb_ways = 2;
        uint32_t bht_entries = 512;
        std::string replacement_policy = "LRU";
    };

    // Parameter block consumed from YAML/Sparta config.
    sparta::ParameterSet params_;
};

YAML Configuration

top.cpu.core0.fetch.branch_predictor:
  type: enhanced

  btb:
    entries: 256
    ways: 2
    replacement_policy: LRU

  bht:
    entries: 512
    counter_bits: 2
    initial_state: 1  # Weakly not-taken

  presets:
    realistic:
      btb_entries: 256
      bht_entries: 512

    optimistic:
      btb_entries: 1024
      bht_entries: 2048

    pessimistic:
      btb_entries: 64
      bht_entries: 128

Class Structure

namespace olympia {

class EnhancedBranchPredictor :
    public BranchPredictorIF<DefaultPrediction, DefaultUpdate, DefaultInput>,
    public sparta::Unit {
public:
    // Runtime configuration (YAML-backed).
    struct Config {
        uint32_t btb_entries = 256;              // Total BTB entries
        uint32_t btb_ways = 2;                   // Set associativity
        uint32_t bht_entries = 512;              // Total BHT entries
        std::string replacement_policy = "LRU";  // Replacement policy
    };

    // Sets up BTB, BHT, and stats counters.
    EnhancedBranchPredictor(sparta::TreeNode* node, const Config& config);

    // Main branch-predictor API.
    DefaultPrediction getPrediction(const DefaultInput& input) override;
    void updatePredictor(const DefaultUpdate& update) override;

    // Optional helper used in design examples.
    bool predictBranchPseudo(Addr branch_pc, Addr& predicted_target);

    // Stats accessors.
    uint64_t getTotalPredictions() const;
    uint64_t getMispredictions() const;
    double getAccuracy() const;

private:
    // BTB helpers.

    // BTB lookup; updates LRU state on hit.
    bool btbLookup_(Addr pc, Addr& target);

    // BTB insert/update; evicts LRU when needed.
    void btbUpdate_(Addr pc, Addr target);

    // BHT helpers.

    // BHT direction prediction.
    bool bhtPredict_(Addr pc);

    // BHT training with saturating counters.
    void bhtUpdate_(Addr pc, bool taken);

    // BHT index calculation.
    uint32_t bhtIndex_(Addr pc) const;

    Config config_;

    // BTB storage.
    std::unique_ptr<sparta::cache::SimpleCache2<BTBEntry>> btb_cache_;
    std::unique_ptr<sparta::cache::ReplacementIF> replacement_policy_;

    // BHT storage.
    std::vector<uint8_t> bht_counters_;

    // Core predictor counters.
    sparta::Counter total_predictions_;   // Total predictions made
    sparta::Counter mispredictions_;      // Incorrect predictions
    sparta::Counter btb_hits_;            // BTB lookups that hit
    sparta::Counter btb_misses_;          // BTB lookups that missed
};

}

Comparison: SimpleBranchPredictor vs Enhanced

Feature SimpleBranchPredictor EnhancedBranchPredictor
BTB Structure std::map (unlimited) 128 sets x 2-way (256 entries)
BHT Structure std::map (unlimited) Direct-mapped (512 entries)
Replacement None LRU
Indexing fetch_PC keyed maps (no explicit set index) PC[9:1] (compressed support)
Configurability None Full YAML config
Accuracy Typically optimistic on repeated traces Target 70-85% after EDM validation (pending)
Memory Unbounded 2KB BTB + 512B BHT
Realism Low High
EDM Value Hard to demonstrate consistently Hypothesized visible IPC gap; final value pending measurement

Future Enhancements

Conditional BHT Update

Currently, the BHT is updated for all branches, even those not in the BTB. This can cause counter pollution when not-taken branches that aren't tracked in the BTB alias with taken branches that are tracked.

Current Approach:

void updatePredictor(const DefaultUpdate& update) {
    bhtUpdate_(update.fetch_PC, update.actually_taken);  // Always update
    if (update.actually_taken) {
        btbUpdate_(update.fetch_PC, update.corrected_PC);
    }
}

Alternative Approach:

void updatePredictor(const DefaultUpdate& update) {
    Addr dummy_target;
    if (btbLookup_(update.fetch_PC, dummy_target)) {
        bhtUpdate_(update.fetch_PC, update.actually_taken);  // Only update if in BTB

    }
    if (update.actually_taken) {
        btbUpdate_(update.fetch_PC, update.corrected_PC);
    }
}

This reduces BHT pollution and may improve accuracy by 2-3%.

Global History Register (GHR)

A Global History Register tracks recent branch outcomes across all branches, improving prediction for correlated branches:

class EnhancedBranchPredictor {
private:
    uint32_t ghr_;  // Last 8 branch outcomes

    uint32_t bhtIndex_(Addr pc) const {
        return ((pc >> 1) ^ ghr_) & (config_.bht_entries - 1);
    }

    void bhtUpdate_(Addr pc, bool taken) {
        uint32_t index = bhtIndex_(pc);
        // Update counter...

        // Shift in the latest branch result.
        ghr_ = ((ghr_ << 1) | (taken ? 1 : 0)) & 0xFF;
    }
};

Expected accuracy improvement: 5-8% for workloads with correlated branches.

Return Address Stack (RAS)

Dedicated stack for function returns provides near-perfect return prediction:

class EnhancedBranchPredictor {
private:
    std::vector<Addr> ras_;
    size_t ras_top_ = 0;

    void handleCall(Addr return_addr) {
        ras_[ras_top_] = return_addr;
        ras_top_ = (ras_top_ + 1) % RAS_SIZE;
    }

    Addr handleReturn() {
        ras_top_ = (ras_top_ - 1 + RAS_SIZE) % RAS_SIZE;
        return ras_[ras_top_];
    }
};

Eliminates BTB pollution from function returns and improves return prediction accuracy.

RISC-V Performance Model

Clone this wiki locally