矢量化是把一個算法的一次處理一對操作的標量（非向量）實現轉化為一次處理多對操作的向量實現。

假設在32核心上并行化算法，每個核心有4-wide SIMD寄存器。

SIMD就是單指令多數據流，是一類指令集，允許處理器同時在多個數據點執(zhí)行相同的操作。

來看單指令單數據流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優(yōu)缺點
優(yōu)點：算法如果能夠向量化可以獲得顯著地性能提升和對資源的利用率
缺點：用SIMD實現一個算法主要還是手動過程；SIMD會限制數據對齊alignment；把數據收集到SIMD寄存器并放到正確的位置很難效率也低。

針對上面的缺點，有三種解決方法
使用簡單<--->編程控制

1. 自動矢量化：編譯器會識別循環(huán)中的指令能不能重寫為向量化的操作。這只在簡單的循環(huán)中起作用，但是在數據庫操作中是很少見的。需要硬件支持SIMD指令

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

這個循環(huán)不能自動矢量化。XYZ可能指向同一個地址，那么對于循環(huán)中的指令它們就是有關聯的，對于編譯器它不知道應該直接寫Z并且重寫XY，還是按照順序執(zhí)行。

2. 編譯器提示：用額外的信息告訴編譯器這部分代碼是可以安全的矢量化的。
   實現上，可以給出關于內存地址的明確信息；或告訴編譯器忽略向量依賴。

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，忽略循環(huán)內的向量依賴（需要自己判斷是否正確）。

3. Explicit矢量化：用CPU內部函數手動處理SIMD寄存器之間的數據并執(zhí)行矢量化執(zhí)行。
   移植性差
   __mm128i vecX = (__m128i)X;
   直接把向量存到128位SIMD寄存器中，調用內部函數將矢量相加，并寫入輸出位置
   ......然后是很魔幻的操作，看不懂是啥

矢量化DBMS算法

用基本的矢量化操作構建更高級的功能的高效矢量化原則

• 通過處理每個lane（可以理解為列）的不同輸入數據來支持垂直向量化。
• 通過每個lane的子集執(zhí)行不同的事情來最大化lane利用率。

基礎操作

Selective Load 與 Selective Store

Selective Gather和scatter
按順序導入或導出
gather和scatter不是真正的并行執(zhí)行，因為L1緩存每個周期只允許一個或兩個不同的訪問。

矢量化操作

Selection Scans

調度與執(zhí)行中講過CPU的分支處理

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

標量有分支和無分支
現在多了一個矢量的

將key向量加入SIMD寄存器中進行SIMD比較，產生mask，再進行SIMD Store
這里雖然也有if(?比較符),但是它比順序執(zhí)行快，因為它可以進行批量的比較。
對于DSM列存儲更有優(yōu)勢，可以通過一個load把整列加入一個SIMD寄存器，輸出的結果也不用存儲key的值，只需要存它的offset。

哈希表

在線性探測法的哈希表中，對于每個元組需要計算它的哈希值，然后通過線性掃描找到正確的地址。
水平矢量化的方式是在hash表中直接存了一組值作為key，然后用SIMD compare對比K1和向量中的所有值，產生mask，如果沒有匹配再用線性開放尋址解決沖突。
垂直矢量化是同時hash多個key，分別映射表哈希表中。 或者是通過SIMD Gather同時查詢多個值。一次查詢多個值會統一返回查詢結果，通過直接比對值和查詢的結果得到mask，mask為0的需要再次查詢。

Partitioning

h2和h4指向同一個位置，發(fā)生沖突，用復制直方圖解決沖突。

矢量化查詢對于OLAP查詢至關重要。
當數據超出CPU cache這些算法就不起作用了。
把所有intra-query并行優(yōu)化結合起來：

• 同一個查詢多個線程同時處理
• 每個線程都能執(zhí)行一個編譯的plan
• 編譯的plan能調用矢量化操作

矢量化和編譯都能加速執(zhí)行，現在討論在什么條件下這兩種方法更好。

原語是操作系統的核心,內核或微核提供核外調用的過程或函數稱為原語(primitive)。由若干條指令組成,來完成一定功能的過程,執(zhí)行必須過程連續(xù),不允許被中斷
重點 - - 原子語句,不可分割,執(zhí)行不可中斷(要么全部執(zhí)行,要么都不執(zhí)行)

矢量方向——預編譯的原語
預編譯數千條元組在類型數據上進行基本操作（對每個原語用簡單的核意味著他們更容易矢量化）

DBMS執(zhí)行查詢計劃時會調用這些原語

• 函數調用是分攤到多個元組的

• 一個元組的輸出是元組的偏移量

  
  
  一個查詢的原語表示

Hyper-JIT查詢編譯
用LLVM在內存中把查詢編譯成本地代碼，盡可能將元組存在CPU寄存器中

• 由底向上/push-based查詢處理模型

• 不可矢量化

矢量化 vs. 編譯

Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask這篇論文
講的是如何測試和測試的結果，不再寫了
用于測試矢量化執(zhí)行和查詢編譯之間的權衡的測試臺

在同一個系統中用兩種方法實現一個高級算法的方式不同

1. Tectorwise：把操作分解成預編譯原語；必須把每一步元組的數據給物化
2. Typer：用JIT編譯的Push-based處理模型；處理一個元組完全用pipeline而不物化中間結果

實驗發(fā)現：兩個模型都很高效，性能基本一致；Data-centric對高計算的查詢更好，因為會更少的cache miss；矢量化在隱藏cache未命中延遲稍好一些。