王 琦 韓 林 姚金陽 陶小涵

(數(shù)學工程與先進計算國家重點實驗室 河南 鄭州 450001)

0 引 言

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

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

圖1 示例程序

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

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

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

具體本文的主要貢獻有：

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

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

1 不充分向量化問題描述

1.1 向量寄存器的使用方式

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

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

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

圖2 向量寄存器使用方式

1.2 不充分向量化適用場景

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

圖3 示例程序—435.gromacs

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

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

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

圖5 示例程序—456.hmmer

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

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

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

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

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

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

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

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

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

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

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

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

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

3 不充分向量化收益分析

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

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

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

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

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

4 測試以及分析

4.1 實驗測試環(huán)境

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

表2 實驗相關軟件環(huán)境

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

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

圖11 科學計算程序不充分向量化加速比

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

5 結(jié) 語

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

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