王 琦 韓 林 姚金陽 陶小涵

(數(shù)學(xué)工程與先進(jìn)計(jì)算國家重點(diǎn)實(shí)驗(yàn)室 河南 鄭州 450001)

0 引 言

隨著個(gè)人計(jì)算機(jī)的不斷增強(qiáng)，人們對計(jì)算機(jī)的期望也越來越高，這也要求計(jì)算機(jī)的計(jì)算速度越來越快。目前多數(shù)通用處理器上已經(jīng)集成了SIMD(Single Instruction Multiple Data)擴(kuò)展部件[1]。SIMD擴(kuò)展部件一次可以對多個(gè)數(shù)據(jù)進(jìn)行操作，減少指令執(zhí)行次數(shù)，因此其越來越多的應(yīng)用于高性能計(jì)算中[2]，同時(shí)越來越多的研究利用SIMD擴(kuò)展部件對程序進(jìn)行加速[3-4]。為了方便對SIMD擴(kuò)展部件的使用，大部分編譯器也都集成了自動向量化模塊[5-6]。為了實(shí)現(xiàn)更多程序的向量化，出現(xiàn)了很多面向向量化的分析方法[7-9]，這些方法基本原理是依據(jù)數(shù)據(jù)依賴關(guān)系尋找可并行的語句，然后將可并行的語句用向量方式并行執(zhí)行。

為了獲得更高的程序執(zhí)行效率，SIMD擴(kuò)展部件的位寬越來越長，以英特爾處理器的SIMD擴(kuò)展為例，從最初的64位的MMX到128位的SSE，以及256位的AVX。目前英特爾最新的Knights Landing處理器可以支持512位向量指令[10]，向量寄存器的寬度越來越長，這使得應(yīng)用程序執(zhí)行速度越來越快，然而這也使得一次向量執(zhí)行所需要的元素個(gè)數(shù)越來越多。一些程序由于其迭代次數(shù)不足，或者基本塊內(nèi)向量并行的語句不夠多，不足以為向量寄存器提供足夠的并行，因而不能向量化。例如若向量因子(向量計(jì)算中一次操作處理的元素個(gè)數(shù))為4，針對圖1所示循環(huán)，gcc編譯器識別為not enough data-refs in basic block，不能向量化。

圖1 示例程序

而隨著向量寄存器長度的增加，程序會有越來越多的循環(huán)或者基本塊會被識別為數(shù)據(jù)引用不足，因此當(dāng)向量因子較大時(shí)，如何對向量寄存器進(jìn)行部分使用是亟待解決的問題。

對于不充分向量化，目前已經(jīng)有了一定的研究，文獻(xiàn)[11]通過添加冗余的語句，將不充分的向量化構(gòu)造為充分的向量化，達(dá)到程序向量化的目的，但是其不能結(jié)合SLP超字并行算法來實(shí)現(xiàn)基本塊內(nèi)的不充分向量化。文獻(xiàn)[12]利用AVX指令集中的permute指令將有效數(shù)據(jù)填充到冗余數(shù)據(jù)的槽位，以確保計(jì)算時(shí)的數(shù)據(jù)不會出現(xiàn)異常，同時(shí)利用insert和extract指令實(shí)現(xiàn)不充分向量化的存取。但是這種向量存取的方法需要多條指令來實(shí)現(xiàn)，會有額外的開銷，而且在向量計(jì)算中，一個(gè)槽位中的數(shù)據(jù)出現(xiàn)異常不會對向量中的其他數(shù)據(jù)產(chǎn)生影響。所以實(shí)際上不需要數(shù)據(jù)整理指令以使得向量寄存器中的所有數(shù)據(jù)均有效，只需要確保冗余數(shù)據(jù)沒有被寫回到內(nèi)存中即可。文獻(xiàn)[13]利用循環(huán)的向量并行度指導(dǎo)循環(huán)進(jìn)行向量化，而當(dāng)向量并行度低時(shí)，利用提取指令將有效數(shù)據(jù)寫回到內(nèi)存中，實(shí)現(xiàn)不充分的向量化。

上述研究對于不充分的向量化處理有了一定的研究，并且在性能上取得一定的提升，但是仍然存在額外的開銷。隨著向量指令集越來越豐富，實(shí)現(xiàn)不充分向量化的方案越來越多，額外的開銷也會變的越來越少，因此本文針對不充分的SIMD向量化技術(shù)進(jìn)行研究分析，旨在為不同場景下的不充分向量化提供更高效靈活的方案。

具體本文的主要貢獻(xiàn)有：

1) 為向量并行度低的循環(huán)和基本塊提供不充分向量化的實(shí)現(xiàn)方案；

2) 對基于256位AVX指令集的不充分向量化進(jìn)行收益分析。

1 不充分向量化問題描述

1.1 向量寄存器的使用方式

向量寄存器一次可以容納多個(gè)數(shù)據(jù)，現(xiàn)有的編譯器將向量寄存器作為一個(gè)整體使用，一次性從內(nèi)存中讀取多個(gè)數(shù)據(jù)，一條指令對多個(gè)數(shù)據(jù)同時(shí)進(jìn)行計(jì)算，最后一次性的將向量寄存器中的數(shù)據(jù)寫回到內(nèi)存中，而且，在這個(gè)過程中，向量寄存器中的所有的數(shù)據(jù)均為有效的，向量寄存器被當(dāng)成一個(gè)整體來使用。

但是在很多情況下，可以進(jìn)行向量處理的數(shù)據(jù)不足以充滿整個(gè)向量寄存器，而現(xiàn)有的很多編譯器，例如GCC，不能對這一部分進(jìn)行向量化。如果這一部分串行執(zhí)行則會浪費(fèi)其向量化機(jī)會，所以，這里需要對向量寄存器進(jìn)行不充分的使用，即在向量寄存器中，有一部分?jǐn)?shù)據(jù)是冗余數(shù)據(jù)，其余部分是有效數(shù)據(jù)，只針對有效數(shù)據(jù)進(jìn)行計(jì)算，達(dá)到不充分向量化的目的。

向量寄存器的使用方式可以分為如圖2所示的4種：1) 充分使用；2) 不充分使用——有效部分連續(xù)；3) 不連續(xù)使用；4) 不規(guī)則使用。

圖2 向量寄存器使用方式

1.2 不充分向量化適用場景

當(dāng)向量并行度低時(shí)，則需要不充分向量化，這里包括迭代內(nèi)的并行和迭代間的并行，例如圖3所示程序?yàn)镾PEC2006 中435.gromacs的核心循環(huán)，其迭代間存在間接數(shù)組索引以及規(guī)約求和操作，而且迭代間極有可能存在數(shù)據(jù)依賴。所以其迭代間并行難以挖掘，而迭代內(nèi)可以并行執(zhí)行的數(shù)據(jù)個(gè)數(shù)為3，當(dāng)向量寄存器可以處理的元素個(gè)數(shù)大于3時(shí)，則需要不充分向量化。

圖3 示例程序—435.gromacs

當(dāng)數(shù)據(jù)非連續(xù)時(shí)，例如循環(huán)跨步不是1時(shí)，導(dǎo)致數(shù)組訪問非連續(xù)，如圖4所示為FFT(快速傅里葉變換)中復(fù)數(shù)乘法計(jì)算。當(dāng)然，此時(shí)如果可以利用數(shù)據(jù)整理指令，將離散的數(shù)據(jù)組合為一個(gè)向量，或者利用類似gather/scatter指令，以使得計(jì)算時(shí)對向量寄存器充分使用，這樣效果可能會更好。但是一些處理器的向量指令集不支持豐富的數(shù)據(jù)整理指令，例如國產(chǎn)的申威處理器在主核上不支持shuffle指令，所以此時(shí)利用不充分向量化對程序進(jìn)行并行度較低的向量計(jì)算也是比較好的選擇。

圖4 示例程序—復(fù)數(shù)乘法計(jì)算

當(dāng)循環(huán)中存在if條件語句時(shí)，受if條件語句的控制，對數(shù)據(jù)訪問不規(guī)則，一些數(shù)據(jù)不需要參與當(dāng)前計(jì)算。例如圖5所示程序?yàn)镾PEC2006 中456.hmmer的核心循環(huán)，所以這里需要向量寄存器的部分使用，對需要作數(shù)組賦值的部分進(jìn)行不充分的向量化操作。

圖5 示例程序—456.hmmer

2 不充分向量化的實(shí)現(xiàn)

不充分向量化的實(shí)現(xiàn)主要分為：不充分向量化讀、不充分向量化計(jì)算和不充分的向量化寫操作，而不充分向量化的實(shí)現(xiàn)最主要的目的是避免冗余數(shù)據(jù)寫回到內(nèi)存中，確保寫回內(nèi)存的數(shù)據(jù)均為有效數(shù)據(jù)。所以，讀數(shù)據(jù)時(shí)，讀取相應(yīng)向量長度的數(shù)據(jù)，不需要計(jì)算的數(shù)據(jù)則為冗余數(shù)據(jù)，在計(jì)算過程中，冗余數(shù)據(jù)同樣參與計(jì)算，但是將計(jì)算結(jié)果寫回時(shí)，不寫回冗余計(jì)算的結(jié)果，只將有效數(shù)據(jù)寫回到內(nèi)存中即可，這樣就確保了計(jì)算的正確性。因此，如何實(shí)現(xiàn)不充分的向量化寫操作是不充分向量化技術(shù)實(shí)現(xiàn)的關(guān)鍵，圖6展示了不充分向量化寫的預(yù)期功能，將向量寄存器中的部分?jǐn)?shù)據(jù)寫到內(nèi)存中。

圖6 不充分向量化實(shí)現(xiàn)過程

2.1 掩碼指令實(shí)現(xiàn)

一些處理器支持的向量指令集支持掩碼操作，例如：英特爾的AVX、AVX512指令集支持帶掩碼的存取操作，掩碼指令寫操作相對靈活，通過掩碼控制，可以將向量寄存器中的任意數(shù)據(jù)寫回到內(nèi)存中，所以利用掩碼，可以將有效數(shù)據(jù)寫回到內(nèi)存，完成不充分向量讀操作。

如圖7所示，示例程序向量并行度為3，當(dāng)向量寬度為4時(shí)，程序可以利用不充分向量化達(dá)到并行執(zhí)行的目的，利用掩碼指令實(shí)現(xiàn)的具體操作如圖8所示。

圖7 示例程序—不充分向量化實(shí)現(xiàn)

圖8 不充分向量化的掩碼執(zhí)行實(shí)現(xiàn)

ymm0是要寫回到內(nèi)存中的數(shù)據(jù)，ymm1中保存的掩碼。掩碼指令寫操作可以確保冗余數(shù)據(jù)不被寫回到內(nèi)存中去，程序得以正確執(zhí)行，所以這里應(yīng)確保掩碼ymm1的正確性，在掩碼操作中，有效槽位對應(yīng)的掩碼為1，無效槽位對應(yīng)的掩碼為0。當(dāng)循環(huán)迭代內(nèi)，程序的不充分向量化模式一致時(shí)，其利用的掩碼是相同的，這樣只需要在循環(huán)外獲取掩碼向量，如圖8將其賦值給ymm1向量寄存器，此后的掩碼存操作可以直接讀取向量寄存器ymm1中的掩碼，減少循環(huán)迭代內(nèi)的指令條數(shù)，更好地提升程序執(zhí)行的效率。

2.2 選擇指令實(shí)現(xiàn)

一些處理器不支持帶掩碼的向量操作，比如：國產(chǎn)的申威處理器。因此，為了確保程序的正確性，需要將冗余數(shù)據(jù)所在的槽位填充為內(nèi)存中相對應(yīng)的數(shù)據(jù)。這樣在進(jìn)行向量寫操作時(shí)，雖然也對不進(jìn)行計(jì)算的數(shù)據(jù)進(jìn)行了覆蓋，但是覆蓋的值仍為原始數(shù)據(jù)，相當(dāng)于沒有對內(nèi)存中的數(shù)據(jù)進(jìn)行修改。所以問題就在于如何將冗余數(shù)據(jù)所在的槽位填充為內(nèi)存中相對應(yīng)的數(shù)據(jù)，目前大多數(shù)的處理器均支持向量的選擇指令，利用選擇指令對兩個(gè)向量中的元素進(jìn)行選擇，將向量中的冗余數(shù)據(jù)替換為內(nèi)存中的數(shù)據(jù)，具體實(shí)現(xiàn)如圖9所示。

圖9 不充分向量化的選擇指令實(shí)現(xiàn)

圖中：① 將原始數(shù)據(jù)利用向量的load指令加載到向量寄存器中；② 根據(jù)掩碼對兩個(gè)向量進(jìn)行數(shù)據(jù)的選擇；③ 將選擇后的結(jié)果寫回到內(nèi)存中。當(dāng)利用選擇指令實(shí)現(xiàn)不充分向量化向量加載指令、向量選擇指令以及向量存儲指令時(shí)，這些額外的操作會使得不充分向量化的收益變小，甚至出現(xiàn)負(fù)加速。所以這里需要對程序進(jìn)行收益分析，如果分析結(jié)果為不充分向量化會得到性能收益，則對循環(huán)進(jìn)行不充分向量化變換。

3 不充分向量化收益分析

英特爾的AVX向量化指令集支持向量的掩碼指令以及向量選擇指令，所以可以分別用兩種方式實(shí)現(xiàn)不充分的向量化。但是兩種實(shí)現(xiàn)方式的收益是不同的，所以這里對圖10所示程序用掩碼指令以及選擇指令分別進(jìn)行測試，測試結(jié)果如表1所示。

圖10 示例程序—不同實(shí)現(xiàn)方式收益分析

掩碼實(shí)現(xiàn)選擇指令實(shí)現(xiàn)程序(a)1.501.48程序(b)1.291.27

兩種實(shí)現(xiàn)方式均有加速效果。利用掩碼指令實(shí)現(xiàn)，其實(shí)現(xiàn)方式簡單，可以很靈活地實(shí)現(xiàn)不充分的向量化，并且掩碼訪存指令開銷比較小，一般會有比較好的加速效果。而利用選擇指令實(shí)現(xiàn)不充分向量化需要對向量元素進(jìn)行選擇再寫回到內(nèi)存中，存在額外的開銷，所以加速比略低于掩碼實(shí)現(xiàn)，然而當(dāng)處理器不支持掩碼指令時(shí)，利用選擇指令實(shí)現(xiàn)不充分向量化一定程度上也可以提升程序執(zhí)行的效率。

示例程序比較簡單，當(dāng)不充分向量化的訪存變得復(fù)雜時(shí)，兩種實(shí)現(xiàn)方式的實(shí)現(xiàn)效率是不確定的，所以在生成相應(yīng)的指令時(shí)，應(yīng)利用代價(jià)模型計(jì)算向量化的收益以使程序的加速效果最優(yōu)。

4 測試以及分析

4.1 實(shí)驗(yàn)測試環(huán)境

本文使用的硬件環(huán)境為處理器：Intel Xeon CPU E5-2620?；绢l率：1.20 GHz；最大睿頻頻率：2.10 GHz；L1 cache 64 KB；L2 cache 256 KB；指令集擴(kuò)展：Intel AVX；內(nèi)存：64 GB。實(shí)驗(yàn)相關(guān)軟件環(huán)境如表2所示。

表2 實(shí)驗(yàn)相關(guān)軟件環(huán)境

4.2 非連續(xù)數(shù)據(jù)訪問的向量化測試

為測試本文提出的不充分向量化方法的有效性，選擇spec2006程序中的435.gromacs、456.hmmer、482.sphinx3程序，以及科學(xué)計(jì)算程序高精度有限體積方法CFV(Compact high order finite volume method on unstructured grids)的核心循環(huán)進(jìn)行測試。這些程序的核心計(jì)算中存在循環(huán)迭代次數(shù)低或者基本塊內(nèi)同構(gòu)計(jì)算語句條數(shù)低的情況，比較適合做不充分的向量化，分別對這些程序進(jìn)行測試，并比較串行執(zhí)行、不充分向量化優(yōu)化前，以及不充分向量化優(yōu)化后的執(zhí)行時(shí)間，并做加速比對比，結(jié)果如圖11所示。

圖11 科學(xué)計(jì)算程序不充分向量化加速比

通過測試結(jié)果可以發(fā)現(xiàn)，本文提出的不充分向量化方法可以有效地提升程序執(zhí)行效率，但是456.hmmer加速效果不明顯。因?yàn)槠洳怀浞窒蛄炕饕怯蒳f條件語句引起的，而gcc在針對向量化進(jìn)行循環(huán)分析時(shí)，如果循環(huán)內(nèi)存在條件語句，則會使循環(huán)內(nèi)的基本塊個(gè)數(shù)變多，這時(shí)gcc不會對其向量化，導(dǎo)致其加速效果不明顯，所以下一步將針對由if條件語句引起的不充分向量化進(jìn)行深入研究。

5 結(jié) 語

隨著人們對計(jì)算機(jī)期望的增高，要求計(jì)算機(jī)的計(jì)算速度越來越快，但是目前一些自動向量化算法沒有很好地解決不充分向量化的問題，而且隨著向量寄存器的位寬越來越大，在向量化方面需要針對不充分向量化進(jìn)行更深入的研究，以提高程序的計(jì)算速度?；诖?，本文對不充分向量化進(jìn)行研究，提出不充分向量化的兩種實(shí)現(xiàn)方法，并對這兩種方法進(jìn)行簡單的收益分析，最后選擇科學(xué)計(jì)算程序以及spec2006中的程序來驗(yàn)證本文提出方法的有效性。

但是不同的處理器支持的向量指令不同，而且對于不同的實(shí)現(xiàn)方式，其向量指令的代價(jià)也是不同的，并且不充分向量化中的訪存問題對程序執(zhí)行效率也是比較大的，所以采用何種方式實(shí)現(xiàn)不充分向量化都值得進(jìn)一步研究。本文對其代價(jià)進(jìn)行簡單的分析，后續(xù)將設(shè)計(jì)更精確的代價(jià)模型，以使得程序執(zhí)行效率達(dá)到最優(yōu)。此外，利用向量的數(shù)據(jù)重組可以將不充分向量化變換為充分的向量化，提升程序的并行度。然而這會帶來很復(fù)雜的訪存問題并且數(shù)據(jù)重組的實(shí)現(xiàn)方案也是難以確定的，不過當(dāng)計(jì)算任務(wù)比較大時(shí)，這種實(shí)現(xiàn)方案雖然復(fù)雜，但也會得到比較好的加速效果，值得進(jìn)一步研究。最后，由if條件語句引起的不充分向量化在向量化分析時(shí)，存在分支控制，使得循環(huán)內(nèi)基本塊個(gè)數(shù)變多，gcc則不會對其進(jìn)行向量化，所以程序還存在進(jìn)一步提升性能的潛能，下一步將針對if條件語句下的不充分向量化進(jìn)行研究。