Welcome back! In our last session, you successfully implemented naive C functions for Euclidean distance and Cosine similarity. These straightforward implementations serve as our correct, functional baseline. But as someone interested in high-performance systems, you know that "functional" is just the starting point. Our goal is to make these calculations dramatically faster.
To do that, we need to move beyond writing simple, sequential code and start thinking like the CPU. Modern processors are marvels of parallel engineering, capable of executing many operations simultaneously. This lesson delves into the two fundamental concepts that unlock this power: Instruction-Level Parallelism (ILP) and Single Instruction, Multiple Data (SIMD). Understanding these concepts is the theoretical key to transforming our baseline functions into highly optimized, high-frequency-trading-grade code.
The Iron Law of Performance
Before diving into CPU architecture, let's establish a mental model for performance. It's tempting to think performance is all about clock speed (GHz), but the reality is more nuanced. The Iron Law of Processor Performance gives us a much more powerful way to reason about speed.
One Law to Rule Them All: The Iron Law of Software ...
This article by Abhinav Upadhyay provides an excellent framework for understanding low-level optimizations. It adapts a hardware concept for software engineers.
Read the introduction, the section on the hardware law, and the section adapting it for software. Focus on understanding the three core components and how they relate: Instruction Count: The total number of instructions your program executes. IPC (Instructions Per Cycle): How many instructions the CPU can complete, on average, in a single clock cycle. This is the inverse of CPI (Cycles Per Instruction). Clock Cycle Time: The duration of a single CPU clock cycle (the inverse of frequency). As you'll see, every optimization we discuss is a trade-off between these three factors.
The core idea is that total execution time is a product of these three variables. To make our code faster, we must reduce the number of instructions, increase the number of instructions executed per cycle, or decrease the clock cycle time (increase frequency). With this framework in mind, let's see how CPUs are designed to maximize performance.
Instruction-Level Parallelism: The CPU's Inner Assembly Line
Even on a single CPU core, modern processors don't execute instructions one by one, waiting for each to finish completely before starting the next. Instead, they use several techniques to run multiple instructions in parallel. This is the essence of Instruction-Level Parallelism (ILP).
Pipelining
The most fundamental form of ILP is pipelining. Think of it as an assembly line. Executing a single instruction involves several stages, such as fetching it from memory, decoding it, executing the operation, and writing the result back to a register. Instead of processing one instruction through all stages before starting the next, a pipelined processor overlaps them. As one instruction moves to the "execute" stage, the next instruction is already in the "decode" stage, and another is being "fetched."
Superscalar and Out-of-Order Execution
Modern CPUs take this even further. A superscalar processor has multiple pipelines and duplicate execution units (e.g., several ALUs for integer arithmetic, several FPUs for floating-point math). This allows it to issue and execute more than one instruction in the same clock cycle, provided those instructions are independent of each other.
To keep these multiple execution units as busy as possible, processors also use out-of-order execution. The CPU looks ahead in the instruction stream, finds independent instructions, and executes them as soon as their data and an appropriate execution unit are available, even if that's not their original order in the program.
These concepts are critical for getting the most out of a single core. The following article provides a clear explanation of how they work together.
Instruction-Level Parallelism - Algorithmica
This article from Algorithmica clearly distinguishes between multi-core parallelism and the parallelism that exists inside a single core.
Read the introduction, the section on Instruction Pipelining, and the brief description of superscalar architecture. Notice how these techniques aim to increase the Instructions Per Cycle (IPC) from our Iron Law equation.
ILP is a general strategy the CPU uses automatically to speed up your code. However, there's another, more explicit form of parallelism we can leverage for our vector math problem: SIMD.
Data Parallelism with SIMD
While ILP deals with executing different instructions in parallel, data parallelism is about performing the same operation on multiple pieces of data simultaneously. The most common architecture for this on modern CPUs is SIMD: Single Instruction, Multiple Data.
Flynn's Taxonomy
To understand where SIMD fits, it's helpful to look at Flynn's Taxonomy, a classic classification of computer architectures based on their instruction and data streams.
- SISD (Single Instruction, Single Data): This is the traditional sequential model. One instruction operates on one piece of data at a time. The naive C loops you wrote in the last lesson are a perfect example of SISD-style programming.
- SIMD (Single Instruction, Multiple Data): This is the data-parallel model. A single instruction is issued, but it operates on an entire vector of data at once. For example, a single SIMD
addinstruction might add eight pairs of floating-point numbers simultaneously. - MIMD (Multiple Instruction, Multiple Data): This describes systems with multiple independent processors, like multi-core CPUs. Each core can run different instructions on different data. This is what people typically mean by "multithreading" or "parallel processing."
- MISD (Multiple Instruction, Single Data): This is a rare architecture, sometimes used in fault-tolerant systems where multiple processors perform different operations on the same data for verification.
Our project will leverage both SIMD (within a core) and MIMD (across cores, in a later module). For now, our focus is on SIMD.
How SIMD Works
SIMD is implemented using special wide registers in the CPU (e.g., 256 bits or 512 bits wide) and a special set of instructions that operate on them. A 256-bit register can hold eight 32-bit floating-point numbers. A single SIMD instruction can then perform an operation—like addition, multiplication, or subtraction—on all eight of these numbers in parallel.
This is a perfect match for our vector math problem. Instead of looping through a vector and processing one float at a time, we can process 8 floats at a time. The following video gives a great introduction to the concept and its history on x86 processors.
SIMD and vectorization using AVX intrinsic functions (Tutorial)
This tutorial by Joel Carpenter introduces vectorization from a practical perspective.
Watch the introduction from the beginning to the end of the overview to get a feel for what vectorization is. Then, watch the section covering Flynn's taxonomy and the history of x86 SIMD instruction sets (MMX, SSE, AVX, etc.). This will give you the vocabulary to understand the specific technologies we'll be using.
SIMD and The Iron Law
How does SIMD affect our performance equation? It's a powerful lever, but one with trade-offs.
One Law to Rule Them All: The Iron Law of Software ...
Let's return to the "Iron Law" article to analyze SIMD through its lens.
Read the section on SIMD Vectorization and its impact on instruction count. Then, skim the subsections on its impact on IPC and Clock Cycle Time.
As the article explains, SIMD has a dramatic effect:
- Instruction Count: Massively Reduced. This is the primary benefit. One instruction does the work of many (e.g., 8, in the case of 256-bit vectors of floats). This is a huge win.
- IPC (Instructions Per Cycle): Mixed Impact. SIMD instructions can be more complex and take longer to decode, which can sometimes lower IPC.
- Clock Cycle Time: Potentially Increased. Heavy use of certain SIMD instructions (like AVX2/AVX-512) can cause the CPU to slightly lower its clock frequency to manage power and heat. This increases the clock cycle time, working against our performance goal.
The key is that the massive reduction in instruction count almost always outweighs the potential negative effects on IPC and clock speed for data-parallel workloads like ours.
Conclusion
In this lesson, we've pulled back the curtain on how modern CPUs achieve their incredible performance. You've moved from seeing the processor as a simple sequential executor to understanding it as a complex parallel machine.
Key Takeaways:
- Performance is best understood through the Iron Law, as a trade-off between instruction count, instructions per cycle (IPC), and clock cycle time.
- Instruction-Level Parallelism (ILP) refers to the techniques a CPU core uses to execute multiple different instructions concurrently, such as pipelining and superscalar execution. This primarily boosts IPC.
- SIMD (Single Instruction, Multiple Data) is a form of data parallelism where a single instruction operates on multiple data points at once. This primarily slashes the total instruction count.
- Our vector math problem is a perfect candidate for SIMD because calculating distances involves applying the same sequence of arithmetic operations to all components of the vectors.
You now have the conceptual foundation needed to start writing truly high-performance code. In our next lesson, we will put this theory into practice. You will use AVX2 intrinsic functions—a C/C++ interface to the CPU's SIMD instructions—to rewrite the Euclidean distance function and directly measure the speedup against our naive baseline.