Pipelined Processor Architecture

Introduction

A pipelined processor overlaps the execution of several instructions. Instead of completing one instruction before beginning the next, the processor divides instruction processing into stages separated by pipeline registers. While one instruction is being decoded, another may be fetched and a third may be executed. Pipelining increases instruction throughput, although it does not normally reduce the latency of an individual instruction.

A conventional five-stage integer pipeline contains:

1. IF (Instruction Fetch): read the instruction and update the program counter.
2. ID (Instruction Decode/Register Read): decode the operation 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.

The stages are illustrative rather than universal. Modern processors may use many more stages, separate issue queues, multiple execution units, out-of-order scheduling, and speculative execution.

Learning objectives

After studying this chapter, you should be able to:

• model a synchronous instruction pipeline;
• calculate latency, throughput, execution time, speedup, and efficiency;
• distinguish structural, data, and control hazards;
• construct correct timing diagrams, including bubbles caused by load-use dependencies;
• explain forwarding, stalling, compiler scheduling, speculation, and branch prediction;
• evaluate design trade-offs in embedded and high-performance processors.

Pipeline timing and performance

Let:

• n = number of instructions;
• k = number of pipeline stages;
• t_i = delay of stage i;
• t_r = pipeline-register overhead, including clock-to-Q and setup time;
• T_clk = clock period.

For a balanced synchronous pipeline,

The latency of one instruction, measured from its entry into IF to completion of WB, is approximately kT_clk. The ideal steady-state throughput is one completed instruction per clock period, or

For a single-issue pipeline with no stalls, the total time for n instructions is

The first instruction requires k cycles; each of the remaining n−1 instructions completes one cycle later.

Non-pipelined comparison

If the same work is performed by a non-pipelined processor whose instruction takes the sum of all stage delays plus any relevant control overhead, let its instruction time be T_inst,np. Then

This is the general comparison. The often-used expression

is valid only as an idealized equal-stage model in which every stage has delay approximately T_clk and register overhead and imbalance are ignored. It should not be treated as a universal formula. In practice, pipeline registers add overhead and unequal stage delays may make the pipelined clock slower than the average stage delay.

Speedup and efficiency are

The efficiency definition applies when comparing a k-stage pipeline with a corresponding one-instruction-at-a-time baseline. It measures how close the speedup is to the ideal value k.

Worked example: ideal timing

A five-stage pipeline executes 20 independent instructions with a 2 ns clock period. Assuming no stalls,

T_pipe=(5+20−1)×2=48 ns.

In the ideal equal-stage non-pipelined comparison, T_nonpipe=20×5×2=200 ns. Therefore,

Speedup=200/48≈4.17,

and Efficiency=4.17/5≈83.3%. The efficiency is below 100% because the pipeline must be filled and drained.

Timing model

A timing table records the stage occupied by each instruction during each cycle. For instructions A, B, and C in a five-stage pipeline:

A bubble is an unused pipeline-stage slot. It is not another instruction and must not be shown as a second complete IF–WB progression.

Load-use dependency and a correctly represented bubble

Consider:

LW   R1, 0(R2)
ADD  R4, R1, R5

The load obtains data from memory in MEM. In a conventional five-stage, single-issue pipeline, the dependent ADD needs its operand in EX. Forwarding cannot provide the loaded value early enough for the immediately following EX cycle, so one stall is required.

The stall freezes the dependent instruction in ID and usually prevents a new instruction from entering IF. The control logic inserts a bubble into EX. Thus, the stall is a control action, whereas the bubble is the empty slot produced in the pipeline. If the design supports an early memory-result path or a different register-file timing convention, the required stall may differ; the timing must always be derived from the actual datapath.

Hazards

A hazard is a condition that prevents the next instruction from executing in its intended cycle.

Structural hazards

A structural hazard occurs when two operations require the same hardware resource simultaneously. For example, if one single-ported memory must fetch an instruction and access data in the same cycle, a load can conflict with IF. Solutions include separate instruction and data caches, multiported memories, resource duplication, or controlled stalls. Resource duplication improves throughput but increases area, power, and verification cost.

Data hazards

Data hazards arise from instruction dependences.

• RAW (read after write): a later instruction reads a value before an earlier instruction has written it. This is the principal true-dependence hazard in a simple in-order pipeline.
• WAR (write after read): a later write could overtake an earlier read. It is generally absent in a basic in-order pipeline but can occur with out-of-order execution.
• WAW (write after write): two writes could complete in the wrong order. It also matters mainly in out-of-order or multi-issue designs.

Forwarding

Forwarding, or bypassing, sends a result directly from a later pipeline stage to an earlier consumer without waiting for register-file write-back. ALU-to-ALU dependencies can often be resolved by forwarding the EX result to the next instruction’s EX input. Forwarding reduces stalls but requires comparators, multiplexers, control logic, and additional timing paths. It cannot eliminate every dependency, especially a conventional load-use dependency.

Stalling

A hazard-detection unit can freeze the PC and IF/ID register while inserting a bubble into the next stage. A generic load-use condition is detected when the instruction in EX is a load and its destination matches a source of the instruction in ID. The exact comparison must account for instructions that do not actually read particular register fields and for architectures in which register zero is hard-wired.

Stalls reduce performance. If an ideal pipeline executes n instructions and incurs s one-cycle stalls, ignoring other effects,

The formula is a simplified single-issue model; branch penalties, cache misses, variable latency, and multiple-issue effects require additional terms or simulation.

Compiler scheduling

A compiler may place an independent instruction between a producer and its consumer. For example, an address calculation or loop-counter update can occupy a cycle that would otherwise be a stall. Scheduling is effective only when suitable independent work exists and when the compiler knows the processor’s latency rules. Static scheduling is especially important in VLIW and some embedded architectures.

Control hazards and branches

A branch creates uncertainty about the next PC. If a five-stage pipeline resolves a branch in EX and fetches sequential instructions meanwhile, wrong-path instructions may need to be flushed. If p is the misprediction penalty in cycles and m branches are mispredicted, the additional time is approximately mpT_clk.

A simple branch-prediction accuracy model is

where f_b is the fraction of instructions that are branches, a is prediction accuracy, p is the penalty for a misprediction, and CPI_ideal is the ideal CPI, often close to 1 for a scalar pipeline. This estimate assumes penalties are additive and independent; real processors may have overlapping misses and more complex front ends.

Prediction methods include:

• static prediction, such as always-not-taken or backward-taken/forward-not-taken;
• one-bit dynamic prediction, which records the last outcome;
• two-bit saturating prediction, which requires two consecutive contrary outcomes to change a strong prediction;
• branch target buffers, which cache target addresses;
• global-history predictors, which correlate predictions with recent branch outcomes;
• hybrid predictors, which select among several prediction mechanisms.

Speculation allows fetching and executing along a predicted path before branch confirmation. Correct speculation improves throughput; incorrect speculation requires recovery and may have security implications because transiently executed operations can affect microarchitectural state.

Superscalar and out-of-order pipelines

A scalar processor issues at most one instruction per cycle; a superscalar processor may issue several if resources and dependences permit. A useful upper bound is

but actual throughput is limited by dependences, functional-unit availability, cache behavior, branch accuracy, and instruction-level parallelism.

Out-of-order processors use reservation stations or issue queues, register renaming, and in-order retirement. Register renaming removes false WAR and WAW dependences by mapping architectural registers to physical registers. A reorder buffer preserves precise architectural state: instructions may execute out of order but normally retire in program order. These mechanisms improve utilization but increase hardware complexity, power consumption, verification difficulty, and exposure to speculative-execution side channels.

A quantitative branch example

Suppose a scalar pipeline has CPI_ideal=1, branch frequency f_b=0.20, prediction accuracy a=0.90, and misprediction penalty p=3 cycles. Then

CPI≈1+0.20×(1−0.90)×3=1.06.

For one billion instructions at a 2 GHz clock,

cycles=1.06×10⁹, and the execution time is 1.06×10⁹/(2×10⁹)=0.53 s.

The result assumes no cache misses or other stalls. It demonstrates why a seemingly small prediction-error rate can affect total performance.

Applied case: pipeline selection for an embedded controller

Background. An illustrative automotive sensor controller must execute a fixed control loop every 10 μs. The design team is choosing between a short three-stage in-order pipeline and a deeper eight-stage pipeline.

Problem. The deeper pipeline can use a shorter clock period, but it increases branch-flush cost and may require more forwarding paths. The controller also has strict power and safety requirements.

Analysis. A deeper pipeline is attractive only if its clock-frequency gain exceeds the performance losses caused by branch penalties, stalls, and clock-register power. A safety-certified in-order design offers simpler timing analysis and more predictable worst-case execution time. A speculative out-of-order core may have higher average performance but makes worst-case analysis and security validation more difficult.

Approach. The team benchmarks representative control loops, measures branch frequency and memory stalls, calculates average and worst-case execution time, and verifies that every loop meets the 10 μs deadline with margin. It selects the shorter pipeline when predictable latency and low energy are more valuable than peak throughput.

Outcome. The decision is based on workload-specific measurements rather than nominal clock frequency. The design also documents hazard behavior, interrupt latency, cache assumptions, and recovery from prediction errors.

Learning points. Pipeline depth is not an isolated measure of performance. Application constraints, verification, energy, security, and real-time determinism are equally important.

Design limitations and best practices

Important limitations include unequal stage delays, register overhead, cache misses, interrupts, variable-latency operations, branch behavior, and finite instruction-level parallelism. Average CPI alone may conceal unacceptable worst-case latency in real-time systems.

Best practices are to:

• define the datapath and timing convention before calculating hazards;
• distinguish instruction latency from instruction throughput;
• show bubbles explicitly in timing tables;
• use forwarding before adding stalls where correctness permits;
• validate branch assumptions with representative traces;
• include memory hierarchy and recovery costs in performance models;
• evaluate energy, area, safety, and security—not only clock frequency;
• test precise exceptions, interrupts, and misprediction recovery.

Chapter Summary

Pipelining overlaps instruction stages to improve throughput. In an ideal k-stage, single-issue pipeline, n instructions require k+n−1 cycles, but real performance is reduced by structural, data, and control hazards. The correct non-pipelined comparison uses the actual non-pipelined instruction time; nkT_clk is only an ideal equal-stage approximation. Forwarding resolves many RAW hazards, while load-use dependencies may require a stall and an explicitly inserted bubble. Scheduling can expose independent work. Branch prediction and speculation reduce control-hazard costs but introduce recovery, power, verification, and security concerns. Superscalar and out-of-order mechanisms increase potential throughput through parallel issue and register renaming, while application requirements determine whether their complexity is justified.

Key Terms

Pipeline: Overlapped sequence of instruction-processing stages.

Stage: A functional portion of instruction processing completed in one pipeline cycle.

Pipeline register: Storage separating adjacent stages.

Latency: Time from the start of an instruction to its completion.

Throughput: Completed instructions per unit time.

CPI: Average clock cycles per instruction.

Structural hazard: Conflict over a hardware resource.

Data hazard: Timing conflict caused by instruction dependence.

RAW: Read-after-write true dependence.

WAR: Write-after-read false dependence.

WAW: Write-after-write false dependence.

Forwarding: Direct transfer of a result to a consuming stage.

Stall: Deliberate delay that holds pipeline progress.

Bubble: Empty pipeline slot inserted to resolve a hazard.

Control hazard: Uncertainty about the next instruction address.

Branch prediction: Estimation of branch direction or target.

Speculation: Execution based on a predicted future path.

Superscalar: Capable of issuing multiple instructions per cycle.

Register renaming: Mapping architectural registers to physical registers.

Precise exception: State in which completed instructions precede the faulting instruction and later instructions have not changed architectural state.

Review Questions

Short Answer Questions

1. Distinguish instruction latency from instruction throughput.
2. Why is nkT_clk not a general non-pipelined timing formula?
3. What is the difference between a stall and a bubble?
4. Why can forwarding fail to remove a conventional load-use stall?
5. Name two mechanisms used to reduce control hazards.

Long Answer Questions

1. Explain the operation of a five-stage pipeline and derive the ideal execution-time expression.
2. Compare structural, data, and control hazards, including one remedy for each.
3. Explain forwarding and hazard detection using a load-use example.
4. Discuss static prediction, dynamic prediction, speculation, and branch recovery.
5. Evaluate the benefits and costs of superscalar out-of-order execution.

Analytical / Application Questions

1. A six-stage pipeline has a 1.5 ns clock and executes 40 independent instructions without stalls. Calculate its execution time and compare it with the ideal equal-stage non-pipelined model.
2. A workload has branch frequency 15%, prediction accuracy 92%, and a five-cycle misprediction penalty. With ideal CPI of 1, calculate the approximate CPI.
3. Design a timing table for a load followed by a dependent ALU instruction and explain where the bubble appears and why.

Multiple Choice Questions with Answers

Question 1

For a five-stage pipeline executing 12 instructions with no stalls, how many clock periods are required?

A. 12

B. 16

C. 60

D. 17

Correct Answer: B. 16

Question 2

Which hazard is a conflict between two instructions needing the same hardware resource in one cycle?

A. Structural hazard

B. RAW hazard

C. Control hazard

D. WAW hazard

Correct Answer: A. Structural hazard

Question 3

In the conventional five-stage pipeline described, why does a load-use pair usually require one stall?

A. The load has no WB stage

B. The dependent instruction needs the value before memory data is available for forwarding

C. The register file cannot be read

D. The branch predictor is incorrect

Correct Answer: B. The dependent instruction needs the value before memory data is available for forwarding

Question 4

What does forwarding primarily do?

A. Increases memory capacity

B. Sends a result directly to a consuming pipeline stage

C. Eliminates all control hazards

D. Changes a scalar processor into a superscalar processor

Correct Answer: B. Sends a result directly to a consuming pipeline stage

Question 5

A pipeline has ideal CPI 1, branch frequency 0.10, accuracy 0.80, and penalty 4 cycles. What is the approximate CPI?

A. 1.08

B. 1.20

C. 1.32

D. 4.80

Correct Answer: A. 1.08

Question 6

Which statement about T_nonpipe=nkT_clk is correct?

A. It is valid for every real processor

B. It applies only to an ideal equal-stage comparison that ignores imbalance and register overhead

C. It calculates branch-prediction accuracy

D. It is the latency of one pipelined instruction

Correct Answer: B. It applies only to an ideal equal-stage comparison that ignores imbalance and register overhead

Question 7

Which mechanism primarily removes false WAR and WAW dependences?

A. Register renaming

B. Instruction flushing

C. Static branch prediction

D. Clock gating

Correct Answer: A. Register renaming

Question 8

A bubble in a timing table represents:

A. A second complete instruction

B. An empty pipeline slot

C. A cache line

D. A committed branch

Correct Answer: B. An empty pipeline slot

Question 9

If a five-stage pipeline has a 2 ns clock and executes 20 instructions with no stalls, its ideal time is:

A. 40 ns

B. 48 ns

C. 50 ns

D. 200 ns

Correct Answer: B. 48 ns

Question 10

What is a principal advantage of in-order pipelines in embedded real-time systems?

A. They always have the highest peak throughput

B. They make timing and worst-case behavior easier to analyze

C. They eliminate all memory stalls

D. They require no hazard detection

Correct Answer: B. They make timing and worst-case behavior easier to analyze