Pipelining and Processor Execution

Introduction

Processor performance depends not only on clock frequency but also on how effectively hardware overlaps, predicts, schedules, and completes instructions. Pipelining is the central technique used to exploit instruction-level parallelism (ILP). It divides instruction execution into stages separated by registers so that different instructions can occupy different stages simultaneously. Although a pipeline does not normally reduce the work required by one instruction, it increases throughput—the number of completed instructions per unit time.

Modern processors extend the basic pipeline with multiple functional units, out-of-order execution, register renaming, speculation, branch prediction, and precise exception mechanisms. These features improve average performance but also introduce hazards, complex control logic, energy costs, and verification challenges. This chapter develops the analytical foundations of pipelining and connects them with contemporary superscalar processor execution.

Learning Objectives

After studying this chapter, the reader should be able to:

1. Explain the structure and performance goals of an instruction pipeline.
2. Calculate latency, throughput, speedup, and pipeline efficiency.
3. Identify structural, data, and control hazards.
4. Compare stalling, forwarding, scheduling, speculation, and renaming techniques.
5. Explain superscalar, out-of-order, speculative, and simultaneous multithreaded execution.
6. Analyze branch penalties, cache effects, and pipeline depth trade-offs.
7. Evaluate a processor pipeline for performance, power, correctness, and security.

1. Instruction Execution as a Sequence of Stages

A conventional RISC instruction can be described using five logical stages:

These stages are conceptual. Real processors may divide them into many finer stages. A floating-point multiplication, cache miss, or vector operation may use a different pipeline from an integer instruction.

In a non-pipelined processor, one instruction completes all stages before the next begins. In a pipelined processor, stage registers hold intermediate results while other instructions use the preceding stages. The clock period must be long enough for the slowest stage plus register overhead:

Here, T_i is the combinational delay of stage i, k is the number of stages, and T_reg is the delay associated with a pipeline register, including clock-to-output and setup effects. The inequality assumes a single synchronous clock and ignores skew or margin terms; practical designs include timing margins.

The latency of an individual instruction in a k-stage pipeline is approximately:

Latency is the time from entering the first stage to leaving the final stage. Once the pipeline is full, ideal completion throughput is one instruction per clock for a single-issue pipeline:

2. Ideal Pipeline Performance

For n independent instructions and k stages, assuming equal stage delays, no hazards, no interrupts, and one instruction entering per cycle, completion requires:

The corresponding non-pipelined schedule requires approximately nk stage-times. If the clock period is the same stage time, ideal speedup is:

As n becomes large, speedup approaches k, but it never exceeds k in this simple single-issue model. This result assumes that pipeline registers do not add delay and that all stages have equal duration. Real speedup is lower because of imbalance, hazards, cache misses, branch recovery, and pipeline-fill and drain effects.

Worked Example 1: Ideal Speedup

A four-stage pipeline executes 20 independent instructions. Each stage takes 2 ns, and register overhead is ignored. The pipelined completion time is:

C_pipe = (4 + 20 − 1) × 2 = 46 ns

The non-pipelined time is:

C_nonpipe = 20 × 4 × 2 = 160 ns

Thus:

S = 160/46 ≈ 3.48

The result is below the maximum theoretical speedup of four because the pipeline requires filling and draining.

3. Pipeline Design and Stage Balancing

A pipeline is effective only when its stages are balanced. If one stage takes substantially longer than the others, every stage must use a clock period determined by that slow stage. Suppose the stage delays are 180 ps, 220 ps, 150 ps, and 260 ps, and register overhead is 20 ps. Then:

T_clk = 260 + 20 = 280 ps

Dividing the 810 ps of logic into four stages does not produce a 202.5 ps clock because the maximum stage delay, rather than the average, determines the clock period.

Pipeline partitioning involves trade-offs:

• More stages can increase clock frequency.
• More pipeline registers increase area, power, and clock distribution load.
• Deeper pipelines increase branch-misprediction and exception-recovery penalties.
• Very short stages make register overhead proportionally more significant.
• Unequal stage delays reduce potential throughput.

A useful idealized performance model includes stalls. If CPI_ideal is the ideal cycles per instruction and s_i is the average stall contribution of event i, then:

For a single-issue pipeline, CPI_ideal = 1. For a superscalar processor with maximum issue width W, the ideal CPI may approach 1/W under a suitable instruction mix, although dependencies and limited parallelism usually make the actual value larger.

4. Pipeline Hazards

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

4.1 Structural Hazards

A structural hazard occurs when two operations require the same hardware resource simultaneously. For example, if a processor has one memory port, an instruction fetch and a data load may conflict in the same cycle. Solutions include duplicating resources, using separate instruction and data caches, scheduling operations, or stalling.

Resource duplication improves performance but increases area and power. A designer must consider the expected frequency of conflicts rather than assuming that every resource should be replicated.

4.2 Data Hazards

Data hazards arise from dependencies between instructions. The principal dependency types are:

• RAW (read after write): a true dependence. A consumer needs a value produced by an earlier instruction.
• WAR (write after read): an anti-dependence. A later write must not occur before an earlier read.
• WAW (write after write): an output dependence. Writes must preserve program order when they target the same architectural destination.

In a simple in-order pipeline, RAW hazards are the dominant issue. Consider:

ADD   R1, R2, R3
SUB   R4, R1, R5

The SUB instruction needs the result produced by ADD. If the register file is read before ADD writes back, SUB must wait unless the result can be forwarded directly from a later pipeline stage.

#### Forwarding

Forwarding, or bypassing, sends a computed value from an execution or memory pipeline register to a dependent functional-unit input without waiting for architectural write-back. It reduces the number of stalls for ALU-to-ALU dependencies. It does not eliminate every stall: a load-use dependence may still require a delay if the loaded value becomes available only after the memory stage.

#### Stalling

A hazard-detection unit can insert a bubble—a cycle in which no useful instruction advances through a selected stage. Stalling preserves correctness but reduces throughput. A bubble is not an instruction; it is empty pipeline capacity.

#### Register Renaming

Register renaming maps architectural registers to a larger set of physical registers. It removes false WAR and WAW dependencies and allows independent instructions to execute concurrently. True RAW dependencies remain because the consumer genuinely requires the producer’s value.

4.3 Control Hazards

A control hazard occurs when the next program counter is uncertain, usually because of a conditional branch or indirect jump. The processor may:

1. stall until the branch direction and target are known;
2. predict the direction and target;
3. fetch along a predicted path and later squash incorrect instructions.

If the branch prediction accuracy is p, the misprediction rate is 1 − p, and the recovery penalty is B cycles, the average branch penalty contribution is:

where f_b is the fraction of instructions that are conditional branches. The formula assumes a fixed penalty and independent average behavior; real penalties can vary with branch type, target availability, and pipeline state.

Worked Example 2: Branch Prediction

Suppose 18% of instructions are conditional branches, prediction accuracy is 92%, and each misprediction costs 10 cycles. The branch contribution is:

0.18 × (1 − 0.92) × 10 = 0.144 cycles per instruction.

If the ideal CPI is 1 and all other stalls contribute 0.25 cycles per instruction, then:

CPI = 1 + 0.144 + 0.25 = 1.394

At a 3 GHz clock, the instruction throughput of a single-issue processor is approximately:

3×10⁹/1.394 ≈ 2.15×10⁹ instructions per second.

5. Static and Dynamic Scheduling

Static scheduling places responsibility for hazard avoidance primarily on the compiler. The compiler may reorder independent instructions, insert NOPs, or select instructions that hide functional-unit latency. Static scheduling is inexpensive in hardware but depends on accurate knowledge of the target processor and runtime behavior.

Dynamic scheduling allows hardware to detect readiness and select instructions during execution. Tomasulo-style organization uses reservation stations, tags, result forwarding, and register renaming. Instructions wait near functional units until operands and resources are available. Dynamic scheduling can exploit runtime information such as cache-hit status, but it requires wakeup, selection, and dependence-tracking logic.

A modern out-of-order processor typically separates:

• dispatch: decode instructions and allocate entries;
• issue: select ready instructions for execution;
• execute: operate on operands;
• complete or write back: make results available;
• retire or commit: update architectural state in program order.

Retirement in order enables precise exceptions: if an instruction faults, all earlier instructions appear complete and all later instructions appear not yet executed, even though internal execution may have occurred out of order.

6. Superscalar and Speculative Execution

A superscalar processor can issue multiple instructions per cycle. If its issue width is W, the ideal upper bound is W instructions per cycle, but the actual rate depends on available ILP, dependency chains, functional-unit capacity, cache behavior, branch prediction, and instruction-window size.

A useful performance expression is:

For a superscalar processor, CPI may be less than one when measured per instruction, while IPC (instructions per cycle) may exceed one:

This reciprocal relationship assumes the same instruction-count and cycle-count definitions.

Speculative execution executes instructions before their control-flow or data dependence is certain. Incorrect-path instructions are prevented from changing committed architectural state. A reorder buffer commonly tracks speculative instructions and commits them in program order.

Speculation improves performance when predictions are accurate. It also increases energy consumption because incorrect-path instructions consume fetch, decode, scheduling, and execution resources. Furthermore, microarchitectural state such as caches and predictors may reveal information even when speculative results are discarded. This observation underlies transient-execution vulnerabilities such as Spectre-class attacks. Secure design therefore requires speculation barriers, partitioning, bounds-checking strategies, and careful software-hardware contracts where appropriate.

7. Exceptions, Interrupts, and Precise State

An exception is an internally detected event such as an arithmetic fault, page fault, or illegal instruction. An interrupt is an externally signaled event. In an out-of-order machine, several younger instructions may have completed internally when an older instruction raises an exception. The reorder buffer delays architectural commitment so that the processor can discard younger work and present a precise state.

Precise state is essential for operating-system recovery, debugging, virtualization, and reliable application behavior. It is not free: reorder buffers, checkpointing, recovery paths, and retirement logic consume storage and energy. Some specialized accelerators use weaker completion models when precise architectural exceptions are unnecessary, but such designs require explicit software and system-level contracts.

8. Memory Dependence and Cache Interaction

Memory operations create dependencies that are harder to analyze than register operations because addresses may be unknown until execution. A load must not incorrectly bypass an older store to the same address. Store buffers, load queues, memory-dependence predictors, and disambiguation logic support speculative memory execution.

A cache miss can stall an instruction for far longer than an ALU operation. Out-of-order execution may hide part of this latency by executing independent instructions, but the benefit is limited by the instruction window and by dependencies on the missing value. Memory-level parallelism (MLP) is the ability to sustain multiple outstanding cache misses or memory requests.

Average memory access time can be expressed for a two-level hierarchy as:

Here, T_L1 and T_L2 are lookup times, m_L1 and m_L2 are local miss rates at L1 and L2, and T_mem is main-memory access time. The expression assumes serial lookup and a two-level hierarchy. Alternative nonblocking or parallel-access organizations require different models.

Pipeline performance is therefore a system property: a fast execution core can be limited by instruction-cache misses, data dependencies, translation misses, coherence traffic, or memory bandwidth.

9. Branch Prediction and Recovery

Branch predictors may be static or dynamic. Static policies use rules such as “backward branches are taken.” Dynamic predictors use execution history. A one-bit predictor records the most recent outcome; a two-bit saturating counter changes prediction only after repeated evidence, reducing disruption from isolated anomalies.

More advanced predictors combine local history, global history, target caches, and indirect-branch prediction. The branch target buffer (BTB) predicts the target address, while a return-address stack predicts procedure returns. Prediction quality must be evaluated jointly: a correct direction with an unavailable target may still delay fetch.

On a misprediction, the processor identifies the recovery point, invalidates younger speculative instructions, restores relevant rename state, and redirects fetch. Deeper pipelines and wider machines generally make this recovery more expensive because more wrong-path work may be in flight.

10. Illustrative Case: Improving a Server-Class Pipeline

Background

Consider an illustrative eight-core server processor whose workload consists of database queries, compression, and transaction processing. Its front end is frequently limited by indirect branches and instruction-cache misses. The baseline core is four-wide, out of order, and operates at 3.2 GHz.

Problem

Performance measurements show an average CPI of 1.8. Profiling attributes 0.35 CPI to branch mispredictions, 0.25 to data-cache stalls, and 0.20 to instruction-delivery limitations. The remaining 0.00? The baseline ideal contribution is 1.00, so the measured total is accounted for as 1.00 + 0.35 + 0.25 + 0.20 = 1.80.

Analysis and Approach

The design team evaluates three interventions:

1. enlarge and improve the BTB and indirect-branch predictor;
2. increase instruction-cache capacity and improve fetch bandwidth;
3. add more execution units.

Adding execution units is rejected as the first intervention because execution capacity is not the dominant measured limitation. Suppose prediction improvements reduce branch stalls by 30%, and instruction delivery improvements reduce its stall component by 25%. The new estimated CPI is:

CPI_new = 1 + (0.35×0.70) + 0.25 + (0.20×0.75) = 1.695

The relative performance improvement, assuming the same clock frequency, is:

Improvement = 1.80/1.695 − 1 ≈ 6.2%

Outcome

The analysis demonstrates why bottleneck measurement should precede hardware expansion. The improvements may also increase predictor and cache power. A final decision should therefore include energy per instruction, silicon area, verification complexity, and workload variability—not merely average CPI.

Learning Points

• CPI components should be measured rather than guessed.
• Improving a non-bottleneck resource may produce little benefit.
• Pipeline changes must be evaluated with frequency, power, area, and correctness together.
• Average results can conceal serious regressions for particular applications.

11. Contemporary Developments and Research Issues

Current processor research explores several directions:

• heterogeneous cores that match work to performance or energy requirements;
• wide out-of-order windows and improved dataflow scheduling;
• chiplet-based designs with specialized accelerators;
• vector and matrix pipelines for machine learning and scientific computing;
• near-memory and processing-in-memory approaches to reduce data movement;
• security-aware speculation and microarchitectural isolation;
• compiler–hardware co-design for domain-specific workloads;
• adaptive voltage, frequency, and pipeline control.

Artificial intelligence is relevant both as a workload and as a design aid. Matrix engines require deep pipelines and high data reuse, while machine-learning models can assist branch, cache, or prefetch prediction. Such techniques must be evaluated against interpretability, training overhead, distribution shift, verification, and security requirements. A predictor that performs well on benchmarks may fail on unseen workloads.

12. Best Practices for Pipeline Analysis

A rigorous analysis should:

1. Define the instruction-count, cycle-count, and clock-frequency conventions.
2. Separate latency from throughput.
3. State whether CPI includes cache, branch, synchronization, and operating-system effects.
4. Identify the workload and its phase behavior.
5. Measure stall sources with hardware counters or validated simulation.
6. Check pipeline balance and register overhead.
7. Evaluate average and tail performance.
8. Include energy, thermal, area, and verification costs.
9. Treat speculative state as a security concern.
10. Validate conclusions across representative applications rather than one benchmark.

Challenges and Limitations

Pipelining does not create unlimited parallelism. Long dependence chains, unpredictable branches, serializing instructions, synchronization, and memory latency constrain performance. Deeper pipelines may improve frequency but amplify control penalties. Wider issue increases the complexity of dependence checking and instruction selection, often with diminishing returns. Out-of-order execution can hide latency but requires substantial energy and may expose microarchitectural information. Finally, simple CPI equations are useful for first-order reasoning but cannot replace cycle-accurate simulation or measurement when interactions among caches, predictors, coherence, and operating-system behavior are significant.

Chapter Summary

Pipelining divides instruction execution into sequential stages so that multiple instructions overlap. The clock period is determined by the slowest stage plus pipeline-register overhead, while ideal throughput approaches one instruction per cycle for a single-issue pipeline. Ideal speedup is limited by pipeline fill and drain, stage imbalance, and real-world stalls.

Structural hazards arise from resource conflicts; data hazards arise from dependencies; and control hazards arise from uncertain control flow. Forwarding, stalling, scheduling, register renaming, branch prediction, and speculation address these hazards in different ways. Superscalar and out-of-order processors exploit instruction-level parallelism, while in-order retirement preserves precise exceptions.

Memory hierarchy behavior, branch recovery, instruction-window capacity, energy, and security all influence practical performance. Effective pipeline design therefore requires measurement-based bottleneck analysis and balanced consideration of speed, power, area, correctness, and information security.

Key Terms

Pipelining: Overlapping execution of multiple instructions across sequential hardware stages.

Pipeline stage: A portion of instruction processing completed in one clock interval.

Throughput: Number of completed instructions or operations per unit time.

Latency: Time required for one operation to traverse the pipeline.

Pipeline register: Storage separating adjacent combinational stages.

Structural hazard: Conflict for a hardware resource.

Data hazard: Dependence-related conflict between instructions.

RAW dependence: A true read-after-write dependence.

WAR dependence: An anti-dependence caused by write-after-read ordering.

WAW dependence: An output dependence caused by write-after-write ordering.

Forwarding: Direct transfer of a result to a dependent operation.

Bubble: An empty pipeline slot introduced to handle a hazard.

Control hazard: Uncertainty about the next instruction address.

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

Out-of-order execution: Execution in an order different from program order when dependencies permit.

Register renaming: Mapping architectural registers to physical registers.

Speculative execution: Execution based on predicted control or data conditions.

Reorder buffer: Structure supporting out-of-order completion and in-order retirement.

IPC: Instructions completed per cycle.

AMAT: Average memory access time for a specified cache hierarchy.

Review Questions

Short Answer Questions

1. What is the difference between pipeline latency and throughput?
2. Why does the slowest pipeline stage determine the clock period?
3. Distinguish RAW, WAR, and WAW dependencies.
4. What function does a reorder buffer perform?
5. Why can forwarding fail to eliminate a load-use stall?

Long Answer Questions

1. Explain structural, data, and control hazards and discuss hardware techniques for handling each.
2. Derive the ideal completion time and speedup of a k-stage pipeline executing n instructions.
3. Explain how Tomasulo-style scheduling and register renaming support out-of-order execution.
4. Discuss branch prediction, speculative execution, and precise recovery in a modern processor.
5. Analyze the effects of deeper pipelines and wider issue on performance, power, and security.

Analytical / Application Questions

1. A six-stage pipeline executes 30 independent instructions with a 500 ps clock. Calculate the ideal completion time and compare it with a non-pipelined design whose instruction time is six clock periods.
2. A workload has a branch frequency of 15%, prediction accuracy of 95%, and a 12-cycle misprediction penalty. Calculate the branch contribution to CPI and explain two ways to reduce it.
3. A processor has CPI components of 1.00 base, 0.30 branch stalls, 0.20 cache stalls, and 0.10 structural stalls. A redesign halves branch stalls but increases clock period by 8%. Determine whether execution time improves, assuming instruction count is unchanged, and state the assumptions needed.

Multiple Choice Questions with Answers

Question 1

Which quantity primarily determines the clock period of a basic synchronous pipeline?

A. The average instruction count

B. The slowest stage delay plus register overhead

C. The branch prediction accuracy

D. The number of architectural registers

Correct Answer: B. The slowest stage delay plus register overhead

Question 2

For a single-issue pipeline executing n instructions in k stages under ideal conditions, the number of cycles is:

A. n/k

B. nk

C. k + n − 1

D. k − n + 1

Correct Answer: C. k + n − 1

Question 3

Which hazard represents a true data dependence?

A. RAW

B. WAR

C. WAW

D. Structural

Correct Answer: A. RAW

Question 4

What is the principal purpose of forwarding?

A. To increase memory capacity

B. To send a computed result directly to a dependent operation

C. To eliminate all branch mispredictions

D. To commit instructions out of order

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

Question 5

If branch frequency is 0.20, prediction accuracy is 90%, and misprediction penalty is 5 cycles, what is the branch CPI contribution?

A. 0.01

B. 0.05

C. 0.10

D. 1.00

Correct Answer: C. 0.10

Question 6

Which technique removes false WAR and WAW dependencies?

A. Pipeline stalling

B. Register renaming

C. Branch delay insertion

D. Instruction-cache indexing

Correct Answer: B. Register renaming

Question 7

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

A. To reduce register-file size

B. To preserve precise architectural state

C. To prevent all cache misses

D. To guarantee one instruction per cycle

Correct Answer: B. To preserve precise architectural state

Question 8

If a processor completes 2 instructions per cycle on average, its CPI is:

A. 0.5

B. 1

C. 2

D. 4

Correct Answer: A. 0.5

Question 9

Which event is a structural hazard?

A. A consumer needs an unavailable producer result

B. Two instructions require the same single memory port simultaneously

C. A branch target is mispredicted

D. A register is renamed

Correct Answer: B. Two instructions require the same single memory port simultaneously

Question 10

In the two-level AMAT expression, a local L1 miss rate is multiplied by which additional cost?

A. Only the L1 hit time

B. The L2 access time plus the conditional main-memory cost

C. The instruction count

D. The pipeline depth only

Correct Answer: B. The L2 access time plus the conditional main-memory cost