Pipelining and Processor Performance

Introduction

A processor executes a program by repeatedly fetching, decoding, and executing instructions. In a simple single-cycle design, one instruction completes before the next begins. This design is easy to understand but inefficient: different hardware units remain unused during much of each cycle. Instruction pipelining improves hardware utilization by overlapping the processing of several instructions.

Pipelining is comparable to an industrial assembly line. Each instruction passes through a sequence of stages, and different instructions can occupy different stages at the same time. Pipelining normally improves throughput, the number of instructions completed per unit time. It does not necessarily reduce the latency of an individual instruction. In fact, pipeline registers and control mechanisms may slightly increase individual latency.

Modern processors extend basic pipelining with forwarding, branch prediction, multiple-issue execution, register renaming, and out-of-order execution. These techniques improve performance, but they also introduce greater hardware complexity, power consumption, and verification difficulty.

Learning Objectives

After studying this chapter, you should be able to:

1. Explain the operation and performance of an instruction pipeline.
2. Distinguish latency, throughput, clock cycle time, and CPI.
3. Identify structural, data, and control hazards.
4. Explain forwarding, stalling, and pipeline flushing.
5. Describe branch prediction and its performance effects.
6. Explain superscalar and out-of-order execution at a diploma level.
7. Calculate ideal and practical pipeline performance.
8. Apply these concepts when analysing a processor design.

1. The Basic Instruction Pipeline

A common educational pipeline contains five stages:

Pipeline registers separate adjacent stages. For example, an IF/ID register stores the fetched instruction while the next instruction is being fetched. These registers preserve data and control information between clock cycles.

In an ideal five-stage pipeline, the first instruction requires five cycles to complete. Once the pipeline is full, one instruction completes during every cycle. A possible schedule is:

The table illustrates overlap. It does not mean that one instruction is physically divided into five independent instructions. Rather, each instruction advances through hardware stages while other instructions use different stages.

Pipeline clock period

The clock period must be long enough for the slowest stage, plus the delay introduced by pipeline registers and clock skew. A simplified model is:

Here, T_cycle is the clock period, T_IF through T_WB are the combinational delays of the stages, and T_reg is the pipeline-register overhead. All delays are measured in seconds. The formula assumes that stages operate synchronously and that each stage has a single dominant delay.

The clock frequency is:

where f is measured in hertz and T_cycle in seconds.

If one stage is much slower than the others, dividing that stage into smaller stages may increase the clock frequency. However, every additional stage requires another pipeline register and can increase branch penalties, forwarding complexity, power use, and instruction latency.

2. Latency, Throughput, and Speedup

Latency is the time from the start of an instruction until that instruction completes. Throughput is the rate at which completed instructions emerge from the pipeline. These measures must not be confused.

For a pipeline with k stages, clock period T_cycle, and no stalls, the time for n instructions is:

The first instruction occupies k cycles, and each additional instruction requires one further cycle. The formula assumes a full instruction stream, no hazards, no cache misses, and one instruction entering the pipeline per cycle.

For an unpipelined implementation in which each stage takes one clock period, the corresponding time is:

Under these simplified assumptions, speedup is:

As n becomes large, ideal speedup approaches k, but it never exceeds that value in this simple comparison. Real speedup is lower because of pipeline-register overhead, unequal stage delays, hazards, cache misses, interrupts, and instructions that use different resources.

Worked example: ideal performance

A four-stage pipeline has a clock period of 2 ns and executes 100 independent instructions without stalls. The completion time is:

An unpipelined design requiring four stage-times per instruction would take:

Thus:

The speedup is less than the ideal value of four because the pipeline must first fill.

CPI and performance

A useful processor-performance relationship is:

Instruction count is the number of executed instructions, CPI is cycles per instruction, and T_cycle is the clock period. Equivalently, if frequency is used:

The formula assumes that the measured CPI includes all pipeline stalls, cache effects, and other execution delays relevant to the workload.

For a scalar ideal pipeline, CPI approaches 1, not 0, because at most one instruction completes per cycle. A processor may have a CPI below 1 only when it completes multiple instructions per cycle, as in a superscalar processor.

3. Pipeline Hazards

A hazard is a condition that prevents the next instruction from executing in its intended cycle. Hazards are classified as structural, data, or control hazards.

3.1 Structural hazards

A structural hazard occurs when two or more operations require the same hardware resource at the same time. For example, if a processor has one memory used for both instruction fetch and data access, a load instruction in the MEM stage may conflict with another instruction in the IF stage.

Common solutions include:

• providing separate instruction and data caches;
• adding extra functional units;
• duplicating register-file ports;
• scheduling instructions so that requests occur at different times;
• stalling one instruction when duplication is uneconomical.

Resource duplication reduces stalls but increases area, power, and design complexity. A designer therefore balances performance against implementation cost.

3.2 Data hazards

A data hazard occurs when instructions are related through their operands. The most important type in a normally ordered pipeline is a read-after-write (RAW) hazard:

ADD R1, R2, R3       ; R1 ← R2 + R3
SUB R4, R1, R5       ; uses the new value of R1

The SUB instruction needs the result produced by ADD. If SUB reads the register file before ADD writes back, it may receive an old value.

Other dependency names are:

• Write after read (WAR): a later instruction writes a location before an earlier instruction has read it.
• Write after write (WAW): two instructions write the same location in an order that must be preserved.

In a simple in-order pipeline, WAR and WAW hazards generally do not occur because reads and writes happen in a fixed order. They become important in out-of-order or multiple-issue processors.

3.3 Forwarding

Forwarding, also called bypassing, sends a result directly from a later pipeline stage to an earlier stage that needs it. The value need not wait until register write-back.

For example, an ALU result may be forwarded from the EX/MEM pipeline register to the ALU input for the following instruction. Forwarding reduces the number of stalls for ordinary arithmetic dependencies, but it does not eliminate every dependency delay.

A particularly important case is the load-use hazard:

LW  R1, 0(R2)       ; R1 ← memory[R2]
ADD R4, R1, R5      ; immediately uses loaded value

The loaded data may not be available until the end of the MEM stage. The following ADD needs it during its EX stage, so one bubble may be required in a typical five-stage pipeline. Forwarding can then deliver the value after the bubble.

3.4 Stalls and bubbles

A stall prevents an instruction from advancing for one or more cycles. A bubble is an empty pipeline position created by a stall. The control unit may freeze the program counter and an earlier pipeline register while inserting a harmless operation into a later stage.

Stalls preserve correctness but reduce throughput. The performance impact can be represented conceptually as:

For a scalar pipeline, CPI_ideal is approximately 1. The relationship assumes that stall categories are counted without double-counting the same cycle.

3.5 Control hazards

A control hazard arises from a branch or jump because the processor does not immediately know which instruction should be fetched next. Consider:

BEQ R1, R2, TARGET

Until the branch condition and target are resolved, the processor may not know whether the next sequential instruction or TARGET should enter the pipeline.

Solutions include:

• stalling until the branch is resolved;
• resolving branches earlier in the pipeline;
• predicting that the branch is taken or not taken;
• using a branch target buffer;
• fetching along a predicted path and flushing incorrect instructions;
• using compiler scheduling or delayed branching in suitable architectures.

A flush removes incorrectly fetched instructions from the pipeline. These instructions must not change architectural state.

4. Branch Prediction

Branch prediction estimates the outcome and, often, the target address of a conditional branch. Correct prediction allows fetching to continue without a visible interruption. Incorrect prediction causes a misprediction penalty because speculative instructions are discarded.

Static prediction

Static methods use a fixed rule, such as “always not taken” or “backward branches are taken.” The latter often works for loops because a backward branch usually repeats the loop.

Dynamic prediction

Dynamic predictors record recent branch behaviour in hardware. A one-bit predictor changes its prediction after each outcome, but it may mispredict twice for a loop: once when the loop begins or ends and once when it exits. A two-bit saturating counter changes prediction more cautiously. It normally requires two consecutive outcomes favouring the opposite direction before changing a strong prediction.

A branch target buffer (BTB) stores target addresses so that the processor can begin fetching from a predicted target without waiting for address calculation. A return-address stack improves prediction for procedure returns.

A simplified branch penalty model is:

Here, p_b is the fraction of instructions that are branches, p_m is the branch-misprediction rate, and P_m is the penalty in cycles per misprediction. CPI_base excludes these particular penalties. The formula assumes that branch effects are additive and that all mispredictions have the same average penalty.

Worked example: branch penalty

Suppose a processor has a base CPI of 1.1. Branches form 20% of instructions, 8% of branches are mispredicted, and each misprediction costs 5 cycles.

The predictor therefore adds 0.08 cycles per instruction on average. Better prediction or a shorter resolution pipeline can improve performance.

Branch prediction is speculative: predicted instructions may be fetched, decoded, and even executed, but their results must not become permanent until the processor confirms that the prediction was correct.

5. Superscalar Execution

A scalar processor attempts to issue at most one instruction per cycle. A superscalar processor can issue multiple instructions per cycle when sufficient hardware and instruction-level parallelism are available.

A two-issue processor might contain multiple ALUs, load/store units, and register-file ports. Its theoretical maximum is two completed instructions per cycle, but actual performance is limited by dependencies, branches, cache misses, unavailable functional units, and the instruction mix.

The average instructions per cycle (IPC) is related to CPI by:

This reciprocal relationship applies when CPI and IPC describe the same instruction stream and measurement interval. A two-issue processor can have an IPC below two; issue width is a maximum, not a guarantee.

Superscalar designs may be:

• statically scheduled, where the compiler determines much of the issue order; or
• dynamically scheduled, where hardware examines instruction readiness at run time.

A processor also needs mechanisms to prevent multiple instructions from using a resource beyond its capacity. For example, if only one multiplier is available, two multiply instructions cannot both begin in the same cycle unless additional hardware or scheduling support exists.

6. Out-of-Order Execution

In-order execution requires instructions to proceed through major stages in program order. This is simple and predictable, but a stalled instruction can prevent later independent instructions from using available hardware.

Out-of-order execution allows a later independent instruction to execute before an earlier instruction that is waiting for data. The processor still preserves the program’s required architectural behaviour.

A typical out-of-order processor contains the following conceptual structures:

1. Instruction window: holds decoded instructions that are waiting to execute.
2. Reservation stations or issue queues: track operands and functional-unit requirements.
3. Register renaming: maps architectural registers to physical registers, removing false WAR and WAW dependencies.
4. Reorder buffer (ROB): records instructions in program order and supports in-order retirement.
5. Load/store queue: tracks memory operations and checks ordering constraints.

Register renaming

Architectural registers are the names visible in the instruction set. Physical registers are internal storage locations. If two instructions use the same architectural destination but do not have a true data dependency, they can be assigned different physical registers. This removes false name dependencies.

For example:

I₁: ADD R1, R2, R3
I₂: SUB R1, R4, R5

The second instruction does not need the result of the first. Renaming can map the destination of I₁ to P7 and the destination of I₂ to P8, avoiding a WAW conflict.

Speculation and retirement

Out-of-order execution must not allow an incorrect branch path or a faulting instruction to corrupt visible program state. Instructions may execute speculatively, but they normally retire or commit in program order. The reorder buffer ensures that earlier instructions complete their architectural updates before later instructions do so.

If a branch is mispredicted, speculative instructions younger than the branch are removed from the instruction window and reorder buffer. If an exception occurs, the processor can use the precise program-order state maintained by the retirement mechanism.

7. A Unified Performance Analysis

Pipeline performance depends on several interacting factors:

• clock period and maximum stage delay;
• pipeline depth;
• instruction count;
• base CPI or IPC;
• structural conflicts;
• data dependencies and forwarding paths;
• branch frequency and prediction accuracy;
• cache and memory latency;
• issue width and available functional units;
• compiler-generated instruction scheduling.

A practical performance model can be written as:

where IC is instruction count and CPI_stalls includes the average cost of hazards, cache misses, and other stalls. The terms must be measured or estimated for the same workload and must not count the same delay twice.

Worked example: comparing two designs

Design A has a 2 ns clock period and CPI of 1.4. Design B has a 1.4 ns clock period and CPI of 1.9 because its deeper pipeline suffers more branch and data penalties. For 10⁹ instructions:

Design B is faster despite its higher CPI because its clock period is shorter. This example demonstrates why CPI alone is not a sufficient performance measure.

8. Applied Case: Pipeline Selection for an Embedded Network Controller

Background

Consider an illustrative embedded network controller that processes Ethernet frames, checks headers, calculates checksums, and transfers data to memory. The controller must provide predictable response time while operating within a limited power budget.

Problem

A designer is considering a deep, high-frequency pipeline. The design could process more instructions per second, but packet-processing code contains frequent branches, loads, and stores. A branch misprediction or cache miss may therefore cause a significant penalty.

Analysis

The design team measures representative workloads rather than relying on the peak clock frequency. It identifies:

• frequent load-use dependencies in checksum code;
• branches in protocol validation;
• contention between memory access and instruction fetch;
• limited benefit from multiple ALUs because many operations depend on previous results;
• the need for deterministic interrupt response.

Approach and solution

The selected design uses a moderate-depth pipeline, separate instruction and data caches, forwarding paths, a one-cycle load-use stall where necessary, and a small dynamic branch predictor. It uses limited dual issue for independent arithmetic operations but avoids an excessively large out-of-order engine. Critical interrupt paths are given precise state and bounded completion behaviour.

Outcome

Although the selected processor has a lower peak frequency than the deepest alternative, its measured packet throughput is higher for the actual workload. It also consumes less power and provides more predictable timing. The result illustrates that processor performance must be evaluated using realistic instruction streams, not clock frequency alone.

Learning points

1. Workload characteristics determine the value of pipeline depth.
2. A hazard-reduction mechanism is useful only if its cost is justified by the workload.
3. Throughput and response-time requirements may lead to different design choices.
4. Embedded systems must consider power, area, verification, and predictability in addition to speed.

9. Limitations, Design Trade-offs, and Professional Practice

Pipelining does not create computational work capacity without limits. It exposes dependencies and requires additional hardware to manage them. Deeper pipelines can increase frequency but amplify branch penalties. Wider issue can increase peak IPC but requires more instruction bandwidth, register ports, functional units, and scheduling logic.

Out-of-order execution can hide some latency, but it increases energy use and verification effort. Large speculation structures also raise security concerns. Microarchitectural attacks such as timing-based side channels can exploit the fact that speculative execution affects caches or other shared resources, even when incorrect-path instructions do not retire. Mitigations may include speculation barriers, restricted prediction behaviour, cache partitioning, and software or hardware isolation. These controls can reduce performance and must be evaluated carefully.

Good engineering practice includes:

• defining the workload and performance metric before changing the pipeline;
• measuring CPI, IPC, cache misses, branch accuracy, and stall categories;
• checking that benchmark results represent real applications;
• verifying precise exceptions and correct recovery from misprediction;
• considering power, thermal limits, area, cost, and reliability;
• documenting assumptions in performance models;
• avoiding claims based solely on clock frequency or issue width.

Compilers remain important. Instruction scheduling can separate dependent operations, arrange useful work around branches, improve locality, and expose instruction-level parallelism. However, compiler techniques cannot remove true dependencies or guarantee that runtime branch and memory behaviour will match static assumptions.

10. Contemporary Developments

Current processors combine pipelines with multicore execution, vector or SIMD units, hardware multithreading, sophisticated memory hierarchies, and increasingly specialised accelerators. Graphics processors and machine-learning accelerators exploit large amounts of parallelism, but their execution models differ from a conventional scalar pipeline.

Performance analysis increasingly uses hardware performance counters and simulation. Counters can report retired instructions, cycles, cache misses, branch misses, and stalled cycles. Such measurements must be interpreted carefully because counters may be sampled, model-specific, or affected by operating-system activity.

Artificial intelligence workloads have encouraged specialised pipelines for matrix multiplication and tensor operations. These accelerators may sacrifice general-purpose flexibility for high throughput and energy efficiency. The underlying principles remain familiar: divide work into stages, overlap operations, manage dependencies, supply data efficiently, and recover correctly from exceptional conditions.

Chapter Summary

Instruction pipelining overlaps the stages of several instructions to improve throughput. A typical pipeline contains instruction fetch, decode, execute, memory access, and write-back stages. Its clock period is governed by the slowest stage plus pipeline-register overhead. For n instructions in an ideal k-stage pipeline, completion time is (k + n − 1)T_cycle, while real performance is reduced by hazards and other delays.

Latency is the time for one instruction; throughput is the completion rate. Structural hazards result from resource conflicts, data hazards from operand dependencies, and control hazards from branches and jumps. Forwarding reduces many data stalls, while load-use dependencies may still require a bubble. Branch prediction reduces control delays, but mispredictions require flushing speculative work.

Superscalar processors issue multiple instructions per cycle. Out-of-order processors use instruction windows, reservation stations, register renaming, reorder buffers, and in-order retirement to exploit instruction-level parallelism while preserving correct architectural behaviour. Practical processor selection must consider workload, CPI, clock period, cache behaviour, power, cost, security, and predictability rather than relying on one performance number.

Key Terms

Pipeline: Overlapped sequence of instruction-processing stages.

Pipeline stage: A portion of instruction processing completed during one pipeline interval.

Throughput: Number of instructions completed per unit time.

Latency: Time required for one instruction to complete.

CPI: Average number of clock cycles required per instruction.

IPC: Average number of instructions completed per clock cycle.

Pipeline register: Storage separating two pipeline stages.

Hazard: Condition that prevents an instruction from advancing normally.

Structural hazard: Conflict for a hardware resource.

Data hazard: Conflict caused by an instruction dependency.

RAW dependency: Read-after-write true data dependency.

Forwarding: Direct transfer of a result to a consumer without waiting for write-back.

Stall: Temporary prevention of pipeline advancement.

Bubble: Empty pipeline position created by a stall.

Control hazard: Uncertainty about the next instruction caused by control flow.

Branch prediction: Estimation of a branch outcome or target.

Misprediction penalty: Cycles lost when a branch prediction is wrong.

Superscalar processor: Processor capable of issuing multiple instructions per cycle.

Register renaming: Mapping architectural registers to physical registers to remove false dependencies.

Reorder buffer: Structure that supports speculative execution and in-order retirement.

Review Questions

Short Answer Questions

1. What is the main difference between pipeline latency and pipeline throughput?
2. Name the five stages of a common educational instruction pipeline.
3. What is a structural hazard? Give one example.
4. How does forwarding reduce data-hazard stalls?
5. Why does a branch misprediction require a pipeline flush?

Long Answer Questions

1. Explain the operation of a five-stage pipeline and derive the ideal completion-time formula for n instructions.
2. Compare structural, data, and control hazards, including one solution for each.
3. Explain dynamic branch prediction, branch target buffers, and the effect of misprediction penalties on CPI.
4. Describe superscalar execution and discuss why a two-issue processor does not necessarily achieve an IPC of two.
5. Explain how register renaming, an instruction window, and a reorder buffer support out-of-order execution.

Analytical / Application Questions

1. A five-stage pipeline has a 1.5 ns clock period and executes 200 independent instructions. Calculate the ideal completion time and explain why it is not exactly 200 × 1.5 ns.
2. A processor has a base CPI of 1.0. Branches are 15% of instructions, the misprediction rate is 10%, and each misprediction costs 6 cycles. Calculate the branch-related CPI and total CPI under the stated model.
3. An embedded controller can choose a shallow pipeline with a 2.0 ns period and CPI 1.3 or a deep pipeline with a 1.2 ns period and CPI 2.1. For the same instruction count, determine which design has lower CPU time and identify two non-performance factors that should also influence the decision.

Multiple Choice Questions with Answers

Question 1

Which measure describes the number of instructions completed per unit time?

A. Latency

B. Throughput

C. Clock skew

D. Instruction count

Correct Answer: B. Throughput

Question 2

In an ideal five-stage pipeline, how many cycles are required to complete 10 instructions when there are no stalls?

A. 10 cycles

B. 14 cycles

C. 15 cycles

D. 50 cycles

Correct Answer: B. 14 cycles

Question 3

Which hazard occurs when two operations require the same hardware resource at the same time?

A. Structural hazard

B. RAW hazard

C. Control hazard

D. Branch prediction hazard

Correct Answer: A. Structural hazard

Question 4

What is the primary purpose of forwarding?

A. To increase instruction memory capacity

B. To send a result directly to a dependent operation

C. To remove all branch instructions

D. To reduce the number of architectural registers

Correct Answer: B. To send a result directly to a dependent operation

Question 5

Which instruction pair most directly illustrates a load-use hazard?

A. ADD followed by an unrelated SUB

B. LW producing R1 followed immediately by an instruction using R1

C. Two instructions using different constants

D. A branch followed by a program halt

Correct Answer: B. LW producing R1 followed immediately by an instruction using R1

Question 6

What normally happens after a branch prediction is found to be incorrect?

A. The processor permanently disables pipelining

B. Incorrect speculative instructions are flushed

C. All register values are discarded

D. The clock frequency is doubled

Correct Answer: B. Incorrect speculative instructions are flushed

Question 7

A processor that can issue several instructions in one cycle is called:

A. Scalar

B. Superscalar

C. Unclocked

D. Non-pipelined

Correct Answer: B. Superscalar

Question 8

What problem does register renaming primarily reduce?

A. False WAR and WAW dependencies

B. Instruction-cache capacity

C. The need for a clock

D. All RAW dependencies

Correct Answer: A. False WAR and WAW dependencies

Question 9

Why do out-of-order processors usually retire instructions in program order?

A. To preserve correct architectural state and precise exceptions

B. To make branch prediction unnecessary

C. To prevent all cache misses

D. To ensure CPI is always one

Correct Answer: A. To preserve correct architectural state and precise exceptions

Question 10

A processor has a base CPI of 1.0. Branches are 20% of instructions, the misprediction rate is 5%, and the penalty is 4 cycles. What is the estimated CPI?

A. 1.01

B. 1.04

C. 1.20

D. 1.80

Correct Answer: A. 1.01