Pipeline Hazards

A hazard is a situation that prevents the next instruction from executing in its planned cycle. The pipeline must then stall (insert bubbles) or use extra hardware to keep going.

Three kinds of hazards

Data dependences

For instructions I (earlier) and J (later):

WAR and WAW are name dependences: they disappear if the second instruction writes a different register (register renaming).

Stalls and forwarding

In the 5-stage pipeline, a result is written in WB, but the next instruction reads its registers in ID, three stages earlier.

• Without forwarding, a dependent instruction must wait until the producer's WB. If the register file is written in the first half of a cycle and read in the second half, the consumer's ID can share the cycle with the producer's WB. An instruction that uses the result of the one right before it then stalls 2 cycles.
• With forwarding (bypassing), the ALU result is sent straight from the EX/MEM pipeline register to the ALU input of the next instruction: no stall for ALU-to-ALU dependences.
• Load-use hazard: a load's data is only available at the end of MEM, so an instruction that uses it immediately must stall 1 cycle even with forwarding. Compilers try to put an independent instruction after each load to fill that slot.

The simulator below computes when each instruction can execute, for the program

LW   R1, 0(R2)
ADD  R3, R1, R4      ; uses the loaded R1 right away
SUB  R5, R3, R6      ; uses the ADD result
SW   R5, 8(R2)       ; uses the SUB result
ADD  R7, R8, R9      ; independent

def schedule(program, forwarding):
    ex, prev_ex, stalls = [], 2, 0          # the first instruction executes in cycle 3
    for i, (op, dest, sources) in enumerate(program):
        earliest = prev_ex + 1
        need = earliest
        for j in range(i):
            p_op, p_dest, _ = program[j]
            if p_dest and p_dest in sources:            # RAW dependence on instruction j
                if forwarding:
                    need = max(need, ex[j] + (2 if p_op == "LW" else 1))
                else:
                    need = max(need, ex[j] + 3)         # wait for j's write back
        stalls += need - earliest
        ex.append(need)
        prev_ex = need
    return ex[-1] + 2, stalls                           # last instruction: MEM, WB

program = [("LW", "R1", ["R2"]), ("ADD", "R3", ["R1", "R4"]), ("SUB", "R5", ["R3", "R6"]),
           ("SW", None, ["R5", "R2"]), ("ADD", "R7", ["R8", "R9"])]
for fwd in (False, True):
    total, stalls = schedule(program, fwd)
    print(f"forwarding={fwd!s:5}: {total} cycles, {stalls} stall cycles (no hazards: {len(program) + 4})")

forwarding=False: 15 cycles, 6 stall cycles (no hazards: 9)
forwarding=True : 10 cycles, 1 stall cycles (no hazards: 9)

Without forwarding, each of the three back-to-back dependences costs 2 stalls. With forwarding only the load-use pair costs 1.

Control hazards

A branch is resolved late (say in EX), and meanwhile the pipeline has fetched the following instructions. If the branch is taken, those must be flushed: the branch penalty is the number of wasted cycles.

CPI = 1 + (fraction of branches) × (fraction that cause a penalty) × (penalty in cycles)

Example: 20% of instructions are branches with a 3-cycle penalty on every branch: CPI = 1 + 0.2 × 3 = 1.6.

Remedies:

• Resolve branches earlier (compute the target and the condition in ID): penalty 1 cycle.
• Predict not taken: keep fetching sequentially and flush only if the branch is taken.
• Dynamic branch prediction: a branch history table with 1-bit or 2-bit saturating counters, plus a branch target buffer to know the target address at fetch time.
• Delayed branch: the instruction right after the branch (the delay slot) is always executed; the compiler fills it with something useful.

Practice questions