Pipelining and Vector Processing
Open in the Padhaiko app6.1 Pipelining and its importance
Pipelining
Pipelining is an implementation technique in which a sequential task is decomposed into independent sub-operations (stages), each handled by a dedicated hardware segment separated by inter-stage latch registers, so multiple tasks overlap in execution simultaneously—analogous to an industrial assembly line.
- Why Pipelining Matters: While pipelining does not reduce the latency of a single isolated task (in fact, inter-stage latch delay slightly increases it), it dramatically boosts instruction throughput (completions per second) and keeps all CPU functional units busy on every clock tick.
- Ideal Speedup & Throughput: Consider executing tasks through a -stage pipeline where each stage takes clock cycle time (compared to for a non-pipelined unit):
If , the speedup is:
As , throughput approaches result per clock cycle and speedup approaches the number of pipeline stages .
6.2 Instruction and arithmetic pipelining
Arithmetic Pipelining
Arithmetic pipelining divides a multi-step arithmetic operation (most notably floating-point addition/subtraction or multiplication) into sequential hardware stages so a stream of vector/array operands flows through at one result per clock cycle:
- Example 4-stage floating-point adder pipeline:
- Stage 1 (
Compare): Compare exponents (). - Stage 2 (
Align): Shift the smaller-exponent mantissa right to align binary points. - Stage 3 (
Add/Sub): Add or subtract aligned mantissas. - Stage 4 (
Normalize): Shift result and adjust exponent to restore normalized1.Fform.
- Stage 1 (
Instruction Pipelining
Instruction pipelining overlaps the execution phases of consecutive machine instructions—commonly modeled as a 4-stage (FI, DA, FO, EX) or classical 5-stage pipeline (IF, ID, EX, MEM, WB):
- IF (Instruction Fetch): Read instruction from instruction cache at
PC; incrementPC. - ID (Instruction Decode / Register Fetch): Decode opcode and read source operands from the register file.
- EX (Execute / Address Calculation): Perform ALU operation or compute memory effective address (
Base + Offset). - MEM (Memory Access): Read/write data cache for
LOAD/STOREinstructions. - WB (Write Back): Write ALU or loaded memory result back to destination register.
6.3 Pipelining hazards: Data, structural and control hazards
A pipeline hazard is any condition that prevents the next instruction in the instruction stream from executing in its designated clock cycle, forcing a pipeline stall (bubble) that lowers throughput.
| Hazard Type | Cause | Example | Resolution / Mitigation |
|---|---|---|---|
| Structural Hazard | Two instructions simultaneously need the same hardware resource | Single unified memory accessed by IF and MEM in the same cycle | Split L1-I and L1-D caches; duplicate functional units; insert stall cycles |
| Data Hazard | An instruction depends on the result of a previous in-flight instruction not yet written back | ADD R1, R2, R3 followed immediately by SUB R4, R1, R5 (RAW dependence) | Operand forwarding (bypassing) from EX/MEM or MEM/WB latches directly to ALU inputs; compiler instruction scheduling; hardware interlock/stall |
| Control (Branch) Hazard | Fetching the next instruction before a branch's outcome and target address are known | BEQ R1, R2, TARGET followed by sequential instructions | Branch prediction (static/dynamic BTB); delayed branch (fill delay slot); early branch resolution in ID; flush wrong-path instructions |
Data hazards are further classified by read/write order: RAW (Read After Write — true dependence), WAR (Write After Read — anti-dependence), and WAW (Write After Write — output dependence).
6.4 RISC pipeline
RISC architectures (fixed-length 32-bit instructions, register-to-register ALU ops, only LOAD/STORE accessing memory) are engineered specifically for smooth 5-stage integer pipelining (IF, ID, EX, MEM, WB) with minimal stalls:
- Load-Use Hazard & Delay Slot: A
LOAD R1, 0(R2)producesR1only at the end ofMEM, whereas a followingADD R3, R1, R4needsR1at the start ofEX—requiring a 1-cycle stall (or a compiler-scheduled independent instruction in the load delay slot). - Delayed Branch: The instruction immediately following a branch (branch delay slot) always executes regardless of whether the branch is taken, allowing compilers to place a useful pre-branch instruction there instead of wasting a pipeline bubble.
6.5 Parallel processing
Parallel processing achieves higher throughput by performing simultaneous data processing across multiple functional units, pipelines, or processors. Flynn's Classification categorizes computer architectures by the multiplicity of instruction streams and data streams:
| Class | Full Name | Structure & Execution | Representative Examples |
|---|---|---|---|
| SISD | Single Instruction, Single Data | One control unit fetches one instruction stream acting on one data stream | Classical uniprocessor (even if pipelined) |
| SIMD | Single Instruction, Multiple Data | One control unit broadcasts the same instruction to many processing elements operating on distinct data | Vector processors, GPU warps, AVX/NEON SIMD units, attached array processors |
| MISD | Multiple Instruction, Single Data | Multiple instruction streams process a single shared data stream | Specialized fault-tolerant / systolic filters (rare commercially) |
| MIMD | Multiple Instruction, Multiple Data | Autonomous processors execute independent instruction streams on independent data | Multi-core CPUs, SMP servers, distributed clusters |
6.6 Vector processing
Scientific simulations, weather forecasting, finite-element analysis, and matrix algebra apply identical operations across huge arrays of numbers (vectors). Vector processors add dedicated vector registers (each holding e.g. floating-point elements), vector instructions (e.g., VADD V1, V2, V3), and deeply pipelined arithmetic units.
6.6.1 Vector operations
A single vector instruction replaces an entire scalar loop (for i = 0..63: C[i] = A[i] + B[i]):
- Eliminates per-iteration loop counter updates, branch prediction overhead, and instruction-fetch bottlenecks.
- Supports vector chaining: the output stream of one vector pipeline (e.g.,
VMUL) feeds directly into the input of a second vector pipeline (e.g.,VADD) without waiting for the entire vector writeback.
6.6.2 Matrix multiplication
Multiplying two matrices computes . On a vector processor:
- An inner product accumulates products using a pipelined multiplier feeding a pipelined adder (multiply-accumulate chain).
- Vectorizing over rows/columns (SAXPY form: ) exploits stride-1 unit memory access and vector chaining to sustain near-peak FLOPS.
6.6.3 Memory interleaving
A single DRAM bank cannot deliver one word per CPU clock cycle to feed a vector pipeline. Memory interleaving partitions main memory into independent memory modules (banks) that can operate concurrently:
- Low-Order Interleaving: The least significant address bits select the module, and the upper bits select the word within that module. Consecutive memory addresses (
0, 1, 2, 3, ...) sit in different modules, allowing all modules to be accessed in overlapped (pipelined) fashion to sustain one word per clock cycle for sequential vector streams. - High-Order Interleaving: Upper address bits select the module (simpler expansion and fault isolation, but consecutive addresses hit the same bank and cannot overlap).
6.6.4 Superscalar processors
A superscalar processor fetches, decodes, and dispatches multiple independent instructions per clock cycle (e.g., 2–6 instructions/cycle) to multiple parallel execution pipelines (multiple ALUs, FPUs, load/store units):
- Hardware dynamically checks register dependencies and issues non-conflicting instructions (out-of-order execution with in-order commit via a reorder buffer) to achieve CPI (equivalently IPC ).
6.6.5 Supercomputers
Supercomputers achieve extreme floating-point throughput (petaflops to exaflops, measured on LINPACK benchmarks) by combining thousands of multi-core superscalar CPUs, vector/GPU accelerators, high-bandwidth interleaved memory, and ultra-low-latency interconnection networks—historically pioneered by vector supercomputers (Cray-1) and today dominated by massively parallel MIMD + SIMD heterogeneous clusters.
6.7 Array processors: Attached array processor and SIMD array processor
An array processor executes vector/matrix computations across a regular array of Processing Elements (PEs):
| Aspect | Attached Array Processor | SIMD Array Processor |
|---|---|---|
| System Role | Auxiliary co-processor attached via I/O or system bus to a general-purpose host computer | Standalone computer featuring a master Control Unit (CU) and an array of synchronized Processing Elements (PEs) |
| Internal Architecture | High-speed pipelined floating-point ALU + local vector memory | Each PE has its own ALU, registers, and local memory, interconnected via a routing network (e.g., 2D mesh) |
| Operation | Host offloads large matrix/FFT routines; array processor streams vectors through internal arithmetic pipes | Master CU decodes one instruction and broadcasts control signals simultaneously to all active PEs (lockstep SIMD) |
| Conditionals | Handled via vector mask bits | Each PE uses a local mask flag to enable or disable execution on conditional branches |
Worked Out Examples
1
A non-pipelined processor executes each instruction in sequential phases taking each (total per instruction). Converting this processor into a -stage pipeline adds zero latch overhead, keeping the pipeline clock cycle at .
- Find the total execution time and speedup over the non-pipelined processor for independent instructions.
- Repeat for instructions, and find the ideal maximum throughput in MIPS.
Computing execution times and speedup for instructions: With stages and :
Computing execution times, speedup for , and ideal throughput:
As , the pipeline completes instruction every :
- For : , Speedup . 2. For : , Speedup ; ideal maximum throughput .
2
Analyze data hazards in the following 5-stage (IF, ID, EX, MEM, WB) RISC instruction sequence:
I1: LW R1, 0(R2)
I2: ADD R3, R1, R4
I3: SUB R5, R3, R6
I4: OR R7, R3, R8- Identify all RAW data hazards in this sequence.
- Determine how many stall cycles (
bubbles) are needed without forwarding versus with full ALU forwarding (EX/MEMandMEM/WBbypass paths).
Identifying RAW dependencies:
I1 -> I2onR1(I2readsR1written byLW).I2 -> I3onR3(I3readsR3written byADD).I2 -> I4onR3(I4readsR3written byADD).
Counting stalls without vs. with forwarding:
- Without forwarding (assuming register file writes in first half of
WBand reads in second half ofID):I2must wait inIDuntilI1finishesWB: 2 stall cycles.I3must wait inIDuntilI2finishesWB: 2 stall cycles.I4readsR3afterI2has already completedWB: 0 extra stalls.- Total without forwarding stall cycles (completing in cycles).
- With full forwarding:
I1 -> I2(load-use):I2needsR1atEXstart, whileI1finishesMEMone cycle later 1 stall cycle (forwarded fromMEM/WB).I2 -> I3(ALU-ALU):I2forwardsR3fromEX/MEMtoI3'sEXinput 0 stalls.I2 -> I4(ALU-ALU):I2forwardsR3fromMEM/WBtoI4'sEXinput 0 stalls.- Total with forwarding stall cycle (completing in cycles).
- RAW hazards exist on
R1(I1 -> I2) andR3(I2 -> I3,I2 -> I4). 2. Without forwarding: stall cycles ( cycles total); with full forwarding: load-use stall cycle ( cycles total).
3
A vector processor uses -way low-order memory interleaving where each memory module has a -word capacity and a memory cycle time of CPU clock cycles.
- For a -word memory space, how many address bits select the module and how many select the word within the module?
- How many clock cycles are needed to read a contiguous vector of words, and what is the sustained transfer rate (words per clock cycle) for a long contiguous vector of words once the memory pipeline is full?
Mapping address bits for 8-way low-order interleaving:
- Total words words (-bit address).
- With modules, the lowest address bits (
A[2:0]) select the module (0..7). - The upper address bits (
A[12:3]) select the word inside the module (0..1023).
Computing cycle count and sustained bandwidth: Because consecutive addresses fall into modules in round-robin order, the CPU initiates one module read every clock cycle:
- Reading consecutive words overlaps all modules: module returns at cycle , module at cycle , , module at cycle cycles.
- Once the initial -cycle latency passes, 1 word arrives every clock cycle, so words complete in cycles ( word/cycle sustained, the single-bank bandwidth).
- Lowest bits select the module; upper bits select the word within the module. 2. An -word vector completes in clock cycles, and sustained bandwidth approaches word per clock cycle.
Exercises
Exercise — Pipelining and Vector Processing
Define pipelining and derive the speedup equation for executing tasks in a -stage pipeline with stage time . A -stage arithmetic pipeline has stage delay . Calculate the time required to add pairs of floating-point numbers and the speedup relative to a non-pipelined adder taking per addition.
Deriving the pipeline speedup formula:
- Non-pipelined time for tasks of steps of duration : .
- Pipelined time: the first task finishes after , and each of the remaining tasks finishes every : .
- Speedup: .
Evaluating for , , :
Pipelined execution time (vs. non-pipelined), giving a speedup of .
Explain the three classes of pipeline hazards—structural, data, and control—and describe one hardware and one compiler/software technique to mitigate data and control hazards in a RISC pipeline.
Explaining the three pipeline hazards:
- Structural Hazard: Hardware resource conflict when two instructions need the same unit (e.g., single memory port) simultaneously. Mitigated by split L1-I/L1-D caches or replicated hardware.
- Data Hazard: Instruction depends on data still being computed by an earlier in-flight instruction (RAW, WAR, WAW).
- Control Hazard: Uncertainty about which instruction to fetch next until a branch direction/target resolves.
Hardware and software mitigations:
- Data Hazards: Hardware operand forwarding (bypassing) routes ALU/MEM outputs directly back to ALU inputs without waiting for
WB; software instruction scheduling reorders independent instructions between producer and consumer (filling load delay slots). - Control Hazards: Hardware dynamic branch prediction (branch target buffer / 2-bit predictors) speculatively fetches the predicted path; software delayed branching places a safe independent instruction in the branch delay slot.
Structural hazards stem from resource conflicts, data hazards from operand dependencies, and control hazards from branches. Hardware uses forwarding and branch predictors; compilers schedule independent instructions into load and branch delay slots.
State Flynn's classification of computer architectures (SISD, SIMD, MISD, MIMD) and classify a multi-core processor, a GPU/vector array, and a classic single-core pipelined CPU under Flynn's taxonomy.
Summarizing Flynn's four categories:
- SISD: Single instruction stream operating on a single data stream (classic single-core CPU—pipelining overlaps one instruction stream, so it remains SISD).
- SIMD: One instruction stream broadcasted to multiple processing elements acting on multiple data items (vector processors, SIMD array processors, GPU vector units).
- MISD: Multiple instruction streams operating on one shared data stream (theoretical/systolic specialty systems).
- MIMD: Multiple autonomous processors executing independent instruction streams on separate data streams (multi-core CPUs, multiprocessors).
Flynn's taxonomy divides systems into SISD (single-core pipelined CPU), SIMD (vector/GPU array), MISD (specialized systolic), and MIMD (multi-core CPU).
Distinguish between low-order and high-order memory interleaving, and explain why vector processors and superscalar CPUs benefit from low-order interleaving and vector chaining.
Comparing low-order and high-order interleaving:
- Low-Order Interleaving: Lower address bits pick the memory bank, scattering sequential addresses (
0, 1, 2, ...) across all banks so sequential vector loads/stores overlap concurrently and deliver up to word/cycle. - High-Order Interleaving: Upper address bits pick the bank, placing contiguous addresses inside one bank—easy to expand memory modules, but sequential array accesses serialize on one bank.
Explaining vector chaining and superscalar parallelism:
- Vector Chaining: Connects the output of one vector functional pipeline directly to the input of the next (e.g.,
VMULVADDin matrix dot products), executing both operations overlapped instead of waiting for vector register writeback. - Superscalar CPUs: Issue multiple independent scalar instructions per clock cycle to parallel execution pipelines (IPC ), demanding high sustained memory bandwidth supported by interleaved banks and multi-ported caches.
Low-order interleaving maps sequential words to different banks for concurrent access, whereas high-order interleaving groups contiguous blocks in one bank. Vector chaining overlaps chained vector pipelines, while superscalar CPUs dispatch multiple independent instructions per cycle.
Compare an attached array processor with an SIMD array processor, explaining how conditional branching (if-else) is handled across processing elements (PEs) in an SIMD array.
Comparing attached and SIMD array processors:
- Attached Array Processor: Peripheral co-processor connected to a host computer over I/O/system buses to accelerate vector/matrix kernels using internal pipelined arithmetic units and local vector memory.
- SIMD Array Processor: Standalone parallel architecture with a central Control Unit (
CU) broadcasting a single instruction stream in lockstep to Processing Elements (PEs), each owning an ALU, registers, local memory, and interconnection links.
Handling conditional operations in an SIMD array: Each PE maintains a 1-bit mask (activity) flag. On a conditional test (if A[i] > 0), PEs satisfying the condition keep their mask bit set (1) and execute the then instructions, while failing PEs mask themselves off (0) and sit idle; then the mask bits invert to execute the else branch for the remaining PEs.
An attached array processor acts as a host-driven pipelined vector co-processor, whereas an SIMD array processor broadcasts instructions from one CU to local-memory PEs in lockstep, using per-PE mask bits to execute conditional branches.