Divergence 與 Convolution/Filtering 的近似在 NEON 的處理

在 2017 年的最後一天想用技術分享做一個結束

Divergence

會特別想提 NEON divergence handling 的原因是許多的 NEON 教學並沒有特別著墨這部份, 儘管並不困難, 但是在眾多 instruction 找出適當的指令也不是容易的事.

對於多數 SIMD instruction 而言 divergence (if-else, switch-cases)都是不容易處理的部份
在許多 modern SIMD ISA 的設計中都採用了 predication 的作法: 可以透過 per-lane flag 數值來個別控制每個 lane 是否執行該指令, 輸出結果.
然而 NEON 並沒有 predication 的設計, 因此對於 if-else 的作法採用的是對於結果做 selection 的方式, 而其中扮演關鍵角色的是 VBSL 這個指令
考量下列範例

unsigned char pix;
...
if(pix >= 192){
     pix += 10;
}else{
     pix +=5;
}

改以 NEON 實作則如下

uint8x16_t vpix;
...
//selection mask
uint8x16_t vsel = vcgeq_u8(vpix, vdupq_n_u8(192));
//for >= 192
vpix1 = vaddq_u8(vpix, vdupq_n_u8(10));
//for < 192
vpix2 = vaddq_u8(vpix, vdupq_n_u8(5));
//get correspond16-bit Multiply-Accumulation ing result from each lane
vpix = vbslq_u8(vsel, vpix1, vpix2);

事實上 vbsl 的用途不僅如此因為他是 bit-selection, 可以處理 bit-wise operation

16-bit Multiply-Accumulation 

 

這篇第二個要分享的是 fixed point 的技巧, 適合 convolution 與 image filtering 的數值近似.
在 image filtering 與 NN 的 convolution/FC 中的計算, 有許多數值介於 -1.0 ~ 1.0 的浮點數與 整數相乘的處理, 一方面 floating point 本身為 32b 運算(需要 ARMv8.2 才有 NEON FP16 的支援), 再者 float 與 int16/32 的轉換也需要消化額外的指令, 另一方面轉為 int16/32 的 fixed point 處理需要使用更多位元數的 int32/64.

對於許多這類應用有許多乘加的運算, 16bit 的數值相乘需要 32bit 來存放, 然而對於輸出通常也都會到 16bit (也就是最後結果需要 right shift 16 bit), 考量這類應用可以有些微的誤差, 可以考慮一個特別的指令 - vqdmulh or vqrdmulh

vqdmulh 的輸出結果是兩個 16b 數值相乘的 "兩倍" 作 right shift 16 bit
vqrdmulh 相較 vqdmulh 會多做一個 rounding 的動作

對於浮點的處理可以先轉為 16b 的數值 (類似 1/65536 for unsigned or 1/32768 for signed), 而相乘 x2 的結果主要是做 0.5 的近似, 可以取得更好的累加近似結果(最後結果需要 right shift 1bit).  對於一些能事先轉為 16b 資料固定的 pattern (像是 filtering 與 NN 的 weight, 或是除法), 這兩個指令相當實用.

out = 0.14 * pix0 + 0.7 * pix1 + 0.16 * pix2;

轉為 NEON 可以計算近似為:

// 0.14 * pix0
vout = vqdmulh_s16(vpix0, vdupq_n_s16(4588));
// 0.7 * pix1
vout = vaddq_s16(vout, vqdmulh_u16(vpix1, vdupq_n_u16(22934)));
// 0.16 * pix2
vout = vaddq_s16(vout, vqdmulh_u16(vpix2, vdupq_n_u16(5243)));