Introduction
The previous two articles introduced the topics of CPU and CPU Cache, with performance being a perpetual core concern. We also discussed the three walls faced in optimizing CPU performance:
-
The power wall Currently, to increase computation speed by 30%, it requires double the voltage and heat, and this design approach cannot satisfy mobile devices and is not sustainable in the long run.
-
The memory wall The performance gap between memory and CPU is widening.
-
The IPL wall Most applications currently do not have good parallelization design (instruction level).
Regarding the first wall, the article “The Free Lunch Is Over” tells us that this performance optimization has reached its limit. For the second wall, CPU Cache serves as a buffer to address the performance gap. Today, we will look at solutions for the third wall.
Modern CPUs increasingly rely on parallel technology to achieve high performance. With the development of hardware technologies such as multi-core, hyper-threading, and instruction sets supporting multi-task operating systems, multi-threading seems to be a silver bullet for performance optimization. However, few people understand the parallel technology at the CPU instruction level: within a single cycle, the CPU applies a set of vector operations, executing the same instruction on 4 or 8 input data, producing corresponding 4 or 8 results, which is called SIMD (Single Instruction, Multiple Data).
SIMD technology was first applied in supercomputers, such as the CDC Star-100. In 1996, Intel introduced the MMX extension for the X86 instruction set, marking the first commercial hardware support for SIMD technology. In 1999, Intel launched SSE (Streaming SIMD Extensions) in the P3, based on 128-bit registers, providing 70 assembly instructions for vector data of 4 floats. AVX (Advanced Vector Extensions) is Intel’s SSE extended architecture, essentially making CPUs more like GPUs.
Practice
Next, let’s see how to use SSE in C++.
union { __m128 result_sum4; float result_sum[4]; };
result_sum[0] = result_sum[1] = result_sum[2] = result_sum[3] = 0.0f;
result_sum4 = _mm_set_ps1(0.0f);
In the above union, __m128 is a vector that corresponds to 4 float values. Similarly, there are two other variable types __m128i and __m128d, corresponding to int and double, respectively. After assigning values to the variable result_sum, result_sum4 and result_sum share the same memory block. Of course, you can also initialize result_sum4 using the SSE instruction _mm_set_ps1.
Data Parallelism
for (int i = 0; i < 1000; i++)
{
pResult[i] = pL[i] + pR[i];
}
// SSE2.0
for (int i = 0; i < 1000; i += 4)
{
result_sum4 = _mm_add_ps(
_mm_setr_ps(pL[i], pL[i + 1], pL[i + 2], pL[i + 3]),
_mm_setr_ps(pR[i], pR[i + 1], pR[i + 2], pR[i + 3]));
pResult[i] = result_sum[0];
pResult[i + 1] = result_sum[1];
pResult[i + 2] = result_sum[2];
pResult[i + 3] = result_sum[3];
}
In the above code, a for loop sums two arrays. In SSE, we achieve synchronous operations on four elements using the _mm_add_ps instruction. Similarly, SSE also provides _mm_sub_ps ，_mm_mul_ps，_mm_div_ps for subtraction, multiplication, and division, respectively.
Conditional Judgement
Next, let’s look at a piece of code for a conditional statement:
int fun(floatx)
{
if (x < 0.1f)
{
return 0;
}
elseif (x > 0.9f)
{
return 1;
}
else
{
return -1;
}
}
__m128i fun4(__m128 x4)
{
__m128 mask = _mm_cmpge_ps(x4, _mm_set_ps1(0.1f));
__m128 fV1 = _mm_blendv_ps(_mm_set_ps1(0.0f), _mm_set_ps1(-1.0f), mask);
mask=_mm_cmpge_ps(_mm_set_ps1(0.9f), x4);
__m128 fV2 = _mm_blendv_ps(_mm_set_ps1(2.0f), _mm_set_ps1(0.0f), mask);
__m128i result4 = _mm_cvtps_epi32(_mm_add_ps(fV1, fV2));
return result4;
}
Here, _mm_cmpge_ps is equivalent to an if statement, _mm_blendv_ps corresponds to the ? : statement, and _mm_cvtps_epi32 is responsible for converting float to int. Thus, using the corresponding SSE implementation, we can perform logical judgments on four elements at once.
From a learning perspective, SSE instructions are not complex; they provide a set of instruction sets for common mathematical operations and logical judgments. Initial use may feel slightly uncomfortable, but the learning cost is relatively low. If you’re interested, you might want to learn about the corresponding SSE instructions for methods like max, min, sin, and power, and you can visit the following website for the corresponding instruction descriptions: https://software.intel.com/sites/landingpage/IntrinsicsGuide/#techs=MMX,SSE,SSE2,SSE3,SSSE3,SSE4_1,SSE4_2,AVX,AVX2,FMA,AVX_512
Tips
It seems that using SSE is not complicated; it’s just a matter of transforming the commonly used + – * / in C++ into a data-parallel approach by replacing them with the corresponding SSE instructions. Logical judgments may seem a bit complex, but they are just small techniques. This was my initial thought when I first wrote SSE code, and I believe many of you can relate. However, when I modified an algorithm for backpropagation neural networks using SSE2.0 instructions, I found that the time only reduced to about 70%, not the promised quarter. I felt deeply deceived.
Therefore, I conducted simple tests on these basic operations, running a for loop 100,000,000 times for the simplest arithmetic operations and exponentiation, and obtained the following performance comparison:
The conclusion is that addition, subtraction, multiplication, and division are roughly equivalent, while exponentiation shows a significant improvement. I checked the corresponding assembly under Release and found that the compiler automatically compiles such simple for loops into SSE instructions. Therefore, for such code, we do not need to modify it, and our modifications may not be better than what the compiler wrote; in fact, it may even slow down. This is because the exp function does not have a direct corresponding SSE instruction; it is a third-party library function I found, which accounts for the significant performance improvement.
Key Point 1: 20% of the code will consume 80% of the time, so finding the most computationally intensive and complex parts is the focus of our code modification. If we are unsure whether the optimization is effective, we can only practice to gain knowledge.
Additionally, using the SSE instruction set requires merging 4 floats into one __m128, which is a very frequent operation that requires calling instructions such as _mm_setr_ps or _mm256_loadu_pd. During this process, initializing these variables also takes time, and we also need to convert the results back to 4 floats. Whether this cost can be avoided is a question.
Here, we can save such initialization time costs by using pointer casting, as shown in the following code:
__m128* ptrLeft = (__m128*)&pValueLeft[i];
However, there is a requirement here: the variable pValueLeft must be 16-byte aligned, while a typical float array only guarantees 4-byte alignment. Therefore, when declaring variables, we need to explicitly specify 16-byte alignment. C++11 provides alignas to ensure array alignment, while pointer types must ensure byte alignment using the _aligned_malloc method.
Moreover, since SSE is designed for parallel processing of four float data, there is an annoying situation: if the loop length is not divisible by 4, the remaining part will not be modified, and we still need to fill in empty values before performing another parallel computation. This is a tedious choice, and it makes the code look inelegant, with too many “exception” checks. My suggestion is to restructure the data layout to ensure that all arrays are divisible by 4.
This is a significant improvement because the newly added “remainders” may interfere with the calculation process and change the values of elements in the array. Therefore, it is best to design the data layout correctly during the design phase to avoid issues caused by additional elements during restructuring that could compromise the accuracy of computations.
Key Point 2: Optimize data layout, ensure the first address of the array is 16-byte aligned, and the length is divisible by four. AVX?
By now, we have covered the key points of SSE coding, but we are different; we are programmers who have learned about Cache. The previous chapter had an example of nested for loops that demonstrated that row-major efficiency is far superior to column-major because the former is contiguous in memory. SSE primarily targets data parallelism for computation-intensive areas (such as images, neural networks, etc.), so we need to pay special attention to such code during our modifications. For example, consider the following code:
for (inti = 0; i < NUMHIDDEN4; i++)
{
// get error gradient for every hidden node
errorGradientsHidden[i] = GetHiddenErrorGradient(i);
// for all nodes in input layer and bias neuron
for (intj = 0; j < INPUTSIZE4; j++)
{
constintweightIdx = GetInputHiddenWeightIndex(j, i);
// calculate change in weight
deltaInputHidden[weightIdx] = errorGradientsHidden[i] * weightIdx;
}
}
Here, GetInputHiddenWeightIndex(j, i) is column-major, which is not ideal. From an optimization perspective, there is significant room for improvement:
for (inti = 0; i < NUMHIDDEN4; i += STEP_SSE)
{
// get error gradient for every hidden node
errorGradientsHidden[i] = GetHiddenErrorGradient(i);
}
// for all nodes in input layer and bias neuron
for (intj = 0; j < INPUTSIZE4; j++)
{
for (inti = 0; i < NUMHIDDEN4; i += STEP_SSE)
{
const int weightIdx = GetInputHiddenWeightIndex(j, i);
deltaInputHidden[weightIdx] = errorGradientsHidden[i] * weightIdx;
}
}
Here, the for loops are split, and the order of i and j is swapped, which does not affect the final computation result but ensures that memory access is contiguous. Then, both for loops can be modified for data parallelism.
Key Point 3: When optimizing with SSE, always remind yourself whether the code is executed with contiguous memory and whether there is room for modification.
Finally, I want to say that while learning SSE is not difficult, there are many comprehensive applications in practice, and there may be compatibility issues between different CPUs with newly added instruction sets. Therefore, I do not recommend writing your own, but rather using some professional third-party libraries. The benefit is that you do not have to maintain and upgrade it yourself, while logically reducing coupling. Our focus is not on writing our own SSE/AVX libraries.
Key Point 4: Professionals should do professional things. Based on our depth of understanding of SSE and our code needs, we should reasonably transplant VCL (vector class library) to better utilize external resources.
Conclusion
This concludes the introduction to SIMD. The theory is not complex, but practice requires attention to various possible points. So far, we have discussed CPUs, the significant value of Cache in performance optimization, and learned about SIMD technology for data parallelism.
In short, the core of the CPU is the optimization of data computation. The next chapter is the last article about the CPU, DOD (Data Oriented Design), which will provide an overall understanding of the conflict between modern CPUs and object-oriented programming, and how as C++ programmers, we can critically understand the gains and losses of object-oriented programming from a larger dimension to write our code.