SIMD介绍

数据的移动：在向量寄存器中移入移出
算数计算：能够在多个数据项上计算（比如2 doubles, 4 floats, 16 bytes） ADD, SUB, MUL...
逻辑指令：能够在多个数据项上进行逻辑运算，ADD, OR...
比较指令：在多个数据项上进行比较(==,<,>...)
Shuffle指令：在SIMD寄存器之间移动数据
转换：数据在x86和SIMD寄存器间进行转换
Cache控制：把数据从SIMD寄存器直接移动到内存而绕过CPU cache

SMID优缺点
优点：算法如果能够向量化可以获得显著地性能提升和对资源的利用率
缺点：用SIMD实现一个算法主要还是手动过程；SIMD会限制数据对齐alignment；把数据收集到SIMD寄存器并放到正确的位置很难效率也低。

针对上面的缺点，有三种解决方法
使用简单<--->编程控制

自动矢量化：编译器会识别循环中的指令能不能重写为向量化的操作。这只在简单的循环中起作用，但是在数据库操作中是很少见的。需要硬件支持SIMD指令

void add(int *X,
                    int *Y,
                    int *Z) {
    for (int i=0; i<MAX; i++) {
    Z[i] = X[i] + Y[i];
    }
}

这个循环不能自动矢量化。XYZ可能指向同一个地址，那么对于循环中的指令它们就是有关联的，对于编译器它不知道应该直接写Z并且重写XY，还是按照顺序执行。

编译器提示：用额外的信息告诉编译器这部分代码是可以安全的矢量化的。
实现上，可以给出关于内存地址的明确信息；或告诉编译器忽略向量依赖。

void add(int *restrict X,
                    int *restrict Y,
                    int *restrict Z) {
    for (int i=0; i<MAX; i++) {
        Z[i] = X[i] + Y[i];
    }
}

这里的restrict关键字就是告诉编译器XYZ在内存中不同的位置。
或者是在void add(int *X, int *Y, int *Z){后面加#pragma ivedp，忽略循环内的向量依赖（需要自己判断是否正确）。

Explicit矢量化：用CPU内部函数手动处理SIMD寄存器之间的数据并执行矢量化执行。
移植性差
__mm128i vecX = (__m128i)X;
直接把向量存到128位SIMD寄存器中，调用内部函数将矢量相加，并写入输出位置
......然后是很魔幻的操作，看不懂是啥

矢量化DBMS算法

用基本的矢量化操作构建更高级的功能的高效矢量化原则

通过处理每个lane（可以理解为列）的不同输入数据来支持垂直向量化。
通过每个lane的子集执行不同的事情来最大化lane利用率。

基础操作

Selective Load 与 Selective Store

vector表示寄存器中的数据
通过mask来表示寄存器中哪些数据需要导入、导出。

Selective Gather和scatter
按顺序导入或导出
gather和scatter不是真正的并行执行，因为L1缓存每个周期只允许一个或两个不同的访问。

矢量化操作

Selection Scans

调度与执行中讲过CPU的分支处理

SELECT * FROM table
  WHERE key >= $low AND key <= $high

标量有分支和无分支
现在多了一个矢量的

将key向量加入SIMD寄存器中进行SIMD比较，产生mask，再进行SIMD Store
这里虽然也有if(?比较符),但是它比顺序执行快，因为它可以进行批量的比较。
对于DSM列存储更有优势，可以通过一个load把整列加入一个SIMD寄存器，输出的结果也不用存储key的值，只需要存它的offset。

哈希表

在线性探测法的哈希表中，对于每个元组需要计算它的哈希值，然后通过线性扫描找到正确的地址。
水平矢量化的方式是在hash表中直接存了一组值作为key，然后用SIMD compare对比K1和向量中的所有值，产生mask，如果没有匹配再用线性开放寻址解决冲突。
垂直矢量化是同时hash多个key，分别映射表哈希表中。或者是通过SIMD Gather同时查询多个值。一次查询多个值会统一返回查询结果，通过直接比对值和查询的结果得到mask，mask为0的需要再次查询。