朱廣林,賴慶寬,何先波,王博生，陳燕生

(西華師范大學(xué)計(jì)算機(jī)學(xué)院，四川南充 637009)

0 引言

為了充分利用處理器的并行潛力，現(xiàn)代CPU大多已提供向量處理單元(Vector Processing Units，VPUs)以允許在單條指令中對(duì)多個(gè)數(shù)據(jù)執(zhí)行操作.GCC、LLVM、ICC和AOCC等主流編譯器中也提供了編譯器的自動(dòng)向量化(Compiler Automatic Vectorization，CAV)支持，它們能夠分析應(yīng)用程序中的循環(huán)，自動(dòng)找到使用SIMD指令的機(jī)會(huì)[1].通過(guò)一個(gè)向量指令操作完成對(duì)多個(gè)數(shù)據(jù)元素的同時(shí)運(yùn)算[2,3]，可以在與標(biāo)量運(yùn)算相同的時(shí)間內(nèi)執(zhí)行更多的操作，是提高程序性能的重要途徑之一.利用SIMD指令最常用的方法是編譯器的自動(dòng)向量化，當(dāng)編譯器不能對(duì)代碼進(jìn)行向量化時(shí)，可嵌入向量化的匯編代碼，或調(diào)用一些高級(jí)的庫(kù)文件，如Boost.SIMD[4]等.

編譯器能否準(zhǔn)確高效地進(jìn)行自動(dòng)向量化對(duì)程序整體的性能至關(guān)重要.編譯器根據(jù)編譯時(shí)得到的有效信息對(duì)程序進(jìn)行向量化評(píng)估，以決定采用何種指令集[5].商業(yè)編譯器AOCC和ICC在O3及相關(guān)優(yōu)化組合下可以有效地挖掘和使用SIMD指令，做規(guī)整的向量化，但GCC編譯器的自動(dòng)向量化優(yōu)化存在一些保守限制，因此編譯器的自動(dòng)向量化技術(shù)仍有重要的研究?jī)r(jià)值.

本文主要對(duì)現(xiàn)代x86多核處理器中， GCC編譯器的數(shù)據(jù)結(jié)構(gòu)布局進(jìn)行優(yōu)化，將代碼熱區(qū)域中進(jìn)行數(shù)據(jù)結(jié)構(gòu)對(duì)齊，亦或是重組，拆分之后的結(jié)構(gòu)體進(jìn)行數(shù)組結(jié)構(gòu)體數(shù)組(AoSoA)的布局轉(zhuǎn)換優(yōu)化，通過(guò)改善內(nèi)存布局方式，提高向量化優(yōu)化能力.通過(guò)分析優(yōu)化前后代碼中向量指令的數(shù)量和功能，最后在AMD平臺(tái)上進(jìn)行了基準(zhǔn)測(cè)試，驗(yàn)證了該方法的有效性，以及具有向量化指令寬度擴(kuò)展能力.

1 研究背景

編譯器的優(yōu)化能力受到諸多因素影響，為使應(yīng)用程序的向量運(yùn)算性能最大化的發(fā)揮出來(lái)，本文基于國(guó)產(chǎn)x86處理器平臺(tái)上的GCC編譯器進(jìn)行性能分析，通過(guò)變換數(shù)據(jù)結(jié)構(gòu)的布局方式，以有效利用全寬度的向量寄存器.

根據(jù)優(yōu)化粒度的不同，自動(dòng)向量化分為循環(huán)向量化(Loop vectorization)和超字級(jí)并行向量化(Superword-Level Parallelism vectorization，SLP).循環(huán)向量化在基于循環(huán)和依賴關(guān)系的理論上使用SIMD指令[6]，它利用粗粒度的并行性，通過(guò)展開(kāi)循環(huán)以減少迭代次數(shù)，同時(shí)在每個(gè)迭代中執(zhí)行更多操作.超字級(jí)并行向量化可利用SIMD基本塊中語(yǔ)句之間的并行性[7,8]，也可用于優(yōu)化多重的嵌套循環(huán)[9].超字級(jí)并行向量化以更精細(xì)的粒度使用，可以在循環(huán)向量化存在限制的情況下加以利用，它將多個(gè)標(biāo)量操作打包在一起來(lái)使用SIMD指令[10].

循環(huán)向量化先對(duì)循環(huán)的最內(nèi)層進(jìn)行分析，以檢查是否存在數(shù)據(jù)依賴和函數(shù)調(diào)用等限制因素，當(dāng)確定可進(jìn)行向量化優(yōu)化之后，變換循環(huán)體結(jié)構(gòu)并生成向量化指令代碼.如圖1所示為循環(huán)向量化示例，圖1(a)的示例程序中，向量化受限于循環(huán)體中存在的循環(huán)依賴關(guān)系和函數(shù)調(diào)用，GCC編譯器需要在-O3及-ffast-math等優(yōu)化組合的情況下才能進(jìn)行循環(huán)向量化.如圖1(b)所示，為了最大限度地進(jìn)行向量化，編譯器需要執(zhí)行循環(huán)分裂(loop fission)轉(zhuǎn)換，將循環(huán)的一部分塑造成可向量化的形式，第一個(gè)循環(huán)經(jīng)過(guò)分裂和展開(kāi)之后可進(jìn)行向量化，如圖1(c)所示.

GCC編譯器中，向量化主要作用于中端GIMPLE trees表示的循環(huán)優(yōu)化上，且大部分向量化優(yōu)化選項(xiàng)已在-O3優(yōu)化中默認(rèn)開(kāi)啟.如圖2所示，當(dāng)源碼經(jīng)過(guò)前端解析進(jìn)入中端時(shí)，生成GIMPLE表示，它是一種與前端語(yǔ)言和目標(biāo)機(jī)器都無(wú)關(guān)的三地址表示形式，引入了臨時(shí)變量來(lái)保存中間值，GCC中眾多的優(yōu)化在GIMPLE中間表示上進(jìn)行[11].

圖1 循環(huán)向量化示例Fig.1 Examples of loop vectorization圖2 GCC編譯器中向量化優(yōu)化位置Fig.2 The vectorization optimization location in the GCC compiler

2 數(shù)據(jù)結(jié)構(gòu)布局優(yōu)化設(shè)計(jì)與實(shí)現(xiàn)

本章節(jié)結(jié)構(gòu)如下：首先簡(jiǎn)要介紹向量化優(yōu)化中指令數(shù)據(jù)類型及其相關(guān)的寄存器內(nèi)存布局；最后詳細(xì)說(shuō)明數(shù)據(jù)結(jié)構(gòu)布局的向量化優(yōu)化方法的設(shè)計(jì)與實(shí)現(xiàn).

2.1 指令集數(shù)據(jù)類型及其內(nèi)存布局介紹

不同的SIMD擴(kuò)展指令集都有其對(duì)應(yīng)的指令集體系結(jié)構(gòu)(Instruction Set Architecture, ISA和向量寄存器寬度[12].如圖3展示了英特爾SSE和AVX指令集中的數(shù)據(jù)類型以及相關(guān)向量寄存器的布局結(jié)構(gòu)，圖3(a)中的數(shù)據(jù)類型，在SSE指令集中，128位寄存器可以表示為四個(gè)32位的元素或者兩個(gè)64位的元素，并且SSE中定義了標(biāo)量和打包兩種類型的操作，標(biāo)量運(yùn)算對(duì)最低位有效數(shù)據(jù)元素進(jìn)行運(yùn)算，打包運(yùn)算可并行計(jì)算所有位元素.在x86處理器上目前支持的最大向量寄存器寬度為512位，在支持多個(gè)向量寄存器的機(jī)器上，位數(shù)較小的寄存器作為較大寄存器的低位，不同大小的寄存器組分別為：ZMM、YMM和XMM[13].如圖3(b)所示，512位的ZMM寄存器低256位是YMM寄存器，而YMM寄存器的低128位與128位XMM寄存器復(fù)用.

圖3 SSE和AVX指令中的數(shù)據(jù)類型和相關(guān)寄存器布局Fig.3 The data types in SSE and AVX instructions and related register layout

C/C++中的基本類型__m512、__m256d、__m128等可與編譯器的內(nèi)部函數(shù)一起使用，以促進(jìn)向量寄存器的每一位元素都能有效利用，減少指令數(shù)量.

2.2數(shù)據(jù)結(jié)構(gòu)布局方法設(shè)計(jì)

數(shù)據(jù)布局是向量化中最重要的因素之一，數(shù)據(jù)根據(jù)組織方式的不同可以分為：結(jié)構(gòu)體數(shù)組(Array of Structures，AoS)、數(shù)組結(jié)構(gòu)體(Structure of Arrays，SoA)或數(shù)組結(jié)構(gòu)體數(shù)組(Array of Structures of Arrays，AoSoA).本文的設(shè)計(jì)方法是通過(guò)將數(shù)據(jù)結(jié)構(gòu)對(duì)齊，亦或是重組(reorder)，拆分(split，peeling)之后的結(jié)構(gòu)體進(jìn)行內(nèi)存布局轉(zhuǎn)換，變換為AoSoA組織方式.

數(shù)據(jù)結(jié)構(gòu)對(duì)齊包含數(shù)據(jù)對(duì)齊、數(shù)據(jù)填充和打包.結(jié)構(gòu)體數(shù)據(jù)對(duì)齊能提高訪存效率，根據(jù)對(duì)齊規(guī)則會(huì)對(duì)結(jié)構(gòu)中未使用的空間進(jìn)行填充，如圖4所示，圖4(a)中的示例代碼，根據(jù)結(jié)構(gòu)體總大小為所有成員中最大對(duì)齊數(shù)的整數(shù)倍的規(guī)則，進(jìn)行對(duì)齊和填充之后如圖4(b)所示，填充后的內(nèi)存布局如圖4(c)所示，而通過(guò)將結(jié)構(gòu)體中數(shù)據(jù)打包，可以減少應(yīng)用程序所需的內(nèi)存空間，如圖4(d)所示，對(duì)結(jié)構(gòu)體進(jìn)行打包之后編譯器便不會(huì)進(jìn)行填充，但某些編譯器可能不允許未對(duì)齊的內(nèi)存訪問(wèn).

AoS、SoA和AoSoA優(yōu)化示例如圖5所示，使用AoS數(shù)據(jù)結(jié)構(gòu)時(shí)，在訪問(wèn)下一組數(shù)據(jù)之前需要先獲取結(jié)構(gòu)體的所有元素，但可能許多元素都未被使用，使用SoA結(jié)構(gòu)時(shí)，結(jié)構(gòu)體的每個(gè)元素分為一個(gè)數(shù)組，具有更好的布局方式.圖5(d)所示為三種結(jié)構(gòu)的內(nèi)存使用布局方式.AoSoA是AoS和SoA兩種布局的一種組合方法，它通過(guò)vpshufb等指令將按AoS組合的數(shù)據(jù)進(jìn)行混洗到適當(dāng)向量寄存器中，以有效利用寄存器寬度，不僅保持了良好的數(shù)據(jù)布局和代碼的直觀性，同時(shí)對(duì)現(xiàn)代處理器的緩存體系也更加友好，使用AoSoA可對(duì)大多數(shù)運(yùn)算進(jìn)行高效地向量化.

圖4 結(jié)構(gòu)體的數(shù)據(jù)結(jié)構(gòu)對(duì)齊及其內(nèi)存布局示意圖Fig.4 Schematic diagram of structure data structure alignment and memory layout圖5 AoS、SoA和AoSoA優(yōu)化示例和內(nèi)存布局Fig.5 AoS, SoA and AoSoA optimized examples and memory layout

在GCC編譯過(guò)程中通過(guò)插樁(profiling)的反饋數(shù)據(jù)收集到熱區(qū)域中的結(jié)構(gòu)體信息，然后在GCC中端GIMPLE IR(Intermediate Representation)上新建優(yōu)化pass，對(duì)熱區(qū)域中的結(jié)構(gòu)體進(jìn)行數(shù)組結(jié)構(gòu)體數(shù)組的布局轉(zhuǎn)換優(yōu)化.對(duì)優(yōu)化前后的匯編碼對(duì)比分析發(fā)現(xiàn)，優(yōu)化后采用了vbroadcast、vpshufb、vpermilpd等數(shù)據(jù)混洗，轉(zhuǎn)置操作指令.

3 實(shí)驗(yàn)設(shè)計(jì)與分析

3.1 實(shí)驗(yàn)平臺(tái)與測(cè)試用例

為了對(duì)本文提出的方法的有效性進(jìn)行評(píng)估，將優(yōu)化方法應(yīng)用到GCC8.2.0編譯器，其中GCC8.2.0版本發(fā)布時(shí)間為2018年7月26日.在AMD平臺(tái)上，對(duì)優(yōu)化前后的編譯器進(jìn)行實(shí)驗(yàn)，可以評(píng)估本文方法的有效性，以及編譯器的向量化能力.

表1列出了實(shí)驗(yàn)中所使用平臺(tái)的基礎(chǔ)架構(gòu)特征以及支持的向量化指令集.表2給出了編譯器所使用的主要優(yōu)化選項(xiàng)組合.

表1 實(shí)驗(yàn)平臺(tái)主要信息Tab.1 Main information of the experimental platform

表2 編譯器信息Tab.2 Compiler information

表1中進(jìn)行實(shí)驗(yàn)的AMD平臺(tái)支持所有Intel SIMD ISA擴(kuò)展，表2中列出的編譯器的peak性能主要優(yōu)化選項(xiàng)組合，常規(guī)優(yōu)化-O3，鏈接時(shí)優(yōu)化-flto和數(shù)學(xué)函數(shù)優(yōu)化等.

本文實(shí)驗(yàn)采用的是國(guó)際標(biāo)準(zhǔn)測(cè)試套件SPEC CPU 2017，其包含43個(gè)基準(zhǔn)測(cè)試用例，涵蓋區(qū)域海洋模擬、天氣預(yù)報(bào)、圖像和視頻壓縮等眾多領(lǐng)域，是一套廣泛用于評(píng)估編譯器性能的測(cè)試集[14-16].采用ref數(shù)據(jù)集，將優(yōu)化前后的編譯器編譯測(cè)試用例得到的ratio值，分別作為baseratio和optimizedratio，根據(jù)公式1計(jì)算出優(yōu)化后的編譯器的性能加速比.

(1)

3.2 實(shí)驗(yàn)結(jié)果與分析

為評(píng)估本文方法的有效性以及不同版本編譯器的向量化能力，在此對(duì)GCC8.2.0編譯器進(jìn)行基準(zhǔn)測(cè)試，并計(jì)算出性能加速比.以ref為輸入數(shù)據(jù)集進(jìn)行編譯器優(yōu)化前后的測(cè)試，根據(jù)公式1對(duì)實(shí)驗(yàn)的ratio值進(jìn)行計(jì)算得到性能加速比.

對(duì)SPEC 2017中浮點(diǎn)測(cè)試集進(jìn)行測(cè)試，得到實(shí)驗(yàn)結(jié)果如圖6所示，GCC8.2.0編譯器在進(jìn)行數(shù)據(jù)結(jié)構(gòu)布局優(yōu)化后625.x264_s、628.pop2_s和638.imagick_s 三個(gè)benchmark分別取得1.04x、1.05x和1.07x的性能加速比，驗(yàn)證了該方法的有效性，并且優(yōu)化后的匯編碼中出現(xiàn)預(yù)期的數(shù)據(jù)轉(zhuǎn)換操作相關(guān)的向量化指令.實(shí)驗(yàn)數(shù)據(jù)表明該方法具有在進(jìn)行向量化指令寬度擴(kuò)展的能力.

圖6 AMD平臺(tái)上優(yōu)化前后的性能加速比Fig.6 Performance speedup before and after optimization on AMD platform

4 結(jié)束語(yǔ)

本文提出的數(shù)據(jù)結(jié)構(gòu)布局優(yōu)化方法對(duì)熱區(qū)域中，進(jìn)行數(shù)據(jù)結(jié)構(gòu)對(duì)齊，亦或是重組，拆分之后的結(jié)構(gòu)體進(jìn)行數(shù)組結(jié)構(gòu)體數(shù)組(AoSoA)的布局轉(zhuǎn)換優(yōu)化，通過(guò)改善內(nèi)存布局方式，提高向量化優(yōu)化能力.通過(guò)在AMD上進(jìn)行的實(shí)驗(yàn)分析，驗(yàn)證了該方法的有效性，以及具有向量化指令寬度擴(kuò)展能力.