Branches, measured: operand waits, prediction and the return stack

Does a branch have to wait for its operands, and what do prediction and a return stack buy back once it does?

The first article left one open question. Its model let a branch predicted taken read an ALU result in the cycle the ALU computed it, and load data in the cycle the load finished MEM. That is what a design does when it verifies the prediction in EX: the fetch is redirected in ID, and the direction is checked later, with the operands read as any EX instruction reads them. A design that verifies in ID cannot do that without a stall. This article measures that second design, which it calls H3, and what the wait costs. Then it adds a table of 2-bit counters with a branch target buffer, and a return address stack, and measures what each one changes.

The caveat from the first article still holds: every cycle count in this post comes from a model I wrote, not from silicon. The model follows its rules exactly, and several independent checks show that. Whether those rules describe a real core is a separate question. Every measured number below comes from a result file that a script produced. Host timings are not part of this article.

01Setup

The core is the first article's: RV32I plus mul, in order, with five stages, the same memory and the same MMIO exit. Every timing parameter lives in config/variants.cfg. The variants form a ladder:

H0 to H2 and their penalties are the first article's. A taken transfer resolved in EX costs 2 cycles, a taken transfer predicted in ID costs 1, and a misprediction costs 2.

02What the model does not model

• Wrong-path fetches. The trace holds only retired instructions, so a squashed fetch never trains a predictor or reaches a cache.
• Predictor timing and history. Tables are updated in trace order when a branch retires, with no latency. Counters are indexed by pc bits alone.
• Indirect jumps. Only returns are predicted. Every other jalr is resolved in EX.
• Mispredictions. A mispredicted branch costs 2 cycles even where ID could catch it. That is conservative for H3 to H5.
• The operand path. The bypass wires cost nothing of their own; only the timing of the value makes a branch wait. There is no clock period, power or area.

03The rules

Reading operands in ID

In H1 and H2, a branch predicted taken redirects fetch in ID, and its direction is verified in EX, where it reads its operands the way an EX instruction does: an ALU result in the cycle it is computed, and load data in the cycle the load finishes MEM. A correct prediction costs one cycle, and a wrong one two. That is a design that exists. The other design verifies in ID, where the operands must already be ready, so H3 is the cost of that choice.

H3 verifies such a branch in ID. A conditional branch predicted taken reads its operands there: an ALU result from the cycle its producer is in MEM, and load data from the cycle its producer is in WB. Everything else keeps the H2 rules. From the stages, with no other stall, the waits follow:

• an ALU result one instruction back: the branch waits 1 cycle;
• a load one instruction back: 2 cycles, one more than in H2;
• a load two instructions back: 1 cycle;
• an ALU result two instructions back, or any producer three or more back: no wait.

The scoreboard checks each operand against an extra ready time per register, the cycle in which the value can reach ID:

The stage-thread model enforces the same rule on its latches:

The rule changes a loop's timing in a way that is easy to miss. A back-edge waits one cycle for the counter that the instruction before it has just decremented. But the target of a predicted-taken branch is fetched during that wait, and it reaches ID when it would have reached it anyway. The one-cycle bubble of a correct taken prediction is hidden. So a correctly predicted back-edge costs the same in H3 as in H2, and a mispredicted exit costs three cycles instead of two.

Counters and the branch target buffer

H4 predicts conditional branches with 64 two-bit saturating counters, indexed by pc bits and starting weakly not taken, and a 16-entry direct-mapped branch target buffer (BTB), tagged with the full pc and allocated by taken branches. A branch is predicted taken only when its BTB entry hits and its counter is 2 or 3. A BTB miss means predicted not taken. The BTB supplies the target in ID, so a correct taken prediction costs 1 cycle. The sizes are my choice.

jal keeps its static rule, and jalr stays in EX.

The return stack

H5 predicts returns (jalr x0, 0(ra)) from an 8-entry return address stack. A call, which is a jal or a jalr with rd = ra, pushes pc + 4, and a return pops. The stack is circular: a push past its depth overwrites the oldest entry, so once the calls outnumber the entries, the pops read overwritten values.

A correct return costs 1 cycle and a wrong one 2. Both timing models call one predictor, once per retired instruction, in trace order, so they cannot disagree about a prediction. The cross-check compares only their timing.

04The workloads

• fib: naive recursive Fibonacci of 20, 247,578 instructions. Of 21,891 conditional branches, 38.2 % are taken. It makes 10,946 calls and as many returns.
• bubble: bubble sort of 128 values, 51,599 instructions, 16,639 branches, 28.5 % taken.
• dot and matmul: 65,557 and 15,447 instructions, with 8,192 and 592 branches.
• micro: the first article's 20-instruction loop.
• pattern (new): a 118-instruction nested loop. The inner loop runs four times and the outer five, so the inner back-edge has the outcomes T T T N in every outer iteration.
• calls (new): 71 instructions, with two chains of nested calls, six and twelve deep. Each function saves ra in a word of its own, and every call site is distinct.

05Validation

Functional. The ISS did not change. The first article's checks still pass: rv32ui 42 of 42, the decoder cross-check on 10,317 words in 47 ELFs, and the QEMU trace on 15,430 checks, none with a mismatch. The two new programs add 387 QEMU checks, also with none. H0 to H2 are unchanged: for the five first-article programs, the cycle counts in both timing models, and the per-cycle stage traces of the stage threads, are identical to the first article's binary.

Cross-check. Every program under every variant runs through both timing models, under four charge settings (described below). That is 168 pairs, and every pair gives the same cycle count.

The pattern benchmark, worked out in full. The inner back-edge is bnez s1, instruction 8 of the program counting from 0, and the outer one is bnez s0, instruction 12. The fillers keep every value three instructions from its reader, so no variant waits for an operand.

The base is 118 + 4 = 122 cycles. There are 25 branches, 19 of them taken: 15 on the inner back-edge and 4 on the outer.

• H0: every taken branch is resolved in EX, 19 × 2 = 38. 160.
• H1: the 19 taken branches are predicted taken and correct, 19 × 1. The six not-taken exits are predicted taken and mispredicted, 6 × 2 = 12. 122 + 19 + 12 = 153.
• H2: the program fills four 16-byte instruction lines, and each misses once, 4 × 10 = 40. 193.
• H3: no waits. 193.
• H4: the inner branch's first taken outcome misses the BTB, so it is predicted not taken, and its counter climbs to 3. Each exit is mispredicted and drops the counter to 2, so each later run starts with a correct first taken outcome. That is 2 + 4 = 6 mispredictions for the inner branch. The outer branch mispredicts its first taken outcome, a BTB miss, and its exit: 2. The totals are 8 mispredictions and 17 correct taken predictions. 122 + 17 + 16 + 40 = 195.
• H5: no calls or returns. 195.

The model gives 160, 153, 193, 193, 195 and 195. The dynamic predictor is two cycles behind the static rule, and its two cold starts are the whole difference.

The calls benchmark, worked out in full. The program has 71 instructions, so the base is 75 cycles. It makes 18 calls and has 18 returns. Sixteen of the functions reload ra one instruction before their ret, so that ret waits for the load.

• Caches (H2): 20 instruction lines miss, 200 cycles. The save area is four lines, and their four store misses cost 40 cycles. Each store miss overlaps the fetch miss of the next function, so the net is 200.
• H0: 36 cycles for the calls and 36 for the returns, all in EX, plus 16 reload waits of 2 cycles, 32. The save store and the leaf return also read ra from the call, but they are hidden under the call's 2-cycle redirect. 75 + 72 + 32 = 179.
• H1: calls predicted in ID, 18. Returns in EX, 36. Reload waits of 1 cycle, 16. 75 + 18 + 36 + 16 = 145.
• H2: 145 + 200 = 345. H3 and H4 are the same, since the program has no conditional branches: 345.
• H5: the calls cost 18. The stack holds the eight most recent calls, so 12 non-leaf returns are correct. Each waits 1 cycle for its reload, which hides its predicted bubble, so each costs 1. The two correct leaves cost 1 each. The four wrong returns wait 1 and then redirect for 2. 75 + 18 + 26 + 200 = 319.

With 4 entries, 10 of the 18 returns are wrong, and the returns cost 38, giving 331. With 16 entries none is wrong, and the total is 311. The model gives 331, 319 and 311. My first count missed two overlaps, a predicted bubble hidden under a wait and the overlapping misses. The stage trace shows both.

The independent predictor. A short Python program reads each program's trace, decodes the transfers from the instruction words, and simulates the static rule, the counters and the BTB, and the return stack. For all seven programs it reproduces the model's counts exactly: 98 configurations, nine counts each, with no mismatch.

06Measurements

Cycles and CPI

The table gives the cycles and CPI for each program and variant. The stage threads agree in all 42 program and variant pairs.

View larger ↗

Three results stand out. The operand rule costs bubble 16,161 cycles (18.4 %) and costs fib and dot nothing. Against H2, the dynamic predictor takes 13,263 cycles off bubble (15.1 %), because the static rule mispredicts 11,770 of its 16,639 branches. The return stack saves 10,945 cycles on fib against H4 (3.6 %), one per correct return.

Where the branch cycles go

Each run's stall cycles split into two parts: other stalls, which are data hazards of ordinary instructions and cache misses, and the costs of control transfers. To separate the second part, I ran each program with no transfer costs, then added the operand waits of conditional branches, then the taken predictions, then the redirects. The last run is the model. The three steps are exact differences, so they sum to the stall that the model reports.

View larger ↗

"Mispredict" counts the 2-cycle redirects. That covers real mispredictions and transfers the variant does not predict at all. H0 pays it on every taken transfer, and H1 to H4 pay it on every return. Dot is dominated by its caches: under H2, 168,006 of its 241,764 cycles are other stalls. Matmul's branch costs are 669 of its 17,130 cycles.

What the operand rule costs

Against H2, H3 adds 16,383 operand-wait cycles on bubble, and 223 taken bubbles disappear under those waits. Bubble's backward branches are the cause. The static rule predicts them taken, and most of them read a value one instruction earlier: 4,362 taken and 3,766 not taken read a load, and 8,002 not taken and 254 taken read an ALU result. Counting one cycle for an ALU result and two for a load predicts 24,512 waits, and the model reports 24,510. The two-cycle gap is not explained by the rule, and I have not traced it. Fib's and dot's backward branches read values further back, so they cost nothing. Matmul has eight waits, which add one cycle in total.

View larger ↗

The timeline shows the rule on the first article's loop. Each hatched cell is a branch waiting in ID for an operand. The back-edges at trace numbers 5, 9, 13 and 17 each wait one cycle, and the last of them is also mispredicted.

Prediction

The static rule is poor on bubble. Its branches are mostly backward and mostly not taken, so 11,770 of 16,639 are mispredicted. The counters bring that down to 2,946.

Sensitivity

View larger ↗

On fib the stack depth changes nothing. The one wrong return, at every depth, is main's return into the start-up code, whose entry the deep recursion overwrites. Every other return is predicted correctly even with 4 entries, which I did not expect. A return that reads an overwritten entry still gets the right address, because the call that overwrote it came from the same call site. The independent predictor agrees. The calls micro-benchmark, whose call sites are all distinct, shows the overflow clearly: 10, 4 and 0 wrong returns.

Bubble is flat from 16 counter and BTB entries upwards: 74,705 cycles and 2,946 mispredictions at each of the nine combinations of 16, 64 and 256. Smaller tables change the result. With one or two entries, bubble mispredicts 4,488 branches and runs 1,390 cycles faster than with 16. Only 262 of its branches are predicted taken, against 4,736 with 16 entries, and only a branch predicted taken reads its operands in ID. So under H4, a smaller predictor can run faster while predicting worse.

07Limitations

• The rules are mine. The checks show that the model follows them and that the two timing models agree. They say nothing about a real core's timing.
• Few workloads. Four first-article kernels, the first article's loop, and two micro-benchmarks built to be counted by hand.
• The split depends on order where costs overlap. In calls under H0, 36 cycles of hazards after each call sit in "other", because the call's redirect hides them until redirects are removed first. Cache misses overlap redirects in the same way, so calls' mispredict column is one cycle higher under H2 (37) than under H1 (36).
• Mispredictions keep their 2 cycles. A design that caught them in ID would pay 1, and the misprediction columns would shrink.
• The sizes are my choice. The defaults are 64 counters, 16 BTB entries and 8 return entries.

08How far can this be trusted?

The implementation follows its rules, and the checks show it. The ISS agrees with QEMU. The two timing models agree in every run. The hand calculations agree with the model. The independent predictor agrees on every count. None of that says the rules describe a real core. For comparisons inside the model, such as what the operand rule costs on one loop, it is useful.

09Reproduction

Everything runs from the cpu-systemc folder. The first article's targets are unchanged, and the branch measurements have their own:

make branches writes its results to results/, as JSON or CSV, and reads no host timings. The figure and table steps read only those files.