幫助線程預取質量的實時在線評價方法

張建勛，古志民

(1.天津職業技術師范大學 信息技術工程學院，天津 300222； 2.北京理工大學 計算機學院，北京 100081)

(*通信作者電子郵箱zhangjx@tute.edu.cn)

幫助線程預取質量的實時在線評價方法

張建勛1*，古志民2

(1.天津職業技術師范大學 信息技術工程學院，天津 300222； 2.北京理工大學 計算機學院，北京 100081)

(*通信作者電子郵箱zhangjx@tute.edu.cn)

針對傳統靜態枚舉設置幫助線程控制參數值的繁雜耗時問題，提出了一種幫助線程預取質量的實時在線評價方法。首先，明確了幫助線程的預取服務質量(QoS)的目標；其次，分析了幫助線程預取性能評價的動態指標，對幫助線程預取QoS進行了建模分析；最后，提出一個幫助線程預取的動態自適應調節算法，算法根據程序的階段行為變化和動態預取獲益變化等信息來判斷參數值的適用度以及是否需要進行反饋優化，從而實現對預取控制的自適應調節。實驗結果表明，應用自適應預取評價算法之后，Mst熱點模塊的性能提升加速比為1.496，所提出的自適應預取評價方法能夠根據程序的動態階段行為對幫助線程控制參數值作出自適應控制和調節。

幫助線程；預取質量；評價方法；性能分析

0 引言

隨著多核處理器技術的發展，緩存和主存作為多核處理器的共享部件已經成為影響系統性能的關鍵因素之一。多核平臺的幫助線程數據預取技術利用多核處理器的空閑核運行數據預取線程，將主線程應用所需要的數據提前推送到最后一級共享緩存中以隱藏主線程應用的片外訪存延遲，從而達到提高應用程序性能的目的。幫助線程主要為主線程提供數據預取服務，其預取服務質量(Quality of Service， QoS)的好壞將直接影響到主線程的性能。目前，幫助線程預取質量常常通過一定的控制參數及其閾值來控制[1]。傳統PV方法[2]使用LOOP_SYNC_INTERVAL和MAX_DIST兩個參數來控制幫助線程。交織預取KPB方法[3-5]采用預取距離K、預取大小P和同步距離B三個參數來控制幫助線程。在以上兩種方法中幫助線程預取控制參數值的選取都是通過靜態枚舉獲得，參數值的選擇過程是一個耗時繁雜的過程。此外，當應用程序運行的平臺環境不同和數據輸入集不同時，這些靜態枚舉獲得控制參數值都會失效。因此，針對不同運行環境和程序輸入集，在幫助線程預取執行過程中如何實時在線地進行預取質量分析和動態反饋調節是需要進一步研究的問題。

要實現幫助線程預取質量的動態調節和優化，首先需要明確幫助線程預取質量的評價指標問題。現有研究大多采用預取準確率和預取覆蓋率兩個指標來度量預取質量的優劣。例如文獻[6-7]中將預取請求中有用的預取區分出來分別用于計算預取準確率和預取覆蓋率。具體到幫助線程預取的研究中，一般硬件實現方法[8-12]中采用上述兩個指標的研究較多，因為硬件模擬器能夠有效地將有用預取和無用預取區分開來。軟件實現方法[13-15]中的大多研究都是采用CPU時鐘數、緩存缺失率、加速比等靜態指標來度量。預取準確率能夠精確地反映預取的質量好壞，如果能夠在程序實時執行過程中獲得這個指標數據就可以根據預取準確率對預取進行很好的自適應控制。但在真實商用機器上實現幫助線程預取時，主線程的訪存流和幫助線程的預取流在最后一級共享緩存(Last Level Cache， LLC)合并，很難區分有用預取和無用預取的數量，因此在幫助線程動態預取執行過程中預取質量評價可以從應用線程性能提升的角度來衡量。本文通過實驗分析幫助線程的預取行為，確定幫助線程預取性能的評價指標，在此基礎上提出了一種自適應的幫助線程預取質量實時在線評價方法。

1 幫助線程預取QoS目標

幫助線程預取QoS是指幫助線程對主線程的預取服務質量。多核平臺幫助線程的數據預取場景如圖1所示。C0為主線程計算核，C1為幫助線程預取核。當啟動幫助線程數據預取之后，由計算核C0和預取核C1分別發出的數據訪問流在LLC緩存合并，理想情況下，主線程計算核C0的LLC緩存缺失流完全可以由幫助線程的預取數據流替代，即主線程不發生LLC緩存缺失，數據全部由幫助線程預取流將數據推送到LLC緩存中。但是實際情況常常會由于幫助線程預取數據流的干擾使得主線程仍然存在LLC缺失流。因此，幫助線程預取QoS控制的重點在于如何對幫助線程發出的預取數據流進行有效的調節和控制，從而減少主線程計算核的LLC緩存缺失率，最大限度地隱藏主線程計算核的片外訪存延遲，從而改善主線程的程序性能。

幫助線程預取QoS目標可以通過對幫助線程的預取觸發、預取行為、同步機制等幾方面的控制策略來實現。在前期工作[3-5]的基礎上，本文實現的幫助線程預取觸發時機選擇在應用主線程進入熱點程序模塊之前觸發；幫助線程的預取行為通過預取距離K和預取工作量大小P兩個參數來控制，幫助線程與應用線程的同步機制通過參數B來控制，主要用于控制幫助線程和主線程之間的同步粒度(頻度)。將幫助線程控制參數K、P和B的不同取值組合，稱之為一個預取QoS策略。

2 幫助線程預取質量在線評價

幫助線程預取QoS評價的目的主要是為了改善主線程的片外訪存延遲，提升主線程的執行性能。評價一個幫助線程QoS策略是否有效，度量指標可以分為靜態度量指標和動態度量指標兩種。靜態度量指標主要用于評價應用某種預取QoS策略對主線程的性能提升情況，著重于對幫助線程預取結果的性能評價。動態度量指標主要用于實時在線對幫助線程的預取QoS進行度量和評價，著重于對幫助線程預取過程的度量。

2.1 預取QoS動態評價的基本思想及相關定義

實現幫助線程預取策略的動態調節，首先需要明確如何對不同的幫助線程預取策略的效果和預取性能進行度量和比較。通過對應用程序中熱點模塊的采樣實驗發現，程序熱點模塊存在不同的階段行為，并且在同一個運行階段內每指令時鐘數(CyclesPerInstruction，CPI)指標保持相對穩定。因此，在熱點模塊程序運行過程中，可以將熱點模塊程序的運行劃分成等長的運行代碼段，每一個運行代碼段用于評測一組預取控制參數值，然后通過觀察應用主線程CPI的變化來度量和評價不同預取控制參數取值的預取性能好壞，這是本文幫助線程動態QoS評價和預取控制策略調節的核心思想。本節以下部分主要介紹幫助線程預取質量動態調節所涉及的相關定義和術語。

定義1 采樣區間平均每條指令運行時鐘數(CPI)。

CPI=Unhalted_CPU_Cycles/Retired_Instructions

(1)

CPI是一個經常使用的綜合性能評測指標，在相同的采樣間隔內通過觀察主線程CPI指標的改進情況來評價不同的預取QoS策略優劣。式(1)中Unhalted_CPU_Cycles表示不停頓的CPU時鐘數，Retired_instructions表示采樣期間提交的指令數，二者均可以通過CPU的硬件性能監視部件獲得。

定義2 熱點模塊M。對于應用程序A中的任意模塊M，存在閾值ε1和ε2分別滿足Cycle(M)/Cycle(A)≥ε1和LLC_Miss(M)/LLC_MISS(A)≥ε2，則稱M為熱點模塊。其中0<ε1,ε2<1，Cycle(X)和LLC_Miss(X)分別表示利用Profiling工具對程序X進行性能剖析所獲得的程序運行時鐘數和LLC缺失數。

定義3 程序階段(Phase)。假設應用程序A動態運行過程中的一個執行區間P，在這個執行區間P內應用程序的某個性能指標(如：CPI、分支預測等)保持相對穩定，那么這個執行區間P為一個程序階段。

定義4 階段變化判定函數(ΔP)。

ΔP=(CPIPi-CPIPj)/CPIPi*100%;i

其中：Pi表示第i個階段檢測期，Pj表示第j個階段檢測期。Pi和Pj之間的程序運行區間即為參數值應用期。在階段檢測期Pi和Pj內，關閉幫助線程預取操作，并采集n個采樣間隔內的CPI數據，最后計算CPI均值來表征檢測期Pi內的程序階段特征。設ΔPthreshold為一個閾值，當ΔP>ΔPthreshold時，稱程序運行階段發生變化。

定義5 預取獲益判定函數(ΔCPI)。

ΔCPI=CPIPi|disable prefetch-CPIPi|enable prefetch

其中Pi表示第i個檢測階段。CPIPi|disable prefetch表示階段Pi在關閉預取狀態下的CPI采樣均值，CPIPi|enable prefetch表示階段Pi在開啟預取狀態下的CPI采樣均值，二者之差用于判定預取是否獲益。在階段Pi內采集n個執行樣本的CPI數據，最后計算CPI均值來表征階段Pi內主線程的性能情況。ΔCPI>0時，表示在幫助線程預取的作用下主線程取得了性能提升，即預取是正獲益；當ΔCPI<0時，表示在幫助線程預取的作用下使得主線程性能下降，即預取是負獲益。

2.2 預取QoS動態評價模型

由定義2所知，程序熱點模塊是指占用應用程序絕大多數運行時間的程序模塊。根據定義3中程序階段的定義，假設程序熱點模塊包含P個執行階段，每個執行階段所運行的指令數用IC表示，由于在每個執行階段內CPI保持相對穩定，以該運行階段的平均CPI值近似的表示該階段內每條指令的CPU時鐘數。為了便于表述，現將模型中的關鍵符號表示如表1所示。

表1 預取QoS動態評價模型的符號表示

原始的串行熱點模塊的CPU執行時鐘數為：

在每個程序運行階段Pj內，將程序熱點模塊的執行分為階段檢測(detect)、參數訓練(train)和參數應用(application)三個部分。階段檢測主要用于程序階段行為的檢測，參數訓練主要用于評價不同參數組合的預取質量。程序階段Pj內真正用于幫助線程數據預取優化的部分是參數應用期，因此參數應用期的長短比例直接決定了程序運行階段Pj預取優化的效果。

其中：CPItrain表示參數訓練期內的采樣樣本CPI的均值，CPIapp為參數應用期內采樣樣本CPI的均值。在一個程序階段Pj內CPI相對保持穩定。由于在階段檢測期內不開啟幫助線程預取，因此在階段檢測期CPIj與原有串行程序一致。

現在僅考慮程序在某個運行階段Pj的CPU時鐘情況。在階段檢測期內，采樣個數Detect_sample=(ICdetect)j/U,參數訓練期采樣個數為Train_sample=(ICtrain)j/U，程序進入參數應用期后不進行采樣，其所包含的樣本個數為App_sample=(ICapp)j/U。

原始串行熱點模塊在程序階段Pj內的執行CPU時鐘近似表示為：

應用幫助線程預取之后，在程序階段Pj內熱點模塊的執行CPU時鐘近似表示為：

應用幫助線程預取后熱點模塊在程序階段Pj內CPU時鐘減少數為：

其中：CPIj表示串行程序在運行階段Pj內的采樣CPI均值，CPItrain為參數訓練期不同參數組合所對應的采樣CPI，CPIapp為參數應用期CPI均值，三者滿足約束條件(CPIj>CPItrain>CPIapp)。

通過以上建模分析，可以得出影響基于動態采樣機制的幫助線程預取性能的兩個主要因素:其一是參數訓練期與參數應用期之間的比例關系；其二是幫助線程預取行為帶來的CPI改善程度。與靜態參數幫助線程預取優化相比，盡管動態方法引入了參數訓練期的額外開銷，但是動態方法中通過引入自適應預取反饋機制，在幫助線程預取過程中能夠根據程序的階段行為和預取獲益對預取的參數值進行動態調節和控制，從而解決了傳統靜態方法應用中在參數選擇、運行平臺調整和輸入集變化等因素帶來參數值優選難題。

2.3 程序階段行為判定及方法

熱點模塊程序階段行為檢測的目的就是當熱點模塊內程序的階段行為發生變化時，幫助線程預取控制參數能夠根據階段變化作出調整。典型階段檢測技術通常將程序的執行區間劃分成等長的采樣間隔，一般以動態執行提交的指令數為劃分單位。在采樣期間收集與程序執行相關的信息，收集完成之后計算兩個采樣間隔之間的相似性，然后根據相似性作出兩個采樣間隔是否處于同一個運行階段的判斷。如果相似性大于一定的閾值即稱程序運行發生了階段行為變化。根據定義4，不同程序運行階段之間的相似性可以用各階段的CPI均值來表示。當程序的不同運行階段之間的CPI均值相差ΔP大于一定的閾值時，即稱為程序運行階段發生了變化。

2.4 幫助線程預取獲益判定及方法

幫助線程預取是通過隱藏主線程應用的片外訪存延遲來實現提高主線程執行性能的目的，因此判定幫助線程預取是否有效可以從幫助線程預取是否帶來主線程性能提升的角度來衡量。如定義5所示，通過觀測在指定程序運行階段Pi內在開啟幫助線程預取和不開啟預取情況下CPI的差值ΔCPI的變化來判斷預取的獲益情況。當幫助線程落后于主線程或是領先主線程過多時，會造成共享緩存污染的情況，此時勢必會干擾主線程的片外訪存行為，造成主線程性能的下降。因此，通過觀測主線程動態CPI指標的變化就能夠直觀地刻畫主線程性能的變化情況，也就能夠客觀描述幫助線程預取的獲益情況。

3 幫助線程預取的實時在線評價算法

在幫助線程預取中引入反饋機制的主要目的是在程序運行過程中能夠根據程序執行的動態階段行為和幫助線程的獲益情況對幫助線程的預取參數值作出調整，從而有效控制幫助線程的預取質量。自適應幫助線程預取的反饋信息主要包括兩方面：一是程序的動態階段變化信息；二是幫助線程預取是否獲益的信息。

幫助線程預取的自適應反饋評價算法如下所示。

算法 幫助預取自適應反饋評價算法。

輸入: 階段檢測區間CPI采樣數據，當前執行進度。 輸出: 自適應決策。

1)

//進入階段檢測和反饋決策

2)

計算ΔP;

//階段判定

3)

計算預取獲益Prefetch_benifit=ΔCPI

4)

if(Prefetch_benifit<0)then

//預取負獲益

5)

if((1-Current_progress)>Progressth)then

//當前執行進度

6)

Init parameter train engine;

7)

Phase=1;

//重新進入參數訓練期

8)

else

9)

Disable Helper Thread；

10)

endif

11)

else

//預取正獲益

12)

if (ΔP>ΔPthreshold)then

//判斷階段是否變化

13)

if((1-Current_progress)>Progressth)then

//當前執行進度

14)

Init parameter train engine;

15)

Phase=1;

//重新進入參數訓練期

16)

else

//接近末尾，沒必要重新優化

17)

Apply CurrentK,P;Phase=3;

//參數保持不變，進入參數應用期

18)

endif

19)

else

//程序階段沒有變化

20)

Apply CurrentK,P;Phase=3;

21)

endif

22)

endif

//if prefetch benefit

幫助線程預取的自適應反饋評價算法的核心思想是在程序熱點模塊執行過程中，周期性地引入反饋機制，并對反饋信息進行條件判定，根據不同的判定結果，幫助線程的預取作出不同的控制決策。算法決策輸出有3種情況：1)重新進入參數選擇優化階段；2)關閉幫助線程預取；3)保持當前狀態不變。

在幫助線程預取的自適應反饋評價算法的反饋執行過程主要有以下兩個步驟：

1)首先判斷當前幫助線程預取是否獲益，主要判斷定義5中ΔCPI的變化。如果預取獲益為負，即ΔCPI<0，此時根據熱點模塊執行的當前進度情況決定是否進入重新優化階段。如果熱點模塊剩余的執行比例不足以完成一個完整的參數的訓練和參數應用周期，那么在預取獲益為負時，直接關閉幫助線程預取；否則進入參數訓練期，進入重新優化階段。

2)如果預取獲益為正，即ΔCPI>0，此時將進行程序的階段行為判斷，主要判斷ΔP指標的變化。如果程序的運行階段行為發生變化，即ΔP>ΔPthreshold，此時根據當前執行進度作出是否進入重新優化階段的決策；如果程序階段沒有發生變化或是程序剩余比例不足以完成一個優化周期，那么當前的配置參數保持不變。

4 實驗評測與分析

4.1 實驗環境與方法

表2提供了本文實驗平臺的關鍵系統結構信息和操作系統內核。

表2 實驗平臺參數及配置

Intel酷睿Q6600四核處理器內部集成了2個Intel早期的Core2Duo處理器，因此Q6600處理器中的4個CPU核每兩個共享一個容量為4Mb的L2緩存，將這兩4個CPU處理核分成兩組，分別是以{(0，1)(2，3)}表示。

基準測試程序及輸入參數如表3所示，其中Gcc和Mcf來自于CPUSPEC2006，Mst和Em3d來自于OLDEN基準測試程序集。所有的性能指標均在Q6600平臺上進行驗證測試。

表3 基準測試程序和輸入集

基準測試程序的運行時間通過在原程序的開頭和結尾分別插樁時間函數，計算被測試程序的整體運行時間。實驗中通過使用LinuxCPUaffinity接口將目標應用綁定在共享緩存的處理核上。在IntelQ6600平臺，將程序綁定在處理核組(0，1)或(2，3)。幫助線程的構造在源代碼級通過手工構造生成。幫助線程預取QoS動態采樣及其性能指標的評測通過采用開源工具庫perfmon2[16]來實現。該工具利用多核平臺的PMU部件的事件計數中斷來達到對主線程執行過程中的CPU性能數據采樣的目的。數據的采樣操作均在操作系統內核級完成，對用戶空間運行的主線程性能影響不是很大。

4.2 實驗結果與分析

4.2.1 熱點模塊的程序階段行為分析

本節通過實驗采樣原始串行應用程序的熱點模塊在執行過程中發生的UNHALTED_CPU_CYCLES和RETIRED_INSTRUCTIONS兩個性能事件的數據，然后計算CPI性能指標，描述應用程序熱點模塊所存在的程序階段行為特征。實驗以Q6600平臺為平臺環境，以Mcf、Em3d和Mst程序為例，采樣周期為100萬條指令。圖2(a)至圖2(c)分別是Mcf、Em3d和Mst三個測試程序的熱點模塊CPI采樣結果，采樣周期為100萬條指令。

從圖2(a)中可以看出，Mcf原始串行程序的熱點模塊Refresh_potential()在進入熱點的開始階段，CPI有逐漸上升的趨勢，當在第2 000個采樣點左右，CPI值接近9，之后的熱點模塊CPI的值均在9左右浮動。在圖2(b)中，Em3d程序的熱點模塊fill_from_field()的CPI值基本保持穩定，熱點模塊的LLC缺失數也基本保持穩定，程序處于一個階段，采樣樣本的變異系數COV為0.009 5。在圖2(c)中，Mst程序的熱點模塊在程序的執行過程中，熱點模塊內部的熱點循環的迭代次數依次遞減，因此總體上看，熱點模塊的CPI值有下降的趨勢。

圖2 基準測試程序的熱點模塊CPI采樣結果

然而，當對采樣數據局部放大時，三個測試程序的CPI分布如圖3所示。圖3中是前100個采樣點數據。幫助線程預取動態調節算法的基礎就是假設在同一個程序階段內程序的性能保持相對穩定。從實驗結果可以看出，三個程序的局部的CPI變化相對很小，因此可以用局部等長的執行間隔近似評價不同預取策略的預取質量好壞。

圖3 Mst、Em3d和Mcf程序CPI采樣局部放大

4.2.2 幫助線程預取動態反饋評價算法解析

4.2.1節對程序熱點模塊的階段行為特征分析發現，Mst程序的熱點模塊在動態執行過程中，CPI呈現下降趨勢。從圖2(c)中的采樣數據看，串行程序熱點模塊的CPI采樣數據從最開始的13左右浮動到最后下降到2～3左右。程序的CPI采樣表現出較大的差異。因此本節將以Mst程序為例，對幫助線程預取動態反饋評價算法的執行過程進行解析，以驗證程序的正確性。

1)算法輸入參數閾值。

算法閾值ΔPthreshold=5%，即兩次階段檢測期間的CPI均值差異超過5%時，即認為程序的執行階段發生了變化。Progressthreshold是指熱點模塊運行過程中，至少需要有Progressthreshold比例的程序還未執行時，才重新進入參數訓練期，進行參數的重新選擇和優化。算法中將Progressthreshold設置為參數訓練期長度的2倍，即至少要保證參數訓練完成，并能夠應用一個訓練周期。在此次執行中，Progressthreshold=0.34%。

2)算法執行過程解析。

表4是Mst程序應用動態反饋評價算法的數據計算過程。當程序受到系統平臺、操作系統、緩存狀態等因素的影響時，程序的CPI性能數據也會發生變化，算法能夠根據幫助線程預取獲益和程序的階段行為作出自適應調整，因此算法再次執行時所得數據不一定與表4完全相同，即算法具有自適應性特征。

首先對表4中各列數據的涵義和計算方法解釋如下。

第1列，反饋點表示信息反饋的次數，由于Mst程序的熱點模塊被調用了1萬次，以熱點函數的1次調用為執行樣本，每調用1000次進行一次信息反饋，因此，反饋點共有10個。

第2列，參數值組合是指參數K和參數P的取值組合([K]-[P]),是反饋評價算法在執行過程中選擇出的適應當前運行階段的較好參數值組合。

第3，4列，程序執行進度以熱點模塊的調用次數衡量，即當前是第X次調用，那么當前的執行進度即為(X/10 000)×100%。程序剩余比例用1減去當前進度得到。

第5列表示動態采樣得到的CPI均值。每次進入反饋算法之后，連續執行10個采樣執行樣本，然后計算10次采樣CPI的均值。可以看到P0反饋點是首次進入反饋，算法只是在關閉幫助線程預取的情況下([0]-[0])，采樣主線程的CPI數據以備之后階段檢測使用，之后程序轉向參數訓練期繼續執行。

當再次進入反饋點后，需要獲得2個采樣CPI均值，即開啟幫助線程預取時的CPI均值和關閉幫助線程預取時的CPI均值。例如反饋點P1中，[460]-[115]即為應用該組參數值時，主線程在采樣區間內的CPI均值，該值用于預取獲益判定函數的計算。P1中的[0]-[0]是指關閉幫助線程預取時采樣主線程的CPI均值，主要用于階段檢測判定函數的計算。

第6列，ΔP是階段檢測判定函數的值，當ΔP>ΔPthreshold并且熱點模塊待執行的比例大于Progressthreshold時，才重新進入參數訓練期，重新根據當前執行階段進行參數值組合的優選。ΔP的計算通過定義4公式計算。例如反饋點P1的ΔP計算是(13.855 60-13.802 48)/13.802 48×100%=0.38%。采用的CPI均值數據是關閉預取時的CPI均值。

第7列，ΔCPI是預取獲益判定函數的值。計算方法為當前反饋點內關閉預取的CPI均值與打開預取的CPI均值之差。ΔCPI主要用于判定程序當前運行階段幫助線程預取是否獲益。

表4 預取動態反饋評價算法解析過程(Mst為例)

在明確了表4各列的涵義之后，算法的執行過程即是表中從反饋點P0到反饋點P9的過程。從P0到P9的過程中，在P4、P5、P6、P7和P8反饋點分別進入了參數訓練期進行自適應的參數選擇和優化。在P0到P3反饋點區間，幫助線程的控制參數保持不變。算法執行的結果與Mst熱點模塊程序階段采樣實驗結果一致。通過對Mst熱點模塊的階段行為分析發現，Mst程序在運行的開始階段，CPI保持相對平穩，同樣幫助線程預取的自適應反饋評價算法的結果在CPI平穩時，保持幫助線程的控制參數不變。應用自適應預取反饋算法之后，Mst熱點模塊的性能加速比為1.496。傳統靜態枚舉方法使得Mst程序熱點模塊的性能加速比為1.524。動態自適應方法與靜態枚舉方法相比，性能相差1.8%，其主要原因在于動態自適應反饋算法具有額外的階段檢測開銷和采樣開銷，算法的性能可以通過減少反饋次數、調節ΔPthreshold和Progressthreshold閾值等進一步縮小算法的額外開銷。

5 結語

傳統幫助線程的預取控制參數值通過靜態枚舉獲得，這將是一個耗時繁雜的過程，已經成為制約幫助線程應用推廣的重要因素，因而實現幫助線程的預取質量的實時評價是突破這一瓶頸的重要一步。本文在分析幫助線程動態評價指標的基礎上，對幫助線程預取的在線評價進行了建模分析，結合實驗評測得出如下結論：1)幫助線程動態預取性能可以采用CPI指標來度量；2)幫助線程不同預取控制策略的評價可以通過動態采樣指令流的方法解決；3)程序階段變化和預取獲益信息是設計自適應的預取反饋評價算法的基礎。通過實驗對提出的評價指標、采樣機制和反饋評價機制進行了驗證，結果證明提出的評價指標能夠描述幫助線程預取服務的質量，提出的自適應預取評價方法能夠根據程序的動態階段行為對幫助線程控制參數值作出自適應控制和調節。下一步的研究工作將對所提出的算法進行詳細的實驗評測與分析。

References)

[1] 張建勛,古志民.幫助線程預取技術研究綜述[J].計算機科學,2013,40(7):19-23.(ZHANG J X, GU Z M.Survey of helper thread prefetching [J].Computer Science, 2013, 40(7): 19-23.)

[2] 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.

[3] GU Z M, FU Y X, ZHENG N H, et al.Improving performance of the irregular data intensive application with small workload for CMPs [C]// ICPPW 2011: Proceedings of 40th International Conference on Parallel Processing Workshops.Piscataway, NJ: IEEE, 2011: 279-288.

[4] HUANG Y, TANG J, GU Z M, et al.The performance optimization of threaded prefetching for linked data structures [J].International Journal of Parallel Programming, 2012, 40(2): 141-163.

[5] 張建勛,古志民,胡瀟涵,等.面向非規則大數據分析應用的多核幫助線程預取方法[J].通信學報,2014,35(8):137-146.(ZHANG J X, GU Z M, HU X H, et al.Multi-core helper thread prefetching for irregular data intensive applications [J].Journal on Communications, 2014, 35(8): 137-146.)

[6] ALAMLDEEN A R, WOOD D A.Interactions between compression and prefetching in chip multiprocessors [C]// HPCA 2007: Proceedings of the 13th International Symposium of High Performance Computer Architecture.Washington, DC: IEEE Computer Society, 2007: 228-239.

[7] LEE C J, MUTLU O, NARASIMAN V, et al.Prefetch-aware DRAM controllers [C]// MICRO 2008: Proceedings of the 41st IEEE/ACM International Symposium on Microarchitecture.Washington, DC: IEEE Computer Society, 2008: 200-209.

[8] ANNAVARAM M, PATEL J M, DAVIDSON E S.Data prefetching by dependence graph precomputation [C]// ISCA 2011: Proceedings of the 28th Annual International Symposium on Computer Architecture.New York: ACM, 2001: 52-61.

[9] MOSHOVOS A, PNEVMATIKATOS D N, BANIASADI A.Slice-processors: an implementation of operation-based prediction [C]// ICS 2001: Proceedings of the 15th International Conference on Supercomputing.New York: ACM, 2001: 321-334.

[10] ZILLES C B, SOHI G.Execution-based prediction using speculative slices [C]// ISCA 2001: Proceedings of the 28th Annual International Symposium on Computer Architecture.New York: ACM, 2001: 2-13.

[11] 歐國東.基于線程的數據預取技術研究[D].長沙：國防科學技術大學,2011.(OU G D.Research on thread-based data prefetching techniques [D].Changsha: National University of Defense Technology, 2011.)

[12] HOU R, ZHANG L B, HU W W.Accelerating sequential programs on chip multiprocessors via dynamic prefetching thread [J].Microprocessors and Microsystems, 2007, 3(31): 200-211.

[13] COLLINS J D, WANG H, TULLSEN D M.Speculative precomputation: long-range prefetching of delinquent loads [C]// ISCA 2001: Proceedings of the 28th Annual International Symposium on Computer Architecture.New York: ACM, 2001: 14-25.

[14] ROTH A, SOHI G S.Speculative data-driven multithreading [C]// HPCA 2001: Proceedings of the 7th International Conference on High Performance Computer Architecture.Washington, DC: IEEE Computer Society, 2001: 191-202.

[15] WON W R, GAUDIOT J L.Speculative pre-execution assisted by compiler (SPEAR) [J].Journal of Parallel and Distributed Computing, 2006, 66(8): 1076-1089.

[16] ERANIAN S.Perfmon2 [EB/OL].[2016-04-15].http://perfmon2.sourceforge.net/.

This work is partially supported by the National Natural Science Foundation of China (61070029, 61370062), the Research Starting Funds of Tianjin University of Technology and Education (KYQD1619).

ZHANG Jianxun, born in 1978, Ph.D., associate professor.His research interests include multi-core computing, cache performance optimization.

GU Zhimin, born in 1964, Ph.D., professor.His research interests include multi-core system architecture, cache optimization, energy conservation and performance analysis.

Real-time online evaluation method of helper thread prefetching quality

ZHANG Jianxun1*, GU Zhimin2

(1.CollegeofInformationEngineering,TianjinUniversityofTechnologyandEducation,Tianjin300222,China;2.SchoolofComputerScienceandTechnology,BeijingInstituteofTechnology,Beijing100081,China)

Focusing on the multifarious and time-consuming optimization process of traditional helper thread parameter value enumeration method, a real-time online helper thread prefetching quality assessment method was proposed.First, the help thread prefetching Quality of Service (QoS) target was defined.Second, the dynamic evaluation index of helper thread prefetching quality was analyzed, as well the helper thread prefetching QoS model.Finally, a dynamic and adaptive helper thread prefetching adjustment algorithm was presented.The algorithm was based on phase behavior and dynamic prefetching benefit information to determine the suitable degree of parameter values, and whether to need feedback optimization, so as to realize the adaptive adjustment and control of helper thread prefetching.By applying the adaptive prefeching algorithm, the speed up of Mst’s hotspot module was 1.496.The experimental results show that the proposed adaptive prefetching evaluation method can control parameter values adaptively according to the dynamic phase behavior and prefetching benefit information.

helper thread; prefetching quality; evaluation method; performance analysis

2016-07-29;

2016-09-01。

國家自然科學基金資助項目(61070029, 61370062)；天津職業技術師范大學科研啟動基金資助項目(KYQD1619)。

張建勛(1978—)，男，河北保定人，副教授，博士，主要研究方向：多核計算、緩存性能優化； 古志民(1964—)，男，山西運城人，教授，博士生導師，博士，CCF會員，主要研究方向：多核系統結構、緩存優化、節能和性能分析。

1001-9081(2017)01-0114-06

10.11772/j.issn.1001-9081.2017.01.0114

TP302.7

A