AVX2指令集優(yōu)化整形數(shù)組求和算法
一、AVX2指令集介紹
AVX2是SIMD(單指令多數(shù)據(jù)流)指令集，支持在一個指令周期內(nèi)同時對256位內(nèi)存進行操作。包含乘法，加法，位運算等功能。下附Intel官網(wǎng)使用文檔。
我們本次要用到的指令有 __m256i _mm256_add_epi32(__m256i a, __m256i b), __m256i _mm256_add_epi64等
它們可以一次取256位的內(nèi)存，并按32/64位一個整形進行加法運算。下附官網(wǎng)描述。
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 |
二、代碼實現(xiàn)
0. 數(shù)據(jù)生成
為了比較結果，我們生成從1到N的等差數(shù)列。這里利用模版兼容不同數(shù)據(jù)類型。由于AVX2指令集一次要操作多個數(shù)據(jù)，為了防止訪存越界，我們將大小擴展到256的整數(shù)倍位比特，也就是32字節(jié)的整數(shù)倍。
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. 普通數(shù)組求和
為了比較性能差異，我們先實現(xiàn)一份普通的數(shù)組求和。這里也使用模版。
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的整形變量，每次從數(shù)組中取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是橫向加法，具體實現(xiàn)類似下圖，可以幫我們實現(xiàn)數(shù)組內(nèi)求和：
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];
}
三、性能測試
測試環(huán)境
| 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庫獲取系統(tǒng)時鐘計算運行時間，精確到毫秒級
uint64_t getTime()
{
uint64_t timems = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now().time_since_epoch()).count();
return timems;
}
測試內(nèi)容
對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個。
第二次測試
測試命令
現(xiàn)在我們再開啟O2編譯優(yōu)化試一試：
g++ -O2 -mavx2 avx_big_integer.cpp ./a.out
測試結果
| 方法 | 耗時(ms) |
|---|---|
| AVX2加法 32位 | 269 |
| 普通加法 32位 | 342 |
| AVX2加法 64位 | 516 |
| 普通加法 64位 | 750 |
發(fā)現(xiàn)開啟O2后相對的性能提升減小很多。
四、總結
使用AVX2進行指令層面的并行加法，確實提高了運算效率。
但是，這里可能有朋友會有疑問，我們明明是每次同時處理了4/8個整形，為什么加速比達不到4/8倍呢？
個人推斷原因：
- VX2加法指令的長度大于普通加法，單次指令實現(xiàn)比普通加法略慢一些。
- 在進行AVX2加法時，我們每次需要拷貝256位內(nèi)存進對應256位的變量內(nèi)，再把結果拷貝出來，存在拷貝的開支。
- 普通加法在for循環(huán)內(nèi)可能會激發(fā)流水線執(zhí)行。
- 開啟O2后普通加法可以激發(fā)并行，提高實際運行效率。
以上就是AVX2指令集優(yōu)化整形數(shù)組求和算法的詳細內(nèi)容，更多關于AVX2指令集整形數(shù)組求和的資料請關注腳本之家其它相關文章！
相關文章
解決pip?install?dlib報錯C++11?is?required?to?use?dlib
這篇文章主要介紹了在使用pip?install?dlib安裝dlib的時候報錯C++11?is?required?to?use?dlib的解決方法，需要的的小伙伴可以參考一下，希望對你有所幫助2022-02-02
線性表的鏈式存儲又稱為單鏈表，它是指通過一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素。本文將用C++實現(xiàn)單鏈表，需要的可以參考一下2022-06-06
C++兩個cpp文件間如何進行各自函數(shù)的調(diào)用方式
這篇文章主要介紹了C++兩個cpp文件間如何進行各自函數(shù)的調(diào)用方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
這篇文章主要介紹了C++的.cpp文件運行全過程，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
本文主要給大家分享的是作者在使用C++制作俄羅斯方塊小游戲的時候所需要的常用的函數(shù)，有需要的小伙伴可以借鑒下，希望大家能夠喜歡。2017-12-12
今天小編就為大家分享一篇關于C++使用初始化列表的方式來初始化字段的方法，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
這篇文章主要為大家詳細介紹了C++實現(xiàn)雙向鏈表，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-05-05
詳解_beginthreadex()創(chuàng)建線程
這篇文章主要介紹了詳解_beginthreadex()創(chuàng)建線程，使用_beginthreadex(),需要的頭文件支持#include <process.h> 下面我們就來看看具體的實現(xiàn)吧2022-01-01
++和--運算符分別是+=1和-=1的簡寫。設計這樣兩個運算符的本意是?便程序員，但i++和++i使?不恰當有時候會造成混淆，反倒令剛入門的C程序員有點混亂2022-04-04
Qt是目前最先進、最完整的跨平臺C++開發(fā)工具,下面這篇文章主要給大家介紹了關于QT中幾種常用的排序函數(shù)用法的相關資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2024-01-01