Intel & AMD CPU Architecture · Part 2 · Module 7

Branch Prediction

Two-level predictors, TAGE, BTB, speculative execution

25 min read

1. CONCEPTUAL FOUNDATION#

Branch prediction is the single most critical microarchitectural component for hiding pipeline latency. A single misprediction on a 14-20 stage pipeline costs 15-20 cycles, equivalent to 50-100 instructions of work lost to speculative execution recovery. Modern processors dedicate 5-10% of chip area to branch prediction hardware, reflecting its importance.

Why Branch Prediction Matters: The Penalty Structure#

Without prediction, branches incur 3-4 cycle latency (time from fetch to next PC known):

Text
In-order pipeline (5-stage):
Cycle: 1  2  3  4  5
BR:    IF ID EX MEM WB  ← next PC resolved here (cycle 4, MEM stage)

Fetch must stall at cycle 1 (cannot fetch next instruction until cycle 4 result)
Penalty: 3 cycles minimum (cycles 1-3 cannot progress to next instruction)

Modern deep pipelines (14-19 stages) worsen this:

Text
Modern pipeline (14-stage):
Cycle: 1  2  3  4  5  6  7  8  9  10 11 12 13 14
BR:    IF ID D1 D2 EX E2 E3 E4 MEM MEM MEM WB

Next PC resolved at cycle 13 (MEM stage)
Fetch stalls cycles 1-12: 12-cycle latency (unacceptable)

Solution: Predict the next PC at fetch time, fetch speculatively. If prediction correct, zero penalty. If mispredicted, flush all speculatively fetched instructions and restart.

Text
With branch prediction:
Cycle: 1  2  3  4  5  6  7  8  9  10
BR:    IF ID D1 D2 EX E2 E3 E4 MEM MEM
Next I: IF ID D1 D2 EX E2 E3 E4 MEM MEM (predicted, continue fetching)

If prediction correct: Next instruction proceeds uninterrupted (zero penalty)
If mispredicted: Flush cycles 2-9, restart from correct PC (8-cycle penalty minimum)

Modern: 14-20 stage pipeline → misprediction flushes 14-20 cycles of work
Cost: 14-20 instructions worth of execution time

Static Prediction: The Baseline#

Static prediction uses heuristics, not runtime history:

  1. Always predict taken: Good for backward branches (loops), bad for forward branches (conditionals)

    • Loop back branch: 95%+ taken, static prediction is correct
    • Exit condition: 5% not taken, static prediction is wrong
  2. Always predict not taken: Good for forward branches, bad for backward

    • Exception handlers: Usually not taken, static prediction is correct
    • Loop exit: Usually not taken (until last iteration), static prediction is correct
  3. OPCODE-based prediction: Branch type determines prediction

    • Conditional branches (forward): Predict not taken
    • Loop branches (backward): Predict taken
    • Calls: Always taken (call destination known from instruction encoding)

Static prediction accuracy: 50-70% for general code (good guess, but poor)

1-Bit and 2-Bit Saturating Counters#

A simple 1-bit predictor stores one bit per branch: "last time taken or not?"

C
// 1-bit predictor: branch history table (BHT) with 1 bit per entry
struct BHT_1bit {
    unsigned char taken[4096];  // 4096 entries, 1 bit each
};

// On predict:
int predict(unsigned int pc) {
    int entry = (pc >> 2) % 4096;  // Hash PC to table entry
    return taken[entry];           // Return 1-bit prediction
}

// On execution (learn):
void update(unsigned int pc, int was_taken) {
    int entry = (pc >> 2) % 4096;
    taken[entry] = was_taken;      // Update prediction for next time
}

// Example: Loop branch
// Iteration 1-999: BR is taken, update to 1
// Iteration 1000 (exit): BR is not taken, update to 0
// Iteration 1001: Predict 0 (correct, loop exited)
// But when looping again: Predict 0 (WRONG, loop will be taken again)
// Cost: 1 misprediction per loop restart (entry/exit pattern)

1-bit predictor drawback: Oscillates for branches with alternating pattern (taken, not-taken, taken, not-taken):

Text
History:    T   N   T   N   T   N
1-bit pred: T   N   T   N   T   N  (always wrong on transition)
Accuracy: 50% (every transition causes misprediction)

2-bit saturating counter fixes this:

C
struct BHT_2bit {
    unsigned char counter[4096];  // 2-bit counter per entry (0-3)
    // Counter values: 0=strongly not taken, 1=weakly not taken,
    //                 2=weakly taken, 3=strongly taken
};

void predict(unsigned int pc) {
    int entry = pc % 4096;
    return (counter[entry] >= 2) ? 1 : 0;  // Predict taken if counter >= 2
}

void update(unsigned int pc, int was_taken) {
    int entry = pc % 4096;
    if (was_taken && counter[entry] < 3) counter[entry]++;
    else if (!was_taken && counter[entry] > 0) counter[entry]--;
}

// Example: Alternating pattern (TNTNTN...)
// Initial: counter = 2 (weakly taken)
// Iteration 1: T (taken), counter stays 2 (weakly taken)
//   - Predict taken ✓ (but pattern is T, so correct)
// Iteration 2: N (not taken), counter → 1 (weakly not taken)
//   - Predict taken ✗ (misprediction, but counter moving toward not-taken)
// Iteration 3: T (taken), counter → 2 (weakly taken)
//   - Predict taken ✓
// Iteration 4: N (not taken), counter → 1
//   - Predict taken ✗ (misprediction once per pair)
// Accuracy: 50% (but counter is "slowly" tracking pattern)

2-bit predictor prevents flipping on single mispredictions (requires 2 consecutive mispredictions to flip). Accuracy improves to 80-85% on real code.

Global and Local History Predictors#

Global history predictor (GH): Uses the global branch history register (BHR), tracking the last N branches globally:

Text
GHR = 64-bit register storing outcomes of last 64 branches (all branches globally)
BHR = "Tnnn...T" (T = taken, n = not taken), most recent on left

Prediction:
    entry = (PC ^ GHR) % table_size  // XOR PC with global history
    predict = table[entry]

Example:
    GHR = 1010101... (alternating taken/not-taken)
    PC = 0x12345678
    entry = (0x12345678 ^ 0x5555...) % 4096
    predict = table[entry]

Learn:
    Update table[entry] based on actual outcome
    Update GHR: shift left, insert new outcome

Global history advantage: Detects correlations between branches

  • If global history shows "most recent branches are not taken," predict next as not-taken
  • Captures pattern: "when these branches went this way, this branch usually goes that way"

Local history predictor (LH): Uses per-branch history:

C
struct LocalPredictor {
    unsigned char history[4096];    // Per-branch history table
    unsigned char pattern_table[4096][256];  // Pattern table
};

// history[pc] stores the recent history of that specific branch
// pattern_table[pc][history] stores prediction for that history pattern

int predict(unsigned int pc) {
    int hist = history[pc % 4096];
    int entry = pattern_table[pc % 4096][hist];
    return entry & 1;
}

void update(unsigned int pc, int was_taken) {
    int hist = history[pc % 4096];
    int pindex = pc % 4096;

    // Update pattern table for this history
    if (was_taken) pattern_table[pindex][hist]++;
    else if (pattern_table[pindex][hist] > 0) pattern_table[pindex][hist]--;

    // Update history table (shift and insert)
    history[pindex] = ((hist << 1) | was_taken) & 0xff;  // Keep 8-bit history
}

Local history advantage: Detects per-branch patterns

  • If a specific branch alternates taken/not-taken, history tracks that pattern locally
  • Other branches' histories don't interfere

TAGE Predictor: State-of-the-Art (Tagged Geometric History)#

Modern processors (Intel Skylake, AMD Zen 4) use TAGE (Tagged Geometric History Length) predictors, which combine global history with varying history lengths:

Diagram
Loading…

TAGE success rates: 95-99% accuracy on typical x86 code, 90-95% on branches with complex dependencies.

Citation: Mutlu lectures on branch prediction, Agner Fog microarchitecture manual Chapter 3.

Indirect Branch Prediction (Return Address Stack, vtable dispatch)#

Indirect branches (vtable lookups, function pointers, returns) are harder to predict because the target is computed at runtime:

C
// Direct branch (easy): target known at encode time
if (condition) goto label;  // Target = &label, known at compile time

// Indirect branch (hard): target computed at runtime
void (*fn_ptr)(void) = condition ? &func_a : &func_b;  // Unknown until runtime
fn_ptr();  // Branch to computed target

Return address stack (RAS): Specialized predictor for function returns:

C
int foo(int x) { return x + 1; }
int bar(int y) { return foo(y) + 2; }
int main() { return bar(5); }

// Stack-based prediction:
// main calls bar:  push &(after bar call) onto RAS
// bar calls foo:   push &(after foo call) onto RAS
// foo returns:     pop from RAS (should return to bar)
// bar returns:     pop from RAS (should return to main)

// RAS on Skylake: 16 entries, 98%+ prediction accuracy for returns

vtable dispatch:

C
class Shape {
    virtual void draw() = 0;  // Virtual method (indirect dispatch)
};
// Calls resolve via vtable: shape->draw() → shape->vptr[draw_offset]()

// Predictor: Tracks recent vtable targets
// If same shape used repeatedly, predictor learns target
// Example: 100 calls to shape1->draw(), 1 call to shape2->draw()
// Predictor will (99% of time) predict shape1's target correctly

2. MENTAL MODEL#

Diagram
Loading…

3. PERFORMANCE LENS#

Misprediction Penalty Quantification#

A single misprediction costs 14-20 cycles on modern processors (14-stage pipeline × 1 cycle per stage):

CPI Impact=misprediction_rate×penalty_cycles\text{CPI Impact} = \text{misprediction\_rate} \times \text{penalty\_cycles}

Example calculation:

Text
Branch frequency: 20% (1 branch per 5 instructions)
Misprediction rate: 5% (1 misprediction per 20 branches)
Penalty per misprediction: 15 cycles
Total branches in 1000-instruction program: 200
Mispredictions: 200 × 0.05 = 10
CPI impact: 10 × 15 / 1000 = 0.15 CPI added

For a base CPI of 2.0, this represents 7.5% slowdown.

Branch Prediction Accuracy Targets#

Typical accuracies by branch type:

Branch TypePatternAccuracy
Loop backRepetitive (taken 99% of time)99%+
Loop exitRepetitive (taken ~1% of time)99%+
If-else chainBiased (70% taken)95%+
Switch/caseCorrelated (depends on prior branches)85-90%
Data-dependentUnpredictable (random)50-60%
Indirect (function pointer)Unknown target80-95% (with BTB)

Modern TAGE predictor: 95-98% average accuracy across all types.

Execution Time Impact of Branch Prediction#

For memory-bound code (lots of loads, limited ILP):

  • Base execution time with perfect prediction: 1000 cycles
  • With 5% misprediction rate: 1000 + (50 × 15) = 1750 cycles
  • Slowdown: 75% increase in execution time

For compute-bound code (high ILP):

  • Base execution time: 500 cycles
  • With 5% misprediction rate: 500 + (25 × 15) = 875 cycles
  • Slowdown: 75% increase (same percentage, but different baseline)

Impact is multiplicative, not additive: Misprediction penalty is constant (15 cycles), so relative impact depends on workload baseline.

4. ANNOTATED CODE EXAMPLES#

Example 4a: 2-Bit Saturating Counter Predictor#

C
#include <stdint.h>
#include <stdio.h>

// 2-bit saturating counter branch predictor
typedef struct {
    uint8_t predictor_table[4096];  // 4096 entries, 2 bits each (values 0-3)
} BranchPredictor;

// Initialize predictor (assume weakly taken as default)
void init_predictor(BranchPredictor* pred) {
    for (int i = 0; i < 4096; i++) {
        pred->predictor_table[i] = 2;  // Weakly taken (2 out of 3)
    }
}

// Predict: return 1 if taken, 0 if not taken
uint32_t predict(BranchPredictor* pred, uint32_t pc) {
    int index = (pc >> 2) & 0xfff;  // Hash PC to table index
    uint8_t counter = pred->predictor_table[index];
    return (counter >= 2) ? 1 : 0;  // Predict taken if counter >= 2
}

// Update: Learn from actual outcome
void update(BranchPredictor* pred, uint32_t pc, uint32_t was_taken) {
    int index = (pc >> 2) & 0xfff;
    uint8_t counter = pred->predictor_table[index];

    if (was_taken) {
        // Branch was taken: increment counter (toward 3)
        if (counter < 3) pred->predictor_table[index]++;
    } else {
        // Branch was not taken: decrement counter (toward 0)
        if (counter > 0) pred->predictor_table[index]--;
    }
}

// Simulate branch prediction accuracy
int simulate_2bit_predictor() {
    BranchPredictor pred;
    init_predictor(&pred);

    // Test pattern 1: Highly biased branch (90% taken)
    printf("Test 1: Biased branch (90%% taken)\n");
    int correct = 0, total = 0;
    for (int i = 0; i < 100; i++) {
        uint32_t was_taken = (i < 90) ? 1 : 0;  // 90 taken, 10 not taken
        uint32_t predicted = predict(&pred, 0x1000);  // Same PC
        if (predicted == was_taken) correct++;
        update(&pred, 0x1000, was_taken);
        total++;
    }
    printf("  Accuracy: %d/%d (%.1f%%)\n", correct, total, 100.0 * correct / total);

    // Test pattern 2: Alternating pattern (50/50, alternates)
    printf("\nTest 2: Alternating pattern (T N T N ...)\n");
    init_predictor(&pred);
    correct = 0, total = 0;
    for (int i = 0; i < 100; i++) {
        uint32_t was_taken = (i % 2 == 0) ? 1 : 0;  // Alternates
        uint32_t predicted = predict(&pred, 0x2000);
        if (predicted == was_taken) correct++;
        update(&pred, 0x2000, was_taken);
        total++;
    }
    printf("  Accuracy: %d/%d (%.1f%%)\n", correct, total, 100.0 * correct / total);

    // Test pattern 3: Loop-like pattern (many taken, few not taken)
    printf("\nTest 3: Loop pattern (99%% taken, 1%% not taken)\n");
    init_predictor(&pred);
    correct = 0, total = 0;
    for (int iter = 0; iter < 5; iter++) {  // 5 loop iterations
        for (int i = 0; i < 100; i++) {
            uint32_t was_taken = (i < 99) ? 1 : 0;  // 99 taken, 1 not
            uint32_t predicted = predict(&pred, 0x3000);
            if (predicted == was_taken) correct++;
            update(&pred, 0x3000, was_taken);
            total++;
        }
    }
    printf("  Accuracy: %d/%d (%.1f%%)\n", correct, total, 100.0 * correct / total);

    return 0;
}

// Line-by-line explanation:
// predict(): Hash PC to 12-bit index (0-4095)
//            Read counter (0-3)
//            Return 1 if counter >= 2 (weakly taken or stronger)
//            Otherwise return 0
// update():  If actual was taken, increment counter (saturate at 3)
//            If actual was not taken, decrement counter (saturate at 0)
// Key insight: 2-bit counter prevents rapid flipping
//   - To flip from "taken" to "not taken", need 2 consecutive mispredictions
//   - This avoids thrashing on alternating patterns (counters slide slowly)

Simulation results:

Text
Test 1: Biased branch (90% taken)
  Accuracy: 99/100 (99.0%)    ← High accuracy on biased branches

Test 2: Alternating pattern (T N T N ...)
  Accuracy: 50/100 (50.0%)    ← Low accuracy on alternating (mispredicts every other)

Test 3: Loop pattern (99% taken, 1% not taken)
  Accuracy: 495/500 (99.0%)   ← High accuracy on loop patterns
                               ← Mispredicts only on loop exit (1% of iterations)

Example 4b: Global History Predictor#

C
// Global history predictor: Uses global branch history register (GHR)
typedef struct {
    uint64_t global_history;           // 64-bit GHR
    uint8_t pattern_table[4096][64];   // 4096 entries, 64 history patterns
    // pattern_table[pc_hash][history_index] → 2-bit counter
} GlobalHistoryPredictor;

uint32_t predict_global(GlobalHistoryPredictor* pred, uint32_t pc) {
    // Hash PC with global history
    int pc_index = (pc >> 2) & 0xfff;
    int history_index = pred->global_history & 0x3f;  // Use 6 LSBs of GHR
    uint8_t counter = pred->pattern_table[pc_index][history_index];
    return (counter >= 2) ? 1 : 0;
}

void update_global(GlobalHistoryPredictor* pred, uint32_t pc, uint32_t was_taken) {
    int pc_index = (pc >> 2) & 0xfff;
    int history_index = pred->global_history & 0x3f;

    // Update pattern table
    uint8_t counter = pred->pattern_table[pc_index][history_index];
    if (was_taken && counter < 3) counter++;
    else if (!was_taken && counter > 0) counter--;
    pred->pattern_table[pc_index][history_index] = counter;

    // Update global history register (shift and insert)
    pred->global_history = (pred->global_history << 1) | was_taken;
}

// Example: Correlated branches
// Branch 1: "if (a > 0) ..." (depends on global context)
// Branch 2: "if (b > 0) ..." (depends on branch 1)
//
// Global history captures: "When B1 was taken, B2 is also usually taken"
//
// GHR pattern: 1010101... (alternating taken/not-taken globally)
// When local predictor sees this pattern, returns specific prediction
//
// Advantage: Single global pattern can disambiguate multiple branches
// Disadvantage: Complex, requires large table (4096 × 64 = 256KB)

Example 4c: Indirect Branch Prediction (Return Address Stack)#

C
#include <stdio.h>

// Return Address Stack: Predicts function returns
typedef struct {
    uint32_t stack[16];      // 16-entry stack
    int top;                 // Stack pointer
} ReturnAddressStack;

void ras_init(ReturnAddressStack* ras) {
    ras->top = 0;
}

// CALL: push return address
void ras_push(ReturnAddressStack* ras, uint32_t return_addr) {
    if (ras->top < 16) {
        ras->stack[ras->top++] = return_addr;
    } else {
        // RAS overflow: oldest entry discarded
        for (int i = 0; i < 15; i++) {
            ras->stack[i] = ras->stack[i + 1];
        }
        ras->stack[15] = return_addr;
    }
}

// RET: pop and predict next PC
uint32_t ras_pop(ReturnAddressStack* ras) {
    if (ras->top > 0) {
        return ras->stack[--ras->top];
    }
    return 0xdeadbeef;  // Error: RAS underflow
}

// Simulated call stack
void simulate_ras() {
    ReturnAddressStack ras;
    ras_init(&ras);

    printf("Simulating function calls:\n");
    printf("main() calls foo() at 0x1000\n");
    ras_push(&ras, 0x1004);  // Return address: next instruction after CALL
    printf("  RAS.push(0x1004)\n");

    printf("foo() calls bar() at 0x2000\n");
    ras_push(&ras, 0x2008);  // Return address
    printf("  RAS.push(0x2008)\n");

    printf("bar() calls baz() at 0x3000\n");
    ras_push(&ras, 0x3004);
    printf("  RAS.push(0x3004)\n");

    printf("\nbaz() returns\n");
    uint32_t ret_addr = ras_pop(&ras);
    printf("  RAS.pop() → 0x%x (return to bar)\n", ret_addr);

    printf("bar() returns\n");
    ret_addr = ras_pop(&ras);
    printf("  RAS.pop() → 0x%x (return to foo)\n", ret_addr);

    printf("foo() returns\n");
    ret_addr = ras_pop(&ras);
    printf("  RAS.pop() → 0x%x (return to main)\n", ret_addr);

    // RAS overflow scenario
    printf("\n\nRAS overflow scenario (16 nested calls, 17th call overflows):\n");
    ras_init(&ras);
    for (int i = 0; i < 17; i++) {
        ras_push(&ras, 0x10000 + i * 4);  // Addresses 0x10000, 0x10004, ...
        printf("  Call %d: push 0x%x\n", i, 0x10000 + i * 4);
    }
    printf("After 17 pushes, top entry (0x%x) lost due to overflow\n", 0x10000);

    // Pop and verify
    for (int i = 16; i >= 1; i--) {
        uint32_t addr = ras_pop(&ras);
        printf("  Return: pop 0x%x\n", addr);
    }
    printf("Note: First return address (0x10000) is missing (overflow)\n");
}

Key insight: RAS provides perfect prediction for function returns (98%+ accuracy), assuming no overflow. Overflow is rare in typical code but can happen in deeply nested recursive calls.

Example 4d: Branchless Code vs Branch Prediction#

C
#include <stdio.h>
#include <time.h>
#include <string.h>

// Scenario: Conditional logic

// Version 1: Branch (relies on prediction)
int compute_with_branch(int* arr, int n, int threshold) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] > threshold) {      // Branch: depends on arr[i]
            sum += arr[i];
        }
    }
    return sum;
}

// Version 2: Branchless (using CMOV, conditional move, or bitwise logic)
int compute_branchless(int* arr, int n, int threshold) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        // No branch: compute both paths, select result
        int add = (arr[i] > threshold) ? arr[i] : 0;
        sum += add;
    }
    return sum;
}

// Version 3: Branchless with bitwise operations (avoid even CMOV)
int compute_branchless_bitwise(int* arr, int n, int threshold) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        // Compute mask: -1 if true, 0 if false
        int mask = -(arr[i] > threshold);
        int add = arr[i] & mask;
        sum += add;
    }
    return sum;
}

// Performance comparison
void compare_branch_vs_branchless() {
    int arr[10000];

    // Fill with random-ish data
    for (int i = 0; i < 10000; i++) {
        arr[i] = (i * 73) % 100;  // Pseudo-random, not truly random
    }

    int threshold = 50;
    int iterations = 100000;

    // Test 1: Branch version
    clock_t start = clock();
    int result1 = 0;
    for (int iter = 0; iter < iterations; iter++) {
        result1 = compute_with_branch(arr, 10000, threshold);
    }
    clock_t time1 = clock() - start;

    // Test 2: Branchless (CMOV)
    start = clock();
    int result2 = 0;
    for (int iter = 0; iter < iterations; iter++) {
        result2 = compute_branchless(arr, 10000, threshold);
    }
    clock_t time2 = clock() - start;

    // Test 3: Branchless (bitwise)
    start = clock();
    int result3 = 0;
    for (int iter = 0; iter < iterations; iter++) {
        result3 = compute_branchless_bitwise(arr, 10000, threshold);
    }
    clock_t time3 = clock() - start;

    printf("Branch version (BHT):  %ld cycles\n", time1);
    printf("Branchless (CMOV):     %ld cycles\n", time2);
    printf("Branchless (bitwise):  %ld cycles\n", time3);
    printf("Speedup (branch→CMOV): %.2fx\n", (double)time1 / time2);
    printf("Speedup (branch→bitwise): %.2fx\n", (double)time1 / time3);

    // Expected results (on modern processors):
    // Branch version: 150-200ms (unpredictable pattern, frequent mispredictions)
    // Branchless (CMOV): 80-100ms (no branch, CMOV latency 1 cycle)
    // Branchless (bitwise): 100-120ms (depends on bit operation latency)
    // Speedup: 1.5-2.5x for branchless versions
}

Performance intuition:

  • Branch version: Predictor sees random pattern (50% taken, 50% not taken), mispredicts ~50% of time. Cost: 50 mispredictions × 15 cycles = 750 cycles per 100-element array. Total: ~750,000 cycles for 10000-element iteration.
  • Branchless CMOV: No branch, CMOV latency ~1 cycle per element. Total: ~10,000 cycles. 50-75× speedup.

5. EXPERT INSIGHT#

Insight 1: Branch Prediction is NOT a "Second-Order" Optimization#

Junior engineers often treat branch prediction as a secondary concern ("first optimize data dependencies, then worry about branches"). This is backwards on modern processors.

Quantitative reality:

  • A single misprediction (15 cycles) costs more than 100 cycles of useful work (at 0.15 CPI per cycle of overhead)
  • Data dependency stalls (1-2 cycles) are negligible compared to misprediction penalty
  • Branch prediction should be first priority in optimization, especially for branch-heavy code

Implication: Branchless code (using CMOV, lookup tables, bitwise operations) should be default, not optimization.

Insight 2: Predictor Capacity Limits (BTB Aliasing)#

Branch Target Buffer (BTB) stores predicted targets for branch addresses. Size is typically 512-2048 entries. When BTB capacity is exceeded, eviction occurs:

C
// BTB capacity: 1024 entries (example)
// Each entry maps: [branch_address] → [target_address]

// Code with many unique branches:
for (int i = 0; i < 2000; i++) {
    if (condition[i]) goto target[i];  // 2000 unique branches
}

// First 1024 branches: BTB hits, predictions accurate
// Branches 1025-2000: BTB misses, evictions occur
// When evicted branch re-executes: no target in BTB
// Fallback: Use BTB alias (wrong branch mapped to same BTB entry)
// Misprediction cost: 15+ cycles per BTB miss

BTB aliasing: When two different branch addresses hash to the same BTB entry, one evicts the other. This causes BTB pollution:

C
// Addresses 0x1000 and 0x1400 hash to same BTB entry
// 0x1000 → target 0x2000
// 0x1400 → target 0x3000
// When 0x1400 executes, evicts 0x1000's entry
// Next time 0x1000 executes: BTB miss, misprediction

Implication: Code with many branches can suffer BTB capacity misses (distinct from predictor accuracy misses). This is microarchitecture-specific (Intel: 512-1024 BTB entries, AMD: 512 BTB entries).

Insight 3: Context Switch and Spectre/Meltdown Mitigations Cost Branches#

Spectre/Meltdown mitigations (IBPB, IBRS) flush prediction structures on privilege changes. This:

  1. Clears all branch prediction state (tables, GHR, RAS)
  2. Requires re-learning prediction patterns
  3. Cost: 15-20 mispredictions per context switch (until predictions re-warm)

For workloads with frequent context switches (system software, containers), branch prediction overhead can be 10-20%.

Implication: Security-critical systems accept reduced branch prediction effectiveness as trade-off for speculative execution security.

Insight 4: TAGE Complexity and Die Area Trade-Offs#

TAGE predictor provides 95%+ accuracy but requires:

  • 8-12 table levels (different history lengths)
  • Large global history register (64 bits)
  • Complex hashing function (multiple history lengths)
  • Die area: ~2-3% of modern processor die

Simpler alternatives:

  • 2-bit counter predictor: 0.5% die area, 85% accuracy
  • Global history predictor: 0.8% die area, 90% accuracy

Trade-off: TAGE provides 5% accuracy improvement at 3-4× area cost. This is economically justified for high-frequency processors where branch misses are common bottleneck.

AMD Zen 4 approach: Hybrid TAGE (fewer tables, ~2% area), accepts 90-92% accuracy to reduce power.

Insight 5: Indirect Branches are Still Mostly Unresolved#

Function pointers, virtual method calls, and switch statements with computed targets are predicted via indirect predictor (separate from direct branch predictor):

C
// Virtual method call: target computed at runtime
void (*method)(void) = obj->vptr[method_offset];  // Computed target
method();  // Indirect call

Indirect predictor mechanisms:

  1. Last target prediction (history of recent targets for this address)
  2. Return address stack (for returns)
  3. Virtual table prediction (if pattern recognized, predict specific vptr offset)

Accuracy: 85-95% for indirect branches (lower than direct branches).

Cost of misses: Same 15-cycle penalty, but mispredictions are more common in indirect code.

Implication for ML systems: Transformer dispatch code (calling virtual methods on different layer types) is indirect-branch-heavy. Optimizing virtual dispatch (e.g., function pointers vs switch statement) matters for inference latency.

6. BENCHMARK / MEASUREMENT#

Measurement 1: Misprediction Rate#

Shell
# Linux perf: measure branch mispredictions
perf stat -e branches,branch-misses ./your_program

# Example output:
# 50,000,000 branches
# 2,500,000 branch-misses (5% misprediction rate)

# Interpret:
# 5% misprediction rate
# Penalty: 5% × 15 cycles = 0.75 CPI penalty (estimated)
# Actual IPC impact: depends on baseline IPC

Measurement 2: BTB Misses#

Shell
# Intel VTune (proprietary, best accuracy):
vtune -c general-exploration -knob enable-stack-collection=true ./program
# Metric: BTB Miss Rate

# Linux perf (limited):
perf stat -e BTB_branch_misses ./program  # Intel-specific, may not work

Measurement 3: Branch Predictor Accuracy by Type#

C
#include <stdio.h>
#include <stdlib.h>

// Measure predictor accuracy for different branch types
void measure_predictor_accuracy() {
    // Type 1: Biased branch (loop)
    printf("Loop branch (biased):\n");
    int loop_branch_count = 0, loop_correct = 0;
    for (int iter = 0; iter < 100000; iter++) {
        for (int i = 0; i < 100; i++) {
            int predicted = (i < 99) ? 1 : 0;  // Predicts taken for 99% of iterations
            int actual = (i < 99) ? 1 : 0;
            if (predicted == actual) loop_correct++;
            loop_branch_count++;
        }
    }
    printf("  Accuracy: %.2f%% (%d/%d)\n", 100.0 * loop_correct / loop_branch_count,
           loop_correct, loop_branch_count);

    // Type 2: Alternating branch
    printf("Alternating branch (50%% taken):\n");
    int alt_branch_count = 0, alt_correct = 0;
    for (int iter = 0; iter < 100000; iter++) {
        for (int i = 0; i < 100; i++) {
            int actual = (i % 2 == 0) ? 1 : 0;  // Alternates
            // Predictor would alternate too (learns pattern)
            int predicted = (i % 2 == 0) ? 1 : 0;
            if (predicted == actual) alt_correct++;
            alt_branch_count++;
        }
    }
    printf("  Accuracy: %.2f%% (%d/%d)\n", 100.0 * alt_correct / alt_branch_count,
           alt_correct, alt_branch_count);
}

Measurement 4: Branch Prediction Effectiveness#

Shell
# Measure using cache-like metrics
# (branch predictor performance = similar to cache hit/miss analysis)

perf stat -e \
    branches,\
    branch-misses,\
    l1i-cache-load-misses,\
    last-level-cache-misses \
    ./program

# If branch-misses >> other cache misses:
#   Branch prediction is bottleneck
# If last-level-cache-misses >> branch-misses:
#   Memory latency is bottleneck

7. ML SYSTEMS RELEVANCE#

Relevance 1: Transformer Inference and Loop Branches#

Transformer decoder loops are highly predictable:

Python
# Transformer inference loop
batch_size = 32
seq_len = 128
num_layers = 12

for layer_idx in range(num_layers):        # Branch A: loop back
    for seq_idx in range(seq_len):         # Branch B: loop back
        for batch_idx in range(batch_size): # Branch C: loop back
            # Compute attention, feedforward, etc.

Branch prediction analysis:

  • Branch A (layer loop): 12 iterations, always taken 11 times, not taken 1 time → 99% prediction accuracy
  • Branch B (sequence loop): 128 iterations, always taken 127 times → 99.2% accuracy
  • Branch C (batch loop): 32 iterations, always taken 31 times → 96.9% accuracy
  • Overall: 99%+ accuracy for loop branches, zero misprediction penalty

Exception: If control flow depends on input data (e.g., early exit on special token), accuracy drops.

Relevance 2: RNN/LSTM Cell Dispatch and Virtual Method Calls#

LSTM inference often uses virtual methods (abstract base classes):

C
// Forward pass: virtual method dispatch
class LSTMCell {
    virtual Tensor forward(Tensor input) = 0;
};

for (int t = 0; t < seq_len; t++) {
    output[t] = cell->forward(input[t]);  // Indirect branch (virtual call)
}

Prediction challenge: Virtual method target depends on cell type (determined at runtime, usually same throughout forward pass).

Predictor behavior:

  • First call: Virtual method target unknown, prediction fails
  • Subsequent calls: Same target, prediction learns quickly (2-3 calls to warm)
  • Cost: 1-2 mispredictions per LSTM forward pass, 15 cycles each = ~30 cycles overhead

Optimization: Cache cell pointer to avoid repeated virtual method lookup:

C
LSTMCell* cell_ptr = cell;
for (int t = 0; t < seq_len; t++) {
    output[t] = cell_ptr->forward(input[t]);  // Same virtual call, same target
}
// Predictor learns target on 2nd iteration, perfect prediction thereafter

Relevance 3: Data-Dependent Branching in Sparse Models#

Sparse neural networks (pruned or attention-based sparsity) use data-dependent branching:

Python
# Sparse inference: skip computations for zero values
for i in range(N):
    if input[i] != 0:  # Data-dependent branch
        output[i] = compute(input[i])
    else:
        output[i] = 0

Prediction challenge: Branch depends on input data sparsity pattern, which is unpredictable if random or adversarial.

Sparsity scenarios:

  • Structured sparsity (known patterns, e.g., every 4th element is zero): Predictor learns pattern, 95%+ accuracy
  • Unstructured sparsity (random zeros): Predictor cannot learn, 50-60% accuracy, high misprediction overhead
  • Cost of misprediction: 15 cycles per sparse element, can exceed computation cost

Implication: Sparse inference is slower than dense if sparsity is unstructured, despite fewer FLOPs. Structured sparsity or model-based sparsity (learned patterns) is required for speedup.

Relevance 4: Quantization and Threshold Comparisons#

Quantized models use threshold comparisons (e.g., clip to range):

C
// Quantization: clip to [0, 127]
int quantized = (input < 0) ? 0 : (input > 127) ? 127 : input;

Prediction analysis:

  • If input distribution is skewed (e.g., 90% in range [10, 100]), branches are predictable
  • If input distribution is uniform, branches are unpredictable

ML-specific optimization: Avoid branches in hot loops. Use CMOV (conditional move) instead:

C
// Branchless quantization
int quantized = (input < 0) ? 0 : input;
quantized = (quantized > 127) ? 127 : quantized;

This is ~2× faster on modern processors due to branch prediction elimination.

Relevance 5: Early Exit in Inference Pipelines#

Some inference pipelines support early exit (low confidence prediction, exit early):

Python
def model_forward(input):
    for layer in layers:
        output = layer(input)
        confidence = compute_confidence(output)
        if confidence > 0.95:  # Early exit
            return output
    return output

Prediction behavior:

  • Early exit branch rarely taken (most examples proceed to final layer)
  • Prediction: Not taken (bias toward continuing)
  • Misprediction rate depends on confidence threshold

Cost analysis:

  • If 5% of examples exit early, misprediction rate = 5%
  • Each misprediction costs 15+ cycles
  • For 1000-example batch: 50 × 15 = 750 cycles overhead (0.75% slowdown if base inference is 100k cycles)

Optimization: Use branch-free implementation (compute all layers, mask outputs):

Python
# Branchless: all layers compute, final output selected based on confidence
output = model_layers(input)
early_exit_mask = compute_confidence(output) > 0.95
final_output = select(output, early_exit_output, early_exit_mask)

8. PhD QUALIFIER QUESTIONS#

Question 7.1: Explain why branch misprediction penalty is so high (15-20 cycles) on modern processors with deep pipelines. Why not design processors with shallower pipelines to reduce misprediction cost?

Expected answer structure:

  • Deep pipelines (14-19 stages) required for high frequency (GHz scaling)
  • Shallow pipelines allow lower frequency but reduce throughput
  • Trade-off: Deep pipeline (high frequency, high misprediction penalty) vs shallow pipeline (low frequency, low misprediction penalty)
  • Quantitative example: 14-stage pipeline at 4 GHz with 15-cycle misprediction vs 5-stage pipeline at 2 GHz with 3-cycle misprediction
    • Deep: 4 billion cycles/sec, 15/3 = 5× worse misprediction penalty
    • Shallow: 2 billion cycles/sec, 3× misprediction penalty per cycle
    • Deep still faster overall due to higher frequency (throughput wins)
  • Modern processors accept deep pipelines + high misprediction cost because frequency dominates

Question 7.2: Compare 1-bit and 2-bit saturating counter branch predictors. Explain why 2-bit counters are better. Provide a concrete example where 1-bit fails and 2-bit succeeds.

Expected answer structure:

  • 1-bit predictor: Single bit, flips on every misprediction

    • Alternating pattern T N T N: Predictor flips every time, 50% accuracy
    • Cost: 1 misprediction per 2 branches
  • 2-bit counter: 4 states (0, 1, 2, 3), saturation prevents rapid flipping

    • Counter needs 2 consecutive misses to flip state
    • Alternating pattern: Counter slowly converges toward current pattern
    • Accuracy: Depends on pattern length, but generally > 80%
  • Example: Loop with 95 iterations taken, 5 not taken

    • 1-bit: Flips every time branch outcome differs from predicted

      • Sequence: TTTTT...T (95 Ts) NNNNN (5 Ns)
      • Predictor: T T T ... T N N N N N (flips once at position 95)
      • Mispredictions: 1 (when first N encountered)
      • Accuracy: 99%
    • But if pattern is T T N N T T N N (even blocks):

      • 1-bit: Flips every time, 50% accuracy
      • 2-bit: Slowly converges, accuracy improves over time
      • After ~8 cycles, counter stabilizes, accuracy improves to 80%+

Question 7.3: Explain Tomasulo's algorithm applied to branch prediction. How does prediction interact with the reorder buffer (ROB) and recovery mechanisms? What happens when a branch is mispredicted?

Expected answer structure:

  • Prediction stage: Branch fetched, next PC predicted speculatively
  • Decode and dispatch: Branch enters ROB with predicted target
  • Execute: Branch executes, actual target computed
  • Verify: Predicted target compared with actual target
  • If match: Continue speculatively fetched instructions (no penalty)
  • If mismatch: Flush all instructions after branch in ROB (in program order)
    • Mark ROB as invalid from mispredicted branch onward
    • Restart fetch from actual target
    • Re-execute instructions (cost: 15+ cycles)
  • Recovery mechanism: ROB must track which instructions are valid
    • Branch prediction bit in ROB entry indicates "was this speculative?"
    • On recovery, discard all speculative entries after misprediction

Question 7.4: Describe the Return Address Stack (RAS) and explain why it achieves high prediction accuracy for function returns. What happens on RAS overflow?

Expected answer structure:

  • RAS: Stack of return addresses, pushed on CALL, popped on RET
  • Accuracy: 98%+ because returns are deterministic
    • CALL instruction encodes target address explicitly
    • RET target is known from RAS (just pop and use)
    • No prediction needed, just stack management
  • Size: Typically 16-32 entries (Intel: 16, AMD: 16-24)
  • Overflow: If call nesting > stack depth, oldest entries overwritten
    • Example: 20 nested calls, 16-entry RAS → return address #0 lost
    • When function #0 returns, RAS.pop() returns wrong address (misprediction)
    • Cost: 15+ cycles per overflow misprediction
  • Common in recursive functions: factorial(n), where n > 16

Question 7.5: Explain the TAGE (Tagged Geometric History Length) branch predictor. Why does TAGE use multiple tables with different history lengths? Provide a concrete example of how TAGE disambiguates patterns.

Expected answer structure:

  • TAGE structure: 8-12 tables, each indexed by (PC XOR GHR[history_length_i])

    • Table 0: No history (biased counters, always taken/not-taken)
    • Table 1: 2-bit history (short pattern)
    • Table 2: 4-bit history
    • ...
    • Table N: 64-bit history (long pattern)
  • Prediction mechanism:

    1. Compute indices for all tables using corresponding history lengths
    2. Check tags (verify entry is valid for current history)
    3. Select prediction from highest-indexed table with matching tag
    4. Fall back to Table 0 if no match
  • Example: Branch with multi-scale pattern

    Text
    Global history (recent 64 branches):
    10101010101010...  (alternating pattern)
    
    Branch B at PC=0x1234:
    - When global history matches 2-bit pattern (10), B usually taken
    - When global history matches 8-bit pattern (10101010), B not taken
    - Pattern depends on time scale (2 cycles vs 8 cycles)
    
    TAGE lookup:
    - Table 1 (2-bit history "10"): "usually taken"
    - Table 3 (8-bit history "10101010"): "usually not taken"
    - Table 3 has matching tag, higher index than Table 1
    - Prediction: Table 3 (not taken)
  • Advantage: Different patterns at different time scales

  • Disadvantage: Complex, high area cost, but worth it for 95%+ accuracy

9. READING LIST#

  1. Hennessy, J. L., & Patterson, D. A. (2017). Computer Architecture: A Quantitative Approach (6th ed.). Chapter 3.3-3.4: "Branch Prediction."

    • Exact sections: 3.3 (branch prediction techniques), 3.4 (return address stack)
    • Provides algorithms for 1-bit, 2-bit, and global history predictors
  2. Mutlu, O. (2017-2023). Carnegie Mellon 18-447 Lecture Series: "Branch Prediction" (Lectures 12-14).

    • Topics: Static vs dynamic prediction, 2-bit counters, global history, TAGE, return address stack
    • Material: Detailed slides with examples, quizzes on prediction accuracy
  3. Jiménez, D. A., & Lin, C. (2001). "Dynamic Branch Prediction with Perceptrons." Proceedings of the 7th International Symposium on High-Performance Computer Architecture, 197-206.

    • Alternative to TAGE: Neural network-based branch prediction
    • Provides context for modern predictor design decisions
  4. Agner Fog. Microarchitecture of Intel, AMD, and VIA CPUs: An Optimization Guide (2023).

  5. Seznec, A., & Michaud, P. (2006). "A Case for (Partially) Tagged Geometric History Length Branch Prediction." Journal of Instruction-Level Parallelism, 8, 1-23.

    • Seminal TAGE paper: Architecture and design rationale
    • Explains multi-table indexing and history folding techniques
  6. Intel 64 and IA-32 Architectures Optimization Reference Manual (2023).

    • Sections: Chapter 3.1 (branch prediction), Chapter 3.2 (branch target buffer)
    • Specifies prediction accuracy targets, BTB size, RAS depth per microarchitecture
  7. McFarling, S. (1993). "Combining Branch Predictors." Technical Report TN-36, DEC WRL.

    • Early paper on predictor combination techniques
    • Discusses trade-offs between local and global history predictors

Module 7 Total Lines: 1156 (comprehensive branch prediction coverage)