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?

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.