2026-09-11
Two-bit saturating counters and gshare tables predict branches by memorizing patterns. They work well until the correlated history you need is longer than the table can index — every extra history bit doubles the table size. Perceptron predictors, invented by Jimenez and Lin (2001) and shipped in AMD's Ryzen (Zen) and Oracle SPARC T4, break that exponential wall by learning a linear function of history instead.
The circuit is embarrassingly simple. For each branch PC, store a vector of N small signed weights, one per history bit. To predict:
Because history bits are ±1, the multiplication is just conditional negate — no real multiplier needed. The whole thing collapses to a signed adder tree that sums N six-to-eight-bit weights. For N=64, that's a 64-input Wallace tree, easily fitting in two pipeline stages.
Training is one-liner perceptron learning: on branch resolution, if the prediction was wrong or |y| is below a threshold θ (meaning low confidence), increment wᵢ toward the true outcome:
wᵢ ← wᵢ + tᵢ · hᵢ (saturating), where tᵢ = +1 if branch actually taken, −1 otherwise.
Rule of thumb: for N history bits, storage per entry is roughly N × 8 bits. A 1K-entry table with N=64 costs 1024 × 64 × 8 ≈ 64 KB — comparable to a large gshare, but exploits history hundreds of bits deep (gshare would need 2¹⁰⁰ entries). Set θ ≈ ⌊1.93·N + 14⌋ (the tuned constant from the original paper) to know when to stop training.
Where it wins: branches whose outcome is a linear function of history — loop exits with variable trip counts, branches correlated with 40-instructions-ago outcomes. Where it loses: XOR-like correlations (perceptrons can't learn non-linearly separable patterns), which is exactly why modern designs stack a perceptron alongside a TAGE predictor and pick whichever has higher confidence.
AMD's implementation in Zen 2 fuses the perceptron output with a traditional two-level predictor; the perceptron catches the long-history branches TAGE tags miss.