Implementing A Toy MIPS R10K CPU

Introduction

In the summer of 2025, I implemented a toy CPU simulator using Tomasulo’s algorithm in C++. It was not cycle-accurate and was pretty janky. It did help me understand out-of-order execution, though. What kept bothering me was all the data movement: reservation stations holding operands, waiting for broadcasts, copying values around…

During the Computer Systems course, I learned about the MIPS R10K architecture, and its design made more sense to me. So, for the course’s bonus project, Zhaoyuan Wan and I built a toy R10K-like CPU with Assassyn ↗, the hardware description framework developed by our teacher’s lab. It has a Python frontend and can generate both a simulator and Verilog.

You can find our implementation here ↗. Despite the name, it runs RISC-V instructions. We borrowed the R10K’s approach to out-of-order execution, rather than trying to reproduce the original MIPS chip.

I’ll assume you know the basics of CPU pipelines and Tomasulo’s algorithm. If not, you can read my previous post first. This time, I want to focus on how the pieces fit together when we actually build one.

What Is Different About R10K?

The MIPS R10000 uses explicit register renaming with a Physical Register File (PRF). You can read about the original processor in Kenneth C. Yeager’s paper ↗, but we do not need all of its details to understand the idea.

Recall how a reservation station works in textbook Tomasulo. For each operand, it holds either a value or a tag saying which instruction will produce that value. When the result appears on the common data bus, the station captures it.

In our R10K-like design, an instruction waiting in a queue holds physical register numbers. The values stay in the PRF until an execution unit reads them. If an operand is not ready yet, the instruction waits for that physical register’s ready bit to become set.

So the queues mostly deal with names, while the register file holds the actual data. With 64 physical registers, a name takes only six bits; the value itself takes 32 bits. We still have to move values into and out of execution units, of course. We just do not need a copy of each operand in every waiting queue entry.

There is also an Active List, which plays the ordering role of a reorder buffer. It remembers instructions in program order, even when they execute in a completely different order. This gives us three separate places to look: the PRF for values, the issue queues for work that can run, and the Active List for work that can retire.

Let’s start with the register names, because the rest of the design depends on them.

One Register Name, Several Values

Consider these three instructions:

add x1, x2, x3
add x4, x1, x2
add x1, x6, x3

The second instruction needs the first instruction’s result. The third writes x1 again. If we let the third instruction finish before the second has read its operands, wouldn’t it overwrite the value the second one needs?

It would, if both versions of x1 lived in the same place. Register renaming gives them different places.

Suppose our current mappings include x1 → p5, x2 → p2, x3 → p3, x4 → p4, and x6 → p6. The Free List gives us p40, p41, and p42 for the next three destinations. After renaming, the instructions look like this:

The second instruction remembers p40. Even after the mapping for x1 changes to p42, its input is still p40. We do not look up x1 again when the instruction executes. That would defeat the whole point!

Now the first and third instructions can finish in either order without overwriting each other’s results. The second instruction still has to wait for the first one, because it really does need its value. Renaming removes false dependencies caused by reusing a name; it cannot remove a real data dependency.

At decode, we therefore need to do a few things together:

1. Look up the physical registers for the sources.
2. Allocate a fresh physical register for the destination and save its old mapping.
3. Update the mapping and mark the new register not ready.
4. Put the instruction into the Active List and an execution queue.

The source lookup uses the mapping from before this instruction changes it. Think about addi x1, x1, 1: it must read the old x1 and write a new one.

When Can We Reuse the Old Register?

We only have 64 physical registers, so we cannot keep allocating new ones forever. But when is it safe to give one back?

Look at p40 in the example. We cannot free it when the third instruction is decoded, because the second instruction may still need it. We cannot free it when the third instruction finishes, either: the second instruction might still be waiting.

We free it when the third instruction retires.

Retirement happens in program order. By the time the third instruction retires, the second instruction has already retired, so it has finished using p40. This is why we save the old destination in the Active List: the instruction that replaces a mapping is responsible for freeing the old register when it retires.

In our example, the first instruction eventually frees p5, the second frees p4, and the third frees p40. The final value of x1 remains in p42.

Two Map Tables

There is one more problem. What if the third instruction was on the wrong side of a branch? We have already changed x1 to point to p42, but now we need the earlier value back.

Our Map Table ↗ keeps two sets of mappings:

• The speculative map follows decode. It points to the latest renamed version, whether or not the instruction has finished.
• The committed map follows retirement. It points to the latest version we have accepted as part of the program’s state.

After decoding all three instructions, the speculative map says x1 → p42. If none has retired yet, the committed map still says x1 → p5. When the first instruction retires, the committed map becomes x1 → p40; the speculative map stays at p42.

Notice what retirement does here: it changes a mapping. The result is already in the PRF, so there is no need to copy it into another register file just to make it official.

We will come back to the two maps when we deal with branch recovery.

Putting the Pipeline Together

Our CPU has a frontend that decodes at most one instruction per cycle, 64 physical registers, and three queues with 32 entries each: the Active List, ALU Queue, and Load/Store Queue (LSQ).

The frontend renames instructions in order. In the middle, ready instructions can go ahead of stalled ones. At the other end, retirement puts everything back into program order.

Finding Something to Execute

Each entry in the ALU Queue contains the operation, source and destination tags, and some extra information such as the immediate and PC. The scheduler looks for the oldest entry whose required operands are ready and which has not already been issued.

In simplified form:

valid
and not issued
and (source 1 is unused or ready[source 1])
and (source 2 is unused or ready[source 2])

“Unused” matters. An immediate addition only reads one register. We should not make it wait for a second register just because some bits in the instruction happen to occupy the rs2 field.

Suppose the oldest instruction is waiting for a load, but a younger addition has both operands ready. We can execute the addition now. If another instruction needs its result, that instruction may become ready too, all while the original load is still holding up retirement.

This is where the out-of-order behavior comes from. We keep the program order for bookkeeping, but we do not force every instruction to wait for the one immediately before it.

Our implementation keeps issued instructions in their queues until they retire, with an issued bit to prevent them from running twice. That makes queue management simpler, at the cost of keeping those slots occupied longer.

Although decode admits only one instruction per cycle, the arithmetic and memory paths can work at the same time. The scheduler can dispatch one arithmetic operation and one memory operation in a cycle when both are ready.

Finished Does Not Mean Retired

When an ordinary ALU instruction finishes, it writes the result into its destination physical register, sets that register’s ready bit, and marks its Active List entry complete. A dependent instruction can then use the result without waiting for retirement.

Loads take an extra step. The data SRAM has a cycle of read latency, so a separate writeback module receives the data and completes the load.

Meanwhile, commit only looks at the head of the Active List. If that instruction is not complete, commit waits, even if everything behind it has finished. Once it is ready, commit updates the committed map, returns the old destination to the Free List, and removes the instruction.

Keeping completion and retirement separate is what lets us use speculative results without immediately treating them as permanent program state.

What About Slower Operations?

We also implemented multiplication, division, and remainder from the RISC-V M extension. Multiplication uses radix-4 partial products, a Wallace-tree reduction, and a final addition. Division uses an iterative unit, so it can take much longer than an ordinary addition.

From the rest of the CPU’s point of view, these instructions still have physical source and destination registers and an Active List entry. Their destination just stays not ready for longer.

That is a nice property of this organization. A consumer does not need to know whether its input came from an addition, a load, or a division. It only needs to know which physical register to read and whether the value is ready.

Memory Is Trickier

Register dependencies are visible at decode: we know which registers an instruction reads and writes. Memory dependencies are harder because we might not know the addresses yet.

sw x5, 0(x1)
lw x6, 0(x2)

Are these instructions independent? That depends on the values of x1 and x2. If they contain the same address, the load must see the value written by the store. Letting it run early could give us the old memory value instead.

Our solution is deliberately simple: a load cannot pass an older store in the LSQ. Even if their addresses would turn out to be different, the load waits. Among the loads allowed by this rule, we choose the oldest unissued one whose base register is ready.

This loses some parallelism, but saves us from having to predict memory dependencies or forward values from pending stores. A more ambitious CPU would do both.

Why Stores Wait Until Retirement

A wrong-path arithmetic instruction can write into a physical register without immediately causing trouble. We can discard its mapping later. A wrong-path store is different: if it overwrites memory, how do we get the old value back?

We avoid that problem by executing stores only after they retire.

At retirement, a store leaves the LSQ and enters a one-entry Store Buffer. The scheduler gives this buffer priority over loads, and the LSU performs the write. The buffer bridges the gap between “this store is allowed to happen” and “the memory unit is doing it.”

There is a slightly surprising detail here: we mark stores ready in the Active List as soon as they are decoded. What if their operands are not ready?

Their producers must be older instructions. Since retirement is in order, those producers have to finish and retire before the store reaches the head. By then, the operands are available. We do not need a separate execution step just to tell commit that the store can proceed.

Our memory path is simple enough to drain the Store Buffer promptly. If we added a memory system that could stall for many cycles, we would also need to handle a full buffer and keep its operands alive until the write was accepted.

Accessing Individual Bytes

The data memory is built from four eight-bit SRAM lanes. A word store writes all four lanes, a byte store writes one, and an aligned halfword store writes two. The low address bits tell us which lanes to use.

For loads, writeback combines the lanes, extracts the requested bytes, and sign-extends or zero-extends the result. That gives us byte, halfword, and word accesses without having to read an entire word, modify it, and write it back for every byte store.

This is still a simple SRAM memory model. There are no cache misses or replacement policies, and we do not handle general misaligned accesses across word boundaries.

Recovering from a Wrong Branch Prediction

Suppose we predict a branch as taken and start executing instructions at its target. Some of them may finish before the branch reaches retirement.

Then we discover that the branch was not taken. Oops.

Changing the PC is easy. The harder part is undoing everything we let into the CPU: wrong-path queue entries, newly allocated physical registers, and speculative mappings pointing to the wrong values.

To keep this manageable, our design allows only one outstanding conditional branch. We can decode ordinary instructions beyond it, but if we reach another conditional branch, decode waits until the first one retires. For jal and jalr, we take an even simpler approach and stall fetching until commit redirects it.

The conditional branch executes in the ALU, which records its actual outcome in the Active List. Commit checks that outcome against the prediction when the branch reaches the head.

Why wait so long? Recovering as soon as the branch executes would be faster. But at retirement, we know that every older instruction has already retired. We can throw away everything behind the branch without accidentally losing older work.

What Gets Thrown Away?

On a misprediction, we:

1. Redirect fetch to the correct PC.
2. Clear the Active List, ALU Queue, and LSQ.
3. Copy the committed map back into the speculative map.
4. Recover the physical registers allocated after the branch.
5. Reset readiness tracking and stop issuing new speculative work during the flush.

The third step is why we kept a committed map. In the diagram, the wrong-path instruction wrote p42, but the earlier value in p40 is still there. Restoring x1 → p40 makes us use the right value again. We do not need to copy register data back and forth.

For the Free List, we save its allocation head when the branch is decoded. Recovery moves that head back, reclaiming the registers handed out along the wrong path. We keep the registers returned by older instructions that retired in the meantime; those returns were valid.

Resetting the ready bits is safe for the restored committed mappings because their producers have already finished. A register allocated again for a new instruction will be marked not ready at decode.

One thing we keep is the committed Store Buffer. Its store has already retired, so it belongs to the part of the program that really happened. A branch flush must not erase it.

We also have to stop work already inside execution units. Clearing a queue does not magically stop a divider that started several cycles ago. The multiply/divide path receives the flush signal too. Otherwise, a late result could arrive after we have reused its register or Active List slot for a different instruction.

This is also why allowing several outstanding branches would take more work. We would need to know which instructions and allocations belong to which branch, and recover only the part after the branch that was mispredicted.

A Few Things About Assassyn

Although the source looks like Python, we are describing hardware. The bit widths, storage, and timing between modules are part of the design. A Python loop can construct a row of multiplexers; it does not necessarily mean the CPU will run a loop at execution time.

One useful example is the Map Table. We have 32 mappings, each six bits wide. On recovery, we want to restore all of them together. Writing 32 separate array entries at once would require expressing all those writes, so we pack the mappings into one 192-bit register:

storage_dtype = Bits(32 * 6)
spec_table = RegArray(storage_dtype, 1, initializer=[0])
commit_table = RegArray(storage_dtype, 1, initializer=[0])

A normal rename replaces one six-bit field. A flush selects the entire committed table as the next speculative table. There is still selection logic behind this, but the state update becomes much easier to express.

The readiness table uses the same trick: one 64-bit register, with a bit for each physical register. Decode clears a bit, execution sets it, and flush resets the whole set.

Another place to be careful is stalling. If decode cannot accept an instruction, it must not allocate a physical register anyway, or update the map without inserting the corresponding queue entry. These actions have to happen together. In Assassyn, that means paying attention to wait_until and the conditions attached to downstream enables, not just the arithmetic inside a module.

The ALU gets most of the attention in a CPU diagram, but a lot of the work is in making these little state changes agree with each other.

How Does It Perform?

We test the individual structures, then run assembly programs and check their final x10 value against the expected result. We also have tests that run the generated Verilog through Verilator. Checking the return value is a useful start; comparing the full retirement trace with a reference interpreter would catch more subtle mistakes.

Here are a few results from our benchmark report ↗:

IPC is the number of instructions retired per cycle:

These numbers cover the whole program run, so short tests pay a lot for filling the pipeline and reaching termination. Four instructions taking 14 cycles looks quite different from a longer program that keeps the CPU busy.

You might wonder why we bother with out-of-order execution if IPC is still below one. Our frontend decodes at most one instruction per cycle, and commit retires at most one. One is the ceiling for sustained IPC in this design. Out-of-order execution helps us get closer to it by doing useful work during cycles that would otherwise be spent waiting.

We also gave up performance in several places to keep the implementation small. Loads wait behind stores, branch recovery waits for retirement, and a second conditional branch can stall decode. Any of these can leave the backend without enough useful work. Finding out how much each one costs would be an interesting follow-up experiment.

What Next?

The change I would most like to try is earlier branch recovery. Waiting until retirement makes the bookkeeping easy, but it also means wasting more time on the wrong path. Recovering at execution would force us to preserve older unfinished instructions and undo only the younger ones.

Memory scheduling is another obvious place to improve. Once a store’s address is known, a load to a different address should not have to wait for it. A load to the same address could potentially get its value directly from the store. Both would make the LSQ considerably more interesting.

A wider frontend is tempting too, but it brings its own problems. Two instructions decoded together might depend on each other, so their renaming has to account for updates within the same group. We would also need more allocation and register-file ports. Simply changing “one” to “two” would not get us very far.

For now, the part I find most satisfying is how register renaming and retirement fit together. An instruction can finish early, and other instructions can already use its result, while we still have a way to abandon it if the branch prediction was wrong. The old value has been sitting in another physical register all along. We just have to know when it is finally safe to let it go.