Pipelined Processor Performance: Stalls and Hazards

Welcome back! In our last lesson, we demystified the control unit, exploring the trade-offs between fast but rigid hardwired designs and flexible but slower microprogrammed ones. We established that for RISC architectures, where speed is paramount, hardwired control is often preferred. Today, we'll explore the single most important technique used by these architectures to achieve high performance: instruction pipelining.

This lesson will shift our focus from executing one instruction at a time to executing multiple instructions in parallel, much like an assembly line. Our goal is to understand how this technique dramatically improves processor throughput. You will learn to calculate the performance improvement, or speedup, offered by a pipelined processor compared to a non-pipelined one. Critically, we will also touch upon why the ideal performance is not always achievable by introducing the concept of pipeline stalls, setting the stage for our next discussion on hazards.

1. The Assembly Line Analogy: From Sequential to Overlapped Execution

Imagine building a car. A non-pipelined approach would be for one mechanic to build an entire car from start to finish: build the chassis, install the engine, add the body, paint it, and install the interior. Only after the first car is completely finished would the mechanic start on the second one. This is inefficient because while the mechanic is painting, the engine-installation tools are idle.

A modern car factory uses an assembly line—a pipeline. The process is broken into stages.

Station 1: Builds the chassis.
Station 2: Installs the engine.
Station 3: Adds the body.
Station 4: Paints the car.
Station 5: Installs the interior.

As soon as the first car's chassis is done and it moves to Station 2, a new chassis can be started at Station 1. All stations are working simultaneously on different cars. While the total time for one car to pass through the entire line doesn't change, the rate at which cars roll off the end of the line (the throughput) is dramatically higher.

Instruction execution can be similarly broken down into stages. In our previous lessons, we saw the classic 5-stage RISC pipeline:

IF (Instruction Fetch)
ID (Instruction Decode & Register Fetch)
EX (Execute / ALU Operation)
MEM (Memory Access)
WB (Write Back)

A non-pipelined processor executes these 5 stages for one instruction before starting the first stage of the next instruction. A pipelined processor overlaps them.

2. Visualizing Pipelining: The Space-Time Diagram

The best way to understand the performance gain is with a space-time diagram. This chart plots pipeline stages against clock cycles. Let's see how this works for executing 8 instructions (I1 to I8) on a 5-stage pipeline.

L-4.3: Pipelining Vs Non-Pipelining | Instruction Execution | Speedup, Efficiency, Utilization | COA

This video from Gate Smashers provides an excellent visual demonstration of non-pipelined vs. pipelined execution using a space-time diagram.

First, watch the brief explanation of the non-pipelined case, which shows that for 8 instructions and 5 stages, it takes 8 * 5 = 40 clock cycles. Then, pay close attention to the construction of the space-time diagram for the pipelined case. Observe how after the first instruction (I1) completes its fetch (IF) in cycle 1, the second instruction (I2) begins its fetch in cycle 2, while I1 moves to the decode (ID) stage. This overlap is the essence of pipelining.

As the video illustrates, in a non-pipelined processor, executing $N$ instructions where each instruction takes $K$ cycles would require $N \times K$ total cycles.

In an ideal pipelined processor with $K$ stages, the situation is much better.

The first instruction takes $K$ clock cycles to complete, as it must pass through all stages.
After the first instruction is complete, a new instruction finishes on every subsequent clock cycle.
This means the remaining $N - 1$ instructions take just $N - 1$ additional cycles.

This leads to the fundamental formula for calculating the number of cycles in an ideal pipeline:

Total Cycles_{pipeline} = K + (N - 1)

Where:

$K$ is the number of pipeline stages.
$N$ is the number of instructions.

3. Calculating Performance Improvement: Speedup

We can now quantify the "performance improvement" mentioned in the learning outcome. This is done by calculating the speedup. Speedup is the ratio of the execution time on the old (non-pipelined) system to the execution time on the new (pipelined) system.

Speedup (S) = \frac{Execution Time _{non-pipeline}}{Execution Time _{pipeline}}

Assuming the clock cycle time ( $T_{cy c l e}$ ) is the same for both, the execution time is the number of cycles multiplied by $T_{cy c l e}$ .

S = \frac{( N \times K ) \times T _{cy c l e}}{( K + N - 1 ) \times T _{cy c l e}} = \frac{N \times K}{K + N - 1}

Theoretical Maximum Speedup:
What happens as we execute a very large number of instructions ( $N \to \infty$ )? The $K - 1$ term in the denominator becomes insignificant compared to $N$ .

N \to \infty lim S = \frac{N \times K}{N} = K

This is a crucial insight: The theoretical maximum speedup of a K-stage pipeline is K. In our 5-stage example, we can never make the program run more than 5 times faster using pipelining alone.

L-4.3: Pipelining Vs Non-Pipelining | Instruction Execution | Speedup, Efficiency, Utilization | COA

Let's see this calculation in action. The same Gate Smashers video explains and applies these formulas.

Watch the segment where the instructor derives the K + N - 1 formula and then uses it to calculate the speedup for the 8-instruction example. With N=8 and K=5, the non-pipelined time is 40 cycles, while the pipelined time is 5 + 8 - 1 = 12 cycles. The speedup is 40 / 12 ≈ 3.33.

4. A GATE-Style Numerical Problem

GATE questions often add a twist. A common one is that introducing pipeline registers adds some overhead, causing the clock cycle time of the pipelined processor to be slightly different from the non-pipelined one.

Let's analyze a problem from GATE 2015.

Problem: A non-pipelined processor has a clock rate of 2.5 GHz and an average CPI (Cycles Per Instruction) of 4. The same processor is upgraded to a 5-stage pipelined processor. Due to internal pipeline delays, the clock rate is reduced to 2 GHz. Assuming there are no stalls, find the speedup.

This problem is solved in the following video. Let's break it down together.

L-4.5: Numerical Question on Pipelining | Previous year GATE Question | COA

This video walks through the solution to the GATE 2015 question. It's a perfect example of applying the concepts of speedup with varying clock rates.

Watch the entire video, paying attention to how the execution time for a single instruction is calculated for each case before computing the final ratio.

Let's re-trace the logic.

Step 1: Calculate Execution Time for the Non-Pipelined Processor.

Clock Rate = 2.5 GHz $⟹$ Clock Time = $\frac{1}{2.5 \times 1 0 ^{9}}$ seconds.
CPI = 4.
Time per instruction (non-pipeline) = $C P I \times Clock Time = 4 \times \frac{1}{2.5 \times 1 0 ^{9}}$ s.

Step 2: Calculate Execution Time for the Pipelined Processor.

Clock Rate = 2 GHz $⟹$ Clock Time = $\frac{1}{2 \times 1 0 ^{9}}$ seconds.
The problem states "assume there are no stalls". For a large number of instructions in an ideal pipeline, the effective CPI approaches 1. This is because one instruction completes every cycle. So, we take CPI = 1.
Time per instruction (pipeline) = $C P I \times Clock Time = 1 \times \frac{1}{2 \times 1 0 ^{9}}$ s.

Step 3: Calculate Speedup.

S = \frac{Time _{non-pipeline}}{Time _{pipeline}} = \frac{4 \times \frac{1}{2.5 \times 1 0 ^{9}}}{1 \times \frac{1}{2 \times 1 0 ^{9}}}

The $1 0^{9}$ terms cancel out.

S = \frac{4/2.5}{1/2} = \frac{4}{2.5} \times 2 = \frac{8}{2.5} = 3.2

So, the speedup is 3.2. This problem shows how to apply the core concepts even when the clock times are not identical.

5. The Impact of Stalls

Our calculations so far have been for an ideal pipeline, where the flow of instructions is perfectly smooth. In reality, the assembly line can jam. What if Station 2 (engine install) needs a specific tool that is also being used by Station 4 (painting)? The entire line before Station 2 would have to wait.

In a processor, such situations are called hazards. A hazard is any condition that prevents the next instruction from executing in its designated clock cycle. To deal with a hazard, the processor must insert a stall, also known as a pipeline bubble. A stall is a delay where no useful work is done in a pipeline stage.

This means our ideal formula is incomplete. The actual number of cycles is:

Total Cycles = (Ideal Cycles) + (Stall Cycles)

Total Cycles = (K + N - 1) + (Number of Stalls)

For example, if our 8-instruction program encountered 4 stall cycles due to various hazards, the total execution time would be $12 + 4 = 16$ cycles. The speedup would then drop from 3.33 to 40 / 16 = 2.5.

The presence of stalls means the effective CPI is no longer 1. If a program of 100 instructions has 20 stall cycles, the total cycles are 120, making the effective CPI = 120/100 = 1.2.

Calculating the performance improvement must account for these stalls. For the GATE exam, a problem might state: "A 5-stage pipeline executes 100 instructions. 20% of instructions cause a 1-cycle stall."

Ideal Cycles = $5 + 100 - 1 = 104$ .
Stall Cycles = $100 instructions \times 20% \times 1 stall/instruction = 20$ .
Total Cycles = $104 + 20 = 124$ .

This is a more realistic performance calculation.

Conclusion

In this lesson, we explored the powerful concept of instruction pipelining, the cornerstone of modern processor performance.

Key Takeaways:

Pipelining works like an assembly line, overlapping the execution of multiple instructions to increase throughput.
The performance of a pipeline is visualized using a space-time diagram.
In an ideal $K$ -stage pipeline executing $N$ instructions, the total clock cycles are $K + N - 1$ .
Speedup measures the performance gain: $S = Time_{non-pipeline} / Time_{pipeline}$ .
The theoretical maximum speedup for a $K$ -stage pipeline is $K$ .
In reality, hazards cause stalls (pipeline bubbles), which increase the total execution time and reduce the actual speedup achieved.

We've now seen that stalls degrade performance. The logical next question is, what causes these stalls and what can we do about them? In our next lesson, we will perform a deep dive into the three main types of pipeline hazards—structural, data, and control—and explore the clever architectural techniques like forwarding and branch prediction that are used to mitigate their impact.