Pipelines overlap work and expose dependencies

Prerequisites: Instruction execution and register operands.

Learning objectives

• Distinguish latency from throughput.
• Identify data, structural, and control hazards.
• Calculate a cycle count with explicitly stated forwarding rules.

Throughput and latency answer different questions

Imagine a five-stage in-order pipeline: fetch, decode, execute, memory, and writeback. In an ideal model, each stage takes one cycle and processes a different instruction. An individual instruction still takes five cycles from fetch through writeback, but after filling the pipeline, one instruction completes per cycle. For n instructions with no stalls, completion takes n+4 cycles.

Pipelining does not automatically shorten a dependency chain. It divides work into stages so independent work can overlap. The clock period must accommodate the slowest stage plus register overhead. Splitting stages further may raise clock frequency while increasing overhead and branch-recovery cost.

A value has an availability time

A read-after-write dependency occurs when one instruction consumes a value produced by an earlier instruction. Consider this pseudocode, where each line denotes a machine instruction:

PSEUDOCODE: register-machine instruction sequence
add r1, r2, r3
add r4, r1, r5
load r6, [r4]
add r7, r6, r8

Assume ALU results are available at the end of execute, load results at the end of memory, and forwarding can deliver a prior result to a later execute stage. The second add can use the first result without waiting for register-file writeback. The load similarly receives the computed address from the second add. But the final add would enter execute while the preceding load is still obtaining data in memory. Under this conventional timing model, one bubble delays the add so the loaded value is available.

The four-instruction sequence therefore takes 4+4+1=9 cycles in the simplified model. A different pipeline or forwarding network can change that count, so a diagram without timing assumptions is incomplete.

Dependencies and resource conflicts differ

A structural hazard occurs when two operations need a resource that cannot serve both, such as a single memory port shared by instruction fetch and data access. A control hazard occurs when the next instruction address depends on an unresolved branch. A data dependency describes the program; whether it causes a stall depends on the implementation.

Out-of-order machines can execute independent instructions while another waits, but must preserve architectural behavior. Renaming removes false dependencies caused by reusing register names; it cannot remove the need for a consumer to receive its producer’s value. Memory dependencies also require attention because two different address expressions may refer to the same location. Begin any performance explanation by identifying the actual dependency or resource, then determine whether the machine can overlap, forward, predict, or must wait.

Primary reading

• Pipelining the Beta (MIT OpenCourseWare, Computation Structures).

Practice problem

In the same five-stage model, an eight-instruction sequence has two load-use stalls and one independent structural stall. Assume no overlaps among stalls and no branches. Compute total cycles and average cycles per instruction. Explain why the result differs from the steady-state ideal of one instruction per cycle.

Worked solution

The ideal completion time for eight instructions is eight plus four fill-and-drain cycles, giving twelve. The three additional non-overlapping stalls raise the total to fifteen cycles. Average cycles per instruction over this finite sequence is 15/8=1.875. The result includes the startup and completion overhead as well as stalls. One instruction per cycle describes the ideal sustained completion rate after filling the pipeline, not the latency of a single instruction and not necessarily the average for a short program. If the same pattern repeats for a very long stream, the fixed four-cycle boundary cost becomes relatively small, while recurring stalls still contribute. If stalls overlap or a different forwarding path exists, the arithmetic must be revised rather than adding penalties blindly.

Check your understanding

What does forwarding change for a true read-after-write dependency?

• It removes the mathematical dependence.
• It can deliver the value before register-file writeback.
• It lets the consumer use an arbitrary old value.
• It guarantees zero latency for all loads.

Explanation

The consumer still needs the correct result; forwarding changes the delivery path and timing.

Under the stated model, why does a load followed immediately by its consumer stall?

• The loaded value becomes available too late for the consumer’s next execute stage.
• All consecutive instructions always stall.
• The register name has too many bits.
• The pipeline cannot fetch any arithmetic instruction.

Explanation

The availability time of a load differs from an ALU result in this model.

Primary reading

• Pipelining the Beta: MIT OpenCourseWare, Computation Structures

Open the study and save your work →