Count the pipeline stalls – Architecture Practice

Count the stall cycles and total cycles of a program on the classic 5-stage pipeline (IF, ID, EX, MEM, WB), with these rules:

The first instruction is in ID in cycle 2. Each instruction is in ID at least one cycle after the one before it.
An instruction reads its source registers in ID. Without forwarding, it may only be in ID in or after the WB cycle of the latest earlier instruction that writes that register: ID(p) + 3.
With forwarding, it must wait only for a load: in ID no earlier than ID(p) + 2 if p is a load, ID(p) + 1 otherwise.
The program takes as many cycles as the last instruction's WB: its ID + 3. Stalls are the extra cycles over 5 + n − 1.

Instructions: add, sub, and, or rd, rs, rt; addi rd, rs, number; lw rd, number(rs) (a load; writes rd); sw rt, number(rs) (reads rt and rs, writes nothing); nop.

Input

A line forwarding yes or forwarding no, a line with n (1 ≤ n ≤ 50), then n instructions.

Output

Two lines: cycles X and stalls Y.

Examples

Example 1 · Input

forwarding yes
4
lw r1, 0(r2)
sub r4, r1, r5
and r6, r1, r7
or r8, r1, r9

Expected output

cycles 9
stalls 1

Example 2 · Input

forwarding no
4
lw r1, 0(r2)
sub r4, r1, r5
and r6, r1, r7
or r8, r1, r9

Expected output

cycles 10
stalls 2

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Keep, for each instruction, the cycle of its ID stage; the first is in ID in cycle 2, and each next one at least one cycle after the one before.

Hint 2

For each source register written by an earlier instruction p: without forwarding, ID must be at least ID(p) + 3; with forwarding, ID(p) + 2 if p is a load, else ID(p) + 1.

Hint 3

Stalls = the total of the delays; cycles = ID of the last instruction + 3.

Solution

Show one correct solution (try it yourself first)

import re

forwarding = input().split()[1] == "yes"
n = int(input())
decode, writer, loads = [], {}, set()
for i in range(n):
    line = input().strip().lower()
    regs = re.findall(r"r\d+", line)
    op = line.split()[0]
    if op == "nop":
        dest, srcs = None, []
    elif op == "sw":
        dest, srcs = None, regs
    else:
        dest, srcs = regs[0], regs[1:]
    d = 2 if i == 0 else decode[-1] + 1
    for r in srcs:
        if r in writer:
            p = writer[r]
            need = decode[p] + 3 if not forwarding else decode[p] + (2 if p in loads else 1)
            d = max(d, need)
    decode.append(d)
    if op == "lw":
        loads.add(i)
    if dest:
        writer[dest] = i
cycles = decode[-1] + 3
print("cycles", cycles)
print("stalls", cycles - (5 + n - 1))

Lesson: Pipeline hazards →