余龍龍, 韓 林

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

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

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

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

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

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

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

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

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

1 間接預取可行性分析

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

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

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

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

代碼清單2. 間接預取序列調(diào)度for ( 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ù)組預取

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

圖1 間接預取算法總體框架

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

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

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

算法1. 間接訪存模式識別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)存儲內(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é)點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 }

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

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

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

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

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

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

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

2.2 預取錯誤避免

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

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

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

2.3 預取距離計算

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

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

2.4 預取代價評估

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

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

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

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

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

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

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

2.5 預取生成

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

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

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

算法2. 預取地址計算和預取發(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)//計算索引內(nèi)存引用前向字節(jié)數(shù)4 offt = index_step * indir_ahead//插入計算索引預取地址指令5 addr = insns (&index_ref + offt)6 emit_prefetch (addr) //發(fā)射預取//為間接內(nèi)存引用發(fā)射預取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)//計算歸納變量前向偏移量10 indvar_offt = insns (indir_step+indir_offt)//若索引內(nèi)存引用是mem_ref類型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 類型14 index_date = insns(index_array[indvar_off])//間接內(nèi)存引用存在常量偏移量15 if (indir_delta != null) index_date = insns (index_date +indir_delta)//插入計算間接內(nèi)存引用前向字節(jié)數(shù)指令16 date_step = insns (index_date * indir_step)//插入計算間接內(nèi)存引用預取地址17 indir_addr = insns (indir_address+date_step)18 emit_prefetch (indir_addr) //發(fā)射間接預取19 endif

3 實驗測試及分析

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

3.1 正確性測試

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

3.2 性能測試

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

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

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

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

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

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

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

圖5 變化的前向預取距離加速比

圖6 自動預取和最好的手工設定offset=16 的預取性能

4 結(jié)束語

為了解決申威GCC編譯器中缺乏間接預取自動化方法的問題, 本文設計并開發(fā)了一個完整的編譯器遍來識別適合預取的間接訪存模式, 并插入必要的代碼計算預取地址和發(fā)射預取. 對簡單跨步-間接存儲器訪問模式插入合適的預取, 提高了SW1621處理器對間接訪問的高速緩存命中率, 顯著提高了SW621訪存性能.

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