SIMD and Vector Processing Explained

What is SIMD? A Taxonomy of Parallelism

To formally understand SIMD, it's helpful to place it within a classic framework for classifying computer architectures known as Flynn's Taxonomy. This framework categorizes systems based on the number of instruction streams and data streams they can process simultaneously.

The video below, from a comprehensive computer architecture course by Dr. Onur Mutlu at Carnegie Mellon University, introduces this taxonomy and situates SIMD within it.

As you saw, the architectures are:

• SISD (Single Instruction, Single Data): This is the traditional sequential model we've been implicitly working with so far. One instruction operates on one piece of data.
• SIMD (Single Instruction, Multiple Data): One instruction operates on multiple pieces of data simultaneously. This is the focus of our lesson.
• MISD (Multiple Instruction, Single Data): Multiple instructions operate on a single stream of data. This is a rare architecture, sometimes seen in fault-tolerant systems.
• MIMD (Multiple Instruction, Multiple Data): Multiple processors or cores execute different instructions on different data. This is the model for multi-core and distributed systems, which we will cover later in the course.

Why SIMD? Exploiting Data Parallelism

The primary benefit of SIMD is its ability to exploit data parallelism—the same operation being performed across a large dataset. Think of adjusting the brightness of an image: you apply the exact same mathematical operation to every single pixel.

By executing one instruction that handles, for example, 8 or 16 pixels at once, the CPU dramatically reduces the overhead associated with fetching and decoding instructions. This leads to higher performance and better energy efficiency.

The next segment of the same lecture explains these benefits in more detail.

The performance gains are not just theoretical; they are substantial in practice, especially in data-intensive fields.

Vector Processing Architectures

Now that we understand the concept, let's look at how it's implemented in hardware. Historically, two main types of SIMD machines emerged: array processors and vector processors. The distinction lies in how they use hardware resources (space) and time.

• Array Processor: Uses multiple identical processing units to execute the same instruction on different data elements at the same time. It parallelizes in space.
• Vector Processor: Uses a single, deeply pipelined processing unit that executes an instruction on different data elements in consecutive clock cycles. It parallelizes in time.

The following video segment provides an excellent visual comparison of these two approaches.

While this is a purist's distinction, modern processors, especially GPUs, are effectively a hybrid of both. They have multiple parallel processing "lanes" (like an array processor) and each of those lanes is deeply pipelined (like a vector processor).

Essential Features for Vector Processing

To be truly programmable and effective, a vector processor needs more than just the ability to perform an ADD on a vector. It requires a set of specialized features to handle common programming constructs and data layouts.

Let's explore four of the most important ones:

1. Vector Registers, Length, and Stride: The hardware needs registers to hold the vectors of data. It also needs to know how long a vector is (Vector Length) and how the elements are laid out in memory. The distance between consecutive elements is called the stride. A stride of 1 means elements are contiguous, but if you're processing a column of a matrix stored in row-major order, the stride will be equal to the number of columns.
2. Conditional Execution (Masking): What happens if you have an if statement inside a loop you want to vectorize? if (A[i] > 0) { B[i] = ... }. SIMD processors handle this using a vector mask register. A comparison operation generates a bitmask (e.g., 1 if true, 0 if false), and subsequent instructions only execute for elements where the corresponding mask bit is set to 1.
3. Irregular Memory Access (Gather/Scatter): What if your memory access isn't a constant stride? For example, A[index[i]]. Vector processors support this with special gather and scatter instructions. A gather instruction loads data from addresses specified in an index vector into a dense vector register. A scatter instruction does the reverse.
4. Data Forwarding (Chaining): To maximize performance, the result from one vector functional unit (e.g., multiplier) should be directly "forwarded" to the input of the next (e.g., adder) without waiting for the entire vector operation to complete and be written back to a register. This is analogous to data forwarding in a scalar pipeline and is called vector chaining.

The next reading provides a concise summary of these concepts and shows how they are applied in practice with modern C++ intrinsics.

For a more in-depth architectural explanation of these features, you can refer back to the lecture by Dr. Onur Mutlu. The following sections are particularly relevant:

• Vector Registers, Length, and Stride: LINK, section 4 (25:32 - 31:28)
• Gather/Scatter Operations: LINK, section 7 (01:06:40 - 01:12:18)
• Vector Mask Registers: LINK, section 8 (01:12:18 - 01:18:47)

SIMD in Modern C++ Programming

So far, we've focused on the architectural concepts. How does a programmer actually leverage SIMD? There are three primary methods, ranging from easy-but-less-control to hard-but-full-control.

1. Auto-Vectorization: You write a standard C++ loop, and you rely on the compiler to recognize that the loop is parallelizable and automatically generate SIMD instructions for you. This is the easiest approach but is not always successful if the loop is complex.
2. Intrinsic Functions: These are special functions provided by compiler toolchains that map almost directly to a single SIMD assembly instruction (e.g., _mm256_add_ps for a vector add of 8 floating-point numbers). This gives you explicit control over vectorization while still letting the compiler handle low-level details like register allocation. This is the most common approach for manual SIMD optimization.
3. Assembly Programming: You write the SIMD instructions directly in assembly language. This provides the ultimate level of control but is complex, error-prone, and not portable.

The following video provides an excellent summary of these three approaches and demonstrates the significant performance difference between a standard C++ loop and one written with intrinsics.

To use intrinsics, you work with special data types that represent the contents of a vector register. For example, on a modern CPU with the AVX2 instruction set, you'd use the __m256 data type, which holds eight 32-bit floating-point numbers.

#include <immintrin.h>

// Scalar version
void scalar_add(float* a, float* b, float* c, int n) {
    for (int i = 0; i < n; ++i) {
        c[i] = a[i] + b[i];
    }
}

// SIMD version using AVX intrinsics
void simd_add(float* a, float* b, float* c, int n) {
    // We process 8 floats at a time
    for (int i = 0; i < n; i += 8) {
        // Load 8 floats from array 'a' into a vector register
        __m256 vec_a = _mm256_loadu_ps(&a[i]);
        // Load 8 floats from array 'b' into another vector register
        __m256 vec_b = _mm256_loadu_ps(&b[i]);
        
        // Add the two vectors
        __m256 vec_c = _mm256_add_ps(vec_a, vec_b);
        
        // Store the 8 resulting floats into array 'c'
        _mm256_storeu_ps(&c[i], vec_c);
    }
}

This example shows the core pattern: load data into vector registers, perform vector operations, and store the results back to memory.

Conclusion

In this lesson, we explored data-level parallelism through SIMD, a key technique for single-core performance optimization. You've seen that it's not just a theoretical concept but a practical tool used in modern CPUs to achieve massive speedups on data-parallel tasks.

Key Takeaways:

• SIMD (Single Instruction, Multiple Data) is a parallel processing model where one instruction operates on multiple data elements simultaneously.
• It leverages special hardware, including wide vector registers and a Vector Processing Unit (VPU).
• The key advantage is exploiting data parallelism, which reduces instruction processing overhead and improves performance and energy efficiency.
• Key architectural features like masking enable conditional logic (if-then-else), while gather/scatter instructions handle irregular memory accesses, making vector processors more general-purpose.
• Programmers can leverage SIMD through compiler auto-vectorization or by using intrinsic functions for explicit control.

Preview of the Next Lesson

We've discussed the concept of auto-vectorization, where the compiler does the heavy lifting for us. But how do we know if the compiler was successful? In the next lesson, we will get our hands dirty. The learning outcome will be to use compiler flags and diagnostic reports to enable and verify auto-vectorization of a C++ loop. We'll write a simple loop and learn how to coax the compiler into vectorizing it and, just as importantly, how to read the compiler's output to confirm that it did.