Loading page…
Master the fundamental concepts of pipelining & out-of-order execution through this focused micro-challenge.
You have read the whole brief, and the concepts above stay free on every task. Writing and running the code needs a plan.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksOut-of-order CPUs execute speculatively but retire instructions in original program order through a Reorder Buffer (ROB). Each entry tracks destination, value readiness, and exception state. Only when an instruction is oldest and complete does it commit to architectural state.
cLoading…
For example, if a divide-by-zero occurs in the ROB but younger ops already executed, the fault fires only when the divide reaches the ROB head.
For this exercise, you will simulate a small ROB that buffers out-of-order completion and commits in order. This task asks you to model flush on branch mispredict before studying Tomasulo's algorithm.
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.
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.
Simulate a reorder buffer (ROB), the structure that lets a CPU execute instructions out of order while still finishing them in order. Instructions are dispatched in program order into ROB entries, execute as soon as their operands are ready, write their results back, and are retired in order from the head of the buffer. In-order retirement is what makes precise exceptions possible: everything before the faulting instruction has committed, and nothing after it has.
cLoading…
Latencies: +/- 1 cycle, * 3, load 4 (or 10 if the address is a multiple of 64: a cache miss), fault 1. A load reads simulated memory whose contents are ADDR / 4.
W instructions from the head of the ROB, but only while the head is complete. A retiring fault raises an exception: flush every remaining entry and stop.W instructions in program order into free ROB entries.Registers start at 0. The ROB is a circular buffer; an instruction can be dispatched only when an entry is free.
One line per cycle, listing the events in the order above:
cLoading…
Omit any empty stage, but always end with rob USED/SIZE (occupancy after the cycle). If nothing at all happened, print cycle N: idle | rob U/SIZE. Retire shows the register result, or iK(fault) for the faulting instruction. Stop when the ROB is empty and everything is dispatched, on an exception, or after 200 cycles. Then:
cLoading…
plus exception at iK on the line before, when one was raised.
Input:
cLoading…
Output:
cLoading…
Hidden tests cover a ROB too small for the program (dispatch stalls), a cache-missing load that delays retirement of everything behind it, an exception that flushes completed instructions behind it, and a width of 1.