Pipelining Overview

Overview of Pipelining

• Modifying the sign-extend unit involves expanding the 2:1 multiplexor using opcode bits 31 and 26 to include a 26-bit address
• A value of 01 selects the address for B, 10 for LDUR or STUR, and 11 for CBZ

Single-Cycle Implementation Drawbacks

• Single-cycle designs are inefficient because the clock cycle must accommodate the longest instruction path
• The longest path is typically a load instruction, utilizing five functional units in series
• Despite a CPI of 1, the single-cycle implementation suffers from poor overall performance due to a long clock cycle
• Historically, early computers used this technique with simple instruction sets
• Implementing floating-point units or complex instructions makes the single-cycle design impractical
• Single-cycle implementations violate the principle of optimizing for the common case, as the clock cycle is determined by the worst-case delay
• Pipelining is an implementation technique that uses a similar datapath to the single-cycle approach but achieves higher throughput by executing multiple instructions simultaneously

Pipelining Explained

• Pipelining is an implementation method where multiple instructions are executed concurrently
• Pipelining is now a widely used technique
• Understanding pipelining can be achieved by using an analogy
• Instruction execution in LEGv8 processors typically involves five steps:
• Fetch instruction from memory
• Read registers and decode the instruction
• Execute the operation or calculate an address
• Access an operand in data memory (if necessary)
• Write the result into a register (if necessary)
• The LEGv8 pipeline consists of five stages
• Pipelining speeds up instruction execution

Single-Cycle vs Pipelined Performance

• Instructions under consideration: LDUR, STUR, ADD, SUB, AND, ORR, and CBZ
• Functional unit execution times are 200 ps for memory access, 200 ps for ALU operation, and 100 ps for register file read or write
• Single-cycle implementation requires every instruction to take one clock cycle, sized to the slowest instruction
• The single-cycle design must accommodate the slowest instruction (LDUR) and thus requires 800 ps for every instruction
• Pipelined execution requires each pipeline stage to take a single clock cycle that accommodates the slowest operation
• The pipelined execution clock cycle must have the worst-case clock cycle of 200 ps
• Pipelining offers a fourfold performance improvement; time between first and fourth instruction is 600ps
• Time between instructions, assuming ideal conditions is defined as time between nonpipelined instructions divided by number of pipe stages
• The formula suggests that a five-stage pipeline can achieve nearly a fivefold improvement over the non-pipelined time of 800 ps, resulting in a 160 ps clock cycle
• Real-world performance shows that the stages may be imperfectly balanced and pipelining involves overhead, resulting in a lower speed-up versus the number of stages
• Pipelining improves performance by increasing throughput, not by decreasing the execution time of an individual instruction

Pipelining Instruction Set Design

• In LEGv8, all instructions are the same length, simplifying fetching and decoding
• The x86 architecture translates x86 instructions into simpler operations to facilitate pipelining
• LEGv8 uses few instruction formats, with consistent placement of source and destination register fields
• Operands are in memory for load/store instructions in LEGv8 code
• Memory address calculation uses the execute stage
• Memory access occurs in the following stage

Pipeline Hazards

• Hazards are defined as situations where the next instruction cannot execute in the following clock cycle
• Three types of such hazards are possible

Structural Hazards

• A structural hazard occurs when hardware cannot support the combination of instructions needed in the same clock cycle

Data Hazards

• Data hazards necessitate pipeline stalls because one step depends on the completion of another
• Without intervention, dependencies can stall the pipeline
• A solution involves forwarding or bypassing, using extra hardware to retrieve missing data early from internal resources

Forwarding

• Forwarding connects pipeline stages is to resolve data hazards
• Forwarding paths are only valid if the destination stage occurs later

Pipeline Stalls

• Pipeline stalls, or bubbles, occur when data is unavailable
• Reordering code can potentially avoid pipeline stalls

Reordering Code

• Assembly language programmers can reorder the instructions to get the branch behavior desired
• Branch delays are rare in processors if they span more than one cycle
• Hardware-based branch prediction is best in these scenarios

Control Hazards

• A control hazard arises when a decision depends on the results of an instruction while others are executing
• Stalling: operate sequentially until the first batch is dry and then repeat until you have the right formula
• Prediction: predict that formula works and wash the second load while waiting for the first load to dry

Branch Prediction

• Under branch prediction, the pipeline proceeds at full speed when branches are untaken, or until there is a conditional branch
• Dynamic hardware predictors make guesses depending on the behavior of each conditional branch and may change predictions
• Dynamic branch predictors can correctly predict conditional branches with high accuracy
• When the guess is wrong, the pipeline control must ensure that the instructions following the wrongly guessed conditional branch have no effect and must restart the pipeline

Pipeline Overview Summary

• Pipelining exploits parallelism between instructions in a sequential stream, invisible to the programmer
• Structural, data, and control hazards remain important in both simple and sophisticated pipelines
• For modern pipelines, structural hazards involve the floating-point unit
• Integer programs see control hazards
• Branches are conditional, branch frequently, and are less predictable
• Data hazards often involve floating point units, which may require long delays