4.2 Pipelining — Arithmetic & Instruction Pipelining

Prerequisites

Before studying this chapter, ensure you have reviewed the following topics:

• Chapter 1.5: Fixed & Floating Arithmetic (floating-point representations, alignment, normalization)
• Chapter 1.6: Instruction Cycle & Interrupts (the fetch, decode, execute stages of sequential processors)
• Chapter 4.1: RISC vs CISC Architectures (RISC load-store and instruction uniformity advantages)

1. Introduction to Pipelining

Pipelining is an implementation technique where multiple instructions are overlapped in execution. It acts like an industrial assembly line: instead of waiting for a single product to finish all production stages before starting the next, new products enter stage 1 as soon as the previous product moves to stage 2.

Pipelining represents **temporal parallelism** rather than spatial parallelism. Instead of duplicating the execution hardware (spatial), we split the single execution path into sequential stages and overlap execution times (temporal).

In a pipelined processor, the clock cycle time ($T_{\text{clk}}$) is limited by the propagation delay of the slowest pipeline stage, plus the latching setup time of the intermediate registers. Let $\tau_i$ be the delay of stage $i$, and $d$ be the register latch delay. The clock cycle duration is:

2. Arithmetic Pipelining

Arithmetic pipelines are used to segment complex mathematical calculations, such as floating-point arithmetic or multiplication. A classic example is **Floating-Point Addition**, which is typically decomposed into four distinct stages:

1. Compare Exponents: Subtract exponents to find the difference.
2. Align Mantissa: Shift the mantissa of the smaller number to align it with the larger exponent.
3. Add/Subtract Mantissa: Perform addition or subtraction on the aligned mantissas.
4. Normalize Result: Shift the mantissa back and update the exponent to fit the standard floating-point representation.

3. Instruction Pipelining — The 5-Stage Pipeline

Instruction pipelining overlaps phases of the instruction cycle. A classic RISC processor employs a **5-stage instruction pipeline**:

• Instruction Fetch (IF): Read the instruction from memory using the Program Counter (PC).
• Instruction Decode (ID): Decode the instruction and read operands from register file.
• Execute (EX): Run the instruction through the ALU (e.g., execute addition or compute memory address).
• Memory Access (MEM): Read or write data from/to memory (load and store operations only).
• Write Back (WB): Write the final computed value back into the register file.

To allow independent stage operations, **Pipeline Registers** (IF/ID, ID/EX, EX/MEM, MEM/WB) are placed between adjacent stages to hold state variables and data for the next clock cycle.

4. Space-Time Diagrams

A **Space-Time Diagram** (also called a pipeline schedule) is a grid demonstrating instruction execution cycles. The vertical axis represents the pipeline stages (space), while the horizontal axis represents clock cycles (time).

The diagram below shows the startup transient (filling the pipeline), the steady-state (full throughput), and the flushing transient:

5. Pipeline Performance Analysis

Let $n$ be the number of instructions, and $k$ be the number of pipeline stages. Let $t_{\text{clk}}$ be the clock cycle duration.

• The total time taken to execute $n$ instructions on a non-pipelined sequential CPU is: $$T_{\text{seq}} = n \times k \times t_{\text{clk}}$$
• The total time taken to execute $n$ instructions on a pipelined CPU is: $$T_{\text{pipe}} = [k + (n - 1)] \times t_{\text{clk}}$$

The ideal performance metrics are defined as:

Equation 4.2.2: Speedup (S) of a k-stage pipeline processing n instructions.

Equation 4.2.3: Pipeline Throughput (Tp), representing instructions executed per second.

Equation 4.2.4: Pipeline Efficiency (E), indicating the average utilization percentage of all stages.

6. Pipeline Hazards — Taxonomy

In practice, the ideal speedup is rarely achieved due to **pipeline hazards** — conditions that prevent the next instruction in the instruction stream from executing in its designated clock cycle. Hazards force the pipeline to stall, introducing "bubble" cycles (CPI increases above 1.0).

Hazards are classified into three primary categories:

1. Structural Hazards: Occur when two instructions require the same hardware resource simultaneously (e.g., a single memory port used for both instruction fetch and data read).
2. Data Hazards: Occur when an instruction depends on the result of a previous instruction that has not yet completed execution (RAW, WAR, WAW).
3. Control Hazards: Occur when the pipeline makes a decision based on a branch instruction before the branch condition is resolved.

7. Structural Hazards

A structural hazard represents a resource conflict. For example, if a CPU has a unified cache memory (containing both data and instructions) with a single read/write port, a conflict occurs when instruction $I_1$ attempts to read data in cycle 4 (MEM stage) while instruction $I_4$ attempts to fetch its instruction (IF stage).

Resolutions:

• Resource Duplication: Separate caches for instructions (I-Cache) and data (D-Cache) (Harvard memory architecture).
• Stalling: The hardware control unit stalls the fetch phase of the conflicting instruction, inserting a bubble cycle.

8. Data Hazards

Data hazards occur when the execution order of instructions violates register dependency rules:

• Read After Write (RAW): Instruction B attempts to read a register before Instruction A writes to it. This is a *true dependency* and the most common hazard.
• Write After Read (WAR): Instruction B attempts to write to a register before Instruction A reads it. This *anti-dependency* does not occur in simple in-order 5-stage pipelines, but is common in out-of-order execution.
• Write After Write (WAW): Instruction B attempts to write to a register before Instruction A writes to it. This *output dependency* occurs only in out-of-order execution engines.

9. Data Hazard Resolution

To prevent incorrect calculations, the processor must detect data hazards and resolve them:

1. Pipeline Stalling (Inserting Bubbles)

The hazard detection unit halts the IF and ID stages, allowing the execution stages to continue. This introduces a "bubble" cycle that pushes the dependent read phase back until the write phase completes.

2. Data Forwarding / Bypassing

The result computed by the ALU is available at the end of the EX stage (in the EX/MEM register) before it is physically written to the register file in the WB stage. **Data Forwarding** routes this computed result directly back to the input of the ALU for the next cycle, eliminating stalls for ALU-to-ALU dependencies.

10. Control Hazards & Branch Prediction

Control hazards are caused by branch instructions. In a 5-stage pipeline, a branch decision is typically computed in the EX stage (cycle 3). By that time, two subsequent instructions have already entered the fetch and decode stages. If the branch is *taken*, these two instructions are incorrect and must be flushed (converting them to NOPs), causing a **2-cycle branch penalty**.

Resolutions:

• Branch Delay Slot: The instruction following a branch is always executed, regardless of whether the branch is taken. Compilers attempt to place a safe, useful instruction here.
• Static Prediction: Always predict "Taken" or "Not-Taken". Modern compilers predict backward branches (like loops) as Taken, and forward branches as Not-Taken.
• Dynamic Prediction: Uses runtime history to predict outcomes. A popular mechanism is the **2-Bit Saturating Counter**, which requires two consecutive mispredictions to change its prediction direction, avoiding mistakes on loop exits.

11. Worked Examples

I1: ADD R1, R2, R3    ; R1 = R2 + R3
I2: SUB R4, R1, R5    ; R4 = R1 - R5

12. Practice Numerical Problems

13. Assessment Bank (GATE & University)

GATE Questions

LW  R1, 0(R2)      ; R1 = Mem[R2]
AND R3, R1, R4     ; R3 = R1 & R4

University Exam Questions

UQ 4.2.1: Explain the three types of pipeline hazards with examples for each. How does data forwarding resolve RAW hazards? (8 marks)

UQ 4.2.2: Draw a space-time diagram for a 4-stage arithmetic pipeline performing floating-point addition on four pairs of operands. (5 marks)

Viva Voce Questions

VQ 4.2.1: Why can't data forwarding resolve load-use hazards without inserting a stall?

Model Answer: In a load instruction, data is read from memory only at the end of the MEM stage. A dependent instruction requires this operand at the start of its EX stage. Because these stages occur in the same clock cycle, the data cannot be forwarded without delaying the dependent instruction by 1 cycle (stalling it), which shifts the EX stage to the next clock cycle when the loaded data is available in the MEM/WB register.