Intel & AMD CPU Architecture · Part 2 · Module 7
Branch Prediction
Two-level predictors, TAGE, BTB, speculative execution
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):
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:
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.
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 timeStatic Prediction: The Baseline#
Static prediction uses heuristics, not runtime history:
-
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
-
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
-
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?"
// 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):
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:
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:
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 outcomeGlobal 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:
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:
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:
// 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 targetReturn address stack (RAS): Specialized predictor for function returns:
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 returnsvtable dispatch:
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 correctly2. MENTAL MODEL#
Loading…3. PERFORMANCE LENS#
Misprediction Penalty Quantification#
A single misprediction costs 14-20 cycles on modern processors (14-stage pipeline × 1 cycle per stage):
Example calculation:
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 addedFor a base CPI of 2.0, this represents 7.5% slowdown.
Branch Prediction Accuracy Targets#
Typical accuracies by branch type:
| Branch Type | Pattern | Accuracy |
|---|---|---|
| Loop back | Repetitive (taken 99% of time) | 99%+ |
| Loop exit | Repetitive (taken ~1% of time) | 99%+ |
| If-else chain | Biased (70% taken) | 95%+ |
| Switch/case | Correlated (depends on prior branches) | 85-90% |
| Data-dependent | Unpredictable (random) | 50-60% |
| Indirect (function pointer) | Unknown target | 80-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#
#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:
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#
// 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)#
#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#
#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:
// 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 missBTB aliasing: When two different branch addresses hash to the same BTB entry, one evicts the other. This causes BTB pollution:
// 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, mispredictionImplication: 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:
- Clears all branch prediction state (tables, GHR, RAS)
- Requires re-learning prediction patterns
- 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):
// Virtual method call: target computed at runtime
void (*method)(void) = obj->vptr[method_offset]; // Computed target
method(); // Indirect callIndirect predictor mechanisms:
- Last target prediction (history of recent targets for this address)
- Return address stack (for returns)
- 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#
# 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 IPCMeasurement 2: BTB Misses#
# 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 workMeasurement 3: Branch Predictor Accuracy by Type#
#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#
# 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 bottleneck7. ML SYSTEMS RELEVANCE#
Relevance 1: Transformer Inference and Loop Branches#
Transformer decoder loops are highly predictable:
# 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):
// 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:
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 thereafterRelevance 3: Data-Dependent Branching in Sparse Models#
Sparse neural networks (pruned or attention-based sparsity) use data-dependent branching:
# 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] = 0Prediction 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):
// 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:
// 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):
def model_forward(input):
for layer in layers:
output = layer(input)
confidence = compute_confidence(output)
if confidence > 0.95: # Early exit
return output
return outputPrediction 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):
# 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:
- Compute indices for all tables using corresponding history lengths
- Check tags (verify entry is valid for current history)
- Select prediction from highest-indexed table with matching tag
- Fall back to Table 0 if no match
-
Example: Branch with multi-scale pattern
TextGlobal 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#
-
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
-
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
-
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
-
Agner Fog. Microarchitecture of Intel, AMD, and VIA CPUs: An Optimization Guide (2023).
- Sections: Chapter 3 (branch prediction), Chapter 3.1 (TAGE variants)
- Exact specifications for Intel (Skylake, Ice Lake, SPR) and AMD (Zen 4) predictors
- URL: https://www.agner.org/optimize/microarchitecture.pdf
-
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
-
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
-
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)