Tomasulo Algorithm
Simulation
Doaa Saad – Gamal Ibrahim
The American University in Cairo / Dr. Cherif Salama
I. Objective
The primary goal of this project is to implement a simplified out-of-order processor
simulator based on Tomasulo’s algorithm. The simulator is designed to model
dynamic scheduling, operand forwarding, and register renaming through reservation
stations and tags. In addition to correctly executing instructions, the simulator must
support configurable hardware parameters such as the number and types of
reservation stations and their execution latencies. It also allows multiple instructions
to be issued per cycle, thereby modeling wider pipelines. The final objective is to
evaluate its performance on several test programs that include arithmetic
instructions, loads and stores, branches, calls, returns, and loop structures.
II. Implementation Overview
The simulator is implemented as a collection of interacting software components
that together mimic the behavior of an out-of-order pipeline. The core architectural
blocks include classes representing memory, instructions, registers, reservation
stations, and the simulator driver. The system follows a strict pipeline model: during
each clock cycle, it first attempts to write back results from instructions that have
completed, then advances execution within each active reservation station, and
finally issues new instructions into the pipeline when free hardware resources are
available. Instructions transition through states such as INITIAL, ISSUED,
EXECUTINGOFFSET for address calculations, EXECUTING for the main
operation, EXECUTED, and finally WRITTEN at the write-back stage.
Pipeline Model
At each clock cycle:
• Write back results of completed instructions.
• Execute instructions in busy reservation stations.
• Try to issue new instructions.
Instruction states:
• INITIAL
• ISSUED
• EXECUTINGOFFSET (address calculation for loads/stores)
• EXECUTING
• EXECUTED
• WRITTEN
III. Data Structures and Control Signals
Global Vectors
• instructions: static list of program instructions.
• stations: configured reservation stations (functional units).
• registers: architectural register file (data + tag).
• loadStore: active load/store instructions for memory conflict checks.
• finished: dynamically issued instructions that have completed.
Global Scalars
• time: current cycle number.
• PC: index of next instruction to issue.
• branchesInFlight: number of unresolved control‑flow instructions.
• totalbranches: total committed branches/calls/returns.
• totalpredictionfail: number of mispredicted branches/calls/returns.
IV. Class Responsibilities
• Memory is modeled as a fixed-size integer array with bounds-checked load/store
operations and a small set of pre-initialized locations for test programs.
• The Instruction structure encodes opcode, source/destination register indices,
immediates, result value, and per-stage timing (issue, execute, write-back). It also
stores Tomasulo-specific state, including dependency information (producer tags,
branch dependencies) and status flags for each pipeline stage.
• Reservation stations implement out-of-order execution. Each entry records the
supported operation type, busy flag, operand values and readiness bits, producer
station tags for unresolved operands, and execution latencies for address/offset
calculation and the main operation. On issue, a free station is allocated and
marked busy. Memory operations first perform address calculation, then check
ordering constraints against older memory operations. Once all operands are
ready and conflicts resolved, the station executes for the configured number of
cycles and then transitions to a completed state, ready for write-back.
• The Register file holds architectural register values plus Qi tags that identify the
reservation station expected to produce the next value for each register. On issue,
source registers either supply a value (if no pending producer) or a Qi tag (if there
is a dependency). Destination registers are tagged with the allocated reservation
station to propagate dependencies to younger instructions.
• The Simulator coordinates global execution. Its main loop runs until all
instructions are issued and all reservation stations are idle. Each cycle is divided
into write-back, execute, and issue phases. In write-back, completed station
results are broadcast to the register file and all dependent stations, memory is
updated for stores, and branch outcomes are resolved to detect mispredictions.
The execute phase advances instruction latencies and transitions stations from
address-calculation to execution and from execution to completion. The issue
phase selects the next instruction, finds a compatible free station, and binds
register dependencies via Qi tags. The simulator also records per-instruction
timing and aggregates performance metrics for reporting.
V. Simulator Implementation
Key methods:
Simulate():
• Call WriteBack().
• Call Execute() on all busy stations.
• Call Issue() up to issues times.
• Increment time.
WriteBack(): For each busy station whose currentInst is EXECUTED:
• For ALU instructions:
• Write result to any register tagged with this station.
• Forward result to other stations waiting on src1/src2.
• For STORE: Write value to memory at computed address.
• For BRANCH / CALL / RET:
• Update branch counters and misprediction count (when control flow diverges
from default).
• Update PC when control flow changes.
• Flush younger instructions waiting on that branch if needed.
• Remove instruction from loadStore (if applicable).
• Record writeTime and add instruction pointer to finished.
• Mark station as free.
Execute(): Call execute() on each busy reservation station.
Issue(): If PC still within program:
• Find a free station whose type list includes the instruction’s type.
• Create a dynamic copy of the static instruction template.
• Set its PC and issueTime.
• Handle branch tracking (branchesInFlight, LastBranch, branchWait, branch).
• Bind operands or dependency pointers using registers[].Qi.
• Tag destination register (except for STORE and R0).
• For LOAD/STORE: append to loadStore.
• Increment PC.
• allDone(): Returns true only when all stations have busy == false.
• printdata(): Prints performance metrics and the instruction timeline table.
allDone(): Returns true only when all stations have busy == false.
printdata(): Prints performance metrics and the instruction timeline table.
VI. Hardware Configuration and Multiple Issue
Reservation‑station Configuration
• Load units: ReservationStation({0}, speed=4, offspeed=2) × 2
• Store units: ReservationStation({1}, speed=4, offspeed=2) × 1
• Branch units: ReservationStation({2}, speed=1) × 1
• Call/return units: ReservationStation({3, 4}, speed=1) × 1
• Integer ALU units (ADD, ADDI): ReservationStation({5, 6}, speed=2) × 4
• NAND units: ReservationStation({7}, speed=1) × 2
• Multiply unit: ReservationStation({8}, speed=8) × 1
Issue Width
Parameter issues in Simulator constructor controls pipeline width. When issues > 1,
Simulate() calls Issue() multiple times each cycle. Up to issues instructions can be
issued in a single cycle if stations are free.
Expected impact
Changing number/latency of stations affects:
• Structural hazards (availability of units).
• Overall IPC and total cycles.
Increasing issues can:
• Increase parallelism when dependencies and resources allow.
• Stress the branch and memory systems due to more overlapping instructions.
VII. Test Cases
Test Case 1
Program:
1. LOAD R1, 10(R0)
2. ADD R2, R1, R1
3. NAND R3, R2, R1
4. ADDI R4, R3,-5
5. MUL R5, R4, R2
6. STORE R5, 20(R0)
7. CALL label 1
8. STORE R5, 40(R0)
9. Label 1:
[Link] R6, 40(R0)
[Link] R6, R0, 2
[Link] R6, 50(R0)
[Link]
Data:
• Memorylocation 10: Value = 1
• Memorylocation 20: Initialized to 2
• Memorylocation 30: Value = 0
• Memorylocation 40: Initialized to 0
Output:
Test Case 2:
Program:
1. LOAD R3,10(R0)
2. LOAD R2,20(R0)
3. Call Label 2
4. Label 2:
5. ADD R3, R3, R2
6. ADDI R2, R2,-1
7. BQE R2, R0, 2
8. RET
Output:
Test Case 3
Program:
1. ADDI R4, R0, 20
2. ADDI R3, R0, 0
3. ADDI R3, R3, 5
4. ADDI R3, R3, 5
5. BEQ R4, R3, 1
6. RET
Output: