自編教材分享：第七章—數(shù)據(jù)級(jí)并行（三）
向量程序優(yōu)化
本節(jié)介紹在已經(jīng)改寫的向量化程序上如何更進(jìn)一步的提升性能，主要包含以下六點(diǎn)內(nèi)容：
不對(duì)齊訪存；
不連續(xù)訪存；
向量重用；
向量運(yùn)算融合；
循環(huán)完全展開；
全局不變量合并；
不對(duì)齊訪存
訪存對(duì)齊性是影響向量程序性能的重要因素，內(nèi)存對(duì)齊訪問是指內(nèi)存地址A 對(duì)n求余等于0，其中n為訪存數(shù)據(jù)的字節(jié)數(shù)。如果向量訪存是不對(duì)齊的，與對(duì)齊的向量訪存相比，需要額外的開銷才能實(shí)現(xiàn)數(shù)據(jù)的存儲(chǔ)操作。在編寫向量程序時(shí)，應(yīng)盡量使用對(duì)齊的訪存指令。然而現(xiàn)實(shí)程序中更多的是不對(duì)齊訪存，優(yōu)化人員可以借助程序變換的方法，將不對(duì)齊訪存調(diào)整為對(duì)齊以提升向量程序的性能。例如使用循環(huán)剝離方法可以將循環(huán)迭代中非對(duì)齊的部分從循環(huán)中剝離出來，使主體循環(huán)變?yōu)閮?nèi)存訪問對(duì)齊的循環(huán)。編譯器默認(rèn)從A[0]開始進(jìn)行對(duì)齊訪問，而主體循環(huán)從A[1]開始訪問，因此如果不進(jìn)行循環(huán)剝離，在進(jìn)行向量化時(shí)對(duì)數(shù)組A和B的訪存是不對(duì)齊的。利用循環(huán)剝離將循環(huán)的前3次迭代剝離出去，從循環(huán)的第4次迭代開始轉(zhuǎn)為向量執(zhí)行，那么主體循環(huán)中的向量操作均可以轉(zhuǎn)為對(duì)齊內(nèi)存訪問。
源代碼：
當(dāng)多維數(shù)組的最低維長度不是向量長度的整數(shù)倍時(shí)，難以判斷訪存的對(duì)齊性，此時(shí)一般會(huì)使用非對(duì)齊訪問指令保證程序的正確性。這個(gè)問題可以使用數(shù)組填充來解決，即當(dāng)數(shù)組最低維長度不是向量化因子的整數(shù)倍時(shí)，通過增加數(shù)組最低維的長度，使得向量化的時(shí)候能夠統(tǒng)一按照對(duì)齊的方法進(jìn)行向量化裝載或者存儲(chǔ)。
源代碼：
數(shù)組填充后：
現(xiàn)實(shí)程序中數(shù)據(jù)訪存不對(duì)齊的情況更多，如果程序?qū)嶋H是不對(duì)齊訪存，而寫為對(duì)齊訪存，那么就會(huì)造成程序運(yùn)行錯(cuò)誤。因此，如果優(yōu)化人員不能確定訪存的對(duì)齊性時(shí)，需要使用不對(duì)齊指令進(jìn)行訪存，以保證程序的正確運(yùn)行。
源代碼：
不對(duì)齊指令改寫：
不連續(xù)訪存
連續(xù)的向量訪存不僅可以提高向量訪存指令的效率，還可以提高向量寄存器中有效數(shù)據(jù)的比率。但多數(shù)計(jì)算都不是理想的連續(xù)訪存情況，本節(jié)將介紹如何在不改變引用順序和數(shù)據(jù)布局的情況下，利用處理器提供的向量指令實(shí)現(xiàn)不連續(xù)訪存程序的向量化。
源代碼：
不連續(xù)訪存改寫后的代碼：
然而并不是所有的平臺(tái)都支持聚集和分散指令，對(duì)于一些不連續(xù)訪存、但是訪問內(nèi)存有規(guī)律的程序可以利用向量重組實(shí)現(xiàn)不連續(xù)訪存，向量重組是指當(dāng)目標(biāo)向量中的所有元素不在同一個(gè)向量中時(shí)，通過多個(gè)向量之間的重新組合得到目標(biāo)向量。
對(duì)于上一節(jié)不對(duì)齊訪問的優(yōu)化示例，并不是所有的平臺(tái)都支持不對(duì)齊的訪存指令，當(dāng)平臺(tái)不支持不對(duì)齊訪存指令時(shí)，可以借助于數(shù)據(jù)重組實(shí)現(xiàn)不對(duì)齊訪存。如通過兩次對(duì)齊訪存，然后將數(shù)據(jù)移位或者重組。
使用Intel處理器的SIMD擴(kuò)展指令集，進(jìn)一步如何說明利用向量重組實(shí)現(xiàn)不連續(xù)訪存程序的向量化?？梢酝ㄟ^混洗指令simd_vshff將數(shù)據(jù)重組。假設(shè)VA={a0，a1，a2，a3}；VB={b0，b1，b2，b3}表示復(fù)數(shù)取出向量化數(shù)據(jù)，a0、a2為實(shí)部，a1、a3為虛部，VB同樣如此，當(dāng)掩碼為(2,0,2,0)時(shí)，可以得到VC={a0，a2，b0，b2}，當(dāng)掩碼為(3,1,3,1)時(shí)，可以得到VC={a1，a3，b1，b3}，VC中前兩位數(shù)據(jù)只能來源于VA，后兩位數(shù)據(jù)只能來源于VB。
源代碼：
混洗指令改寫后的代碼：
混洗指令不僅可以用作數(shù)據(jù)整理，當(dāng)掩碼為零的時(shí)候也可以用作數(shù)據(jù)廣播填充。如下：
通過以上使用混洗指令，實(shí)現(xiàn)了float類型的數(shù)據(jù)轉(zhuǎn)換成四個(gè)槽位的相同數(shù)據(jù)，作用類似于向量取值指令。在編寫程序時(shí)，可以根據(jù)實(shí)際情況使用不同的方式進(jìn)行數(shù)據(jù)填充轉(zhuǎn)換。
向量重用
不對(duì)齊訪存代碼可以利用向量重用進(jìn)一步優(yōu)化。以下面代碼為例，在使用對(duì)齊指令對(duì)C賦值時(shí)，循環(huán)體內(nèi)對(duì)于不對(duì)齊數(shù)組的向量訪存需要兩條對(duì)齊的向量訪存和一條拼接指令，可以將其中一次訪存指令重用。下面代碼中用到了向量的局部重用。在拼成V1向量時(shí)使用了va1寄存器中的后2個(gè)值，以及va2中的前2個(gè)值，在下一次迭代中需要使用到本次迭代中va2中的后兩個(gè)值，因此對(duì)于下次循環(huán)迭代來說，直接將本次va2中的值賦于下次迭代計(jì)算的va1可省去一次訪存操作。
源代碼：
使用對(duì)齊指令改寫后的代碼：
向量寄存器的重用可以減少或者去除訪存的需求。向量寄存器含有多個(gè)數(shù)據(jù)項(xiàng)，因此向量寄存器的重用包括全部數(shù)據(jù)項(xiàng)的重用和部分?jǐn)?shù)據(jù)項(xiàng)的重用，向量寄存器的完全重用是最理想的情況，將避免后續(xù)所有的向量訪存，如下：
源代碼：
使用向量指令改寫后的代碼：
向量重用后：
向量運(yùn)算融合
向量運(yùn)算融合就是將多條向量運(yùn)算指令合并為一條向量運(yùn)算指令，以提高向量程序的執(zhí)行性能?？梢詫⒓臃ㄖ噶詈统朔ㄖ噶钊诤蠟橄蛄砍思又噶?，一般情況下乘加指令和乘法的節(jié)拍數(shù)一致，假設(shè)乘法指令的指令周期為6，加法指令的指令周期為4，那么向量運(yùn)算合并后提升了(6+4)/6=1.67倍。不是所有的向量運(yùn)算指令都可以合并，它需要復(fù)合向量運(yùn)算指令的支持，常見的復(fù)合向量運(yùn)算指令包括向量乘加、向量負(fù)乘加、向量乘減、向量負(fù)乘減等。
源代碼：
使用向量指令改寫后的代碼：
乘加指令改寫后的代碼：
循環(huán)完全展開
循環(huán)展開不僅可以提高程序的指令級(jí)并行還可以提高寄存器重用，優(yōu)化人員可以在循環(huán)被向量化后繼續(xù)對(duì)循環(huán)進(jìn)行展開，相當(dāng)于在發(fā)掘完程序數(shù)據(jù)級(jí)并行的基礎(chǔ)上，進(jìn)一步發(fā)掘程序的指令級(jí)并行，同時(shí)提升向量寄存器的重用。
假設(shè)使用的向量寄存器長度為128位，一次能夠處理4個(gè)float數(shù)據(jù)，向量化后原來的循環(huán)僅需要兩次迭代，因此優(yōu)化人員在展開時(shí)可以將循環(huán)完全展開，去掉循環(huán)控制結(jié)構(gòu)，如下：
源代碼:
循環(huán)完全展開:
全局不變量合并
循環(huán)不變量是指該變量的值在循環(huán)內(nèi)不發(fā)生變化。向量化的過程中會(huì)引入很多向量類型的循環(huán)不變量，如果未將向量類型的循環(huán)不變量移到循環(huán)外，將影響程序的向量化性能。循環(huán)內(nèi)含有循環(huán)不變量C，向量化的過程中需要將C轉(zhuǎn)為向量類型，這個(gè)過程一般利用向量設(shè)置指令。
源代碼：
不變量外提后的代碼：
如果其它循環(huán)在向量化過程中也產(chǎn)生了同樣的向量常數(shù)，可以在過程內(nèi)甚至程序內(nèi)進(jìn)行更大范圍的常數(shù)合并。
向量改寫后的代碼：
不變量外提的代碼：
