CS274: Computer Architecture - Pipelining: Data and Control Hazards

Activity Goals

The goals of this activity are:
  1. To identify the three types of pipeline hazards
  2. To identify and mitigate the hazards present in the MIPS pipelined architecture

Supplemental Reading

Feel free to visit these resources for supplemental background reading material.

The Activity

Directions

Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity, and compare with your group to prepare for our whole-class discussion. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

Model 1: Pipeline Hazards

Structural Hazards: not enough hardware to execute each pipeline stage independently
Control Hazards: Need to execute an instruction to determine the location or control of the next instruction
Data Hazards: An instruction needs to read data being calculated by a prior instruction

Questions

  1. Where, if anywhere, do each of these hazards exist in the MIPS architecture?
  2. What are some strategies to mitigate each of these hazards?

Model 2: Control Hazards

Timeline diagram showing a stall while the branch instruction is resolved in order to determine the next instruction to execute.
Predicting branch not taken, and then bubbling the isntruction before it finishes upon determining that the branch should be taken.

Questions

  1. Notice that if a branch occurs, we must stall one cycle until the ALU stage so that we can compare the registers and determine if a branch should be taken or not. Here, the branch is taken. If the branch was not taken, what could we have done during that stalled time instead?
  2. How might we cancel an instruction already in progress? Do we have time to do this before it writes to any registers or memory? If so, how many cycles do we have, and is this enough time to resolve a branch?
  3. Is it better to predict that a branch is taken or not taken, and why?
  4. Could the compiler help to avoid these stalls by changing the order of execution? What do you think a "branch delay slot" is?

Model 3: Data Hazards

Timeline showing a two cycle data hazard on writeback.
Forwarding the register value prior to writeback for use in subsequent instructions without a stall.

Questions

  1. Notice the and and or instructions will receive stale data because the register writeback from the prior instruction hasn't completed by the time they decode. At what point is this data actually available, and how might it be used to override the register decode values?
  2. What would happen if two consecutive instructions write to the same register, and the next instruction reads that register? Which pipeline stage forward should take priority and why?
  3. Will this work for a load instruction? Why or why not? Hint - when is that value available, and from what stage can it be forwarded?
  4. Modify our strategy to allow forwards from load instructions using a stall cycle.

Model 4: Forwarding Detection

Forwarding Detection
Forwarding Control
Pipelined Datapath and Control with Forwarding

Questions

  1. Why is the else if critical here to ensure that an EX/MEM forwarding hazard doesn't also exist when checking for a MEM/WB forwarding hazard?

Model 5: Hazard Detection for Load (Control Hazard) and Branch (Data Hazard) Stalls

Example load hazard requiring a stall followed by a forward from the writeback stage
Pipelined Datapath and Control with Hazard Detection

Questions

  1. How does this unit work in tandem with the forwarding unit for load data hazards?
  2. How does this approach ensure we do not skip the currently executing instruction (but instead re-issue it with a no-op feeding into the execute stage)?

Model 6: MIPS Pipeline Performance

25% load instructions, 10% of which result in hazards
50% R-type instructions, 20% of which require forwarding
25% branch instructions, 50% of which are taken

Questions

  1. How many penalty cycles result from stalling the pipeline, on average, per instruction?

Model 7: Key Formulas and Concepts Recap

A one-page summary of pipeline hazards and their fixes.

The three hazard types and their mitigations:

Hazard Cause Micro-example Mitigations
Structural Two instructions need the same hardware in the same cycle One memory for both fetch and data access Duplicate hardware (separate instruction and data memories)
Data An instruction reads a register a prior in-flight instruction hasn't written yet add $s0, ... immediately followed by and $t0, $s0, ... Forwarding from EX/MEM or MEM/WB; a one-cycle stall for load-use
Control The next PC isn't known until a branch resolves beq resolved in EX while two younger instructions are already fetched Predict not taken and squash on a taken branch; early branch resolution; branch delay slot

Key rules and formulas:

Rule / Formula Micro-example
Forward from EX/MEM when EX/MEM.RegWrite = 1, EX/MEM.rd = ID/EX.rs (or rt), and EX/MEM.rd ≠ 0; otherwise check MEM/WB the same way. EX/MEM (the newer value) wins ties. Back-to-back add $s0,... then sub ..., $s0, ...: ForwardA = 10
Load-use rule: a value loaded by lw is not available until after MEM, so a dependent instruction in the very next slot always costs one stall cycle (then forward). lw $t0, 0($s1) then add $t2, $t0, $t3: 1 bubble
Stall detection: stall if ID/EX.MemRead = 1 and ID/EX.rt matches IF/ID.rs or IF/ID.rt (zero the ID/EX control bits, freeze PC and IF/ID). The lw/add pair above trips this test in the add's decode cycle
Average stall cycles per instruction = sum of (frequency × hazard rate × penalty). 25% loads × 10% hazards × 1 cycle = 0.025 cycles/instruction from loads
Real CPI = 1 + average stall cycles per instruction. 1 + 0.025 (loads) + 0.25 × 50% × penalty (branches) + ...
Forwarding fixes most data hazards with zero cost; stalls and squashes are the fallback when the value literally does not exist yet. R-type-to-R-type dependences never stall with forwarding

A load-use stall, pictured:

cycle:              1    2    3    4    5    6    7
lw  $t0, 0($s1)     IF   ID   EX   MEM  WB
add $t2, $t0, $t3        IF   ID   **   EX   MEM  WB
                                   stall, then forward MEM/WB -> EX

Glossary:

Term One-line definition
Forwarding (bypassing) Routing a result from a pipeline register straight to the ALU input, skipping the register file.
Stall Holding an instruction in place for a cycle by freezing the PC and IF/ID and inserting a bubble.
Bubble (no-op) A pipeline slot whose control signals are all zeroed so it changes no state.
Squash (flush) Canceling already-fetched instructions after a taken branch, before they write anything.
Load-use hazard A data hazard where the very next instruction needs a value still being loaded from memory.
Branch prediction Guessing a branch's outcome (e.g. "not taken") so fetching can continue; wrong guesses are squashed.
Branch delay slot An instruction slot after a branch that executes regardless; the compiler tries to fill it with useful work.
Hazard detection unit Logic in ID that spots load-use hazards and triggers the stall.
Forwarding unit Logic in EX that compares register numbers across pipeline registers and steers the ALU input muxes.

Submission

I encourage you to submit your answers to the questions (and ask your own questions!) using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section. You can find the link to the class notebook on the syllabus.