矢量化是把一个算法的一次处理一对操作的标量(非向量)实现转化为一次处理多对操作的向量实现。
假设在32核心上并行化算法,每个核心有4-wide SIMD寄存器。
SIMD就是单指令多数据流,是一类指令集,允许处理器同时在多个数据点执行相同的操作。
来看单指令单数据流SISD和SIMD的对比
单指令多数据流.png 单指令单数据流.png
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的需要再次查询。
Partitioning
h2和h4指向同一个位置,发生冲突,用复制直方图解决冲突。
矢量化查询对于OLAP查询至关重要。
当数据超出CPU cache这些算法就不起作用了。
把所有intra-query并行优化结合起来:
- 同一个查询多个线程同时处理
- 每个线程都能执行一个编译的plan
- 编译的plan能调用矢量化操作
矢量化和编译都能加速执行,现在讨论在什么条件下这两种方法更好。
原语是操作系统的核心,内核或微核提供核外调用的过程或函数称为原语(primitive)。由若干条指令组成,来完成一定功能的过程,执行必须过程连续,不允许被中断
重点 - - 原子语句,不可分割,执行不可中断(要么全部执行,要么都不执行)
矢量方向——预编译的原语
预编译数千条元组在类型数据上进行基本操作(对每个原语用简单的核意味着他们更容易矢量化)
DBMS执行查询计划时会调用这些原语
- 函数调用是分摊到多个元组的
-
一个元组的输出是元组的偏移量
一个查询的原语表示
Hyper-JIT查询编译
用LLVM在内存中把查询编译成本地代码,尽可能将元组存在CPU寄存器中
- 由底向上/push-based查询处理模型
- 不可矢量化
矢量化 vs. 编译
Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask这篇论文
讲的是如何测试和测试的结果,不再写了
用于测试矢量化执行和查询编译之间的权衡的测试台
在同一个系统中用两种方法实现一个高级算法的方式不同
- Tectorwise:把操作分解成预编译原语;必须把每一步元组的数据给物化
- Typer:用JIT编译的Push-based处理模型;处理一个元组完全用pipeline而不物化中间结果
实验发现:两个模型都很高效,性能基本一致;Data-centric对高计算的查询更好,因为会更少的cache miss;矢量化在隐藏cache未命中延迟稍好一些。
网友评论