A fast processor runs instructions out of order (whichever has its inputs ready first), but the outside world must still see results appear in the exact order you wrote them. The reorder buffer is a waiting line that lets work finish in any order internally, yet lets results become "official" strictly oldest-first.
This page assumes nothing . Before you read Reorder buffer (ROB) you must own a handful of words and pictures. We build each one from the ground up, in an order where every symbol is earned before it is used.
An instruction is one tiny command the processor obeys, like "add these two numbers and store the answer". Think of it as a single line in a recipe.
We will write instructions like this:
ADD R 1 , R 2 , R 3
Read it as: "take the value in box R 2 R 3 R 1 R 1 , R 2 , R 3 registers — we define those next.
Everything the ROB does is about instructions : giving them a slot, watching them finish, and letting the oldest one become permanent. If you don't picture an instruction as one recipe line, nothing later makes sense.
A register is a tiny, named storage box inside the processor that holds one number. Names look like R 0 , R 1 , R 2 , …
Definition Register file (RF)The register file , written RF RF [ R k ] R k
Look at the figure: the register file is just a row of labelled cups. RF [ R 1 ] R 1 permanent and visible to the program.
Intuition Why the topic needs thisThe ROB's whole job is deciding when it is safe to pour a result into the register file. So you must first see the register file as the "official, permanent" state — the thing we must protect from being written in the wrong order.
We call the contents of the register file the architectural state : the state the program is supposed to have. Related reading: Register-file-management .
Program order is the top-to-bottom order in which you wrote the instructions. I1 before I2 before I3, always.
Definition Execution orderExecution order is the order in which instructions actually finish computing , which can be different — a quick add may finish before a slow multiply that came earlier.
In the figure, the left column is program order (I1, I2, I3, I4 top-down). The right column is when each instruction finishes : notice I3 finishes first because it is fast, even though it was written third. This mismatch is the entire reason the ROB exists — see Speculative-execution and Superscalar-processors for why processors bother finishing out of order at all.
Common mistake Common confusion"Out of order" does not mean the results become official out of order. Only the computing is out of order. The committing (pouring into the register file) stays strictly in program order.
Definition In-flight instructionAn in-flight instruction is one that has started (been issued) but has not yet become permanent (not yet retired). It is "in the air", still cancellable.
Imagine planes that have taken off but not landed. They are committed to nothing on the ground yet. If we cancel a flight (e.g. a wrong branch guess), no harm reaches the register file. The ROB is the airspace holding all in-flight planes.
Every instruction passes through three named moments. You must know all three verbatim.
Definition Issue, Execute, Retire
Issue : the instruction is admitted and given a slot. Happens in program order .Execute : the instruction actually computes its answer. Happens out of order , whenever inputs are ready.Retire (also called commit ) : the finished result is poured into the register file and becomes permanent. Happens in program order , oldest first.
This trio appears throughout Instruction-retirement and is the backbone of the parent note.
Definition Queue and FIFOA queue is a line, like people waiting at a shop. FIFO means "First In, First Out": whoever joined first leaves first. No pushing ahead.
The ROB is a FIFO because retirement must be in program order — first issued, first retired.
Definition Circular bufferA circular buffer is a fixed row of N
The figure shows N = 8
Definition Head and Tail pointers
Head points at the oldest in-flight instruction — the next one allowed to retire.Tail points at the next free slot — where a newly issued instruction goes.
As instructions retire, Head walks forward. As new ones issue, Tail walks forward. Both loop around the ring.
The only symbol from mathematics the parent note uses is mod . We define it from zero.
a mod N a N remainder . It answers the question "where do I land on a clock with N a
Intuition Why THIS tool and not plain addition?On a straight row, "advance the pointer" is just tail = tail + 1 off the end . We need advancing to wrap back to slot 0. Modulo is exactly the wrap-around counter — it is the mathematical name for a clock. No other operation gives "loop back to start after N".
next_tail = ( tail + 1 ) mod N
Worked example Concrete numbersLet N = 8 tail = 7 ( 7 + 1 ) mod 8 = 8 mod 8 = 0.
Common mistake Off-by-one trap8 mod 8 = 0 not 8 not 1 0 … N − 1
Two conditions decide whether the ring can accept or release work.
Intuition Why "tail+1 = head" means full, not emptyIf we let tail reach head, we could not tell full from empty (both would read head = tail one slot always empty as a spacer. When the tail is just one step behind head, the ring is declared full. This costs one slot but removes the ambiguity.
A completed instruction that is not at the head must wait — its answer sits in the ROB slot, not in the register file. This waiting is the essence of in-order retirement.
A tag is just the ROB slot number used as a temporary name for a result-in-progress. Instead of "wait for register R 1
Intuition Why rename to a slot number?Two different instructions might both write R 1 R 1 which R 1 Register-renaming , and the same idea powers Tomasulo-algorithm and Reservation-stations .
Instruction = one recipe line
Register and register file
Architectural state = official values
Program order vs execution order
Issue Execute Retire stages
Circular buffer with Head and Tail
Modulo wrap-around counter
Full and empty conditions
Slot status pending completed exception
Tag = slot number as temporary name
Every arrow means "you must understand the source before the target makes sense." The whole graph funnels into the Reorder buffer (ROB) node. Downstream topics that reuse these foundations include Precise-exceptions , Branch-prediction , Memory-ordering , and Instruction-retirement .
Self-test: can you answer each before revealing?
What one line of a program does an instruction represent? One tiny command, like "add R2 and R3, store in R1".
What is the register file RF The shelf of permanent named boxes holding the program's official (architectural) values.
What does RF [ R k ] The number currently stored in box R k
Program order vs execution order? Program order = the written top-to-bottom order; execution order = the order instructions actually finish computing.
Name the three life stages of an instruction, and which are in-order. Issue (in order), Execute (out of order), Retire/commit (in order).
What does FIFO stand for and why does the ROB use it? First In First Out; retirement must follow program order, so oldest leaves first.
What does the Head pointer point to? The oldest in-flight instruction, next in line to retire.
What does the Tail pointer point to? The next free slot where a newly issued instruction is placed.
What is a mod N The remainder after dividing a N
Compute ( 7 + 1 ) mod 8 0
Empty condition of the ROB? head = tail
Full condition of the ROB? ( tail + 1 ) mod N = head
Why keep one slot always empty? So full and empty don't both read head = tail
What are the three slot statuses? pending, completed, exception.
Why can a completed instruction still not write the register file? If it isn't at the head, older instructions haven't retired yet; in-order commit forbids it.
What is a tag ? The ROB slot number used as a unique temporary name for an in-progress result.
