美文网首页
矢量化执行

矢量化执行

作者: 玲珑塔上玲珑人 | 来源:发表于2020-07-02 09:43 被阅读0次

矢量化是把一个算法的一次处理一对操作的标量(非向量)实现转化为一次处理多对操作的向量实现。

假设在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寄存器并放到正确的位置很难效率也低。

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

  1. 自动矢量化:编译器会识别循环中的指令能不能重写为向量化的操作。这只在简单的循环中起作用,但是在数据库操作中是很少见的。需要硬件支持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,还是按照顺序执行。

  1. 编译器提示:用额外的信息告诉编译器这部分代码是可以安全的矢量化的。
    实现上,可以给出关于内存地址的明确信息;或告诉编译器忽略向量依赖。
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,忽略循环内的向量依赖(需要自己判断是否正确)。

  1. 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这篇论文
讲的是如何测试和测试的结果,不再写了
用于测试矢量化执行和查询编译之间的权衡的测试台

在同一个系统中用两种方法实现一个高级算法的方式不同

  1. Tectorwise:把操作分解成预编译原语;必须把每一步元组的数据给物化
  2. Typer:用JIT编译的Push-based处理模型;处理一个元组完全用pipeline而不物化中间结果

实验发现:两个模型都很高效,性能基本一致;Data-centric对高计算的查询更好,因为会更少的cache miss;矢量化在隐藏cache未命中延迟稍好一些。

相关文章

  • 矢量化执行

    矢量化是把一个算法的一次处理一对操作的标量(非向量)实现转化为一次处理多对操作的向量实现。 假设在32核心上并行化...

  • numpy学习4:NumPy基本操作

    一、数组与标量、数组之间的运算 数组不用循环即可对每个元素执行批量的算术运算操作,这个过程叫做矢量化,即用数组表达...

  • 矢量化信息

    也可以说将信息矢量化。 不论象形文字还是拼音文字,进化过程中都运用到了信息矢量化原理。矢量化过程中,中文的冗余度较...

  • Matlab编程思想的一点总结

    Matlab编程思想的一点总结 矢量化编程 基本思路: 正向思路和逆向思路相结合,矢量化编程,分块 编程步骤 1....

  • arcgis矢量化——点矢量化

    小伙伴们,师兄今天又给大家带来好消息了呢,别急,且听我细细道来: 我们作为GIS行业的一名成员,不会矢量化简直天理...

  • arcgis矢量化——线矢量化

    小伙伴们, 今天我们来学习利用arcgis进行线的矢量化。昨天我们学习了点的矢量化,同学们学习的如何了?俗话说:“...

  • clickhouse 加速查询方法和mpp架构

    数据加速查询处理的方法 矢量化查询执行 运行时代码生成 在后者中,动态地为每一类查询生成代码,消除了间接分派和动态...

  • 矢量化

  • PS文字创建工作路径矢量化后变细,导出的svg也变细的解决方案

    解决方案很简单: 设计图显示用时不矢量化,就保持原来的状态; 导出用的图标就矢量化后给图层加一个文字颜色的“颜色叠...

  • NumPy(利用数组进行数据处理)

    用数组表达式代替循环的做法,通常被称为矢量化。一般来说,矢量化数组运算要比等价的纯Python方式快上一两个数量级...

网友评论

      本文标题:矢量化执行

      本文链接:https://www.haomeiwen.com/subject/ojzcqktx.html