Vector Processing

Introduction

Vector processing is a form of parallelism that operates on entire arrays of data with single instructions, rather than processing one element at a time in a loop. When a scalar processor adds two arrays of 1000 numbers, it executes 1000 individual add instructions with all the associated loop overhead — fetching the instruction, decoding it, updating the loop counter, and checking the termination condition each iteration. A vector processor accomplishes the same work with a single vector add instruction, dramatically reducing instruction fetch overhead and exploiting the inherent data-level parallelism.

This approach is particularly powerful for scientific computing, multimedia processing, machine learning, and any workload where the same operation is applied uniformly across large datasets. The concept has evolved from dedicated vector supercomputers (like the Cray-1) in the 1970s to SIMD extensions built into every modern desktop and mobile processor.

Vector Processor Architecture

A classic vector processor contains several key components that distinguish it from a scalar processor:

Vector Registers: Large registers that hold multiple data elements. Unlike a scalar register holding one 64-bit value, a vector register might hold 64 separate 64-bit values. The Cray-1 had eight vector registers, each holding 64 elements of 64 bits.

Vector Functional Units: Pipelined arithmetic units that accept vector operands and produce one result element per clock cycle once the pipeline is full. Separate units exist for addition, multiplication, division, and logical operations.

Vector Load/Store Units: Specialized memory units that can stream contiguous (or strided) data between memory and vector registers at high bandwidth.

Vector Length Register (VLR): Specifies how many elements of the vector register to process. This handles arrays whose length does not match the hardware vector register size.

SIMD: Vectors in Modern Processors

Modern processors implement vector processing through SIMD (Single Instruction, Multiple Data) extensions rather than separate vector processors. SIMD packs multiple data elements into wide registers and processes them all with one instruction:

For example, an AVX-512 instruction can add 16 single-precision floating-point numbers simultaneously in one clock cycle. A simple loop adding two arrays:

Key Concepts in Vector Processing

Stride

Stride refers to the spacing between consecutive elements accessed in memory. A stride of 1 means elements are contiguous (best case — maximizes cache line utilization). A stride of N means we skip N-1 elements between each access (common when accessing a column of a row-major matrix). Hardware must handle non-unit strides, though performance degrades because cache lines are underutilized.

Vector Masks

Vector masks enable conditional execution on individual elements. A mask register holds one bit per element, and only elements whose corresponding mask bit is 1 are processed. This handles situations where an operation should apply only to elements meeting a condition:

Chaining

Chaining (or forwarding) allows the output of one vector operation to feed directly into the input of the next without waiting for the entire first operation to complete. As soon as the first result element emerges from unit 1, unit 2 can begin processing it. This overlaps execution of dependent vector operations and significantly improves throughput.

Strip Mining

When the array length exceeds the vector register length, the compiler or programmer must break the array into strips that fit in the vector registers. Each strip is processed with one vector instruction sequence, and a loop iterates over strips. For a 1000-element array with 16-element vector registers, strip mining creates a loop of 63 iterations (62 full strips of 16, plus one partial strip of 8).

Auto-Vectorization

Modern compilers can automatically transform scalar loops into vector instructions (auto-vectorization) when they can prove:

• No data dependencies between iterations
• Loop bounds are known or can be determined at runtime
• Memory accesses are aligned or can be handled with unaligned loads
• The operation maps to available SIMD instructions

However, compilers are conservative and may miss optimization opportunities. Programmers can use intrinsics (direct SIMD instruction wrappers) or pragma hints to guide vectorization.

Performance Analysis

The speedup from vector processing depends on the vector length and the ratio of vectorizable to scalar code. For a vector operation on N elements with vector register length L:

• Startup time: Time to fill the pipeline (typically equal to pipeline stages)
• Steady-state: One result per cycle once pipeline is full
• Total time: Startup + N cycles (vs. N × scalar_cycles for scalar execution)

For long vectors, the startup cost is amortized, and speedup approaches the theoretical maximum of the vector width (e.g., 16x for AVX-512 with 32-bit data).

Applications

Vector processing excels in:

• Scientific computing: Matrix operations, fluid dynamics, weather modeling
• Media processing: Image filtering, video encoding, audio DSP
• Machine learning: Neural network inference (matrix multiplication, convolutions)
• Cryptography: AES encryption, hash computation (dedicated SIMD instructions)
• Database operations: Scanning, filtering, and aggregating columnar data

Key Takeaways

1. Vector processing applies one instruction to multiple data elements simultaneously, eliminating loop overhead
2. Classic vector processors use long vector registers and pipelined functional units for high throughput
3. Modern SIMD extensions (SSE, AVX, NEON) bring vector processing to mainstream CPUs with 128-512-bit registers
4. Vector masks enable conditional per-element execution within a single vector instruction
5. Chaining overlaps dependent vector operations for near-ideal pipeline utilization
6. Strip mining handles arrays larger than the vector register by processing fixed-size chunks in a loop
7. Auto-vectorization by compilers transforms scalar loops into SIMD instructions when dependencies allow