Vectorized Execution (Part I)

说实话，这节课有点没听明白。

上节课说到了通过矢量化来加速查询的优化，需要这么做的原因是：

1. 构建一个DBMS是非常难的一件事情
2. DBMS中有很多的问题需要去克服
3. 新的CPU加速效果不明显，所以必须想别的办法来提升效果

硬件方面

一般来说，现在用的CPU主要分为两种

MULTI-CORE CPUS

使用少量高功率内核，这些内核的结构复杂功能，功能也更加强大。

• 例如：英特尔Haswell / Skylake
• 每个内核具有高功耗和大面积的特性。

大规模的超标量和积极的失序执行

• 指令是从顺序流发出的，类似管道的任务队列。
• 多个核在分别取得各自的指令，需要检查指令之间的依赖关系。
• 每个时钟周期处理多个指令。

MANY INTEGRATED CORES (MIC)

使用大量的低功率内核，这些内核设计的思想有点像GPU，数量多，但是结构简单，功能稍弱。

• 英特尔Xeon Phi，内核 = Intel P54C（也就是20世纪90年代的Pentium）。
• 每个内核的面积较小，功耗和较低。

非超标量和有序执行，但具有扩展的SIMD功能。

• 更大的寄存器大小，和更高级的指令。
• 只能有序执行是因为妥协的结果

MULTI-CORE VS. MIC

VECTORIZATION

程序从一次处理一对操作数的标量实现转换为一次处理多对操作数的一个操作的矢量实现。

STREAMING SIMD EXTENSIONS (SSE)

英特尔1999年首次推出，在推出之前Intel最早的SIMD只支持64位的SIMD寄存器，而且编译器也不怎么支持，需要人工往内存中写东西，同时也会阻断不是SIMD指令集中的其他指令。SSE一推出就广受欢迎。

SSE是针对特定128位SIMD寄存器的集合SIMD指令。

这些寄存器可以打包四个32位标量，之后可以同时对四个元素中的每一个执行操作。

• Data Movement
  
  • 往寄存器中移入或者移出数据
• Arithmetic Operations
  
  • 对多个变量同时进行算术运算，加减乘除等
• Logical Instructions
  
  • 对多个变量同时进行逻辑运算，与或非等
• Comparison Instructions
  
  • 比较运算
• Shuffle instructions
  
  • 在SIMD寄存器中之间移动数据
  • 我们不希望在运算没有结束之前将SIMD的数据写到CPU cache或者内存上。
• 其他
  
  • 转换：在x86和SIMD寄存器之间转换数据。
  • 高速缓存控制：将数据直接从SIMD寄存器移到内存（绕过CPU cache）。当SIMD寄存器中的数据不用再使用，而需要持久化保存的时候，不经过Cache直接存入内存。

方法

Automatic Vectorization

编译器可以识别何时循环内的指令可以被重写为矢量化操作。GCC等自己不支持，需要人工去实现。

仅适用于简单循环，在数据库操作中很少见。且该自动识别需要SIMD指令的硬件支持。

假设X,Y,Z指向的是同一块地址，那么对于循环中的指令，他们之间就是有关联的。对于编译器它不知道应该是直接写Z并且重写X和Y，还是按照顺序来执行。

COMPILER HINTS

向编译器提供有关代码的其他信息，以使其知道向量化是安全的。虽然这种做法不是完全必要的，但是大部分情况都会使用这种方式。

两种方法：

• 提供有关内存位置的明确信息。
• 告诉编译器忽略向量依赖。

restrict 告诉编译器这些数组是在独立的内存位置。

忽略循环内的依赖，直接矢量化。

这时候就需要程序员去判断这个程序的正确性，编译器就直接照着自己的想法去做。

EXPLICIT VECTORIZATION

使用CPU内部函数手动处理SIMD寄存器之间的数据并执行矢量化指令。

移植性可能较差。

将向量存入128位的SIMD寄存器，然后调用内部函数将矢量相加，并将它们写入输出位置。

它如1、2这样简单的操作，并通过几种简单的曹组的组合使得如3这样复杂的操作得以实现

1. 线性访问操作符
   
   • 谓词评估
   • 压缩
2. 专门的矢量化
   
   • 排序
   • 合并
3. 可组合操作
   
   • 多路树
   • 分块hash表

VECTORIZED DBMS ALGORITHMS

通过使用基本向量操作来构建更高级功能的高效矢量化原则：

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

lane的意思是，假设有128位的寄存器，其中存了4个32位的数，那么一列32位的数就称为一个lane。

基础操作

Selective Load 和 Selective Store

vector表示寄存器中的数据

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

在Xeon CPU中，使用向量置换也可以模拟选择性加载和存储。

Selective Gather 和 Selective Scatter

按一定顺序的导入导出。

gather和scatter并不是真正并行执行，因为L1缓存每个周期只允许一个或两个不同的访问。

新的CPU才支持gather，只有Xeon5 支持scatter

VECTORIZED OPERATORS

Selection Scans

对于如下操作

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

不考虑矢量化，我们可以得出两种不同的代码

• branching通过if判断是否进入一个分支，如果不进入分支则需要刷新管道。这样做对CPU而言是非常不友好的
• branchless对于所有的数据都进行传输，但是因为是在内存中，又运用了管道技术，所以花费时间并不是很多。CPU可以直接顺序执行。

如下图所示的是测试的结果，横轴的百分比表示有多少是判断结果是true的tuple占的百分比。

考虑矢量化的话，我们可以转化为如下的代码

将

$V_m$表示mask向量。

虽然这儿也有一个if（其实也可以写成没有if的形式），但是比顺序执行快的是，它可以批量处理。

DSsam的优势之一就是，数据是按照列存储的，则可以通过一个load操作就将整列存入一个寄存器。

我们不需要存储key的值，只需要计算offset即可。

HASH TABLES

这儿使用的是线性开放寻址的hash表。

所以对于每一个tuple，我们计算它的hash值，然后需要线性扫描找到正确的地址。

水平矢量化的方式是，在hash表中直接存储一组值作为key。

然后用SIMD Compare去对比k1和一个向量中的所有值，产生一个mask。如果都没有匹配的，则用线性开放寻址去解决冲突。

一次性查询多个值，然后会统一返回查询的结果。

通过直接对比值和查询的结果，得到mask。

对于mask是0的，就再次进行查询。

PARTITIONING

使用scatter和gather来增加计数。
复制直方图以处理冲突。

当h4和h2指向同一个位置的时候，会发生冲突。所以复制直方图来解决冲突。

没有分区

• 使用原子构建一个共享散列表
• 部分矢量化

最小分区

• 分区建立表
• 为每个线程构建一个哈希表
• 完全向量化

最大分区

• 重复对两个表进行分区
• 构建并探测缓存驻留散列表
• 完全向量化

参考资料

课件
Rethinking SIMD Vectorization for In-Memory Databases