AVX2指令集優化整形數組求和算法

Posted on by

一、AVX2指令集介紹

AVX2是SIMD(單指令多數據流)指令集，支持在一個指令周期內同時對256位內存進行操作。包含乘法，加法，位運算等功能。下附Intel官網使用文檔。

Intel® Intrinsics Guide

我們本次要用到的指令有 __m256i _mm256_add_epi32(__m256i a, __m256i b), __m256i _mm256_add_epi64等

它們可以一次取256位的內存，並按32/64位一個整形進行加法運算。下附官網描述。

Synopsis

__m256i _mm256_add_epi64 (__m256i a, __m256i b)
#include <immintrin.h>
Instruction: vpaddq ymm, ymm, ymm
CPUID Flags: AVX2

Description

Add packed 64-bit integers in a and b, and store the results in dst.

Operation

FOR j := 0 to 3
	i := j*64
	dst[i+63:i] := a[i+63:i] + b[i+63:i]
ENDFOR
dst[MAX:256] := 0

Performance

Architecture Latency Throughput (CPI)
Icelake 1 0.33
Skylake 1 0.33
Broadwell 1 0.5
Haswell 1 0.5

 

二、代碼實現

0. 數據生成

為瞭比較結果，我們生成從1到N的等差數列。這裡利用模版兼容不同數據類型。由於AVX2指令集一次要操作多個數據，為瞭防止訪存越界，我們將大小擴展到256的整數倍位比特，也就是32字節的整數倍。

uint64_t lowbit(uint64_t x)
{
    return x & (-x);
}
uint64_t extTo2Power(uint64_t n, int i)//arraysize datasize
{
    while(lowbit(n) < i)
        n += lowbit(n);
    return n;
}

template <typename T>
T* getArray(uint64_t size)
{
    uint64_t ExSize = extTo2Power(size, 32/sizeof(T));
    T* arr = new T[ExSize];
    for (uint64_t i = 0; i < size; i++)
        arr[i] = i+1;
    for (uint64_t i = size; i < ExSize; i++)
        arr[i] = 0;
    return arr;
}

1. 普通數組求和

為瞭比較性能差異，我們先實現一份普通的數組求和。這裡也使用模版。

template <typename T>
T simpleSum(T* arr, uint64_t size)
{
    T sum = 0;
    for (uint64_t i = 0; i < size; i++)
        sum += arr[i];
    return sum;
}

2. AVX2指令集求和：32位整形

這裡我們預開一個avx2的整形變量，每次從數組中取8個32位整形，加到這個變量上，最後在對這8個32位整形求和。

int32_t avx2Sum(int32_t* arr, uint64_t size)
{
    int32_t sum[8] = {0};
    __m256i sum256 = _mm256_setzero_si256();
    __m256i load256 = _mm256_setzero_si256();
    for (uint64_t i = 0; i < size; i += 8)
    {
        load256 = _mm256_loadu_si256((__m256i*)&arr[i]);
        sum256 = _mm256_add_epi32(sum256, load256);
    }
    sum256 = _mm256_hadd_epi32(sum256, sum256);
    sum256 = _mm256_hadd_epi32(sum256, sum256);
    _mm256_storeu_si256((__m256i*)sum, sum256);
    sum[0] += sum[4];
    return sum[0];
}

這裡的hadd是橫向加法，具體實現類似下圖，可以幫我們實現數組內求和：

3. AVX2指令集求和：64位整形

int64_t avx2Sum(int64_t* arr, uint64_t size)
{
    int64_t sum[4] = {0};
    __m256i sum256 = _mm256_setzero_si256();
    __m256i load256 = _mm256_setzero_si256();
    for (uint64_t i = 0; i < size; i += 4)
    {
        load256 = _mm256_loadu_si256((__m256i*)&arr[i]);
        sum256 = _mm256_add_epi64(sum256, load256);
    }
    _mm256_storeu_si256((__m256i*)sum, sum256);
    sum[0] += sum[1] + sum[2] + sum[3];
    return sum[0];
}

三、性能測試

測試環境

Device Description
CPU Intel Core i9-9880H 8-core 2.3GHz
Memory DDR4-2400MHz Dual-Channel 32GB
complier Apple Clang-1300.0.29.30

計時方式

利用chrono庫獲取系統時鐘計算運行時間，精確到毫秒級

uint64_t getTime()
{
    uint64_t timems = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now().time_since_epoch()).count();
    return timems;
}

測試內容

對1到1e9求和，答案應該為500000000500000000, 分別測試32位整形和64位整形。

	uint64_t N = 1e9;
    // compare the performance of normal add and avx2 add
    uint64_t start, end;
    // test int32_t
    cout << "compare int32_t sum: " << endl;
    int32_t* arr = getArray<int32_t>(N);
    start = getTime();
    int32_t sum = simpleSum(arr, N);
    end = getTime();
    cout << "int32_t simpleSum time: " << end - start << endl;
    cout << "int32_t simpleSum sum: " << sum << endl;
    start = getTime();
    sum = avx2Sum(arr, N);
    end = getTime();
    cout << "int32_t avx2Sum time: " << end - start << endl;
    cout << "int32_t avx2Sum sum: " << sum << endl;
    delete[] arr;
    cout << endl << endl;
    // test int64_t
    cout << "compare int64_t sum: " << endl;
    int64_t* arr2 = getArray<int64_t>(N);
    start = getTime();
    int64_t sum2 = simpleSum(arr2, N);
    end = getTime();
    cout << "int64_t simpleSum time: " << end - start << endl;
    cout << "int64_t simpleSum sum: " << sum2 << endl;
    start = getTime();
    sum2 = avx2Sum(arr2, N);
    end = getTime();
    cout << "int64_t avx2Sum time: " << end - start << endl;
    cout << "int64_t avx2Sum sum: " << sum2 << endl;
    delete[] arr2;
    cout << endl << endl;

進行性能測試

第一次測試

測試命令

g++ -mavx2 avx_big_integer.cpp 
./a.out

測試結果

方法 耗時(ms)
AVX2加法 32位 537
普通加法 32位 1661
AVX2加法 64位 1094
普通加法 64位 1957

可以看出，avx2在32位加法上大致能快3倍，在64位加法上隻能快2倍，因為64位下每次隻能操作4個變量，而32位能操作8個。

第二次測試

測試命令

現在我們再開啟O2編譯優化試一試：

g++ -O2 -mavx2 avx_big_integer.cpp 
./a.out

測試結果

方法 耗時(ms)
AVX2加法 32位 269
普通加法 32位 342
AVX2加法 64位 516
普通加法 64位 750

發現開啟O2後相對的性能提升減小很多。

四、總結

使用AVX2進行指令層面的並行加法，確實提高瞭運算效率。
但是，這裡可能有朋友會有疑問，我們明明是每次同時處理瞭4/8個整形，為什麼加速比達不到4/8倍呢？

個人推斷原因：

  • VX2加法指令的長度大於普通加法，單次指令實現比普通加法略慢一些。
  • 在進行AVX2加法時，我們每次需要拷貝256位內存進對應256位的變量內，再把結果拷貝出來，存在拷貝的開支。
  • 普通加法在for循環內可能會激發流水線執行。
  • 開啟O2後普通加法可以激發並行，提高實際運行效率。

以上就是AVX2指令集優化整形數組求和算法的詳細內容，更多關於AVX2指令集整形數組求和的資料請關註WalkonNet其它相關文章！

推薦閱讀：