基于緩存行為特征的線程數據預取距離控制策略

黃 艷 張啟坤 段趙磊 古志民

1 引言

隨著片上多核處理器技術的快速發(fā)展，阻礙多核系統(tǒng)性能提升的“存儲墻”問題進一步突顯。目前，線程數據預取技術是隱藏存儲器訪問延遲、提高多核系統(tǒng)性能的有效手段。

預取距離指數據預取技術中發(fā)出預取請求到預取數據被使用之間的執(zhí)行間隔。預取距離的大小直接決定了預取的有效性。一方面，為了讓預取數據在被使用前到達以便完全隱藏該數據的緩存失效延遲，預取距離應該足夠大[1]；另一方面，為了避免預取數據到達的太早造成緩存污染，預取距離又不能過大[2]。

近年來，不少研究者[316]-利用幫助線程數據預取隱藏應用程序中長延遲取數指令的訪存延遲，其中多數采用特殊的線程間同步機制來控制預取距離。文獻[3]在程序執(zhí)行過程中使用特殊的硬件預測表預測最優(yōu)預取距離；文獻[4]通過關聯表評估連續(xù)兩次緩存失效事件的時間間隔，在一定預取距離范圍內盡早發(fā)出預取請求；文獻[5]通過編譯器分析設置特定的采樣間隔，主線程在每個采樣間隔觸發(fā)一個幫助線程；文獻[6]通過預解碼（decode）檢測到長延遲取數指令時觸發(fā)幫助線程；文獻[7]中幫助線程通過一個循環(huán)計數器與主線程進行同步；文獻[8]使用信號量同步機制控制幫助線程的預取距離；文獻[9]通過增量改變預取距離的值找到較優(yōu)預取距離；文獻[10]在檢測到規(guī)律的只讀缺失模式時進行數據預取。當面向非規(guī)則數據密集應用時，由于非規(guī)則數據訪問間的相互依賴關系，這些方法難以實現對預取距離的有效控制，預取時效性難以得到保證。

本文提出一種基于緩存行為特征的有效預取距離控制策略。該方法的核心思想是：首先分析和預測熱點循環(huán)數據訪問的緩存行為特征；然后，根據應用程序熱點循環(huán)的緩存行為特征選取最大有效預取距離；最后，在預測的有效預取距離取值范圍內通過實驗測試選擇較優(yōu)預取距離取值。通過該策略控制線程數據預取距離能進一步提高線程預取性能。

2 面向共享緩存的間隔預取策略（Skip-Pre fetching, SP）

指針應用程序中的熱點數據通常可以分為循環(huán)依賴數據和非循環(huán)依賴數據。在 SP線程預取機制中，幫助線程通過忽略對部分非循環(huán)依賴數據的預取控制線程預取距離和平衡主線程與幫助線程。SP的基本思想：如果在幫助線程與主線程的并行執(zhí)行過程中，幫助線程的預取操作能與主線程的訪存操作或計算操作完全并行地執(zhí)行，互不干擾，且?guī)椭€程預取的數據都恰好被主線程需要，則主線程將獲得最大的性能收益。理論上，當幫助線程的執(zhí)行延遲占熱點循環(huán)執(zhí)行總延遲的一半時，幫助線程與主線程達到最大程度的并行執(zhí)行，主線程的性能得到最大限度地提高。圖1抽象地說明了這種理想狀況下的程序執(zhí)行流程。依據圖1 （a）所示，源程序熱點循環(huán)的單次循環(huán)延遲為（TFM＋TSM＋TC）。根據圖1（b），應用線程預取機制后，通過合理地設置A_SKI與A_PRE的值（A_SKI即是預取距離），幫助線程的性能收益最大化時主程序熱點循環(huán)的單次循環(huán)延遲減少至原來的一半，即（TFM＋TSM＋TC）/2。

圖1 理想狀態(tài)下的線程預取

我們已有的研究結果表明，可以根據TFM，TSM和 TC三者間的關系確定 A_SKI與 A_PRE的關系。本文的研究工作即是在A_SKI與A_PRE關系確定的基礎上，通過分析應用程序熱點數據的緩存行為特征，確定預取距離 A_SKI的有效取值范圍并通過實驗選擇較優(yōu)的預取距離取值。

圖1中，TFM對應于單次熱點循環(huán)中循環(huán)依賴數據的平均訪存延遲；TSM對應于單次熱點循環(huán)中非循環(huán)依賴數據的平均訪存延遲；TC對應于單次熱點循環(huán)中的平均計算延遲；A_SKI（預取距離）指幫助線程在執(zhí)行熱點循環(huán)時，不預取非循環(huán)依賴數據時連續(xù)執(zhí)行的循環(huán)次數；A_PRE（預取長度）指幫助線程在執(zhí)行熱點循環(huán)時，預取非循環(huán)依賴數據時連續(xù)執(zhí)行的熱點循環(huán)次數。

3 基于緩存行為特征的線程預取距離控制策略

3.1 緩存行為特征分析

數據預取引發(fā)緩存污染的可能性與應用程序的訪存特征及共享緩存的映射機制密切相關。對于片上多處理器中普遍使用的多路組相聯共享緩存來說，執(zhí)行幫助線程數據預取時，如果一個應用程序的熱點訪問數據都集中映射到共享緩存的同一個緩存組中，則很容易引起緩存污染；反之，如果一個應用程序的熱點循環(huán)訪問數據極少映射到共享緩存的相同緩存組中，則不容易引起緩存污染。因此，通過分析應用程序熱點數據訪問流，識別出當映射到同一個共享緩存組中的緩存行超過共享緩存的組相聯度時的熱點循環(huán)次數，可以預測在執(zhí)行數據預取時熱點循環(huán)何時會發(fā)生緩存污染。

這里把識別出的此特征定義為熱點循環(huán)對應于共享緩存組的緩存相關度，并分析此特征與 SP預取策略中預取距離 A_SKI取值的關系。特別地，對本文中選擇的實驗平臺Intel Core 2 Quad 6600處理器，其共享緩存的組相聯度是16。

定義 1 緩存相關度SA（L, Sx）： 假設對于CMP結構中共享緩存（最低級）的組相聯度是C, Sx是該共享緩存中的某一個緩存組，包含C個緩存塊（B1, B2,…,BC）。對于訪存密集型程序中的熱點循環(huán)L，其循環(huán)次數是I。共享緩存采用的是LRU替換算法。假設在 L執(zhí)行到第 j（j＜I）次循環(huán)時，恰好 L中有C個數據塊映射到Sx中的C個緩存塊中。這里定義j為L對應于Sx的緩存相關度，記為SA（L,Sx）= j。圖2進一步解釋了緩存相關度的定義。

圖 2 緩存相關度SA（L, Sx）=j 時的情況

熱點循環(huán)對應于共享緩存組 Sx的緩存相關度表明熱點循環(huán)訪問數據間的緩存相關性。例如，對于某個熱點循環(huán)，其對應于共享緩存中緩存組Sx的緩存相關度為40，表明在應用程序獨立運行時，當熱點循環(huán)執(zhí)行到第40次循環(huán)時，共享緩存組Sx中的熱點循環(huán)訪問數據塊已經達到飽和。當再有熱點循環(huán)訪問數據塊到達此緩存組時，將要進行緩存替換。

定理1 假設熱點循環(huán)L對應于共享緩存組Sx,SA（L, Sx）=j。應用SP預取機制后，當A_SKI +A_PRE ＞j時，幫助線程造成共享緩存污染的可能性增大。

證明 設 A_SKI+ A_PRE=R，圖 3（a）說明了A_SKI+A_PREj≤時Sx的數據駐入情況。如圖3（a）所示，A_SKI+A_PREj≤時，在主線程執(zhí)行A_SKI次循環(huán)，同時幫助線程執(zhí)行A_PRE次循環(huán)后，L的訪問數據只占據Sx緩存組中C個緩存塊的一部分。當熱點循環(huán) L的訪問數據占用了 Sx緩存組中的全部C個緩存塊時，主線程早已執(zhí)行過第R次循環(huán)，此時幫助線程預取的數據也已被主線程訪問過，因此，除非數據被重復訪問，否則，新駐入的數據替換掉的都是無用數據，不存在緩存污染。

圖3（b）分析了A_SKI + A_PRE＞j時 Sx的數據駐入情況。如圖 3（b）所示，在主線程執(zhí)行 N（N＜A_SKI）次循環(huán)，同時幫助線程執(zhí)行第 M（A_SKI＜M＜R）次循環(huán)時，熱點循環(huán)L的訪問數據已經占用了Sx緩存組中全部的C個緩存塊。所以當L繼續(xù)執(zhí)行時，主線程將執(zhí)行第N+1次循環(huán)，而幫助線程將執(zhí)行第M+1次循環(huán)。此時主線程或幫助線程新駐入的訪問數據將替換掉Sx緩存組中存儲的數據，如果替換掉的數據是幫助線程最近駐入的訪問數據，因這些數據還沒有被主線程訪問，從而造成緩存組Sx被污染。因此，當A_SKI+A_PRE＞j時幫助線程造成共享緩存污染的可能性增大。 證畢

定理2 假設熱點循環(huán)L對應于共享緩存組Sx,SA（L,Sx）=j。應用 SP 預取機制時，當預取距離A_SKI＜j/2時，幫助線程造成共享緩存污染的可能性比A_SKI ＞j/2小。

圖 3 基于緩存相關度和預取距離的緩存污染分析

證明 （1）當 A_SKI≤ A _PRE時，因A_SKI≤A_PRE，如果 A_SKI＞j/2，則 A_SKI+A_PRE＞j。根據圖 3和定理 1的證明過程，應用SP預取機制后，A_SKI+A_PRE＞j時，幫助線程造成共享緩存污染的可能性增大。因此，A_SKI≤ A _PRE時，預取距離A_SKI＜j/2時，幫助線程造成共享緩存污染的可能性比A_SKI ＞j/2小。

（2）當 A_SKI＞A_PRE 時，因 A_SKI＞A_PRE，如果 A_SKI ＜j/2，則 A_SKI + A_PRE ＜j。根據圖3和定理1的證明過程，應用SP預取機制后，A_SKI+A_PRE ＜j時，幫助線程造成共享緩存污染的可能性比A_SKI+A_PRE＞j時小。因此，A_SKI＞A_PRE時，預取距離A_SKI＜j/2時，幫助線程造成共享緩存污染的可能性比 A_SKI＞j/2小。 證畢

3.2 基于緩存行為特征的預取距離控制模型

預取距離的度量方式有多種，例如，預取指令與對應取數指令執(zhí)行時間隔的CPU時鐘周期數、分支語句數、指令數、緩存失效事件數等都可以作為預取距離的度量標準[17]。SP預取機制中，幫助線程在每個循環(huán)中進行預取操作時都跳過 A_SKI次內層循環(huán)，也就意味著幫助線程提前 A_SKI次循環(huán)發(fā)出預取請求。因此，SP中預取距離A_SKI就是指從發(fā)出預取請求到預取數據被使用時間隔的熱點循環(huán)次數。

3.2.1 基于緩存相關度的最大有效預取距離取值 定理2表明，本文在應用SP預取機制時，應設置預取距離 A_SKI＜SA（L, Sx）/2，即 A_SKI＜j/2，以便減少幫助線程引起的緩存污染。因此，為了減少整個共享緩存被污染的可能性，SP的預取距離A_SKI與熱點循環(huán)L對應于共享緩存組Sx的緩存相關度應該具有關系為

3.2.2 最小有效預取距離取值 在SP預取策略中為了保證數據預取的及時性，可以使用式（2）求得 SP預取的最小有效預取距離取值[18]：

這里平均訪存延遲指的是源測試程序中單次熱點循環(huán)的平均訪存延遲；而平均迭代延遲指的是應用SP預取機制后，單次熱點循環(huán)的平均執(zhí)行延遲。在SP預取策略中，根據圖1，平均訪存延遲=TFM+TSM，理想情況下的平均迭代延遲=（TFM+TSM+TC）/2。則

特別地，當TC相比于（TFM+TSM）可以忽略不計時，有效預取距離A_SKI最小為2次熱點循環(huán)；當TC大于（TFM+TSM），有效預取距離A_SKI最小為0次熱點循環(huán)。

式（1）與式（3）為設置 SP 預取距離 A_SKI提供了直接依據。例如，熱點循環(huán)對應于各共享緩存組的緩存相關度最小為 40，且 TC大于（TFM+TSM），為減少共享緩存污染和提高預取時效性，最大預取距離取值應該設置為20，最小預取距離為0次熱點循環(huán)，SP預取距離A_SKI的較優(yōu)取值應在0與20之間搜索。

4 實驗結果與分析

為了得到 A_SKI預取距離的較優(yōu)取值，先分析應用程序熱點循環(huán)對應于共享緩存組的緩存相關度分布，并在此基礎上預測 A_SKI預取的有效預取距離取值范圍；然后，通過實驗測試結果確定SP對特定測試程序的較優(yōu)預取距離 A_SKI取值；最后，為幾個非規(guī)則數據密集應用實現了 SP預取機制和傳統(tǒng)幫助線程數據預取機制，并通過對實驗結果的比較分析，評估SP預取策略的性能和有效性。

4.1 實驗背景

本文采用Intel Core 2 Quad 6600處理器作為實驗平臺評估 SP預取策略對非規(guī)則數據密集應用的性能影響。該處理器上有兩個L2 硬件預取裝置，ACL與DPL[19]，每個處理器上的兩個核動態(tài)共享這兩個硬件預取裝置。共享緩存的大小為 4 MB，組相聯度是16。

從基準測試程序包SPEC2006和Olden中選擇EM3D, MCF和MST作為測試對象。所有的測試程序都使用GCC 4.3編譯器進行編譯，編譯選項為“-O2”。表1中顯示了這些測試程序的基本信息，包括輸入參數、熱點函數等信息。為了分析熱點循環(huán)訪問數據的緩存相關度，表1中最后一列顯示了各測試程序的熱點循環(huán)的循環(huán)次數。如果此項數據是個具體數值，說明對熱點函數的每次調用，外層循環(huán)次數始終是該數值。如果此項數據是一個數值區(qū)間，說明對熱點函數的不同次調用，外層循環(huán)次數在此區(qū)間內變化。

表1 熱點循環(huán)的循環(huán)次數

4.2 基于緩存相關度的SP有效預取距離取值結果

表2是各測試程序基于緩存相關度的SP有效預取距離取值結果。值得一提的是，本文中各程序的有效預取距離取值范圍只是一個比較粗略的界限，旨在為我們選擇較優(yōu)預取距離取值提供指導作用。

4.3 SP的有效預取距離取值分析

為了檢測硬件預取對有效預取距離取值范圍的影響[20]，在兩種硬件預取配置下測試EM3D, MCF和MST 3個測試程序在預取距離取值范圍內的性能變化。這兩種硬件預取配置情況描述如下：

PF_ON：指DPL和ACL都是打開狀態(tài)。PF_OFF：指DPL和ACL都是關閉狀態(tài)。

圖4 中顯示的是在PF_ON和PF_OFF兩種配置下，相對于源程序，SP預取程序的執(zhí)行時間、主線程 L2 緩存失效次數、幫助線程 L2 緩存失效次數、主線程訪存次數和幫助線程訪存次數的規(guī)范化數值。

比較圖4（a）中PF_ON和PF_OFF兩種配置下的結果表明，L2硬件預取對EM3D的SP預取程序性能產生了明顯影響，但總的來說，隨著預取距離的不斷增大，程序性能逐漸降低。這一方面說明L2硬件預取增加了緩存污染的嚴重性，另一方面說明隨著預取距離的不斷增大，緩存污染的嚴重性也不斷增加。

表2 SP預取距離參數的取值范圍

圖4 預取距離對SP預取的性能影響

圖 4（b）中的結果顯示，當預取距離參數取值逐漸變大時，MCF的SP預取程序中，除L2 緩存失效次數外，其它各性能參數的變化趨勢均相同。而在PF_OFF配置下，各性能參數的變化均不明顯。這表明當關閉L2硬件預取時，MCF的SP預取程序性能對預取距離的變化不敏感。

圖 4（c）顯示的是，當預取距離參數取值逐漸變大時，MST的SP預取程序性能變化情況。從圖4（c）顯示的結果可以看出，在PF_ON和PF_OFF兩種配置下，都是在預取距離為 25時，MST的 SP預取程序性能發(fā)生了大的變化；當預取距離小于25時，各性能參數有緩慢減少的趨勢；當預取距離大于30時，程序的執(zhí)行時間，主線程的L2 緩存失效次數和訪存次數均有逐漸增長的趨勢，而幫助線程的 L2 緩存失效次數和訪存次數均有逐漸減小的趨勢。

總之，根據圖4中的顯示結果，可以得到如下結論。首先，程序執(zhí)行時間總是與其訪存次數有相同的變化趨勢，說明訪存次數是衡量程序性能的一個重要指標。其次，程序執(zhí)行時間與其 L2 緩存失效次數的變化趨勢不總是相同，表明 L2 緩存失效次數不能作為衡量程序性能的唯一指標。最后，當預取距離高于預測范圍內的某一數值時，程序的性能開始逐漸下降。這說明當預取時效性得到保證后，更大的預取距離導致更嚴重的緩存污染。

4.4 SP的性能優(yōu)勢

為了有效分析傳統(tǒng)線程預取的局限性，作者實現了兩種傳統(tǒng)線程預取技術。其中，提前式線程預?。ˋhead Prefetching, AP）是在文獻[6]中所描述的線程預取技術的基礎上實現的。能動式線程數據預取方法（Active threaded Prefetching, PV）是在文獻[8]中所描述的線程預取技術的基礎上實現的。

圖5和圖6顯示了AP, PV和SP對測試程序的性能影響。總體來看，SP為這幾個測試程序平均取得了約13 %的加速比，AP平均取得了約4.4 %的加速比，PV平均取得了約5.3 %的加速比。這說明本文提出的 SP預取策略比傳統(tǒng)幫助線程數據預取方法的平均性能好。尤其值得注意的是，對于測試程序MST, SP取得了27.1 %的性能提高，而AP和PV下卻都遭受到近2%的性能降低。圖6中顯示的規(guī)范化 CPI數值（相對于源程序）進一步說明了 SP預取策略相對于傳統(tǒng)幫助線程數據預取方法的優(yōu)勢。因此，實驗結果表明，通過該策略控制線程數據預取距離能進一步提高線程預取性能。

5 結束語

在 SP線程預取機制基礎上，通過分析應用程序熱點循環(huán)執(zhí)行的延遲特征和緩存行為特征評估有效的 SP預取距離取值范圍，并在該范圍內通過實驗測試為特定的非規(guī)則數據密集應用程序選擇合適的 SP預取距離。通過實驗結果我們可以看出，合適的SP預取距離取值不僅提高了SP預取機制的預取效率，減小了幫助線程引發(fā)緩存污染的可能性，還減少了系統(tǒng)總線壓力和共享資源競爭，進而優(yōu)化了SP預取性能。

圖 5 加速比

圖 6 CPI變化

[1] Chen T F and Baer J L. A performance study of software and hardware data prefetching schemes[C]. Proceedings of 21st International Symposium on Computer Architecture,Chicago, USA, 1994: 223-232.

[2] Saavedra R H and Daeyeon P. Improving the effectiveness of software prefetching with adaptive execution[C]. Proceedings of Conference on Parallel Architectures and Compilation Techniques, Boston, USA, 1996: 68-78.

[3] Hur I and Lin C. Feedback mechanisms for improving probabilistic memory prefetching[C]. Proceedings of 15th International Symposium on High Performance Computer Architecture, North Carolina, USA, 2009: 443-454.

[4] Dongkeun K, Liao S S W, Wang P H, et al.. Physical experimentation with prefetching helper threads on Intel,s hyper-threaded processors[C]. Proceedings of International Symposium on Code Generation and Optimization,California, USA, 2004: 27-38.

[5] Lu J. Design and implementation of a lightweight runtime optimization system on modern computer architectures[D].[Ph.D. dissertation], University of Minnesota, 2006.

[6] Ro W W and Gaudiot J L. Speculative pre-execution assisted by compiler （SPEAR）[J]. Journal of Parallel and Distributed Computing, 2006, 66（8）: 1076-1089.

[7] Somogyi S, Wenisch T F, Ailamaki A, et al.. Spatial-temporal memory streaming[C]. Proceedings of the 36th International Symposium on Computer Architecture, Austin, USA, 2009:69-80.

[8] Lee J, Jung C, Lim D, et al.. Prefetching with helper threads for loosely coupled multiprocessor systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2009,20（9）: 1309-1324.

[9] 單書暢, 胡瑜, 李曉維. 基于數據預取的多核處理器末級緩存優(yōu)化方法[J]. 計算機輔助設計與圖形學學報, 2012, 24（9）:1241-1248.Shan Shu-chang, Hu Yu, and Li Xiao-wei. Date prefetching based last-level cache optimization for chip multiprocessors[J]. Journal of Computer-Aided Design & Computer Graphics,2012, 24（9）: 1241-1248.

[10] 張建勛, 古志民, 胡瀟涵, 等. 面向非規(guī)則大數據分析應用的多核幫助線程預取方法[J]. 通信學報, 2014, 35（8）: 137-146.Zhang Jian-xun, Gu Zhi-min, Hu Xiao-han, et al.. Multi-core helper thread prefetching forirregular data intensive applications[J]. Journal on Communications, 2014, 35（8）:137-146.

[11] Marin G, McCurdy C, and Vetter J S. Diagnosis and optimization of application prefetching performance[C].Proceedings of the 27th International ACM Conference on International Conference on Supercomputing, Oregon, USA,2013: 303-312.

[12] Garside J and Audsley N C. Prefetching across a shared memory tree within a network-on-chip architecture[C].Proceedings of 15th International Symposium on System-on-Chip, Melbourne, Australia, 2013: 1-4.

[13] Jain A and Lin C. Linearizing irregular memory accesses for improved correlated prefetching[C]. Proceedings of the 46th IEEE/ACM International Symposium on Microarchitecture（MICRO）, Davis, USA, 2013: 247-259.

[14] Zhao Y, Yoshigoe K J, and Xie M J. Pre-execution data prefetching with I/O scheduling[J]. The Journal of Supercomputing, 2014, 68（2）: 733-752.

[15] 巫旭敏, 殷保群, 黃靜, 等. 流媒體服務系統(tǒng)中一種基于數據預取的緩存策略[J]. 電子與信息學報, 2010, 32（10）:2440-2445.Wu Xu-min, Yin Bao-qun, Huang Jing, et al.. A prefetchingbased caching policy in streaming service systems[J]. Journal of Electronics & Information Technology, 2010, 32（10）:2440-2445.

[16] 劉斌, 趙銀亮, 韓博, 等. 基于性能預測的推測多線程循環(huán)選擇方法[J]. 電子與信息學報, 2014, 36（11）: 2768-2774.Liu Bin, Zhao Yin-liang, Han Bo, et al.. A loop selection approach based on performance prediction for speculative multithreading[J]. Journal of Electronics & Information Technology, 2014, 36（11）: 2768-2774.

[17] Emma P G, Hartstein A, Puzak T R, et al.. Exploring the limits of prefetching[J]. IBM Journal of Research and Development, 2005, 49（1）: 127-144.

[18] Srinath S, Mutlu O, Hyesoon K, et al.. Feedback directed prefetching: improving the performance and bandwidthefficiency of hardware prefetchers[C]. Proceedings of the IEEE 13th International Symposium on High Performance Computer Architecture, Arizona, USA, 2007: 63-74.

[19] Doweck J. White paper: inside intel core microarchitecture and smart memory access[R]. Intel Corporation, 2006.

[20] Hui K and Jennifer L W. To hardware prefetch or not to prefetch?: a virtualized environment study and core binding approach[C]. Proceedings the 8th International Conference on Architectural Support For Programming Languages And Operating Systems, Houston, USA, 2013: 357-368.