Pipelining is one of the most important techniques used to improve instruction throughput in a processor. Instead of completing one instruction completely before starting another, a pipelined processor divides instruction execution into stages and allows different instructions to occupy different stages at the same time.
The basic idea is similar to an assembly line. In a manufacturing line, one product may be assembled while another is being painted and a third is being inspected. The same principle can be applied inside a processor: one instruction can be fetched while another is decoded and another is being executed.
Pipelining does not normally reduce the amount of work required by an individual instruction. Its main purpose is to increase the number of instructions that can be completed over a period of time by keeping different processor stages active simultaneously.
In this chapter, we will understand the working of instruction pipelines, pipeline stages, throughput, speedup, pipeline hazards, stalls, forwarding, and branch prediction.
Pipelining is a processor design technique in which instruction execution is divided into multiple stages. Each stage performs a particular part of the instruction-processing operation, and pipeline registers are used to hold intermediate information between stages.
Once the pipeline is filled, several instructions can be in progress simultaneously. Each instruction is at a different stage, but all stages are working during the same clock cycle.
Consider four stages: F = Fetch D = Decode E = Execute W = Write Back Without pipelining: Instruction 1 → F → D → E → W Instruction 2 → F → D → E → W Instruction 3 → F → D → E → W Only one instruction is processed at a time. With pipelining: Cycle 1: I1-F Cycle 2: I1-D | I2-F Cycle 3: I1-E | I2-D | I3-F Cycle 4: I1-W | I2-E | I3-D | I4-F Cycle 5: I2-W | I3-E | I4-D | I5-F
The important point is that the instructions overlap. The processor is not executing all parts of one instruction simultaneously; instead, different stages are working on different instructions during the same clock cycle.
A processor contains different functional units that perform different parts of instruction processing. In a non-pipelined design, much of this hardware may remain unused while another part of the processor is working.
For example, while an instruction is being decoded, the execution hardware may not be doing useful work for another instruction. Pipelining reduces this idle time by allowing the stages to work on different instructions concurrently.
Therefore, the primary objective of pipelining is to increase instruction throughput.
Pipelining should not be confused with simply increasing the speed of a processor. A pipeline improves the number of instructions completed per unit time by overlapping their execution.
A simple instructional pipeline can be divided into several stages. The exact stages vary between processor architectures, but a commonly used model contains the following five stages.
| Stage | Name | Function |
|---|---|---|
| 1 | IF - Instruction Fetch | The processor fetches the instruction from memory. |
| 2 | ID - Instruction Decode | The instruction is decoded and required registers or control information are identified. |
| 3 | EX - Execute | The required arithmetic, logical, comparison, or address calculation operation is performed. |
| 4 | MEM - Memory Access | Memory is accessed when the instruction requires a load or store operation. |
| 5 | WB - Write Back | The result is written into the destination register. |
These stages are a simplified educational model. Real processors may use more stages and may divide individual operations into several smaller pipeline stages.
Suppose a processor has five pipeline stages and each stage requires one clock cycle. Consider four independent instructions.
Cycle
Instruction 1 2 3 4 5 6 7 8
I1 IF ID EX MEM WB
I2 IF ID EX MEM WB
I3 IF ID EX MEM WB
I4 IF ID EX MEM WB
The first instruction requires five cycles to pass through all stages. However, after the pipeline becomes full, an instruction can potentially complete on every subsequent clock cycle.
This is the main performance advantage of pipelining: higher throughput rather than simply shorter execution time for one instruction.
Throughput refers to the number of instructions completed during a given period of time. A well-balanced pipeline can complete approximately one instruction per clock cycle after the initial pipeline filling period.
For a pipeline containing k stages and a sequence of n instructions, the ideal execution time can be represented as:
Ideal pipelined cycles = k + n - 1
For example, if a processor has five stages and must execute ten independent instructions:
k = 5
n = 10
Execution time = k + n - 1
= 5 + 10 - 1
= 14 clock cycles
Without pipelining, assuming every instruction requires five cycles:
Non-pipelined time = n × k
= 10 × 5
= 50 clock cycles
This demonstrates the theoretical benefit of overlapping instruction execution.
Speedup compares the execution time of a non-pipelined processor with the execution time of a pipelined processor for the same workload.
Speedup = Non-pipelined execution time -------------------------------- Pipelined execution time
For the previous example:
Non-pipelined time = 50 cycles
Pipelined time = 14 cycles
Speedup = 50 / 14
≈ 3.57
The ideal speedup approaches the number of pipeline stages as the number of instructions becomes very large. However, practical speedup is normally lower because of hazards, pipeline stalls, unequal stage delays, branch instructions, and other processor overheads.
A pipeline works most efficiently when instructions can move from one stage to another without interference. Unfortunately, instructions often interact with each other or compete for processor resources. These situations can prevent the pipeline from progressing normally.
Such situations are called pipeline hazards.
The three major types are:
A structural hazard occurs when two pipeline stages require the same hardware resource at the same time, but the processor does not have enough copies of that resource to serve both operations simultaneously.
Suppose a processor has a single memory unit. Instruction 1 requires a memory access. At the same time, another instruction needs the memory unit to fetch its next instruction. Both operations cannot use the resource simultaneously. One instruction must wait.
This waiting period creates a pipeline stall.
A common architectural solution is to provide separate resources or additional hardware so that competing operations can occur simultaneously. For example, separating instruction and data memory can reduce certain memory-access conflicts.
A data hazard occurs when the execution of one instruction depends on data produced or modified by another instruction that has not yet completed the required operation.
Instruction 1: ADD R1, R2, R3 Instruction 2: SUB R4, R1, R5
Instruction 2 requires the new value of R1 produced by Instruction 1. Because the instructions overlap inside the pipeline, Instruction 2 may reach its execution stage before Instruction 1 has written the result into R1.
If the processor simply reads the old value, the second instruction could calculate an incorrect result.
One important technique for reducing data hazards is forwarding, also called bypassing. Instead of waiting for a result to travel through the normal write-back path, the processor can forward an available result directly from one pipeline stage to another stage that needs it.
Instruction 1 calculates result
↓
Forwarding
↓
Instruction 2 uses result
Forwarding can eliminate many data-related stalls, although some dependencies still require the pipeline to wait.
Data hazards can be further classified according to the relationship between instructions.
| Type | Meaning |
|---|---|
| RAW | Read After Write - an instruction reads a value that a previous instruction must write. |
| WAR | Write After Read - a later write could interfere with an earlier read. |
| WAW | Write After Write - two instructions write to the same destination and their write order matters. |
In a simple in-order pipeline, RAW dependencies are the most commonly encountered data hazards. More advanced processors can encounter or manage WAR and WAW dependencies through techniques such as out-of-order execution and register renaming.
A control hazard occurs when the processor cannot immediately determine which instruction should be fetched next. Branch and jump instructions are the primary source of this problem.
Instruction 1: Compare two values Instruction 2: Branch if the values are equal Instruction 3: Next sequential instruction
While the branch condition is being evaluated, the processor may not yet know whether Instruction 3 is actually the correct next instruction.
If the branch is taken, instructions that were fetched from the wrong path may have to be removed from the pipeline. This process is commonly called a pipeline flush.
Modern processors often use branch prediction to reduce the performance cost of control hazards. The processor predicts the likely direction or target of a branch and continues fetching instructions based on that prediction.
If the prediction is correct, useful work continues without a large interruption. If the prediction is wrong, the incorrectly fetched instructions are discarded and execution continues from the correct branch target.
A pipeline stall occurs when an instruction cannot safely move to the next stage and one or more pipeline stages must temporarily wait.
A stall introduces one or more empty clock-cycle slots into the normal pipeline flow. These empty slots are sometimes called bubbles.
Cycle: 1 2 3 4 5 6 Instruction 1 IF ID EX MEM WB Instruction 2 IF ID STALL EX MEM ... The stall delays the progress of Instruction 2.
Frequent stalls reduce the actual performance benefit obtained from pipelining.
A pipeline flush occurs when instructions already present in the pipeline are no longer valid and must be removed.
This commonly happens after an incorrect branch prediction. The processor discards instructions belonging to the wrong execution path and begins fetching instructions from the correct address.
A flush can therefore introduce several lost clock cycles, depending on the processor's pipeline depth and the point at which the branch decision becomes known.
| Hazard | Main Cause | Typical Handling |
|---|---|---|
| Structural | Insufficient hardware resources | Additional or separate resources, scheduling, or stalls |
| Data | Dependency between instructions | Forwarding, scheduling, or stalls |
| Control | Uncertainty caused by branches or jumps | Branch prediction, delayed execution, or pipeline flush when necessary |
| Feature | Non-Pipelined Execution | Pipelined Execution |
|---|---|---|
| Instruction overlap | No significant overlap | Multiple instructions overlap |
| Hardware utilization | Lower | Higher |
| Instruction throughput | Lower | Higher |
| Design complexity | Generally simpler | More complex |
| Hazard handling | Less relevant | Essential |
| Performance | Lower for long instruction streams | Higher when the pipeline remains well utilized |
| Term | Meaning |
|---|---|
| Pipeline Stage | A specific step through which an instruction passes during execution. |
| Throughput | The number of instructions completed per unit of time. |
| Latency | The time required for one instruction to travel through the pipeline. |
| Pipeline Hazard | A condition that prevents normal pipeline execution. |
| Stall | A temporary delay inserted into the pipeline. |
| Bubble | An empty pipeline slot created because of a stall or other delay. |
| Forwarding | Directly passing an available result to a dependent instruction. |
| Pipeline Flush | Removing invalid instructions from the pipeline. |
| Branch Prediction | Predicting the likely outcome of a branch to keep the pipeline moving. |
Pipelining divides instruction processing into stages and allows different instructions to occupy those stages simultaneously. This overlapping increases instruction throughput and makes better use of processor hardware.
A simple pipeline may contain stages such as instruction fetch, instruction decode, execute, memory access, and write back. Once the pipeline is filled, an ideal processor can complete approximately one instruction per clock cycle, although the exact behavior depends on the processor architecture and workload.
The major challenge is that instructions are not always independent. Structural hazards occur when hardware resources conflict, data hazards occur when instructions depend on one another, and control hazards occur when branches make the next instruction uncertain. Techniques such as additional hardware resources, forwarding, scheduling, branch prediction, stalls, and pipeline flushing are used to manage these problems.
Understanding pipelining is essential for studying modern processor performance because it connects instruction execution with concepts such as throughput, latency, hazards, branch prediction, and parallel execution.