Before you can read Tomasulo's algorithm, you need a small toolbox of ideas. Below is every symbol, structure, and word the parent note leans on — built from nothing, in an order where each one rests on the one before it. Nothing here is assumed; if the parent used it, we define it.
Picture it as a little machine with two input wires and one output wire.
Why the topic needs it: every rule in Tomasulo is phrased as "read the sources, produce the destination." If you can't see which register is a source and which is a destination, none of the hazard talk lands.
Think of the register file as a row of numbered lockers. R2 = 2 means locker number 2 currently holds the number 2.
Why the topic needs it: instructions only ever read from and write to registers (in this model). The name of a register — the number on the locker — is exactly the thing that will cause trouble in Section 5, so we pin it down now.
Why the topic needs it: out-of-order execution is the whole point. But it is only safe if we never break the answer the program expected — which is why we next study dependencies.
Two instructions can be related in a few ways. Getting these straight is the heart of everything. See data-hazards.
Why the topic needs it: the parent's entire "What Problem Does Tomasulo Solve?" section is about killing WAR/WAW hazards while respecting RAW. You must tell a real dependency from a fake one.
This is the single cleverest idea, so we build it slowly.
Why the topic needs it: tags are the renaming. When R1.tag = Mult1, the register R1 is no longer a number — it is a note saying "waiting for station Mult1." This is how two R1s become two different things.
Read the pairs like this: for each source you have either a value Vor a tag Q — never both, never neither.
Why the topic needs it: the whole algorithm is written in terms of Vj,Vk,Qj,Qk. If those four symbols are a blur, the pseudocode is unreadable. Their names are just: V = Value, Q = "Queue tag I'm waiting on"; j = first source, k = second source.
Why the topic needs it: the entire "Write Result" stage and the operand-capture in "Execute" happen over the CDB. The symbol ⟨tag,value⟩ appears constantly.
Every arrow means "you need the left idea to understand the right one." Notice the tag feeds both the reservation stations and the CDB — it is the glue of the whole design.
Cover the right side and answer out loud. If any stumps you, reread its section above.
In ADD R4, R1, R5, which register is the destination?
R4 — the leftmost one; R1 and R5 are sources.
What is a register file, in one image?
A numbered row of lockers, each holding one number.
What does "out-of-order execution" mean?
Running a later instruction before an earlier one finishes, when its data is ready.
What is a clock cycle?
The CPU's basic tick of time; a MUL taking 5 cycles is ready 5 ticks after it starts.
Which dependency is real and must always wait?
RAW (read-after-write) — a later instruction reads a value an earlier one produces.
Why are WAR and WAW called false dependencies?
They clash only because of a shared register name, not the data; renaming makes them vanish.
What is a tag?
A short label naming the station that will produce a value, e.g. Mult1.
In a reservation station, what's the difference between Vj and Qj?
Vj is the actual value if we have it; Qj is the tag we're waiting on if we don't.
What does Qj=NULL mean?
We already have source 1's value (in Vj); we're not waiting for anyone.
What does the execute condition Qj=NULL∧Qk=NULL say?
Both operands are ready, so the instruction may now run.
What travels on the Common Data Bus?
A pair ⟨tag,value⟩ — a finished station's name and its result.
Why broadcast a result to everyone instead of specific consumers?
Because at issue time nobody knows how many later instructions will need it; broadcasting once is simpler.
When every line above is easy, you're ready for Tomasulo's algorithm — or read it first in Hinglish. Related deeper dives: reorder-buffer, scoreboarding, memory-disambiguation.
