Tomasulo Algorithm Simulator

A cycle-accurate simulator of the Tomasulo out-of-order execution algorithm, written in C++17. It models a superscalar processor with dynamic scheduling, a reorder buffer, a common data bus, and a 2-bit branch predictor — running a subset of RISC-V assembly.

---

Features

• Out-of-order execution via Tomasulo's algorithm with register renaming (RAT)
• Reorder Buffer (ROB) for in-order commit and precise exceptions
• Multiple functional units with configurable latencies and reservation station sizes:
  • Adder (ADD, SUB, ADDI, SLT, SLTI)
  • Multiplier (MUL)
  • Divider (DIV, REM)
  • Logic unit (AND, OR, XOR, ANDI, ORI, XORI)
  • Branch unit (BEQ, BNE, BLT, BLE, J)
  • Load/Store Queue (LW, SW)
• Common Data Bus (CDB) for result broadcasting and operand forwarding
• 2-bit saturating counter branch predictor with per-PC state and misprediction recovery (pipeline flush)
• Memory-mapped data section via .label: declarations in assembly files
• Cycle limit flag for bounded simulation

---

Architecture Overview

Fetch → Decode → [Reservation Stations] → Execute → CDB Broadcast → Commit
                        ↑                                               |
                       RAT ←──────────────────── ROB ─────────────────┘

Component	Description
ARF	32 architectural registers (x0–x31)
RAT	Register Alias Table for renaming to ROB tags
ROB	64-entry circular Reorder Buffer
CDB	Broadcasts results to waiting reservation stations
LSQ	32-entry Load/Store Queue with memory disambiguation
Branch Predictor	Per-PC 2-bit saturating counter; flushes pipeline on mispredict

Default Latencies

Unit	Latency (cycles)	RS Capacity
Logic	1	4
Adder	2	4
Multiplier	4	2
Divider	5	2
Memory	4	32
Branch	2	2

---

Building

Requires g++ with C++17 support.

make compile

To compile with a custom entry file:

make compile FILE=<filename.cpp>

This produces the main binary.

---

Usage

./main <program.s>

To cap execution at N cycles:

./main <program.s> -cycles N

Output

After execution completes, the simulator prints:

• All 32 architectural register values
• Branch predictor accuracy (correct / total)
• Exception information (if applicable)
• Full memory contents

Exceptions

Execution halts and the offending instruction's PC is reported if:

Cause	Instructions
Integer overflow (result doesn't fit in 32 bits)	add, sub, addi, mul
Division by zero	div, rem

On exception the pipeline is flushed and the architectural state reflects all instructions committed before the faulting one.

---

Assembly Format

The simulator accepts a RISC-V-style assembly dialect. Registers are written as x0–x31. Comments begin with #.

Instruction Set

Category	Instructions
Arithmetic (R-type)	add, sub, mul, div, rem, slt
Arithmetic (I-type)	addi, slti
Logic (R-type)	and, or, xor
Logic (I-type)	andi, ori, xori
Memory	lw, sw
Branch	beq, bne, blt, ble, j

Notes

• x0 is always 0 (RISC-V convention); writes to it are ignored.
• sw takes the source register first: sw xSource, offset(xBase) — the opposite of lw.
• Branch offsets and label targets are relative to the instruction's PC (in instruction units, not bytes).

Labels and Data

Code labels can appear inline:

loop:
    addi x1, x1, 1
    blt  x1, x2, loop

Memory data is declared at the top of the file with .label: syntax:

.arr: 10 20 30 40 50

main:
    lw x1, arr(x0)     # loads Memory[arr + 0] into x1

Example Program

# Compute sum of 5 elements
.data: 3 7 2 9 4

    addi x2, x0, 5     # loop counter
    addi x3, x0, 0     # sum accumulator
    addi x4, x0, 0     # index

loop:
    lw   x5, data(x4)  # load data[index]
    add  x3, x3, x5    # sum += data[index]
    addi x4, x4, 1     # index++
    blt  x4, x2, loop  # if index < 5, continue

Run it:

./main example.s

Output:

[+] Execution complete naturally in 31 cycles.

=== ARCHITECTURAL STATE (CYCLE 31) ===
x0:    0 | x1:    0 | x2:    5 | x3:   25 | x4:    5 | x5:    4 | x6:    0 | x7:    0 |
x8:    0 | x9:    0 | x10:   0 | x11:   0 | x12:   0 | x13:   0 | x14:   0 | x15:   0 |
...
Branch Predictor Stats: 4/5 correct.
3 7 2 9 4 0 0 0 ...

x3 = 25 is the sum of {3, 7, 2, 9, 4}. The branch predictor mispredicted once on the final loop iteration (branch not taken), which is expected behaviour for a 2-bit counter seeing a new PC.

---

Configuration

Processor parameters are set in ProcessorConfig (Basics.h) and require recompilation to change. Key fields:

Field	Default	Description
num_regs	32	Number of architectural registers
rob_size	64	Reorder Buffer entries
mem_size	1024	Memory words
add_lat / mul_lat / div_lat / mem_lat / logic_lat	2 / 4 / 5 / 4 / 1	Execution latencies (cycles)
adder_rs_size / mult_rs_size / div_rs_size / br_rs_size / lsq_rs_size / logic_rs_size	4 / 2 / 2 / 2 / 32 / 4	Reservation station sizes per unit

---

Project Structure

File	Responsibility
Basics.h	Core structs: Instruction, ROBEntry, RSEntry, ProcessorConfig, opcode/unit enums
Processor.h / .cpp	Top-level processor: pipeline stages (Fetch, Decode, Execute, Commit), CDB broadcast, flush
LoadProgram.cpp	Assembly parser: tokenization, label resolution, memory section handling
ExecutionUnit.h / .cpp	Functional unit with reservation station, cycle countdown, result capture
LoadStoreQueue.h / .cpp	Memory access unit; handles load forwarding and store ordering against ROB
BranchPredictor.h / .cpp	2-bit saturating counter predictor; updates on commit, triggers flush on mispredict
main.cpp	Entry point: argument parsing, run loop, final state dump
Makefile	Build rules

---

Contributors

• Manya Jain
• Prabuddha Sinha