Week 4 AOS: Pipelining

What is the basic idea behind instruction pipelining?

Pipelining divides the instruction cycle into distinct stages. Each stage processes a different instruction simultaneously, like an assembly line. This increases throughput.

What are the five stages of the instruction cycle?

• Instruction Fetch (IF)

• Instruction Decode / Register Fetch (ID/RF)

• Execute / Address Generation (EX/AG)

• Memory Access (MEM)

• Write Back (WB)

What are the characteristics of an ideal pipeline?

• Repetition of identical operations

• Repetition of independent operations

• Uniformly partitionable sub-operations

• Minimal hardware cost increase

• Even latency across stages

How does pipelining affect bandwidth?

Bandwidth ≈ Number of stages / Total latency
Example:

• 1 stage → BW ≈ 1/T

• 2 stages → BW ≈ 2/T

• 3 stages → BW ≈ 3/T

What is the formula for throughput in pipelining with register delay?

• Nonpipelined: BW = 1 / (T + S)

• k-stage pipeline: BW = 1 / (T/k + S)
  Where S = register delay

How does pipelining affect hardware cost?

• Nonpipelined: Cost = G + R

• k-stage pipeline: Cost = G + Rk
  Where G = gate cost, R = register cost

Why is a real instruction pipeline not ideal?

• Instructions differ → not all need same stages

• Stages have different latencies

• Instructions are interdependent → causes stalls

• Clock must control all stages uniformly

What are key issues in pipeline design?

• Balancing work across stages

• Handling stalls

• Managing resource contention

• Resolving instruction dependencies

• Dealing with long-latency operations

What are the two main types of instruction dependences?

• Data dependence

• Control dependence
  Also called hazards.
  Resource contention is a type of resource dependence.

What are the three types of data dependences?

• Flow dependence (RAW) – Read after Write

• Anti dependence (WAR) – Write after Read

• Output dependence (WAW) – Write after Write

Which data dependences cause pipeline stalls?

• Flow dependence (RAW) must always be obeyed

• Anti and output dependences are name-based and arise due to limited registers

What are five ways to handle flow dependences?

• Detect and wait

• Detect and forward/bypass

• Eliminate in software

• Predict and execute speculatively

• Use fine-grained multithreading

What is data forwarding in pipelining?

Also called data bypassing. It forwards the result to the dependent instruction as soon as it’s available, avoiding stalls.

What is stalling and when is it needed?

Stalling delays instruction execution to resolve hazards. Used when forwarding is not possible due to pipeline design or latency.