1.背景
SIMD是(Single instruction multiple data)的缩写，代表了通过单一一条指令就可以操作一批数据，可用一组指令对多组数据进行并行操作。该项技术最早应用在视频的加速解码上，早在Intel的奔腾系列就引入了MMX（multi-media extend）技术，不过该项技术是为了支持MPEG视频解码，图像的数据常用的数据类型是RGB565,RGBA8888,YUV422等格式，这些格式的数据特点是一个像素点的一个分量总是用小于等于８bit的数据表示的，如果使用传统的处理器做计算，虽然处理器的寄存器是32位或是64位的，处理这些数据确只能用于他们的低８位，似乎有点浪费，如果把64位寄存器拆成８个８位寄存器就能同时完成８个操作，计算效率就会提升８倍。后来Intel进一步实现了SSE、SSE2~SSE4、AVX指令集，如下的两个图分别表示了各指令集的功能区别和不同cpu所支持指令集的丰富程度。
指令集名称 | 功能 |
MMX | 64位整型 |
SSE | 128位浮点运算，整数运算仍然要使用MMX寄存器，只支持单精度浮点运算 |
SSE2 | 对整型数据的支持，支持双精度浮点数运算，CPU快取的控制指令 |
SSE3 | 扩展的指令包含寄存器的局部位之间的运算，例如高位和低位之间的加减运算；浮点数到整数的转换，以及对超线程技术的支持 |
SSE4 | 增加了更多指令，并且在数据搬移上支持不对齐的数据搬移，同时增加了super shuffle引擎 |
AVX | 256位浮点运算 |
AVX2 | 对256位整型数据的支持，三运算指令（3-Operand Instructions） |
AVX512 | 512位运算 |
表格1：不同指令集支持的功能迭代
图二：不同CPU系列支持的SIMD指令集示意图
随着移动互联网以及IOT技术的发展和普及，系统可以使用的数据呈现指数级别的增长，如何应对这些海量数据的快速处理和查询，大数据软件厂商迫切需要使用SIMD向量加速处理海量的数据。SIMD指令可以在一个控制器上同时控制多个平行的处理微元，一次指令运算执行多个数据流，通过这种方式，在相同的时钟周期内，CPU能够处理的数据的能力就大大增加。SIMD指令在本质上非常类似一个向量处理器，可对控制器上的一组数据（又称“数据向量”）同时分别执行相同的操作从而实现空间上的并行。它可以通过单指令多数据技术和单时钟周期并行处理多个浮点来有效地提高浮点运算速度。
以乘法计算说明SIMD计算对比传统CPU计算的区别及优势：
图三：传统CPU乘法计算方式
图三是一个简单的乘法计算：4个数字都需要进行乘3的计算。共需要执行12个指令：
◇4个load内存指令
◇ 4个乘法指令
◇ 4个内存回写指令
图四：SIMD计算方式
从图四可以看出，具有128位寄存器的CPU可以保存4个32位数并进行一次计算，比一次执行一条指令快4倍。通过SIMD指令则可以按批的方式来更快的处理数据，由原先的12个指令，减少到了3个指令。当代的X86处理器通常都支持了MMX，SSE，AVX等SIMD指令，通过这样的方式来加快CPU的计算。当然SIMD指令也是有一定条件的，从上面的图中也能看出端倪。
◇处理的数据需要连续，并且对齐的内存能获得更好的性能
◇ 寄存器的占用比传统的SISD的CPU多
通常生成SIMD指令的方式有两种：
Auto Vectorized
自动向量化，也就是编译器自动去分析for循环是否能够向量化。如果可以的话，便自动生成向量化的代码，通常我们开始的-O3优化便会开启自动向量化。
手写SIMD指令
SIMD可以通过库的方式进行支持。也可以直接通过Intel提供的库来直接进行向量化编程，比如SSE的API的头文件为xmmintrin.h，AVX的API头文件为immintrin.h。这种实现方式最为高效，但是需要程序员熟悉SIMD的编码方式，并且并不通用。比如实现的AVX的向量化算法并不能在不支持AVX指令集的机器上运行，也无法用SSE指令集代替。
2.SIMD在MPP数据库中常见应用场景分析
SIMD指令为分析型数据库引擎性能提升的设计和实现提供了新的机会，我们研究了starrocks、clickhouse等开源OLAP数据库的SIMD使用，看它们是如何在SQL的各种执行流程当中使用SIMD指令进行查询的加速。
◆ 2.1 Sort计算加速
在数据分析的场景，大多数SQL都有对某列数据排序的需求，如何利用SIMD 指令对数据排序进行加速是MPP数据库一个非常重要的研究方向。
但是利用SIMD技术进行排序规模受限于向量寄存器的长度，因此SIMD实现的排序网络只可作为building block，它生成多个有序的小向量，然后外层将这多个有序向量进行归并。快速排序并不适合利用SIMD来优化，因为快速排序划分出来的子块并不均匀，对于归并排序算法而言，基本所有的子块大小都相等，因此当子块大小划分达到向量长度阈值时，可以采用SIMD来加速对子块的排序。
双调排序就是一种特别适合做并行计算的排序算法，我们在介绍双调排序之前先介绍一下双调序列和Batcher定理。
双调序列：一个先单调递增后单调递减（或者先单调递减后单调递增）的序列，如1,5,8,6,3。
Batcher定理：将任意一个长为2n的双调序列A分为等长的两半X和Y，将X中的元素与Y中的元素一一按原序比较，即a[i]与a[i+n](i
双调排序：假设我们有一个双调序列，则我们根据Batcher定理，将该序列划分成2个双调序列，然后继续对每个双调序列递归划分，得到更短的双调序列，直到得到的子序列长度为1为止，这时的输出序列按单调递增顺序排列。
见下图：升序排序，具体方法是，把一个序列(1…n)对半分，假设n=2^k，然后1和n/2+1比较，小的放上，接下来2和n/2+2比较，小的放上，以此类推；然后看成两个(n/2)长度的序列，因为他们都是双调序列，所以可以重复上面的过程；总共重复k轮，即最后一轮已经是长度是2的序列比较了，就可得到最终的排序结果。
双调排序示意图
上面介绍了双调序列完成排序的过程，但是并不是任意的序列都是双调序列，首先需要生成双调序列。
生成双调序列的过程叫Bitonic merge,实际上也是divide and conquer的思路。和前面sort的思路正相反，是一个bottom up的过程——将两个相邻的，单调性相反的单调序列看作一个双调序列，每次将这两个相邻的，单调性相反的单调序列merge生成一个新的双调序列，然后排序（同3、双调排序）。这样只要每次两个相邻长度为n的序列的单调性相反，就可以通过连接得到一个长度为2n的双调序列，然后对这个2n的序列进行一次双调排序变成有序，然后在把两个相邻的2n序列合并（在排序的时候第一个升序，第二个降序）。n开始为1，每次翻倍，直到等于数组长度，最后就只需要再一遍单方向（单调性）排序了。
以16个元素的array为例：
1.相邻两个元素合并形成8个单调性相反的单调序列。
2.两两序列合并，形成4个双调序列，分别按相反单调性排序。
3.4个长度为4的相反单调性单调序列，相邻两个合并，生成两个长度为8的双调序列，分别排序。
4.2个长度为8的相反单调性单调序列，相邻两个合并，生成1个长度为16的双调序列，排序。
如下图所示：
最后再放一个8元素的完整排序示意图：
讲完了双调排序算法，我们看下如何使用SIMD指令对双调排序的进行加速。
使用g++-o test test.cc-mavx2进行编译以及./test对该排序算法进行排序结果的校验，相比std::sort的排序实现有4-5倍的提速,实测数据如下:
如果你想对更大的数组进行排序，可以使用merge_sort对于此基础排序算法进行递归调用从而实现。
◆ 2.2 数值条件比较的加速
select a from tbl1 where a>1,类似这样的SQL语句是非常常见的，如何将SQL语句当中的filter算子执行过程使用SIMD指令进行加速是非常有收益的。
以表达式a>1为例，我们看下普通的数据过滤是如何实现的。
图五：内存谓词计算
遍历column a，对a中的数据与1做比较，将比较结果写入filter result数组，filter result数组由UInt8 组成（1 byte），1代表满足过滤条件，0代表不满足过滤条件。
遍历filter result数组，拿到元素是1的offset，将对应存储在数据库对应位置的数据复制到result column中。
以下展示starrocks2.3中如何根据filter result 得到目的数据：
以上代码段基于starrocks2.3版本。BinaryColumnBase
if(mask==0) 如果全是0，代表本次循环中32个元素均不满足条件，则什么都不做。
else if(mask==0xffffffff)如果全是 ，代表本次循环中32个元素都满足条件，则一次把32个元素全部copy到result column中。因为starrocks中column是数组表示，这里是对连续内存的copy。在循环展开中减少了寄存器依赖，而且连续内存copy，对CPU cache友好。
如果非全0也非全1，就需要继续对32个元素做单独判断，先把掩码转化为32位的整数，再把是1的元素值copy到result column中。
由上可见，对int值进行过滤时，这个函数的每次循环都将连续8个带过滤的数据（即int类型）压缩到一个__m256i中一起做位计数。其中每次调用上述指令都会按32个8位整型进行处理，其中8位不能有溢出，正好是256位。基于SIMD，CPU能从一次计算一个值到一次计算一组值，这样计算效率、速度就会有数倍的提升。
代码段涉及的AVX2指令，介绍：
#ifdef__AVX2__说明当前环境支持AVX2指令集。
__m256i包含若干个整型数据的向量，如char、short、int、unsigned long long等。例如256位的vector可以32个char、16个short、8个int，这些整型既可以是有符号的也可以是无符号的；
_mm256_setzero_si256()初始化256位（32字节）的全0位图，即一个XMM寄存器；
_mm256_loadu_si256()从内存地址中读入一个256位的整型数据（32字节地址无需对齐；
_mm256_cmpgt_epi8(f,all0)按8位整形处理，比较f和all0两个256位整形数，若f的对应8位比all0的对应8位大，则填充对应位为全1，否则填充全0；
_mm256_movemask_epi8()根据256位整形数的每个8位组的最高位创建掩码；
Join计算通常是最为常见的耗时算子，优化Join算子的时延有大体可以分为两种思路。第一种思路是改进Join的计算算法，比如对于HashJoin，可以优化 HashTable实现（包括降低散列函数的计算复杂度和降低冲突列的查询复杂度），也可以将表做合适的partition数量提升并行度，在网络传输和计算并行度中间做一些平衡。
另一种思路是在具体计算过程中尽可能做数据的裁剪，减少参与算子计算的数据。Runtime Filter在一些场景下特别是事实表Join维度表的星型模型场景有比较好的效果，在此类场景下，通常事实表的规模会非常大，而大部分的过滤条件都是在维度表上面。
Runtime Filter（下文中简称RF）是在运行时对数据进行过滤，过滤通常发生在Join阶段。当多表进行Join时，往往伴随着谓词下推等优化手段进行数据过滤，以减少Join的表的数据的扫描以及shuffle等阶段会产生的IO，从而提升查询性能。RF的优化方式同样也是会对数据进行过滤，但是无需用户进行设置，执行引擎会在查询时自动进行过滤优化。
在StarRocks中为了充分利用AVX2指令的并行处理能力，实现了基于SIMD的Runtime Filter给多表join进一步加速。
以下为starrocks利用Runtime Filter加速join的场景：
如图所示，Fact和Dim两个表通过id字段join，左图表示的是未优化的时候，左表需要扫描10亿行的数据，而优化后只需要扫描100万行，减少大量的数据扫描，极大提升查询效率。这里的实现就是Runtime Filter，就是在sql运行过程中，将右表查询结果建一个RF下推到左表，可以达到提前过滤的效果。当前支持broadcast和shuffle runtime filter，整个过程是自动优化的。
以下是一段在runtime filter过程当中构建布隆过滤器的时候使用SIMD进行加速的代码：
◆ 2.4 加速字符串的大小写转换
大小写的转化也是SQL当中一个比较常见的操作，以ASCII拉丁字符大小写转换函数（即toLower()和toUpper()）为例，我们来看下ClickHouse当中的字符串大小写的实现。
原理比较简单，就是利用flip_case_mask这个掩码来翻转字符的大小写（大小写字母的ASCII码值相差32）。not_case_lower_bound和not_case_lower_bound则用来标定转换的字符范围，比如a~z或A~Z。不过在SSE2的加持下，就可以一次性加载16个字符进行转换。
◆ 2.5 加速字符串的子串搜索
类似like的子串匹配也是SQL查询当中很常见的一个场景，对于前缀和后缀都可以使用字典树索引+倒排的组织方式进行快速搜索，但是对于like %abc%这样的子串匹配就不太好使用索引，通常会采用逐行匹配的方式，那么如何加速子串在单行数据的搜索就非常有意义了。我们来看下常规的子串匹配算法：
原理是一个一个字符地匹配，但是有下列缺点：
◇逐字节比较也要逐次访问内存，浪费CPU周期；
◇ 错误的分支预测则会浪费更多的CPU周期；
◇ 这类代码难以乱序并行执行。
那么在MPP数据库中如何使用SMID来优化子串搜索的性能呢？
假设我们有一些8-byte的寄存器，我们要在字符串 “a_cat_tries” 中搜索子串 “cat”。
首先我们将“cat”的第一个字节和最后一个字节填充到两个寄存器中，并尽可能地重复直到寄存器被填满。
然后我们将字符串“a_cat_tries”加载到另外两个寄存器中，其中一个寄存器从子串长度-1个字符开始加载。
然后比较两组寄存器的内容，对应位置的内容相同为1，反之则为0。
最后我们将两个寄存器的内容合并，即“位与”运算。
此时我们发现只有第2位（从零开始）是1，说明只有从此处开始搜索才有可能搜索到子串。这样就减少了我们的搜索次数。
以下提供基于SIMD指令中的AVX2指令集的实现：
◆ 2.6 场景总结
从上面的场景来看，随着现代CPU架构中所提供的指令集越来越丰富，可用不同指令对多个数据进行不同的并行操作，当前MPP数据库当中很多基础的算子都基于SIMD指令集进行重写从而获得了对应的性能提升，如上的算子只是列举了部分，还有更多的算子可以使用SIMD指令集进行加速，基于SIMD指令集进行算子加速是MPP性能提升的一个非常重要的方向。
3.总结
提升OLAP引擎在大数据场景下的分析性能是一个永不过时的话题，这个领域近年来不断涌现出一些新的技术方向，包括存储格式、数据裁剪、CodeGen、向量化计算等。而向量化计算是将内存连续的数据充分利用CPU硬件的SIMD指令进行并行计算从而达到执行提速的目的，SIMD采用和并发无关的数据级并行，SIMD指令允许在同一时钟周期内，对多条数据执行相同的指令。现在的Intel 编译器配置了AVX-512（高级矢量扩展）指令集，该指令集增加SIMD寄存器的宽度到512比特，换而言之，可以并行运算16个4字节的整数列值。要使用SIMD指令集进行向量化处理，很重要的一点是正确组织数据以最大化收益。如何正确合理的组织数据，充分合理的利用SIMD指令是OLAP引擎性能提升的一个非常重要的研究方向。
| 留言与评论（共有 0 条评论） “” |
