使用向量操作

使用向量操作

现代微处理器具有向量指令，使得可以同时对向量的所有元素进行操作，也称为单指令多数据操作（SIMD）
每个向量的总大小可以是64位（MMX），128（XMM），256（YMM）和512（ZMM）；

大型数据集中，对多个数据元素执行相同的操作并且程序逻辑允许并行计算时，向量操作非常有用。

而本质上是串行的算法，比如大多数排序操作，以及严重依赖于查找表涉及大量数据变换的算法(例如许多加密算法)或许也不太适合向量操作

向量操作使用一组特殊的向量寄存器，若SEE2指令集可用，每个向量寄存器等最大大小为128（XMM），若AVX指令集可用，则为256位（YMM），若AVX512指令集可用，则为512位（ZMM）向量中的元素数量取决于元素的大小和类型。

较新的处理器上，向量操作特别快，许多处理器可以像标量一样计算向量，通俗的说，意味着像处理单个元素一样快的处理向量中的所有元素。

数据元素越小，向量运算的使用优势及更大，比如我们可以同时进行四个float加法，而只能进行两个double运算。
在现代cpu中，如果数据很适合向量寄存器，那么向量运算几乎总是有利的，而如果要将正确的数据放入正确的向量元素中需要进行大量的数据操作，那么可能就没有优势了。

AVX指令集和YMM寄存器

128位的XMM寄存器在AVX指令集中被扩展为256位的YMM寄存器，允许更大的浮点向量，还有一些别的优势可以一定程度上提高性能，AVX2指令集也允许256位整数向量。

为AVX指令集编译的代码只有在CPU和操作系统都支持AVX的情况下才能运行，

某些intel处理器上混合使用和不使用AVX指令集编译的代码会有问题，从AVX 代码切换到非AVX代码时，由于YMM寄存器的变化，会造成性能损失，因此应该切换时调用_mm256_zeroupper()来避免这种损失

AVX512指令集和ZMM寄存器

64位模式下，向量寄存器数量有32个，而32位模式下只有8个，因此最好将AVX512代码译为64位模式

AVX512指令集还添加了一组掩码寄存器，会用作bool变量，几乎任何向量指令都可以配合掩码寄存器操作，只有当掩码寄存器对应位为1时才会就向量元素（类似位运算）

自动向量化

好的编译器（如Gnu，Clang，Intel）编译器可以在并行性明显的情况下自动使用向量操作，例如： 

1
2
3
4
5
const int N = 1024;
int a[N], b[N];
for(int i = 0; i < N; i ++) {
    a[i] = b[i] + 2;
}

一个好的编译器会在指定SSE2或者更高指令集的时候使用向量操作来优化这个循环，根据使用指令集的不同，将4、8或者16个元素一次读取到向量寄存器中，与另外一个向量寄存器（2，2，2、、、）做加法并将结果存储到a中。

循环计数最好是能被每个向量的元素数整除，必要的时候可以在数组末尾添加多余的元素使得数组的大小成为向量大小的倍数。

若数组是通过指针访问，可能存在缺点，例如：

1
2
3
4
5
void AddTwo(int * __restrict aa, int * __restrict bb) {
    for(int i = 0; i < N; i ++) {
        aa[i] = bb[i] + 2;
    }
}

如果数组按照向量大小对齐，XMM、YMM、ZMM寄存器分别为16、32、64字节则性能最佳，AVX指令集之前，指令集下的高效向量操作要求数组按照可以被16整除的地址排列。

采用非指针版本的例子中，编译器可以根据需要对数组进行对齐，但是在后面通过指针访问的版本中，编译器无法确定数组是否正确对齐，循环依旧可以向量化，但是代码效率会降低，因为编译器必须对未对齐的数组采取额外的预防措施。这种情况下可以做以下工作：

  • intel编译器可以使用#pragma vector aligned或者_assume_aligned指令，告诉编译器数组是对齐的并确保他们是对齐的。
  • 将函数声明为inline，这使编译器可能去掉引用和指针
  • 可能情况下，启用向量大小最大的指令集，AVX和之后的指令集对于对齐的限制少，无论是否对齐，代码都很高效。

如果满足以下条件，自动向量化效果最好：

  • 使用支持自动向量化的编译器，如Gnu、Clang、Intel等
  • 使用编译器的最新版本，编译器在向量化方面越来越好
  • 使用是当地编译器选项来启用所需的指令集，对于Linux(-msse2, -mavx等)
  • 使用限制较少的浮点选项
  • 对于SSE2，数组和大结构地址按照16字节对齐，AVX最好按照32对齐，AVX512最好按照64字节对齐
  • 循环计数最好是能够被向量中元素数整除的常数
  • 数组或结构体通过指针访问的话，inline __restrict或者显式告诉编译器是对齐
  • 在向量元素级别上最小化分支的使用
  • 避免在向量元素级别上使用查找表

使用指令集函数

这部分颇有一些复杂，暂时指望编译器自动向量化先

数据对齐

1
2
3
4
5
6
7
#ifdef _MSC_VER
// if Microsoft compiler
#define Aligned(X) __declspec(align(16)) X
#else
//Gnu
#define Aligned(X) X __attribute__((aligned(16)))
#endif

查表向量化

略

使用向量类

略

希望之后通过学习写一个自己用的简单的向量类

为向量化转换串行代码

1
2
3
float a[100];
float sum = 0;
for(int i = 0; i < 100; i ++) sum += a[i];

上面的代码时串行的，因为每次迭代的sum值都依赖于前一次迭代后的sum值。

诀窍是将循环按n展开并重组织代码，每个值依赖n个位置之前的值，其中n是向量中元素的数量，例如如果n=4，那么有：

1
2
3
4
5
6
7
8
9
float a[100];
float s0 = 0, s1 = 0, s2 = 0, s3 = 0, sum;
for(int i = 0; i < 100; i += 4) {
    s0 += a[i];
    s1 += a[i + 1];
    s2 += a[i + 2];
    s3 += a[i + 3];
}
sum = (s0 + s1) + (s2 + s3);

现在s0 s1 s2 s3可以组合成一个128位的向量，因此可以在一个操作中做4个加法。

如果使用fast math选项并指定更高指令集的选项，好编译器会自动优化成展开形式并将代码向量化。

一个头：

1
#pragma GCC optimize("Ofast, unroll-loops, ffast-math")

总结

如果代码具有并行性，那么使用向量可以达大大提高速度，增益取决于每个向量的元素数量。最简单和最干净的解决方案是依赖编译器的自动向量化，我们要做的就是使用适当的指令集和限制少的浮点选项。

使向量化有利的因素

  • 小数据类型：char short int float
  • 大数组中对所有数据进行相似的操作
  • 数组大小可以被向量大小整除
  • 在不可预测的分支中选择两个简单表达式
  • 向量指令集可用时，如AVX, AVX2, AVX-512
  • 数学向量函数库
  • 使用gnu clang intel编译器

    向量化的不利因素

  • 大数据类型: int64_t double
  • 未对齐数据
  • 额外的数据转换
  • 编译器没有足够的指针对其和别名信息
  • 在指令集中缺少合适的向量操作（能用新的就用新的，或者是用次新版）
  • 执行单元小于向量寄存器大小的老CPU

对于程序员来说，向量化的代码更不容易编写，因此也更容易出错，因此，向量化代码最好放在可重用并且经过良好测试的库模块和头文件中