COMPUTER ORGANIZATION & ARCHITECTURE

Answer: (iii) Consists of both sequential and combinational circuit

Explanation: A pipeline stage typically contains combinational logic (ALU, adder) to perform operation and sequential elements (pipeline registers/latches) to hold intermediate results between stages and synchronize with clock. Hence it is not purely sequential or purely combinational.

Answer: (iv) All of these

Explanation:
Pipeline performance (Ideal CPI=1) degrades due to:

1. Different stage delays: Clock period is set by slowest stage; faster stages idle => loss of efficiency. Unequal delays create bottlenecks/bubbles.
2. Consecutive instruction dependency (Data hazard): RAW/WAR/WAW dependencies force stalls or forwarding.
3. Shared hardware resources (Structural hazard): e.g., single memory for instruction & data, single ALU; simultaneous use by two stages causes conflict/stall.

All three cause pipeline stalls/NOPs, reducing speedup < number of stages. Hence (iv).

Answer: b) Control hazards

Explanation:

• Control hazard occurs due to branch instructions (conditional/unconditional) where next PC is unknown until decode/execute; pipeline must stall/flush.
• Branch prediction predicts taken/not-taken and target address to fetch next instruction speculatively, reducing stalls/flushes.
• Data hazards are handled by forwarding/bypassing, stalling, instruction scheduling.
• Structural hazards handled by resource duplication/pipelining.

Hence branch prediction primarily reduces control hazards.

Answer: (iii) MISD

Explanation (Flynn's taxonomy):

• SISD - Single Instruction Single Data - conventional von Neumann uni-processor - widely used.
• SIMD - Single Instruction Multiple Data - vector/array processors, GPUs - widely used.
• MIMD - Multiple Instruction Multiple Data - multicore, multiprocessor, distributed systems - widely used.
• MISD - Multiple Instruction Single Data - multiple processors execute different instructions on same data stream - no practical commercial implementation; considered impractical/theoretical only (some argue systolic array is near example but not pure MISD).

Hence MISD has no practical usage.

Answer: b) Instruction scheduling

Explanation:

• Data hazards (RAW, etc.) handled by:
  • Data forwarding/bypassing
  • Instruction scheduling / reordering (compiler or hardware - out-of-order execution) to insert independent instructions between dependent ones
  • Stalling (NOP insertion)
• Increasing memory size, parallel processing, or clock speed do not resolve data dependencies.

Hence among options, Instruction scheduling is the technique.

Answer: (ii) Structural hazard

Explanation:

• Structural hazard: Stall due to hardware resource unavailability, e.g., memory port conflict where instruction fetch and data access need same memory, or insufficient ALUs. Unavailability of instruction (I-cache miss / memory contention) falls under this.
• Control hazard: Due to branches.
• Data hazard: Due to operand dependency.

Some texts specifically call "instruction hazard" as subtype of structural hazard.

Answer: (i) data hazard

Explanation:

• Data hazard: Operand/data not yet available/computed by previous instruction (RAW - Read After Write) when needed, causing stall.
• Structural hazard: Hardware resource conflict (e.g., same memory port used by two stages).
• Control hazard: Due to branch/jump altering PC.
• Stock/deadlock are not pipeline hazard terms (stock is typo for stall).

Hence unavailable operand = data hazard.

Correct option: (i) High-speed memory at fetch stage (Loop Buffer)

Loop buffer is a small, very high-speed memory at the instruction fetch stage that stores recently fetched instruction sequence of a loop. On loop repetition, instructions are fetched directly from buffer instead of main memory/cache, reducing fetch time and memory traffic. Hence answer is (i).

Conflicts/Hazards in Instruction Pipeline: pipeline cannot overlap execution. Three types:

1. Structural Hazard (Resource conflict): Two stages need same hardware resource in same cycle. e.g., single memory for instruction fetch and data access, single ALU. Solved by separate I-cache/D-cache, extra functional units, pipeline stalls.

2. Data Hazard: Next instruction needs data not yet produced by previous instruction. Types: RAW (Read After Write - true dependency), WAR, WAW. Causes stalls/bubbles. Solved by forwarding/bypassing, register renaming, compiler scheduling.

3. Control Hazard (Branch hazard): Due to branch/jump instructions. Pipeline doesn't know next PC until branch resolved, so wrong instructions fetched. Causes flushing. Solved by branch prediction, delayed branch, branch target buffer, prefetch.

All reduce speedup from ideal $k$ to $<k$ and need hazard handling.

Data Hazards (RAW) Definition (2 Marks)

In a pipelined processor, a data hazard occurs when an instruction depends on result of a previous instruction still in pipeline and data is not yet available.

RAW (Read After Write) - True dependence: Most common type.

I1: ADD R1, R2, R3   // R1 ← R2+R3
I2: SUB R4, R1, R5   // needs R1

I2 reads R1 before I1 writes it. If I2 enters ID/EX while I1 still in EX/MEM, it reads stale value — incorrect execution.

Handling: Data forwarding/bypassing from MEM/WB to ALU input, pipeline stalling (bubble/NOP), compiler reordering.

Other types WAW and WAR cause hazards only in out-of-order pipelines.

Answer: (iii) Number of pipeline stages

Explanation:
Ideal pipeline speedup (ignoring hazards and overhead) is:

$$Speedup = \frac{T_{non-pipelined}}{T_{pipelined}} \approx k$$

where $k$ = number of stages, or more precisely for $n$ tasks:

$$S = \frac{n \times k \times t_p}{k \times t_p + (n-1) \times t_p} \approx k \text{ for large } n$$

where $t_p$ = stage delay. Throughput increases because multiple instructions overlap in different stages simultaneously.

• (iii) is correct: More stages → finer subdivision → more instructions overlapped → higher ideal speedup (linear with $k$). Example: 5-stage RISC pipeline ideally gives ~5x speedup.

• Why others are wrong:

  • (i) Number of control units - pipelining uses one control unit with stages, not multiple CUs.
  • (ii) Size of RAM / (iv) Size of cache - affects memory performance, not pipeline speedup directly.

Note: Practical speedup < $k$ due to pipeline hazards (data, control, structural), branch penalties, and latch overhead, so deeper pipeline gives diminishing returns.

Array Processor (Vector Processor):
An array processor is a processor that performs the same operation on multiple data elements simultaneously. It is designed for vector/array computations (matrix operations, image processing, scientific computing). It implements SIMD - Single Instruction Multiple Data architecture (Flynn's taxonomy). Example: ILLIAC-IV, BSP, GPU vector units, Intel AVX.

It consists of a single Control Unit and multiple Processing Elements (PEs)/ALUs working in parallel under common control.

Scalar Processor:
A scalar processor processes one data item at a time per instruction. It executes one instruction on one operand pair sequentially. It implements SISD - Single Instruction Single Data. Example: Conventional Intel 8086, basic RISC core. To process an array of N elements, scalar must loop N times.

Difference - Array vs Scalar (SIMD vs SISD):

Aspect	Array (SIMD)	Scalar (SISD)
Parallelism	Data parallelism, N PEs operate concurrently	No data parallelism, sequential
Instruction	One instruction controls many ALUs	One instruction → one ALU operation
Performance	High throughput for vector tasks, $Speedup \approx N$	Lower for vector tasks, loop overhead
Use	Scientific, MATLAB, ML, graphics	General purpose
Cost/Complexity	Higher hardware, interconnection network needed	Simpler control

In short, array processor exploits DLP to compute C[i]=A[i]+B[i] in one step; scalar needs N iterations.

Pipeline Hazards - Types with Examples (7M)

1. Pipeline Concept
Pipelining overlaps fetch-decode-execute stages of multiple instructions. Ideal speedup = n stages. But dependencies cause hazards → pipeline stalls (bubbles) or flushes, reducing throughput. Clock must also handle slowest stage + latch delay.

2. What is Hazard?
Situation where next instruction cannot execute in its designated clock cycle due to resource / data / control dependency.

3. Three Types (Stallings Classification):

A) Structural Hazard - Resource Conflict

Occurs when hardware resources insufficient to support overlapping execution.

Example: Single memory for instruction + data (Von Neumann). IF stage needs memory to fetch, MEM stage needs memory for load/store at same cycle.

Cycle: 1   2   3   4   5
I1:    IF  ID  EX  MEM WB
I2:         IF  ID  EX  MEM*  <- MEM conflict with I1 MEM
I3:              IF*  ID ...  * structural stall 1 cycle

Solutions: Harvard architecture (separate I-cache/D-cache), separate Instruction & Data memories, multi-port register file, pipelined ALU.

Other example: Single ALU for EX and address calculation.

B) Data Hazard - Data Dependency

Instruction needs data still being computed/ not yet written back.

Classification per register access:

1. RAW (Read After Write) - True dependency - Most common

I1: ADD R1, R2, R3   ; R1 = R2+R3
I2: SUB R4, R1, R5   ; needs R1 -> must wait for WB of I1

If pipelined without forwarding, I2 reads stale R1. With 5-stage pipeline, need 2 stalls or forwarding.

2. WAR (Write After Read) - Anti-dependency (only in out-of-order)

I1: ADD R2, R1, R3   ; reads R1
I2: SUB R1, R4, R5   ; writes R1 - must not overwrite before I1 reads

3. WAW (Write After Write) - Output dependency

I1: ADD R1, R2, R3
I2: SUB R1, R4, R5   ; both write R1 -> order matters

Sub-types by pipeline stage:

• Load-Use Hazard: Load followed by use needs 1 stall even with forwarding.

LW  R1, 0(R2)
ADD R3, R1, R4  ; needs R1 from MEM stage - 1 bubble inserted

• EX-Use Hazard: ALU result forwarded from EX/MEM latch.

Example Timing with Forwarding vs Stall:

Without forwarding:
ADD R1,R2,R3
SUB R4,R1,R5  -> stall 2 cycles

With forwarding (bypass EX->EX):
ADD: IF ID EX MEM WB
SUB:    IF ID --EX-- MEM WB  (forwarded path from EX/MEM to ALU input)

Solutions: Data Forwarding/Bypassing, Register Scoreboarding, Tomasulo, Compiler scheduling (insert NOP), stalls/bubbles.

C) Control Hazard - Branch / Jump Hazard

Due to branches, next PC unknown until decode/execute.

BEQ R1, R2, LABEL  ; branch taken ?
Next instr fetch is speculative -> if taken, fetched instr wrong -> flush

Cycle 1: IF BEQ
Cycle 2: IF next (wrong) | ID BEQ -> branch decoded
Cycle 3: IF next2 | ID next | EX BEQ -> target known -> flush IF,ID

Penalty = 2-3 cycles in simple 5-stage (branch resolved in EX). Modern pipelines predict.

Example: JMP Label, CALL, interrupts.

Solutions:

1. Stall until target known (simple)
2. Branch Prediction - Static (predict not taken) / Dynamic (1-bit, 2-bit saturating counter, BTB)
3. Branch Target Buffer (BTB) + Branch History Table
4. Delayed Branch - Fill delay slot with useful instruction (MIPS)
5. Speculative execution + flush on mispredict
6. Loop unrolling

4. Summary Table

Hazard	Cause	Example	Stall Cycles	Fix
Structural	Lack of HW	One memory	1	Add HW, split cache
RAW Data	Need result	ADD->SUB R1	1-2 (0 with fwd)	Forwarding, NOP
WAR/WAW	Write conflict	Out-of-order only	0 in-order	Renaming
Control	Branch PC unknown	BEQ, JMP	2-3	Predict, BTB, delay slot

5. Performance Impact

Hazard stalls increase CPI:
CPI_pipelined = 1 + stall_cycles_per_instr
Speedup = n / (1 + stalls) * (cycle_unpipelined / cycle_pipelined)

Goal of hazard handling is to keep CPI ~1.

Diagram to draw in exam: 5-stage pipeline (IF-ID-EX-MEM-WB) reservation table showing overlapping and bubble insertion for each hazard type.

Flynn's Classification of Computer Architecture (7M)

Proposed by Michael J. Flynn (1966) - classifies parallel architectures based on number of Instruction streams vs Data streams.

Streams = independent sequence of instructions / data as seen by CPU.

                    Single Data (SD)
                    One data stream
                   ┌─────────────────
                   │
Single Instruction │   SISD
Single instruction │
stream             │   (von Neumann)
                   │
-------------------+---------------------------------
                   │
Multiple Instruction│  MISD
Multiple instruction│ (rare - systolic)
stream             │
                   └─────────────────
                    Multiple Data (MD)
                    Multiple data streams
Actually 2x2 grid:
         ┌─────────────┬──────────────┐
         │  SD         │  MD          │
─────────┼─────────────┼──────────────┤
 SI      │  SISD       │  SIMD        │
─────────┼─────────────┼──────────────┤
 MI      │  MISD       │  MIMD        │
         └─────────────┴──────────────┘

1. SISD - Single Instruction Single Data

One instruction stream, one data stream. Sequential.

• Architecture: Conventional Von Neumann uniprocessor. One CU fetches one instruction, one ALU operates on one data element at a time. (No parallelism)
• Execution: IF -> ID -> EX -> MEM -> WB single thread.
• Example: Intel 8086, 80386 uniprocessor, ARM single-core, IBM 360. Old mainframes.
• Diagram:

  ┌────┐      ┌─────┐      ┌─────┐      ┌─────┐
  │ CU |----->| PU  |----->| MU  |  IS  DS -> Single pipeline
  └────┘      └─────┘      └─────┘
   (IS= Instruction Stream, DS=Data Stream, PU=Processing Unit, MU=Memory)

• Performance: Limited by clock, CPI, pipelining is still SISD (ILP but not classified separately by Flynn). Speedup via pipelining/superscalar still logically SISD.

2. SIMD - Single Instruction Multiple Data

One instruction executed on multiple data elements in parallel (Lockstep). Data parallelism.

• Architecture: One CU broadcasts same instruction to multiple Processing Elements (PEs)/ALUs, each with own data. Requires array of processors + interconnection network (shared memory or mesh).
• Execution: Fetch once, decode once, execute simultaneously on N data:
  for (i=0..N-1) C[i] = A[i] + B[i] single instruction ADD does all.
• Examples:
  • Vector processors: Cray-1, CDC STAR-100, TI ASC
  • Array processors: ILLIAC-IV (64 PEs), CM-2, DAP
  • Modern: GPU warp (SIMT - extension), Intel SSE/AVX (single core SIMD within register), AVX-512 executes 16 floats per instruction, Multimedia extensions MMX.
• Diagram:

          ┌────┐
          │ CU |---- IS (same instruction broadcast) ----+
          └────┘                                         |
      ┌──────┼──────┬───────┐
      v      v      v       v
    ┌────┐┌────┐┌────┐  ┌────┐
    │PE0 ││PE1 ││PE2 │..│PEN │ each PE has own data DS0..DSN
    │ALU ││ALU ││ALU │  │ALU │
    └────┘└────┘└────┘  └────┘
      ↕     ↕     ↕       ↕  Data Memory Module 0..N or interleaved

• Use: Matrix operations, image processing, graphics, scientific loops where same operation applied to large dataset. Excellent speedup for vectorizable code; branch divergence hurts (masking).
• Types: Word-slice vs bit-slice, true array vs vector/pipelined.

3. MISD - Multiple Instruction Single Data

Multiple instruction streams on same single data stream. Rare/ theoretical.

• Architecture: Multiple CUs each with distinct instruction on same data item, pipelined through stages. Data flows through chain of processors.
• Example / Interpretation:
  • Pipeline / Systolic array where data flows X -> PE1 (Op1) -> PE2 (Op2) -> PE3 (Op3) each stage different instruction but same datum stream - e.g., real-time signal processing, fault-tolerant systems with redundant execution for voting (N-version).
  • Carnegie Mellon C.mmp (conceived but no commercial)
  • Some view pipeline within single CPU as MISD-like (IF,ID,EX operate on same instruction stream overlapped) but not true.
• Diagram:

 DS ---->┌────┐    ┌────┐    ┌────┐
         │PE0 │--->│PE1 │--->│PE2 │----> Result
 IS0---->|CU0 | IS1|CU1 | IS2|CU2 |

• Use: Almost no general-purpose machine purely MISD; considered for specialized: multiple frequency filters on same sample stream, cryptographic pipelines.

4. MIMD - Multiple Instruction Multiple Data

Multiple instruction streams, multiple data streams. True parallelism - autonomous processors.

• Architecture: Multiple independent processors (each with own CU+ALU+Memory/Local) work on own instruction & data. Two flavors:
  • Shared Memory (Tightly coupled): SMP (Symmetric Multiprocessors) - bus/cache coherent shared address space. E.g., Multicore CPU (Intel i7 8 cores), Xeon server.
  • Distributed Memory (Loosely coupled): Message-passing - cluster, network of workstations (NOW), supercomputer. E.g., Beowulf cluster, IBM BlueGene, NUMA.
• Execution: MIMD can execute completely independent tasks (MIMD - multiple Programs) or cooperate on single problem (parallel programs) via synchronization (lock, barrier, MPI_Send).
• Examples: Multicore processors, Multiprocessors, Clusters, Grids, Multi-computer (Cray T3D, Intel Paragon).
• Diagram:

  ┌────┐  ┌────┐          ┌────┐  ┌────┐
  │CU0 │->│PE0 │->DS0     │CU1 │->│PE1 │->DS1
  └────┘  └────┘          └────┘  └────┘
     IS0     \ shared/ \     IS1
              Distribution Network (Bus/Crossbar/Network)
  ┌────┐  ┌────┐          ┌────┐  ┌────┐
  │CUN │->│PEN │->DSN  etc.
  └────┘  └────┘

• Use: General-purpose parallel computing - database servers, OS multitasking, HPC. Most flexible; speedup limited by Amdahl's law: Speedup = 1 / (f + (1-f)/N).

Comparison Table

Class	Instr Streams	Data Streams	Parallelism	Examples	Use Case
SISD	1	1	None (sequential)	8086, ARM single	Basic PC
SIMD	1	N	Data parallel	ILLIAC, GPU warp, AVX	Vector/matrix
MISD	N	1	Pipeline on data	Systolic (rare)	Fault tolerance, pipeline
MIMD	N	N	Task parallel	Multicore, Cluster	General parallel

Extended Classifications (Johnson, later): SISD vs pipelines etc., but Flynn remains standard.

For exam: Draw 4 quadrants diagram + small block for each type with CU/PE and arrows.

Flynn's Classification (1966) – based on number of Instruction streams and Data streams

Streams = sequence of instructions / data operated by CPU.

	Single Data (SD)	Multiple Data (MD)
Single Instruction (SI)	SISD	SIMD
Multiple Instruction (MI)	MISD	MIMD

1. SISD – Single Instruction Single Data

• One control unit, one ALU, one data stream. Sequential execution (von Neumann).
• Eg: Uniprocessor 8086, RISC, single-core CPU.
• Instruction: $I_1 \rightarrow D_1$ then $I_2 \rightarrow D_2$ …
• No parallelism. Performance via pipelining.

   CU ---> PU ---> Memory
    1      1      1

2. SIMD – Single Instruction Multiple Data

• One instruction stream broadcast to many processing elements (PEs), each with own data.
• Array / Vector processors, GPU.
• Eg: ILLIAC-IV, Vector supercomputers, MMX/SSE, GPU warps.
• Operation: One opcode ADD executes on vectors $A[0..n]+B[0..n]$ in lockstep.

         CU
          |
   +------+------+------+
   PE     PE     PE     PE
   D1     D2     D3     D4

• Exploits data parallelism, high throughput for multimedia, matrix ops. Requires synchronous control.

3. MISD – Multiple Instruction Single Data

• Many instructions operate on same data stream. Rare / theoretical.
• Eg: Systolic arrays, fault-tolerant systems where same data through different algorithms ($N$-version programming), pipeline MISD interpretation: successive stages apply different operations on same data flowing through.
• No commercial general MISD.

  CU1 ---> PU1 --\
  CU2 ---> PU2 ---> same Data stream (pipelined)
  CU3 ---> PU3 --/

4. MIMD – Multiple Instruction Multiple Data

• Multiple autonomous processors each with own instruction and data stream. Most general, multiprocessors / multicomputers.
• Two subclasses:
  • Tightly coupled / Shared memory (SMP, multi-core): All CPUs share common RAM via bus/crossbar. Eg: Intel i7 quad-core, Xeon.
  • Loosely coupled / Distributed memory (message passing): Each node has private memory, communicates via network. Eg: Clusters, supercomputers (Beowulf).

  CU1->PU1->M1 \
  CU2->PU2->M2 ---> Interconnection Network
  CU3->PU3->M3 /

• Exploits task parallelism, true concurrency, scales (but needs synchronization, coherence).

Summary Table

Type	#CU	#PU	Use	Example	Parallelism
SISD	1	1	General	8086, ARM single	ILP only
SIMD	1	N	Vector	GPU, AVX	Data
MISD	N	1	Special	Systolic, fault-tolerant	Rare
MIMD	N	N	General parallel	Multi-core, Cluster	Task/Data

Extended taxonomies: SPMD (Single Program Multiple Data – subset of MIMD), MPMD. Modern machines are hybrid: MIMD of SIMD cores (multi-core GPU).

Diagram: All 4 types [SISD = single lane, SIMD = single instruction fan-out, MISD = multiple instr single data pipeline, MIMD = multiple independent lanes].

Given Data

Clock $f = 10$ GHz $\Rightarrow T_c = 1/f = 0.1$ ns $= 10^{-10}$ s

Type	CPI$_i$ ($c_i$)	$I_i$
Control	5	5000
Data transfer	4	4000
Floating	2	2000
Integer	1	1000

Total instructions $I = \sum I_i = 5000+4000+2000+1000 = 12000$

Total cycles $C = \sum c_i I_i$

$C = 5000\times5 + 4000\times4 + 2000\times2 + 1000\times1$
$C = 25000 + 16000 + 4000 + 1000 = 46000$ cycles

(a) CPI (Average Clock Cycles per Instruction)

$CPI = \dfrac{C}{I} = \dfrac{46000}{12000} = 3.833... \approx 3.83$ cycles/instr

If weighted: $CPI = \sum (I_i/I)\times c_i = 0.4167\times5 + 0.3333\times4 +0.1667\times2+0.0833\times1 =3.83$

(b) Execution Time

$T_{cpu}= C \times T_c = \dfrac{C}{f}$

$T_{cpu}= \dfrac{46000}{10\times10^9}= 4.6\times10^{-6}$ s $= 4.6 \mu s$

Alternatively $T_{cpu}= I \times CPI \times T_c =12000\times3.833\times0.1ns =4600 ns$

$T_{cpu}=4.6 \mu s$ (if $f=1GHz$, $46 \mu s$)

(c) MIPS Rate

$MIPS = \dfrac{I}{T_{cpu}\times10^6} = \dfrac{f}{CPI\times10^6}$

$MIPS = \dfrac{10\times10^9}{3.833\times10^6}= 2608.7$

$\approx 2609$ MIPS $\approx 2.61\times10^3$ MIPS $=2.61$ BIPS

Check: $MIPS =12000/(4.6\times10^{-6}\times10^6)=12000/4.6=2608.7$

If using MIPS = I/(T in $\mu s$) same result.

Summary: CPI $\approx 3.83$, $T \approx 4.6 \mu s$ at 10GHz ($46 \mu s$ at 1GHz), ~2609 MIPS.

Two Techniques for Enhancing Performance with Multiple Execution Pipelines

Multiple execution pipelines (superscalar / superpipelined architecture) allow Instruction Level Parallelism (ILP) by executing more than one instruction per clock. Two key techniques:

1. Superscalar Execution (Multiple Issue Pipeline)

• Concept: Processor contains $m$ parallel pipelines (e.g., Integer pipe, FP pipe, Load/Store pipe). In each cycle, issue logic fetches and issues $n$ instructions simultaneously ($n$-way superscalar) if no dependencies.
• Hardware required:
  • Multiple functional units: ALU1, ALU2, FPU, Branch unit, Load/Store unit
  • Instruction Fetch & Decode capable of $n$ instructions/cycle
  • Dependency checking / Scoreboarding / Tomasulo algorithm to detect data hazards (RAW, WAR, WAW)
  • Register renaming to remove false dependencies
• Example: 2-way superscalar can issue ADD R1,R2,R3 and MUL R4,R5,R6 together if independent.
• Advantage: Increases throughput ideal CPI $\to 1/n$ (e.g., CPI 0.5 for 2-way). Exploits ILP without compiler support (dynamic).
• Limitation: Complex issue logic, requires out-of-order execution and large window; limited by true dependencies and branches.

2. Superpipelining and Out-of-Order / Speculative Execution (Complementary techniques)

Often paired with superscalar; other major technique is VLIW-like / Superpipelined + Branch Prediction & Speculative Execution (can also be answered as Superpipelining or VLIW).

a) Superpipelining:

• Divides pipeline into many finer stages (e.g., 8-10 stages vs classic 5-stage: IF1, IF2, ID1, ID2, EX1, EX2, WB). Clock period = 1/m of base, so multiple instructions are in different sub-stages of same functional pipe - higher clock rate.
• Combination Superscalar + Superpipelining = Super-speculative processor (e.g., Pentium 4).

b) Out-of-Order Execution + Register Renaming + Speculative/Branch Prediction (essential to keep multiple pipelines busy):

• Multiple pipelines stall on hazards/branches. Solution:
  • Register Renaming: maps architectural registers to larger physical register file to eliminate WAR/WAW, allowing parallel execution.
  • Out-of-Order Execution: Instructions wait in Reservation Stations; execute as soon as operands ready, not program order. ReOrder Buffer (ROB) commits in order.
  • Branch Prediction + Speculative Execution: Predict branch direction (2-bit predictor, BTB) and speculatively execute down predicted path to keep pipelines filled. On mispredict, flush.
  • Dynamic Scheduling: Tomasulo / Scoreboard.

Alternative valid answer - VLIW (Very Long Instruction Word):
Compiler packs $k$ independent operations into one very long instruction word (e.g., 128-256 bit). Hardware is simple (no dependency check), compiler does static scheduling. Example: IA-64/Itanium. Merits: simple hardware; Demerits: poor code density, compiler dependent, binary incompatibility.

Performance gain summary: With $N$ pipelines ideal speedup $\to N$ if hazards avoided. Combination of ** Superscalar (space parallelism) + Superpipelining (time parallelism) + OOO/Speculation/Renaming** yields practical speedup 1.5x-3x per core.

Feature	Superscalar	Superpipeline/VLIW
Parallelism	Space - multiple pipes	Time - finer clocks / compiler-packed
Dependency check	Hardware dynamic	VLIW: Compiler static
Complexity	High hardware	VLIW: simple HW, complex compiler

Pipeline Conflicts (Hazards) and Remedies

Pipeline ideally gives 1 instruction per cycle, but dependencies cause hazards that stall/flush pipeline.

1. Structural Hazards (Resource Conflicts)

• Cause: Two stages need same hardware same cycle. e.g., single memory for IF and MEM stage; single ALU; register file with one write port but two instructions need write.
• Example: 4-stage pipeline with IF and MEM sharing memory -> IF of I4 conflicts with MEM of I1.
• Solutions:
  • Separate Instruction and Data caches (Harvard) / L1 split - simultaneous IF+MEM.
  • Multiple functional units, pipelined units, extra ports on register file.
  • Stall (bubble) - hardware interlock delays one instruction.

2. Data Hazards (Data Dependency)

• RAW - Read After Write (True): ADD R1,R2,R3 ; SUB R4,R1,R5 - second needs R1 before first writes. Classic.
  • Sub-types: distance 1,2 hazards in pipeline.
• WAR - Write After Read and WAW - Write After Write (false dependencies) - occur in OOO / superscalar pipelines due to register reuse.
• Effects: Wrong operand value if pipeline forwards unupdated register.
• Solutions:
  • Data Forwarding / Bypassing: Directly route ALU output to next instruction's ALU input via forwarding path (EX->EX, MEM->EX) - avoids stall for most RAW.
  • Stall / Pipeline Interlock + NOP injection: Compiler/hardware inserts bubble when forwarding insufficient (e.g., Load-Use hazard: LW R1,0(R2) ; ADD R3,R1,R4 - needs one stall because data available after MEM).
  • Register Renaming: Remove WAR/WAW by mapping to physical registers (Tomasulo).
  • Compiler Scheduling: Reorder independent instructions between dependent pair: LW R1; ... independent ... ; USE R1
  • Out-of-Order Execution + Scoreboarding: Execute independent instructions while dependent waits in reservation station.

3. Control Hazards (Branch Hazards)

• Cause: Pipeline doesn't know next PC after Branch/Jump until decode/execute stage. Fetches wrong path.
• Example: BEQ R1,R2, Label - 2-3 instructions after branch already fetched before condition resolved.
• Penalties: Flush 1-3 cycles (branch penalty) ~10-20% performance loss if ~15% branches.
• Solutions:
  • Stall + Flush: On branch detection, freeze IF/ID, flush wrong path once target known (simple, slow).
  • Branch Prediction: Predict taken/not-taken.
    • Static: Predict not-taken or compiler hint.
    • Dynamic: 1-bit / 2-bit saturating counter, Correlated (Gshare), BTB (Branch Target Buffer) to store target. Accuracy 90-95% -> penalty only on mispredict.
  • Delayed Branch (Branch Delay Slot): Architecturally fill slot after branch with useful independent instruction - used in MIPS.
  • Predicated Execution: Convert branch to conditional move CMOV -> no flush.
  • Speculative Execution: Execute predicted path speculatively with ROB, rollback on mispredict.
  • Loop Buffer / Branch Target Cache: Cache branch targets.

Summary Table

Hazard	Cause	Detection	Remedy	Cost
Structural	Resource sharing	Scheduler	Duplicate resources, split cache	Hardware cost
Data RAW	Register dependency	Comparator on RD vs RS	Forwarding + stall if load-use	1 bubble if not forwarded
Control	PC change	Branch logic	Predict, delayed branch, flush	1-3 cycles mispredict penalty

Overall techniques to keep pipeline busy: Forwarding (data), Prediction + Speculation (control), Superscalar OOO + Renaming.

Ideal CPI =1, actual CPI =1 + stall cycles per instruction. With forwarding+prediction CPI ~1.1-1.3 instead of ~1.6 without.

Pipelining

1. Definition

Pipelining is an implementation technique where multiple instructions are overlapped in execution, analogous to an assembly line. Each instruction is split into $k$ sequential stages; different stages of successive instructions execute concurrently using separate hardware resources.

Ideally $k$-stage pipeline can execute $k$ instructions simultaneously and achieve speedup $\approx k$.

2. Why Require Instruction Pipelining?

• Performance without increasing clock rate: Single-cycle CPU has long critical path (IF+ID+EX+MEM+WB). Pipelining breaks it into shorter stages -> higher clock frequency and throughput.
• Exploit Instruction-Level Parallelism (ILP): Sequential model wastes hardware when one unit is active, others idle. Pipelining keeps all units busy.
• CPI approaches 1: Without pipeline CPI = 1 (single-cycle) but long $T_{clk}$ or CPI >1 (multi-cycle). With pipeline, throughput = 1 instruction/cycle in steady state.
• Cost-effective speedup: No need for multiple CPUs; just pipeline registers.

3. Working Procedure (5-stage Classic RISC Pipeline)

Stages:

1. IF - Instruction Fetch: IR <- M[PC]; PC <- PC+4
2. ID - Instruction Decode/Register Fetch: decode opcode, read $Rs,Rt$, generate immediates.
3. EX - Execute/ALU: ALU operation or effective address ALUout <- Rs op Rt or Rs + imm
4. MEM - Memory Access: MDR <- M[ALUout] for LOAD or M[ALUout] <- Rt for STORE
5. WB - Write Back: Rd <- ALUout or Rd <- MDR

Pipeline registers between stages: IF/ID, ID/EX, EX/MEM, MEM/WB isolate stages.

Timing diagram (no hazards, 5 instructions):

Cycle:  1    2    3    4    5    6    7    8
I1:    IF | ID | EX | MEM| WB |
I2:         IF | ID | EX | MEM| WB |
I3:              IF | ID | EX | MEM| WB |
I4:                   IF | ID | EX | MEM| WB |
I5:                        IF | ID | EX | MEM| WB |

After 5 cycles (fill), one instruction completes per cycle.

Non-pipelined: 5 cycles per instruction sequentially -> 25 cycles for 5 instr. Pipelined: 9 cycles.

Hazards (practical issues)

• Structural: two instr need same resource (e.g., single memory for IF and MEM) - solve by separate I/D caches.
• Data hazard: I2 needs result of I1 (RAW) - forward/bypass or stall (bubble).
• Control hazard: branch target unknown until ID/EX - flush pipeline, branch prediction.

4. Pipeline Performance Measures

Let $k$ = stages, $t_p$ = time per stage, $t_{latch}$ = latch overhead, $n$ = number of instructions.

• Clock period: $T_{clk,pipelined}= \max(t_i) + t_{latch}$ vs $T_{clk,non-piped}= \sum t_i$

• Time for n instructions:
  $T_{non-pipe}= n \cdot k \cdot t_p$
  $T_{pipe}= k\cdot t_p + (n-1)\cdot t_p = (k+n-1)t_p$ (ideal)

• Speedup: $S = \frac{T_{non-pipe}}{T_{pipe}} = \frac{n k}{k+n-1}$. For $n \gg k$, $S \to k$ (ideal).
  With overhead: $S = \frac{k t_p}{t_p + t_{latch}} \cdot \frac{n}{n+k-1}$

• Efficiency: $\eta = \frac{S}{k} = \frac{n}{k+n-1}$ . For large $n$, $\eta \to 1$.

• Throughput: $W = \frac{n}{T_{pipe}} = \frac{1}{t_p}$ instr/sec in steady state (vs $\frac{1}{k t_p}$ non-piped). $n/(k+n-1)t_p$.

• CPI: Ideal CPI = 1, effective CPI = $1 + stalls/instr$ (due to hazards).

• Example: $k=5$, $t_p=2ns$, $n=100$: $T_{non}=1000ns$, $T_{pipe}= (5+99)*2=208ns$, $S=4.8$, $\eta=96\%$.

Pipeline improves throughput, not single-instruction latency (latency stays $k t_p$). Maximum speedup limited by stage imbalance, latches, and hazards.

Solution - Speedup Ratio of Pipeline (Q6a, 2024)

Given:

• Non-pipeline time per task $t_n = 50$ sec
• Number of pipeline segments $k = 6$
• Pipeline clock cycle time $t_p = 10$ sec
• Number of tasks $n = 100$

1. Time without pipeline (Sequential):
$$T_{non-pipe} = n \times t_n = 100 \times 50 = 5000 \text{ sec}$$

2. Time with pipeline:
The first task takes $k \times t_p$ to fill the pipeline, then one task completes every $t_p$.

$$T_{pipe} = k \cdot t_p + (n-1) \cdot t_p = (k + n -1) \cdot t_p$$
$$T_{pipe} = (6 + 100 - 1) \times 10 = 105 \times 10 = 1050 \text{ sec}$$

3. Speedup Ratio ($S$):
$$S = \frac{T_{non-pipe}}{T_{pipe}} = \frac{5000}{1050} \approx 4.76$$

Interpretation:

• Theoretical maximum speedup = $t_n / t_p = 50/10 = 5$. As $n \to \infty$, $S \to 5$.
• For $n=100$, speedup is 4.76, i.e., pipeline is 4.76 times faster than non-pipeline for 100 tasks.
• Efficiency $\eta = S/k = 4.76/6 \approx 0.793$ or $79.3\%$.

Answer: Speedup $\approx$ 4.76 (1050 sec vs 5000 sec). If $n$ is very large, speedup approaches 5.

Note: If clock cycle were $t_n/k \approx 8.33$ sec ideally, speedup would approach 6. Here $t_p=10$ sec > ideal, so overhead reduces speedup.

Solution - Pipeline Hazards and Types

Pipeline Hazard: A situation that prevents the next instruction in the pipeline from executing during its designated clock cycle. It causes stalls/bubbles, reduces speedup and throughput, breaking ideal pipeline flow.

Three Major Types:

1. Structural Hazards (Resource Conflict):
Occurs when hardware resources required by two or more instructions overlap in same clock cycle.

• Cause: Insufficient hardware duplication. E.g., single memory for both instruction fetch and data access (von Neumann), single ALU, single register file write port.
• Example: In 4-stage pipeline IF-ID-EX-MEM, if instruction I1 is in MEM accessing memory and I4 needs IF at same time with single memory port - conflict.
• Solution: Separate instruction and data memories (Harvard), duplicate resources, pipeline register file, stall pipeline (bubble).

2. Data Hazards (Data Dependency):
Occurs when instructions exhibit data dependency and pipeline changes order of read/write accesses.
There are three types:

• RAW (Read After Write) - True Dependency: $I_2$ tries to read operand before $I_1$ writes it.
  ADD R1,R2,R3 ; SUB R4,R1,R5 -> SUB needs R1 before ADD writes. Most common. Causes stalls.
• WAR (Write After Read) - Anti-dependency: $I_2$ writes before $I_1$ reads. Occurs in out-of-order execution.
  ADD R1,R2,R3 ; MUL R2,R4,R5 -> MUL writes R2 before ADD reads it.
• WAW (Write After Write) - Output dependency: Both write same register out-of-order.
  ADD R1,R2,R3 ; MUL R1,R4,R5 -> ordering of writes matters.
• Solutions: Data forwarding/bypassing, operand forwarding, compiler reordering, pipeline interlocks, register renaming, stalling.

3. Control Hazards (Branch Hazards):
Occurs due to branch instructions (conditional/unconditional) - pipeline doesn't know next PC until branch is resolved.

• Example: BEQ R1,R2,target - whether to fetch next sequential instruction or target is unknown until EX/MEM stage. Fetching wrong instruction causes flush.
• Penalty: If pipeline has 5 stages and branch resolved at stage 3, 2 instructions already fetched must be flushed if branch taken.
• Solutions:
  • Stall/Flush: freeze pipeline until branch resolved (simple but slow).
  • Branch Prediction: static (predict not-taken) or dynamic (2-bit predictor, BTB).
  • Delayed Branch: compiler fills delay slot with useful independent instruction after branch.
  • Branch Target Buffer (BTB) and Prefetch.

Additional: Some textbooks add Pipeline Data Hazards sub-class and mention handling via scoreboarding/Tomasulo.

Hazards reduce ideal CPI=1 to CPI >1; effective speedup $< k$.

(a) Speedup

Let $N$ = no. of instructions.

Non-pipelined:

• Clock $f_{np}=2.5\text{ GHz} \Rightarrow T_{np}=0.4\text{ ns}$
• $CPI_{np}=4$
• $T_{old}= N\cdot CPI_{np}\cdot T_{np}= N\cdot 4 / f_{np}= N\cdot 1.6\text{ ns}$

Time per instruction $= 1.6\text{ ns}$.

Pipelined (5-stage, ideal, no hazards):

• $f_{p}=2.0\text{ GHz} \Rightarrow T_{p}=0.5\text{ ns}$
• Ideal $CPI_{p}=1$ (one instruction completes per cycle in steady state). Ignoring fill/drain overhead for large $N$: $T_{new}= N\cdot 1 \cdot T_{p}= N\cdot 0.5\text{ ns}$.

With fill overhead: $T_{new}= (k+N-1)T_{p}$ where $k=5$, $\approx N T_{p}$ for $N\gg k$.

$$Speedup = \frac{T_{old}}{T_{new}} = \frac{CPI_{np}/f_{np}}{CPI_{p}/f_{p}} = \frac{4/2.5}{1/2}= \frac{1.6}{0.5}=3.2$$

So $\approx 3.2\times$ speedup in the ideal hazard-free case. If pipeline stalls/hazards raise $CPI_{p}$ to e.g. 1.2 then $Speedup = (4/2.5)/(1.2/2)=2.67$.

Maximum theoretical speedup ignoring clock reduction: $CPI_{np}/CPI_{p}=4$; with clock penalty $2/2.5=0.8$, net $4\times0.8=3.2$.

(b) MIPS rate

$$MIPS = \frac{f}{CPI\times10^{6}}$$

• Non-pipelined: $MIPS_{np}= \dfrac{2.5\times10^{9}}{4\times10^{6}} = \mathbf{625\ MIPS}$

• Pipelined (ideal $CPI=1$): $MIPS_{p}= \dfrac{2.0\times10^{9}}{1\times10^{6}} = \mathbf{2000\ MIPS}$

If hazards included, e.g. $CPI_{p}=1.14$, $MIPS_{p}\approx 1754$. In general $MIPS_{p}=2000/CPI_{p}$.

Throughput gain $=2000/625=3.2$ same as speedup.

Pipelining - Basic Concepts

Pipelining is an implementation technique where multiple instructions are overlapped in execution, like an assembly line. An $k$-stage pipeline divides instruction execution into $k$ stages (classic RISC: IF-ID-EX-MEM-WB) operating concurrently.

Basic Operation

Each stage has combinational logic + pipeline register/latch. Clock period $T_p = \max(T_{stage}) + T_{latch}$. While stage $i$ processes instruction $n$, stage $i-1$ processes $n+1$.

For $k=4$, $n$ instructions: non-pipelined time $= n\cdot k\cdot T_p$, pipelined time $= (k+n-1)T_p$.

Speedup

$$S = \frac{T_{non-pipe}}{T_{pipe}} = \frac{n\cdot k}{k+n-1} \xrightarrow{n\gg k} k$$
Ideal speedup = number of stages. With stage imbalance and latch overhead: $S = \frac{k\cdot T_{seq}}{T_p}$.

Example $k=5$, $n=100$: $S = 500/104 \approx 4.8$.

Efficiency $\eta = S/k$, Throughput $= n/(k+n-1)T_p \xrightarrow{n\to\infty} 1/T_p$ instructions/sec = $f_{clk}$ (one per cycle).

Throughput

Rate of instruction completion. Non-pipelined: $1/(kT_s)$, Pipelined (steady): $1/T_p$. Improvement factor same as speedup. Supercalar/superpipelined increase further.

Pipeline Hazards - prevent next instruction from executing in next cycle

1. Structural Hazards: Hardware resource conflict (e.g. single memory for IF+MEM, single ALU). Solution: Separate I/D caches (Harvard), duplicate units, stalling (bubble).

2. Data Hazards: Dependency on previous result still in pipe.

• RAW (true) ADD R1,R2,R3 followed by SUB R4,R1,R5 (R1 not written back)
• WAR, WAW in out-of-order pipes.
  Solution: Forwarding/bypassing (EX→EX), compiler code scheduling, pipeline interlock + stall, register renaming.

3. Control Hazards: Branch/jump changes PC, next fetched instructions wrong.

• Unconditional: 1-cycle bubble
• Conditional: taken/not-taken decision at EX/MEM → flush.
  Solutions: Stall/flush, branch prediction (static: not-taken/backward-taken; dynamic: 2-bit saturating counter, BTB), delayed branch (branch delay slot, predication), speculative execution.

Additional classification Data hazards = load-use: LW R1,0(R2); ADD R3,R1,R4 requires 1 stall even with forwarding (mem latency).

Performance impact: $CPI_{pipe}= CPI_{ideal} + stall_{structural}+stall_{data}+stall_{control}$ ; $CPI_{ideal}=1$.

Ideal pipeline CPI=1, real $1.2\text{-}1.5$ due to hazards; longer pipe → higher hazard penalty.

Diagram should show 5 stages overlapped in time (Gantt chart) and hazard bubble insertion.

Parallel Processors

Parallel processors execute multiple operations concurrently to increase throughput. Classified by Flynn's taxonomy:

• SISD: Single Instruction Single Data - conventional uniprocessor.
• SIMD: Single Instruction Multiple Data - array/vector processors, e.g., GPU, vector supercomputer.
• MISD: Multiple Instruction Single Data - rare, pipelined architectures.
• MIMD: Multiple Instruction Multiple Data - most parallel computers. Two models:
  1. Shared Memory (Tightly coupled): All processors share a common main memory via interconnection network (bus, crossbar, multistage). Sub-types: UMA (uniform memory access / SMP) - equal access time; NUMA - distributed shared memory, non-uniform latency; COMA/COMA.
  2. Distributed Memory (Loosely coupled): Each processor has private memory, communicates via message passing.
• Multicore / Multiprocessor: Modern CMPs are MIMD shared-memory on single chip.

Parallelism levels: Job-level, task-level, instruction-level and loop-level.

Cache Coherency Problem in Shared Memory

In shared-memory MIMD, each processor has private cache for latency reduction. Coherency problem: If multiple caches hold a copy of same memory block $X$, and one processor writes $X$, other copies become stale, leading to inconsistent views.

Example: $P_1$ and $P_2$ cache $X=5$. $P_1$ does $X \leftarrow 10$ in its cache, $P_2$ still sees $X=5$. Memory may be 5 or 10 depending on write-through/write-back - inconsistency.

Coherence requires: (1) Writes to same location seen in same order by all processors (write serialization), (2) Read returns last written value.

Solutions:

1. Snooping (Snoopy) Protocol - for bus-based SMPs: Every cache monitors (snoops) bus transactions.

   • Write-Invalidate: On write hit, processor broadcasts invalidate to all other caches holding block. Others discard copy. Most common (MESI/MOESI).
   • Write-Update (Write-Broadcast): Write is broadcast to update all copies.

2. Directory-Based Protocol - for scalable networks / NUMA: Central directory keeps state of each block (which caches have copy, dirty/clean). On write, directory sends point-to-point invalidates only to holders. Avoids broadcast overhead.

3. MESI States (Illinois Protocol):

   • M (Modified): Dirty, exclusive.
   • E (Exclusive): Clean, exclusive.
   • S (Shared): Clean, may be shared.
   • I (Invalid): Not valid.

On Read Miss → BusRd, on Write → BusRdX / BusUpgr, state transitions enforce coherence.

Coherence is handled in hardware; software must ensure consistency model (sequential consistency, etc.).

Given stage delays: $T_1=800$, $T_2=500$, $T_3=400$, $T_4=300$ ps. Pipeline clock $T_{clk}= \max(T_i)$ (+ latch overhead ignored).

Before modification:
$$T_{clk1}= \max(800,500,400,300)=800\text{ ps}$$
Throughput $= 1/T_{clk1}$ instructions per ps.
$$f_1 = \frac{1}{800\text{ ps}} =1.25\times10^{9}\text{ instr/s}$$

After splitting first stage into $600$ ps + $350$ ps, stages become: $600,350,500,400,300$.

$$T_{clk2}= \max(600,350,500,400,300)=600\text{ ps}$$
$$f_2 = \frac{1}{600\text{ ps}} =1.667\times10^{9}\text{ instr/s}$$

Throughput increase:
$$\%\Delta = \frac{f_2-f_1}{f_1}\times100 = \frac{\frac{1}{600}-\frac{1}{800}}{\frac{1}{800}}\times100 = \left(\frac{800}{600}-1\right)\times100$$
$$= \left(1.333...-1\right)\times100 = 33.33\%$$

Speedup $= 800/600 = 1.33$.

If latch overhead $t_l$ (e.g., 20ps) included, then $T_{clk1}=800+t_l$, $T_{clk2}=600+t_l$, increase $= \frac{800+t_l}{600+t_l}-1 \approx 32.25\%$ for $t_l=20$ps. Ideal approx 33.33% increase.

Note: Total latency increases slightly ($2000$ ps → $2150$ ps) but steady-state throughput improves due to smaller max stage delay (pipeline bottleneck reduced).

Hazards in Pipeline Architecture (7 Marks)

Pipelining overlaps fetch-decode-execute stages to increase throughput (ideal CPI=1). Hazards prevent next instruction from executing in designated cycle, causing stalls/bubbles.

1. Structural Hazards – Resource Conflict
Two instructions need same hardware at same time.
Example: Single memory for instruction + data. Stage IF and MEM both need memory in same cycle. Solution: separate I-Cache/D-Cache (Harvard) or stall.
Other examples: Single ALU used for EX and address calculation; insufficient registers ports.

2. Data Hazards – Data Dependency
Occurs when instruction depends on result of previous instruction not yet completed. Three types:

a) RAW (Read After Write) – True Dependency: $I2$ reads register $I1$ writes.

ADD R1,R2,R3   ; R1 written
SUB R4,R1,R5   ; R1 read – needs forwarding/stall

Most common. Solved by forwarding/bypassing, operand forwarding, compiler reordering, stalling.

b) WAR (Write After Read) – Anti-Dependency:

ADD R4,R1,R5
SUB R1,R2,R3   ; writes R1 before first reads it

Not in classic 5-stage in-order pipeline but appears in out-of-order execution. Solved by register renaming.

c) WAW (Write After Write) – Output Dependency:

ADD R1,R2,R3
SUB R1,R4,R5   ; both write R1

Also for out-of-order. Solved by renaming.

3. Control Hazards (Branch Hazards)
Caused by branches/jumps – next PC unknown until branch resolved.

BEQ R1,R2, LABEL ; whether to take branch known in EX/MEM
ADD R3,R4,R5     ; next instruction fetched incorrectly if branch taken

Penalty = flush pipeline. Solutions:

• Stall until decision known
• Branch prediction (static: predict not taken; dynamic: 1-bit/2-bit predictor, BTB)
• Delayed branch (fill delay slot with useful/no-op instruction)
• Speculative execution

All hazards reduce speedup: $Speedup = \frac{n}{\text{ideal cycles + stalls}}$.

Array Processor and SIMD Array Processor [7M]

Classification (Flynn):
SISD (Single Instruction Single Data - uniprocessor), SIMD (Single Instruction Multiple Data - array/vector), MISD, MIMD (multiprocessor).

What is Array Processor?
Processor that performs same operation on multiple data elements simultaneously via array of Processing Elements (PEs). Specially for vector/matrix operations: image processing, scientific simulation, ML.

Also called Vector processor if pipelined single ALU, Array processor if many ALUs.

SIMD Array Processor Architecture:

            +-------------------+
            | Control Unit (CU)/|
            | Instruction Unit  |--- Master Control (Fetch/Decode)
            +---------+---------+
                      | broadcast
        +-------------+-------------+
        |             |             |
     PE0           PE1 ....      PE_{n-1}
   |ALU|RAM|    |ALU|RAM|      |ALU|RAM|
     \             |             /
      +---- Interconnection N/w ----+ (Mesh, Cube, Bus, Crossbar)
                      |
                   Shared Memory / I/O

• Components:

  1. Master Control Unit / Front-end CPU: Fetches/decodes instructions, executes scalar instructions, broadcasts vector instruction and address to all PEs.
  2. N Processing Elements (PEs): Each has own ALU, local memory/registers, and indexing logic. Identical. e.g. 64 to 65536 PEs.
  3. Interconnection Network: Permits data exchange between PEs: nearest neighbour mesh, hypercube, crossbar. Needed for permutations (shuffle, transpose).
  4. Mask register: Enables/disables subset of PEs for conditional execution (if).

• Execution: Single instruction stream -> all enabled PEs execute lock-step synchronously on their own data stream element. E.g.

Instruction: C[i] = A[i] + B[i] for i=0..1023
CU broadcasts ADD
PE0: C0 = A0+B0
PE1: C1 = A1+B1  (...1024 parallel)
...

Time taken = 1 vector instruction vs 1024 SISD loop iterations.

Example:

• ILLIAC IV (historical): 64 PEs in 8x8 mesh, CU broadcast, used for air dynamics.
• BSP (Burroughs Scientific Processor): 16 PEs.
• Modern: GPU (NVIDIA) - each SM is SIMD (warp of 32 threads executes same instruction - SIMT variant), Intel AVX-512 (vector width 16 floats), Connection Machine CM-2 (65536 bit-serial PEs).

Another example: Adding two $4\times4$ matrices: distribute rows to 4 PEs, single ADD does 16 additions in parallel.

Advantages:

• Huge speedup for data-parallel problems: $Speedup \approx N_{PE}$.
• Simple control (single fetch unit), regular structure, high throughput per cost.

Limitations:

• Only data-parallel problems benefit; branching causes idle PEs (divergence).
• Requires alignment of data; communication overhead via network.
• Amdahl's law: scalar part limits. I/O handling through CU bottleneck.

vs MIMD: Multiple instruction streams (multicore) more general but complex control.