Module IV: Array & Vector Pipeline

An Array Processor (also called a SIMD processor) is a type of parallel computer that consists of multiple identical Processing Elements (PEs) operating synchronously under the control of a single Control Unit (CU). All PEs execute the same instruction at the same time, but each PE operates on its own different data from its own local memory.

Architecture:

• Control Unit (CU): Fetches and decodes one instruction at a time, then broadcasts the control signals to all PEs.
• Processing Elements (PEs): Each PE is a simple ALU with its own local memory. All PEs execute the broadcast instruction in lockstep.
• Interconnection Network: Connects PEs to allow inter-PE data communication (e.g., shifting data between neighbors).
• Masking: Individual PEs can be disabled (masked) so that only a subset of PEs participates in an operation (used for conditional operations).

Example:

• ILLIAC IV: One of the earliest array processors (1972). It had 64 PEs, each with its own 2KB local memory. The CU broadcast a single instruction to all 64 PEs to perform parallel operations on 64 data elements simultaneously.
• Modern GPUs: Modern Graphics Processing Units (like NVIDIA CUDA cores) are essentially massively parallel array processors with thousands of PEs (CUDA cores), optimized for data-parallel graphics and scientific computations.

Classification: Array processors fall under Flynn's SIMD (Single Instruction, Multiple Data) category, as one instruction stream operates on multiple data streams.

A Vector Processor is a CPU designed to operate on entire vectors (one-dimensional arrays of data) using a single instruction. Instead of using a loop to process each element one at a time (scalar processing), a vector processor issues one instruction like VADD V1, V2, V3 which adds every element of vector V2 to every element of vector V3, storing results in V1.

Architecture:

• Vector Registers: Large registers (e.g., V0-V7) that can hold 64 or more elements each (e.g., 64 double-precision floating-point numbers).
• Deeply Pipelined Functional Units: The ALU/FPU is deeply pipelined (e.g., 6-10 stages). After an initial startup latency, it produces one result per clock cycle.
• Vector Load/Store Units: Specialized memory units that can fetch entire vectors from memory in a streaming fashion.
• Vector Length Register (VLR): Specifies how many elements of the vector register to process (handles vectors shorter than the register length).
• Vector Mask Register: A boolean register that enables/disables individual element operations (for conditional vector processing).

Key Application Area:

• Scientific Computing and Weather Forecasting: Climate models involve massive matrix operations, fluid dynamics simulations, and linear algebra — all perfectly suited for vector processing. The Cray-1 and Cray X-MP supercomputers, which were vector processors, were heavily used by national weather services worldwide.
• Other applications: Molecular dynamics, computational fluid dynamics (CFD), seismic analysis, image processing.

In vector processors, pipelining refers to the deep segmentation of the arithmetic functional units (like Floating-Point Adders, Multipliers) into multiple stages. This allows a new pair of vector elements to enter the pipeline every clock cycle, achieving a sustained throughput of one result per clock cycle after the initial startup latency.

How It Works:

1. A vector instruction (e.g., VADD V3, V1, V2 — add 64 elements) is issued.
2. The floating-point adder pipeline has, say, 6 stages (Compare Exponents → Align Mantissa → Add → Normalize → Round → Pack).
3. Cycle 1: Element pair (V1[0], V2[0]) enters Stage 1.
4. Cycle 2: (V1[0], V2[0]) moves to Stage 2. (V1[1], V2[1]) enters Stage 1.
5. Cycle 6: (V1[0], V2[0]) exits Stage 6 — the first result V3[0] is produced. Elements V1[1]–V1[5] are in various pipeline stages.
6. Cycle 7 onwards: One result is produced every single clock cycle. V3[1] in cycle 7, V3[2] in cycle 8, etc.
7. Cycle 69: V3[63] (the last result for a 64-element vector) is produced.

Key Formula:

Significance: Without pipelining, 64 additions would take 64 × 6 = 384 cycles. With pipelining, it takes only 6 + 63 = 69 cycles. The throughput approaches 1 element/cycle for long vectors.

Speedup in vector pipelining is the ratio of the time taken by a scalar (non-pipelined) processor to process a vector operation compared to the time taken by a pipelined vector processor for the same operation.

Derivation:

• Scalar Time: If the operation takes k clock cycles for one element (because the functional unit has k stages), and the vector has N elements:
  Time_scalar = N × k cycles
• Vector (Pipelined) Time: The first result takes k cycles (startup). After that, one result per cycle for the remaining N-1 elements:
  Time_vector = k + (N - 1) cycles
• Speedup:
  Speedup = (N × k) / (k + N - 1)

Limiting Behavior:

• As N → ∞ (very long vectors): Speedup → k (the number of pipeline stages). The startup cost becomes negligible.
• As N = 1 (single element): Speedup = k/k = 1 (no benefit from pipelining).

Conclusion: Vector pipelining is most effective for long vectors, where the throughput approaches the theoretical maximum of one result per cycle.

A Mask Register (or Vector Mask Register) is a special hardware register in a vector processor that holds a vector of boolean values (0 or 1), one bit per vector element. It is used to implement conditional operations on individual elements within a vector instruction.

Why It's Needed:

Consider the scalar code:

for (i = 0; i < N; i++) {
    if (A[i] > 0)
        B[i] = A[i] + C[i];
}
    

In scalar processing, the if statement is a branch. In vector processing, there are no branches within a vector operation. Instead, the mask register selectively enables or disables the operation for each element.

How It Works:

1. Set the Mask: A vector comparison instruction (e.g., VCMP.GT VM, V_A, 0) compares each element of V_A against 0 and sets the corresponding bit in the mask register VM. If A[i] > 0, VM[i] = 1; otherwise VM[i] = 0.
2. Masked Operation: The subsequent vector ADD instruction (VADD V_B, V_A, V_C, VM) only executes the addition for elements where VM[i] = 1. Elements where VM[i] = 0 are skipped (or their results are not written back).

Significance: The mask register allows vector processors to handle if-else constructs without branches, maintaining the streaming pipeline efficiency of vector execution even for conditional computations.

1. ILLIAC IV (1972):

• One of the earliest and most iconic SIMD array processors.
• Built at the University of Illinois and operated at NASA Ames Research Center.
• Featured 64 Processing Elements, each with its own local memory, controlled by a single Control Unit.
• Used for aerodynamic simulations and weather modeling.

2. Connection Machine CM-2 (1987):

• Designed by Thinking Machines Corporation.
• Contained up to 65,536 simple 1-bit processors arranged in a hypercube interconnection network.
• Each processor had its own local memory. The CU broadcast instructions to all processors.
• Used for massively parallel applications like fluid dynamics, AI, and database search.

Modern Examples:

• NVIDIA GPUs (CUDA architecture): Thousands of CUDA cores execute the same instruction (kernel) on different data elements — a modern, massively parallel SIMD architecture.
• Intel SSE/AVX extensions: SIMD instruction sets within x86 CPUs that process 4-16 data elements per instruction using 128-512 bit wide registers.

Both exploit data-level parallelism (DLP), but they do so through fundamentally different architectural approaches.

Conceptual Block Diagrams:

Array Processor:

    Control Unit (CU)
    ┌──────────────┐
    │  Fetch & Decode  │──── broadcasts instruction ────┐
    └──────────────┘                                    │
         ┌──────┐  ┌──────┐  ┌──────┐  ┌──────┐       │
         │ PE 0 │  │ PE 1 │  │ PE 2 │  │ PE N │ ◄─────┘
         │ ALU  │  │ ALU  │  │ ALU  │  │ ALU  │  (all execute same op)
         │ Mem  │  │ Mem  │  │ Mem  │  │ Mem  │
         └──────┘  └──────┘  └──────┘  └──────┘
    

Vector Processor:

    Scalar Unit ──► Vector Control Unit
                        │
         ┌──────────────┼──────────────┐
         │              │              │
    ┌─────────┐  ┌─────────┐   ┌─────────────┐
    │ V Reg 0 │  │ V Reg 1 │   │ V Reg N     │
    │ 64 elems│  │ 64 elems│   │ 64 elems    │
    └────┬────┘  └────┬────┘   └──────┬──────┘
         │            │               │
         └──►  Pipelined FP Adder  ◄──┘
              [S1|S2|S3|S4|S5|S6]
              ──► 1 result/cycle after startup
    

A vector pipeline processes an entire vector of data through a deeply segmented functional unit, producing one result per clock cycle after an initial fill-up period.

Example: Vector Floating-Point Addition (VADD V3, V1, V2)

This instruction adds corresponding elements of vector registers V1 and V2, storing results in V3. The floating-point adder pipeline typically has 4-6 stages:

1. Stage 1 — Compare Exponents: Compare the exponents of the two floating-point operands to determine the difference.
2. Stage 2 — Align Mantissa: Shift the mantissa of the smaller number right by the exponent difference so both numbers have the same exponent.
3. Stage 3 — Add Mantissas: Perform the actual addition (or subtraction) of the aligned mantissas.
4. Stage 4 — Normalize: Shift the result mantissa so it is in normalized form (leading 1 before the decimal point) and adjust the exponent accordingly.

Pipeline Timing (Vector Length = 6, Stages = 4):

Cycle:    1    2    3    4    5    6    7    8    9
Stage 1:  E0   E1   E2   E3   E4   E5
Stage 2:       E0   E1   E2   E3   E4   E5
Stage 3:            E0   E1   E2   E3   E4   E5
Stage 4:                 E0   E1   E2   E3   E4   E5
Output:                  V3[0] V3[1] V3[2] V3[3] V3[4] V3[5]
    

Total Cycles = 4 + 6 - 1 = 9 cycles (vs. 4 × 6 = 24 cycles without pipelining).

Speedup = 24/9 = 2.67x

Vector Chaining is an optimization technique in vector processors that allows the output of one vector functional unit to be fed directly into the input of another vector functional unit without waiting for the first operation to complete on the entire vector. It is the vector equivalent of data forwarding in scalar pipelines.

Example Without Chaining:

VMUL V3, V1, V2    ; V3 = V1 × V2 (takes k + N - 1 cycles)
VADD V5, V3, V4    ; V5 = V3 + V4 (must wait until VMUL finishes ALL elements)
    

Total time ≈ 2 × (k + N - 1) cycles. The VADD cannot start until the entire VMUL is done.

Example With Chaining:

• As soon as the VMUL pipeline produces V3[0] (after its startup latency), that result is immediately forwarded to the VADD pipeline input.
• One cycle later, V3[1] is forwarded, and so on.
• The two pipelines operate concurrently, with the VADD pipeline trailing the VMUL pipeline by just the startup latency.

Total time ≈ k_mul + k_add + N - 1 cycles (much less than the sequential sum).

Performance Improvement:

• For long vectors, chaining nearly halves the execution time for a sequence of two dependent vector operations.
• Multiple chains can be active simultaneously if the processor has multiple independent functional units.
• Chaining was a hallmark feature of the Cray-1 supercomputer, contributing significantly to its legendary performance.

Data-Level Parallelism (DLP) is a form of parallelism that arises when the same operation is applied to multiple independent data elements simultaneously. Array processors are specifically designed to exploit DLP.

How Array Processors Exploit DLP:

1. Data Distribution: The dataset is distributed across the local memories of the Processing Elements (PEs). For example, if you have a 64-element array and 64 PEs, element A[i] is stored in PE[i]'s local memory.
2. Instruction Broadcast: The Control Unit (CU) fetches a single instruction (e.g., "ADD the value from local memory address X to register R1") and broadcasts it to all PEs simultaneously.
3. Parallel Execution: All 64 PEs execute the ADD instruction at the exact same time, each operating on its own local data. In one clock cycle, 64 additions are performed.
4. Conditional Execution (Masking): If only some elements need to be processed (e.g., if A[i] > 0), a mask register disables the PEs that don't meet the condition, while the active PEs proceed.

Example — Vector Addition:

To compute C[i] = A[i] + B[i] for i = 0 to 63:

• A[i] is stored in PE[i]'s memory at address 100.
• B[i] is stored in PE[i]'s memory at address 200.
• CU broadcasts: LOAD R1, [100] → All 64 PEs load their respective A[i].
• CU broadcasts: LOAD R2, [200] → All 64 PEs load their respective B[i].
• CU broadcasts: ADD R3, R1, R2 → All 64 PEs compute C[i] = A[i] + B[i] simultaneously.
• CU broadcasts: STORE R3, [300] → All 64 PEs store their C[i].

4 instructions process 64 elements — a massive exploitation of DLP.

Given:

• Number of pipeline stages (k) = 5
• Vector length (N) = 100

a) Total Clock Cycles Required:

Explanation: The pipeline takes 5 cycles to fill (startup latency for the first element). After that, one element completes every cycle for the remaining 99 elements.

b) Pipeline Efficiency:

Pipeline efficiency measures how well the pipeline utilizes its hardware compared to the ideal case.

Interpretation:

• The pipeline is 96.15% efficient, meaning only 3.85% of the pipeline's capacity is wasted (during the 4 startup cycles where not all stages are active).
• For comparison, if the vector length were only 10: Efficiency = 10/(5+9) = 10/14 = 71.4%. Short vectors are much less efficient.
• The speedup over scalar execution = (N × k) / (k + N - 1) = (100 × 5) / 104 = 500/104 = 4.81x.

Problem: Multiply two 64×64 matrices: C = A × B, where C[i][j] = Σ(A[i][k] × B[k][j]) for k = 0 to 63.

Data Distribution:

• We have 64 PEs. Assign each PE to compute one element of a result row.
• PE[j] stores: Column j of Matrix B (i.e., B[0][j], B[1][j], ..., B[63][j]) in its local memory.
• Matrix A rows will be broadcast by the Control Unit.

Algorithm (Row-at-a-Time):

1. For each row i of Matrix A (i = 0 to 63):
   1. Initialize: Each PE sets its accumulator R_acc = 0.
   2. For each k = 0 to 63:
      • CU broadcasts A[i][k] to all 64 PEs.
      • Each PE[j] loads B[k][j] from its local memory.
      • Each PE[j] computes: R_acc = R_acc + A[i][k] × B[k][j].
   3. After the inner loop: PE[j] stores R_acc → C[i][j].

Data Flow Summary:

• Broadcast: A[i][k] is broadcast from the CU to all PEs (one scalar value per inner loop step).
• Local Read: Each PE reads B[k][j] from its own local memory.
• Parallel Compute: All 64 PEs perform a multiply-accumulate simultaneously.

Total Steps: 64 (rows) × 64 (inner loop) = 4,096 multiply-accumulate steps. But since each step involves 64 PEs working in parallel, the effective work is 64 × 64 × 64 = 262,144 multiplications in 4,096 steps. Without the array processor, a scalar machine would need 262,144 sequential steps.

Given:

• Vector length (N) = 128 elements
• Initiation rate = 1 element per cycle (one new pair enters the pipeline each cycle)
• Number of pipeline stages (k) = 6

Note: A dot product involves two operations: element-wise multiplication followed by a summation (reduction). Let's calculate the time for the multiplication phase first.

Step 1: Vector Multiply Time (V3 = V1 × V2)

Step 2: Reduction (Summation)

After multiplication, we have 128 products that must be summed. A vector reduction (tree-based summation) takes log₂(N) passes:

• Pass 1: Add pairs → 64 partial sums (pipeline time: 6 + 63 = 69 cycles)
• Pass 2: Add pairs → 32 partial sums (6 + 31 = 37 cycles)
• Pass 3: 16 sums (6 + 15 = 21 cycles)
• Pass 4: 8 sums (6 + 7 = 13 cycles)
• Pass 5: 4 sums (6 + 3 = 9 cycles)
• Pass 6: 2 sums (6 + 1 = 7 cycles)
• Pass 7: 1 final sum (6 + 0 = 6 cycles)

Total reduction = 69 + 37 + 21 + 13 + 9 + 7 + 6 = 162 cycles.

With Vector Chaining: If chaining is supported, the multiply and the first reduction pass can overlap, saving significant time.

Total Time (without chaining): 133 + 162 = 295 cycles for the complete dot product.

If only multiplication is asked: 133 cycles.

An array processor (SIMD machine) is designed to execute a single instruction simultaneously across many data elements using multiple, identical Processing Elements.

Detailed Architecture:

1. Control Unit (CU):
   • A conventional scalar processor that fetches instructions from main memory.
   • Decodes each instruction and determines whether it is a scalar operation (handled by the CU itself) or a parallel array operation (broadcast to the PEs).
   • For array operations, the CU broadcasts the opcode and operand addresses to all PEs simultaneously.
2. Processing Elements (PEs):
   • Each PE contains: a simple ALU, a set of local registers, and its own local memory module.
   • All PEs are identical in hardware.
   • Each PE has an Activity Flag (Enable/Disable bit) that can be set by mask instructions. Disabled PEs ignore the broadcast instruction.
3. Interconnection Network:
   • Connects PEs to each other for inter-PE data exchange (e.g., shifting data to neighbor, routing data to a specific PE).
   • Common topologies: Linear array, 2D mesh, hypercube.
4. I/O System: A separate system for loading data into PE local memories and reading results out.

Executing Arithmetic on Data Arrays:

To compute C[i] = A[i] + B[i] for all i:

1. Data is pre-loaded: A[i] resides at address 100 and B[i] at address 200 in PE[i]'s local memory.
2. CU broadcasts LOAD R1, [100]: All PEs load A[i] from their local address 100 into register R1.
3. CU broadcasts LOAD R2, [200]: All PEs load B[i] into R2.
4. CU broadcasts ADD R3, R1, R2: All PEs compute A[i] + B[i] in parallel.
5. CU broadcasts STORE R3, [300]: All PEs store C[i] to address 300.

All N additions are completed in the time of a single addition instruction.

The Cray-1 (1976) was a landmark vector processor. Its architecture featured Vector Registers and deeply pipelined functional units with vector chaining.

Cray-1 Architecture Highlights:

• 8 Vector Registers (V0-V7), each holding 64 elements of 64 bits each.
• Pipelined Functional Units: FP Add (6 stages), FP Multiply (7 stages), FP Reciprocal (14 stages), Integer Add, Logical, Shift.
• Two Load/Store pipelines for memory-to-register and register-to-memory transfers.
• Vector chaining supported between functional units.

Example: Compute V3 = V1 × V2 + V4

Instruction 1: VMUL V3, V1, V2   (7-stage multiply pipeline)
Instruction 2: VADD V5, V3, V4   (6-stage add pipeline, chained to VMUL)
    

Timing Diagram (Vector Length = 8, simplified):

Cycle:  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
VMUL:  [--- 7 stages for E0 ---]
        E0 E1 E2 E3 E4 E5 E6 E7    ← one element enters per cycle
Output:                      M0 M1 M2 M3 M4 M5 M6 M7

VADD (chained):              [--- 6 stages for E0 ---]
                              M0 enters immediately when produced
Output:                                     A0 A1 A2 A3 A4 A5 A6 A7
    

Without Chaining: VMUL finishes at cycle 14. VADD starts at cycle 15, finishes at cycle 14 + 6 + 7 = 27. Total = 27 cycles.

With Chaining: VADD starts at cycle 8 (when M0 is produced). VADD finishes at cycle 8 + 6 + 7 = 20. Total = 20 cycles. Saving 7 cycles (25% faster).

Given:

• Number of pipeline stages (k) = 6
• Vector length (N) = 64 elements
• Scalar execution time = 6 cycles per element (one element uses all 6 stages sequentially)

a) Total Clock Cycles for Pipelined Vector Multiply:

b) Speedup over Scalar Execution:

Conclusion:

• Pipelined execution takes 69 cycles.
• The speedup is approximately 5.57x.
• The theoretical maximum speedup equals the number of pipeline stages (k = 6). The achieved 5.57x is very close to this maximum because the vector length (64) is much larger than the number of stages (6), making the startup overhead negligible.
• Pipeline Efficiency = N / (k + N - 1) = 64/69 = 92.75%.

Advantages:

1. Massive Throughput for Regular Data: Both architectures can process hundreds or thousands of data elements per clock cycle for regular, structured computations, far exceeding the throughput of scalar processors.
2. Reduced Instruction Overhead: A single vector or array instruction replaces an entire loop (which would involve many fetch-decode-branch cycles). This reduces instruction cache pressure and branch prediction overhead.
3. Energy Efficiency: Fetching and decoding one instruction to process 64 or more elements is far more energy-efficient than fetching and decoding 64 separate scalar instructions. The control overhead per operation is amortized over many data elements.
4. Predictable Memory Access: Vector load/store operations access memory in regular, predictable patterns (stride-1, stride-N), allowing the memory controller to optimize prefetching and bank access, hiding memory latency.
5. Simplified Programming for DLP: High-level constructs (array operations in Fortran, CUDA kernels) map naturally to vector/array hardware.

Limitations:

1. Poor Scalar Performance: Both architectures are inefficient for scalar, sequential code (e.g., pointer-chasing, tree traversal, irregular graph algorithms). The massive parallel hardware sits idle during scalar operations.
2. Conditional Execution Penalties: Branches and if-else statements within data-parallel operations are handled via masking, which disables some PEs/elements. In the worst case (50% of elements masked), half the hardware is wasted.
3. Short Vector Penalty: For very short vectors, the pipeline startup latency dominates, making pipelining inefficient. Array processors with 64 PEs processing only 10 elements waste 54 PEs.
4. Data Redistribution Overhead: Array processors incur significant overhead when PEs need to exchange data (e.g., matrix transposition, scatter/gather operations). The interconnection network becomes a bottleneck.
5. Memory Bandwidth Demands: Vector and array processors can consume data far faster than memory can supply it. If the memory system cannot keep the pipelines fed, performance drops dramatically (memory wall).