tomasulo

Pure-Python simulator of Tomasulo's out-of-order instruction scheduling algorithm. Implements reservation stations, a Common Data Bus (CDB), and register renaming for computer architecture education.

Zero runtime dependencies. Requires Python 3.10+.

Installation

pip install tomasulo

Or with uv:

uv pip install tomasulo

Quick start

from tomasulo import Instruction, TomasuloSim, render_trace

program = [
    Instruction(op="LOAD", dest="F6",  src1="R2", src2="R0"),
    Instruction(op="LOAD", dest="F2",  src1="R3", src2="R0"),
    Instruction(op="MUL",  dest="F0",  src1="F2", src2="F4"),
    Instruction(op="SUB",  dest="F8",  src1="F6", src2="F2"),
    Instruction(op="DIV",  dest="F10", src1="F0", src2="F6"),
    Instruction(op="ADD",  dest="F6",  src1="F8", src2="F2"),
]

sim = TomasuloSim(
    stations={"add": 3, "mult": 2, "load": 3},
    latencies={"ADD": 2, "SUB": 2, "MUL": 10, "DIV": 40, "LOAD": 2},
)
trace = sim.run(program=program)
print(render_trace(trace=trace))

Output:

   #  Op     Dest   Src1   Src2    Issue  ExecComplete   Write
---------------------------------------------------------------------
   1  LOAD   F6     R2     R0          1             3       4
   2  LOAD   F2     R3     R0          2             4       5
   3  MUL    F0     F2     F4          3            15      16
   4  SUB    F8     F6     F2          4             6       7
   5  DIV    F10    F0     F6          5            56      57
   6  ADD    F6     F8     F2          6             9      10

CLI

tomasulo examples/sample_program.txt
tomasulo examples/sample_program.txt --snapshots
tomasulo --help

Program file format -- one instruction per line:

# comments are ignored
LOAD F6  R2  R0
LOAD F2  R3  R0
MUL  F0  F2  F4
SUB  F8  F6  F2
DIV  F10 F0  F6
ADD  F6  F8  F2

Public API

@dataclass
class Instruction:
    op: str    # "ADD", "SUB", "MUL", "DIV", "LOAD"
    dest: str  # destination register e.g. "F0"
    src1: str  # first source register; for LOAD: base address register
    src2: str  # second source register; for LOAD: unused, pass "R0" by convention

@dataclass
class InstructionResult:
    instruction: Instruction
    issue_cycle: int
    exec_complete_cycle: int
    write_cycle: int

@dataclass
class Trace:
    results: list[InstructionResult]
    snapshots: list[CycleSnapshot]

class TomasuloSim:
    def __init__(self, stations: dict[str, int], latencies: dict[str, int]) -> None: ...
    def run(self, program: list[Instruction]) -> Trace: ...

def render_trace(trace: Trace) -> str: ...

Algorithm

Stage order each cycle: WRITE, then EXECUTE, then ISSUE.

Hazards handled:

• RAW: a station waits on the tag (Qj/Qk) of the station that will produce a missing operand. When that station broadcasts on the CDB the value is forwarded and the tag is cleared.
• WAR and WAW: handled by register renaming. Each issued instruction renames its destination to the station tag. Only the last writer commits to the register file.
• Structural: at most one result per cycle on the CDB. Ties broken by lowest station index (declaration order).

See docs/architecture.md for a full description.

Development

uv venv && uv pip install -e ".[dev]"
uv run pytest -q
uv run ruff check .
uv run mypy src
uv build

License

MIT. Copyright (c) 2026 Amaar Chughtai.