First Experience with SIMD Capabilities

SIMD technology has a wide range of applications in big data and machine learning. Why is Clickhouse fast? Why is NumPy fast? Both rely on the support of SIMD technology. So what exactly is SIMD? Let’s take a look.

SIMD, or Single Instruction Multiple Data, is a type of parallel processing technology supported at the CPU instruction level. The first time many of us heard this term was probably in a “Computer Organization” class:

To illustrate the difference, let’s first look at the simplest mode: Single Instruction Single Data (SISD). In this mode, a single-core CPU receives and executes one instruction. This instruction only loads one piece of data from a memory unit into a register and then processes it.

In SIMD mode, the CPU’s registers are usually quite large, for example, 128 bits, and the latest versions support up to 512 bits. If we use a 512-bit register, we can load 8 int64 numbers at once and perform calculations at a parallelism of 8:

Of course, there are also two other categories, MISD and MIMD, but we won’t go into detail here.

Intel CPU Support for SIMD

Intel CPUs provide support for SIMD through an expanded instruction set. There are three sets in total, in the order they appeared: MMX, SSE, and AVX:

We can check whether our processor supports these instruction sets through the Intel official website (link provided at the end of the article). Below, we take MacOS as an example to briefly demonstrate. We can check the CPU model using sysctl:

sysctl -a | grep brand 
machdep.cpu.brand_string: Intel(R) Core(TM) i7-1068NG7 CPU @ 2.30GHz
machdep.cpu.brand: 0

The query results show that mainstream SSE and AVX instruction sets are supported:

So how do we use these instruction sets? Intel provides a C language library along with detailed function documentation, named “Intel® Intrinsics Guide”

These functions have a clear naming convention, consisting of three parts:

1. _mm<bit width>: _mm 128 bits, _mm256 256 bits, _mm512 512 bits;

2. _<operation>: _add for addition, _sub for subtraction, _mul for multiplication, _div for division, and similarly for logical operations;

3. _<primitive type>: _epi16 for int16, _epi32 for int32, _ps for float32, _pd for float64

For example, if I want to see the addition under 256 bits, searching for _mm256_add_ will return a set of functions:

Next, let’s use these instructions to check the performance.

Preparation Work

Since we need to perform performance testing, the programming language is C/C++, so we choose google/benchmark as an auxiliary tool. The testing scenario involves performing addition on two arrays of 1 million entries, where the elements can be int32, float32, int64, etc. We will use float32 for testing.

Follow the “Installation” section on Github for google/benchmark, and ensure to execute the installation step:

sudo cmake --build "build" --config Release --target install

Writing Code:

First, we write a standard unit test code, using #include <immintrin.h> to leverage SIMD capabilities. The preparation work includes:

1. Initializing three arrays of length 1 million: a, b, and c, with _mm_malloc responsible for memory allocation.

2. Initializing arrays a and b.

The calculation logic is c = a + b, with the number of iterations controlled by benchmark::State &state. The code is as follows:

#include <immintrin.h>
#include <benchmark/benchmark.h>

constexpr int N = 1000000;

static void normal(benchmark::State &state)
{
  float *a = static_cast<float *>(_mm_malloc(sizeof(float) * N, 16));
  float *b = static_cast<float *>(_mm_malloc(sizeof(float) * N, 16));
  float *c = static_cast<float *>(_mm_malloc(sizeof(float) * N, 16));
  for (int i = 0; i < N; ++i)
  {
    a[i] = i;
    b[i] = 2 * i;
  }

  for (auto _ : state)
  {
    for (int i = 0; i < N; ++i)
    {
      c[i] = a[i] + b[i];
    }
  }

  _mm_free(a);
  _mm_free(b);
  _mm_free(c);
}

BENCHMARK(normal);

We name the file benchmark_float32.cpp. Compile and execute:

g++ -Wall -std=c++20 -msse4 -mavx512f -mavx512bw benchmark_float32.cpp -pthread -lbenchmark -o benchmark_float32

Since we need to support sse4 and avx512, we need to add -msse4 -mavx512f -mavx512bw during compilation. Running ./benchmark_float32 gives the following results:

2023-06-17T18:30:04+08:00
Running ./benchmark_float32
Run on (8 X 2300 MHz CPU s)
CPU Caches:
  L1 Data 48 KiB
  L1 Instruction 32 KiB
  L2 Unified 512 KiB (x4)
  L3 Unified 8192 KiB
Load Average: 3.24, 3.72, 4.09
-----------------------------------------------------
Benchmark           Time             CPU   Iterations
-----------------------------------------------------
normal        1821404 ns      1812256 ns          386

As of now, the test is running. Next, we will add support for 128-bit calculations. This requires three functions:

1. _mm_load_ps loads four packed float32 values into a __m128 type variable.

2. _mm_add_ps performs addition on two __m128 type variables.

3. _mm_store_ps stores a __m128 type variable into memory pointed to by a float32* pointer.

Assembled together, it looks like this:

for (int i = 0; i < N; i += 4)
{
  __m128 v1 = _mm_load_ps(a + i);
  __m128 v2 = _mm_load_ps(b + i);
  __m128 v3 = _mm_add_ps(v1, v2);
  _mm_store_ps(c + i, v3);
}

Since a __m128 type variable can hold 4 float32 values, we increment i by 4 each time.

Using the same method, we can include __m256 and __m512 in the tests, with the results as follows:

It can be observed that the execution performance of these extended instruction sets is quite good; however, due to the additional time required for loading and storing, there is no multiplicative speedup.

Similarly, we can test with int32 and int64, with the results as follows:

Looking at the Iterations metric, the higher the number, the faster the execution speed. We summarize the different types in a table:

Iterations	float32	int32	int64	float32-O3	int64-O3
normal	388	383	361	1541	516
sse128	573	709	345	1441	2716
avx256	943	1176	550	1435	2959
avx512	1791	1872	759	6611	2601

It can be seen that the iterations for float32 and int32 increase sequentially, while int64 remains roughly the same in sse128 and normal modes, with an increasing trend in avx256 and avx512. The possible reason is that in sse128 mode, the computational speed theoretically increases by 100%, but the time for loading and saving offsets the speed gain.

Additionally, after enabling the highest level of compilation optimization with -O3, the speedup for int64 under SIMD is very significant, while float32 shows noticeable speedup only in avx512 mode.

Besides simple arithmetic operations, SSE and AVX can support many forms of calculations, including but not limited to: bitwise operations, type conversions, comparisons, encryption algorithms, mathematical functions, statistical functions, random number generation, strings, etc. A complete list can be found in the “Intel® Intrinsics Guide”. As this is for learning purposes, not all these functions have been tested.

I asked ChatGPT about the “disadvantages of SIMD,” and the response was as follows:

1. Requires specific hardware support: SIMD instructions are supported by CPU hardware and require specific hardware to use. If the CPU does not support the SIMD instruction set, SIMD instructions cannot be used. 2. High coding complexity: Using SIMD instructions requires an in-depth understanding and proficiency with the instruction set, making the coding process relatively complex. 3. Data structure limitations: SIMD instructions are suitable for processing sequentially stored data and require data to be packed in a specific way. Therefore, in some cases, data structure conversions may be needed to use SIMD instructions. 4. Cannot handle branches: SIMD instructions operate on data streams and cannot directly handle branches; branches must be converted to data streams and handled in a specific manner. 5. Prone to precision errors: When using SIMD instructions for high-precision calculations, precision errors may occur due to the limited precision of floating-point numbers and potential conversions to other precision data types during processing.

From an application perspective, Clickhouse has inspired many big data processing frameworks to adopt SIMD capabilities, the introduction of the NumPy library, and widespread use in multimedia fields. The performance gains brought by SIMD are undeniable. As for Linus Torvalds’ complaints about 512-bit instructions, we can only smile knowingly.

What optimizations Clickhouse has made and how fully it utilizes SIMD capabilities will be supplemented later after further understanding.

Query CPU information: https://ark.intel.com/content/www/us/en/ark.html

The complete code will be released in the next article “[Code Appendix] First Experience with SIMD Capabilities”.