Back to the 2019 paper

Module 3: Pipelining

20197m

What is an array processor? Explain SIMD array processor with a suitable example.

Worked SolutionAI Assisted

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×44\times4 matrices: distribute rows to 4 PEs, single ADD does 16 additions in parallel.

Advantages:

  • Huge speedup for data-parallel problems: Speedup≈NPESpeedup \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.

Similar questions

Budget AppAndroid App

Pocketly on Android

Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.