x86 and SIMD programming Part0: Background

mwish

2022-11-05

作为指令集并行的一部分，SIMD 已经被大幅度用来提高程序的性能了。而在数据库系统中，分析型数据库也大量使用 SIMD 来做 vectorize，来提高性能。本栏尽量介绍一下基本的 SIMD 的历史、需求和基础，然后后面也会讲到 AVX2 的入门、xsimd 库和让编译器自动来做向量化。在这里，了解硬件和指令集是比较重要的组成部分，而虽然 ARM 平台也有自己的 SIMD 指令集，但作为 db 研发，我们还是以 x86 的为准（倒不是看不起 arm，就单纯先不花时间吧）。

CPU 有一些技术来帮忙优化，比如 Hyper Threading / Super Scalar，CPU 也有专门的 SIMD 处理单元。这使得人们可以给出更好的实现。在数据库里面，近年来卷到爆炸的分析型数据库领域也希望能够利用好 SIMD。

言归正传，程序员早期其实是没那么懂并发编程的，原因大概在 perfbook 那节也讲过，以前硬件提升都是可以直接反映到程序上，啥都不做性能就提升了，但是现在的程序员必须 get hands dirty，来了解一下下层的抽象，来一把捅下去获得性能。同时，有的时候性能、生产力、通用性是个不肯能三角，这个在 perfbook 那节也有提到。这话有点太俗了，下面的图其实是比较好理解的：

0EDCEC2A-2361-4560-91DD-68FE51B150D8

这里还有一张关于内存带宽和频率有关的图：

5FC1C556-0F2B-474B-B12E-4A6EAC8405FF

（实际上，可以看 ref 4，单线程已经跑不满内存带宽了，不过内存带宽仍然受到限制）

关于性能，这里还有一些 hints:

cache miss 可能很重，可能相当于几十几百条指令，当然，IO 就更重了
需要利用 SIMD、多核、多线程甚至 GPU 甚至特殊硬件来改善性能
写 fastcode 可能涉及代码量大、多线程协调、不跨平台（比如单平台 SIMD 的问题），同时，Compiler 可能也不一定能够生成合适的代码。多线程必不多说，SIMD 可能也没法生成很好的选项，实际上很多地方（例如 TiFlash、ClickHouse）都是写便于向量化的代码，尽量让编译器自动向量化然后加一些编译参数来检查，一些关键路径也得自己手搓 SIMD 或者用 SIMD 库。

18C67A41-F361-4853-8F9E-E1F4E5F61D01

硬件发展和硬件基础

D8C704E9-F29C-48E4-8B8E-E9387C8DBE44

X86-64 平台是 x86-32 的一个扩展。当然，这里 x86 指的是 ISA，与之等同的是 RISC-V、ARM、POWER、MISC 等。而不同的是下层的实现和 microarch，比如 cacheline 的长度。x86 是一个 CISC 指令集，但是它的指令会被处理成 RISC 的，以获取性能：

AFA12812-C13B-4C01-BA95-E6E92971B7E5

下面是一个 Intel 芯片的图，来自 wiki:

Intel 在 06 年提出 tick-tock 模型: Tick 一次代表制程（Process）更新，利用硬件提升；Tock 代表作出新的架构。这个策略后来被更新为 Process–architecture–optimization 模型：

A5C7244A-F0A4-4EFE-8C73-B02694C904D8

最早出现的芯片是 16位的 Intel 8086, Intel 8088, Intel 80186, Intel 80286。游戏的开端是 1985 年的 Intel 80386，它最初采用了 32位的 IA-32 架构（此外，还有个名字很像的、创造者同样包含 Intel 的 IA-64，则是另一个指令集。），它有各种寄存器、4GB 的虚拟地址空间、基于页的虚拟内存。80386 有独立的 80387 FPU。在 80486 中，这些被集成到了系统中，即 x87 FPU。实际上，FPU 和 SIMD 很多处理的逻辑类似，一定程度上，它们是被整合到一起的。

x86-32 平台在 93-95 年推出的 P5 microarchitecture 中，MMX 技术出现，它用 64-bits 位宽的寄存器来同时处理多个整数。

在 P6 架构的 Pentium Pro (1995) 和 Pentium II (1997) 中，Intel 引入了 superscalar，decode / dispatch / execute 可以乱序执行。Pentium 有个你可能很熟悉的名字，叫「奔腾」。

99 年引入的 P6 架构的 Pentium III 中，SSE（Streaming SIMD extensions）指令集被引入了，它加入了一组 128bits 的寄存器，可以进行 SIMD 的单精度浮点运算.

一年后，2000 年，Intel 推出了 Netburst 架构，并引入了 SSE2，它补全了 SSE 处理双精度浮点数的能力，同时，它在 SSE 引入的寄存器上补齐了整数运算的能力。04 年，SSE3 推出，并运行在制程 90nm 的 Pentium 和 Xeon 架构上，这一代架构有 hyper-threading. 06年推出的 Core 架构（酷睿）做了不少优化、降低了能耗，同时引入了 SSSE3 指令集和 SSE4.1，他们没有引入新的寄存器，同时，hyper-threading 也被去除了。2008 年的 Nehalem 再次引入了 hyper-threading，同时也引入了 SSE 最后的 SSE4.2 指令集，这个指令集扩展了 SSE 寄存器上的字符串/文本处理。

2011 年 Intel 推出了 Sandy Bridge 架构，它引入了 Advanced Vector Extensions (AVX) 这一 SIMD 指令集，它用 256-bits 的寄存器来处理数据，这提升了寄存器的宽度，一定程度上减小了开销.

2013 年 Intel 推出了 Haswell 架构，同时，它引入了 AVX2，实际上，现在比较常用的编译参数包含 -mavx2 -march=haswell，同时，它提供了一组 data transfer 相关的指令：

broadcast: 把一个值广播到多个位置
gather: 把多个不连续位置的内存加载
permute: 给出一组 index, 按照 index 来加载数据

Haswell 还引入了 FMA 操作，FMA 代表 Fused Multiply-Add, eg:

/* matrix multiplication; A, B, C are n x n matrices of doubles */ 
for (i = 0; i < n; i++)
  for (j = 0; j < n; j++) 
    for (k = 0; k < n; k++) 
      C[i*n+j] += A[i*n+k]*B[k*n+j];