可以自動(dòng)矢量化的代碼
使用gcc version 4.3.4的gcc編譯器栗恩,編譯下面的示例代碼:
int main(){
const unsigned int ArraySize = 10000000;
float* a = new float[ArraySize];
float* b = new float[ArraySize];
float* c = new float[ArraySize];
for (unsigned int j = 0; j< 200 ; j++) // some repetitions
for ( unsigned int i = 0; i < ArraySize; ++ i)
c[i] = a[i] * b[i];
}
編譯并運(yùn)行上面的代碼:
g++ vectorisable_example.cpp -o vectorisable_example -O2 time ./vectorisable_example
簡(jiǎn)單且预,現(xiàn)在我們看下如何告訴 compiler 自動(dòng)對(duì)代碼進(jìn)行矢量化:
g++ vectorisable_example.cpp -o vectorisable_example_vect -O2 -ftree-vectorize time ./vectorisable_example_vect
第二種編譯方式,產(chǎn)生的可執(zhí)行程序比第一種產(chǎn)生的可執(zhí)行程序運(yùn)行的更快?我們深入研究下措伐,看看為什么他就這么快侦另?
簡(jiǎn)介
從上世紀(jì)九十年代后期開(kāi)始秩命,英特爾就已經(jīng)將單指令多數(shù)據(jù)(SIMD)機(jī)器指令集成到其商品CPU產(chǎn)品線中。這些SIMD指令允許一次將相同的數(shù)學(xué)運(yùn)算(乘褒傅,加...)應(yīng)用于2,4或甚至更多的數(shù)據(jù)值上弃锐。這組數(shù)據(jù)值也被稱為“vector”(不要與代數(shù)中的vector混淆)。理論上矢量計(jì)算的性能增益等于CPU可以容納的矢量單位的數(shù)量樊卓。
盡管SIMD指令集已經(jīng)集成到普通CPU中相當(dāng)長(zhǎng)一段時(shí)間了拿愧,但是這些擴(kuò)展功能(SIMD指令集)只能通過(guò)在C或者C++代碼中通過(guò)準(zhǔn)匯編語(yǔ)言進(jìn)行使用。像GNU編譯器系列(GCC)這樣的現(xiàn)代編譯器現(xiàn)在可以將常規(guī)的C或C ++源代碼轉(zhuǎn)換成向量操作碌尔。這個(gè)過(guò)程被稱為自動(dòng)矢量化(auto-vectorization)浇辜。
這篇文章,我們將會(huì)介紹必要的軟件工具和編程技術(shù)唾戚,并進(jìn)一步提供利用GCC自動(dòng)矢量化功能的示例源代碼
硬件
要估算自動(dòng)矢量化代碼可以帶來(lái)多大的性能提升柳洋,首先需要了解您正在使用的CPU的能力以及CPU可以處理多少個(gè)Vector。因此叹坦,運(yùn)行以下命令:
$ cat /proc/cpuinfo...
flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2ss ht tm pbe syscall nx rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2ssse3cx16 xtpr pdcmsse4_1 sse4_2x2apic popcnt xsaveavxlahf_lm ida arat epb xsaveopt pln pts dts tpr_shadow vnmi flexpriority ept vpid...
在CPU屬性中熊镣,您將找到有關(guān)SIMD功能的信息(以粗體突出顯示)。若信息中包含下表列出的字符串募书,則您的CPU支持(SIMD)功能:
Name | Register Size | Amount of floats | Amount of doubles |
---|---|---|---|
mmx (*) | 64 bit | 0 | 0 |
sse2 | 128 bit | 4 | 2 |
ssse3 | 128 bit | 4 | 2 |
sse4_1 | 128 bit | 4 | 2 |
sse4_2 | 128 bit | 4 | 2 |
avx | 256 bit | 8 | 4 |
- 英特爾處理器上的第一個(gè)矢量單元只能容納兩個(gè)迭代器绪囱。
所有Intel和AMD 64位CPU都至少支持sse2指令集。 AVX指令集已于2011年推出莹捡,采用Sandy Bridge架構(gòu)鬼吵,可在最新一代Mac Book Pro筆記本電腦上使用。
AVX指令集可以同時(shí)對(duì)四個(gè)雙精度浮點(diǎn)值應(yīng)用數(shù)學(xué)運(yùn)算篮赢。因此齿椅,與未使用矢量單位的版本相比琉挖,應(yīng)用程序可以實(shí)現(xiàn)的最大性能增益是4倍。
Vector單位大小的持續(xù)增大涣脚,反應(yīng)了是計(jì)算機(jī)微體系結(jié)構(gòu)演化的新趨勢(shì)示辈。十年前,計(jì)算機(jī)的時(shí)鐘頻率幾乎每年翻一番遣蚀。計(jì)算機(jī)的時(shí)鐘頻率已經(jīng)達(dá)到了極限矾麻,制造商轉(zhuǎn)而開(kāi)始提供越來(lái)越大的矢量單位,并且在每個(gè)芯片中提供越來(lái)越多的核心數(shù)量芭梯。
哪些代碼可以被auto-vectorized ?
為了將計(jì)算分布到CPU的矢量單元射富,編譯器必須對(duì)源代碼的依賴性和相互影響有一個(gè)很好的理解。但最重要的是粥帚,編譯器必須能夠檢測(cè)出那些代碼段可以使用SIMD指令進(jìn)行優(yōu)化胰耗。最簡(jiǎn)單的情況是對(duì)數(shù)組執(zhí)行計(jì)算的循環(huán):
for ( unsigned int i = 0; i < ArraySize; ++ i)
{
c[i] = a[i] * b[i];
}
使用等于或者高于gcc461(在slc5_amd64_gcc461 scram體系結(jié)構(gòu)的服務(wù)器中可用)版本的gcc編譯器,編譯的時(shí)候芒涡,一定要帶上is-ftree-vectorize柴灯。
注意:從自動(dòng)矢量化中獲益最多的循環(huán)是包含數(shù)學(xué)運(yùn)算的循環(huán)。只是迭代對(duì)象集合的循環(huán)不會(huì)獲利费尽,在大多數(shù)情況下甚至不能自動(dòng)矢量化赠群。
可以在這里找到可以自動(dòng)矢量化的循環(huán)結(jié)構(gòu)列表:http://gcc.gnu.org/projects/tree-ssa/vectorization.html
一旦你使用選項(xiàng)-ftree-vectorizer-verbose = 7編譯你的代碼,GCC將會(huì)給你一個(gè)關(guān)于你的程序中所有循環(huán)的詳細(xì)報(bào)告旱幼,以及它們是否已經(jīng)被自動(dòng)矢量化了查描。以下報(bào)告是成功對(duì)循環(huán)進(jìn)行向量化的結(jié)果:
autovect.cpp:66: note: vect_model_load_cost: aligned.
autovect.cpp:66: note: vect_get_data_access_cost: inside_cost = 1, outside_cost = 0.
autovect.cpp:66: note: vect_model_load_cost: aligned.
autovect.cpp:66: note: vect_get_data_access_cost: inside_cost = 2, outside_cost = 0.
autovect.cpp:66: note: vect_model_store_cost: aligned.
autovect.cpp:66: note: vect_get_data_access_cost: inside_cost = 3, outside_cost = 0.
autovect.cpp:66: note: vect_model_load_cost: aligned.
autovect.cpp:66: note: vect_model_load_cost: inside_cost = 1, outside_cost = 0 .
autovect.cpp:66: note: vect_model_load_cost: aligned.
autovect.cpp:66: note: vect_model_load_cost: inside_cost = 1, outside_cost = 0 .
autovect.cpp:66: note: vect_model_simple_cost: inside_cost = 1, outside_cost = 0 .
autovect.cpp:66: note: vect_model_simple_cost: inside_cost = 1, outside_cost = 1 .
autovect.cpp:66: note: vect_model_store_cost: aligned.
autovect.cpp:66: note: vect_model_store_cost: inside_cost = 1, outside_cost = 0 .
autovect.cpp:66: note: Cost model analysis:
Vector inside of loop cost: 5
Vector outside of loop cost: 11
Scalar iteration cost: 5
Scalar outside cost: 0
prologue iterations: 0
epilogue iterations: 2
Calculated minimum iters for profitability: 3
autovect.cpp:66: note: Profitability threshold = 3
autovect.cpp:66: note: Profitability threshold is 3 loop iterations.
autovect.cpp:66: note: LOOP VECTORIZED.
若一個(gè)循環(huán)不能被向量化, GCC將會(huì)給出原因:
autovect.cpp:133: note: not vectorized: control flow in loop.
上面的輸出的含義是:在循環(huán)中調(diào)用了tostd :: cout,引入了一個(gè)控制流柏卤,從而無(wú)法對(duì)該循環(huán)進(jìn)行向量化冬三。
讓GCC自動(dòng)對(duì)你的代碼進(jìn)行向量化
想要讓GCC對(duì)自己的代碼進(jìn)行自動(dòng)向量化,需要使用最新的編譯器缘缚,建議使用至少GCC 4.6.1版本的編譯器勾笆,通常來(lái)說(shuō),版本越新越好桥滨。
編譯器標(biāo)示
想要打開(kāi)auto-vectorization窝爪,使用標(biāo)示:
-ftree-vectorize
如果您使用優(yōu)化級(jí)別-O3or進(jìn)行編譯,則隱式啟用此選項(xiàng)齐媒。
想要得到哪些loop是已經(jīng)被auto-vectorized和哪些loops沒(méi)有被成功矢量化以及原因蒲每,可以使用選項(xiàng):
-ftree-vectorizer-verbose=7
關(guān)于如何閱讀這個(gè)輸出,請(qǐng)看下面的Real-World代碼示例部分喻括。
某些循環(huán)結(jié)構(gòu)(例如浮點(diǎn)數(shù)的減法)只能在允許編譯器改變數(shù)學(xué)運(yùn)算順序的情況下進(jìn)行矢量化邀杏。要做到這一點(diǎn),需要使用選項(xiàng):
-ffast-math
如果您使用優(yōu)化級(jí)別-Ofast双妨,則會(huì)隱式啟用該選項(xiàng)淮阐。請(qǐng)注意,fast-math選項(xiàng)會(huì)修正修改浮點(diǎn)運(yùn)算中的錯(cuò)誤操作刁品。詳情請(qǐng)看http://gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Optimize-Options.html
此外泣特,您可以明確指出編譯器在生成二進(jìn)制文件時(shí)應(yīng)使用哪一個(gè)SIMD指令集。在編譯x86-64架構(gòu)時(shí)挑随,GCC默認(rèn)使用SSE2指令集状您。如果要啟用AVX指令集,請(qǐng)使用編譯器標(biāo)志:
-mavx
需要注意的是兜挨,要運(yùn)行二進(jìn)制文件的機(jī)器必須支持AVX指令集膏孟。您還可以讓通過(guò)下面的選項(xiàng),讓編譯器自己決定使用機(jī)器中的哪個(gè)指令集:
-march=native
若你想要使用 C++11 的特性拌汇,例如:lambda 表達(dá)式,一定要確認(rèn)開(kāi)啟了新的C++ Standard:
-std=gnu++0x
啟用auto-vectorization最佳實(shí)踐
使用數(shù)組結(jié)構(gòu)
想要啟用自動(dòng)向量化柒桑,編譯器不僅需要能夠分析循環(huán)迭代,還需要能夠分析訪問(wèn)內(nèi)存的模式噪舀。嵌套數(shù)組的復(fù)雜類型很難或不可能由編譯器自動(dòng)進(jìn)行矢量化魁淳。建議使用簡(jiǎn)單的c數(shù)組orstd :: arrays(在C ++ 11中引入)來(lái)保存數(shù)據(jù),并允許編譯器以連續(xù)的方式訪問(wèn)數(shù)據(jù)与倡。這也將使您的程序能夠利用CPU的各種緩存界逛。
如果你需要可變數(shù)組,建議使用std :: vectorand 獲取指向第一個(gè)元素的指針來(lái)訪問(wèn)循環(huán)中的元素:
std::vectormyData(23);
double * pMyData = &myData.front();
...
pMyData[i] += 5;
數(shù)組結(jié)構(gòu)的完整示例可以在下面的“綜合代碼示例”一節(jié)中找到纺座。
限制分支
盡力限制for循環(huán)內(nèi)的分支息拜。 GCC能夠?qū)⒁恍﹊f語(yǔ)句翻譯成向量化的代碼,但很有限净响。這樣做時(shí)少欺,將評(píng)估所有可能的分支,并丟棄未采用分支的值馋贤。
盡量簡(jiǎn)化代碼
如果在for循環(huán)中有復(fù)雜的計(jì)算狈茉,您希望GCC對(duì)其進(jìn)行矢量化,可以考慮使用C ++ 11中的lambda表達(dá)式掸掸,將它們分解為更簡(jiǎn)單的代碼氯庆。在這里可以找到C ++11新功能的介紹:http://en.wikipedia.org/wiki/Anonymous_function#C.2B.2B
這里是一個(gè)lambda函數(shù)的例子,用來(lái)計(jì)算一個(gè)double變量的平方扰付。
auto kernel_square =
[] // capture nothing
( double const& a) // take 1 parameter by reference
->double // lambda function returns the square
{
return ( a * a );
};
在循環(huán)中調(diào)用lambda函數(shù):
for ( unsigned int i = 0; i < size; ++ i)
{
ptr_square[i] = kernel_square( ptr_x[i] ) + kernel_square( ptr_y[i] ) + kernel_square( ptr_z[i] ) ;
}
請(qǐng)注意堤撵,此代碼將由GCC自動(dòng)矢量化。對(duì)lambda函數(shù)的調(diào)用不會(huì)像常規(guī)函數(shù)調(diào)用那樣羽莺,造成特別大的開(kāi)銷实昨,因?yàn)榇a會(huì)被完全內(nèi)聯(lián)。
另一個(gè)更全面的例子是lambda函數(shù)中的for循環(huán)盐固。這個(gè)循環(huán)也會(huì)被GCC自動(dòng)矢量化:
// Defining a compute kernel to encapsulate a specific computation
auto kernel_multiply =
[ &cFixedMultiply ] // capture the constant by reference of the scope of the lambda expression
( DataArray const& a, DataArray const& b, DataArray & res ) // take 3 parameters by reference
->void // lambda function returns void
{
// simple loop vectorized
for( unsigned int i = 0; i < a.size(); ++ i)
{
res[i] = a[i] * b[i];
}
};
不要調(diào)用外部函數(shù)
調(diào)用外部函數(shù)荒给,如exp()丈挟,log()等等,會(huì)導(dǎo)致循環(huán)不能被向量化志电。因此曙咽,您必須決定循環(huán)中的數(shù)學(xué)運(yùn)算是否足夠,從而將循環(huán)分解挑辆。這意味著例朱,在第一個(gè)循環(huán)中,計(jì)算調(diào)用exp()時(shí)鱼蝉,需要使用的參數(shù)洒嗤,并將此結(jié)果存儲(chǔ)在臨時(shí)數(shù)組中。GCC會(huì)自動(dòng)矢量化這個(gè)循環(huán)魁亦。第二個(gè)循環(huán)將簡(jiǎn)單地執(zhí)行對(duì)exp()的調(diào)用并存儲(chǔ)結(jié)果渔隶。
如果要調(diào)用的函數(shù)是由您控制的,請(qǐng)盡量嘗試將此函數(shù)指定為C ++ 11 lambda表達(dá)式洁奈∨伤海可以在這里找到該特性的介紹:http://en.wikipedia.org/wiki/Anonymous_function#C.2B.2B
在循環(huán)中使用普通的整數(shù)計(jì)數(shù)器
使用普通的整數(shù)計(jì)數(shù)器來(lái)構(gòu)建for循環(huán),而不是std :: iterator睬魂,因?yàn)檫@些使得GCC難以分析內(nèi)存訪問(wèn)和循環(huán)的屬性终吼,如迭代計(jì)數(shù)。
for (vector::iterator it = y.begin(); it != y.end(); it++)
{
(*it) += 23;
}
變?yōu)椋?/p>
for (unsigned int i = 0; i < y.size(); ++i)
{
y[i] += 23;
}
綜合代碼示例
下面的代碼給出了一些關(guān)于如何用GCC編寫自動(dòng)矢量化C ++代碼的例子氯哮。復(fù)制并粘貼源代碼并使用下面命令進(jìn)行編譯即可:
g++ -Ofast -ftree-vectorizer-verbose=7 -march=native -std=c++11 -o autovect autovect.cpp
請(qǐng)保證使用的gcc版本至少是:GCC 4.7
/*
Compile with ( use at least gcc 4.7 ):
g++ -Ofast -ftree-vectorizer-verbose=7 -march=native -std=c++11 -o autovect autovect.cpp
*/
#include <math.h>
#include <string>
#include <iostream>
#include <array>
#include <vector>
// Sturcture-Of-Array to hold coordinates
struct Vector3
{
std::vector<double> x;
std::vector<double> y;
std::vector<double> z;
// final result of the distance calcualtion
std::vector<double> distance;
void add( double _x, double _y, double _z )
{
x.push_back( _x );
y.push_back( _y );
z.push_back( _z );
distance.push_back( 0.0f );
}
};
int main()
{
// Fixed Size Arrays
typedef std::array<double, 10> DataArray;
DataArray vect_a = { 0,1,2,3,4,5,6,7,8,9 };
DataArray vect_b = {0.5,1,2,3,4,5,6,7,8,9 };
DataArray vect_res_plain = { 0,0,0,0,0,0,0,0,0,0};
DataArray vect_res_lambda = { 0,0,0,0,0,0,0,0,0,0};
constexpr double cFixedMultiply = 23.5f;
// simple loop vectorized
// -- auto-vectorized --
for( unsigned int i = 0; i < vect_a.size(); ++ i)
{
vect_res_plain[i] = vect_a[i] + vect_b[i];
}
// Defining a compute kernel to encapsulate a specific computation
auto kernel_multiply =
[ &cFixedMultiply ] // capture the constant by reference of the scope of the lambda expression
( DataArray const& a, DataArray const& b, DataArray & res ) // take 3 parameters by reference
->void // lambda function returns void
{
// simple loop vectorized
// -- auto-vectorized --
for( unsigned int i = 0; i < a.size(); ++ i)
{
res[i] = a[i] * b[i] * cFixedMultiply;
}
};
// call the lambda function
// this call is autovectorized
kernel_multiply ( vect_a, vect_b, vect_res_lambda );
// This kernel will be called multiple times and performs the quadrature
auto kernel_square =
[] // capture nothing
( double const& a) // take 1 parameter by reference
->double // lambda function returns the square
{
return ( a * a );
};
// create struct and fill with dummy values
Vector3 v3;
for ( unsigned int i = 0; i < 50 ; ++ i)
{
v3.add( i * 1.1, i * 2.2, i* 3.3 );
}
// store the size in a local variable. This is needed to GCG
// can estimate the loop iterations
const unsigned int size = v3.x.size();
// -- auto-vectorized --
for ( unsigned int i = 0; i < size; ++ i)
{
v3.distance[i] = sqrt( kernel_square( v3.x[i] ) + kernel_square( v3.y[i] ) + kernel_square( v3.z[i] )) ;
}
// output the result, so GCC won't optimize the calculations away
std::cout << std::endl << "Computation on std::array" << std::endl;
for( unsigned int i = 0; i < vect_a.size(); ++ i)
{
std::cout << vect_res_plain[i] << std::endl;
std::cout << vect_res_lambda[i] << std::endl;
}
std::cout << std::endl << "Computation on Structure-of-Array with variable sized std::vectors" << std::endl;
for( unsigned int i = 0; i < v3.x.size(); ++ i)
{
std::cout << "sqrt( " << v3.x[i] << "^2 + " << v3.y[i] << "^2 + " << v3.z[i] << "^2 ) = "
<< v3.distance[i] << std::endl;
}
return 0;
}
自動(dòng)矢量化的實(shí)際應(yīng)用
在這里际跪,您可以找到一部分利用GCC編譯器的自動(dòng)矢量化功能的應(yīng)用列表:
The VDT mathematical library
參考: https://twiki.cern.ch/twiki/bin/view/CMSPublic/WorkBookWritingAutovectorizableCode