Control hazards, branch prediction and speculation

About one instruction in five or six is a branch or jump. In a pipelined processor every one of them is a small crisis: the fetch stage must choose the next instruction address before the branch has been decoded, let alone evaluated. If it guesses wrong, the instructions fetched behind the branch must be thrown away. In the five-stage pipeline of lesson 3 the cost of a wrong guess is one to three cycles. In a deep, wide processor that fetches four instructions a cycle through a pipeline of fifteen stages, a wrong guess can discard sixty instructions' worth of work. Branch prediction is therefore one of the most heavily engineered parts of any modern processor, and its accuracy has a direct, measurable effect on CPI.

The NS-5 classifier is branch-heavy. Its inner loop walks through radar samples, tests the sign of filter outputs, and compares features against thresholds in a decision tree. When Jonah profiles it on Core A, branch mispredictions account for about 0.15 of the 1.40 CPI, more than a tenth of all cycles. This lesson explains where that cost comes from and what predictors do about it.

The cost of a control hazard

The branch penalty is the number of cycles lost when the pipeline fetches the wrong instructions after a branch. It equals the number of stages between fetch and the stage that resolves the branch, plus any cycles to redirect fetch. The contribution of branches to CPI is the product of three factors: how often branches occur, how often they are mispredicted, and how much each misprediction costs.

The equation shows why prediction matters more as pipelines deepen. With 18 percent branches and a 3-cycle penalty, a predictor that is 90 percent accurate adds 0.054 to CPI. The same predictor in a machine with a 15-cycle penalty adds 0.27, and in a four-wide machine whose ideal CPI is 0.25, that is more than doubling the time per instruction. Deep, wide processors need accuracies above 95 percent, and modern designs reach well beyond that on typical code.

Static prediction

The simplest approach is to predict every branch the same way. Predicting not taken costs nothing extra: the pipeline just keeps fetching sequentially and flushes when the branch turns out taken. Predicting taken requires knowing the target address early, which needs extra hardware. A better static rule is backward taken, forward not taken: a branch that jumps backward is usually the bottom of a loop and is usually taken, while a forward branch usually skips rare code such as error handling. Compilers can also lay out code so that the likely path falls through, using profile information or programmer hints. Static prediction is cheap and is the right choice for the smallest cores, but its accuracy rarely exceeds 70 to 80 percent.

Dynamic prediction with saturating counters

A dynamic predictor learns each branch's behaviour as the program runs. The simplest keeps one bit per branch, recording whether it was taken last time, in a small table indexed by low bits of the branch address. A one-bit predictor has an obvious weakness on loops: it mispredicts twice per loop, once at the exit, when the branch falls through for the first time, and once on the next entry, when it predicts falling through again.

A two-bit saturating counter fixes that by requiring two wrong outcomes in a row to change the prediction. The counter counts up on taken and down on not taken, staying within 0 to 3, and predicts taken when its value is 2 or 3. A loop branch that is taken many times and then falls through once costs only one misprediction per loop, because the single fall-through moves the counter from 3 to 2, which still predicts taken. Two-bit counters, kept in a branch history table of a few thousand entries, raise accuracy on typical integer programs to around 85 to 90 percent.

Predicting the target: the branch target buffer

Predicting the direction is half the problem. To fetch from the target of a taken branch in the very next cycle, the fetch stage needs the target address before the branch is even decoded. A branch target buffer is a small cache, indexed by the program counter of the fetch, that stores the predicted target of branches seen before. If the current fetch address hits in the buffer and the direction predictor says taken, the next fetch comes from the stored target. If the address misses, fetch continues sequentially. The buffer also identifies which fetched words are branches at all, information that would otherwise appear only after decode.

Returns from procedures are a special case: the same return instruction goes to a different place depending on the caller, so a target buffer predicts it badly. A return address stack solves this. Every call pushes its return address onto a small hardware stack, and every return pops it as the predicted target. With eight or sixteen entries, the stack predicts nearly all returns correctly unless recursion runs deeper than its size. Indirect jumps through function pointers and virtual method tables need yet another structure, an indirect target predictor that uses recent history to choose among several targets.

Correlating predictors

Some branches are hard to predict from their own history but easy from the history of other branches. In the code if (a == 2) a = 0; if (b == 2) b = 0; if (a != b) ..., the third branch's outcome depends on the first two. A correlating predictor uses a global history register, a shift register recording the outcomes of the last several branches, as part of the table index. The gshare scheme, a widely used design, XORs the global history with the branch address to select a two-bit counter. Each combination of branch and recent history then gets its own counter, so patterns such as alternation, or the outcome that always follows a certain sequence, can be learned.

Tournament predictors combine a local predictor, which tracks each branch's own history, with a global one, and use a third table of counters to choose which to trust for each branch. The most accurate modern designs, such as tagged geometric-history predictors, keep several tables indexed by histories of different lengths, from a few branches to hundreds, and use the longest history that has proved useful. Perceptron predictors learn a weighted combination of history bits. These designs reach mispredict rates of a few per thousand instructions on common benchmarks, and their storage budgets run to tens of kilobytes.

Jonah tests three predictors in software on a trace of the two hottest branches in the classifier loop. One is the loop branch, which is taken seven times and then falls through. The other tests the sign of the filter output, which in the recorded data mostly alternates between positive and negative.

# Compare branch predictors on two branches from the classifier loop
def trace():
    t = []
    for frame in range(200):
        for i in range(8):                                  # 8 samples per frame
            t.append(("sign", (frame + i) % 2 == 0))        # alternates T, N, T, N, ...
            t.append(("loop", i < 7))                       # taken 7 times, then falls through
    return t

def counter_predict(c): return c >= 2                       # 2-bit states 0,1 = not taken; 2,3 = taken
def bump(c, taken): return min(3, c + 1) if taken else max(0, c - 1)

def one_bit(pc, taken, st):
    p = st.get(pc, True); st[pc] = taken; return p

def two_bit(pc, taken, st):
    c = st.get(pc, 2); st[pc] = bump(c, taken); return counter_predict(c)

def gshare(pc, taken, st):
    h = st.get("hist", 0)
    idx = ((0 if pc == "loop" else 37) ^ h) & 63             # branch address XOR 6 bits of history
    c = st.get(idx, 2); st[idx] = bump(c, taken)
    st["hist"] = ((h << 1) | taken) & 63
    return counter_predict(c)

tr = trace()
penalty, branch_frac = 3, 0.18
print("predictor     sign    loop    overall  CPI added")
for name, f in (("1-bit", one_bit), ("2-bit", two_bit), ("gshare", gshare)):
    st, hit = {}, {"sign": [0, 0], "loop": [0, 0]}
    for pc, taken in tr:
        hit[pc][0] += f(pc, taken, st) == taken; hit[pc][1] += 1
    acc = (hit["sign"][0] + hit["loop"][0]) / len(tr)
    print(f"{name:10s} {hit['sign'][0]/hit['sign'][1]:7.1%} {hit['loop'][0]/hit['loop'][1]:7.1%} {acc:8.1%}   {branch_frac*(1-acc)*penalty:.3f}")

predictor     sign    loop    overall  CPI added
1-bit        12.5%   75.1%    43.8%   0.304
2-bit        25.0%   87.5%    56.2%   0.236
gshare       99.7%   87.5%    93.6%   0.035

The results show each predictor's character. On the loop branch the one-bit predictor misses twice per loop, 75 percent accuracy, while the two-bit counter misses only at the exit, 87.5 percent. On the alternating sign branch both per-branch counters fail badly, because the branch flips every time and a counter always predicts the outcome it just saw. The gshare predictor learns the alternation almost perfectly from global history, though its six history bits are too few to see the loop exit, which needs a count of seven. A longer history, or a dedicated loop predictor, would capture that too. The trace is deliberately small; real branches are mixed and the gaps are less extreme, but the pattern of which predictor handles which behaviour carries over.

Speculative execution

Prediction lets the fetch stage keep going; speculation lets the whole processor keep going. A speculative processor executes instructions past a predicted branch as if the prediction were correct, but holds their results in a way that can be undone. When the branch resolves, a correct prediction lets the speculative work become permanent, and a misprediction discards it and restarts fetch on the right path. In the five-stage pipeline, speculation is simple, because instructions behind a branch do not reach WB before the branch resolves. In out-of-order processors, which may have dozens of instructions in flight past several unresolved branches, speculation relies on the reorder buffer and register renaming of lesson 6 to roll back exactly the wrong-path instructions.

Speculation has a cost beyond the wasted cycles: energy. Instructions executed on a wrong path consume power and produce nothing. For a solar-powered node such as the NS-5, a modest predictor and a short pipeline that waste little work on mispredictions can be the better design, even if a deeper speculative core would be faster.

Predication: avoiding branches

Some branches are inherently unpredictable, such as a comparison of noisy sensor data against a threshold. For short if-then-else code, the compiler can remove the branch altogether by computing both outcomes and selecting one with a conditional move or select instruction. This conversion, called if-conversion or predication, trades a few extra instructions for the elimination of a misprediction that would cost several cycles half the time. The RISC-V base has no conditional move, but compilers achieve the same effect with arithmetic and logical tricks, and some extensions add conditional-zero instructions for the purpose.

Speculation and security

Work on a wrong path is discarded architecturally, but it can leave traces in microarchitectural state such as which lines are in the cache. Research published in 2018 showed that carefully constructed code could exploit such traces to infer data the program was never permitted to read, a class of side-channel problems often grouped under the name speculative execution vulnerabilities. Designers and software engineers now defend against them by restricting what speculative instructions may do with secret data, by partitioning or flushing predictor and cache state across security boundaries, and by inserting speculation barriers in sensitive code. For architects the lesson is that performance features must be evaluated for what they reveal as well as for how fast they run.