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

余龍龍, 韓 林

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

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

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

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

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

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

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

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

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

1 間接預取可行性分析

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

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

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

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

代碼清單2. 間接預取序列調度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 循環間接數組預取

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

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

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

2.1 間接內存引用信息收集

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

算法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 = {}//獲取內存引用索引的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}//數據結構存儲內存引用信息8 indir_refs U= prefetch 9 DFS (index_stmt, loop) {10 candidate = {}//間接內存引用存在常量偏移量

11 foreach (op: src_operand of index_stmt)://獲取操作數op的def-stmt 12 op_stmt = get_def_stmt(op)//op_stmt包含內存引用13 if (op_stmt contain a memor reference)14 candidate U= {(index_ref, info, {infos})}//獲取索引內存引用的索引15 index = get_index (index_ref)//若index可以遞歸鏈表示16 if (SCEV (loop, index))17 candidate U={(index, {index_ref, infos}//op_stmt不含有內存引用, 繼續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})}//選擇最接近索引內存引用的歸納變量21 indvar = closest_loop_indvar ()//不允許非歸納變量phi節點22 remove (candidate, contains non-induction phi)//不允許包含函數調用23 remove(candidate, contains function call)//內存引用基址不可尋址24 remove (candidate, base_addr not addressable)25 }

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

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

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

表1 內存引用地址計算公式

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

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

圖2 描述間接內存引用的結構體

2.2 預取錯誤避免

雖然預取本身不會造成錯誤, 但用于間接預取地址計算的中間加載可能會導致錯誤. 若循環體中存在對索引數組的寫數據結構, 可能會預取無效的數據. 更嚴重的是在對索引數組的解引用期間可能會產生非法的加載地址, 與預取操作不同, 加載指令在非法的地址上會發生內存異常, 導致程序崩潰.

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

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

2.3 預取距離計算

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

其中,n是間接預取序列中的總的內存引用數, 對應編譯器常量為indir_mem_count, 若循環只有一個簡單跨步-間接訪存, 則n=2.L是與后端體系結構相關的訪存延遲,indir_time是插入預取之后預估的循環體指令執行時間.

2.4 預取代價評估

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

代價模型1: 循環迭代次數

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

其中,LC表示預估的循環跳脫計數, 在間接預取遍中對應變量為loop_niter;TRIP_COUNT_TO_INDIR_AHEAD_RATIO是預設的比值, 可以根據系統架構進行調整;indir_ahead為前向預取距離, 由式(2)得出.

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

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

其中,INS表示插入預取后循環預估指令數, 對應編譯器變量為indir_ninsns;MEC表示循環間接預取序列的內存引用總數, 對應編譯器常量為indir_mem_count;PREFETCH_MIN_INDIR_INSNS_TO_MEM_RATIO是間接預取遍預設的比值, 可根據系統架構進行設置.

2.5 預取生成

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

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

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

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

3 實驗測試及分析

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

3.1 正確性測試

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

3.2 性能測試

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

圖3 間接預取優化遍性能加速比

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

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

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

圖4 添加軟件預取后, SW1621的動態指令計數增加百分比

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

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

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

4 結束語

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

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