Level 63: Five Instructions in Flight

The task

Goal: build a linear 13-instruction program (lui/addi/ori/xor/and/sw/lw), run it, and predict which instruction will be in the EX stage on cycle 8. The level-61 Race Track showed where an instruction sits on the current cycle; now you read the whole trace at once. The waterfall diagram — cycles horizontally, stages vertically: each instruction draws a diagonal of five cells, from IF to WB. The first four cycles fill the pipe: fewer than five instructions in flight. Then the stream: five instructions fly at once — figure out which instruction (by fetch order) occupies a given stage at a given cycle. After the last instruction — four drain cycles.

The level-61 Race Track showed where the instructions are on the current cycle. Now you read the whole trace at once — on the waterfall diagram: cycles run horizontally, the IF/ID/EX/MEM/WB stages vertically, and each instruction draws a diagonal of five cells, from fetch to write-back.

No schematic to build — this is a programming level. The tasks:

Build a linear 13-instruction program: base lui x5, 0x1, data addi x6, x0, 7 and addi x7, x0, 20, constant ori x8, x0, 0x7F0, store sw x6, 0(x5), read-back lw x12, 0(x5), logic xor x9, x6, x7, and x10, x6, x8, add x11, x9, x7, then more memory and arithmetic: sw x8, 4(x5), add x13, x12, x11, sw x13, 8(x5), add x14, x10, x12.
Predict the instruction number in a stage. The first "Check" asks: which instruction (by fetch order) sits in the EX stage on cycle 8? Count it yourself: instruction No. n is fetched on cycle n and reaches EX on cycle n+2.
Run it and switch the view. The platform has a Lanes/Waterfall switch; the waterfall opens by default. Press "Step" and watch the diagonal of instructions grow one cycle per step. Click a cell for the instruction card.
Explain the phases. 13 instructions — yet 17 cycles: cycles 1–4 are fill (fewer than five instructions in flight), cycles 5–13 are the steady stream (five instructions fly at once), cycles 14–17 are drain.

Solution for self-checking

Write the program yourself first. The solution below is a checkpoint.

What you should get: the 13-instruction program takes 17 cycles (13 retirements + 4 fill); the prediction agrees: instruction No. 6 (lw x12) is in the EX stage on cycle 8; the trace phases: fill 1–4, stream 5–13, drain 14–17.

Step 1 — the golden program.

lui  x5, 0x1        # 0:  base 0x1000
addi x6, x0, 7      # 4
addi x7, x0, 20     # 8
ori  x8, x0, 0x7F0  # 12
sw   x6, 0(x5)      # 16: DMEM[0x1000] = 7
lw   x12, 0(x5)     # 20
xor  x9, x6, x7     # 24: 19
and  x10, x6, x8    # 28: 0
add  x11, x9, x7    # 32: 39
sw   x8, 4(x5)      # 36: DMEM[0x1004] = 0x7F0
add  x13, x12, x11  # 40: 46
sw   x13, 8(x5)     # 44: DMEM[0x1008] = 46
add  x14, x10, x12  # 48: 7
.end                # 52: halt

Step 2 — checkpoint numbers. Run: 13 instructions = 13 retires, 17 cycles (13 + 4 fill), halt at PC = 52. Final registers: x5 = 0x1000, x6 = 7, x7 = 20, x8 = 0x7F0, x9 = 19, x10 = 0, x11 = 39, x12 = 7, x13 = 46, x14 = 7; memory: 0x1000 = 7, 0x1004 = 0x7F0, 0x1008 = 46. No bubbles: lw x12 sits five instructions before the first use of x12 — no load-use occurs.

Step 3 — the prediction. EX on cycle 8 — instruction No. 6 (lw x12): No. 6 is fetched on cycle 6, cycle 7 — ID, cycle 8 — EX, cycle 9 — MEM (the word read), cycle 10 — WB.

Step 4 — reading the waterfall. Diagonal No. 1 runs from the cell (cycle 1, IF) to (cycle 5, WB) and leaves the pipe; the parallel diagonals No. 2–5 follow it one cycle apart. The fill is the staircase of the first four cycles, the drain is its mirror image at the end.

Check yourself

How do you find the instruction in a given stage at a given cycle on the waterfall?

It is a countdown: instruction No. n is fetched on cycle n and reaches EX on cycle n + 2, MEM on n + 3. So EX on cycle 8 holds No. 6, and MEM on the same cycle holds No. 5.