不充分SIMD向量化技術研究

王 琦 韓 林 姚金陽 陶小涵

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

0 引 言

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

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

圖1 示例程序

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

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

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

具體本文的主要貢獻有：

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

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

1 不充分向量化問題描述

1.1 向量寄存器的使用方式

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

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

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

圖2 向量寄存器使用方式

1.2 不充分向量化適用場景

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

圖3 示例程序—435.gromacs

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

圖4 示例程序—復數乘法計算

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

圖5 示例程序—456.hmmer

2 不充分向量化的實現

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

圖6 不充分向量化實現過程

2.1 掩碼指令實現

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

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

圖7 示例程序—不充分向量化實現

圖8 不充分向量化的掩碼執行實現

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

2.2 選擇指令實現

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

圖9 不充分向量化的選擇指令實現

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

3 不充分向量化收益分析

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

圖10 示例程序—不同實現方式收益分析

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

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

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

4 測試以及分析

4.1 實驗測試環境

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

表2 實驗相關軟件環境

4.2 非連續數據訪問的向量化測試

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

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

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

5 結 語

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

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