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 worksILP is the parallelism available within a single thread when instructions do not depend on each other's results. Out-of-order cores rename registers and schedule ready ops across multiple execution units.
cLoading…
The first two adds can execute in parallel; the third waits.
For example, unrolling a loop manually exposes more independent multiplies per iteration, raising IPC until the reorder buffer fills.
For this exercise, you will write microbenchmarks with varying dependency chains and read perf IPC. This task asks you to contrast serial chains against manually unrolled independent bodies on the same CPU.
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.
Show where instruction-level parallelism comes from. Schedule a straight-line block of instructions on a machine with several functional units, using a greedy list scheduler. The result is bounded from below by the critical path, the longest chain of true dependencies, and from above by the number of units. Two code sequences that do the same arithmetic can differ by 4× in cycles purely because one is a single dependency chain and the other isn't.
cLoading…
Register names are r0, r1, … Registers hold values from the start of the block (assume anything read before it is written is already available at cycle 0).
Instructions issue in cycles starting at 1. An instruction may issue in cycle c when:
i with latency L makes its result ready in cycle i + L, so a consumer can issue in cycle i + L or later; andc (+/- and immediate moves use an add unit, * a mul unit).In each cycle, consider the ready instructions in program order and issue as many as the units allow. Ignore write-after-read and write-after-write conflicts: assume perfect register renaming, so only true (read-after-write) dependencies matter.
Per block:
cLoading…
Instructions are named i0, i1, … by program order; cycle lines list the instructions issued that cycle, in program order. The critical path is the longest dependency chain by total latency; break ties by preferring the chain whose last instruction comes first in program order, then the same for earlier positions. Its length is the sum of the latencies along it.
cycles is the last issue cycle plus that instruction's latency, minus 1. IPC = instructions / cycles, to two decimals. ideal 1 unit is the same schedule with one unit of each kind; perfect is the critical-path length (unlimited units). Print a blank line between blocks.
Input:
cLoading…
Output:
cLoading…
Hidden tests cover a mix of adds and multiplies competing for one mul unit, an unrolled loop body (four independent chains) whose IPC is limited only by unit count, immediate moves, and a block where a long-latency multiply feeds a chain of adds.