6. Pipelining and Instruction-Level Parallelism

Introduction and Context

A processor improves performance in two fundamentally different ways: it can execute an individual instruction faster, or it can increase the number of instructions completed per unit of time. Pipelining primarily addresses the second objective. It divides instruction processing into stages so that several instructions can be in progress simultaneously. Instruction-level parallelism (ILP) extends this idea by exploiting independent operations within a sequential instruction stream.

The central difficulty is that instructions are not entirely independent. They may compete for hardware resources, depend on one another’s results, or alter the flow of control through branches. Consequently, high-performance processor design is not simply a matter of adding pipeline stages or functional units. It requires mechanisms for detecting hazards, preserving program correctness, predicting control flow, and recovering from incorrect speculative decisions.

This chapter develops the principles behind scalar pipelines, forwarding, hazard handling, branch prediction, superscalar execution, register renaming, out-of-order execution, and precise exceptions. These mechanisms form the foundation of modern CPU microarchitecture.

Learning Objectives

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

• explain the structure and performance of an instruction pipeline;
• distinguish structural, data, and control hazards;
• calculate pipeline timing, latency, throughput, and speedup;
• design and evaluate forwarding and stalling mechanisms;
• explain branch prediction and speculative execution;
• describe superscalar issue, register renaming, and out-of-order execution;
• explain how reorder buffers support in-order commitment and precise exceptions;
• assess performance trade-offs, implementation risks, and current design trends.

From Sequential Execution to Overlapped Execution

A conventional instruction passes through several activities: instruction fetch, decoding and register reading, execution, memory access, and writing the result. In a non-pipelined processor, one instruction may complete all activities before the next begins. If the five activities require equal time, the completion interval is approximately the sum of their delays.

A pipeline places registers between stages. After an instruction advances from one stage to the next, the hardware stage it leaves can begin processing another instruction. A typical five-stage RISC pipeline is:

1. IF (Instruction Fetch): obtain the instruction and update or predict the program counter.

2. ID (Instruction Decode): interpret the opcode and read source registers.

3. EX (Execute): perform an arithmetic operation, calculate an address, or evaluate a branch condition.

4. MEM (Memory Access): read or write data memory when required.

5. WB (Write Back): write a result into the register file.

Pipelining does not normally reduce the latency of one instruction. Instead, it increases throughput. If there are \(k\) balanced stages and \(n\) instructions, the ideal completion time is approximately \((k+n-1)T\), where \(T\) is the pipeline clock period. The ideal speedup approaches \(k\) only for a long instruction stream and only when hazards, unequal stage delays, and pipeline-register overhead are negligible.

The clock period must accommodate the slowest stage as well as the delay of pipeline registers. Adding stages can raise the clock frequency by reducing logic per stage, but it also increases branch penalties, register overhead, forwarding complexity, and the cost of pipeline disruption. Thus, deeper pipelines are not automatically superior.

Hazards: Where Overlap Meets Dependence

A hazard is a condition that prevents the next instruction from executing in its intended pipeline cycle. Three broad classes are important.

Structural hazards

A structural hazard occurs when two operations require the same hardware resource simultaneously. For example, if a processor uses one memory for both instruction fetch and data access, a load instruction in the MEM stage may conflict with a new instruction in IF. Designers can resolve this conflict by duplicating the resource, using separate instruction and data caches, scheduling access in different cycles, or stalling the pipeline.

Resource duplication improves throughput but increases area, power, and verification effort. A design decision must therefore consider workload demands and implementation cost rather than treating every structural hazard as a purely technical defect.

Data hazards

Data hazards arise from relationships between instructions. The classical dependencies are:

• RAW (read after write): a later instruction reads a value before an earlier instruction writes it. This is a true dependence and must be preserved.
• WAR (write after read): a later instruction writes a location before an earlier instruction reads it. This is an anti-dependence.
• WAW (write after write): two instructions write the same location in an order that must be preserved.

In a simple in-order pipeline, RAW hazards are the most immediate concern. WAR and WAW hazards generally appear when instructions can execute or complete out of order. Register renaming can eliminate the false name dependencies represented by WAR and WAW.

Consider:

```text

ADD R1, R2, R3

SUB R4, R1, R5

```

The SUB instruction requires the value produced by ADD. If the ADD result is written only in WB, SUB may have to wait. A forwarding path can send the result directly from a later pipeline stage to the EX input of SUB, avoiding the need to wait for register-file write-back.

Forwarding does not remove every stall. In a load-use sequence such as:

```text

LW R1, 0(R2)

ADD R3, R1, R4

```

the loaded value may become available only after the MEM stage. The dependent ADD needs it earlier in its EX stage, so a one-cycle interlock is commonly required in a basic five-stage pipeline. The control unit detects the condition, inserts a bubble, and then permits execution to continue with forwarding.

Control hazards

A control hazard occurs when the processor does not yet know which instruction should be fetched next. Conditional branches are the principal source. Until the branch condition and target address are resolved, the sequentially fetched instructions may be incorrect.

A processor may stall until the branch is resolved, resolve branches earlier, use a delayed-branch convention, or predict the direction and target. Stalling is simple but expensive, especially in deep pipelines. Speculation improves performance by allowing the processor to fetch and execute along a predicted path; incorrect work must later be discarded.

Hazard-Handling Methods

A pipeline interlock is hardware that detects a hazard and automatically prevents unsafe advancement. It may hold the program counter and instruction-fetch register while inserting a bubble into a later stage. Interlocks preserve correctness without requiring the compiler to understand every microarchitectural detail.

Compiler scheduling attempts to place independent instructions between a producer and its consumer. For example, an address calculation or unrelated arithmetic instruction may fill a delay created by a load. Scheduling is effective when the compiler has useful independent work, but it is limited by dynamic information and by differences among processor implementations.

Forwarding, also called bypassing, supplies a newly computed value directly to a consuming functional unit. A forwarding network typically includes multiplexers controlled by comparison logic that matches destination registers of older instructions with source registers of the current instruction. It reduces RAW stalls but increases hardware complexity and can lengthen critical paths.

Hazard detection and forwarding must also respect special cases such as an instruction writing a constant zero register, memory operations with unresolved addresses, and instructions whose results have different availability times. Correctness depends on the timing model of each functional unit.

Measuring Pipeline Performance

Three measures should be distinguished:

• Latency: time from the start of an instruction until its result is available.
• Throughput: rate at which completed instructions emerge.
• Issue width: maximum number of instructions that can begin execution in a cycle.

A pipeline can have high throughput but relatively high latency. For a single dependent chain, latency is often more important than peak issue width. For a large collection of independent operations, throughput and available functional-unit capacity dominate.

The ideal CPI of a fully occupied scalar pipeline is approximately one. In practice,

\[

CPI = CPI_{ideal} + CPI_{structural} + CPI_{data} + CPI_{control} + CPI_{memory}.

\]

The terms represent average penalties from different causes. This decomposition is useful for performance analysis, although real processors may have interacting penalties that cannot be cleanly separated.

Branch Prediction and Speculative Execution

Branch prediction estimates both the direction of a branch and, for a taken branch, its target address. A static predictor may always predict not-taken or use a rule based on branch direction. Dynamic predictors learn from execution history.

A one-bit predictor records the most recent outcome. It performs poorly on loop branches because the final loop iteration changes the prediction and the next loop entry changes it again. A two-bit saturating counter requires two consecutive outcomes to move from a strong prediction to the opposite strong prediction, making it more stable for loops.

More advanced predictors use local history, global history, or combinations of predictors. A branch history table stores prediction states, while a branch target buffer (BTB) caches target addresses so that fetching can redirect quickly. A return-address stack improves prediction for procedure returns, whose targets are difficult to infer from ordinary branch history.

Speculative execution allows instructions from a predicted path to enter the pipeline before the branch is resolved. Speculative results cannot be allowed to corrupt the architecturally visible state until the processor knows that the prediction was correct. On a misprediction, younger instructions are squashed, the correct program counter is restored, and fetching restarts at the proper target.

The cost of a misprediction is approximately the number of cycles required to detect the error and refill the affected pipeline stages. Deep pipelines and wide front ends therefore make branch accuracy especially important. Prediction accuracy alone is not sufficient: a highly accurate predictor may still be unattractive if its access time, power, or storage cost is excessive.

Superscalar Execution and Dynamic Scheduling

A superscalar processor can issue multiple instructions per cycle. If a processor has four issue slots, its theoretical peak is four instructions per cycle, but actual performance depends on instruction independence, fetch and decode bandwidth, functional units, register availability, memory behavior, and branch prediction.

A useful organization separates three activities:

1. Dispatch or issue: identify instructions ready to use available execution resources.

2. Execute: perform the operation in an appropriate functional unit.

3. Complete and commit: make results architecturally visible in program order.

In an in-order superscalar processor, instructions are generally issued and completed in program order, limiting the ability to tolerate variable operation latencies. Dynamic scheduling allows an independent younger instruction to execute while an older instruction waits for an operand or a functional unit.

The classic conceptual model uses reservation stations and a common data bus. An instruction waits in a reservation station until its operands are available and a suitable unit is free. When a result is broadcast, waiting instructions may capture it. Modern implementations use more distributed and specialized wakeup and select logic, but the underlying principle remains: separate dependence readiness from program order.

Register Renaming and the Removal of False Dependencies

Architectural registers are names visible in the instruction-set architecture. Physical registers are internal storage locations used by the implementation. Register renaming maps each new destination to a fresh physical register. This breaks false dependencies:

```text

I1: ADD R1, R2, R3

I2: SUB R1, R4, R5

I3: MUL R6, R1, R7

```

I2 and I1 have a WAW relationship if both write architectural R1, while I3 must use the correct version of R1. Renaming gives I1 and I2 different physical destinations and records which version I3 should read. The true dependence between a producer and its consumer remains, but name-based conflicts disappear.

A rename map tracks the current physical register associated with each architectural register. Free-list management supplies unused physical registers, and retirement returns old physical registers to the free list after they are no longer needed. Physical-register exhaustion can become a performance bottleneck even when functional units are idle.

Out-of-Order Execution and In-Order Commitment

Out-of-order execution improves utilization by allowing ready instructions to execute before older instructions that are stalled. However, committing results out of order would make exceptions and interrupts difficult to present precisely. A common solution is the reorder buffer (ROB).

When an instruction is dispatched, an ROB entry records its program order, destination information, completion status, and exception state. Execution may occur out of order, but retirement occurs from the ROB head in program order. An instruction commits only when all older instructions have completed successfully. If an exception is detected, younger instructions are discarded and the processor resumes at the saved exception point.

This separation produces two important properties:

• execution order may differ from program order;
• architectural state changes occur in program order.

A processor thus achieves dynamic parallelism while maintaining the sequential appearance required by the instruction-set architecture.

Precise Exceptions and Speculation Recovery

An exception is precise when the saved architectural state appears as though all instructions before a particular instruction completed and no instruction after it took effect. Precise exceptions simplify operating-system support, debugging, virtual memory, and restartability.

To maintain precision, speculative stores are usually held in store buffers until retirement, rather than immediately modifying the cache in an irreversible way. Register results may be held in physical registers, but the rename map is updated architecturally only at the appropriate retirement point or through a carefully controlled recovery mechanism.

Recovery is also required for branch misprediction, memory-order violations, and faults such as page misses. The processor must identify the affected instruction, invalidate younger work, restore rename and control-flow state, and restart execution. Recovery mechanisms are therefore central to both performance and correctness.

An Illustrative Applied Case: Improving a Database Query Processor

Background

Consider an illustrative server processor running a database engine that performs index scans, address calculations, comparisons, and conditional branches. The workload contains many short dependency chains and frequent branches whose direction depends on data values.

Situation

Performance counters show a high IPC on arithmetic-heavy code but a much lower IPC during index traversal. Investigation reveals load-use stalls, branch mispredictions, and occasional contention between address-generation units and integer units. Simply increasing clock frequency provides little benefit because the processor spends many cycles waiting for dependent loads and recovering from incorrect paths.

Analysis

Forwarding removes several arithmetic RAW stalls, but data loaded from memory remains unavailable until the end of the load pipeline. A wider issue engine cannot exploit parallelism that is not present in the instruction window. Branch mispredictions are expensive because the front end is deep and the query contains data-dependent conditions. In addition, multiple outstanding loads compete for limited queues and miss-status resources.

Approach

The design team adopts several coordinated measures:

• improve load-use scheduling in the compiler and query-engine code generator;
• add a more capable branch predictor and a larger target buffer;
• increase load-queue capacity while preserving memory-order checks;
• use register renaming to remove false dependencies among address calculations;
• provide an additional address-generation resource;
• retain ROB-based in-order retirement for precise faults.

The team evaluates the changes using IPC, branch-misprediction rate, load-use stall cycles, queue occupancy, energy per query, and tail latency rather than relying on clock frequency alone.

Outcome

The main improvement comes from reducing wasted speculative work and exposing independent address computations. The additional hardware does not benefit every query: highly sequential scans remain constrained by memory latency, while branch-heavy and irregular queries benefit substantially. The case illustrates that ILP is workload-dependent and that improving one structure can shift the bottleneck to another.

Learning Points

Performance analysis must identify the dominant limiting resource. Forwarding, prediction, renaming, and wider issue are complementary mechanisms, not interchangeable solutions. Moreover, a design should be evaluated with application-level metrics, power constraints, and correctness requirements.

Design Trade-offs, Risks, and Professional Considerations

Pipeline design involves trade-offs among frequency, area, power, verification complexity, and performance predictability. Deep pipelines increase branch penalties. Wide issue designs require large instruction windows, multiple functional units, complex wakeup logic, and substantial data movement. These structures can consume significant dynamic power even when useful work is limited.

Common mistakes include treating ideal pipeline speedup as an achievable result, ignoring memory stalls, assuming forwarding eliminates all data hazards, and evaluating branch prediction only by accuracy rather than by misprediction cost and energy. Another mistake is to increase issue width without improving instruction-fetch bandwidth or branch handling.

Speculation also has security implications. Although speculative instructions are eventually squashed architecturally, their transient effects on caches and other microarchitectural state can sometimes be observed indirectly. Defenses may restrict speculation, insert barriers, partition resources, or modify operating-system and compiler behavior. Such measures can reduce performance, demonstrating that microarchitectural optimization must be considered alongside system security and governance.

In safety-critical or highly regulated systems, deterministic timing, verification evidence, and controlled recovery may be more important than peak throughput. Processor selection should therefore reflect the application’s reliability, security, energy, and certification requirements.

Current Directions

Contemporary processors continue to develop more accurate hybrid predictors, larger instruction windows, specialized execution units, and improved memory-dependence prediction. Simultaneous multithreading attempts to use otherwise idle resources by drawing instructions from multiple hardware threads, although it introduces fairness, isolation, and security concerns.

Energy efficiency has become a primary design constraint. Designers increasingly use application-specific accelerators, clustered execution units, value prediction, and adaptive control of speculation. Compiler and hardware cooperation is also important: static scheduling, profile-guided optimization, and feedback-directed code generation can expose parallelism that dynamic hardware alone cannot discover.

Emerging designs must balance general-purpose flexibility with domain specialization. The enduring principle is to exploit parallel work without violating the sequential semantics promised by the instruction-set architecture.

Best Practices for Pipeline Analysis and Design

A disciplined analysis should:

• draw a cycle-by-cycle timing diagram before proposing a hazard solution;
• identify the exact availability cycle of every operand;
• distinguish true dependencies from name dependencies;
• quantify each stall, flush, and recovery penalty;
• match predictor and queue sizes to workload behavior;
• verify precise exception behavior under faults and mispredictions;
• evaluate performance, energy, area, security, and verification cost together;
• validate conclusions with representative benchmarks rather than synthetic peak cases alone.

Chapter Summary

Pipelining overlaps instruction-processing stages to improve throughput, but hazards limit ideal performance. Structural hazards result from resource conflicts, data hazards from instruction dependencies, and control hazards from uncertain next instructions. Forwarding, interlocks, compiler scheduling, and resource duplication address these problems in different ways.

Instruction-level parallelism is expanded through superscalar issue, dynamic scheduling, register renaming, and out-of-order execution. Renaming removes false WAR and WAW dependencies, while reservation structures allow ready instructions to execute independently of stalled older instructions. Reorder buffers restore program-order commitment and support precise exceptions. Branch prediction and speculation reduce control penalties but require recovery after misprediction and introduce power and security concerns. Effective processor design therefore combines performance mechanisms with rigorous correctness, workload analysis, and system-level trade-off evaluation.

Key Terms

Pipeline: An organization that divides instruction processing into stages executed in overlap.

Throughput: The number of instructions completed per unit of time.

Latency: The time required for one instruction or operation to produce its result.

Structural hazard: A conflict caused by insufficient hardware resources.

Data hazard: A conflict caused by dependence between instructions.

Control hazard: Uncertainty about the next instruction due to a branch or other control transfer.

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

WAR dependence: A write-after-read name dependence.

WAW dependence: A write-after-write name dependence.

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

Interlock: Hardware that detects hazards and inserts stalls or bubbles.

Speculation: Execution based on a predicted future path or condition.

Branch predictor: Hardware that estimates branch direction and/or target.

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

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

Reservation station: A structure holding an instruction until operands and execution resources are ready.

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

Reorder buffer: A structure that tracks in-flight instructions and enables in-order retirement.

Precise exception: An exception state that preserves the sequential architectural effects of completed older instructions only.

Review Questions

Short Answer Questions

1. Why does pipelining improve throughput without necessarily reducing the latency of an individual instruction?

2. Distinguish structural, data, and control hazards.

3. Why does forwarding not always eliminate a load-use stall?

4. What is the purpose of a branch target buffer?

5. How does a reorder buffer support precise exceptions?

Long Answer Questions

1. Explain the operation of a five-stage pipeline and derive its ideal completion time for a sequence of instructions.

2. Discuss RAW, WAR, and WAW dependencies and explain how register renaming affects each one.

3. Describe dynamic scheduling using reservation stations, execution units, and result communication.

4. Compare static and dynamic branch prediction, including accuracy, hardware cost, and recovery implications.

5. Explain how out-of-order execution can improve performance while preserving in-order architectural behavior.

Analytical / Application Questions

1. Given a sequence containing an arithmetic dependence, a load-use dependence, and a conditional branch, construct a cycle-by-cycle timing diagram for a five-stage pipeline with forwarding and determine the required stalls.

2. A processor has excellent branch accuracy but low IPC because its load queue is frequently full. Analyze the bottleneck and recommend two architectural or compiler-level interventions.

3. A safety-critical embedded system must support recoverable faults and predictable timing. Evaluate whether a deeply speculative, wide out-of-order processor is appropriate, and justify your decision using the trade-offs discussed in this chapter.

22. Multiple Choice Questions with Answers

Question 1

Which statement best describes the primary benefit of pipelining?

A. It always reduces the latency of every individual instruction

B. It increases instruction throughput by overlapping stages

C. It eliminates all data dependencies

D. It removes the need for branch prediction

Correct Answer: B. It increases instruction throughput by overlapping stages

Question 2

Which hazard occurs when a load and an instruction fetch require the same single memory in the same cycle?

A. Structural hazard

B. RAW hazard

C. Control hazard

D. WAW hazard

Correct Answer: A. Structural hazard

Question 3

Why can a load-use sequence still require a stall in a forwarded five-stage pipeline?

A. The load has no destination register

B. The loaded value becomes available only after the dependent instruction needs it

C. Forwarding works only for branches

D. Register renaming prevents forwarding

Correct Answer: B. The loaded value becomes available only after the dependent instruction needs it

Question 4

Which dependency is a true data dependence that must be preserved?

A. WAR

B. WAW

C. RAW

D. Register-name reuse

Correct Answer: C. RAW

Question 5

What is the principal function of a branch target buffer?

A. To store retired register values

B. To predict or quickly supply the target address of a branch

C. To eliminate structural hazards in the memory unit

D. To hold instructions until operands are renamed

Correct Answer: B. To predict or quickly supply the target address of a branch

Question 6

Register renaming primarily eliminates which hazards?

A. Only structural hazards

B. WAR and WAW name dependencies

C. All RAW dependencies

D. Only control hazards

Correct Answer: B. WAR and WAW name dependencies

Question 7

What is the main reason for committing instructions in program order in an out-of-order processor?

A. To maximize branch mispredictions

B. To preserve precise architectural state and exceptions

C. To prevent all instructions from executing concurrently

D. To avoid using physical registers

Correct Answer: B. To preserve precise architectural state and exceptions

Question 8

A branch misprediction in a deep pipeline is generally costly because it:

A. Requires discarding incorrect-path work and refilling the pipeline

B. Always causes a permanent register-file error

C. Eliminates all future speculation

D. Turns every RAW dependence into a WAW dependence

Correct Answer: A. Requires discarding incorrect-path work and refilling the pipeline

Question 9

Which performance measure represents the maximum number of instructions that may begin execution in one cycle?

A. Latency

B. Issue width

C. Exception precision

D. Branch penalty

Correct Answer: B. Issue width

Question 10

Why are speculative stores commonly delayed until retirement or kept in a store buffer?

A. To prevent them from ever reaching memory

B. To preserve precise recovery if speculation or an exception proves incorrect

C. To eliminate instruction fetch bandwidth

D. To convert control hazards into structural hazards

Correct Answer: B. To preserve precise recovery if speculation or an exception proves incorrect