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

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.