Intuition Behind Out-of-Order Execution and How Tomasulo Works

This post is a continuation of the RISC-V pipeline optimisation post. That post took rv32i-pipe from a CPI of 1.3158 to 1.0675 and the dual issue rv32i-superscalar to 0.7271. This post asks what comes next: what out of order execution actually is, how Tomasulo’s scheme works block by block, and what happened when it was built and measured on the same RV32IM cores with the same benchmark. Theory first, then numbers. Every number here comes from simulation runs on my own implementations, and every CoreMark figure is from Verilator.

Special thanks to BitLemon for Out-of-Order Execution (Tomasulo’s Algorithm), and to Core Dumped. Both channels did a lot of the heavy lifting getting computer architecture intuition into my head.

This project was ambitious relative to what I knew going in. Most of the learning came from open source repos and videos available online, including Onur Mutlu’s advanced computer architecture classes. I did not absorb all of that before trying anyway. Rather than restarting from scratch I continued from the previous post’s cores, and worked on speedup alongside correctness from the start. Without correctness the numbers mean nothing, fast or slow.

I initially prototyped Tomasulo in C++, which helped me understand the machinery well enough to get an out of order core working and passing the ISA tests. The results were not particularly different from the in order versions, but the prototype gave me something working to translate into RTL. I also started the RTL rewrite with future variants in mind, since scaling the design to superscalar or more optimised versions can sometimes require taking a completely different design approach rather than simply adding another feature.

A note on the results

The biggest limitation here is that the cores still do not have caches, just as in the previous post. The memory model effectively assumes zero cache misses, which makes CPI look lower and CoreMark/MHz higher than they would with a realistic memory hierarchy. It also removes much of the long memory latency where OoO should have more opportunity to help.

The dual issue core is also still small, so the extra width does not provide enough independent work on this workload to repay the overhead of OoO. These results therefore are not a claim that OoO is ineffective. They show what happens when it is added to a small, already optimised core with very little memory latency to hide.

I will come back to the cache side in a later post, including what I learned from putting caches into the design and what I need to change. I will start from the unoptimised pipeline again and work forward from there, since adding a cache changes the tradeoffs at the most basic level before it changes anything about the OoO design.

Connecting it back

Before getting into the details, the same disclaimer as the previous post applies. Modern high performance cores from ARM, Intel, or Apple are wide out of order superscalar machines with large instruction windows, sophisticated predictors, and execution resources far beyond anything described here. All CoreMark/MHz figures are frequency normalised, all runs use ideal memory with no caches, and there is no synthesis in this post, so timing closure and Fmax are out of scope. The goal is to show how the mechanism works and what it measured on small cores, not to match commercial designs. Synthesis and implementation efforts using Yosys with the Sky130 standard cell library, OpenLane based hardening, and FPGA flows are part of the larger project and are treated separately. If you are interested in those areas, refer to the full project page linked below.

Out of order execution has been on my project list for a long time. It is the most ambitious build in this series by a good margin. I am still learning as I go, and I will update this post if and when that is required.

RV32I(M) Processor Variants

A family of RISC-V RV32I(M) processor implementations exploring different microarchitectural design points, including the out of order variants covered in this post.

Main Project

Quick Note

I felt a bit lazy, so I used a few images directly that were generated with the help of OpenAI’s image_gen, paired with GPT-5.6 Luna. I also used Kimi 2.6 for text formatting to maintain a smooth flow in the writing and avoid any mistakes along the way. Credits wherever needed.

Naming Convention

A naming note before anything else, since the variant names get long. The previous post built several in order features and stacked them onto a core name: early branch resolution, a hybrid predictor, a branch target buffer, a return address stack, hazard cleanup, load-use optimisation, and full load-use forwarding. Every core in this post that carries all of those is written with the suffix -FE (front end) instead of spelling out -br-hybp-btb-ras-hzopt-luopt-fulu every time. So rv32i-pipe-FE is rv32i-pipe with that full front end treatment, and rv32i-super-FE is the dual issue version with the same treatment. Where a core needs two of the out of order fixes described later, an extra o marks it: rv32i-ooo is single issue out of order, rv32i-oooo has the two fixes on top.

Out of order intuition: three small examples

Start with what the machine is actually for, before any results. An in order core issues instructions in the exact order the program lists them. If instruction 2 is waiting on something, instruction 3 waits too, even if instruction 3 has nothing to do with instruction 2. Out of order execution lets the hardware pick a different instruction to run while the stalled one waits, then puts the results back in the original order when it is time to update memory and registers. The program behaves exactly as written. Only the order work gets done inside the machine changes.

To see why this needs care, start from the two operations any instruction can do to a register: read it or write it. Two instructions touching the same register name gives four possible combinations, not three:

• read then read (RAR)
• read then write (RAW)
• write then read (WAR)
• write then write (WAW)

RAR never causes a problem. Reading a register twice does not change what is stored there, so it does not matter how many instructions read it or in what order they read it. The value sits still. This is also why a register file is usually built with two read ports and one write port, 2R1W: multiple reads in the same cycle are free of conflict by construction, so hardware gives out as many read ports as the pipeline needs, backed by a single SRAM array and a couple of read muxes at the output picking which row to return on each port. Only a write changes the value, so only combinations involving a write are worth naming:

• RAW (read after write). Instruction 2 reads a value that instruction 1 writes. This is a true dependency. Instruction 2 cannot run correctly before instruction 1 produces the value.

I1   R3 = R1 + R2
I2   R5 = R3 + R4

I1 produces R3. I2 needs R3 to compute R5. In a five stage pipeline I2 reaches the stage that reads R3 before I1 has written it back, so the value I2 sees is stale unless something intervenes: a stall, or forwarding the result straight from where I1 computed it. The rule for spotting it: I1 writes R3, I2 reads R3, and that overlap is the hazard. I1’s range (what it writes) intersects I2’s domain (what it reads).

• WAR (write after read). Instruction 2 writes to a register that instruction 1 still needs to read. If instruction 2 runs first, instruction 1 reads the wrong value. This is not about data flow, it is about two instructions racing to touch the same name.

I1   R1 = R2 x R3
I2   R2 = R4 + R5

I1 reads R2 to compute R1. I2 writes a new value into R2. In an ordinary five stage pipeline this never actually breaks anything, because I1 reads its operands early in the pipe and I2 cannot write back before I1 has already moved past its read stage: reads always land before the later write reaches the register file. The hazard only becomes a real risk once instructions are allowed to complete out of the order they were fetched in, for example if I2 runs ahead because I1 is delayed waiting on something else, or under auto increment and auto decrement addressing where a register is written before the next instruction has even been fetched. The rule for spotting it: I1 reads R2, I2 writes R2, so I1’s domain intersects I2’s range.

• WAW (write after write). Instruction 1 and instruction 2 both write the same register. If they run out of order, whichever one finishes last decides what the register holds, which may not match program order.

I1   R3 = R1 * R2
I2   R3 = R4 + R5

Both instructions write R3. In program order I2’s write should be the one that survives, since it comes second. In an ordinary five stage pipeline this also cannot go wrong, because writeback happens in the same order instructions were fetched. It becomes a hazard only when the two writes can complete out of that order, for instance if I1’s multiply takes longer than I2’s add and I2 finishes first: whichever write actually lands last in time wins, and if that is I1, the register ends up holding the wrong value for anything read after it. The rule for spotting it: I1 writes R3, I2 writes R3, so I1’s range intersects I2’s range.

RAW is real. The value has to exist before it can be read, in any machine, in any order. WAR and WAW are not about values at all. They exist only because both instructions happen to use the same register name. An out of order machine cannot let WAR or WAW hazards decide execution order, because ordering only for the sake of a shared name throws away exactly the freedom the machine exists to use. The fix, covered in full further down, is renaming: give every write a fresh, unique storage slot instead of reusing the 32 architectural register names, so two writes to “x1” become two writes to two different slots and the false ordering disappears. What remains after renaming is only RAW, and RAW is what the machine actually has to respect.

Example 1: hiding a slow producer. A load misses and takes 100 cycles. The next instruction needs the loaded value. The one after that does not.

lw   x1, 0(x2)      # slow, 100 cycles
add  x3, x1, x4     # true RAW on x1, must wait
add  x5, x6, x7     # independent of both

in order:   lw waits 100 -> add x3 waits 100 -> add x5 waits 100, then runs
out of order: add x5 runs in cycle 1 while lw is still in flight
              add x3 runs when x1 arrives, retire stays in program order

The in order core stalls everything behind the load. The out of order core runs the independent add at once and retires all three in program order. Nothing about the program changed. Only the execution order changed.

The picture above uses a factory as the analogy: a CPU is RAM feeding a control unit, cache, and ALU, the same way a warehouse feeds a shop floor with a buffer, an operator, and a machine. In order execution processes job I1 fully (fetch, decode, execute, writeback) before I2 can leave its stall and move on, even though I2 was ready to decode two cycles earlier. Out of order execution lets I2, I3, and I4 slide left into the cycles I1 leaves idle, so the same four jobs finish sooner without changing what each job does or the order results land in.

Example 2: interleaved independent chains. Compilers interleave independent work to fill load delay slots, but they can only see a few instructions ahead and must respect register pressure. A windowed core sees further:

lw   x1, 0(x10)
lw   x2, 0(x11)     # independent of line 1, runs in parallel
add  x3, x1, x5     # waits on line 1 only
add  x4, x2, x6     # waits on line 2 only

An in order dual issue core pairs lines 1 and 2, then stalls the pair of lines 3 and 4 until both loads complete. An out of order core runs each add as soon as its own load completes. When the two loads have different latencies, the difference shows up directly as saved cycles.

Example 3: false dependencies. These three instructions have no true link between lines 1 and 2. They only reuse the name x1.

add  x1, x2, x3     # writes x1
add  x1, x4, x5     # WAW on x1, no true link to line 1
add  x6, x1, x7     # reads only the second x1

An in order core with a single register file must run line 2 after line 1 completes, because both write the same physical register and line 2 would clobber a value line 3 might need. That ordering constraint is artificial. It comes from having 32 register names for an unbounded number of live values. Renaming removes it:

line  arch rd  physical tag  map state after rename
1     x1       p7            x1 -> p7
2     x1       p8            x1 -> p8 (line 1 keeps p7, both run free)
3     x1       p8            reads p8, the latest x1

After renaming, lines 1 and 2 write different physical registers and can execute in any order or in parallel. Only the true RAW from line 2 to line 3 remains, expressed as p8. This is the core idea of Tomasulo’s scheme: keep program order in the rename map and the retire logic, and let execution order follow data readiness instead.

The machinery that makes this work has six pieces, laid out roughly in the order an instruction meets them:

┌───────┐   ┌─────────┐   ┌─────────────┐   ┌───────┐
│ fetch │   │rename / │   │  ALU queue  │   │ ALU0  │
│   +   │──>│dispatch │──>│  MD queue   │──>│ ALU1  │
│predict│   │ROB alloc│   │  BR queue   │   │  MD   │
└───────┘   └─────────┘   │  LS queue   │   │  BRU  │
                          │ oldest 1st  │   │  LSU  │
                          └─────────────┘   └───────┘
                                 │              │
                               ┌─┬──────────────┬┐   ┌─────────┐
                               │       CDB       │──>│   ROB   │
                               │  wakeup by tag  │   │ retire  │
                               └─────────────────┘   └─────────┘

Instructions fetch and get renamed in order, sit in per-class queues until their inputs are ready, execute whenever a unit is free, broadcast results on a shared bus that wakes up anything waiting on that value, and retire in order at the end. The full walkthrough of each block, with the Verilog for each piece, comes later in this post. What matters for now is the shape: order is preserved at the two ends, fetch and retire, and set free in the middle.

So what should OoO actually buy us?

At this point the intuition sounds straightforward. If an instruction is waiting, the machine should stop waiting for it and find something else to do. Register renaming removes false dependencies, the issue queues let ready instructions move around stalled ones, and the ROB lets all of that happen without changing the architectural order.

So the obvious question is not whether out of order execution works in principle. It is:

After already building a well optimised dual issue core, how much performance is actually left for OoO to find?

The previous post already removed many of the stalls that an in order core can cheaply avoid. rv32i-super-FE has two issue slots, strong branch prediction, early branch resolution, BTB and RAS support, hazard cleanup, and full load-use forwarding. It reaches a CPI of 0.7271 on CoreMark, or 1.3752 IPC. The remaining headroom is therefore much smaller than it was for the original five stage pipeline.

That makes OoO an interesting test rather than an automatic upgrade.

Where OoO should become useful

The mechanism should become more valuable when there is something substantial to hide:

• Long memory latency. With caches and real misses, a load can leave dependent instructions waiting for many cycles while independent work further down the window remains executable.
• Multiple branches in flight. A larger speculative window should allow useful work beyond one unresolved branch instead of stopping dispatch at every branch.
• An out of order load/store queue. Memory operations should be able to execute when their addresses and dependencies are ready rather than waiting for in-order retirement.
• More memory bandwidth. A second load port gives the window somewhere to send independent loads instead of turning memory into the bottleneck.
• Wider issue. More execution width gives OoO more opportunities to exploit independent instructions, provided the workload actually contains them.

Those are the conditions under which the basic intuition should translate into a measurable advantage.

But there is a catch.

OoO does not get the reordering for free. Every instruction now pays for rename, ROB allocation, queue insertion, wakeup, selection and retirement. The question is whether the stalls it removes are large enough to repay that machinery.

So rather than assuming that OoO must be faster, I built it in stages and measured each one against the same cores and the same CoreMark workload.

The first experiment is deliberately the simplest: put OoO on the original single issue pipeline.

If the machinery itself is useful, it should at least reduce stalls there.

If it is not, the numbers should tell us exactly what the overhead costs.

Jump to final 9 config numbers

TL;DR / Results

The short version is that OoO does not automatically beat a well tuned in order core. The experiments show where the mechanism helps, where its overhead dominates, and what has to change before the balance flips.

• Single issue OoO on the plain pipe: rv32i-ooo is 17.4% slower than rv32i-pipe at O3 i100. With only a 1 IPC ceiling, the extra machinery has no throughput headroom to pay for itself.
• Single issue OoO with the optimised frontend: rv32i-ooo-FE still loses. Better prediction removes most of the branch penalty, but the rename, ROB, queue and retirement machinery still costs more than the remaining stalls it hides.
• Dual issue OoO: starting from rv32i-super-FE, the first correct implementation is much slower. Two measured fixes — routing MUL to the ALU pipes and resolving branches in the same cycle — recover 18.9% of its cycles.
• Final result: rv32i-super-oooo-FE reaches 3.5854 CoreMark/MHz at i100 O3. That is 13.1% ahead of the optimised single issue rv32i-pipe-FE, but still behind the tuned dual issue rv32i-super-FE at 4.6545.
• Why it still loses: the counters point mainly to one branch in flight, an in order single port load path, and the remaining JALR gates. The workload has too little long latency to make a 32 entry window worth its overhead.

The important result is therefore not simply that this OoO implementation loses on CoreMark. It is that the counters identify the conditions under which the answer should change: longer memory latency, multiple branches in flight, an out of order load/store queue, more memory bandwidth, or wider issue.

Jump to final 9 config numbers

The four in order designs in brief

These are the four non OOO variants from the previous post. They are the baselines every out of order result here is compared against, so their numbers are repeated below as a table, with the raw terminal block after it. All figures are O3, 100 iterations, rv32im, Verilator.

design               cycles     CPI      CoreMark/MHz   IPC
rv32i-pipe           38877313   1.3158   2.5722         0.7600
rv32i-pipe-FE        31540922   1.0675   3.1705         0.9368
rv32i-superscalar    30832113   1.0435   3.2434         0.9583
rv32i-super-FE       21484390   0.7271   4.6545         1.3752

rv32i-pipe. Plain five stage pipeline with forwarding and stall on load use. No prediction. Branch resolves at the end of EX. CPI 1.3158.

rv32i-pipe-FE. rv32i-pipe with the full treatment. Early branch resolution in ID gave the largest single gain, then the 2 bit predictor, the BTB, generalised load forwarding, the tournament predictor, and the JAL fast path with RAS. Total gain over baseline: +23.26%.

rv32i-pipe-FE waterfall (CoreMark/MHz gain per step):
early branch resolution      +8.557%
2-bit direction predictor    +6.547%
BTB                          +3.458%
false hazard cleanup         +0.002%
store data forwarding        +0.013%
generalised load forwarding  +1.996%
tournament predictor         +0.455%
JAL fast path + RAS          +0.080%
final: 1.0675 CPI, 3.1705 CoreMark/MHz

rv32i-superscalar. Dual issue, in order, unoptimised. CPI 1.0435, only 2.3% ahead of rv32i-pipe-FE, because it spent its extra width on the same avoidable stalls.

rv32i-super-FE. The rv32i-superscalar core with the same ideas applied in dual issue form. Load use forwarding was the dominant win at +17.026%, because a load RAW hazard that squashes slot 1 wastes two issue opportunities per stall cycle instead of one. Total: 1.435x over its own baseline, 46.8% ahead of rv32i-pipe-FE.

rv32i-super-FE waterfall (CoreMark/MHz gain per step):
early branch resolution      +7.871%
hybrid predictor             +6.489%
BR + HyBP combined           +1.350%
BTB + RAS                    +1.474%
hazard optimisation          +3.804%
luopt + fulu                 +17.026%
final: 0.7271 CPI, 4.6545 CoreMark/MHz

A counter instrumented rv32i-super-FE run showed where its remaining cycles go: slot 1 bubbles 19.1% of cycles, slot 1 squash 22.2%, of which 73.6% is control driven and 26.3% is load RAW driven. Control flow dominates the leftover loss. That breakdown matters later, because rv32i-super-oooo-FE attacks exactly this loss and the numbers say how much of it was actually recoverable.

Why wider in order gets hard

A dual issue in order core can retire two instructions per cycle only when the pair is independent. This pair cannot dual issue:

add  x1, x2, x3     # writes x1
add  x4, x1, x5     # reads x1, must wait

This pair can:

add  x1, x2, x3     # writes x1
add  x4, x6, x7     # touches nothing the first writes

Checking that condition in hardware means comparing every destination of every earlier in flight instruction against every source of every candidate instruction, every cycle. For dual issue the checks split into two groups: intra cycle (slot 0 destination vs slot 1 sources) and cross cycle (both slots vs the previous cycles results still in flight). The previous post counted roughly 8 forwarding cases for dual issue and about 44 for four wide before simplification. The count grows faster than the width because every new slot adds checks against every other slot and against every in flight producer.

Branches make it worse. If slot 0 holds a branch, slot 1 cannot safely execute until the branch outcome is known, so the second slot is restricted or squashed. Loads make it worse in the other direction: a load in either slot whose result the next pair needs forces the next pair to stall or squash. The in order core has exactly one tool for all of this: stop issuing. Every dependency, whether true or false, serialises the machine at the issue point. Out of order execution exists to stop paying that price for dependencies that are not real.

Worth pausing on that last sentence, because it is easy to read out of order execution as a superscalar feature. It is not. The dependency problem above shows up the moment a core has to decide what runs next, regardless of issue width. Out of order execution is a scheduling policy, and the design lineage below is where it fits into the broader picture, single issue included.

single cycle -> multicycle -> 5 stage pipe -> dual issue super -> OOO super
1 IPC max       1 IPC max     1 IPC max       2 IPC max           2 IPC max
slow clock      fast clock    overlapped      needs               finds
1 per cycle     1 at a time   1 per cycle     independent pairs   independent pairs

Single cycle is simple and slow. Multicycle improves the clock but keeps a CPI of 3 to 5 with one instruction in flight at a time. Pipelining overlaps the stages and raises steady state throughput toward 1 IPC. Deepening the pipeline past that point, superpipelining, shortens the clock but widens the misprediction penalty and stretches every producer to consumer distance, which is why the previous post stopped at 5 stages and removed overhead instead: early branch resolution, prediction, BTB, RAS, and generalised forwarding. Superscalar widened issue instead of deepening the pipe: two instructions per cycle when they are independent.

Out of order execution sits on top of any of these, not just the wide one. A single issue core still has an IPC ceiling of 1, but it can still stall on a dependency it did not need to respect, the same RAW, WAR, WAW picture from the examples above, just with one instruction moving instead of two. That is why this post builds and measures an out of order version of the plain single issue pipe first, before touching the dual issue core. If the mechanism only mattered at superscalar widths, that first build would be pointless. It is not: it isolates the cost of the machinery itself, separate from whatever the extra issue width does.

For the dual issue core specifically, with a realistic integer dependency rate $d$, the effective CPI floor is:

At $d = 0.3$ the floor is about 0.65. The optimised rv32i-super-FE measured 0.7271, which is why the headroom left for any further technique on that core was always small. That number frames the dual issue results later in this post, but the single issue results that come first are answering a different question: what out of order execution costs on its own, with no extra width to pay for it. The dual issue experiment then asks the more interesting question: once the core already has two places to execute, can OoO use those places more effectively than an in order scheduler can?

Tomasulo from zero: the blocks and what each one does

Tomasulo published the scheme in 1967 for the IBM 360/91 floating point unit. It generalises the older scoreboard idea by adding renaming, so write after write and write after read hazards no longer stall issue. Only true read after write dependencies constrain execution order. The six pieces of machinery were sketched above. Here is what each one actually does, and the Verilog behind the sketch.

Fetch and predict. Same job as in any pipelined core: deliver a stream of instructions with a predicted PC. Mispredictions are discovered later and flush everything younger. The deeper the window behind fetch, the more work a flush discards, which is why prediction quality matters more, not less, in an out of order core.

Dispatch and rename. Instructions enter in program order. Each architectural destination is assigned a fresh physical tag (in our build, the ROB index itself serves as the tag). Sources are looked up in the rename map to get the tag of their latest producer, or read directly if that producer has already completed. A ROB entry is allocated for every dispatched instruction. If the ROB or the target queue is full, dispatch stops. That stall is backpressure, and it is the only in order stall left in the machine.

// Rename sketch (simplified): architectural rs to physical tag,
// plus a ready flag that says whether the value is already in the ROB.
wire [4:0] tag_a = rename_map[id_rs1];
wire [4:0] tag_b = rename_map[id_rs2];
wire       rdy_a = rob_ready[tag_a];
wire       rdy_b = rob_ready[tag_b];
// rd gets a fresh tag at dispatch; WAW and WAR vanish by construction.

Issue queues (reservation stations). Each entry holds an op, its tags, and the values captured so far. An entry becomes ready when all its tags have been broadcast. Selection picks among ready entries, oldest first, so the oldest waiting instruction cannot be starved by younger ones. The queue is what decouples program order from execution order: position in the queue carries no scheduling meaning.

// Oldest first select (simplified): key 0 is the head, min key wins.
integer i;
always_comb begin
  pick = 4'hF; best = 4'hF;
  for (i = 0; i < 16; i = i + 1) begin
    if (iq_valid[i] && iq_ready[i] && (iq_key[i] < best)) begin
      best = iq_key[i];
      pick = i[3:0];
    end
  end
end

Execution units, split by class. This split deserves a careful explanation because it is the piece most often drawn as one box and implemented as several. Suppose all waiting instructions sat in one shared queue feeding one shared ALU, one multiplier, and one divider. A divide occupies the divider for 12 cycles. That is fine on its own, but every instruction behind the divide in a single ordered queue, including ALU ops whose unit is free, must wait: head of line blocking. Splitting the queue per class (ALU queue, MD queue, branch queue, load store queue) lets each class drain independently. A 12 cycle divide stalls only the MD queue. ALU ops keep flowing. Branch resolution keeps flowing. Each queue has its own wakeup and select, sized to its own latency: short queues for single cycle units, deeper tolerance for slow ones. The cost is that dispatch must steer each op to the right queue and each queue needs its own select logic, but the alternative is letting the slowest unit set the pace for all of them.

Common data bus (CDB). When a unit finishes, it broadcasts the result with its tag. Every queue entry comparing tags, and the ROB entry holding the tag, captures the value in the same cycle. One broadcast wakes all waiters. With two completions per cycle, two buses are needed, plus arbitration when more than two units finish at once.

Reorder buffer and retire. Results complete out of order but update architectural state in order. The ROB head retires when it holds a completed, nonspeculative result. Stores write memory at retire, never earlier, so a flushed wrong path instruction never corrupts memory. Branches confirm or trigger a flush at retire or at resolve depending on the design. Precise exceptions fall out of this structure for free: the architectural state always reflects a prefix of the program.

Walk Example 3 through these blocks to see them act together. Lines 1 and 2 dispatch in order and rename x1 to p7 then p8. Both issue to the ALU queue. They execute in whatever order the ALU is free, possibly line 2 first. Each broadcasts on the CDB with its own tag. Line 3 waits on p8 only and runs when p8 arrives. Retire writes p7, then p8, then line 3, in program order. The register file ends exactly as the in order execution would leave it. The intermediate order left no trace.

What we built, part 1: rv32i-ooo on the unoptimised rv32i-pipe

The first experiment put a scalar Tomasulo core on the unoptimised rv32i-pipe base (rv32i-ooo): rename map, ROB, issue queue, single issue and single retire, predict not taken frontend. Same binaries, same Verilator flow, same retired instruction counts (any deviation would mean wrong path retirement; all runs matched). Result:

O3, Verilator. CM = CoreMark/MHz:

          rv32i-pipe          rv32i-ooo           cycles ratio   CM ratio
i1        402765 / 2.4828     472204 / 2.1177     1.172x         0.853x
i10       3900320 / 2.5639    4578130 / 2.1843    1.174x         0.852x
i100      38877313 / 2.5722   45639092 / 2.1911   1.1739x        0.852x
O2 i100   41275362 / 2.4228   48936322 / 2.0435   1.186x         0.843x

rv32i-ooo is slower everywhere: 17.4% more cycles at i100 O3. The cause is structural, not a bug. Both cores have a peak IPC of 1.0, so rv32i-ooo cannot retire faster than rv32i-pipe under any circumstances. What it can do is stall less. What it actually does is add per instruction overhead (rename, allocate, queue, select, retire) on every instruction while removing only some stalls. Worse, every taken branch flushes a deeper window with no predictor to soften it, so the branch penalty grows exactly where CoreMark is most sensitive. Out of order execution only removes stalls; here it added more cycles than it removed, with no ceiling gain to pay for them.

What we built, part 2: rv32i-ooo-FE

The natural reply is that the comparison is unfair: the rv32i-pipe side never got its predictor. rv32i-ooo-FE answers that: the same core with the optimised frontend (hybrid predictor, BTB, RAS). Branch flushes fell about 80% in relative terms, which confirms the predictor works in this pipeline too.

Absolute numbers at O3 i100:

rv32i-pipe       38877313 cycles   2.5722 CM
rv32i-ooo        45639092 cycles   2.1911 CM
rv32i-ooo-FE     40233631 cycles   2.4855 CM   (CPI 1.3617)
rv32i-pipe-FE    31540922 cycles   3.1705 CM

The predictor recovered most of the branch loss: 11.8% fewer cycles than the unprotected rv32i-ooo. But the absolute position barely moved past the starting line: still 3.5% more cycles than the plain unoptimised rv32i-pipe, and 27.6% more than rv32i-pipe-FE. The overhead accounting is now clear. Rename, allocate, queue, select, and retire logic touch every instruction whether or not any reordering happens. The load path is longer. Each remaining flush discards a deeper window. And the ceiling never moved: peak IPC is 1.0 on both sides. rv32i-ooo-FE on this workload is a cost without a ceiling gain. That lesson set up the third experiment: the only place out of order execution can pay is where extra width gives it something to fill.

What we built, part 3: rv32i-super-ooo-FE

The third experiment skipped rv32i-superscalar entirely (an OOO on it was never built) and started from rv32i-super-FE: hybrid predictor, BTB, RAS, dual port LSU with 2 loads per cycle, full forwarding, and single cycle MUL/DIV/REM in EX. One honest note about that base: its single cycle divider is unrealistic, and the comparison later keeps that in mind. The out of order core built on top, rv32i-super-ooo-FE, is 2 wide fetch, dispatch, issue, and retire, with a 32 entry ROB, a 16 entry issue queue split by FU class, dual ALUs, a dedicated MD pipe, a branch unit on pipe 0 only, dual CDBs, positional flush tags, and the hybp/BTB/RAS frontend kept as is. Loads and stores execute at retire in order, and dispatch allows only one branch in flight at a time. Those last two are limitations, and the numbers later say exactly what they cost.

The parts not shown in the picture: flush uses positional tags, and a rename map restore accompanies every redirect.

2 wide fetch + predict
  -> 2 wide dispatch + rename -> ROB 32
       -> ALU IQ -> ALU0, ALU1 ─┐
       -> MD IQ  -> MD         ─┼─ dual CDB -> ROB -> 2 wide retire
       -> BR IQ  -> BRU pipe 0 ─┘
       -> LSQ    -> LSU at retire (in order)
flush: positional tags, map restore at redirect

Bring up was done against correctness first, performance second, and the process is worth describing as it happened because several of the faults were in shared units, not in the new out of order logic. The M extension tests came first, before any CoreMark run: 7 small directed programs, each targeting one corner (multiply, divide and remainder, divide by zero, overflow, CSR). The MULH family failed at once with zero in rd, which pointed straight at the multiply unit; reading alu.v showed the product was computed in 32 bits and the upper half taken with a 32 bit shift, which is zero by construction. The fix was explicit 64 bit intermediates with per variant sign handling. The divide and remainder edge test failed next with a wrong quotient for INT_MIN divided by -1, which pointed at the divide result mux: that case used an unsigned -1 literal, which made the whole mux unsigned and corrupted the signed quotient. A signed literal fixed it. The divide by zero tests failed with 1 in rd; the spec wants all ones. The pipe core had run CoreMark clean with the same ALU, so all three faults passed through the benchmark without noticing, which says more about CoreMark’s coverage of the M extension than about the ALU. The directed tests exist because the benchmark cannot be trusted to exercise corners.

// MULH width fix: the 32 bit product has no upper half to take.
wire [31:0] prod32 = a * b;
assign res_before = prod32 >>> 32;   // 0, always

wire [63:0] prod64 = a64 * b64;      // sign per MULH/MULHSU/MULHU
assign res_after = prod64[63:32];

// Signed divide fix: unsigned -1 literal made the mux unsigned.
res_before = is_min_div_neg1 ? -32'd1  : ($signed(a) / $signed(b));
res_after  = is_min_div_neg1 ? -32'sd1 : ($signed(a) / $signed(b));

// DIVU by zero: the spec value is all ones.
res_divu = (b == 32'b0) ? 32'hffff_ffff : (a / b);

Retire had its own fault, found the same way: the CSR directed test showed each retired read returning the previous instruction’s CSR value, one instruction late. Reading the retire path showed the read used the flopped CSR address, so the value belonged to the previous cycle’s instruction by the time the retiring instruction sampled it. A second combinational read port indexed by the ROB head’s CSR address fixed it, and the CSR directed test confirmed it. The flush path needed positional tags so that a redirect kills exactly the instructions younger than the branch, with a guard so an entry can never match its own tag and kill itself, plus a rename map restore that the first version simply missed. That one surfaced as state corruption right after taken branches; comparing dumps at the first divergent retire showed a stale mapping surviving a mispredict. The self kill guard came from reading the tag distance logic, where an entry with no guard could match its own tag. The Verilator build warnings flagged 9 latch inferences across the new logic; explicit defaults removed all of them with bit identical state afterwards. FENCE needed no special path at all: it retires at dispatch with done set, and a directed test with FENCE and FENCE.I sequences confirmed innocent passage. Reading the select loops during this period also settled the oldest first question by construction: key 0 is the minimum and always wins, so the head ready entry cannot be skipped.

// CSR retire fix: read the retiring entry directly, not the flopped address.
assign csr_rdata2 = csr_file[rob_csr[rob_head]];

// Positional flush (simplified): kill younger entries, never self.
kill = flush_valid && (tag_dist(entry_tag, flush_tag) != 5'd0)
       && is_younger(entry_tag, flush_tag);

The correctness bar for every change was fixed: 7 directed M tests pass, the 31 test suite passes 31/31, binary search and fibonacci match bit for bit, and all 9 CoreMark configs reach HALT with exact state. Retired instruction counts are identical across every variant and config, which is the strongest single check that no wrong path instruction ever retired:

retired instructions, every variant, Verilator:

config   i1        i10       i100
O2       322977    3102274   30899090
O3       307171    2965056   29546307
Ofast    307169    2965054   29546305

Two footnotes on that table, both found by state comparison rather than by failure. rv32i-super-FE once showed 307172 at i1 O3 against our 307171: a halt edge counting difference of one instruction, with identical memory. And it leaves x2 at 0x80001010 from a post ecall overrun in its halt path while ours stops at the initialised 0x80001800; every other register and all of memory match. Fibonacci retired 215 instructions after the later retiming work against 214 before, again with bit identical state: a halt edge shift, not a behavior change. The testbench also had its own quirks worth one line: back to back 12 cycle divides trip its 33 stable PC loop detector (found because the div tests failed only when DIVs sat adjacent; reading the testbench showed the detector), so the directed tests space divides out, and Icarus log buffering hides output when a run hangs, so hangs were diagnosed from binary freshness and state dumps.

First measurement of the correct rv32i-super-ooo-FE at i1 O3: 355184 cycles, CPI 1.1563, CoreMark/MHz 2.8154. Against rv32i-super-FE at 223472 cycles that is 1.59x in cycles, or 0.629x of that core. Correct, and slow. The next section is about finding out why.

Finding the stalls: counters and two fixes

Non functional stall breakdown counters were added to the RTL ([OOO] lines printed at halt, kept in the design afterwards). The first counter run showed retire slot 0 idle roughly 41% of cycles. An out of order core that cannot keep its own retire fed is either starved at dispatch or blocked at issue, and the counters split those cases per pipeline point. Two fixes came out of the data, plus one failed attempt that was reverted.

Fix 1: MUL to the ALU pipes. The [OOO] dump ranked MD busy far above every other stall counter at about 38K cycles. Counting multiplies in the disassembly gave 9491, and 9491 times 4.01 matches the counter almost exactly, which proved every multiply paid the full 4 cycle MD latency. Reading the dispatch steer showed why: every M extension op, including single cycle multiplies, was routed to the 4 cycle non pipelined MD pipe. The steer was changed to match DIV class only (funct3 bit 2 set), leaving MUL class as single cycle dual issue through the ALU pipes. The MD pipe kept a realistic 12 cycle divide; CoreMark executes 6 divides, so that latency is negligible here and honest everywhere else.

// Dispatch steer: DIV class to MD, MUL class to the ALU pipes.
wire is_div_cls = (opcode == OP_M) && (funct3[2] == 1'b1);
wire disp_m = is_div_cls;   // was: (opcode == OP_M)

Saved about 31K cycles: 355184 to 324415, down 8.7%. CoreMark/MHz 2.8154 to 3.0825.

Fix 2: same cycle branch resolve. After fix 1 the dump still showed two large branch counters: about 33K head execute waits and about 14K redirect stalls. Tracing a taken branch through the RTL showed the 3 cycle sequence behind them: latch in the dispatch section, resolve a cycle later, redirect a cycle after that. The fix latches the branch operands early, resolves inline with blocking regs, and lets the flush capture the redirect directly. One implementation detail mattered: combinational wires read stale values mid block in this style, so the inline resolve had to use regs (the first cut used wires and resolved stale values, which the state compare caught at once). After the change the branch wait counter reads 0, the redirect stall counter reads 0, and total flushes fell from 15193 to 14871.

branch timing, taken branch:

before:
  cycle N:    latch branch in dispatch
  cycle N+1:  resolve in BRU, redirect computed
  cycle N+2:  redirect takes effect        2 lost cycles per taken branch

after:
  cycle N:    latch early, resolve inline, flush takes redirect
  cycle N+1:  fetch on the correct path   hx_bru 0, hb_red 0

// Early BRU resolve (simplified): latch early, resolve inline.
// Blocking regs, because comb wires read stale mid block here.
br_rs1 = rs1_val; br_rs2 = rs2_val;
br_taken = br_compare(br_rs1, br_rs2, funct3);

Saved about 36K cycles: 324415 to 288142, down 11.2%. Combined with fix 1: 355184 to 288142, down 18.9%. With both fixes in, the core becomes rv32i-super-oooo-FE; every number from here on is that core.

The reverted attempt: same cycle load retire. With branches fixed, the 1 cycle load completion bubble (lq_oth about 31K) looked like the next target. Same cycle load retire hung, and the state dump showed the signature: the ROB head never completed, stuck waiting on data that never arrived. Tracing the path showed the cross module combinational load data arrives stale mid block because of event ordering, so the fresh ROB entry never saw its own data. The change was reverted. That bubble is structural to this blocking assignment style; only earlier address generation issue shrinks it, not faster sampling at retire. It stays in the final numbers below.

An exoneration worth keeping. A miss counter flagged thousands of cycles where a ready queue head sat unissued with its FU free (q_alu_f 5445, lq_f 2934). That smells like a select bug, so a trace was added that printed the full machine state on every miss. Every one of the 5445 ALU misses showed both lanes idle with ALUs free: the ROB was empty because dispatch had just refilled it, and select runs on the pre edge queue while the snapshot was taken post dispatch. Same cycle dispatch to issue is impossible in this style, so these are frontend bubbles misclassified as misses, not lost wakeups. The only fix is keeping the ROB non empty, which points at the dispatch gate discussed in the gap section.

Post fix counters for rv32i-super-oooo-FE, table plus raw dump (i1 O3, Icarus; Verilator reads 288142, agreement to within 1 cycle):

The chart groups the long tail into “Other” and adds a “Useful work (retire)” bar for scale: even after both fixes, the machine spends more cycles held at the branch gate alone than it spends on anything else in the dump except retiring instructions.

[OOO] 288141 cycles, disp 347994, retired 307171, flushes 14871 (was 15193)
hold bar 69781
idle: empty 7988, ldar 50259, ex 23766
hx:   alu 11642, bru 0 (was ~33K), iqr 12067
lq:   alu 16451, iqr 2934, oth 30874
hb:   br 66621, red 0 (was ~14K), jalr 3154
split q: alu_f 5445, bru 6622, lq_f 2934, alu_b 0, md 0, lq_b 0

Small tests for rv32i-super-oooo-FE after the fixes: binary search runs 601 cycles against the 643 cycle rv32i-super-FE golden with 463 retired and exact state, down 6.5%, which is a genuine win on branch heavy tiny code. Fibonacci runs 285 cycles, down from 296. The 31 test suite halts in 62 cycles, down from 69, 31/31 PASS. The M suite stays 7/7. Verilator builds with 0 latches and no new warnings.

BS 601c/463r exact (golden 643c, down 6.5%)
FIB 285c/215r exact (was 296c, down 3.7%)
31t 62c 31/31 PASS (was 69c, down 10.1%)
M 7/7 PASS, Verilator 0 latches, no new warnings

CPI waterfall at i1 O3:

 1.1563  rv32i-super-ooo-FE (start)
-0.1002  MUL to ALU pipes
-0.1180  same cycle BRU resolve
 =======
 0.9381  rv32i-super-oooo-FE (final)

Final numbers

Verilator, all 9 configs of rv32i-super-oooo-FE to HALT, all exact state. Improvement over the rv32i-super-ooo-FE start is uniform: 18.6% to 19.3% fewer cycles in every config.

config      OOOO cycles  OOOO CM  base CM   ratio
i1_o2       304182       3.2875   4.2440    0.775x
i10_o2      2938906      3.4026   4.4102    0.772x
i100_o2     29314448     3.4113   4.4269    0.771x
i1_o3       288142       3.4705   4.4748    0.776x
i10_o3      2796479      3.5759   4.6377    0.771x
i100_o3     27891100     3.5854   4.6545    0.770x
i1_ofast    285153       3.5069   4.4737    0.784x
i10_ofast   2775834      3.6025   4.6372    0.777x
i100_ofast  27678505     3.6129   4.6535    0.776x

Where the final core sits at i100 O3, best first:

Two comparisons matter. Against rv32i-pipe-FE, rv32i-super-oooo-FE leads by 13.1% (3.5854 vs 3.1705): width plus reordering beats a tuned single issue core. Against rv32i-super-FE, it trails by 1.29x in cycles (288142 vs 223472 at i1 O3). The fixes recovered a fifth of the core’s own cycles and none of that changes the second comparison enough. The next section explains the gap with counter shares.

Why rv32i-super-oooo-FE still trails its in order base

The result looks backwards if you only think of OoO as “finding work that would otherwise be stalled.” The important question is what is actually preventing this particular OoO machine from finding that work.

Four items show up in the counters, ordered by measured size.

1. The single branch dispatch gate. Dispatch allows one branch in flight at a time, and the hold counter for that gate reads 66621 cycles: 23.1% of the run, the largest single counter in the dump. While a branch is in flight, dispatch stops, the ROB drains, address generation completes at the queue head with nothing behind it, and the machine pays the ROB empty bubbles the trace exonerated earlier. This is the binding constraint. Removing it means multiple branches in flight with branch unit squash on redirect, and the risk is real: out of order GHR updates can hurt prediction on history sensitive kernels. It was not attempted.

2. The in order LSU. Memory ops execute at retire, one load per cycle, against a base that sustains 2 loads per cycle from a dual port LSU with forwarding. Add the 1 cycle settle bubble the reverted fix failed to remove (lq_oth 30874, or 10.7% of cycles) and the load path is slower in every dimension: issue rate, latency tolerance, and forwarding. An out of order load path with a second port is the largest structural change remaining.

3. The JALR gates. JALR blocks all dispatch while in flight (hb_jalr 3154, 1.1%), and JALR issue waits for no branch in flight (q_bru 6622, 2.3%). The counters put 6.6K cycles behind the issue gate and 3.2K behind the dispatch gate, and the issue gate looks removable: JALR skips the GHR and BTB updates are order insensitive, so waiting gains nothing. That is the cheapest identified win, around 2%, and it was left in place as the stopping point.

4. The honest divider. The 12 cycle divide was kept deliberately against the base’s single cycle divider. Six divides in CoreMark make this worth almost nothing here, but the comparison flatters the base on any divide heavy code and the numbers above should be read with that in mind.

Net: rv32i-super-oooo-FE wins where the workload has branch heavy bursts its window can absorb (binary search beats rv32i-super-FE by 6.5%) and loses where rv32i-super-FE already removed the same stalls at lower cost (CoreMark, by 1.29x). That core sits at 89.5% of its available headroom from the previous post’s accounting; there was little left to find, and the finding cost more than it returned.

Reproduce it: commands and raw output

Toolchain: Verilator 5.032, Icarus 12.0, riscv64 linux gnu toolchain with riscv32 objdump and objcopy symlinks. CoreMark figures are Verilator only throughout; Icarus was used for fast iteration and agrees to within 1 cycle.

sudo apt-get install -y iverilog verilator gcc-riscv64-linux-gnu

iverilog -g2005 -f tb/tb_program.f -o /tmp/supoo.vvp
make verilator-prog

python3 scripts/elf2hex.py coremark_i100_o3.elf hex/inst_mem.hex hex/data_mem.hex
./obj_dir/Vtb_program

cat tb_program_results.txt
cp tb_program_results.txt tb_program_results_i100_o3.txt

The results parser, same shape as the previous post:

import re

def parse(path):
    txt = open(path).read()
    cycles = int(re.search(r"Total cycles:\s*(\d+)", txt).group(1))
    inst = int(re.search(r"Retired instructions:\s*(\d+)", txt).group(1))
    return cycles, inst

runs = [
    ("O3", 1, "tb_program_results_i1_o3.txt"),
    ("O3", 10, "tb_program_results_i10_o3.txt"),
    ("O3", 100, "tb_program_results_i100_o3.txt"),
]

for opt, iters, path in runs:
    cycles, inst = parse(path)
    cpi = cycles / inst
    ipc = inst / cycles
    cm_mhz = (iters * 1_000_000) / cycles
    print(f"{opt} ITER={iters}: cycles={cycles}, inst={inst}, "
          f"CPI={cpi:.9f}, IPC={ipc:.9f}, CoreMark/MHz={cm_mhz:.9f}")

Raw output for rv32i-super-oooo-FE:

O3 ITER=1: cycles=288142, inst=307171, CPI=0.938050793, IPC=1.066040355, CoreMark/MHz=3.470511067
O3 ITER=10: cycles=2796479, inst=2965056, CPI=0.943145425, IPC=1.060281876, CoreMark/MHz=3.575925297
O3 ITER=100: cycles=27891100, inst=29546307, CPI=0.943979226, IPC=1.059345347, CoreMark/MHz=3.585373112

Directed M extension tests build with the bare metal flow (as, then ld with the link at 0 script, because gcc -Ttext fails on this target):

riscv64-linux-gnu-as -march=rv32im_zicsr_zifencei -mabi=ilp32 -o mtests/div0a.o mtests/div0a.s
riscv64-linux-gnu-ld -m elf32lriscv -T test_hex/link_at_0.ld -o mtests/div0a.elf mtests/div0a.o
python3 scripts/elf2hex.py mtests/div0a.elf hex/inst_mem.hex hex/data_mem.hex
./obj_dir/Vtb_program

mul PASS, divrem PASS, divu PASS, div0a PASS, div0b PASS, ovf PASS, csr PASS
7/7 PASS, 31 test suite 31/31 PASS, CoreMark 9/9 HALT exact state

What this does not cover

Caches would change the CPI story considerably: a load miss penalty makes the memory level parallelism of an out of order LSU worth far more than anything measured here with ideal memory. Multiple branches in flight with squash, an out of order load store queue with a second port, and wider issue are the three structural changes the gap analysis points at, in that order. Timing closure, Fmax, area, and power need synthesis, which this post does not attempt; the forwarding muxes, extra register file ports, tag comparators, and broadcast buses added here all have direct critical path consequences that simulation does not expose. Prefetching, value prediction, and memory dependence prediction were not touched.

Analysis: why out of order loses here, and where it would win

The sections above measured the gap. This section takes standard out of order performance models off the shelf, plugs the measured numbers into them, and reads off two answers: why all three out of order cores lose on CoreMark, and what workload would flip the sign. Each table is followed by its raw numbers.

CPI decomposition

The Karkhanis and Smith model, building on Austin Sohi, writes sustained CPI as ideal CPI plus classified stall terms:

An in order core pays every hazard in full. An out of order core overlaps part of the branch and memory terms through its window, and its machinery adds structural stalls of its own. The standard decomposition behind it:

In an in order core the stall term sums every raw hazard, and every hazard stops the pipeline. In an out of order core the stall term keeps only what bypassing cannot remove, because independent instructions issue around stalls. The speedup form of the same idea:

Measured CPI budgets (ideal CPI is 1.0 for 1 wide cores and 0.5 for 2 wide cores):

base              OOO                    config   base CPI  OOO CPI  gap      ideal  base stalls  OOO stalls
rv32i-pipe        rv32i-ooo              O3 i100  1.3158    1.5447   +0.2289  1.0    0.3158       0.5447
rv32i-pipe-FE     rv32i-ooo-FE           O3 i100  1.0675    1.3617   +0.2942  1.0    0.0675       0.3617
rv32i-super-FE    rv32i-super-oooo-FE    O3 i1    0.7275    0.9381   +0.2106  0.5    0.2275       0.4381

In all three pairs the out of order core pays more stall CPI than its in order base, by 0.2289, 0.2942, and 0.2106. The window’s overlap savings are already netted inside those numbers, so the verdict is direct: on CoreMark the machinery’s own stalls exceed whatever the window hides. The [OOO] counters itemise the wide core’s side (cycles per 307171 retired instructions):

stall source                  cycles  CPI ceiling  share
branch gate (hb_br)           66621   0.2169       23.1%
dispatch held (bar)           69781   0.2272       24.2%
retire idle load (ldar)       50259   0.1636       17.4%
load settle (lq_oth)          30874   0.1005       10.7%
retire idle exec (ex)         23766   0.0774       8.2%
load queue waits (lq_alu)     16451   0.0536       5.7%
issue waits (hx iqr)          12067   0.0393       4.2%
head ALU wait (hx_alu)        11642   0.0379       4.0%
ROB empty (empty)             7988    0.0260       2.8%
JALR issue wait (q_bru)       6622    0.0216       2.3%
ready unissued ALU (alu_f)    5445    0.0177       1.9%
JALR dispatch gate (hb_jalr)  3154    0.0103       1.1%
ready unissued LQ (lq_f)      2934    0.0096       1.0%

Each row is a ceiling, not an addend: the counters overlap (four rows already sum past the total stall CPI), so each bounds what removing that stall could save. Two readings survive the overlap. First, the branch gate holds 66621 cycles while the whole run exceeds the in order base by 64670, so the gate alone covers 103.0% of the gap. Second, 66621 of the 69781 dispatch held cycles are the gate, so 95.5% of dispatch backpressure is that one restriction. Booked as structural stalls, the gates explain the +0.2106 on their own.

Latency hiding and the window formula

The companion formula bounds what any window can hide. If an event costs L cycles and the window holds W instructions at ideal IPC, the hidden part is:

Equivalently, effective latency is raw latency minus overlapped work:

Raw latency is the event cost in cycles. ILP is the average independent instructions available in the code stream. Overlap window is the ROB or reservation capacity looking ahead for that work. If ILP times the window reaches raw latency, hiding is complete and the event costs 0.

For the wide core W is 32 and ideal IPC is 2, so at most 16 cycles hide behind each event, and only with enough independent instructions in the window:

event   L       hidden               value
ALU op  1       1                    about 1 cycle
load    1 to 2  all                  1 to 2 cycles
divide  12      12 if 24 neighbours  up to 12 cycles

CoreMark here is a stream of L near 1 with an occasional L of 12, so the 16 cycle hiding capacity has almost nothing to act on, while every cycle pays gate and bookkeeping costs. The ILP form agrees: full hiding of a divide needs ILP of only 12/32 = 0.375 across its 12 cycles, which the measured IPC of 1.066 clears easily, so divide latency is plausibly fully hidden. It is just not worth much. Cost side: +64670 cycles, +28.9% over the base. That is the measured outcome, and the model accounts for it once the gates are booked as structural stalls: overlap near zero, added stalls near 0.21, net loss.

The critical path view

The Fields et al critical path model treats the pipeline as a directed acyclic graph: tokens flow through fetch, schedule, execute, and commit, with edges for data, resource, and control dependences. Runtime is the critical path through that graph, so an optimisation that does not shorten the critical path gains exactly 0.

The wide pair makes this concrete. The in order base runs CoreMark at IPC 1.3752, which is 68.8% of its 2 IPC ceiling. The out of order core reaches 1.0593, or 53.0%. The window plus its gates move away from the ceiling by 15.8 points: reorder lookahead shortens some data edges, but the branch gate, the JALR gates, and the single port load path add control and resource edges that were not there, and the additions win. In Fields terms the critical path got longer, not shorter, which is why the measured gain is negative.

Window limits: Wall and Little

Wall’s limit study bounds speedup by window size, renaming, and prediction:

$W$ is how far the engine looks ahead: 32 ROB entries here. $R$ is physical registers for renaming, which remove the WAR and WAW edges (the rename walkthrough above turned two writes of x1 into p7 and p8 for exactly this reason). $P$ is prediction accuracy, which decides whether the window stays full: 14871 flushes over 347994 dispatches is 4.27%, and the extra 40823 dispatches over retired instructions put wrong path dispatch overhead at 13.3%.

Little’s law bounds the throughput any window can sustain:

The textbook example: a 128 entry window with average latency 32 sustains 128/32 = 4 IPC:

Read the other way, sustaining IPC 2 with a mean instruction latency of m cycles needs a window of at least twice m entries. CoreMark here averages about 1 to 2 cycles per instruction, so a window of 2 to 4 entries suffices and the 32 entry ROB oversupplies the window by 8 to 16 times. The core is not window limited. It is gate limited. That is the counter table’s conclusion, reached without counters.

Where out of order wins

The overhead to beat is 0.21 CPI, about 21 cycles per 100 instructions, and each overlapped event can save at most 16 cycles. That fixes the breakeven for any workload trait:

workload trait              saving per event  breakeven vs 0.21 CPI
50c miss, window full       16 of 50 (32%)    about 1.3 misses per 100 insts
20c miss, window full       16 of 20 (80%)    about 1.3 misses per 100 insts
12c divide + 24 neighbours  up to 12c         about 1.8 divides per 100 insts
1-2c events only (this CM)  up to 2c each     never
branch gate removed         up to 0.2169 CPI  closes gap if overlap small

Two more levers move the breakeven. A larger window hides more per event (W of 64 hides 32 cycles, W of 128 hides 64) while select and wakeup costs grow with W. Better prediction wastes less window: each flush currently costs about 2.7 dispatches (40823 extra dispatches over 14871 flushes). CoreMark on single cycle memory sits at the worst point of this trade: minimum hideable latency with maximum gate exposure. A workload with a long miss about every 75 instructions, or dense divides with independent neighbours, is where the same 32 entry window earns back its 0.21 CPI.

Model reference

Amdahl’s law against the out of order models:

aspect           Amdahl's law               OOO analytical models
focus            coarse parallel vs serial  fine latency hiding + overlap
limiting factor  serial software portion    window W + mispredict rate
metric           speedup S                  CPI reduction

Summary of the gain each model quantifies:

metric        in order      OOO                     gain
data hazard   full stall N  about 0 if work exists  dCPI about N per stall
memory stall  miss latency  latency minus overlap   scales with ROB/latency

Summary

Out of order execution keeps program order in the rename map and reorder buffer while letting data readiness decide execution order. Renaming removes false dependencies, issue queues let ready instructions move around stalled ones, the CDB wakes dependent instructions, and in order retire keeps architectural state precise. The mechanism works, and the core passed the full ISA test suite.

The interesting part was what happened when it was measured. The first OoO versions lost to the in order cores, but the gap got smaller as the design was fixed. The final rv32i-super-oooo-FE was 18.9% faster than the first correct OoO version after routing MUL through the ALU pipes and resolving branches in the same cycle. It reached 3.5854 CoreMark/MHz, 13.1% ahead of the optimised single issue rv32i-pipe-FE, but still behind the 4.6545 CoreMark/MHz of rv32i-super-FE.

The counters explain why. A single branch dispatch gate held the machine for 23.1% of cycles, the OoO LSU was still limited by an in order single port load path, JALR introduced another 3.4% of combined gating, and the divider was deliberately modelled at a realistic latency while the baseline had an unrealistic single cycle divider. These are not problems that simply disappear because the core is out of order.

The bigger lesson is that OoO needs the right workload to pay for its own machinery. This experiment uses ideal memory with no caches, so there are almost no long memory stalls for the instruction window to hide. CoreMark at these widths also does not provide enough latency and independent work to make a large ROB particularly useful. rv32i-super-FE had already removed much of the easy performance loss, so adding OoO mostly added machinery without giving it enough work to exploit.

That does not make the OoO implementation pointless. It shows where the next experiment needs to go. Caches, real memory latency, more memory-level parallelism, multiple branches in flight, a wider OoO LSU, and wider issue all change the amount of independent work available to the window. The next step is therefore not simply making this OoO core more complicated, but changing the workload and memory system so that there is something for the OoO machinery to hide.

Out of order execution is the right tool when the window holds work that the issue logic cannot otherwise reach. On this small CoreMark configuration, it mostly did not. That is probably the most useful result of the experiment.