Pipeline hazards

A hazard is a situation that stops the next instruction from going on in the next cycle. There are three kinds.

Data hazards

add r1, r2, r3
sub r4, r1, r5     # needs r1, which add has not written yet

add writes r1 in its WB stage, in cycle 5. sub wants to read it in its ID stage, in cycle 3. Without help, sub must stall (wait) for two cycles. (The register file is written in the first half of a cycle and read in the second half, so ID may share a cycle with WB.)

Forwarding (also called bypassing) fixes most of these: the result exists at the end of add's EX stage, so extra wires send it straight to the ALU input for sub's EX, with no stall at all.

Forwarding cannot fix one case: a load followed at once by an instruction that uses the loaded value. The value only arrives at the end of the load's MEM stage, too late for the next EX, so one stall remains: the load-use hazard. Compilers reorder instructions to put something useful in that slot.

Step through the textbook example, then turn forwarding off:

program = [("lw", "r1", ["r2"]), ("sub", "r4", ["r1", "r5"]), ("and", "r6", ["r1", "r7"])]

for forwarding in [False, True]:
    decode, writer, stalls = {}, {}, 0
    for i, (op, dest, srcs) in enumerate(program):
        d = 2 + i + stalls                    # ID cycle if nothing waited
        for r in srcs:
            if r in writer:
                p = writer[r]
                if forwarding:
                    need = decode[p] + (2 if program[p][0] == "lw" else 1)
                else:
                    need = decode[p] + 3          # the producer's WB cycle
                if need > d:
                    stalls += need - d
                    d = need
        decode[i] = d
        writer[dest] = i
    print("forwarding" if forwarding else "no forwarding", ": stalls", stalls, " cycles", decode[len(program) - 1] + 3)

Control hazards

After a branch (beq r1, r2, loop), which instruction comes next? The answer is known only in EX or later, but the pipeline must fetch something now. Options:

• stall until the branch is decided (slow: branches are about 1 in 6 instructions);
• predict and fetch along the predicted path; if wrong, throw those instructions away (flush).

Simple dynamic prediction keeps a 2-bit counter per branch: it changes its prediction only after two wrong guesses in a row, which suits loops well. Modern predictors are right more than 95% of the time.

# A loop branch: taken 4 times, then not taken (the exit), run twice.
outcomes = [1, 1, 1, 1, 0] * 2
counter, right = 3, 0          # 0-1 predict "not taken", 2-3 predict "taken"
for taken in outcomes:
    guess = 1 if counter >= 2 else 0
    right += guess == taken
    counter = min(3, counter + 1) if taken else max(0, counter - 1)
print("correct guesses:", right, "of", len(outcomes))

Structural hazards

Two instructions need the same hardware in the same cycle, for example one memory port for both an instruction fetch and a load. Designs avoid this by duplicating hardware: separate instruction and data caches.

Mark lesson complete