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)在我們再開啟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ù)組求和的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
vc提示unexpected end of file found的原因分析
這篇文章主要介紹了vc提示unexpected end of file found的原因分析,給出了幾點(diǎn)常見錯(cuò)誤原因的分析,需要的朋友可以參考下2015-05-05
今天遇到單向鏈表的反轉(zhuǎn)的問題,于是靜下心來好好想了一番。下面這篇文章主要給大家介紹了關(guān)于單鏈表反轉(zhuǎn)的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-02-02
VS2019開發(fā)Linux C++程序的實(shí)現(xiàn)步驟
由于很多unix特有的函數(shù)無法在Windows上使用，而Vim又用的不太順手，突然想到最初用vs的時(shí)候有一個(gè)基于Linux的C++開發(fā)。本文就來介紹一下，感興趣的可以了解一下2021-07-07
Qt+Quick實(shí)現(xiàn)圖片演示器的開發(fā)
這篇文章主要為大家詳細(xì)介紹了Qt如何利用Quick實(shí)現(xiàn)圖片演示器的開發(fā)，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)Qt有一定的幫助，需要的可以參考一下2023-01-01
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)航班訂票系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-12-12
C++實(shí)現(xiàn)LeetCode(111.二叉樹的最小深度)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(111.二叉樹的最小深度),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
對(duì)圖像中的所有點(diǎn)或特殊點(diǎn)進(jìn)行運(yùn)算，所以遍歷圖像就顯得很重要，如何高效的遍歷圖像是一個(gè)很值得探討的問題，本文給大家?guī)砹硕喾N方法操作OpenCV?通過Mat遍歷圖像，感興趣的朋友一起看看吧2022-02-02
這篇文章主要介紹了C++中指針和引用的區(qū)別，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04
C語言實(shí)現(xiàn)學(xué)生考勤系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)學(xué)生考勤系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
VC動(dòng)態(tài)生成菜單項(xiàng)的實(shí)現(xiàn)方法
這篇文章主要介紹了VC動(dòng)態(tài)生成菜單項(xiàng)的實(shí)現(xiàn)方法,在桌面應(yīng)用程序開發(fā)中常會(huì)用到的一個(gè)功能,需要的朋友可以參考下2014-08-08