wire / wire-format / branch-prediction
Branch prediction predicts the outcome of conditional branches to keep the pipeline full. Static prediction: always taken/not-taken, backward taken/forward not-taken. Dynamic prediction: 1-bit (last outcome), 2-bit saturating counter (strongly/weakly taken/not-taken), gshare (global history XOR PC), tournament (local + global), TAGE (tagged geometric history length). Branch target buffer (BTB) caches branch targets. Return address stack (RAS) predicts return addresses.
aka: Branch prediction (hardware)
spec: Branch prediction
Branch prediction predicts the outcome of conditional branches to keep the pipeline full. Static prediction: always taken/not-taken, backward taken/forward not-taken. Dynamic prediction: 1-bit (last outcome), 2-bit saturating counter (strongly/weakly taken/not-taken), gshare (global history XOR PC), tournament (local + global), TAGE (tagged geometric history length). Branch target buffer (BTB) caches branch targets. Return address stack (RAS) predicts return addresses.
| field | size | meaning |
|---|---|---|
| 1-bit predictor | 1 bit per branch | Predicts the same as the last outcome. Fails on alternating patterns. |
| 2-bit saturating counter | 2 bits per branch | States: 00 (strongly not-taken), 01 (weakly not-taken), 10 (weakly taken), 11 (strongly taken). Increment on taken, decrement on not-taken. |
| gshare | global history + PC | XOR global branch history with PC to index the prediction table. Captures correlations between branches. |
| TAGE | multiple tables | Tagged Geometric History Length: multiple prediction tables with increasing history lengths. Uses partial tags for confidence. |
| BTB | cache | Branch Target Buffer: caches the target address of branches. On a hit, the pipeline redirects to the target. |
| RAS | stack | Return Address Stack: pushes return address on CALL, pops on RET. Predicts return targets. |
| Misprediction penalty | 10-20 cycles | Cost of a mispredicted branch: flush the pipeline and restart from the correct path. |
example:
00 00
Branch prediction (placeholder)
agent: curl -H 'accept: application/json' wire.phall.io/wire-format/branch-prediction
or /wire-format/branch-prediction.json