Simulate Tomasulo's Algorithm for Out-of-Order Execution

Topic Overview

Dynamic Scheduling with Reservations

Tomasulo's algorithm (1967) schedules instructions dynamically using reservation stations and a Common Data Bus (CDB). It renamed physical registers decades before modern Intel cores branded it differently.

cCopy
Loading…

Load and Store Queues

• Load buffer: tracks in-flight addresses, disambiguates stores
• Store buffer: holds retired stores until commit drains to cache

For example, an ADD waiting on a LOAD clears its qj tag when the load broadcasts its value on the CDB, allowing the adder to fire without writing the architectural register yet.

For this exercise, you will simulate two ALU stations and a CDB broadcast loop. This task asks you to compare Tomasulo scheduling against your in-order five-stage pipeline on the same instruction trace.

Working Through the Exercise

Keep the relevant datasheet, ISA manual, or architecture textbook chapter open while you implement. When your output disagrees with the reference trace on the same program, the bug is usually a mis-decoded opcode, a stale register read, or a flag bit left unchanged after arithmetic.

• Trace first: walk one failing input by hand before changing random lines
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

For this exercise, you will use those habits while implementing the requirement in the starter code. Microarchitectural product names change across CPU generations, but the control ideas (fetch, bypass, cache lines, vector lanes) stay stable enough to debug from first principles.

Your Task

Simulate Tomasulo's algorithm, the scheme behind out-of-order execution with register renaming. Instructions issue in order into reservation stations and capture their operands as either values or tags of the stations that will produce them. They execute when both operands are available, and broadcast their results on a common data bus (CDB) to every waiting station. A register alias table (RAT) maps each register to the station that will write it last, which removes WAR and WAW hazards.

Input

cCopy
Loading…

Values are integers; DIV truncates, and division by 0 gives 0.

Each cycle, in this order

1. Write result: of the stations whose execution finished in an earlier cycle, the one holding the earliest-issued instruction broadcasts on the CDB (one per cycle). Every station waiting on its tag takes the value. Every register whose RAT entry still names that station receives the value and its RAT entry is cleared. The station becomes free.
2. Execute: every busy station whose operands are both values starts executing. A station can start no earlier than the cycle after it was issued, or after it received an operand from the CDB. Starting in cycle c with latency L, it finishes at the end of cycle c + L − 1.
3. Issue: the next instruction in program order goes to the lowest-numbered free station of its kind. Otherwise issue stalls this cycle. Each source is read from the RAT: a tag if a station will produce it, else the register's value. Then RAT[Fd] is set to this station (renaming).

The simulation ends when every instruction has issued and every station is free (or after 300 cycles).

Output

One line per cycle: the parts that happened, joined by |, then the RAT.

cCopy
Loading…

• write lists the registers updated, or -> (no register: renamed away) when a later instruction has already renamed the destination (a WAW hazard, resolved).
• exec lists the stations that started this cycle, e.g. exec I0 (Mul1), I3 (Add2).
• issue shows each operand as j=VALUE or j=TAG; a stall prints issue stalled (no free ADD station) (or MUL).
• Print wait when nothing happened, and | RAT ... only when some register is renamed (in register order).

Instructions are named I0, I1, … Finally: finished in C cycles: F0=.. F1=.. ... F7=...

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

I2 overwrote F1 while I1 was still waiting for the old F1. Renaming let both proceed, and the final registers match sequential execution.

Requirements

1. A reservation-station struct with busy, op, Vj, Vk, Qj, Qk, and a RAT of station tags; implement issue, execute and write_result as separate steps.
2. Only one CDB broadcast per cycle.

Hidden tests cover two results finishing in the same cycle (CDB contention), a WAR hazard, DIV including division by zero, and a long independent sequence limited by station count.