Lookup Table 在 NEON 中的處理

在 SIMD Programming 中由於希望能夠每個 lane 有一致的行為,
因此有一些事情是不容易達到的
而 Lookup Table (LUT) 即是其中之一

但若是特定條件之下, 還是有可能透過 NEON 加速
而這個直接前提是 8bit LUT (當然藉此方法可以做 8bit 轉 16bit LUT)
在 ARMv7 中 NEON 就提供兩個指令 - VTBL 與 VTBX 作為有限度的 LUT功能使用
兩者提供了同時能夠處理 8筆 8bit 資料的 LUT 動作 (64bit NEON register)所使用的 table 最多為 4個 64bit NEON 暫存器
這也就是說 index 範圍為 < 8x4 = 32
而 VTBL 與 VTBX 兩者的差異是:
VTBL 對於 index 超出範圍的 lane 輸出值為 0
VTBX 對於 index 超出範圍的 lane 並不更動

值得慶幸的是在 ARMv8 中將這兩者寬度加倍
也就是一次可以查找 16筆 8bit 資料的 LUT 動作 ( 128bit NEON register)
table 也變為 4個 128bit NEON register
因此 index 合法範圍為 < 16x4 =64
以下就只針對重點部分演示:

以下的 code 即為常見的 LUT 方式

#define TEST_W 4096
#define TEST_H 3072
unsigned char *table = (unsigned char*)malloc(256); 
unsigned char *buf_0 = (unsigned char*)malloc(TEST_W*TEST_H); 
unsigned char *buf_1 = (unsigned char*)malloc(TEST_W*TEST_H);  
// buffer filled with random numbers
...
for(int i = 0; i < TEST_W*TEST_H; i++){
    buf_0[i] = table[buf_0[i]];
} 

以下為 ARMv8 的實作方式

uint8x16x4_t vlut_tbl[4]; 
//table initialization
for(int i = 0; i < 4; i++){
    vlut_tbl[i].val[0] = vld1q_u8(table+i*64);
    vlut_tbl[i].val[1] = vld1q_u8(table+i*64+16);
    vlut_tbl[i].val[2] = vld1q_u8(table+i*64+32);
    vlut_tbl[i].val[3] = vld1q_u8(table+i*64+48);
} 
//SIMD LUT
for(int i = 0; i < TEST_W*TEST_H; i+=16){ 
    uint8x16_t vlut_idx = vld1q_u8(buf_1 + i);
    uint8x16_t vlut_val = vqtbl4q_u8(vlut_tbl[0], vlut_idx); 
    vlut_val = vqtbx4q_u8(vlut_val, vlut_tbl[1], vsubq_u8(vlut_idx, vdupq_n_u8(64)));
    vlut_val = vqtbx4q_u8(vlut_val, vlut_tbl[2], vsubq_u8(vlut_idx, vdupq_n_u8(128)));
    vlut_val = vqtbx4q_u8(vlut_val, vlut_tbl[3], vsubq_u8(vlut_idx, vdupq_n_u8(192)));
    vst1q_u8(buf_1 + i, vlut_val);
}

透過手邊的 Xperia M4 (Snapdragon 615, Cortex-A53 octa cores)平台測試
C-LUT : 58271 us, NEON-LUT : 21702 us

得到了 2.7X 的效能

Android NN API 與 OpenVX

乍看之下會覺得很奇怪

一個是 Neutral Network API

另一個則是 CV 的 API

兩者如何能夠相提並論地比較？

但是這兩者其實有著很高的相似度

讓我們先從 Android Neural Network API 的流程圖看起

可以看到 Android NN API 有幾個元件組成
1. ANeuralNetworkModels
2. Operations
3. ANeuralNetworksMemory

而 Android NN API 分為3個步驟
1. Network Create
2. Network Compilation
3. Network Execution

接著來看 OpenVX, 下圖來自於 Khronos 於 2016 的官方 Tutorial T3

可以看到 OpenVX 有幾個元件組成
1. Graph
2. Node
3. Image

而 OpenVX 分為3個步驟
1. Graph Create
2. Graph Verify
3. Graph Process

這裡可以再對照 Android NN API 提供的 Graph 示意圖

是不是很類似的概念呢?

兩者流程與介面的對應上可以說是如出一轍, 而在 OpenVX Neural Network Extension 中, 做了一件事就是新增了 Tensor 資料封裝型別與定義了 Neural Network 中用到的 operations, 並且沿用既有的 Graph 模式