Appendix C: Pipelining: Basic and Intermediate Concepts

These notes follow Computer Architecture — A Quantitative Approach by John L. Hennessy and David A. Patterson, but for a simpler, easier-to-follow version based on my class lectures, check out these notes.

Pipelining is an implementation technique where multiple instructions are overlapped in execution.

• Takes advantage of parallelism among actions needed to execute an instruction
• Key implementation technique for fast processors
• Even processors costing <$1 are pipelined
• Invisible to the programmer
• The primary technique used to achieve high processor performance.

Appendix C: Pipelining: Basic and Intermediate Concepts

Pipelining Analogy

• Comparable to an assembly line:
• Each stage performs part of the task.
• Different instructions occupy different stages simultaneously.
• Each stage is called a pipeline stage or pipe segment.
• Instructions are entered at one end and exit at the other.

Throughput and Clock Cycle

• Throughput: rate at which instructions complete.
• Determined by how often instructions exit the pipeline.
• All stages advance together with each processor cycle.
• Clock cycle time is determined by the slowest pipeline stage.
• Typically equals one clock cycle.

Ideal Pipeline Performance

• If stages are perfectly balanced:

• Ideal speedup equals the number of pipeline stages.
• In practice:
• Stages are unbalanced.
• Pipeline overhead exists.
• Achieved speedup is slightly less than ideal.

Effect on Cycles Per Instruction (CPI)

• Pipelining reduces CPI by increasing instruction throughput.
• Execution time of individual instructions does not decrease.
• Average program execution time does decrease.

RISC-V Instruction Set Basics

Used throughout the book to illustrate concepts.

• Concepts apply broadly to RISC architectures (ARM, MIPS).
• Chosen for simplicity and pipeline friendliness.

Key RISC Properties

All RISC architectures are characterized by these properties.

Why these properties?: Lead to dramatic simplifications in pipelining implementation (why instruction sets are designed this way)

A Simple Implementation of a RISC Instruction Set (Unpipelined)

• Each instruction completes in at most 5 cycles.
• Designed to transition naturally to pipelining.
• Uses temporary internal registers (not architectural).

Five Execution Cycles

1. **IF (Instruction Fetch)

• **Fetch instruction from memory.
• Increment PC by 4.

2. **ID (Instruction Decode / Register Fetch)

• **Decode instruction.
• Read source registers.
• Perform branch comparison.
• Sign-extend immediate.
• Compute branch target.
• Uses fixed-field decoding.

3. **EX (Execute / Address Calculation)

• **ALU operation depending on instruction: — Effective address calculation — Register-register ALU operation — Register-immediate ALU operation — Branch condition evaluation

4. **MEM (Memory Access)

• **Load: read from memory.
• Store: write to memory.

5. **WB (Write Back)

• **Write ALU or load result to the register file.

Instruction Latencies

• Branch instructions: 3 cycles
• Store instructions: 4 cycles
• Other instructions: 5 cycles
• Example CPI with typical mix: 4.66

Note: This implementation is not optimal for:

1. Best performance
2. Minimal hardware given performance level
3. Focus: Pipelining this version (design improvements left as an exercise)

The Classic Five-Stage Pipeline for a RISC Processor

• Each of the five cycles becomes a pipeline stage.
• New instruction starts every clock cycle.
• Multiple instructions execute concurrently in different stages.
• Up to 5× throughput improvement under ideal conditions.

This diagram visualizes a simple RISC five-stage pipeline, illustrating how multiple instructions are overlapped in time to improve throughput. On each sequential clock cycle (1 through 9), a new instruction (i, i+1, etc.) enters the pipeline and begins its execution, shifting through the five distinct stages: IF (Instruction Fetch), ID (Instruction Decode), EX (Execution), MEM (Memory Access), and WB (Write-Back). Ideally, once the pipeline is full (at clock cycle 5), one instruction completes every single cycle, offering a theoretical performance increase of up to five times compared to a non-pipelined processor, where instructions would execute one after another.

Pipeline Resource Considerations

• Hardware resources must not be used simultaneously by different stages.
• RISC simplicity minimizes conflicts.

This figure visualizes pipelining as a series of identical data paths shifted in time, showing the overlap among parts of the data path as hardware resources are utilized across multiple instructions. The horizontal axis tracks time in Clock Cycles (CC 1 to CC 9), while the vertical axis lists instructions in execution order. Key symbols include IM (Instruction Memory) for fetching, the ALU (Arithmetic Logic Unit) for execution, DM (Data Memory) for memory access, and Reg (Register File), which appears twice per row to reflect its use in two different stages. The first “Reg” instance (left) represents reading source operands during the Decode stage, while the second (right) represents saving results during Write-Back; solid lines indicate active use (reading or writing), while dashed lines show when the register is not effectively used. By Clock Cycle 5 (CC 5), the pipeline achieves a “steady state” where all five stages — Fetch, Decode, Execute, Memory, and Write-Back — are active simultaneously, each processing a different instruction.

Key Design Choices

• Separate instruction and data memories (separate caches).
• Register file supports:
• Two reads (ID stage)
• One write (WB stage)
• Register write occurs in the first half of the clock cycle.
• Register read occurs in the second half.

Program Counter and Branch Support

• PC updated every IF stage.
• The separate adder computes the branch target during ID.
• ALU evaluates the branch condition during EX.

Pipeline Registers

• Registers are inserted between stages to prevent interference.
• Preserve intermediate results across cycles.
• Named by connected stages:
• IF/ID
• ID/EX
• EX/MEM
• MEM/WB
• Edge-triggered behavior prevents data corruption.

Basic Performance Issues

• Pipelining:
• Increases throughput
• Does not reduce single-instruction latency
• Execution time per instruction may increase slightly due to overhead.

Performance Limits

• Stage imbalance
• Pipeline register setup time
• Clock skew
• Latch propagation delay
• Once overhead dominates the cycle time, deeper pipelining gives no benefit.

Example Speedup Calculation

• Unpipelined clock: 0.5 ns
• Average CPI: 4.4
• Average instruction time: 2.2 ns
• Pipeline overhead: 0.1 ns
• Pipelined clock: 0.6 ns
• Speedup: 3.7×
• Pipeline overhead limits maximum achievable speedup (Amdahl’s Law).

C.2 The Major Hurdle of Pipelining — Pipeline Hazards

Pipeline hazards are situations that prevent the next instruction from executing in its scheduled clock cycle. They reduce performance by introducing stalls, lowering the ideal speedup from pipelining.

Three Classes of Hazards

1. Structural Hazards

• Occur due to hardware resource conflicts
• Hardware cannot support all overlapping instruction combinations
• Common in special-purpose units (e.g., floating-point divide)
• Rare in modern processors
• Minimal performance impact when compilers and programmers account for low-throughput units

2. Data Hazards

• It occurs when an instruction depends on the result of a previous instruction
• Caused by overlapping execution in the pipeline

3. Control Hazards

• Arise from pipelining of branches and other instructions that change the PC

Pipeline Stalls

Stall Mechanism: When a hazard is detected, some instructions are allowed to proceed while others are delayed

Stall propagation rules:

• Instructions issued LATER than stalled instruction (not as far along): Also stalled
• Instructions issued EARLIER than stalled instruction (farther along): Must continue (otherwise hazard never clears)

Result during stall: No new instructions fetched

Performance of Pipelines With Stalls

A stall causes the pipeline performance to degrade from the ideal performance.

Pipelining can be thought of as decreasing the CPI or the clock cycle time.

Ideal vs Actual CPI

Ideal CPI (pipelined): Almost always 1

Actual CPI (pipelined)

Special Case: Equal Instruction Cycles

When all instructions take the same cycles = number of pipeline stages (pipeline depth):

With no stalls: Speedup = Pipeline depth (intuitive result)

Data Hazards

A major effect of pipelining is to change the relative timing of instructions by overlapping their execution. This overlap introduces data and control hazards.

Problem: Pipeline changes the order of read/write accesses to operands

• An order differs from sequentially executing instructions on an unpipelined processor

Three Types of Data Hazards Assume: Instruction i occurs before instruction j in program order; both use register x

Three Types of Data Hazards

RAW Hazard Example:

This figure displays a sequence of instructions designed to illustrate a Read-After-Write (RAW) data hazard caused by dependencies in a pipelined processor. The initial add instruction calculates a value for register x1, which is effectively the "write" operation. All subsequent instructions (sub, and, or, xor) immediately attempt to use register x1 as a source operand ("read"). Because a standard pipeline writes results back in the final stage (WB) but reads operands in an early stage (ID), the sub instruction attempts to read x1 before the add instruction has actually finished writing the new value, potentially retrieving incorrect or deterministic data unless hardware precautions (like forwarding or stalling) are taken.

This diagram illustrates a Read-After-Write (RAW) data hazard, where dependent instructions attempt to read a register value before the preceding instruction has finished writing it. The shaded Reg box in Clock Cycle 5 (CC 5) marks the moment the initial DADD instruction finally writes its result back to the register file. The dotted lines trace the dependency relationships, connecting this write event to the moments when subsequent instructions (DSUB, AND, OR) try to read that same register during their own Decode stages. These lines visually demonstrate the failure: the DSUB and AND instructions attempt to fetch the data in CC 3 and CC 4—cycles before the data actually exists in the register—while the OR instruction attempts to access it simultaneously in CC 5, necessitating hardware solutions like stalling or forwarding to ensure correct execution.

Minimizing Data Hazard Stalls by Forwarding (Bypassing)

Observation: Result not really needed by sub until after add actually produces it

Solution: Move result from pipeline register where add stores it to where sub needs it → avoid stall

Forwarding Mechanism

Two-step process:

1. ALU result always fed back: From EX/MEM and MEM/WB pipeline registers to ALU inputs
2. Forwarding hardware detection: If the previous ALU operation wrote a register corresponding to the source for the current ALU operation

• Control logic selects the forwarded result as the ALU input
• Rather than the value read from the register file

Important property: If sub is stalled, add completes and bypass not activated (same for interrupt between instructions)

This diagram illustrates how Forwarding (or bypassing) resolves data hazards by creating a shortcut for data flow. Instead of forcing dependent instructions like DSUB and AND to wait until the DADD instruction completely finishes writing to the register file, the hardware uses special paths (shown as dotted lines) to send the computed result directly from the pipeline registers (the vertical gray bars) to the ALU inputs, where it is needed immediately. This allows the pipeline to keep moving without stalling. For the OR instruction, the correct value is retrieved through the register file itself, because the hardware is designed to write the new data during the first half of the clock cycle and allow the OR instruction to read it during the second half.

Forwarding can be generalized to include passing a result directly to the functional unit that requires it: a result is forwarded from the pipeline register corresponding to the output of one unit to the input of another, rather than just from the result of a unit to the input of the same unit. To prevent a stall in this sequence, we would need to forward the values of the ALU output and the memory unit output from the pipeline registers to the ALU and data memory inputs. Check the below example.

This diagram illustrates how generalized forwarding resolves data hazards in a sequence involving arithmetic (DADD), load (LD), and store (SD) instructions. The DADD instruction calculates a value for register R1, which is immediately needed by the LD and SD instructions to compute memory addresses; to prevent delays, this value is forwarded directly from the ALU output to the ALU inputs of the subsequent instructions. Additionally, a unique forwarding path handles the dependency between the load and the store: the data value (R4) retrieved by the LD instruction is forwarded directly from the memory unit's output to the memory unit's input for the SD instruction. This ensures the store operation receives the data it needs to write to memory the instant it is available, bypassing the register file entirely to avoid stalling the pipeline.

Data Hazards Requiring Stalls

This figure highlights a Load-Use Data Hazard, a specific dependency scenario where simple bypassing is insufficient to prevent a stall. The sequence shows a ld instruction loading a value into x1 that is immediately needed by the subsequent sub instruction. Unlike back-to-back ALU operations, this case presents a fundamental timing problem: the ld instruction does not actually retrieve the data until the end of its MEM stage (Clock Cycle 4), but the sub instruction requires that data at the beginning of that same clock cycle for its execution. Because the data simply does not exist yet when the sub needs it, this hazard cannot be completely eliminated with simple hardware forwarding mechanisms.

This diagram illustrates a Load-Use Data Hazard where standard forwarding fails because the required data path would effectively violate causality. The LD instruction retrieves its value only at the end of the MEM stage (Clock Cycle 4), yet the immediately dependent DSUB instruction requires that same value at the beginning of its ALU stage (also Clock Cycle 4). As the dotted line demonstrates, fulfilling this request would require the data to travel "backward in time" from the end of the cycle to the beginning, which is impossible. While subsequent instructions like AND can receive the forwarded value because the timing allows it, the DSUB hazard cannot be resolved by forwarding alone and requires a pipeline interlock to stall execution until the data is actually available.

Forwarding still helps:

• and: Receives forwarded result from pipeline registers (begins 2 cycles after load)
• or: Receives value through register file (no problem)
• sub: Forwarded result arrives too late (end of cycle when needed at beginning)

Pipeline Interlock

Definition: Hardware that detects a hazard and stalls the pipeline until the hazard is cleared

For load-use hazard:

• Interlock stalls pipeline beginning with the instruction wanting to use data
• Until the source instruction produces it

Stall characteristics:

• Introduces a bubble into the pipeline
• CPI for stalled instruction increases by stall length (1 cycle in this case)

Before Stall Insertion: This diagram visualizes the critical timing mismatch of a Load-Use Data Hazard before any correction is applied. The ld instruction retrieves the value for x1 during its MEM stage at Clock Cycle 4, but the dependent sub instruction attempts to consume that same value at the exact same time during its [EX] stage. Because the data becomes available only at the end of the cycle while the sub needs it at the start, this schedule is functionally impossible to execute without hardware intervention.

After Stall Insertion: This diagram demonstrates how inserting a pipeline stall resolves the hazard by delaying the dependent sub instruction and all subsequent operations by one clock cycle. This insertion creates a "bubble" at Clock Cycle 4, where no new instruction begins, pushing the completion of the entire sequence out to cycle 7. As a result of this shift, the sub instruction can now successfully receive the forwarded data, the and instruction can read its operand directly from the register file (eliminating the need for a forward path there), and the or instruction proceeds without needing any forwarding at all.

Results:

• Instructions starting with sub move one cycle later
• Forwarding to and now goes through the register file
• or needs no forwarding at all
• Sequence takes one additional cycle to complete
• No instruction started during clock cycle 4
• No instruction finishes during cycle 6

Branch (Control) Hazards

Performance impact: Control hazards cause greater performance loss than data hazards for RISC-V pipeline

Branch behavior:

• Taken branch: Changes PC to target address
• Untaken/not taken branch: Falls through (PC = PC + 4)

Timing issue: PC not changed until the end of ID (after address calculation and comparison completion)

Simplest Method: Redo Fetch

Mechanism: Redo fetch of instruction following the branch once the branch is detected during ID

This diagram illustrates a control hazard where a branch instruction forces a one-cycle stall in the pipeline. While the Branch is in its Decode (ID) stage during Clock 2, the pipeline fetches the next instruction (Branch succ), but this initial fetch is ignored and effectively treated as a stall because the branch target address has not yet been resolved. The fetch operation is then forcibly restarted in Clock 3 once the target is known, incurring a consistent one-cycle performance penalty for every branch instruction. This loss is technically unnecessary if the branch is not taken (since the correct instruction was fetched the first time).

Characteristics:

• First IF cycle is essentially a stall (never performs useful work)
• If branch untaken: Repetition of IF unnecessary (correct instruction already fetched)

Performance loss: One stall cycle per branch

• Branch frequency dependent: 10–30% performance loss
• Need techniques to reduce this loss

Reducing Branch Penalties

Four Simple Compile-Time Schemes

Characteristic: Static actions — fixed for each branch during the entire execution

Software role: Minimize branch penalty using knowledge of hardware scheme and branch behavior

Later: Hardware-based dynamic branch prediction (Chapter 3 for more powerful techniques)

Scheme 1: Freeze/Flush Pipeline

Mechanism: Hold or delete any instructions after the branch until the branch destination is known

Advantages:

• Primary: Simplicity for both hardware and software
• Used in Figure C.9 example

Disadvantages:

• Branch penalty fixed
• Cannot be reduced by software

Scheme 2: Predicted-Not-Taken (Predicted-Untaken)

Mechanism: Treat every branch as not taken; continue as if the branch was not executed

Key requirement: Must not change processor state until branch outcome is definitely known

Complexity: Knowing when the state might change and how to “back out” changes

Implementation in a 5-stage pipeline:

• Continue fetching instructions as if the branch were a normal instruction
• Pipeline appears normal

If the branch is actually taken:

• Turn fetched instruction into a no-op
• Restart fetch at the target address

Branch untaken (prediction correct): This diagram demonstrates the Predicted-Not-Taken strategy when the prediction is correct, and the branch is untaken. Because the hardware assumes the branch will not be taken, it automatically fetches the next sequential instruction (Instruction i+1) immediately after the branch. When the branch decision is resolved as "untaken" during the ID stage, the pipeline confirms that the correctly fetched fall-through instruction is already present and simply continues execution without any stalls or penalties.

Branch taken (prediction incorrect): This diagram illustrates the performance penalty in a Predicted-Not-Taken scheme when the branch is actually taken and the prediction is incorrect. The pipeline initially follows its default assumption and fetches the sequential instruction (Instruction i+1). However, once the ID stage determines the branch is taken, the hardware must discard the incorrectly fetched instruction (turning it into a no-op or "idle" state) and restart the fetch at the correct Branch target address. This misprediction forces the pipeline to insert a one-cycle stall, delaying all subsequent instructions.

Result: All instructions following taken branch stall 1 clock cycle

Scheme 3: Predicted-Taken

Mechanism: Treat every branch as taken; assume branch taken as soon as decoded and target computed

Advantage: One-cycle improvement when the branch is actually taken

• Target address known at the end of the ID
• One cycle before knowing whether the branch condition is satisfied (in ALU stage)

Compiler optimization: For both predicted-taken and predicted-not-taken

• Organize code so most frequent path matches the hardware’s choice

Scheme 4: Delayed Branch

Heavy usage: Early RISC processors

Delayed Branch: This snippet illustrates the execution sequence for a Delayed Branch, a technique common in early RISC architectures. The instruction immediately following the branch is placed in a branch delay slot and is always executed, regardless of whether the branch is taken or not. This shifts the burden to the compiler, which must ensure the delay slot contains a valid and useful instruction to maintain correct program logic.

Branch delay slot: Sequential successor instruction

• Executed whether or not the branch taken

Branch Untaken (Delayed Branch): This pipeline diagram shows the behavior of a Delayed Branch when the branch is untaken. The instruction in the delay slot (Delay slot (i+1)) is fetched immediately in Clock 2 and executes normally. Since the branch is untaken, the processor simply continues to the next sequential instruction (Instruction i+2) in Clock 4, executing the sequence without any stalls or performance penalties.

Branch Taken (Delayed Branch): This diagram demonstrates the efficiency of a Delayed Branch when the branch is taken. Identical to the untaken case, the Delay slot (i+1) instruction is fetched in Clock 2 and executed. As this instruction runs, the branch target is resolved, allowing the pipeline to fetch the Branch target instruction in Clock 3 immediately after the delay slot. This mechanism avoids the one-cycle stall typically seen in simple pipelines, provided the delay slot is filled with useful work.

Performance of Branch Schemes

The effective pipeline speedup with branch penalties, assuming an ideal CPI of 1, is

Assuming ideal CPI of 1

where, Pipeline stall cycles from branches = Branch frequency × Branch penalty

By combining these two equation:

Branch frequency components:

• Unconditional branches
• Conditional branches (dominate because more frequent)

Advanced Branch Prediction

Motivation: As pipelines deepen: Branch penalty increases → delayed branches and simple schemes are insufficient

Need: More aggressive branch prediction means

Two prediction classes:

1. Low-cost static schemes: Rely on compile-time information
2. Dynamic strategies: Predict based on program behavior

1. Static Branch Prediction with Profiling

Profile-Based Prediction Key improvement: Use profile information from earlier runs Key observation: Branch behavior often bimodally distributed

• An individual branch is highly biased toward taken or untaken

Effectiveness depends on:

1. Accuracy of the scheme
2. Frequency of conditional branches (varies 3–24% in SPEC)

Major limitation: Higher misprediction rate for integer programs

• Typically have higher branch frequency
• Drives the need for dynamic prediction

2. Dynamic Branch Prediction

Branch-Prediction Buffer (Branch History Table) Simplest dynamic scheme: Small memory indexed by the lower portion of the branch instruction address

Contents: Bit indicating whether the branch was recently taken or not

Characteristics:

• No tags
• Useful only to reduce branch delay when delay > time to compute possible target PCs

Operation:

• Don’t know if prediction is correct (may be from another branch with the same low-order address bits)
• Doesn’t matter: Prediction is a hint assumed correct
• Fetching begins in the predicted direction
• If wrong: Prediction bit inverted and stored back

Effectively a cache: Every access is a hit

Performance depends on:

1. How often prediction is for the branch of interest
2. Prediction accuracy when it matches

1-Bit Prediction Shortcoming

Problem: Even if the branch is almost always taken

• Will likely predict incorrectly twice (not once) when not taken
• Misprediction causes the prediction bit to be flipped

Example scenario:

• The branch is taken 99% of the time
• One untaken occurrence causes:
• First misprediction (branch not taken, predicted taken)
• Bit flips to “not taken”
• Second misprediction (branch taken again, now predicted not taken)

2-Bit Prediction Scheme (Standard)

• Prediction changes only after two consecutive misses
• Uses a 2-bit saturating counter
• Four states:
• Strongly taken
• Weakly taken
• Weakly not taken
• Strongly not taken
• Near-optimal accuracy with low hardware cost

This diagram illustrates a 2-bit branch prediction scheme, which uses a four-state machine to improve accuracy and stability compared to simpler 1-bit predictors. The system uses two bits to track the “strength” of a prediction, ranging from Strongly Not Taken (00) to Strongly Taken (11). The key advantage of this approach is that it requires two consecutive mispredictions to change the overall prediction direction, making it more robust against occasional outliers (like the end of a loop). For instance, if the state is “Predict Taken” (11) and the branch is actually not taken, the system essentially “downgrades” its confidence to a weaker state (10) but still predicts “Taken” for the next time; it will only switch to predicting “Not Taken” if the branch outcome is “Not Taken” a second time in a row.

Branch Prediction Accuracy

• 2-bit predictors achieve:
• ~99% accuracy (best cases)
• ~82% accuracy (worst cases)
• Floating-point programs:
• Lower misprediction rates (~4–9%)
• Integer programs:
• Higher misprediction rates (~11–18%)
• Larger buffers improve accuracy slightly
• Predictor quality is more important than buffer size

**Key Takeaways

1. **Hazards limit ideal pipeline speedup
2. RAW hazards are the dominant data hazard
3. Forwarding removes most ALU hazards
4. Load-use hazards require stalls
5. Branch hazards cause major performance loss
6. Static prediction is limited
7. Dynamic 2-bit branch prediction is essential in modern pipelines
8. Branch accuracy becomes critical as pipeline depth increases

C.3 How Is Pipelining Implemented?

Before proceeding to basic pipelining, a simple implementation of an unpipelined version of RISC-V must be reviewed.

A Simple Implementation of RISC-V

A basic multicycle implementation of an integer subset of RISC-V is used as the foundation for pipelining. The subset includes load-word, store-word, branch-equal, and integer ALU instructions. All RISC-V instructions complete in at most five clock cycles.

**Five Clock Cycles (Unpipelined)

**1. Instruction Fetch (IF)

Operations

Actions:

• Send PC to memory
• Fetch instruction into Instruction Register (IR)
• Increment PC by 4 to address the next sequential instruction
• IR holds instructions for subsequent clock cycles
• NPC (register) holds the next sequential PC

2. Instruction Decode/Register Fetch (ID)

Operations

Actions:

• Decode instruction
• Access register file to read registers (rs1, rs2 are register specifiers)
• General-purpose register outputs are read into temporary registers A and B for later cycles
• Lower 16 bits of IR sign-extended and stored in temporary register Imm for next cycle

Key advantage: Decoding is done in parallel with reading registers

• Possible because fields are at a fixed location in the RISC-V format
• Fixed-field decoding

Immediate handling:

• The immediate portion of the load and the ALU immediate are in identical places in every instruction
• Sign-extended immediate calculated during this cycle (in case needed next cycle)
• Stores require a separate sign-extension (immediate field split in two pieces)

3. Execution/Effective Address (EX)

ALU operates on operands from the prior cycle, performing one of four functions:

1. Memory Reference:

Memory Reference

• ALU adds operands to form an effective address
• Result placed in register ALUOutput

2. Register-register ALU instruction:

Register-register ALU instruction

• ALU performs the operation specified by the function code (combination of func3 and func7 fields)
• Operates on the value in register A and register B
• Result placed in ALUOutput

3. Register-Immediate ALU instruction

Register-Immediate ALU instruction

• ALU performs the operation specified by opcode
• Operates on the value in register A and register Imm
• Result placed in ALUOutput

4. Branch:

Branch

• ALU adds NPC to sign-extended immediate (shifted left 2 bits for word offset)
• Computes the branch target address
• Register A (read in prior cycle) checked by comparing with Register B
• Only the branch equal is considered here

Load-store architecture advantage: Effective address and execution cycles are combined into a single clock cycle

• No instruction simultaneously calculates data address, instruction target address, AND operates on data

Other instructions not included: Jumps of various forms (similar to branches)

4. Memory Access/Branch Completion (MEM)

The PC is updated for all instructions: PC ← NPC;

1. Memory Reference:

• Access memory if needed
• Load: Data from memory placed in the LMD (Load Memory Data) register
• Store: Data from the B register is written to memory
• Address used: Computed during prior cycle, stored in ALUOutput

2. Branch:

• If instruction branches: PC replaced with branch destination address in ALUOutput

5. Write-Back (WB)

1. Register-Register or Register-Immediate ALU instruction:

2. Load instruction:

Actions:

• Write the result into the register file
• Source: Memory system (in LMD) or ALU (in ALUOutput)
• rd designates destination register

Instruction Flow Through Data Path

This diagram illustrates a multicycle RISC-V data path implementation where instructions execute in 4 or 5 clock cycles, divided into five distinct stages: Instruction Fetch, Instruction Decode/Register Fetch, Execute/Address Calculation, Memory Access, and Write-back. The flow begins with the PC and Instruction Memory, moving to the Registers for decoding, then to the ALU for execution, followed by Data Memory, and finally writing results back. While the PC and Registers are visually positioned in the stages where they are read (Fetch and Decode), they are modified by operations completing in later stages; specifically, the PC is updated during the Memory Access cycle, and destination registers are written during the Write-back cycle. The lines looping back from the multiplexers (Mux) in the Memory Access and Write-back stages to the PC and Registers represent these updates. These backward-flowing signals are architecturally significant because they represent dependencies that lead to potential hazards when this logic is converted into a pipelined structure.

Multicycle implementation: Reasonable approximation of how earlier processors implemented

Control options:

• Simple finite-state machine for five-cycle structure
• Microcode control for a more complex processor

Instruction sequence: Determines control structure

Hardware Redundancies Potential optimizations (not implemented to preserve base for pipelining):

Decision: Leave design as-is in Figure C.18 for better pipelined implementation base

A Basic Pipeline for RISC-V

Pipelining the Data Path Simple transformation: Start a new instruction each clock cycle with almost no changes

Requirements for pipelining:

• Every pipe stage is active every clock cycle
• All operations in the pipe stage must complete in 1 clock cycle
• Any combination of operations must occur simultaneously

Critical requirement: Values passed from one stage to the next must be placed in registers

Pipeline Registers (Pipeline Latches)

This figure illustrates a pipelined RISC-V data path, achieved by inserting pipeline registers (IF/ID, ID/EX, EX/MEM, MEM/WB) between each of the five stages to store intermediate values and control information. The Program Counter (PC) effectively acts as a pipeline register for the Instruction Fetch stage and is written at the end of the clock cycle, eliminating race conditions. To prevent conflicts where multiple instructions might attempt to update the PC simultaneously (e.g., during a branch), the PC selection multiplexer is strategically moved to the IF stage, ensuring the PC is written in exactly one stage. While the primary data flow moves left-to-right through the pipeline registers, the “backward” paths — specifically those carrying register write-back data and branch target addresses — introduce significant complexity by creating potential hazards.

Naming convention: Labeled with the names of the stages they connect

• IF/ID: Between Instruction Fetch and Instruction Decode
• ID/EX: Between Instruction Decode and Execution
• EX/MEM: Between Execution and Memory Access
• MEM/WB: Between Memory Access and Write-Back

Subsumption: All temporary registers from the unpipelined version are subsumed into pipeline registers

IR field labeling: Fields of Instruction Register (part of IF/ID) labeled when used to supply register names

Content: Pipeline registers carry both data and control from stage to stage

Value preservation: Any value needed in a later stage must be:

• Placed in the pipeline register
• Copied from one register to the next
• Until no longer needed

Reason for copying: If using only temporary registers from the unpipelined data path

• Values could be overwritten before all uses are completed
• Example: Register operand for write on load/ALU from MEM/WB pipeline register (not IF/ID)
• Want the operation to write the register designated by that operation
• Not register field of instruction currently transitioning IF to ID

Destination register field: Simply copied from one pipeline register to the next until needed during WB

Instruction Activity One stage at a time: Any instruction active in exactly one pipeline stage

Actions: Occur between a pair of pipeline registers

Pipeline Stage Activities

Pipeline register field naming: Shows the flow of data from stage to stage

IF (Instruction Fetch)

Independent of instruction type (instruction not decoded until the end of ID)

Operations:

Actions:

• Fetch instruction
• Compute new PC
• Store incremented PC into PC and pipeline register NPC (for later branch-target address computation)

Branch dependency: If instruction in EX/MEM is taken, the branch

• Branch-target address written into PC at the end of IF
• Otherwise: Incremented PC written back

ID (Instruction Decode/Register Fetch)

Critical property: Fixed-position encoding of register source operands allows registers to be fetched during ID

EX (Execution) — Instruction Type Specific

ALU Instruction

Load Instruction

Branch Instruction

Branch actions:

• Perform an ALU operation or address calculation
• Pass along IR and B register (if store)
• Set the cond value to 1 if the instruction is a taken branch

MEM (Memory Access)

ALU Instruction

Load Instruction

Store Instruction

Actions:

• Cycle memory
• Write PC if needed
• Pass along the values needed in the final stage

Simplification note: Always pass the entire IR from stage to stage (although less needed as instruction proceeds)

WB (Write-Back)

ALU Instruction

Load Instruction

Actions: Update register field from ALU output or loaded value

Implementing Pipeline Control

Instruction Issue Definition: Process of letting instruction move from the ID stage into the EX stage

Issued instruction: The Instruction that made this step

Hazard Detection Timing: Two Approaches

Approach 1: Detection in ID (Used Here for Load Interlock) Advantages:

• All data hazards were checked during the ID phase
• If a hazard exists: Instruction stalled before being issued
• Can determine forwarding needs during ID and set appropriate controls
• Reduces hardware complexity: Hardware never suspends instructions that update the processor state (unless the entire processor is stalled)

Approach 2: Detection in EX/MEM Alternative: Detect hazard/forwarding at the beginning of the clock cycle using the operand (EX and MEM stages)

Implementation shown:

• Load interlock (RAW hazard with source from load) checked in ID
• Forwarding paths to ALU inputs implemented during EX

This table summarizes four key scenarios that pipeline hazard detection hardware must handle by comparing the destination register of a ld (load) instruction with the source registers of the following instructions. In the first case, there is no conflict, so execution is smooth; however, if the very next instruction needs the loaded data immediately (a "load-use hazard"), the hardware must insert a stall to wait for the data. If the dependent instruction is one step further away, the pipeline can avoid stopping by using forwarding to pass the data directly to the ALU. Finally, if the instruction is far enough down the line, the register file handles the timing naturally without any special hardware action needed.

Forwarding Implementation

Pipeline registers contain:

• Data to be forwarded
• Source and destination register fields

Forwarding paths: Logically from ALU or data memory output to:

• ALU input
• Data memory input
• Zero detection unit

Implementation: Compare destination registers of IR in EX/MEM and MEM/WB against source registers of IR in ID/EX and EX/MEM

This table details the logic required to implement data forwarding to the ALU inputs, defining the comparisons needed to detect when a result from a later pipeline stage (EX/MEM or MEM/WB) must be bypassed to the current execution stage (ID/EX). The columns specify which pipeline registers and opcodes are compared; specifically, the hardware checks if the destination register (rd) of a previous instruction matches either of the source registers (rs1 or rs2) of the current instruction. If a match is found, the "Forwarded result" is directed to the appropriate Top or Bottom ALU input to resolve the hazard. Crucially, while this table lists the comparisons for forwarding from both the immediately preceding instruction and the one prior, real implementation requires a priority rule: if both stages attempt to forward to the same input (a "double hazard"), the value from EX/MEM (the most recent instruction) must take precedence over MEM/WB to ensure the correct, latest data is used.

Hardware Implementation

Requirements:

• Comparators and combinational logic to determine when the forwarding path is enabled
• Enlarged multiplexers at ALU inputs
• Connections from pipeline registers for forwarding results

Added paths (three extra inputs on each ALU multiplexer):

1. ALU output at the end of EX
2. ALU output at the end of the MEM stage
3. Memory output at the end of the MEM stage

This diagram illustrates the hardware additions required to implement forwarding to the ALU, specifically by adding three extra inputs to each ALU multiplexer. These inputs connect to new bypass paths (shown as dotted lines) that allow the ALU to retrieve data directly from three different sources: the ALU output at the end of the Execution (EX) stage, the ALU output at the end of the Memory (MEM) stage, and the memory output from the end of the Memory (MEM) stage. These “shortcuts” allow the processor to use the most recently computed values immediately, avoiding the delay of waiting for results to be written back to the register file.

C.4 What Makes Pipelining Hard to Implement?

Pipelining improves performance by overlapping instruction execution, but this overlap makes control more complex. The main difficulties arise from exceptions, instruction set features, and long or irregular instructions.

Exceptions are difficult to handle in a pipelined processor

In a pipelined processor, multiple instructions are partially executed at the same time. An exception raised by one instruction may require stopping or discarding other instructions that are already in progress.

The challenge is determining:

• Which instructions are allowed to update the processor state
• Which instructions must be canceled
• Where execution should resume

To support correct behavior, modern processors require restartable and precise exceptions.

Types of Exceptions and Requirements

An exception is any event that changes the normal instruction flow.

Twelve common exception types:

1. I/O device request
2. Invoking the OS service from a user program
3. Tracing instruction execution
4. Breakpoint (programmer-requested interrupt)
5. Integer arithmetic overflow
6. FP arithmetic anomaly
7. Page fault (not in main memory)
8. Misaligned memory accesses (if alignment required)
9. Memory protection violation
10. Using an undefined/unimplemented instruction
11. Hardware malfunctions
12. Power failure

Key Exception Classification Dimensions

Exceptions differ along five important axes:

1. Synchronous vs Asynchronous

• Synchronous: Caused by the current instruction (e.g., page fault)
• Asynchronous: Caused by external events (e.g., I/O interrupt)

2. User-Requested vs Coerced

• User-requested: Explicitly triggered (e.g., system call)
• Coerced: Triggered by hardware conditions (e.g., overflow)

3. Maskable vs Nonmaskable

• Maskable: Can be disabled by software
• Nonmaskable: Must always be handled

4. Within vs Between Instructions

• Within: Occurs during instruction execution (harder)
• Between: Occurs after instruction completion (easier)

5. Resume vs Terminate

• Resume: Program continues after handling
• Terminate: Program execution stops

The hardest cases are synchronous, coerced, resume-type exceptions occurring within instructions.

Exception Classification Table

This table categorizes different types of exceptions using five criteria to determine how the processor should respond, such as whether the event happens predictably (synchronous) or randomly (asynchronous) and whether the program can continue (resume) or must stop (terminate). The most challenging exceptions to implement are those that are synchronous, coerced, and occur within an instruction — such as a page fault or arithmetic overflow — because the processor must safely save the state in the middle of execution and resume exactly where it left off. For instance, even memory protection violations, which often look like fatal errors, frequently require the processor to resume execution to support standard operating system tasks like managing virtual memory pages.

Most difficult to implement: Synchronous, coerced exceptions occurring within instructions that can be resumed

Note on memory protection: Modern OSes use memory protection to detect events (first page use, first write to page) → processors should be able to resume after such exceptions

Stopping and Restarting Execution

Most Difficult Exception Properties

Two challenging characteristics:

1. Occur within instructions (during EX or MEM pipe stages)
2. Must be restartable

Example: RISC-V pipeline virtual memory page fault from data fetch

• Cannot occur until sometime in the MEM stage
• By that time, Several other instructions were in execution
• Page fault must be restartable and requires OS intervention

Restartable Pipeline Requirements Implementation requirements:

• The pipeline must be safely shut down
• The state must be saved
• Instruction must be restartable in the correct state

Restart mechanism: Save the PC of the instruction at which to restart

• Non-branch instruction: Fetch sequential successors, begin normal execution
• Branch instruction: Reevaluate branch condition, fetch from target, or fall-through

Exception Handling Steps When an exception occurs, pipeline control takes three steps:

1. Force trap instruction into pipeline on next IF
2. Turn off all writes for faulting instruction and all following instructions in the pipeline until trap taken

• Done by placing zeros into pipeline latches
• Starting with exception-generating instruction
• Not those that precede it
• Prevents state changes for instructions not completed before the exception is handled

3. After the OS exception handler receives control:

• Immediately save the PC of the faulting instruction
• PC value used to return from the exception later

After exception handled: Special instructions return the processor from the exception

• Reload PCs
• Restart instruction stream
• (Using exception return in RISC-V)

Precise Exceptions

Definition Precise exception: Pipeline can be stopped so that:

• Instructions just before the faulting instruction are completed
• Instructions after it can be restarted from scratch

Ideal behavior: Faulting instruction would not have changed the state

Required for some exceptions: The Faulting instruction must have no effects

Complications: Floating-Point Operations

Problem: Some processors (FP operations) write the result before the exception is handled

Solution required: Hardware must retrieve source operands even if the destination is identical to the source operand

Challenge: FP operations may run many cycles

• Likely some other instruction wrote source operands
• FP operations often complete out of order (Section C.5)

Modern solution: Two operation modes

1. Precise exception mode: Slower (allows less overlap among FP instructions)
2. Fast/performance mode: Not precise (better performance)

Importance of Precise Exceptions

Required in many systems:

• Any processor with demand paging
• Any processor with IEEE arithmetic trap handlers
• Must provide precise exceptions (in hardware or with software support)

Integer pipelines: The Task of creating precise exceptions is easier

• Virtual memory strongly motivates precise exception support for memory references
• Practical result: Designers always provide precise exceptions for the integer pipeline

Exceptions in RISC-V Pipeline

Pipeline Stage Exception Types

Key observation: Instruction/data memory access exceptions account for 6 out of 8 exception cases

Multiple Simultaneous Exceptions

Problem: With pipelining, multiple exceptions may occur in same clock cycle (multiple instructions in execution)

Both exceptions in cycle 5:

• ld: Data page fault (MEM stage)
• add: Arithmetic exception (EX stage)

Simple handling: Deal with only data page fault, then restart execution

• Second exception will reoccur (but not first, if software correct)
• Second exception handled independently when reoccurs

Out-of-Order Exception Problem

More complex scenario: Exceptions may occur out of order

• Instruction may cause exception before earlier instruction

Problem: Instruction page fault actually occurs first, even though caused by later instruction

Required behavior: Precise exceptions require handling ld exception first (program order)

Exception Status Vector Mechanism

Cannot handle exceptions as they occur in time: Would lead to exceptions out of unpipelined order

Solution: Hardware posts all exceptions in exception status vector associated with each instruction

Exception status vector:

• Carried along as instruction goes down pipeline
• Once exception indication set: Any control signal that may write data is turned off
• Includes register writes
• Includes memory writes

Store instruction handling: Hardware must prevent store from completing if raises exception during MEM

Exception Handling at WB Entry

Check point: When instruction enters WB (or about to leave MEM)

Process:

1. Exception status vector checked
2. If any exceptions posted: Handle in order they would occur in unpipelined processor
3. Exception corresponding to earliest instruction (usually earliest pipe stage) handled first
4. Guarantees all exceptions seen on instruction i before any seen on i+1

Invalid actions protection:

• Any action taken in earlier pipe stages on behalf of instruction i may be invalid
• But because writes to register file and memory were disabled: No state changed

FP operations: Maintaining precise model much harder (Section C.5)

Instruction Set Complications

RISC V Integer Pipeline Simplicity Key characteristics:

• No instruction has more than one result
• Pipeline writes result only at end of instruction execution
• Committed instruction: When guaranteed to complete
• RISC V: All instructions committed at end of MEM stage (or beginning of WB)
• No instruction updates state before that stage

Result: Precise exceptions straightforward

State Change Before Commit Problem

Some processors: Instructions change state in middle of execution before instruction and predecessors guaranteed to complete

Example: IA-32 autoincrement addressing modes

• Update registers during instruction execution
• If instruction aborted by exception: Leaves processor state altered
• Imprecise exception: Instruction half-finished despite knowing which caused it

Restart challenge: Restarting instruction stream after imprecise exception difficult.

FP pipeline: Can introduce similar problems (Section C.5)

Memory Update During Execution

Problem instructions: Update memory state during execution

• String copy operations (Intel architecture)
• IBM 360 similar operations (Appendix K)

Solution: Instructions defined to use general-purpose registers as working registers

• State of partially completed instruction always in registers
• Registers saved on exception
• Registers restored after exception
• Allows instruction to continue

Condition Codes

Additional state complexity: Odd bits creating pipeline hazards or requiring extra save/restore hardware

Condition codes as example:

Advantages:

• Many processors set condition codes implicitly as part of instruction
• Decouples condition evaluation from actual branch

Disadvantages

Explicitly set condition codes: Allow delay scheduling between condition test and branch

• But pipeline control must still track last instruction setting condition code
• To know when branch condition decided

RAW hazard handling: Condition code must be treated as operand

• Requires hazard detection for RAW hazards with branches
• Similar to RISC V register handling

Multicycle Operations

Example: x86 Instruction Sequence

Instruction characteristics:

• None particularly long (x86 instructions up to 15 bytes)
• Radically different clock cycle requirements: 1 to hundreds of cycles
• Different data memory access requirements: 0 to possibly hundreds
• Very complex data hazards: Between and within instructions
• Example: movsb can have overlapping source and destination

Simple solution (unacceptable): Make all instructions execute same number of clock cycles

• Introduces enormous number of hazards and bypass conditions
• Creates immensely long pipeline

Solution: Microinstruction Pipelining

Clever solution (similar to VAX):

Microinstruction: Simple instruction used in sequences to implement complex instruction set

Strategy:

1. Convert complex instructions into microinstructions/microoperations
2. Pipeline the microinstruction execution

Advantages:

• Microinstructions simple (look like RISC V)
• Pipeline control much easier

Adoption:

• Since 1995: All Intel IA-32 microprocessors use this strategy
• Also used for some complex ARM instructions

Load-Store Processor Advantages

Comparison: Load-store processors have:

• Simple operations
• Similar amounts of work
• Pipeline more easily

Architectural lesson: If architects realize relationship between instruction set design and pipelining, can design architectures for more efficient pipelining

Architectural Insight

Instruction set design strongly affects pipeline complexity. Simpler instruction sets:

• Reduce hazard handling complexity
• Simplify precise exception support
• Enable deeper and faster pipelines

This realization drove the industry toward RISC-style architectures.

Key Takeaway: Pipelining is difficult primarily because of exceptions, state consistency, and complex instruction behavior. Supporting precise, restartable exceptions while maintaining high performance requires careful pipeline control and disciplined instruction set design.

C.5 Extending the RISC V Integer Pipeline to Handle Multicycle Operations

Floating-point (FP) operations require more cycles than integer operations, making single-cycle execution impractical. Supporting FP operations therefore requires extending the RISC-V pipeline to handle multicycle and variable-latency execution.

Motivation for Multicycle FP Operations

Floating-point add, multiply, and divide operations are significantly more complex than integer operations. Forcing them to complete in one or two cycles would require:

• A much slower clock, or
• Excessive hardware complexity

Allowing FP operations to take multiple cycles achieves better performance and efficiency.

This diagram illustrates how a standard RISC-V pipeline is expanded to handle complex floating-point (FP) operations by adding three specialized hardware units alongside the standard Integer unit. While every instruction shares the initial Fetch (IF) and Decode (ID) stages, the path splits at the Execution (EX) phase: simple integer math goes to the fast Integer unit, while complex tasks are routed to the Multiplier, Adder, or Divider. Because floating-point math takes longer to calculate, these specialized units allow instructions to “loop” and spend multiple clock cycles in the Execution stage, unlike the integer unit, which finishes in one cycle. Once the specific functional unit finishes its work, all paths merge back together to complete the instruction in the standard Memory (MEM) and Write-Back (WB) stages.

Pipeline Structure with FP Units

The extended pipeline assumes multiple independent functional units:

• Integer unit (loads, stores, branches, ALU)
• FP/integer multiplier
• FP adder (add, subtract, conversion)
• FP/integer divider

Key characteristics:

• FP execution stages may repeat for several cycles
• Different operations have different latencies
• Some units are pipelined (adder, multiplier)
• Some units are not pipelined (divider)

If a required unit is busy, instruction issue is stalled.

Exceptions

Latency and Initiation Interval

Two parameters describe functional units:

• Latency: Number of cycles before a result becomes usable
• Initiation interval: Minimum cycles between issuing two operations of the same type

Examples:

• Integer ALU: latency 0, initiation interval 1
• FP add: latency 3, initiation interval 1
• FP multiply: latency 6, initiation interval 1
• FP divide: latency 24, initiation interval 25

Longer pipelines increase latency but allow higher clock frequencies.

Pipeline Registers and Execution Flow

FP pipelines introduce additional execution stages (e.g., A1–A4 for FP add, M1–M7 for FP multiply). Instructions move from ID into the appropriate functional unit pipeline and proceed independently.

Results are written back after execution completes, possibly out of order.

This diagram depicts a RISC-V pipeline designed to support multiple outstanding floating-point operations by fully pipelining the arithmetic units into granular stages. Unlike the unpipelined divider, which occupies a single “DIV” block for 24 cycles, the Multiplier and Adder are broken down into seven stages (M1–M7) and four stages (A1–A4), respectively, allowing a new instruction to enter these units every clock cycle. The number of these execution stages determines the latency before a result can be used; for instance, the integer unit completes in a single stage, allowing immediate use by the next instruction, whereas the deeper adder pipeline requires waiting until the fourth subsequent instruction to avoid a stall.

Hazards in Multicycle FP Pipelines

Multicycle execution introduces new hazards:

Structural Hazards

• Occur when a functional unit or write port is busy
• Common for non-pipelined units such as divide

RAW (Read After Write) Hazards

• Increased due to longer operation latency
• Cause frequent stalls when dependent instructions follow

WAW (Write After Write) Hazards

• Occur because instructions may complete out of order
• Must be detected to preserve correct final register values

WAR hazards do not occur because register reads happen in ID.

Hazard Detection and Issue Control

All hazard detection is performed during the ID stage. Before issuing an instruction, the pipeline checks:

1. Availability of required functional unit and write port
2. Absence of RAW hazards based on result availability timing
3. Absence of WAW hazards with earlier issued instructions

Instructions are stalled if any check fails.

Forwarding Support

Forwarding is extended to include:

• Results from FP adder, multiplier, divider, and memory stages
• Multiple pipeline stages as possible forwarding sources

This reduces stalls but does not eliminate all RAW hazards.

Precise Exceptions and Out-of-Order Completion

Multicycle FP operations may complete out of order. Out-of-order completion complicates exception handling because:

• Later instructions may complete before earlier ones
• Exceptions may occur after state has been partially updated

Precise exceptions require that:

• All earlier instructions are complete
• No later instruction has updated state

Techniques for Maintaining Precise Exceptions

Several approaches exist:

1. Imprecise exceptions: Simple but incompatible with virtual memory and IEEE FP
2. Restricted execution modes: Limit overlap of FP instructions
3. Result buffering (history/future files): Delay or undo state updates
4. Software-assisted recovery: Trap handler reconstructs precise state
5. Conservative issue control: Prevent issue unless earlier instructions are guaranteed safe

The last approach is widely used in commercial processors.

Performance Impact

Long FP latencies significantly increase stall frequency:

• FP result stalls dominate performance loss
• Stall cycles scale with functional unit latency
• Total stalls per instruction typically range from moderate to high in FP-intensive workloads

Despite this cost, multicycle pipelines provide much higher throughput than serialized execution.

Supporting floating-point operations requires multicycle, variable-latency pipelines with advanced hazard detection and exception handling. While complexity increases, careful pipeline control preserves correctness and enables high performance.

C.6 Putting It All Together: The MIPS R4000 Pipeline

Overview

• The MIPS R4000 (including R4400) implements MIPS64 with a deeper pipeline than the classic 5-stage RISC pipeline.
• MIPS and RISC-V are very similar ISAs, differing mainly in features such as delayed branches in MIPS.
• The deeper pipeline enables higher clock rates by breaking stages into smaller pieces, a technique known as superpipelining.
• Extra pipeline stages mainly come from decomposing memory access, which is time-critical.

Eight-Stage Integer Pipeline

Pipeline Stages

1. IF (Instruction Fetch 1: PC selection and initiation of instruction cache access.
2. IS (Instruction Fetch 2): Completion of instruction cache access.
3. RF (Register Fetch): Instruction decode, register fetch, hazard checking, and instruction cache hit detection.
4. EX (Execute): ALU operations, effective address calculation, and branch condition evaluation.
5. DF (Data Fetch 1): First half of data cache access.
6. DS (Data Fetch 2): Completion of data cache access.
7. TC (Tag Check): Determines whether the data cache access is a hit or miss.
8. WB (Write Back): Writes results to registers.

This diagram illustrates the advanced “Super-Pipelined” structure of the MIPS R4000, which expands the standard processor workflow into eight distinct stages to achieve higher clock speeds. The vertical dashed lines indicate the boundaries between these stages, showing how heavy tasks like memory access are broken down into smaller pieces: instruction fetching is split into an initial fetch (IF) and a second stage (IS), with the final verification happening during the Register Fetch (RF) stage. Similarly, data memory access is pipelined across the DF and DS stages, followed by a specific Tag Check (TC) stage to confirm the cache hit before the data is finally written back to the registers.

Instruction and data caches are fully pipelined, allowing one instruction to start every cycle.

This diagram illustrates the timing of a “load delay” in the R4000 pipeline, specifically showing how data is passed from a Load instruction (LD R1) to a dependent instruction (ADDD). Because the pipeline is deep, the data value from the load is not actually available until the end of the Data Select (DS) stage. The arrow in the diagram demonstrates how this data is immediately bypassed (forwarded) to the ALU stage of the dependent instruction, resulting in a 1-cycle load delay (noted as “x1” in your text) rather than a longer stall. If the subsequent Tag Check (TC) reveals a cache miss, the pipeline would then have to back up to wait for the correct data.

Load and Branch Delays

Load Delays

• Load data becomes available at the end of DS.
• Results in a one-cycle load-use stall (x1) when an instruction immediately uses a load result.
• Forwarding allows use by instructions three or four cycles later.

Branch Delays

This diagram depicts the timing penalty associated with conditional branches in the R4000 pipeline, specifically showing a three-cycle delay. Because the branch condition (BEQZ) is not evaluated until the Execution (EX) stage in the fourth clock cycle, the processor effectively “waits” three cycles before it knows the correct address for the next instruction. Consequently, the target instruction cannot be fetched until clock cycle 5, meaning three other instructions (Instruction 1, 2, and 3) enter the pipeline during this gap while the decision is being made.

• Branch condition is evaluated in EX, creating a three-cycle branch delay.
• MIPS ISA provides a single-cycle delayed branch.
• R4000 uses predict-not-taken for the remaining two cycles.
• Untaken branch: one delay slot.
• Taken branch: one delay slot + two idle cycles.
• Branch-likely instructions help reduce wasted delay slots.
• Later MIPS processors adopted dynamic branch prediction due to these costs.

Forwarding Complexity

• Deeper pipeline increases forwarding paths.
• ALU results may be forwarded from:
• EX/DF
• DF/DS
• DS/TC
• TC/WB
• This is more complex than the two forwarding paths in a 5-stage pipeline.

Floating-Point (FP) Pipeline

FP Functional Units

• FP adder
• FP multiplier
• FP divider
• Adder hardware is reused in multiply and divide final stages.

FP Pipeline Stages

• U: Unpack operands
• S: Shift
• A: Add mantissas
• R: Round
• M, N: Multiply stages
• D: Divide stages
• E: Exception check
• Only one copy of each stage exists.
• Instructions may reuse stages multiple times and in different orders.

FP Operation Characteristics

Latency and Initiation Interval

Latency ranges from:

• 2 cycles (negate, absolute)
• 4 cycles (add/subtract)
• 8 cycles (multiply)
• 36 cycles (divide)
• 112 cycles (square root)

Initiation intervals vary and limit how frequently new FP instructions can issue.

FP Instruction Interactions

• Some instruction pairs issue without stalls (e.g., add → multiply).
• Others stall due to shared stage conflicts (e.g., multiply → add, divide → add).
• Divide operations heavily use shared hardware and cause stalls near completion.

Sources of Pipeline Stalls

Four major contributors:

1. Load stalls — using load results too early
2. Branch stalls — taken branches and unfilled delay slots
3. FP result stalls — RAW hazards due to long FP latencies
4. FP structural stalls — conflicts for FP pipeline stages

Performance Results (SPEC92 Benchmarks)

Integer Programs

• Pipeline CPI ranges roughly 1.2–1.9.
• Branch stalls are the dominant contributor due to long branch delays.

Floating-Point Programs

• Pipeline CPI ranges roughly 2.2–2.8.
• FP result stalls dominate (≈80–85% of stall cycles).
• FP structural stalls are secondary.

Overall Insight

• Deeper pipelines significantly increase branch penalties.
• Long FP latencies cause more performance loss than structural hazards.
• Reducing FP operation latency would improve performance more than adding extra pipelining or functional units.

**Key Takeaways

1. **Superpipelining increases clock speed but worsens load and branch penalties.
2. FP performance is limited mainly by operation latency, not hardware conflicts.
3. The R4000 pipeline design directly motivated widespread adoption of dynamic branch prediction and more advanced execution techniques in later processors.

🔙 Back to all notes 𝕏 Let’s Connect

Backlinks: Computer Architecture — A Quantitative Approach