從一個複數點積演算法看NEON的彙編優化
摘要：本文通過一個真實案例（4096點雙精度浮點複數點積演算法），描述了使用 Zynq-7000 NEON進行演算法優化的過程以及一些關鍵技巧，相對於使用編譯器對C程式碼做優化，效能提升了大約4.8倍。 本文介紹的內容對需要用到NEON實現高效能運算的開發者非常有幫助。
開發工具：Xilinx SDK 2013.4
開發板： Xilinx ZC702或者ZC706
一般來說，使用NEON優化演算法有以下幾種方式：
>用現成的開源庫，例如Ne10，FFTW等等
>使用編譯器的auto vectorization功能，通過配置合適的編譯選項讓編譯器來生成NEON程式碼
>使用NEON Intrinsic
>使用NEON彙編
前三種方式簡單易用，但是受限於編譯器的優化能力，往往效能無法達到極致。在需要使用NEON進行高效能運算的時候，就需要用手工彙編來進行優化 了。用匯編語言寫程式看起來很讓人望而生畏，但實際上在一個演算法裡面需要高度優化的核心部分並不會太大，只要靜下心來，掌握一些書寫NEON彙編的技巧， 完全可以輕鬆的完成核心彙編程式。
下面我們來看一個例子：求兩個向量（vector）的點積（dot product），向量的長度為4096，向量的資料為複數（complex），複數的實部和虛部都是雙精度浮點型別。，每個向量佔用記憶體64KB。
對Zynq-7000晶片來說，資料可以儲存在片內高速SRAM（OCM）中，也可以儲存在DDR3 memory中。我們首先以資料儲存在OCM中為例，最後會討論資料儲存在DDR3中的情況。
1. 使用編譯器的auto vectorization進行優化：
對這個演算法來說，C語言的標準實現大致是這樣的。
double a[N*2] ;
double b[N*2] ;
double result_golden[2] = {0.0, 0.0};
int i;
result_golden[0]=0.0;
result_golden[1]=0.0;
for(i = 0; i < 4096; i++)
{
result_golden[0] += a[2 * i] * b[2 * i] - a[2 * i + 1] * b[2 * i + 1];
result_golden[1] += a[2 * i + 1] * b[2 * i] + a[2 * i] * b[2 * i + 1];
}
我們使用以下編譯選項來讓編譯器針對NEON進行優化。
-O2-mcpu=cortex-a9 -mfpu=neon -ftree-vectorize -mvectorize-with-neon-quad -mfloat-abi=softfp -ffast-math
我們將這個演算法執行10次，得到平均的執行時間為289.692us。預設情況下，CPU的主頻為667MHz，換算成CPU cycles，執行時時間為193128 cycles。將這個數字除以向量長度4096，我們就得到每個雙精度複數乘加需要的平均時間為47.14 CPU cycles.
通過上面的原始碼，我們可以看出每個複數乘加涉及到3次雙精度浮點數的乘加（MLA）運算和1次雙精度浮點數的乘減（MLS）運算。查詢 ARM Cortex™-A9 NEON™ Media Processing Engine Technical Reference Manual文件，我們注意到對雙精度浮點數，在理想情況下，MLA/MLS指令需要2個CPU cycles，即理論上執行一次複數乘加需要的時間為8 CPU cycles。
即使我們把資料在memory和NEON registers之間傳輸的時間也考慮進去，每個複數乘加的實測執行時間和理論執行時間之間的差距也是相當大的。這樣，我們可以初步得出結論：在這個算 法上，編譯器的優化能力離效能極限還有很大差距，通過適當的彙編優化，還有很大的效能提升空間。
2. 如何實現最優的指令序列
我們先來做個實驗，測試一下以下函式的執行時間。在這個函式的迴圈體裡面，有4條vmla.f64指令。測試完成後，我們從後往前每次註釋掉一條vmla.f64指令，然後測試實際的執行時間，直到最後只剩1條vmla.f64指令為止。
.align 4 .global neon_instr_seq_0 .arm neon_instr_seq_0: LDR r0, =16384 neon_instr_seq_0_loop: vmla.f64 d8, d0, d4 vmla.f64 d9, d1, d5 vmla.f64 d10, d2, d6 vmla.f64 d11, d3, d7 SUBS r0, r0, #1 BNE neon_instr_seq_0_loop bx lr
這樣我們就得到了以下的表格
| 函式的迴圈體裡面vmla.f64指令的數目 | 每次迴圈需要的CPU cycles | 平均每條NEON指令需要的CPU cycles |
| 4 | 8 | 2 |
| 3 | 6 | 2 |
| 2 | 6 | 3 |
| 1 | 6 | 6 |
從這個表格，我們可以看出：因為CPU內部微架構的原因，對一個NEON指令的目的暫存器寫入後，要等待一段時間再執行下一次寫入操作，否則會導致 pipeline stall導致效能下降。對雙精度浮點數，相鄰的三個NEON指令的目的暫存器必須是不同的。值得注意的是，對其他資料型別，例如單精度浮點數或者32- bit整數，結論會略有差異。
一般來說，在memory和register之間用VLDM/VSTM交換資料會有比較高的效率。對NEON來說，共有32個D暫存器，這樣我們對 每個向量每次可以載入4個複數（即8個雙精度浮點數），其中D0-D7儲存向量1的資料，D8-D15儲存向量2的資料，其他暫存器用於儲存中間結果。按 照這個思路，比較直接的彙編寫法是：
.align 4 .global neon_instr_seq_20 .arm neon_instr_seq_20: LDR r0, =16384 neon_instr_seq_20_loop: vmla.f64 d16, d0, d8 vmla.f64 d17, d0, d9 vmls.f64 d16, d1, d9 vmla.f64 d17, d1, d8 vmla.f64 d18, d2, d10 vmla.f64 d19, d2, d11 vmls.f64 d18, d3, d11 vmla.f64 d19, d3, d10 vmla.f64 d20, d4, d12 vmla.f64 d21, d4, d13 vmls.f64 d20, d5, d13 vmla.f64 d21, d5, d12 vmla.f64 d22, d6, d14 vmla.f64 d23, d6, d15 vmls.f64 d22, d7, d15 vmla.f64 d23, d7, d14 SUBS r0, r0, #1 BNE neon_instr_seq_20_loop bx lr
每次迴圈使用到了16條FPU指令，理論上需要32 CPU cycles，實測每次迴圈需要40 CPU cycles。這也印證了一開始我們通過測試得出的結論，所以我們要通過重新排布指令的順序來取得更好的效能。
重新排布後指令順序如下所示。實測每次迴圈需要32 CPU cycles，這段程式碼達到了最優化。
.align 4 .global neon_instr_seq_21 .arm neon_instr_seq_21: LDR r0, =16384 neon_instr_seq_21_loop: vmla.f64 d16, d0, d8 vmla.f64 d17, d0, d9 vmla.f64 d18, d2, d10 vmla.f64 d19, d2, d11 vmla.f64 d20, d4, d12 vmla.f64 d21, d4, d13 vmla.f64 d22, d6, d14 vmla.f64 d23, d6, d15 vmls.f64 d16, d1, d9 vmla.f64 d17, d1, d8 vmls.f64 d18, d3, d11 vmla.f64 d19, d3, d10 vmls.f64 d20, d5, d13 vmla.f64 d21, d5, d12 vmls.f64 d22, d7, d15 vmla.f64 d23, d7, d14 SUBS r0, r0, #1 BNE neon_instr_seq_21_loop bx lr
對上面的程式碼，使用到的目的暫存器為8個，結合最開始的測試結論，我們只需要4個目的暫存器就夠了，所以可以把上面的程式碼改寫成下面的形式。實測每次迴圈需要32 CPU cycles，效能仍然是最優。
.align 4 .global neon_instr_seq_22 .arm neon_instr_seq_22: LDR r0, =16384 neon_instr_seq_22_loop: vmla.f64 d16, d0, d8 vmla.f64 d17, d0, d9 vmla.f64 d18, d2, d10 vmla.f64 d19, d2, d11 vmla.f64 d16, d4, d12 vmla.f64 d17, d4, d13 vmla.f64 d18, d6, d14 vmla.f64 d19, d6, d15 vmls.f64 d16, d1, d9 vmla.f64 d17, d1, d8 vmls.f64 d18, d3, d11 vmla.f64 d19, d3, d10 vmls.f64 d16, d5, d13 vmla.f64 d17, d5, d12 vmls.f64 d18, d7, d15 vmla.f64 d19, d7, d14 SUBS r0, r0, #1 BNE neon_instr_seq_22_loop bx lr
3. 如何優化使用VLDM
比較直觀的使用VLDM指令後的彙編如下所示。實測每次迴圈需要45 CPU cycles.
.align 4
.global neon_instr_seq_23
.arm
neon_instr_seq_23:
LDR r3, =16384
neon_instr_seq_23_loop:
vldm r0, {d0-d7}
vldm r1, {d8-d15}
vmla.f64 d16, d0, d8
vmla.f64 d17, d0, d9
vmla.f64 d18, d2, d10
vmla.f64 d19, d2, d11
vmla.f64 d16, d4, d12
vmla.f64 d17, d4, d13
vmla.f64 d18, d6, d14
vmla.f64 d19, d6, d15
vmls.f64 d16, d1, d9
vmla.f64 d17, d1, d8
vmls.f64 d18, d3, d11
vmla.f64 d19, d3, d10
vmls.f64 d16, d5, d13
vmla.f64 d17, d5, d12
vmls.f64 d18, d7, d15
vmla.f64 d19, d7, d14
SUBS r3, r3, #1
BNE neon_instr_seq_23_loop
bx lr
在這裡我們可以做一個有趣的實驗，我們可以註釋掉任意一條VLDM指令，然後測試每次迴圈的執行時間。實測的結果是33 CPU cycles。這是一件很有意思的事情。在Cortex-A9核心裡面，NEON/FPU是一個獨立的處理單元，Load/Store Unit也是一個獨立處理單元，兩個單元可以並行執行。Load/Store Unit可以在載入到第一個資料的時候立即把資料forward給NEON/FPU，這樣在只有一條VLDM指令時，只需要引入1個CPU cycles的延遲了。這就提示我們通過合理的打散VLDM指令並和NEON/FPU指令交織（interleave），可以提升指令執行的並行度，並繼 續提升軟體的效能。
到了這個層面，就需要對CPU的微架構（micro architecture）有比較深入的瞭解了。不過對於軟體工程師，沒有必要在這方面花太多的時間，只需要注意一些基本的原則，反覆嘗試幾種可能的組合就好了：
> 在VLDR/VLDM和使用到相關暫存器的資料處理指令之間留出足夠的時間，避免pipeline stall
> VLDM指令能夠快速的把資料forward給暫存器，所以VLDM和資料處理指令之間不要有其他load/store指令
按照上面的原則，我們對程式碼的順序重新調整，得到了下面的彙編程式碼。實測每次迴圈的執行時間從45 CPU cycles縮短為39 CPU cycles。
值得注意的是在這裡我們假定資料已經在L1 cache裡面了。在實際中，資料要從memory載入到L1 cache中，然後再傳到NEON register裡面，這個過程非常複雜。通過上述方法找到的最優指令序列在真實環境中有可能未必是最優的，這時就需要測試幾個在這種簡單情況下最優和次 優的指令序列在真實環境中的效能，從而找出真實環境中效能最優的程式碼。
.align 4
.global neon_instr_seq_35
.arm
neon_instr_seq_35:
LDR r3, =16384
neon_instr_seq_35_loop:
vldr d0, [r0, #0]
vldm r1, {d8-d15}
vmla.f64 d16, d0, d8
vldr d2, [r0, #16]
vmla.f64 d17, d0, d9
vldr d4, [r0, #32]
vmla.f64 d18, d2, d10
vmla.f64 d19, d2, d11
vldr d6, [r0, #48]
vmla.f64 d16, d4, d12
vmla.f64 d17, d4, d13
vldr d1, [r0, #8]
vmla.f64 d18, d6, d14
vmla.f64 d19, d6, d15
vldr d3, [r0, #24]
vmls.f64 d16, d1, d9
vmla.f64 d17, d1, d8
vldr d5, [r0, #40]
vmls.f64 d18, d3, d11
vmla.f64 d19, d3, d10
vldr d7, [r0, #56]
vmls.f64 d16, d5, d13
vmla.f64 d17, d5, d12
vmls.f64 d18, d7, d15
vmla.f64 d19, d7, d14
SUBS r3, r3, #1
BNE neon_instr_seq_35_loop
bx lr
4. 使用PLD指令優化效能
上面的討論都假設資料已經存在於L1 cache中了。在真實的環境中未必會這樣，這時就需要用PLD指令提前把資料載入到L1 cache中。演算法計算量越大，PLD指令對效能的提升也越明顯。
使用PLD指令需要注意：
PLD指令只能載入一個cache line，對Cortex-A9來說一個cache line為32 bytes。
Cortex-A9硬體限制最多有4條PLD指令並行執行，過多的插入PLD指令不會有額外的效能提升。
增加了PLD指令後的完整的彙編程式碼如下所示：
.align 4
.global complex_dot_product_neon_var4
.arm
complex_dot_product_neon_var4:
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ r0: address of source vector a
@ r1: address of source vector b
@ r2: address of destination complex
@ r3: vector length
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
vmov.i32 d16, #0
vmov.i32 d17, #0
vmov.i32 d18, #0
vmov.i32 d19, #0
loop_var4:
vldr d0, [r0, #0]
vldm r1!, {d8-d15}
pld [r0, #64]
pld [r0, #96]
pld [r1, #64]
pld [r1, #96]
vmla.f64 d16, d0, d8
vldr d2, [r0, #16]
vmla.f64 d17, d0, d9
vldr d4, [r0, #32]
vmla.f64 d18, d2, d10
vmla.f64 d19, d2, d11
vldr d6, [r0, #48]
vmla.f64 d16, d4, d12
vmla.f64 d17, d4, d13
vldr d1, [r0, #8]
vmla.f64 d18, d6, d14
vmla.f64 d19, d6, d15
vldr d3, [r0, #24]
vmls.f64 d16, d1, d9
vmla.f64 d17, d1, d8
vldr d5, [r0, #40]
vmls.f64 d18, d3, d11
vmla.f64 d19, d3, d10
vldr d7, [r0, #56]
vmls.f64 d16, d5, d13
vmla.f64 d17, d5, d12
vmls.f64 d18, d7, d15
vmla.f64 d19, d7, d14
add r0, r0, #64
SUBS r3, r3, #4
BNE loop_var4
vadd.f64 d16, d16, d18
vadd.f64 d17, d17, d19
vstm r2!, {d16-d17}
bx lr
5. 測試結果及分析：
資料在OCM和DDR3上的執行結果為：
| 測試項 | 在OCM上的執行時間 | 在DDR3上的執行時間 |
| Compiler Auto-vectorization | 289.677 | 272.526 |
| asm_1 | 175.563 | 396.615 |
| asm_1 with PLD | 70.203 | 180.765 |
| asm_2 | 147.861 | 264.484 |
| asm_2 with PLD | 60.522 | 170.733 |
>Compiler Auto-vectorization為本文最開始的C程式碼通過GCC編譯器優化後的測試
>asm_1為不考慮第3步VLDM/VLDR和NEON資料處理指令交織的彙編程式碼
>asm_2為考慮到第3步VLDM/VLDR和NEON資料處理指令交織後的彙編程式碼
從測試結果來看，我們可以注意到幾點：
>充分優化後的程式碼（asm_2 with PLD）在OCM上執行的結果非常接近NEON的最優效能。NEON資料處理指令需要32 CPU cycles，根據Zynq-7000 TRM， OCM的latency為23 cycles。這時PLD指令可以在處理當前載入的資料的同時，提前把下一批要處理的資料載入到L1 cache中。
>對程式碼（asm_2 with PLD）來說，資料在DDR3上的效能要差於在OCM上的效能。這個也比較好理解，因為DDR3的latency要遠大於NEON資料處理指令執行時間 （32 CPU cycles），在整個運算過程中，PLD指令並不能有效的提前把下一批待處理的資料載入到L1 cache中。或者說，只有部分資料能夠被提前載入到L1 cache中。
>NEON資料處理指令執行時間越長，就越容易抵消掉記憶體系統延遲帶來的影響。
>資料在OCM上時，系統性能要優於資料在DDR3上。不過這時還要額外考慮資料在OCM上搬進搬出的開銷。當然，如果在系統設計時就考慮到這一點，由硬體直接使用 OCM，系統性能就能夠得到明顯的提升。
6. 小結
通過這個真實案例，我們演示了一些NEON/FPU彙編開發的技巧。通過活學活用這些技巧，我們就能充分發揮Zynq-7000的計算能力，實現一個高度優化的高效能嵌入式系統。