Pipelining Cross-Concept Problems: CPI, Hazards and Cache Stalls

Build one reliable cycle ledger for a five-stage pipeline, then use it to combine load-use stalls, branch penalties and cache misses without mixing units.

KnowledgeGate Team

Exam prep & CS education

Updated 3 Nov 20265 min read
Pipelining Cross-Concept Problems: CPI, Hazards and Cache Stalls

Combining forwarding, branches and cache misses is a cycle-accounting problem: start with ideal cycles, convert each event into extra cycles, state the overlap assumptions, then calculate CPI and execution time. The workload is 100 dynamic instructions in a five-stage pipeline under one consistent set of timing assumptions. These calculations connect pipeline timing with the wider CS Fundamentals sequence.

Start With the Pipeline Model, Not the Penalty Formula

The machine is a single-issue, in-order, five-stage pipeline: IF, ID, EX, MEM and WB. Every stage takes 2 ns. It has full data forwarding, no structural hazards, a load value available after MEM, and a conditional branch resolved at the end of EX.

Latency and throughput are different. One isolated instruction takes 5 x 2 ns = 10 ns from IF through WB. After the pipeline fills, it can complete one instruction every 2 ns. For N instructions in k stages, ideal cycles are N + k - 1, not N x k. Pipelining Basics in Computer Architecture isolates finite-batch timing and one load-use cycle table. The combined workload here adds branch mispredictions and cache freezes to that base.

Put Every Cross-Concept Fact Into One Cycle Ledger

The cycle ledger is:

total cycles = ideal cycles + data-hazard stalls + control-hazard penalty + memory-stall cycles

This sum is valid because the events do not overlap. If a cache freeze and another stall occupy the same cycles, adding both would double-count time.

Keep three metrics separate:

  • Effective CPI = total cycles / completed instructions.

  • Execution time = total cycles x clock period.

  • Useful throughput = completed instructions / execution time.

A finite run includes the four-cycle fill/drain overhead; a steady-state CPI convention removes that overhead. A miss rate is not a cycle count, so convert it to events first. Convert cycle penalties to time only in the final calculation.

Translate Dependencies and Branches Into Actual Stalls

Consider I1: LW R1, 0(R2), I2: ADD R3, R1, R4, I3: SUB R5, R3, R6, and I4: BEQ R5, R0, L. The immediate I1 -> I2 load-use dependency needs one stall because the load becomes available after MEM. The I2 -> I3 and I3 -> I4 ALU results can be forwarded to the next EX stage, so they need no stalls.

With predict not taken, a taken I4 resolves at the end of EX and squashes the younger instructions in ID and IF, costing two cycles. Charge only mispredictions. Forwarding does not remove this load-use delay, and flushed instructions do not count as completed work.

Five-stage pipeline timing chart for a load-use dependency and branch: I1 reaches WB5, I2 stalls in cycle 4, and I4 is taken at EX7.

Worked Example: Calculate the 100-Instruction Pipeline

The workload has 100 dynamic instructions: 20 loads with 6 immediate dependants, 15 branches with 3 mispredictions, and 2 instruction-cache misses. Each miss freezes the pipeline for 10 cycles. Penalties do not overlap, with no data-cache misses or structural hazards.

Build the ledger one line at a time:

  1. Ideal cycles: 100 + 5 - 1 = 104 cycles.

  2. Load-use stalls: 6 x 1 = 6 cycles.

  3. Branch penalty: 3 x 2 = 6 cycles.

  4. Instruction-cache penalty: 2 x 10 = 20 cycles.

  5. Extra cycles: 6 + 6 + 20 = 32 cycles.

  6. Total cycles: 104 + 32 = 136 cycles.

Effective CPI is 136 / 100 = 1.36. Time is 136 x 2 ns = 272 ns. Throughput is 100 / 272 ns = 0.367647 instructions/ns, approximately 367.65 million instructions/s.

Removing the four-cycle finite-run overhead gives 132 cycles and CPI = 132 / 100 = 1.32. Thus 1.36 and 1.32 use different conventions.

Horizontal cycle ledger for a 100-instruction example: 104 ideal cycles plus 6 load-use stalls, 6 misprediction cycles, and 20 cache-miss cycles total 136 cycles.

Connect Cache Stalls and Speedup Without Mixing Units

The cache term is 2 x 10 = 20 cycles because each miss stops useful progress. Because miss count and penalty are given directly, cache organisation does not enter the ledger. Cache Mapping and Hit Ratio explains how miss behaviour is derived when those inputs are not supplied.

For a fair non-pipelined baseline, five operations take 5 x 2 ns = 10 ns per instruction, so base time is 1,000 ns. The same two cache misses cost 10 x 2 ns = 20 ns each, giving 1,000 + 40 = 1,040 ns. Load-use and branch-flush penalties do not apply without overlapped younger instructions.

Speedup is 1,040 / 272 = 3.8235, approximately 3.82x. Fill, six load-use stalls, six control cycles and cache stalls keep it below the ideal five-stage limit. Speedup must compare the same workload under two complete models.

Traps That Break Otherwise Correct Arithmetic

  • Confusing latency and clock period: the clock is 2 ns, latency is 10 ns, ideal cycles are 104, and ideal time is 104 x 2 ns = 208 ns. Do not multiply by five again.

  • Charging every event: only six of the 20 loads create immediate load-use stalls. Only three of the 15 branches are mispredicted. The two squashed instructions are not completed work.

  • Mixing units: the cache term is 20 cycles, not 20 ns. Convert it only in the final time calculation.

  • Hiding conventions: label whether fill is included and whether penalties overlap. Compare 272 ns with a baseline that includes the same cache-miss cost.

How Exam-Style Questions Combine and Vary the Model

Exam-style variants ask for a timing table, forwarding decisions, bubbles, squashed instructions, cycles, CPI, execution time, a changed parameter, or a pipeline comparison. Each answer follows from the stated machine assumptions and the same cycle ledger.

If branches resolve in ID, each misprediction costs one cycle. The control term becomes 3 x 1 = 3 cycles. Then 104 + 6 + 3 + 20 = 133 cycles, CPI = 1.33, and time is 133 x 2 ns = 266 ns. Load-use and cache terms stay fixed.

Before accepting an answer, ask:

  1. Does the problem include fill and drain?

  2. Which dependencies actually stall with the stated forwarding?

  3. Does the branch penalty apply to every branch or only mispredictions?

  4. Can stall events overlap?

Practise several cross-concept questions, but do not substitute a memorised CPI formula for the ledger.

The Short Version and the Next Step

  1. Write the stage model and clock.

  2. Compute ideal cycles as N + k - 1.

  3. Count each stall or miss event.

  4. Multiply event counts by their penalties.

  5. State overlap and fill conventions.

  6. Calculate CPI and time after the cycle ledger balances.

For this workload, the labelled result is 136 total cycles, CPI 1.36, 272 ns, and about 3.82x speedup against the defined 1,040 ns non-pipelined baseline. For a complete core-CS sequence, continue with ZERO TO HERO. For preparation organised specifically around GATE, use GATE Guidance by Sanchit Sir. Keep the model explicit, balance the ledger, and only then convert cycles into the requested metric.