基于申威GCC編譯器的間接預(yù)取算法①

余龍龍, 韓 林

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

高性能計(jì)算 (high performance computing, HPC)和數(shù)據(jù)處理程序不僅在傳統(tǒng)醫(yī)藥研發(fā), 航空航天制造和氣象預(yù)測(cè)中起到重要的作用, 同時(shí)與人工智能、大數(shù)據(jù)以及區(qū)塊鏈的融合也日趨緊密. 然而, 一些高性能計(jì)算和數(shù)據(jù)處理程序, 其性能受到嚴(yán)重的內(nèi)存延遲限制[1–3], 這是因?yàn)椴灰?guī)則的內(nèi)存訪問(wèn)(內(nèi)存地址不具備可識(shí)別模式)無(wú)法放入高速緩存中. 傳統(tǒng)的解決方案是使用硬件控制的預(yù)取技術(shù), 允許硬件檢測(cè)常見(jiàn)的訪存模式(如步長(zhǎng)[4])將高速緩存未命中與其他處理器執(zhí)行的有用工作重疊達(dá)到隱藏訪存延遲的目的. 但是, 這些技術(shù)并不適用不規(guī)則的數(shù)據(jù)訪存模式, 如哈希、鏈表等遞歸結(jié)構(gòu), 也不適用間接存儲(chǔ)器訪問(wèn). 在間接訪存中,其加載的地址是基于存儲(chǔ)在數(shù)組中的索引而非歸納變量.

針對(duì)不規(guī)則的數(shù)據(jù)訪問(wèn)模式往往采用軟件預(yù)取技術(shù)[5]. 其原理是, 使用數(shù)據(jù)結(jié)構(gòu)和算法知識(shí)將指令插入程序中, 通過(guò)重疊存儲(chǔ)器訪問(wèn)提前將所需數(shù)據(jù)加載至緩存中, 從而提高了程序訪存性能. 過(guò)去常采取手動(dòng)插入預(yù)取的方式. 然而, 這很難做到. 因?yàn)槭謩?dòng)插入往往面臨著沒(méi)有嚴(yán)格的插入指導(dǎo)原則和對(duì)軟件預(yù)取、硬件預(yù)取之間的相互作用關(guān)系較難理解等困難. 此外, 為了獲得預(yù)取收益, 使用軟件預(yù)取必須保證預(yù)取地址計(jì)算和預(yù)取數(shù)據(jù)的代價(jià)不能超過(guò)隱藏訪存的延遲, 否則預(yù)取將不會(huì)帶來(lái)任何好處. 因此, 為了進(jìn)一步減少程序員工作, 需要設(shè)計(jì)專(zhuān)門(mén)的算法來(lái)自動(dòng)為程序插入合適的預(yù)取.

過(guò)去針對(duì)不規(guī)則訪存模式進(jìn)行軟件預(yù)取做了大量研究, 主要涉及預(yù)取性能研究、預(yù)取生成和預(yù)取調(diào)度3個(gè)方面.

(1) 預(yù)取性能研究. Lee等人[6]分析了軟件預(yù)取和硬件預(yù)取在SPEC各個(gè)基準(zhǔn)上的加速比以及二者之間的協(xié)同和對(duì)抗作用. 然而, 這些基準(zhǔn)并不傾向于在其代碼熱點(diǎn)區(qū)域顯示間接存儲(chǔ)器訪問(wèn), 因此無(wú)法用于間接預(yù)取性能評(píng)測(cè). Mowry[7]使用NAS[8]并行基準(zhǔn)測(cè)試套件的整數(shù)排序和共軛梯度基準(zhǔn)評(píng)測(cè)間接預(yù)取性能.Ainsworth等人[9]使用HPC[10]、大數(shù)據(jù)[11]和數(shù)據(jù)庫(kù)[12]也做到了. 此外, Ainsworth等人還分析了間接預(yù)取在不同體系結(jié)構(gòu)和測(cè)試基準(zhǔn)中性能差距很大的原因, 表明預(yù)取距離、內(nèi)存帶寬、TLB支持等因素對(duì)間接預(yù)取性能的影響. 實(shí)際上, 程序自身特點(diǎn)也會(huì)影響預(yù)取性能,如程序間接預(yù)取數(shù)據(jù)規(guī)模、插入預(yù)取增加的指令開(kāi)銷(xiāo).本文在基于預(yù)取效益和相關(guān)程序特點(diǎn)的基礎(chǔ)上, 增加了間接預(yù)取代價(jià)模型.

(2) 預(yù)取生成. Callahan等人為數(shù)據(jù)庫(kù)哈希表手動(dòng)插入預(yù)取[13]. 在自動(dòng)預(yù)取方面, 過(guò)去針對(duì)常規(guī)步長(zhǎng)訪問(wèn)模式進(jìn)行預(yù)取做了很多工作[5,14], 并且已經(jīng)在GCC[15]、ICC[16]等多個(gè)編譯器中實(shí)現(xiàn). 但是, 只有當(dāng)性能超過(guò)硬件步長(zhǎng)預(yù)取器時(shí), 才會(huì)特別有用. Luk等人[17]實(shí)現(xiàn)了鏈表訪問(wèn)模式的自動(dòng)預(yù)取, 但由于鏈表結(jié)構(gòu)缺乏內(nèi)存級(jí)并行性, 所以性能提升有限. Xeon Phi編譯器[18]實(shí)現(xiàn)了一種簡(jiǎn)單的跨步-間接存儲(chǔ)器訪問(wèn)模式的算法, 但是默認(rèn)情況下并未啟用, 并且關(guān)于其內(nèi)部工作原理的信息也很少. Mowry[7]實(shí)現(xiàn)了高級(jí)類(lèi)C代碼的間接預(yù)取, 還通過(guò)拆分循環(huán)的最后幾次迭代, 消除了對(duì)循環(huán)內(nèi)預(yù)取的邊界檢查. Ainsworth等人[9]在LLVM編譯器中實(shí)現(xiàn)了一種可以為簡(jiǎn)單跨步-間接存儲(chǔ)器訪問(wèn)模式和哈希插入預(yù)取的算法, 在錯(cuò)誤避免和值跟蹤方面做了很多工作, 但缺少預(yù)取代價(jià)分析和預(yù)取距離自動(dòng)計(jì)算. 不同的是, 本文為GCC編譯器設(shè)計(jì)了一個(gè)完整優(yōu)化遍, 可以自動(dòng)識(shí)別程序間接存儲(chǔ)器訪問(wèn)模式并為之插入合適預(yù)取. 黃艷[19]提出一種面向非規(guī)則數(shù)據(jù)的線程預(yù)取與L2硬件預(yù)取優(yōu)化組合策略, 減少了系統(tǒng)訪存請(qǐng)求, 提高了預(yù)取準(zhǔn)確率和相關(guān)開(kāi)銷(xiāo). 此外, 軟件預(yù)取也可以被分配到不同的線程, 以減少為預(yù)取而添加的大量額外指令的影響[20–23].

(3) 預(yù)取調(diào)度. 根據(jù)軟件預(yù)取原理, 需要提前一定循環(huán)迭代次數(shù)將數(shù)據(jù)提前加載至緩存．因此進(jìn)行預(yù)取調(diào)度的時(shí)機(jī)也很重要, 預(yù)取的過(guò)早或過(guò)晚都會(huì)對(duì)程序性能造成影響. Mowry等人[14]考慮內(nèi)存帶寬與指令數(shù)量的比率來(lái)計(jì)算預(yù)取距離, 而對(duì)于間接預(yù)取則從索引數(shù)組提前迭代次數(shù)(預(yù)取距離)隱藏訪存延遲的角度研究了間接預(yù)取序列之間的調(diào)度關(guān)系[7], 但并未提出間接預(yù)取距離計(jì)算方法. 相比之下, Ainsworth等人[9]則提出了根據(jù)生成地址所需的加載次數(shù)對(duì)間接預(yù)取序列進(jìn)行調(diào)度的計(jì)算方法, 但預(yù)取距離卻是一個(gè)測(cè)試經(jīng)驗(yàn)值.不同的是, 本文提出了一種間接預(yù)取距離自動(dòng)計(jì)算方法.

SW1621作為一款高性能多核處理器, 具有完全自主知識(shí)產(chǎn)權(quán). 與之適配的GCC編譯器針對(duì)申威CPU自主指令集進(jìn)行了特定優(yōu)化, 能夠支持多種語(yǔ)言、多種編譯, 同時(shí)還具有良好的可移植性, 但是在處理高延遲間接存儲(chǔ)器訪問(wèn)方面還不完善. 為了進(jìn)一步提高申威架構(gòu)訪存性能, 本文設(shè)計(jì)并實(shí)現(xiàn)了完整的編譯器優(yōu)化遍來(lái)處理中間表示的復(fù)雜性, 同時(shí)還就預(yù)取錯(cuò)誤避免、預(yù)取代價(jià)分析和預(yù)取距離自動(dòng)計(jì)算進(jìn)行深入研究.

本文首先介紹了軟件預(yù)取的相關(guān)背景和研究工作,文中第1節(jié)對(duì)間接訪存進(jìn)行預(yù)取可行性分析以及介紹本文采用的預(yù)取調(diào)度方案; 第2節(jié)詳細(xì)介紹了間接預(yù)取流程; 第3節(jié)是實(shí)驗(yàn)測(cè)試及分析; 最后總結(jié)全文.

1 間接預(yù)取可行性分析

代碼清單1展示了常見(jiàn)的間接存儲(chǔ)器訪問(wèn)模式.它涉及順序移動(dòng)的index_array數(shù)組, 基于index_array數(shù)組數(shù)據(jù)的函數(shù)f(x)對(duì)間接數(shù)組indir_array進(jìn)行訪問(wèn).第1個(gè)數(shù)組(index_array)的索引i是標(biāo)準(zhǔn)的循環(huán)歸納變量, 以固定步長(zhǎng)順序移動(dòng), 可以很容易預(yù)測(cè)下一個(gè)數(shù)組地址. 但對(duì)于間接數(shù)組(indir_array)來(lái)說(shuō), 其索引是index_array[i]數(shù)據(jù)本身, 其存儲(chǔ)器訪問(wèn)地址大都高度分散且不可預(yù)測(cè).

代碼清單1. 跨步間接存儲(chǔ)器訪問(wèn)的一般形式1 for ( i = 0; i ＜ NUM_KEYS; i++) {2 sum += indir_array[f(index_array[i])];3 }

由于間接數(shù)組(indir_array)的地址依賴(lài)于索引數(shù)組(index_array)的數(shù)值本身, 而硬件跨步預(yù)取器無(wú)法識(shí)別這種訪問(wèn)模式. 但是由于常規(guī)索引數(shù)組的前向性,在軟件中可以很容易計(jì)算間接數(shù)組未來(lái)存儲(chǔ)器訪問(wèn)的地址. 當(dāng)f(x)是一個(gè)恒等函數(shù)時(shí), 這表示一個(gè)簡(jiǎn)單的跨步-間接訪問(wèn)模式. 實(shí)際上, 在基于循環(huán)的代碼中, 簡(jiǎn)單跨步-間接訪問(wèn)似乎是最常見(jiàn)的間接訪存類(lèi)型(也是在測(cè)試程序中觀察到的唯一情況). 因此預(yù)取算法將側(cè)重于單級(jí)間接訪存模式的識(shí)別和生成預(yù)取.

選擇合適的間接預(yù)取序列方案, 對(duì)提高間接預(yù)取性能至關(guān)重要. 算法將采用下述方法對(duì)簡(jiǎn)單跨步-間接訪存的預(yù)取序列進(jìn)行調(diào)度. 方法如代碼清單所示, 直接的方式是在第2行插入針對(duì)indir_array的預(yù)取. 然而,為了進(jìn)一步優(yōu)化間接預(yù)取性能, 同時(shí)在第3行以2倍預(yù)取indir_array的偏移量插入針對(duì)index_array的預(yù)取. 這保證了索引數(shù)組數(shù)據(jù)有充足時(shí)間可以加載至L1緩存, 避免了在計(jì)算間接數(shù)組預(yù)取地址時(shí)可能發(fā)生的cache miss現(xiàn)象, 預(yù)取偏移量(offset)的計(jì)算將在第3節(jié)說(shuō)明. 此外, 由于增加對(duì)索引數(shù)組的預(yù)取干擾了硬件跨步預(yù)取器對(duì)預(yù)取距離的訓(xùn)練, 因此硬件預(yù)取不會(huì)對(duì)間接預(yù)取性能產(chǎn)生影響.

代碼清單2. 間接預(yù)取序列調(diào)度f(wàn)or ( i = 0; i ＜ NUM_KEYS; i++) {prefetch(indir_array[index_array[i+offset/2]]);prefetch (index_array[i+offset]);sum += indir_array[(index_array[i])];}1 23 4 5

2 循環(huán)間接數(shù)組預(yù)取

間接預(yù)取算法以一個(gè)完整遍集成于SWGCC編譯器中, 可以基于索引數(shù)組的前向性查找間接存儲(chǔ)器訪問(wèn)模式, 并為之生成軟件預(yù)取. 首先描述所需的分析,然后再插入計(jì)算預(yù)取地址的代碼和發(fā)射預(yù)取. 算法主要流程如圖1所示.

圖1 間接預(yù)取算法總體框架

間接預(yù)取算法以循環(huán)作為輸入, 遍歷循環(huán)基本塊的gimple語(yǔ)句序列搜集間接內(nèi)存引用信息, 然后計(jì)算預(yù)取距離并進(jìn)行預(yù)取收益分析, 得到合適的間接預(yù)取序列, 最后對(duì)滿(mǎn)足收益模型的間接預(yù)取序列插入軟件預(yù)取. 其中預(yù)取錯(cuò)誤避免分為2個(gè)部分: 第1部分是在內(nèi)存引用信息收集階段排除索引數(shù)組是寫(xiě)數(shù)據(jù)結(jié)構(gòu)的間接預(yù)取序列, 避免進(jìn)行無(wú)效預(yù)取; 第2部分是在預(yù)取生成階段, 插入限制歸納變量在有效范圍的指令, 確保不出現(xiàn)地址越界錯(cuò)誤.

2.1 間接內(nèi)存引用信息收集

間接預(yù)取算法是基于GCC編譯器的tree-ssa優(yōu)化框架. 在內(nèi)存引用信息收集階段, 利用gimple中間表示在靜態(tài)單賦值形式(static single assignment form,SSA)形式所具有的精準(zhǔn)的定義/使用關(guān)系, 從每一個(gè)內(nèi)存引用向后深度優(yōu)先搜索間接內(nèi)存引用信息, 之后將其存儲(chǔ)在由兩個(gè)結(jié)構(gòu)體組成的“十字鏈表”數(shù)據(jù)結(jié)構(gòu)中.對(duì)常規(guī)和固定布局的內(nèi)存訪問(wèn)模式進(jìn)行數(shù)據(jù)預(yù)取時(shí),利用數(shù)據(jù)訪問(wèn)的時(shí)間相關(guān)性[24]和空間相關(guān)性[25]可以有效預(yù)測(cè)未來(lái)內(nèi)存訪問(wèn). 但對(duì)于間接內(nèi)存引用的局部性卻存在兩個(gè)極端: 一是所有索引值可能是相同的, 間接訪存看起來(lái)似乎具有時(shí)間局部性一樣. 而另一個(gè)極端中, 每個(gè)引用可能指向唯一的緩存行, 看起來(lái)又好像不具備局部性一樣. 由于無(wú)法分析以上極端情況下的數(shù)據(jù)局部性, 因此決定始終預(yù)取.

算法1. 間接訪存模式識(shí)別1 foreach (bb: blocks within a loop):2 foreach (stmt: stmts within a block):3 if (the rhs of stmt is a memory reference)4 prefetch = {}//獲取內(nèi)存引用索引的def-stmt 5 index_stmt = get_def_stmt(rhs)6 if ((index_ref, info, indvar)=DFS(index_stmt,loop) != null)7 prefetch U= {indvar, index_ref, infos}//數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)內(nèi)存引用信息8 indir_refs U= prefetch 9 DFS (index_stmt, loop) {10 candidate = {}//間接內(nèi)存引用存在常量偏移量

11 foreach (op: src_operand of index_stmt)://獲取操作數(shù)op的def-stmt 12 op_stmt = get_def_stmt(op)//op_stmt包含內(nèi)存引用13 if (op_stmt contain a memor reference)14 candidate U= {(index_ref, info, {infos})}//獲取索引內(nèi)存引用的索引15 index = get_index (index_ref)//若index可以遞歸鏈表示16 if (SCEV (loop, index))17 candidate U={(index, {index_ref, infos}//op_stmt不含有內(nèi)存引用, 繼續(xù)DFS 18 elif (op_stmt not contain memory reference)19 if ((info, index_ref)=DFS(op_stmt, loop)!=null)20 candidate U= {(index_ref, info, {infos})}//選擇最接近索引內(nèi)存引用的歸納變量21 indvar = closest_loop_indvar ()//不允許非歸納變量phi節(jié)點(diǎn)22 remove (candidate, contains non-induction phi)//不允許包含函數(shù)調(diào)用23 remove(candidate, contains function call)//內(nèi)存引用基址不可尋址24 remove (candidate, base_addr not addressable)25 }

分析階段的目標(biāo)是識(shí)別可以發(fā)射有效預(yù)取的間接內(nèi)存引用, 并收集為其生成有效預(yù)取地址所需的所有關(guān)鍵信息. 算法1給出了間接訪存識(shí)別的主要過(guò)程. 分析一次只考慮一個(gè)函數(shù), 并且搜索范圍限定在一個(gè)函數(shù)體, 對(duì)函數(shù)體的每一個(gè)循環(huán)嵌套結(jié)構(gòu)按逆序從最內(nèi)層循環(huán)開(kāi)始查找有效間接內(nèi)存引用. 依次遍歷循環(huán)體的每一個(gè)基本塊, 然后對(duì)每一個(gè)基本塊的gimple語(yǔ)句序列依次進(jìn)行迭代(算法1的1–2行). 若語(yǔ)句的右表達(dá)式是一個(gè)內(nèi)存引用, 則根據(jù)SSA的定義/使用關(guān)系獲取當(dāng)前內(nèi)存引用索引的唯一定義語(yǔ)句(算法1第5行).使用深度優(yōu)先搜索算法向后遍歷定義語(yǔ)句的源操作數(shù)的數(shù)據(jù)依賴(lài)圖(算法1第11行), 若源操作數(shù)的定義語(yǔ)句是一個(gè)包含內(nèi)存引用的賦值語(yǔ)句(算法1第13行),則利用GCC優(yōu)化框架的標(biāo)量演化(scalar evolution,SCEV)功能進(jìn)一步判斷內(nèi)存引用的索引是否為一個(gè)歸納變量(算法1第16–17行). 若是一個(gè)普通賦值語(yǔ)句,將繼續(xù)深度遞歸搜索符合要求的索引內(nèi)存引用(算法1第18–19行). 當(dāng)沒(méi)有找到一個(gè)符合要求的索引內(nèi)存引用或者到達(dá)不在函數(shù)內(nèi)的指令時(shí), 將停止沿著特定路徑繼續(xù)搜索.

如果存在多條路徑引用不同路徑的歸納變量, 選擇最接近索引內(nèi)存引用的歸納變量(算法1第21行),這是因?yàn)樵摎w納變量可能是該循環(huán)中最細(xì)粒度的內(nèi)存級(jí)并行性形式, 而其他歸納變量在當(dāng)前循環(huán)的每次迭代中可能僅作為一個(gè)不變量. 為了確保預(yù)取的順利進(jìn)行, 需要進(jìn)一步約束間接預(yù)取序列, 使其不出現(xiàn)非歸納變量phi節(jié)點(diǎn)(算法1第22行)和函數(shù)調(diào)用(算法1第23行), 因?yàn)榍罢呖赡鼙硎緩?fù)雜的控制流, 而后者可能導(dǎo)致副作用. 對(duì)于一些內(nèi)存引用基址是函數(shù)形參的情況也進(jìn)行了預(yù)取, 前提是該形參變量具備可尋址性, 同樣的內(nèi)存引用的基址也必須是可尋址的(算法1第24行).

算法通過(guò)式(1)對(duì)所有內(nèi)存引用地址進(jìn)行解析. 具體參數(shù)含義如表1所示. 在之后的預(yù)取生成階段, 將按照式(1)插入計(jì)算間接數(shù)組地址的相關(guān)指令.

表1 內(nèi)存引用地址計(jì)算公式

參數(shù) 含義base_address 內(nèi)存引用基址, 與b[0]含義不同step 內(nèi)存引用元素步長(zhǎng), 與數(shù)據(jù)類(lèi)型有關(guān)indvar 在索引數(shù)組中表示循環(huán)歸納變量; 在間接數(shù)組中表示索引數(shù)組本身所加載的數(shù)據(jù)delta 內(nèi)存引用的常量偏移量

循環(huán)中所有間接內(nèi)存引用信息由圖2所示的兩個(gè)結(jié)構(gòu)體描述. 兩個(gè)結(jié)構(gòu)體將內(nèi)存引用信息組織成“十字鏈表”形式, 每一個(gè)元素都是一個(gè)鏈表頭指針, 表示一個(gè)間接訪存信息group, 在同一個(gè)group的索引內(nèi)存引用信息具有相同的indir_address、indir_step和indir_delta. 每一個(gè)索引內(nèi)存引用存儲(chǔ)在mem_index_ref結(jié)構(gòu)體中, mem_indir_ref_group以一個(gè)refs指針指向索引內(nèi)存引用, mem_index_ref以一個(gè)next指針鏈接屬于同一group的索引內(nèi)存引用.

圖2 描述間接內(nèi)存引用的結(jié)構(gòu)體

2.2 預(yù)取錯(cuò)誤避免

雖然預(yù)取本身不會(huì)造成錯(cuò)誤, 但用于間接預(yù)取地址計(jì)算的中間加載可能會(huì)導(dǎo)致錯(cuò)誤. 若循環(huán)體中存在對(duì)索引數(shù)組的寫(xiě)數(shù)據(jù)結(jié)構(gòu), 可能會(huì)預(yù)取無(wú)效的數(shù)據(jù). 更嚴(yán)重的是在對(duì)索引數(shù)組的解引用期間可能會(huì)產(chǎn)生非法的加載地址, 與預(yù)取操作不同, 加載指令在非法的地址上會(huì)發(fā)生內(nèi)存異常, 導(dǎo)致程序崩潰.

為應(yīng)對(duì)上述問(wèn)題, 預(yù)取算法分別采取兩種策略. 首先, 對(duì)循環(huán)的所有規(guī)則仿射內(nèi)存引用信息進(jìn)行收集和分析, 只在沒(méi)有找到對(duì)索引數(shù)組的存儲(chǔ)時(shí), 才對(duì)該間接訪存進(jìn)行預(yù)取. 例如間接內(nèi)存引用A[B[i]], 若循環(huán)中存在對(duì)B[i]的存儲(chǔ), 將舍棄對(duì)A[B[i]]的預(yù)取, 因?yàn)闊o(wú)法保證最終預(yù)取的數(shù)據(jù)是有效的. 其次, 在預(yù)取地址生成代碼中, 將使用gimple三目運(yùn)算語(yǔ)句檢查歸納變量與前向預(yù)取距離相加之后的值是否超過(guò)其最大值.例如,在代碼清單2的第2行檢查i + offset/2 ＜ NUM_KEYS.其中, 歸納變量的最大值作為索引數(shù)組可以被訪問(wèn)的最后一個(gè)元素的下標(biāo), 可以很容易在GCC的循環(huán)結(jié)構(gòu)分析中獲取. 此外, gimple三目運(yùn)算語(yǔ)句在申威后端不會(huì)降級(jí)解析成跳轉(zhuǎn)指令, 這減少了因指令跳轉(zhuǎn)導(dǎo)致的額外開(kāi)銷(xiāo).

在計(jì)算間接預(yù)取地址時(shí), 除了可以使用普通的加載指令, 還可以使用特殊的非異常加載. 若索引內(nèi)存引用類(lèi)型為array_ref, 則可以將歸納變量增加一定前向預(yù)取距離的值作為內(nèi)存引用新的索引, 新的內(nèi)存引用將在后端生成普通加載指令, 并利用原有比較指令進(jìn)行地址檢查, 無(wú)需在gimple階段進(jìn)行額外的歸納變量越界檢查, 既減少了指令開(kāi)銷(xiāo), 同時(shí)也避免了代價(jià)高昂(或可能致命)的地址越界異常.

2.3 預(yù)取距離計(jì)算

獲得預(yù)取性能收益的關(guān)鍵是以一個(gè)足夠大的前向預(yù)取距離對(duì)預(yù)取進(jìn)行調(diào)度, 以達(dá)到隱藏訪存延遲的目的. 預(yù)取距離的經(jīng)典計(jì)算方法[14]在預(yù)估指令執(zhí)行時(shí)間時(shí)并未考慮因插入預(yù)取帶來(lái)的開(kāi)銷(xiāo), 而在間接預(yù)取中指令開(kāi)銷(xiāo)更大. Ainsworth等人[9]認(rèn)為以間接訪問(wèn)為特征的代碼通常是受內(nèi)存限制的, 其執(zhí)行時(shí)間應(yīng)由加載指令決定. 提出根據(jù)預(yù)取序列中加載總數(shù)和給定加載在序列中位置的計(jì)算預(yù)取序列中每個(gè)內(nèi)存引用相對(duì)預(yù)取距離的比值, 但是預(yù)取距離卻是一個(gè)測(cè)試值. 受經(jīng)典預(yù)取距離計(jì)算方法的啟發(fā), 并進(jìn)一步研究了間接內(nèi)存引用數(shù)量和預(yù)取距離之間的關(guān)系, 提出根據(jù)間接預(yù)取的內(nèi)存引用總數(shù)和系統(tǒng)內(nèi)存帶寬乘積與插入預(yù)取后的循環(huán)體執(zhí)行時(shí)間的比率來(lái)計(jì)算預(yù)取距離, 如式(2)所示.

其中,n是間接預(yù)取序列中的總的內(nèi)存引用數(shù), 對(duì)應(yīng)編譯器常量為indir_mem_count, 若循環(huán)只有一個(gè)簡(jiǎn)單跨步-間接訪存, 則n=2.L是與后端體系結(jié)構(gòu)相關(guān)的訪存延遲,indir_time是插入預(yù)取之后預(yù)估的循環(huán)體指令執(zhí)行時(shí)間.

2.4 預(yù)取代價(jià)評(píng)估

在循環(huán)數(shù)組間接預(yù)取算法中定義了兩個(gè)代價(jià)模型,用于決定是否為循環(huán)的間接訪存插入預(yù)取.

代價(jià)模型1: 循環(huán)迭代次數(shù)

根據(jù)預(yù)取產(chǎn)生效益的原理, 若循環(huán)的迭代規(guī)模很小, 則無(wú)法隱藏訪存延遲. 因此, 對(duì)于擁有高延遲的間接存儲(chǔ)訪問(wèn)則需要更大的循環(huán)迭代規(guī)模才可以獲得預(yù)取收益. 算法判斷預(yù)估的循環(huán)的迭代次數(shù)(trip_count)和前向迭代距離(ahead distance)的比值與預(yù)設(shè)值(TRIP_COUNT_TO_INDIR_AHEAD_RATIO)的大小.若比值小于預(yù)設(shè)值或無(wú)法預(yù)估循環(huán)迭代次數(shù), 則不予預(yù)取. 代價(jià)模型如式(3)所示:

其中,LC表示預(yù)估的循環(huán)跳脫計(jì)數(shù), 在間接預(yù)取遍中對(duì)應(yīng)變量為loop_niter;TRIP_COUNT_TO_INDIR_AHEAD_RATIO是預(yù)設(shè)的比值, 可以根據(jù)系統(tǒng)架構(gòu)進(jìn)行調(diào)整;indir_ahead為前向預(yù)取距離, 由式(2)得出.

代價(jià)模型2: CPU操作和訪存操作的重疊度

基于預(yù)取效益和編譯時(shí)間考慮, 若循環(huán)缺乏足夠的CPU 操作與內(nèi)存操作重疊, 預(yù)取不會(huì)帶來(lái)顯著收益.通過(guò)將插入預(yù)取后循環(huán)預(yù)估指令數(shù)和間接預(yù)取序列內(nèi)存引用總數(shù)的比值與預(yù)設(shè)值的大小比較來(lái)判斷循環(huán)中內(nèi)存引用數(shù)是否合理. 若比值比最小比值預(yù)設(shè)值(PREFETCH_MIN_INDIR_INSN_TO_MEM_RATIO)小則不予預(yù)取, 若出現(xiàn)內(nèi)存引用數(shù)為零或者大于最大內(nèi)存引用預(yù)設(shè)值(PREFETCH_MAX_MEM_INDIR_REFS_PER_LOOP)時(shí), 也不予預(yù)取. 代價(jià)模型如式(4)所示:

其中,INS表示插入預(yù)取后循環(huán)預(yù)估指令數(shù), 對(duì)應(yīng)編譯器變量為indir_ninsns;MEC表示循環(huán)間接預(yù)取序列的內(nèi)存引用總數(shù), 對(duì)應(yīng)編譯器常量為indir_mem_count;PREFETCH_MIN_INDIR_INSNS_TO_MEM_RATIO是間接預(yù)取遍預(yù)設(shè)的比值, 可根據(jù)系統(tǒng)架構(gòu)進(jìn)行設(shè)置.

2.5 預(yù)取生成

在確定了生成預(yù)取的所有關(guān)鍵信息, 并滿(mǎn)足了避免引入內(nèi)存錯(cuò)誤和預(yù)取收益條件后, 接下來(lái)將為間接訪存插入預(yù)取. 在預(yù)取生成階段, 將循環(huán)的gimple語(yǔ)句序列依次插入計(jì)算預(yù)取地址的普通語(yǔ)句, 并將計(jì)算獲得的預(yù)取地址作為預(yù)取內(nèi)建函數(shù)(_builtin_prefetch())的地址參數(shù). 在GCC編譯器后端, 將根據(jù)插入的gimple語(yǔ)句生成普通指令和預(yù)取指令.

首先為索引數(shù)組插入預(yù)取, 先將預(yù)取距離轉(zhuǎn)換為數(shù)組前向字節(jié)數(shù)(算法2第4行). 隨后插入一條加法指令, 將當(dāng)前內(nèi)存引用的地址與前向迭代字節(jié)數(shù)相加得到預(yù)取地址(算法2第5行), 之后將預(yù)取地址作為GCC內(nèi)置預(yù)取函數(shù)(_builtin_prefetch())的地址參數(shù)用于在后端生成一個(gè)預(yù)取指令(算法2第6行).

接下來(lái), 將為間接數(shù)組插入相關(guān)地址計(jì)算指令和發(fā)射預(yù)取. 根據(jù)前述預(yù)取調(diào)度方案, 間接數(shù)組的前向字節(jié)數(shù)為索引數(shù)組預(yù)取的前向字節(jié)數(shù)的一半, 若索引數(shù)組存在常量偏移量也必須考慮在內(nèi)(算法2第7–8行).之后插入一條將歸納變量轉(zhuǎn)換為當(dāng)前字節(jié)數(shù)的乘法指令(算法2第9行), 接著插入一條加法指令將其與前向字節(jié)數(shù)相加, 至此完成了歸納變量增加偏移量的計(jì)算(算法2第10行). 若索引數(shù)組內(nèi)存引用是mem_ref類(lèi)型, 將插入一條三目運(yùn)算指令取歸納變量增加一定偏移量后的值和索引數(shù)組索引下標(biāo)最大值兩者之間的最小值, 使用一個(gè)加法指令將索引數(shù)組基址與上述最小值相加得到當(dāng)前索引數(shù)組地址, 之后根據(jù)該地址創(chuàng)建一個(gè)內(nèi)存引用用于加載索引值(算法2第11–13行).若索引數(shù)組是array_ref類(lèi)型, 則只需將歸納變量增加一定偏移量后的值作為索引數(shù)組新的索引即可加載當(dāng)前索引值(算法2第14行). 如果間接數(shù)組存在常量偏移量, 應(yīng)該使用加法指令將其與加載的索引值相加(算法2第15行). 在獲得加載的索引值后, 將使用一個(gè)乘法指令轉(zhuǎn)換成間接數(shù)組對(duì)應(yīng)的前向字節(jié)數(shù), 一條加法指令將間接數(shù)組基址與轉(zhuǎn)換后的前向字節(jié)數(shù)相加得到間接數(shù)組預(yù)取地址(算法2第16–17行), 最后為間接數(shù)組發(fā)射一條預(yù)取指令(算法2第18行).

算法2. 預(yù)取地址計(jì)算和預(yù)取發(fā)射算法1 foreach(group: groups within a loop):2 foreach(indir_ref: indir_refs within a group):3 if (could emit prefetch for index_ref)//計(jì)算索引內(nèi)存引用前向字節(jié)數(shù)4 offt = index_step * indir_ahead//插入計(jì)算索引預(yù)取地址指令5 addr = insns (&index_ref + offt)6 emit_prefetch (addr) //發(fā)射預(yù)取//為間接內(nèi)存引用發(fā)射預(yù)取7 indir_offt = offt / 2 //間接前向字節(jié)數(shù)//若索引內(nèi)存引用有常量偏移量8 if (index_delta!=null) indir_offt+=index_delta//歸納變量轉(zhuǎn)換前向字節(jié)數(shù)9 indvar_step = insns (indvar*index_step)//計(jì)算歸納變量前向偏移量10 indvar_offt = insns (indir_step+indir_offt)//若索引內(nèi)存引用是mem_ref類(lèi)型11 min_val = insns (indvar_off ＜= indvar_max ? indvar_off :indvar_max)12 index_addr =insns(index_address+min_val)//加載索引內(nèi)存引用數(shù)值13 index_date = insns (*index_addr)//若索引內(nèi)存引用是array_ref 類(lèi)型14 index_date = insns(index_array[indvar_off])//間接內(nèi)存引用存在常量偏移量15 if (indir_delta != null) index_date = insns (index_date +indir_delta)//插入計(jì)算間接內(nèi)存引用前向字節(jié)數(shù)指令16 date_step = insns (index_date * indir_step)//插入計(jì)算間接內(nèi)存引用預(yù)取地址17 indir_addr = insns (indir_address+date_step)18 emit_prefetch (indir_addr) //發(fā)射間接預(yù)取19 endif

3 實(shí)驗(yàn)測(cè)試及分析

本文以SW1621處理器作為測(cè)試間接預(yù)取算法系統(tǒng), 編譯器為SWGCC710, 操作系統(tǒng)為國(guó)產(chǎn)深度Linux系統(tǒng). 采用SPEC2006和NAS并行基準(zhǔn)測(cè)試套件進(jìn)行正確性測(cè)試, 而間接預(yù)取性能評(píng)測(cè)則采用NAS-2.3的IS和CG基準(zhǔn), 以及Graph500 (Seq-CSR). 對(duì)于IS和CG基準(zhǔn)均選取CLASS = C的測(cè)試規(guī)模. 對(duì)于Graph500 (Seq-CSR)則選擇在較小的圖(選項(xiàng)-s10 -e16)和較大的圖(選項(xiàng)-s24 -e16)上運(yùn)行基準(zhǔn)測(cè)試, 測(cè)試其在不同規(guī)模狀態(tài)下的預(yù)取性能. 對(duì)于每一個(gè)基準(zhǔn)程序重復(fù)進(jìn)行5次實(shí)驗(yàn).

3.1 正確性測(cè)試

為了驗(yàn)證集成于SWGCC710編譯器的間接預(yù)取算法的健壯性, 使用SPEC2006測(cè)試集的29道測(cè)試題和NAS的8個(gè)測(cè)試基準(zhǔn)進(jìn)行正確性測(cè)試. 實(shí)驗(yàn)結(jié)果表明, 經(jīng)過(guò)間接預(yù)取優(yōu)化的測(cè)試集均能通過(guò)正確性測(cè)試,沒(méi)有出現(xiàn)編譯和執(zhí)行錯(cuò)誤.

3.2 性能測(cè)試

采用NAS-2.3的IS和CG基準(zhǔn)以及Graph500(Seq-CSR)進(jìn)行性能測(cè)試分析. 實(shí)驗(yàn)結(jié)果表明, 與編譯選項(xiàng)為-O2 -static時(shí)的程序性能相比, 間接預(yù)取優(yōu)化遍顯著提高了每個(gè)應(yīng)用程序的性能. 測(cè)試結(jié)果如圖3所示.

圖3 間接預(yù)取優(yōu)化遍性能加速比

對(duì)于擁有較為簡(jiǎn)單的跨步間接訪存模式IS和CG,分別具有17.23%和26.28%的性能提升. 而對(duì)于較為復(fù)雜的Graph500 (Seq-CSR), 在較小圖中(選項(xiàng)為 -s16 -e)性能提升高達(dá)18.65%, 而在較大圖(選項(xiàng)為 -s24 -e16)也有3.56%的性能提升.

在測(cè)試時(shí)發(fā)現(xiàn), 當(dāng)對(duì)CG基準(zhǔn)以 CLASS=B 規(guī)模測(cè)試時(shí), 間接預(yù)取并未產(chǎn)生任何加速效果, 反而降低了程序性能. 而以CLASS=C規(guī)模進(jìn)行測(cè)試時(shí), 間接預(yù)取表現(xiàn)出了可觀的性能收益, 說(shuō)明程序的間接存儲(chǔ)器訪問(wèn)數(shù)據(jù)集規(guī)模對(duì)預(yù)取性能具有重要影響. 然而IS基準(zhǔn)卻表現(xiàn)出完全相反的結(jié)果, 當(dāng)IS以CLASS=B規(guī)模進(jìn)行測(cè)試具有195%的加速比, 而以CLASS=C規(guī)模測(cè)試時(shí)卻僅有117%的加速比, 說(shuō)明即使具有更大的數(shù)據(jù)集規(guī)模, 微體系架構(gòu)的特性也會(huì)影響間接預(yù)取性能. 對(duì)于Graph500 (Seq-CSR)而言, 由于復(fù)雜的控制流分析, 自動(dòng)預(yù)取遍無(wú)法對(duì)外層循環(huán)的邊緣列表(最大的數(shù)據(jù)結(jié)構(gòu))進(jìn)行預(yù)取, 僅可以在最內(nèi)層循環(huán)中插入預(yù)取. 在-s24-e16規(guī)下同時(shí)增加對(duì)外層循環(huán)的手工預(yù)取時(shí), 加速比可以提高至4.27%, 因此應(yīng)用程序自身特點(diǎn)也會(huì)影響間接預(yù)取性能.

(1) 預(yù)取指令開(kāi)銷(xiāo). 預(yù)取間接訪存的另外一個(gè)比較突出的問(wèn)題是指令開(kāi)銷(xiāo). 圖4顯示了在SW1621上每個(gè)基準(zhǔn)在僅隔離包含間接內(nèi)存引用的循環(huán)體的動(dòng)態(tài)指令計(jì)數(shù)增加情況. 通過(guò)添加軟件預(yù)取, 循環(huán)體動(dòng)態(tài)指令計(jì)數(shù)顯著增加, 其中IS增加最多, 高達(dá)115%, 而Graph500(Seq-CSR)也增加了51%, CG增加的較少, 但也達(dá)到了32%. 通過(guò)圖4可以看出, 插入預(yù)取帶來(lái)的指令開(kāi)銷(xiāo)很大, 動(dòng)態(tài)指令計(jì)數(shù)顯著增加. 對(duì)于某些程序, 增加的指令開(kāi)銷(xiāo)將超過(guò)減少緩存未命中所帶來(lái)的好處, 因此在預(yù)取距離計(jì)算和預(yù)取代價(jià)分析中均需要預(yù)估指令開(kāi)銷(xiāo)的執(zhí)行時(shí)間.

圖4 添加軟件預(yù)取后, SW1621的動(dòng)態(tài)指令計(jì)數(shù)增加百分比

(2) 前向預(yù)取距離. 為了驗(yàn)證算法的預(yù)取距離計(jì)算方法的高效性, 將最好的手工設(shè)定的預(yù)取距離與自動(dòng)預(yù)取計(jì)算的距離相比較. 圖5給出了每個(gè)基準(zhǔn)相對(duì)變化的前向預(yù)取距離的加速比, 表明對(duì)于每個(gè)基準(zhǔn)前向預(yù)取距離可以是一個(gè)比較大區(qū)間中任何一個(gè)數(shù)值, 并且不同基準(zhǔn)預(yù)取距離卻具有一致性. 傳統(tǒng)的間接預(yù)取距離設(shè)置方法就是根據(jù)不同基準(zhǔn)測(cè)試結(jié)構(gòu)設(shè)置的一個(gè)固定值, 在SW621處理器平臺(tái)選取offset=16時(shí), 每一個(gè)基準(zhǔn)都可以獲得較好的性能收益. 實(shí)際上, 通常最佳預(yù)取距離是存儲(chǔ)器等待時(shí)間除以每次循環(huán)迭代的時(shí)間[14].由于每個(gè)基準(zhǔn)程序自身特點(diǎn)不同, 循環(huán)指令數(shù)不同, 因插入預(yù)取增加的指令數(shù)開(kāi)銷(xiāo)也不同, 最佳預(yù)取距離并不相同, 而傳統(tǒng)手工設(shè)定方式忽略了不同程序的特性.算法提出的預(yù)取距離計(jì)算方法同時(shí)考慮到因預(yù)取插入帶來(lái)的指令開(kāi)銷(xiāo)和程序特點(diǎn), 可以計(jì)算出每個(gè)程序最接近最佳預(yù)取距離的數(shù)值. 圖6給出了自動(dòng)算法對(duì)每個(gè)基準(zhǔn)的性能改進(jìn), 以及手工設(shè)定offset=16 時(shí)每個(gè)基準(zhǔn)的預(yù)取性能. 測(cè)試結(jié)果表明, 本文提出的預(yù)取距離計(jì)算方法比手工設(shè)定可以獲得更高的性能收益.

圖5 變化的前向預(yù)取距離加速比

圖6 自動(dòng)預(yù)取和最好的手工設(shè)定offset=16 的預(yù)取性能

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

為了解決申威GCC編譯器中缺乏間接預(yù)取自動(dòng)化方法的問(wèn)題, 本文設(shè)計(jì)并開(kāi)發(fā)了一個(gè)完整的編譯器遍來(lái)識(shí)別適合預(yù)取的間接訪存模式, 并插入必要的代碼計(jì)算預(yù)取地址和發(fā)射預(yù)取. 對(duì)簡(jiǎn)單跨步-間接存儲(chǔ)器訪問(wèn)模式插入合適的預(yù)取, 提高了SW1621處理器對(duì)間接訪問(wèn)的高速緩存命中率, 顯著提高了SW621訪存性能.

對(duì)于一些比較復(fù)雜的循環(huán), 其中可能包含多個(gè)簡(jiǎn)單跨步-間接訪存模式, 它們具有相同的間接數(shù)組, 同時(shí)索引數(shù)組數(shù)據(jù)在同一個(gè)緩存行中(例如, B[A[i]]和B[A[i+2]]). 根據(jù)間接預(yù)取調(diào)度方案, 需要對(duì)索引數(shù)組和間接數(shù)組都進(jìn)行預(yù)取, 當(dāng)對(duì)其中一個(gè)索引數(shù)組(A[i])發(fā)射預(yù)取時(shí), 也會(huì)將另外一個(gè)索引數(shù)組(A[i+2])數(shù)據(jù)加載至緩存, 如果繼續(xù)對(duì)索引數(shù)組A[i+2]重復(fù)發(fā)射預(yù)取, 不僅會(huì)增加間接預(yù)取開(kāi)銷(xiāo), 也會(huì)將其他有用數(shù)據(jù)替換出緩存, 顯著降低間接預(yù)取的性能收益. 在后續(xù)工作中需要就上述問(wèn)題考慮進(jìn)行重用分析, 避免出現(xiàn)重復(fù)預(yù)取.