Pipelining Study Notes

Appendix C: Pipelining - Basic and Intermediate Concepts

What is Pipelining?

• Pipelining is a technique used in computer architecture to improve the throughput of instruction execution.

  • Analogous to a car assembly plant where multiple stations work simultaneously to produce a car every few minutes despite it taking hours to assemble a single car. Each station adds parts to the chassis successively.

• In Instruction Set Architecture (ISA), every instruction involves multiple steps such as:

  • Fetch the instruction from memory.

  • Decode the instruction.

  • Fetch data from registers.

  • Form effective memory addresses for data in memory.

  • Execute the instruction.

  • Transfer data to/from memory.

  • Write data to registers.

• Each of these steps consumes one or more clock cycles.

• To enhance performance, it is possible to collapse these seven steps into five stages of execution.

Register File I/O

• The register file is the architecture component containing the processor's registers.

  • Each register can be accessed for read or write by specifying its register number (address).

  • For example, with 32 registers (x0 to x31), each can be addressed with 5 bits, ranging from 00000 to 11111.

• Register File I/O structure includes:

  • One (1) input to write data into a register.

  • Two (2) outputs for carrying contents of specified registers.

• Question Raised: Why limit to one input and two outputs?

Functions by Instruction Type

• Example of an integer RISC-V code segment:

  • lw x1, 104(x0); - load B into x1

  • addw x3, x1, x1; - A = B + B

  • sw x3, 100(x0); - store A from x3

  • beq x3, x0, 8; - if A = 0, branch taken

  • addiw x1, x0, 2; - if branch not taken, B = 2

  • jal x4, 4; - jump; Reg[x4] <- PC + 4, PC <- PC + OFFSET

  • addiw x1, x0, 1; - if branch taken, B = 1

  • sw x1, 104(x0);

Instruction Execution Pipeline (Stages):

• Load: Fetch, Decode, Read Registers, Compute, Access Memory, Write Registers.

• Store: Fetch, Decode, Read Registers, Compute, Access Memory, Write Registers.

• Add/Subtract: Fetch, Decode, Read Registers, Compute, Access Memory, Write Register.

• Conditional Branch: Fetch, Decode, Read Registers, Compute.

• Unconditional Branch: Fetch, Decode, Read Registers.

Five Pipeline Stages of RISC-V

• IF (Instruction Fetch): Fetch instruction from memory, update Program Counter (PC).

• ID (Instruction Decode): Decode instruction, fetch register values, detect if it is a branch instruction or jump, compute possible branch target address.

• EX (Execute): ALU operations, compute memory address, test branch condition, update PC if necessary.

• MEM (Memory Access): Read or write memory operand.

• WB (Write Back): Write ALU result or memory load operand into destination register.

Pipeline Structure

• The pipeline can be envisioned as a series of data paths shifted over time, creating overlap among execution stages.

• The register file serves to provide inputs in the ID stage and act as a destination in the WB stage, with clear rules governing how and when data is read and written.

Pipeline Latches

• Pipeline latches (or registers) are essential components for temporarily holding instructions, operands, register indices, Next Program Counter (NPC), etc., between pipeline stages.

• Each latch is labeled based on the stages it separates:

  • IF/ID latch: between IF and ID stages.

  • ID/EX latch: between ID and EX stages.

  • EX/MEM latch: between EX and MEM stages.

  • MEM/WB latch: between MEM and WB stages.

Pipeline Performance

Example 1: Performance with Pipelining

• Timing calculations for pipeline stages:

  • IF stage: 10 ns

  • ID stage: 8 ns

  • EX stage: 10 ns

  • MEM stage: 10 ns

  • WB stage: 4 ns

• Execution time through the longest stage results in:

  • Total time per instruction with overhead from latches = 10 ns + 2 ns = 12 ns.

• Pipelines execute instructions at a rate of:
  $ext{MIPS} = rac{1000 ext{ ms}}{12 ext{ ns}} ext{ which is approximately } 83.33 ext{ MIPS}.$

• Clock Cycles per Instruction (CPI) in this configuration = 1.

Example 2: Performance Without Pipelining

• Assuming all stages combined without pipelining do the following:

  • Execution times: 10 ns (IF) + 8 ns (ID) + 10 ns (EX) + 10 ns (MEM) + 4 ns (WB).

  • Total time for an instruction is: $10 + 8 + 10 + 10 + 4 = 42 ext{ ns}.$

• In this case, machine instructions execute at:
  $ext{MIPS} = rac{1000 ext{ ms}}{42 ext{ ns}} ext{ yielding about } 23.81 ext{ MIPS}.$

• Speedup حاصل from pipelining calculated as:
  $ext{Speedup} = rac{83.33}{23.81} ext{ resulting in approximately } 3.45.$

Pipeline Hazards

• Pipeline hazards occur when successive instructions cannot be completed as planned due to resource conflicts or inefficiencies in reading/writing data.

  • Types of hazards include:

  • Structural Hazards: Occur when two stages try to use the same hardware resource simultaneously.

  • Data Hazards: Often happen when the order of read/write operations for a variable is disrupted.

  • Control Hazards: Arise when instruction execution alters the normal sequence of PC incrementing.

• Hazards can be corrected by stalling instructions in the pipeline, also known as introducing a pipeline bubble.

Solutions to Hazards

Memory Structural Hazard Solution

• Structural hazards due to simultaneous instruction fetch and data access can be mitigated by separating instruction memory (IM) from data memory (DM).

• Implementing caches or instruction buffers also contributes to preventing structural hazards.

Data Hazards

• To manage data hazards effectively, techniques may include:

  • WB Split Cycle: Allow read & write operations in the same cycle, thus simplifying Write Back as it's simple and fast.

  • Forwarding Paths: Technique where results from the EX/MEM or MEM/WB stages are directly fed into subsequent EX stages to eliminate hazards.

  • Notably, forwarding does not fully address data hazards when load instructions are involved.

Load Delays

• Load Delay: The instruction immediately following a load must be stalled if it uses the memory operand in the ALU.

• Load delays result in CPI increases.

  • Example: If 30% of instructions are loads and half of those are followed by instructions that require the loaded operand, the resultant CPI = $1 + 0.30 * 0.50 = 1.15$, representing a 15% increase.

• One remedy for load delays is re-arranging code with compiler intervention.

Compiler Re-arrangement and Optimizations

• By restructuring code, compilers can simplify execution paths, alleviate load delays and thus enhance performance.

  • Example:

  1. Original code:

     • a := b + c;

     • d := e - f;

  2. RISC-V-like optimized code:

     • ld xb, b

     • ld xc, c

     • ld xe, e

     • ld xf, f

     • add xa, xb, xc

     • sd xa, a

     • Further operations…

• Resulting in a configuration that minimizes or completely avoids load delays.

Time Diagrams Example

• Sequential instructions can be represented in time diagrams to illustrate cycles of execution across different configurations, noting the importance of forwarding paths and memory access separation for improving CPI metrics.

Control Hazards

1. Control Hazards: Inform when PC fetches instructions ahead of branches and other control flow instructions.

   • Example: A branch instruction impacts subsequent instruction execution and PC update, possibly requiring stalls or flushes of the pipeline.

2. Solutions to Control Hazards: Include immediate branching decisions made during the instruction fetch or analysis stage, ensuring correction of erroneous paths.

Reducing Branch Penalty

• Branch penalties can be heavy, especially in loops.

• Utilizing delay slots, predicting branch outcomes, and compiler scheduling can significantly minimize performance hits caused by branches.

• Techniques involve both static (compiler-driven) and dynamic (hardware-driven) scheduling to optimize overall throughput.