GCC非滿載SLP向量化①

劉浩浩, 韓 林, 崔平非

(中原工學院 前沿信息技術研究院, 鄭州 450007)

SIMD擴展[1]作為一種重要的并行加速部件已經被包括數字信號處理器, 游戲機, 通用處理器以及超級計算機在內的大多數現代計算設備所采用. SIMD擴展指令集允許將多個數據元素上的同構標量操作轉換為對應數據元素合集上的向量操作. 這種并行計算方式極大提高了數據吞吐量, 被廣泛的應用于數字信號處理、多媒體應用、科學計算等多個領域. 隨著SIMD部件的發展, SIMD擴展的向量長度不斷增加. 以intel x86處理器SIMD擴展為例, 從MMX開始, 歷經SSE,SSE2, SSE3, SSE4, AVX, AVX2, AVX512, 向量長度由最初的64位增加至512位[2-8]. 國產處理器的Matrix向量指令集達到了1 024位[9]. ARM自ARMv6-A開始支持SIMD, 最初的向量寬度僅為32位, 可同時計算2個16位或4個8位操作數. ARMv7-A和ARMv8-A的向量長度分別是64位和128位. 現在可伸縮向量擴展(scalable vector extension, SVE)最長可支持2 048位向量長度[10]. 向量長度的增加提高了SIMD擴展部件的并行處理能力, 但同時也增加了組成向量發掘數據級并行的難度. 對于現有的自動向量化編譯器,如果在分析階段不能從串行代碼中發掘出足夠的數據級并行性以完全填充向量寄存器, 則不會進入相應的向量代碼變換階段, 從而無法向量化. 因此, 在向量部件長度較大時, 如何實現并行性不足程序的向量化是亟待解決的問題.

目前已經出現了一些針對上述問題的研究: 結合向量長度不可知(vector length agnostic, VLA)編程模型[11], ARM SVE允許向量程序在任一向量長度的SVE實現上運行, 文獻[12]研究了面向ARM SVE的快速傅里葉變換(FFT)算法的向量化實現. 通過增強向量指令集的功能充分發揮較長向量長度的優勢, 文獻[13]提出了通道級并行性(lane level parallelism, LLP)的概念, 研究了點積運算向量化在AVX-512 VNNI指令集上的高效實現.

通過構造冗余數據模擬向量寄存器的滿載使用可以對并行性不足的程序進行向量化. 文獻[14]介紹了一種對3路標量操作的4通道向量化方法PAVER(partial vectorizer), 并在LLVM中予以實現. 文獻[15]對向量寄存器的非滿載使用方式進行了研究, 指出可以使用常規向量存儲與數據重組相結合的方式實現非滿載的向量存儲操作. 提出了一種面向對齊剝離的循環向量化框架, 使用非滿載的向量化方法對剝離產生的頭、尾循環進行向量化. 文獻[16]給出向量并行度的概念及其計算方法. 使用向量并行度作為指導, 為具有不同并行特征的循環選擇合適的向量化方法. 文獻[17]指出在使用掩碼指令對并行性不足的程序進行向量化時,可以考慮對掩碼加載操作進行外提以減少向量化開銷.

GCC (GNU compiler collection)是GUN下的編譯器合集. GCC實現了兩種形式的向量化器, 即循環向量化器(loop vectorizer)和基本塊向量化器(basic block vectorizer), 它們分別具有獨立的入口[18]. 基本塊向量化器使用SLP方法發掘直線型代碼中的超字級并行性[19].本文介紹了一種面向基本塊的非滿載向量化方法ISLP(insufficient SLP), 旨在完成超字級并行性不足程序的向量化. 在深入分析了GCC 7.1.0的SLP向量化框架后, 詳細探討了ISLP在GCC中的實現, 包括非滿載SLP計算樹的構建, 基于數據重組策略的代碼生成和用于收益評估的代價模型. 最后在標準測試集上對擴展后的SLP框架進行了評估. 本文的主要貢獻包括:

(1) 介紹了一種面向基本塊的非滿載向量化方法ISLP.

(2) 闡述了ISLP在GCC中的設計與實現.

本文的章節安排如下. 第1節介紹非滿載SLP向量化的概念; 第2節對GCC 7.1.0的基本塊向量化器進行分析; 第3節從并行性檢測, 代碼生成, 代價模型3個方面描述對非滿載SLP向量化的支持.

1 非滿載SLP向量化

向量化將多個數據元素上相互獨立的同構標量操作轉換為對應數據元素合集上的向量操作, 從而實現對多個數據元素的并行處理. 典型編譯器如GCC、LLVM、ICC, 都實現了自動向量化功能以完成從標量程序到向量程序的自動變換. 目前的自動向量化方法僅支持向量寄存器的滿載使用. 滿載使用是指在向量操作中向量寄存器中的每個數據都是有效的, 從向量裝載到向量計算, 再到向量存儲, 一系列的操作都要保證寄存器中每個數據的有效性. 向量寄存器的滿載使用方式要求自動向量化方法能夠從程序中發掘出足夠的數據級并行, 以完全填充向量寄存器. 當程序中的數據級并行性不足時, 由于無法完全填充向量寄存器, 現有的自動向量化方法無能為力, 為此提出了基于向量寄存器非滿載使用的向量化方法. 在非滿載的向量化框架下, 向量寄存器處于一種非滿載的狀態, 即在向量寄存器中只有部分槽位存放著原標量程序所定義的有效數據,其余槽位是無效的冗余數據.

SLP方法用于發掘直線型代碼中的超字級并行性,超字級并行性的檢測通過檢索基本塊中的同構語句來完成. SLP方法將同一基本塊內的VF條可并行執行的同構語句進行打包并替換為相應的向量語句. VF稱之為向量化因子(vector factor), 表示處理器的向量部件在一次向量操作中所能并行處理的數據元素的個數.當同構語句數目小于VF時, 由于可并行處理的數據不足以完全填充向量寄存器, SLP方法拒絕執行向量化.此外, 由于循環展開可以將向量并行性轉換為超字級并行性[19], 一些經過展開的循環結構也可以使用SLP方法進行向量化.

非滿載SLP方法用于完成超字級并行性不足程序的向量化. 在超字級并行性不足的情況下, 基本塊內的可并行同構語句數目小于VF, 待處理的數據元素無法完全填充向量寄存器, 需要使用某種方法構造冗余數據對向量寄存器中的剩余槽位進行填充. 在向量加載階段, 有效數據和無效數據一起從內存被加載至向量寄存器. 無效數據和有效數據一起參與計算. 在寫回內存時, 有效數據被存儲到相應的內存位置, 而無效數據則不會被存儲. 非滿載SLP向量化維持程序在向量執行后的計算狀態的正確性.

2 GCC中的SLP向量化

非滿載SLP向量化是基于GCC開源編譯器實現的, 本節概述GCC中的SLP向量化框架. 清單1展示了SLP向量化的流程, vect_slp_analyze_bb_1完成對基本塊內超字級并行性的分析, vect_schedule_slp負責向量代碼的生成.

向量化器首先完成基本塊內數據引用的收集. 借助于標量演化分析器, vect_analyze_data_refs為每一個數據引用構建訪問函數. 訪問函數將被用于依賴分析、訪存模式和對齊分析.

清單1. SLP框架vect_slp_analyze_bb_1 vect_analyze_data_refs vect_analyze_data_ref_accesses vect_analyze_slp vect_slp_analyze_and_verify_instance_alignment vect_slp_analyze_instance_dependence vect_slp_analyze_operations vect_bb_vectorization_profitable_p vect_schedule_slp vect_schedule_slp_instance vect_schedule_slp_instance vect_transform_stmt

vect_analyze_data_ref_accesses負責數據引用的訪存模式分析, 交錯鏈(interleaving chains)和組訪問(group access)的識別與建立. 交錯鏈由基址具有線性關系、跨幅相同、數據類型相同的數據引用所組成,根據數據引用的讀寫類型又可分為交錯加載(interleaving load)和交錯存儲(interleaving store). 特別的,當數據引用的訪存模式為非連續訪問且基址相鄰時,這些互相獨立的內存訪問構成了一種特殊的訪存模式,稱之為組訪問, 對應的交錯鏈稱為組加載(group load)或組存儲(group store). 組訪問實際上是對一塊連續內存地址空間的訪問. 每一個group store都將作為一個獨立的SLP種子參與后續超字級并行性的檢測.

vect_analyze_slp檢測基本塊內的超字級并行性并建立SLP實例(SLP instance). SLP實例被定義為一顆SLP計算樹(SLP computing tree), 樹的每一個節點都包含一組同構的標量語句, 根節點為group store, 葉子節點為加載類型的同構語句, 父子節點通過操作數之間的定義使用鏈進行關聯. 所謂同構性指的是節點內的其他語句同構于第一條語句, 即它們具有相同的操作類型和操作數, 并且保持相同的操作順序.

SLP計算樹的構建主要包括同構語句的檢索和打包. 從group store開始, 根據定義使用鏈遞歸地檢索同構語句. 每獲得一組標量語句, 首先檢查數據引用類型和標量語句的同構性, 更新最小數據類型信息max_nunits, max_nunits表示SLP計算樹中最小數據類型對應的向量化因子. 不同構的標量語句無法進行打包, 當遇到一組不同構的標量語句時停止搜索并返回. 數據類型的檢測包括: (1)檢測三地址碼中的最小數據類型,最小數據類型將用于計算展開因子; (2)檢查最小數據類型對應的向量類型是否被目標機支持, 不被支持的數據類型無法向量化; (3)檢查最小數據類型下的向量寄存器是否滿載, 若同構語句的數目小于向量化因子,無法并行執行.

同構性和數據類型檢測通過后, 嘗試對標量語句進行打包. 首先考慮同構語句是否為加載類型, 加載類型的同構語句被視為SLP計算樹的葉子節點, 打包后立即返回. 對非加載類型的同構語句進行打包前, 要首先遍歷它的孩子節點, 對它的孩子節點完成打包. 這是因為父節點的操作數依賴于孩子節點. 當所有的孩子節點打包完成后, 返回至父節點進行打包. 根節點的group store打包后, 一棵完整的SLP計算樹就被建立起來.

遞歸過程結束后對SLP計算樹進行初步的驗證,主要包括: (1)是否需要循環展開, 在循環級和基本塊級相結合的向量化框架下, 可以通過循環展開同時發掘循環迭代間的向量并行性和迭代內的超字級并行性;(2)加載節點數據重組(load permutaion)的合法性檢查, 地址連續的加載操作可以天然的組成向量加載, 而不連續的加載操作, 通過額外的數據重組也有機會得以向量化. 展開因子的計算公式為:

其中, max_nunits表示SLP計算樹中最小數據類型對應的向量化因子, group_size為SLP計算樹節點的同構語句數目. 對于基本塊向量化, 這表明SLP方法希望并行執行的同構語句數目group_size是最大向量化因子max_nunits的整數倍, 這樣SLP向量化總是合法的.此外這也表明, 對于循環向量化, 向量化器以最小數據類型為基準討論可能存在的循環展開, 以完全填充向量寄存器. 在基本塊向量化中, 若UF不為1, 即group_size不是max_nunits的整數倍, 并且存在著max_nunits大于group_size的節點時, SLP向量化是無論如何不能被完成的, 因為不可能展開直線型代碼來獲得更多的數據級并行. 而當max_nunits小于group_size時, 向量化器從原始同構語句組中分裂出一個大小為group_size-group_size%max_nunits的同構語句組, 和一個數目不足max_nunits的同構語句組, 前者可以直接將其向量化, 后者則無法向量化. 這是非滿載SLP向量化的一個重要檢測點, 將在下一節中討論. 展開因子分析完成后, 向量化器對需要進行數據重組的加載節點進行分析、驗證, 以確認數據重組操作可以被完成.

vect_slp_analyze_instance_dependence對基本塊內的數據引用進行依賴分析. 通過判斷SLP計算樹執行路徑上的數據依賴, 決定是否真的可以將分布在基本塊內不同位置的標量語句進行重排序以完成打包.vect_slp_analyze_and_verify_instance_alignment對訪存節點中數據引用的對齊情況進行分析. 不支持的對齊類型無法進行向量化. 不對齊訪存較對齊訪存的代價更高, 在之后的代價模型中對齊信息將用于收益分析.vect_slp_analyze_operations分析基本塊中所有SLP計算樹的操作類型. 對于每一個SLP計算樹, 沿著定義使用關系從葉子節點到根節點, 遞歸的分析節點的向量操作是否被目標機所支持, 對于目標機所不支持的樹節點進行移除.

vect_bb_vectorization_profitable_p完成對基本塊向量化的收益分析. 代價模型對基本塊中所有SLP計算樹的收益進行累加, 作為基本塊向量化的收益. 當收益大于零時, 所有的SLP計算樹都將被向量化; 否則任何SLP計算樹都不會被向量化. SLP計算樹的收益被定義為樹中每個節點的收益之和, 每個節點的收益等于對應的標量語句代價和向量語句代價的差值.

分析和決策階段通過后, 進入向量代碼生成階段.向量化器依次對基本塊內的SLP計算樹進行調度. 每調度一個SLP計算樹, 從葉子節點到根節點遞歸地調用vect_transform_stmt為每個節點生成向量代碼.

3 ISLP實現

3.1 分析

分析階段的目標是構建可以安全應用非滿載SLP向量化的SLP計算樹. 在當前的實現中, 非滿載SLP向量化對應一棵不存在類型轉換操作的非滿載SLP計算樹. 為了對非滿載SLP向量化有更嚴格的描述, 首先介紹一些相關概念, 隨后擴充SLP分析框架以支持非滿載SLP向量化.

定義1. 一個SLP計算樹中的節點稱為是非滿載的, 如果有:

group_size＜VF

其中, group_size是節點中同構語句的數目, VF表示向量化因子, 即可并行執行的同構語句數.

定義2. 一個SLP計算樹稱為是非滿載的當且僅當樹中的全部節點都是非滿載的.

適用于非滿載SLP向量化的SLP計算樹的構建主要包括3個部分: (1)構建非滿載SLP計算樹; (2)檢查類型轉換操作; (3)檢查根節點的數據重組是否被目標機支持.

非滿載SLP計算樹的構建過程與與常規SLP計算樹基本相同. 由定義2可知, 非滿載SLP計算樹要求所有的樹節點都是非滿載的, 因此只要在同構語句檢測階段認為VF大于group_size的同構語句組是合法的, 那么在一個非滿載SLP種子的基礎上, 根據定義使用鏈遞歸的進行擴展, 一個非滿載SLP計算樹就可以被建立起來.

在當前的實現中, 非滿載的類型轉換向量化是不被支持的. 類型提升需要對向量進行拆包擴展, 而類型下降則需要壓縮合并, 這些在非滿載SLP向量化中是過于復雜的. 類型轉換操作可能發生某一個節點, 也可能發生在多個節點. 可能是單一類型轉換, 也可能多種類型轉換同時存在. 但無論發生何種類型轉操作, SLP計算樹中的數據類型一定不唯一. 由于在當前的SLP框架中有關于最小數據類型信息max_nunits的檢測,因此再添加對最大數據類型信息mini_nunits的檢測即可, mini_munits表示SLP計算樹中最大數據類型對應的向量化因子. 在同構語句檢測階段, 檢查并記錄三地址碼中操作數的最大數據類型信息mini_nunits, 該功能由vect_get_biggist_scalar_type完成. SLP計算樹建立后, 如果UF不為1且max_nunits大于group_size,這表明SLP計算樹中存在著非滿載節點, 如果同時有max_nunits等于mini_nunits, 即所有節點的數據類型都對齊到max_nunits且是一致非滿載的, 則說明該SLP計算樹是非滿載.

下面對非滿載SLP計算樹的存儲節點進行驗證.非滿載的存儲操作會破壞程序的正確性, 在當前的實現中, 通過添加額外的向量重組指令對結果中的無效數據進行替換從而實現非滿載存儲的正確性. 為了保證向量重組指令的合法性, 需要對存儲節點的數據類型進行檢查, 以確保可以生成向量重組指令. 現在一個可以安全向量化的非滿載SLP計算樹已經建立起來,接下來是正常的對齊分析、依賴分析等.

3.2 變換

ISLP按照常規的調度順序從葉子節點到根節點為非滿載SLP計算樹生成向量代碼. ISLP代碼生成的核心是通過添加額外的數據重組操作來維持程序計算狀態的正確性和避免可能的算術異常. 我們以清單2所示的標量C代碼為例, 通過展示4通道下3路加法操作的向量化方法, 對ISLP的代碼生成策略進行說明.向量代碼如清單3所示, 在向量寫回階段, 額外的數據重組操作被引入以完成對無效數據的替換.

清單2. 標量C代碼float a[5], b[3], c[3];a[i+0] = b[i+0] + c[i+0];a[i+1] = b[i+1] + c[i+1];a[i+2] = b[i+2] + c[i+2];清單3. 4通道向量代碼vload v1 b vload v2 c

?

詳細的ISLP代碼生成如圖1所示. 對于非滿載的加載節點, 根據對齊信息從起始地址處生成常規向量加載. 為了避免可能存在的訪存越界, 在發射指令之前考慮對待處理的數組進行尾部填充. 對于固定分配數組, 直接增加數組的大小; 對于動態數組, 調整參數申請更大的空間. 以b數組為例, 其內存分配方式為固定分配類型, 大小為3. 4通道向量加載操作將內存中以b[0]為起始地址的4個連續存放的數據元素加載至向量寄存器v1, 向量加載可能觸發地址越界, 造成程序錯誤. 為此, 通過增加數組大小對b數組進行尾部填充,在有效數據之后填充若干個dummy, 即未初始化的冗余數據元素. 這樣vload操作不會訪問到未知的地址空間, 越界異常得以避免.

圖1 ISLP代碼生成

常規向量加載在向量寄存器中引入了無效的冗余數據, 無效數據和有效數據一同參與計算, 算術操作可能觸發不可預測的異常. 為此通過向量重組指令使得向量寄存器中的有效數據覆蓋無效數據. 有效數據的操作總是可以信任的, 因此算術異常得以避免. 異常的發生并不是必然的, 換言之也可以忽略異常發生的風險, 以換取更高的性能. 我們將算術異常的避免設置為一種可選的安全模式供用戶選擇是否啟用. b數組中的dummy和b[0], b[1], b[2]一起被加載至向量寄存器v1, 用于參加后續算術操作. 由于dummy為未知數據,該通道可能觸發浮點異常. 大多數SIMD擴展都支持permute操作對向量寄存器中的數據進行重組. 在安全模式啟用的情況下, 使用已知數據, 例如b[2], 替換dummy. 同理, 根據數據的對應關系, 使用c[2]替換v2中的dummy. 這樣可以避免dummy所在通道發生不可預測的算術異常.

面向ISLP的向量存儲維持程序計算狀態的正確性. 當遞歸至根節點時, 可以根據對齊信息從起始地址處生成常規向量存儲, 在此之前需要對向量寄存器中的無效數據進行替換, 否則它會覆蓋有效數據并導致程序錯誤. 首先從寫回地址處加載原始數據到向量寄存器, 接著按照有效數據的對應位置對兩個向量寄存器中的數據進行重組, 最后使用常規向量存儲將結果寫回內存. 若直接使用vstore指令將向量寄存器v3中的數據寫回以a[0]為起始地址的連續地址空間, 將導致a[3]被冗余數據覆蓋, 造成程序計算狀態的錯誤. 為此首先使用a[3]處的數據替換原dummy通道的冗余數據b[2]+c[2], 然后寫回內存. permute操作可以幫助完成這一功能, 首先從a[0]處進行向量加載, a[3]被加載至向量寄存器v4, 接著和v3進行數據重組, 結果存放至v5, 最后將v5中的內容寫回內存. 這就保證了向量化前后程序計算狀態的一致性.

此外, 在發射數據重組指令或者使用插入指令構造向量操作數時, 需要對掩碼數組或者向量操作數進行尾部填充, 通常重復有效數據到填充位置即可.

3.3 代價模型

非滿載SLP向量化作為常規SLP向量化的擴展重用現有的基本塊向量化代價模型. 基本塊向量化的收益等于基本塊內所有SLP計算樹的收益之和. SLP計算樹的收益等于每個節點的收益之和. 每個節點的收益由對應的標量語句代價和向量語句代價的差值刻畫. 非滿載SLP向量化在完成某些向量操作時存在額外的語句代價, 在進行代價計算時需要對該類型節點的向量代價進行修正.

根據當前的代碼生成方式, 在計算加載節點向量代價時, 如果安全模式被啟用, 需要添加相應的數據重組代價. ISLP加載節點的向量代價:

stmt_costvload+bool×stmt_costperm

其中, stmt_costvload為常規向量加載代價,stmt_costperm表示向量重組語句代價. 當安全模式啟用時, b ool為1,否則為0.

在向量寫回階段要求額外的數據加載和重組操作,加載語句的對齊方式與存儲語句要保持一致. ISLP存儲節點的向量代價:

stmt_costvstore+stmt_costvload+stmt_costperm

其中, stmt_costvstore為 常規向量存儲代價.

4 實驗與分析

為了驗證非滿載SLP向量化的有效性, 從標準測試集中選取適合做非滿載SLP向量化的程序作為測試用例, 對向量化的收益進行評估. 測試用例包括: SPEC CPU2006測試集中的435.gromacs, SPEC CPU2000測試集中的183.equake、191.fma3d, NPB測試集中的BT. 這些程序的核心函數中都存在著超字級并行性不足的情況, 可以使用非滿載SLP向量化進行發掘. 實驗在intel xeon E5-2 620上進行, 操作系統為Linux, 編譯器為GCC 7.1.0, 開啟AVX指令集擴展, 向量長度256 bit,可同時處理8個單精度浮點數據或4個雙精度浮點數據.

進行3組測試: 標量版本, 使用-ftree-no-vectorize選項關閉向量化; 非滿載SLP向量化優化前, 使用-ftree-vectorize選項開啟常規向量化; 非滿載SLP向量化優化后, -insufficient-slp選項開啟非滿載SLP向量化. 記錄程序的執行時間, 以標量版本為基準, 使用標量執行時間除以向量執行時間得到加速比.

實驗結果如圖2所示. 所選測試用例在非滿載SLP向量化后獲得了不同程度的性能提升. 435.gromacs的核心循環存在間接數組訪問, 183.quake的核心為do-while循環, 191.fma3d的核心為結構體訪問, 它們都無法發掘向量并行性, 而迭代內同構語句數目為3,小于AVX平臺的向量化因子, SLP向量化無法發掘核心中的超字級并行性, 因此常規向量化方法的加速比較低, 分別為1.03, 1.0, 1.02. 開啟ISLP后, 核心循環均被向量化. 435.gromacs核心循環中可并行部分占比較少, 加速效果不明顯, 加速比為1.08. 183.quake和191.fma3d分別為1.25和1.13. BT的核心為非循環結構且存在著語句數目小于向量化因子的同構語句塊, SLP方法不能識別, 常規向量化加速比為1.02, 開啟ISLP后核心函數被向量化, 加速比1.10. average一欄展示了對應向量化版本在4個測試用例上加速比的算術平均值, 常規向量化方法為1.02, 打開ISLP后為1.14,ISLP擴展后的基本塊向量化器比常規版本在性能上提升11.8%. 實驗表明, 非滿載SLP向量化可以有效地增強GCC的向量化能力, 提高程序的執行效率.

圖2 實驗結果

5 總結與展望

本文針對較長向量長度下的程序并行性相對不足這一問題, 介紹了一種面向基本塊的非滿載向量化方法ISLP. 在對GCC的SLP向量化框架進行了深入分析后, 從并行性檢測、代價模型、代碼生成3個方面闡述了ISLP在GCC中的設計與實現. AVX平臺上的實驗結果表明, 擴展后的SLP框架可以有效地對超字級并行性不足的程序進行向量化處理, 提高程序執行效率. 值得注意的是, ISLP在多線程環境下是不安全的, 而且代價模型的準確性仍有待提高, 這些都是進一步需要研究的問題[20].