PadhaikoAll subjects

Pipelining and Vector Processing

Computer Organization and Architecture (ENCT 303)

Open in the Padhaiko app

6.1 Pipelining and its importance

Definition

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.

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:

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):

  1. IF (Instruction Fetch): Read instruction from instruction cache at PC; increment PC.
  2. ID (Instruction Decode / Register Fetch): Decode opcode and read source operands from the register file.
  3. EX (Execute / Address Calculation): Perform ALU operation or compute memory effective address (Base + Offset).
  4. MEM (Memory Access): Read/write data cache for LOAD/STORE instructions.
  5. 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.

Classification of Pipeline Hazards and Mitigation Techniques
Hazard TypeCauseExampleResolution / Mitigation
Structural HazardTwo instructions simultaneously need the same hardware resourceSingle unified memory accessed by IF and MEM in the same cycleSplit L1-I and L1-D caches; duplicate functional units; insert stall cycles
Data HazardAn instruction depends on the result of a previous in-flight instruction not yet written backADD 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) HazardFetching the next instruction before a branch's outcome and target address are knownBEQ R1, R2, TARGET followed by sequential instructionsBranch 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:

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:

Flynn's Classification of Parallel Architectures
ClassFull NameStructure & ExecutionRepresentative Examples
SISDSingle Instruction, Single DataOne control unit fetches one instruction stream acting on one data streamClassical uniprocessor (even if pipelined)
SIMDSingle Instruction, Multiple DataOne control unit broadcasts the same instruction to many processing elements operating on distinct dataVector processors, GPU warps, AVX/NEON SIMD units, attached array processors
MISDMultiple Instruction, Single DataMultiple instruction streams process a single shared data streamSpecialized fault-tolerant / systolic filters (rare commercially)
MIMDMultiple Instruction, Multiple DataAutonomous processors execute independent instruction streams on independent dataMulti-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]):

6.6.2 Matrix multiplication

Multiplying two matrices computes . On a vector processor:

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:

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):

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):

AspectAttached Array ProcessorSIMD Array Processor
System RoleAuxiliary co-processor attached via I/O or system bus to a general-purpose host computerStandalone computer featuring a master Control Unit (CU) and an array of synchronized Processing Elements (PEs)
Internal ArchitectureHigh-speed pipelined floating-point ALU + local vector memoryEach PE has its own ALU, registers, and local memory, interconnected via a routing network (e.g., 2D mesh)
OperationHost offloads large matrix/FFT routines; array processor streams vectors through internal arithmetic pipesMaster CU decodes one instruction and broadcasts control signals simultaneously to all active PEs (lockstep SIMD)
ConditionalsHandled via vector mask bitsEach PE uses a local mask flag to enable or disable execution on conditional branches

Worked Out Examples

Example 1

1 (6 marks)

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 .

  1. Find the total execution time and speedup over the non-pipelined processor for independent instructions.
  2. 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 :

Answer:
  1. For : , Speedup . 2. For : , Speedup ; ideal maximum throughput .
Example 2

2 (6 marks)

Analyze data hazards in the following 5-stage (IF, ID, EX, MEM, WB) RISC instruction sequence:

Text
I1: LW   R1, 0(R2)
I2: ADD  R3, R1, R4
I3: SUB  R5, R3, R6
I4: OR   R7, R3, R8
  1. Identify all RAW data hazards in this sequence.
  2. Determine how many stall cycles (bubbles) are needed without forwarding versus with full ALU forwarding (EX/MEM and MEM/WB bypass paths).

Identifying RAW dependencies:

  • I1 -> I2 on R1 (I2 reads R1 written by LW).
  • I2 -> I3 on R3 (I3 reads R3 written by ADD).
  • I2 -> I4 on R3 (I4 reads R3 written by ADD).

Counting stalls without vs. with forwarding:

  • Without forwarding (assuming register file writes in first half of WB and reads in second half of ID):
    • I2 must wait in ID until I1 finishes WB: 2 stall cycles.
    • I3 must wait in ID until I2 finishes WB: 2 stall cycles.
    • I4 reads R3 after I2 has already completed WB: 0 extra stalls.
    • Total without forwarding stall cycles (completing in cycles).
  • With full forwarding:
    • I1 -> I2 (load-use): I2 needs R1 at EX start, while I1 finishes MEM one cycle later 1 stall cycle (forwarded from MEM/WB).
    • I2 -> I3 (ALU-ALU): I2 forwards R3 from EX/MEM to I3's EX input 0 stalls.
    • I2 -> I4 (ALU-ALU): I2 forwards R3 from MEM/WB to I4's EX input 0 stalls.
    • Total with forwarding stall cycle (completing in cycles).
Answer:
  1. RAW hazards exist on R1 (I1 -> I2) and R3 (I2 -> I3, I2 -> I4). 2. Without forwarding: stall cycles ( cycles total); with full forwarding: load-use stall cycle ( cycles total).
Example 3

3 (5 marks)

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.

  1. For a -word memory space, how many address bits select the module and how many select the word within the module?
  2. 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).
Answer:
  1. 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

Question 1

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 , , :

Answer:

Pipelined execution time (vs. non-pipelined), giving a speedup of .

Question 2

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.
Answer:

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.

Question 3

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).
Answer:

Flynn's taxonomy divides systems into SISD (single-core pipelined CPU), SIMD (vector/GPU array), MISD (specialized systolic), and MIMD (multi-core CPU).

Question 4

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., VMUL VADD in 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.
Answer:

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.

Question 5

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.

Answer:

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.

← Computer ArithmeticInput/Output →