Midterm 2 Review: Datapath & Pipelining | CSCI 343

Datapaths and Multiplexers

Note

The full datapath (as shown in Patterson & Hennessy Figure 4.24) will be provided on the exam.

Figure 4.24

• Be ready to draw individual datapaths for specific instructions with labeled bit widths, path annotations, and target address calculations. Include only relevant parts, no unnecessary control lines.
• Be ready to explain/reason through the the different stages of an individual datapath.
• For each mux: know which instructions use it, what the inputs/outputs are, what the control signal is, its bit width, and the meaning of each setting
• Be able to trace what control signals are active for a given instruction as it moves through the datapath
• Understand the implementation of the read and write ports of the register file.

Multiplexers

1. Register Destination (RegDst)
2. Memory to Register (MemtoReg)
3. Jump/Branch Control
4. ALU Source (ALUSrc)
5. PC Source Multiplexers (e.g., for branch/jump)

For each mux, be able to draw a diagram showing all labeled inputs, the labeled output, and the control line with its setting. Only one mux (in the branch datapath) connects to the zero-check signal.

Control Signals and Target Address Calculation

• Know how PC + 4, branch target address, and jump address are computed, and what control lines (branch, jump, zero-check) are involved
• Know what values feed into the PC via muxes depending on the instruction
• Know the order of sign-extend vs. shift-left-2 in target address computation
• Be able to trace the computation of the address stored in the PC register and the address of the next instruction to be executed

Pipelining

• Know what each stage does and which hardware component it uses:
  1. Instruction Fetch (IF)
  2. Instruction Decode/Register Fetch (ID)
  3. Execution (EX)
  4. Memory Access (MEM)
  5. Write Back (WB)
• Know how each instruction type (load, store, R-type, branch) behaves across all five stages — lw is the only instruction active in all five
• Understand why MIPS is well-suited for pipelining
• Draw a pipeline execution chart for a sequence of instructions; cycle duration is determined by the longest stage

Single-Cycle vs. Pipelined Execution Time

• In single-cycle design, all instructions take one cycle and the clock cycle length must accommodate the slowest instruction
• Calculate total execution time by summing component durations (for the critical-path instruction), then multiplying by instruction count
• Be able to compare total execution time between single-cycle and pipelined architectures and explain the speedup

Pipeline Registers

• Registers between pipeline stages are needed to pass data and control signals forward
• These are what make data forwarding possible and prevent instructions in different stages from interfering with each other
• Example: a load result must be passed from MEM to WB via a pipeline register

Pipeline Hazards and Solutions

Data Hazards

• Occur when an instruction depends on the result of a previous one that hasn’t completed yet

• Read-after-write (RAW) is the most common type

• Example: sub needs $s1 before it is updated by the load:

  load $s1, 24($s0)
  sub $t0, $s1, $s2

• Solutions:

  • Stalling with bubbles — introduce NOPs to delay the dependent instruction; implemented by the Hazard Detection Unit
  • Forwarding — uses pipeline registers to forward data to where it’s needed; works when the result is available at EX stage and needed at the ALU input
  • Note: forwarding does not always work — load followed by a dependent instruction (load-use hazard) requires a stall even when forwarding is available

Control Hazards

• Caused by branches and jumps — uncertainty in the next PC value leads to stalls
• MIPS uses Delayed Branch: always execute the next sequential instruction after a branch; may execute incorrect instructions if the branch is taken, requiring a pipeline flush
• Identify the type of hazard between any two instructions, explain why it occurs, and give concrete examples of each type along with a fix

Hazard Units

• Forwarding Unit — complex and costly; implements data forwarding to minimize stalls
• Hazard Detection Unit — detects RAW hazards and inserts bubbles as needed

Compiler Optimization

• Compilers may reorder instructions to reduce hazards
• You are not expected to reorder instructions yourself, but you should be able to identify dependencies between instructions and explain why reordering could reduce hazards