劉浩浩, 韓 林, 崔平非

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

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

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

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

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

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

(2) 闡述了ISLP在GCC中的設(shè)計(jì)與實(shí)現(xiàn).

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

1 非滿載SLP向量化

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

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

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

2 GCC中的SLP向量化

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

向量化器首先完成基本塊內(nèi)數(shù)據(jù)引用的收集. 借助于標(biāo)量演化分析器, vect_analyze_data_refs為每一個(gè)數(shù)據(jù)引用構(gòu)建訪問函數(shù). 訪問函數(shù)將被用于依賴分析、訪存模式和對齊分析.

清單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負(fù)責(zé)數(shù)據(jù)引用的訪存模式分析, 交錯(cuò)鏈(interleaving chains)和組訪問(group access)的識(shí)別與建立. 交錯(cuò)鏈由基址具有線性關(guān)系、跨幅相同、數(shù)據(jù)類型相同的數(shù)據(jù)引用所組成,根據(jù)數(shù)據(jù)引用的讀寫類型又可分為交錯(cuò)加載(interleaving load)和交錯(cuò)存儲(chǔ)(interleaving store). 特別的,當(dāng)數(shù)據(jù)引用的訪存模式為非連續(xù)訪問且基址相鄰時(shí),這些互相獨(dú)立的內(nèi)存訪問構(gòu)成了一種特殊的訪存模式,稱之為組訪問, 對應(yīng)的交錯(cuò)鏈稱為組加載(group load)或組存儲(chǔ)(group store). 組訪問實(shí)際上是對一塊連續(xù)內(nèi)存地址空間的訪問. 每一個(gè)group store都將作為一個(gè)獨(dú)立的SLP種子參與后續(xù)超字級并行性的檢測.

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

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

同構(gòu)性和數(shù)據(jù)類型檢測通過后, 嘗試對標(biāo)量語句進(jìn)行打包. 首先考慮同構(gòu)語句是否為加載類型, 加載類型的同構(gòu)語句被視為SLP計(jì)算樹的葉子節(jié)點(diǎn), 打包后立即返回. 對非加載類型的同構(gòu)語句進(jìn)行打包前, 要首先遍歷它的孩子節(jié)點(diǎn), 對它的孩子節(jié)點(diǎn)完成打包. 這是因?yàn)楦腹?jié)點(diǎn)的操作數(shù)依賴于孩子節(jié)點(diǎn). 當(dāng)所有的孩子節(jié)點(diǎn)打包完成后, 返回至父節(jié)點(diǎn)進(jìn)行打包. 根節(jié)點(diǎn)的group store打包后, 一棵完整的SLP計(jì)算樹就被建立起來.

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

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

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

vect_bb_vectorization_profitable_p完成對基本塊向量化的收益分析. 代價(jià)模型對基本塊中所有SLP計(jì)算樹的收益進(jìn)行累加, 作為基本塊向量化的收益. 當(dāng)收益大于零時(shí), 所有的SLP計(jì)算樹都將被向量化; 否則任何SLP計(jì)算樹都不會(huì)被向量化. SLP計(jì)算樹的收益被定義為樹中每個(gè)節(jié)點(diǎn)的收益之和, 每個(gè)節(jié)點(diǎn)的收益等于對應(yīng)的標(biāo)量語句代價(jià)和向量語句代價(jià)的差值.

分析和決策階段通過后, 進(jìn)入向量代碼生成階段.向量化器依次對基本塊內(nèi)的SLP計(jì)算樹進(jìn)行調(diào)度. 每調(diào)度一個(gè)SLP計(jì)算樹, 從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)遞歸地調(diào)用vect_transform_stmt為每個(gè)節(jié)點(diǎn)生成向量代碼.

3 ISLP實(shí)現(xiàn)

3.1 分析

分析階段的目標(biāo)是構(gòu)建可以安全應(yīng)用非滿載SLP向量化的SLP計(jì)算樹. 在當(dāng)前的實(shí)現(xiàn)中, 非滿載SLP向量化對應(yīng)一棵不存在類型轉(zhuǎn)換操作的非滿載SLP計(jì)算樹. 為了對非滿載SLP向量化有更嚴(yán)格的描述, 首先介紹一些相關(guān)概念, 隨后擴(kuò)充SLP分析框架以支持非滿載SLP向量化.

定義1. 一個(gè)SLP計(jì)算樹中的節(jié)點(diǎn)稱為是非滿載的, 如果有:

group_size＜VF

其中, group_size是節(jié)點(diǎn)中同構(gòu)語句的數(shù)目, VF表示向量化因子, 即可并行執(zhí)行的同構(gòu)語句數(shù).

定義2. 一個(gè)SLP計(jì)算樹稱為是非滿載的當(dāng)且僅當(dāng)樹中的全部節(jié)點(diǎn)都是非滿載的.

適用于非滿載SLP向量化的SLP計(jì)算樹的構(gòu)建主要包括3個(gè)部分: (1)構(gòu)建非滿載SLP計(jì)算樹; (2)檢查類型轉(zhuǎn)換操作; (3)檢查根節(jié)點(diǎn)的數(shù)據(jù)重組是否被目標(biāo)機(jī)支持.

非滿載SLP計(jì)算樹的構(gòu)建過程與與常規(guī)SLP計(jì)算樹基本相同. 由定義2可知, 非滿載SLP計(jì)算樹要求所有的樹節(jié)點(diǎn)都是非滿載的, 因此只要在同構(gòu)語句檢測階段認(rèn)為VF大于group_size的同構(gòu)語句組是合法的, 那么在一個(gè)非滿載SLP種子的基礎(chǔ)上, 根據(jù)定義使用鏈遞歸的進(jìn)行擴(kuò)展, 一個(gè)非滿載SLP計(jì)算樹就可以被建立起來.

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

下面對非滿載SLP計(jì)算樹的存儲(chǔ)節(jié)點(diǎn)進(jìn)行驗(yàn)證.非滿載的存儲(chǔ)操作會(huì)破壞程序的正確性, 在當(dāng)前的實(shí)現(xiàn)中, 通過添加額外的向量重組指令對結(jié)果中的無效數(shù)據(jù)進(jìn)行替換從而實(shí)現(xiàn)非滿載存儲(chǔ)的正確性. 為了保證向量重組指令的合法性, 需要對存儲(chǔ)節(jié)點(diǎn)的數(shù)據(jù)類型進(jìn)行檢查, 以確?？梢陨上蛄恐亟M指令. 現(xiàn)在一個(gè)可以安全向量化的非滿載SLP計(jì)算樹已經(jīng)建立起來,接下來是正常的對齊分析、依賴分析等.

3.2 變換

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

清單2. 標(biāo)量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

?

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

圖1 ISLP代碼生成

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

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

此外, 在發(fā)射數(shù)據(jù)重組指令或者使用插入指令構(gòu)造向量操作數(shù)時(shí), 需要對掩碼數(shù)組或者向量操作數(shù)進(jìn)行尾部填充, 通常重復(fù)有效數(shù)據(jù)到填充位置即可.

3.3 代價(jià)模型

非滿載SLP向量化作為常規(guī)SLP向量化的擴(kuò)展重用現(xiàn)有的基本塊向量化代價(jià)模型. 基本塊向量化的收益等于基本塊內(nèi)所有SLP計(jì)算樹的收益之和. SLP計(jì)算樹的收益等于每個(gè)節(jié)點(diǎn)的收益之和. 每個(gè)節(jié)點(diǎn)的收益由對應(yīng)的標(biāo)量語句代價(jià)和向量語句代價(jià)的差值刻畫. 非滿載SLP向量化在完成某些向量操作時(shí)存在額外的語句代價(jià), 在進(jìn)行代價(jià)計(jì)算時(shí)需要對該類型節(jié)點(diǎn)的向量代價(jià)進(jìn)行修正.

根據(jù)當(dāng)前的代碼生成方式, 在計(jì)算加載節(jié)點(diǎn)向量代價(jià)時(shí), 如果安全模式被啟用, 需要添加相應(yīng)的數(shù)據(jù)重組代價(jià). ISLP加載節(jié)點(diǎn)的向量代價(jià):

stmt_costvload+bool×stmt_costperm

其中, stmt_costvload為常規(guī)向量加載代價(jià),stmt_costperm表示向量重組語句代價(jià). 當(dāng)安全模式啟用時(shí), b ool為1,否則為0.

在向量寫回階段要求額外的數(shù)據(jù)加載和重組操作,加載語句的對齊方式與存儲(chǔ)語句要保持一致. ISLP存儲(chǔ)節(jié)點(diǎn)的向量代價(jià):

stmt_costvstore+stmt_costvload+stmt_costperm

其中, stmt_costvstore為 常規(guī)向量存儲(chǔ)代價(jià).

4 實(shí)驗(yàn)與分析

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

進(jìn)行3組測試: 標(biāo)量版本, 使用-ftree-no-vectorize選項(xiàng)關(guān)閉向量化; 非滿載SLP向量化優(yōu)化前, 使用-ftree-vectorize選項(xiàng)開啟常規(guī)向量化; 非滿載SLP向量化優(yōu)化后, -insufficient-slp選項(xiàng)開啟非滿載SLP向量化. 記錄程序的執(zhí)行時(shí)間, 以標(biāo)量版本為基準(zhǔn), 使用標(biāo)量執(zhí)行時(shí)間除以向量執(zhí)行時(shí)間得到加速比.

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

圖2 實(shí)驗(yàn)結(jié)果

5 總結(jié)與展望

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