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.