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