CPU優化技術之自動向量化實例

一、概述

SIMD 作為一種重要的并行化技術，在提升性能的同時也會增加開發的難度。目前大多數編譯器都具有自動向量化的功能，將 C/C++ 代碼自動替換為 SIMD 指令。

從編譯技術上來說，自動向量化一般包含兩部分：循環向量化（Loop vectorization）和超字并行向量化（SLP，Superword-Level Parallelism vectorization，又稱Basic block vectorization）。

演示代碼：

void add(int *a, int *b, int n, int * restrict sum)
{
    // it is assumed that the input n is an integer multiple of 4
    for (int i = 0; i < (n & ~3); ++i)
    {
        sum[i] = a[i] + b[i];
    }
}

循環向量化：將循環進行展開，增加循環中的執行代碼來減少循環次數。如以下代碼將循環次數精簡到之前的1/4。

for (int i = 0; i < (n & ~3); i += 4)
{
    sum[i]     = a[i    ] + b[i];
    sum[i + 1] = a[i + 1] + b[i + 1];
    sum[i + 2] = a[i + 2] + b[i + 2];
    sum[i + 3] = a[i + 3] + b[i + 3];
}

SLP 向量化：編譯器將多個標量運算綁定到一起，使其成為向量運算。下圖將四次標量運算替換為一次向量運算。

SLP 自動向量化

接下來介紹如何通過編譯器實現自動向量化。

二、編譯器配置

目前支持自動向量化的編譯器有 Arm Compiler 6、Arm C/C++ Compiler、LLVM-clang 以及 GCC，這幾種編譯器間的相互關系如下表所示。

自動向量化默認不會被啟用，編程人員需要向編譯器提供允許自動向量化的“許可證”來對自動向量化功能進行使能。

A. Arm Compiler 中使能自動向量化

下文中 Arm Compiler 6 與 Arm C/C++ Compiler 使用 armclang 統稱，armclang 使能自動向量化配置信息如下表所示：

armclang 實現自動向量化示例：

# AArch32
armclang --target=arm-none-eabi -mcpu=cortex-a53 -O1 -fvectorize main.c

# AArch64
armclang --target=aarch64-arm-none-eabi -O2 main.c

B. LLVM-clang中使能自動向量化

Android NDK 從 r13 開始以 clang 為默認編譯器，本節通過 cmake 調用Android NDK r19c 工具鏈展示 clang 的自動向量化方法。

使用 Android NDK 工具鏈使能自動向量化配置參數如下表：

在 CMake 中配置自動向量化方式如下：

# method 1
set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -O1 -fvectorize")
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -O1 -fvectorize")


# method 2
set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -O2")
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -O2")

C. GCC 中使能自動向量化

在 gcc 中使能自動向量化配置參數如下：

在不明確配置 -mcpu 的情況下，編譯器將使用默認配置（取決于編譯工具鏈時的選項設置）進行編譯。

通常情況下 -mfpu 和 -mcpu 的配置存在關聯性，對應關系如下。（如當選取-mcpu為cortex-a8時，-mfpu一般設置為vfpv3或neon）

gcc 中實現自動向量化的編譯配置如下：

# AArch32
arm-none-linux-gnueabihf-gcc -mcpu=cortex-a53 -mfpu=neon -ftree-vectorize -O2 main.c


# AArch64
aarch64-none-linux-gnu-gcc?-mcpu=cortex-a53?-ftree-vectorize?-O2?main.c

此外，gcc 中可以通過 -fopt-info-vec 命令查看自動向量化的詳細信息，比如哪些代碼實現了向量化，哪些代碼沒有實現向量化及沒有進行向量化的原因。

D. 自動向量化實例

我們以上節的求和示例代碼，來對編譯器自動向量化的功能進行演示。編譯器以 32 位 arm-gcc 為例：

# automatic vectorization is not enabled
arm-none-linux-gnueabihf-gcc -O2 main.c -o avtest


# automatic vectorization is enabled
arm-none-linux-gnueabihf-gcc?-mfpu=neon?-ftree-vectorize?-O2?main.c?-o?avtest

使用 objdump 查看反匯編代碼，反匯編命令如下：

arm-none-linux-gnueabihf-objdump?-d?avtest?>?assemble.txt

反匯編結果對比如下圖:

反匯編代碼

啟用自動向量化之后，編譯器通過矢量化加載?(ldr -> vld1）、求和?(add -> vadd)以及保存?(str -> vst1)等指令，將每次循環中處理的數據變為 4 個，循環次數精簡為之前的 1/4。

三、自動向量化友好型代碼

基于一定的編程優化準則，可以更好的協助編譯器完成自動向量化的工作，獲得理想的性能狀態。

A. 避免使用難以向量化的語句

數據依賴

當循環中存在數據依賴時，編譯器無法進行向量化。

下述代碼中計算 a[i] 時依賴上一次循環的輸出，無法被向量化。

// the output of a[i] depends on its last result
for (int i = 1; i < n; ++i)
{
    a[i] = a[i - 1] + 1;
}

多級指針

編譯器無法對間接尋址，多級索引、多級解引用等行為進行向量化，盡量避免使用多級指針。

下述代碼通過 idx 進行了多級索引，無法被向量化。

// idx is unpredictable, so this code cannot be vectorized
for (int i = 0; i < n; ++i)
{
    sum[idx[i]] = a[idx[i]] + b[idx[i]];
}

條件及跳轉語句

當循環中存在條件語句或跳轉語句時，代碼很難被向量化。因此應盡量避免在循環中的使用if、break等語句。當循環中需要調用函數時，盡量使用內聯函數進行替換。

下述代碼通過調用內聯函數 add_single2 避免發生函數跳轉。

__attribute__((noinline)) int add_single1(int a, int b);


__inline__ __attribute__((always_inline)) int add_single2(int a, int b);


void add(const int *a, const int *b, int n, int * restrict sum)
{
    for (int i = 0; i < (n & ~3); ++i)
    {
        // replace normal functions with inline functions
        // sum[i] = add_single1(a[i], b[i]);
        sum[i] = add_single2(a[i], b[i]);
    }
}

長數據類型

neon 對 64 位長數據類型的支持有限，且較小的數據位寬有更高的并行度，應盡量選用較小的數據類型。當程序中存在浮點數據時，指明其數據類型。

下述代碼指明1.0是浮點數據，否則編譯器會優先將其理解為double。

// assume that array sum and a are floating-point arrays
for (int i = 0; i < (n & ~3); ++i)
{
    // replace 1.0 with 1.f
    // sum[i] = a[i] + 1.0;
    sum[i] = a[i] + 1.f;
}

B. 增加自動向量化信息

地址交疊

指針操縱同一片數據區的情況被稱為地址交疊。地址交疊會阻止自動向量化操作。

當程序不會發生地址交疊時，用 restrict 限定符（C99 引入）在代碼中聲明指針所指區域是獨立的。

下述代碼通過 restrict 限定 sum 與 a、b 間沒有地址交疊的情況。

// add restrict before the output parameter sum
void?add(const?int?*a,?const?int?*b,?int?n,?int?*?restrict?sum)

數組尺寸

明確數組尺寸，使其達到向量化處理長度的整數倍。但應注意處理不足向量化部分的剩余數據。

下述代碼通過掩碼操作表明處理循環次數是 4 的整數倍。

// make number of cycles is an integer multiple of 4, 
for (int i = 0; i < (n & ~3); ++i)
// don't forget to process the remaining data

循環展開

在一些編譯器中可以通過在 for 循環之前增加預處理語句告知編譯器循環展開級數。

下述代碼告知 armclang 編譯器希望將循環展開 4 次。

// #pragma unroll (4) // armcc
#pragma clang loop interleave_count(4) //armclang
for (int i = 0; i < n; ++i)
{
    // ...
}

結構體加載

編譯器僅會對每一成員都有操作的結構體加載操作進行自動向量化，可以結合實際需求考慮去除用于結構體對齊的填充數據。

下述代碼中刪除用于填充結構體的變量 padding 以避免無法向量化。

struct st_align  
{    
    char r;    
    char g;
    char b;
    // delete the data used to populate the structure
    // char padding;
};

neon 加載指令要求結構體中的所有項有相同的大小。

下述代碼中結構體由于 short 類型與 char 類型不一致而不會被執行自動向量化。

struct st_align  
{    
    short r; // change short to char to get auto-vectoration
    char g;
    char b;  
};

循環構造

盡量通過?

下述代碼通過調整i的范圍實現?

// use '<' to construct a loop instead of '<='
// for(int i = 1; i <= n; ++i)
for (int i = 1; i < n + 1; ++i)
{
    // ...
}

數組索引

當對數組進行操作時，使用數組索引替代指針索引。

下述代碼通過 sum[i]?進行索引，而不是*(sum + i)。

// replace arrary with pointer
// *(sum + i) = *(a + i) + *(b + i);
sum[i] = a[i] + b[i];

C. 重排數據實現緩存友好

循環合并

當數據連續存儲在結構體中時，可以進行循環合并操作，即在一個循環內處理臨近的數據，提高緩存命中率。

下述代碼將 r、g、b 三個通道的處理合并到一個循環中。

// combine the rgb operation
/*
for (...)
{
    pixels[i].r = ....;
}  
for (...)
{
    pixels[i].g = ....;
}  
for (...)
{
    pixels[i].b = ....;
}
*/


// cache friendly code
for (...) 
{    
    pixels[i].r = ....;    
    pixels[i].g = ....;    
    pixels[i].b = ....;  
}

四、總結

本章節主要介紹了自動向量化的相關內容，其優缺點對比如下：