張建勛，古志民

(1.天津職業(yè)技術(shù)師范大學(xué) 信息技術(shù)工程學(xué)院，天津 300222； 2.北京理工大學(xué) 計(jì)算機(jī)學(xué)院，北京 100081)

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

幫助線(xiàn)程預(yù)取質(zhì)量的實(shí)時(shí)在線(xiàn)評(píng)價(jià)方法

張建勛1*，古志民2

(1.天津職業(yè)技術(shù)師范大學(xué) 信息技術(shù)工程學(xué)院，天津 300222； 2.北京理工大學(xué) 計(jì)算機(jī)學(xué)院，北京 100081)

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

針對(duì)傳統(tǒng)靜態(tài)枚舉設(shè)置幫助線(xiàn)程控制參數(shù)值的繁雜耗時(shí)問(wèn)題，提出了一種幫助線(xiàn)程預(yù)取質(zhì)量的實(shí)時(shí)在線(xiàn)評(píng)價(jià)方法。首先，明確了幫助線(xiàn)程的預(yù)取服務(wù)質(zhì)量(QoS)的目標(biāo)；其次，分析了幫助線(xiàn)程預(yù)取性能評(píng)價(jià)的動(dòng)態(tài)指標(biāo)，對(duì)幫助線(xiàn)程預(yù)取QoS進(jìn)行了建模分析；最后，提出一個(gè)幫助線(xiàn)程預(yù)取的動(dòng)態(tài)自適應(yīng)調(diào)節(jié)算法，算法根據(jù)程序的階段行為變化和動(dòng)態(tài)預(yù)取獲益變化等信息來(lái)判斷參數(shù)值的適用度以及是否需要進(jìn)行反饋優(yōu)化，從而實(shí)現(xiàn)對(duì)預(yù)取控制的自適應(yīng)調(diào)節(jié)。實(shí)驗(yàn)結(jié)果表明，應(yīng)用自適應(yīng)預(yù)取評(píng)價(jià)算法之后，Mst熱點(diǎn)模塊的性能提升加速比為1.496，所提出的自適應(yīng)預(yù)取評(píng)價(jià)方法能夠根據(jù)程序的動(dòng)態(tài)階段行為對(duì)幫助線(xiàn)程控制參數(shù)值作出自適應(yīng)控制和調(diào)節(jié)。

幫助線(xiàn)程；預(yù)取質(zhì)量；評(píng)價(jià)方法；性能分析

0 引言

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

要實(shí)現(xiàn)幫助線(xiàn)程預(yù)取質(zhì)量的動(dòng)態(tài)調(diào)節(jié)和優(yōu)化，首先需要明確幫助線(xiàn)程預(yù)取質(zhì)量的評(píng)價(jià)指標(biāo)問(wèn)題?，F(xiàn)有研究大多采用預(yù)取準(zhǔn)確率和預(yù)取覆蓋率兩個(gè)指標(biāo)來(lái)度量預(yù)取質(zhì)量的優(yōu)劣。例如文獻(xiàn)[6-7]中將預(yù)取請(qǐng)求中有用的預(yù)取區(qū)分出來(lái)分別用于計(jì)算預(yù)取準(zhǔn)確率和預(yù)取覆蓋率。具體到幫助線(xiàn)程預(yù)取的研究中，一般硬件實(shí)現(xiàn)方法[8-12]中采用上述兩個(gè)指標(biāo)的研究較多，因?yàn)橛布M器能夠有效地將有用預(yù)取和無(wú)用預(yù)取區(qū)分開(kāi)來(lái)。軟件實(shí)現(xiàn)方法[13-15]中的大多研究都是采用CPU時(shí)鐘數(shù)、緩存缺失率、加速比等靜態(tài)指標(biāo)來(lái)度量。預(yù)取準(zhǔn)確率能夠精確地反映預(yù)取的質(zhì)量好壞，如果能夠在程序?qū)崟r(shí)執(zhí)行過(guò)程中獲得這個(gè)指標(biāo)數(shù)據(jù)就可以根據(jù)預(yù)取準(zhǔn)確率對(duì)預(yù)取進(jìn)行很好的自適應(yīng)控制。但在真實(shí)商用機(jī)器上實(shí)現(xiàn)幫助線(xiàn)程預(yù)取時(shí)，主線(xiàn)程的訪(fǎng)存流和幫助線(xiàn)程的預(yù)取流在最后一級(jí)共享緩存(Last Level Cache， LLC)合并，很難區(qū)分有用預(yù)取和無(wú)用預(yù)取的數(shù)量，因此在幫助線(xiàn)程動(dòng)態(tài)預(yù)取執(zhí)行過(guò)程中預(yù)取質(zhì)量評(píng)價(jià)可以從應(yīng)用線(xiàn)程性能提升的角度來(lái)衡量。本文通過(guò)實(shí)驗(yàn)分析幫助線(xiàn)程的預(yù)取行為，確定幫助線(xiàn)程預(yù)取性能的評(píng)價(jià)指標(biāo)，在此基礎(chǔ)上提出了一種自適應(yīng)的幫助線(xiàn)程預(yù)取質(zhì)量實(shí)時(shí)在線(xiàn)評(píng)價(jià)方法。

1 幫助線(xiàn)程預(yù)取QoS目標(biāo)

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

幫助線(xiàn)程預(yù)取QoS目標(biāo)可以通過(guò)對(duì)幫助線(xiàn)程的預(yù)取觸發(fā)、預(yù)取行為、同步機(jī)制等幾方面的控制策略來(lái)實(shí)現(xiàn)。在前期工作[3-5]的基礎(chǔ)上，本文實(shí)現(xiàn)的幫助線(xiàn)程預(yù)取觸發(fā)時(shí)機(jī)選擇在應(yīng)用主線(xiàn)程進(jìn)入熱點(diǎn)程序模塊之前觸發(fā)；幫助線(xiàn)程的預(yù)取行為通過(guò)預(yù)取距離K和預(yù)取工作量大小P兩個(gè)參數(shù)來(lái)控制，幫助線(xiàn)程與應(yīng)用線(xiàn)程的同步機(jī)制通過(guò)參數(shù)B來(lái)控制，主要用于控制幫助線(xiàn)程和主線(xiàn)程之間的同步粒度(頻度)。將幫助線(xiàn)程控制參數(shù)K、P和B的不同取值組合，稱(chēng)之為一個(gè)預(yù)取QoS策略。

2 幫助線(xiàn)程預(yù)取質(zhì)量在線(xiàn)評(píng)價(jià)

幫助線(xiàn)程預(yù)取QoS評(píng)價(jià)的目的主要是為了改善主線(xiàn)程的片外訪(fǎng)存延遲，提升主線(xiàn)程的執(zhí)行性能。評(píng)價(jià)一個(gè)幫助線(xiàn)程QoS策略是否有效，度量指標(biāo)可以分為靜態(tài)度量指標(biāo)和動(dòng)態(tài)度量指標(biāo)兩種。靜態(tài)度量指標(biāo)主要用于評(píng)價(jià)應(yīng)用某種預(yù)取QoS策略對(duì)主線(xiàn)程的性能提升情況，著重于對(duì)幫助線(xiàn)程預(yù)取結(jié)果的性能評(píng)價(jià)。動(dòng)態(tài)度量指標(biāo)主要用于實(shí)時(shí)在線(xiàn)對(duì)幫助線(xiàn)程的預(yù)取QoS進(jìn)行度量和評(píng)價(jià)，著重于對(duì)幫助線(xiàn)程預(yù)取過(guò)程的度量。

2.1 預(yù)取QoS動(dòng)態(tài)評(píng)價(jià)的基本思想及相關(guān)定義

實(shí)現(xiàn)幫助線(xiàn)程預(yù)取策略的動(dòng)態(tài)調(diào)節(jié)，首先需要明確如何對(duì)不同的幫助線(xiàn)程預(yù)取策略的效果和預(yù)取性能進(jìn)行度量和比較。通過(guò)對(duì)應(yīng)用程序中熱點(diǎn)模塊的采樣實(shí)驗(yàn)發(fā)現(xiàn)，程序熱點(diǎn)模塊存在不同的階段行為，并且在同一個(gè)運(yùn)行階段內(nèi)每指令時(shí)鐘數(shù)(CyclesPerInstruction，CPI)指標(biāo)保持相對(duì)穩(wěn)定。因此，在熱點(diǎn)模塊程序運(yùn)行過(guò)程中，可以將熱點(diǎn)模塊程序的運(yùn)行劃分成等長(zhǎng)的運(yùn)行代碼段，每一個(gè)運(yùn)行代碼段用于評(píng)測(cè)一組預(yù)取控制參數(shù)值，然后通過(guò)觀(guān)察應(yīng)用主線(xiàn)程CPI的變化來(lái)度量和評(píng)價(jià)不同預(yù)取控制參數(shù)取值的預(yù)取性能好壞，這是本文幫助線(xiàn)程動(dòng)態(tài)QoS評(píng)價(jià)和預(yù)取控制策略調(diào)節(jié)的核心思想。本節(jié)以下部分主要介紹幫助線(xiàn)程預(yù)取質(zhì)量動(dòng)態(tài)調(diào)節(jié)所涉及的相關(guān)定義和術(shù)語(yǔ)。

定義1 采樣區(qū)間平均每條指令運(yùn)行時(shí)鐘數(shù)(CPI)。

CPI=Unhalted_CPU_Cycles/Retired_Instructions

(1)

CPI是一個(gè)經(jīng)常使用的綜合性能評(píng)測(cè)指標(biāo)，在相同的采樣間隔內(nèi)通過(guò)觀(guān)察主線(xiàn)程CPI指標(biāo)的改進(jìn)情況來(lái)評(píng)價(jià)不同的預(yù)取QoS策略?xún)?yōu)劣。式(1)中Unhalted_CPU_Cycles表示不停頓的CPU時(shí)鐘數(shù)，Retired_instructions表示采樣期間提交的指令數(shù)，二者均可以通過(guò)CPU的硬件性能監(jiān)視部件獲得。

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

定義3 程序階段(Phase)。假設(shè)應(yīng)用程序A動(dòng)態(tài)運(yùn)行過(guò)程中的一個(gè)執(zhí)行區(qū)間P，在這個(gè)執(zhí)行區(qū)間P內(nèi)應(yīng)用程序的某個(gè)性能指標(biāo)(如：CPI、分支預(yù)測(cè)等)保持相對(duì)穩(wěn)定，那么這個(gè)執(zhí)行區(qū)間P為一個(gè)程序階段。

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

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

其中：Pi表示第i個(gè)階段檢測(cè)期，Pj表示第j個(gè)階段檢測(cè)期。Pi和Pj之間的程序運(yùn)行區(qū)間即為參數(shù)值應(yīng)用期。在階段檢測(cè)期Pi和Pj內(nèi)，關(guān)閉幫助線(xiàn)程預(yù)取操作，并采集n個(gè)采樣間隔內(nèi)的CPI數(shù)據(jù)，最后計(jì)算CPI均值來(lái)表征檢測(cè)期Pi內(nèi)的程序階段特征。設(shè)ΔPthreshold為一個(gè)閾值，當(dāng)ΔP>ΔPthreshold時(shí)，稱(chēng)程序運(yùn)行階段發(fā)生變化。

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

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

其中Pi表示第i個(gè)檢測(cè)階段。CPIPi|disable prefetch表示階段Pi在關(guān)閉預(yù)取狀態(tài)下的CPI采樣均值，CPIPi|enable prefetch表示階段Pi在開(kāi)啟預(yù)取狀態(tài)下的CPI采樣均值，二者之差用于判定預(yù)取是否獲益。在階段Pi內(nèi)采集n個(gè)執(zhí)行樣本的CPI數(shù)據(jù)，最后計(jì)算CPI均值來(lái)表征階段Pi內(nèi)主線(xiàn)程的性能情況。ΔCPI>0時(shí)，表示在幫助線(xiàn)程預(yù)取的作用下主線(xiàn)程取得了性能提升，即預(yù)取是正獲益；當(dāng)ΔCPI<0時(shí)，表示在幫助線(xiàn)程預(yù)取的作用下使得主線(xiàn)程性能下降，即預(yù)取是負(fù)獲益。

2.2 預(yù)取QoS動(dòng)態(tài)評(píng)價(jià)模型

由定義2所知，程序熱點(diǎn)模塊是指占用應(yīng)用程序絕大多數(shù)運(yùn)行時(shí)間的程序模塊。根據(jù)定義3中程序階段的定義，假設(shè)程序熱點(diǎn)模塊包含P個(gè)執(zhí)行階段，每個(gè)執(zhí)行階段所運(yùn)行的指令數(shù)用IC表示，由于在每個(gè)執(zhí)行階段內(nèi)CPI保持相對(duì)穩(wěn)定，以該運(yùn)行階段的平均CPI值近似的表示該階段內(nèi)每條指令的CPU時(shí)鐘數(shù)。為了便于表述，現(xiàn)將模型中的關(guān)鍵符號(hào)表示如表1所示。

表1 預(yù)取QoS動(dòng)態(tài)評(píng)價(jià)模型的符號(hào)表示

原始的串行熱點(diǎn)模塊的CPU執(zhí)行時(shí)鐘數(shù)為：

在每個(gè)程序運(yùn)行階段Pj內(nèi)，將程序熱點(diǎn)模塊的執(zhí)行分為階段檢測(cè)(detect)、參數(shù)訓(xùn)練(train)和參數(shù)應(yīng)用(application)三個(gè)部分。階段檢測(cè)主要用于程序階段行為的檢測(cè)，參數(shù)訓(xùn)練主要用于評(píng)價(jià)不同參數(shù)組合的預(yù)取質(zhì)量。程序階段Pj內(nèi)真正用于幫助線(xiàn)程數(shù)據(jù)預(yù)取優(yōu)化的部分是參數(shù)應(yīng)用期，因此參數(shù)應(yīng)用期的長(zhǎng)短比例直接決定了程序運(yùn)行階段Pj預(yù)取優(yōu)化的效果。

其中：CPItrain表示參數(shù)訓(xùn)練期內(nèi)的采樣樣本CPI的均值，CPIapp為參數(shù)應(yīng)用期內(nèi)采樣樣本CPI的均值。在一個(gè)程序階段Pj內(nèi)CPI相對(duì)保持穩(wěn)定。由于在階段檢測(cè)期內(nèi)不開(kāi)啟幫助線(xiàn)程預(yù)取，因此在階段檢測(cè)期CPIj與原有串行程序一致。

現(xiàn)在僅考慮程序在某個(gè)運(yùn)行階段Pj的CPU時(shí)鐘情況。在階段檢測(cè)期內(nèi)，采樣個(gè)數(shù)Detect_sample=(ICdetect)j/U,參數(shù)訓(xùn)練期采樣個(gè)數(shù)為T(mén)rain_sample=(ICtrain)j/U，程序進(jìn)入?yún)?shù)應(yīng)用期后不進(jìn)行采樣，其所包含的樣本個(gè)數(shù)為App_sample=(ICapp)j/U。

原始串行熱點(diǎn)模塊在程序階段Pj內(nèi)的執(zhí)行CPU時(shí)鐘近似表示為：

應(yīng)用幫助線(xiàn)程預(yù)取之后，在程序階段Pj內(nèi)熱點(diǎn)模塊的執(zhí)行CPU時(shí)鐘近似表示為：

應(yīng)用幫助線(xiàn)程預(yù)取后熱點(diǎn)模塊在程序階段Pj內(nèi)CPU時(shí)鐘減少數(shù)為：

其中：CPIj表示串行程序在運(yùn)行階段Pj內(nèi)的采樣CPI均值，CPItrain為參數(shù)訓(xùn)練期不同參數(shù)組合所對(duì)應(yīng)的采樣CPI，CPIapp為參數(shù)應(yīng)用期CPI均值，三者滿(mǎn)足約束條件(CPIj>CPItrain>CPIapp)。

通過(guò)以上建模分析，可以得出影響基于動(dòng)態(tài)采樣機(jī)制的幫助線(xiàn)程預(yù)取性能的兩個(gè)主要因素:其一是參數(shù)訓(xùn)練期與參數(shù)應(yīng)用期之間的比例關(guān)系；其二是幫助線(xiàn)程預(yù)取行為帶來(lái)的CPI改善程度。與靜態(tài)參數(shù)幫助線(xiàn)程預(yù)取優(yōu)化相比，盡管動(dòng)態(tài)方法引入了參數(shù)訓(xùn)練期的額外開(kāi)銷(xiāo)，但是動(dòng)態(tài)方法中通過(guò)引入自適應(yīng)預(yù)取反饋機(jī)制，在幫助線(xiàn)程預(yù)取過(guò)程中能夠根據(jù)程序的階段行為和預(yù)取獲益對(duì)預(yù)取的參數(shù)值進(jìn)行動(dòng)態(tài)調(diào)節(jié)和控制，從而解決了傳統(tǒng)靜態(tài)方法應(yīng)用中在參數(shù)選擇、運(yùn)行平臺(tái)調(diào)整和輸入集變化等因素帶來(lái)參數(shù)值優(yōu)選難題。

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

熱點(diǎn)模塊程序階段行為檢測(cè)的目的就是當(dāng)熱點(diǎn)模塊內(nèi)程序的階段行為發(fā)生變化時(shí)，幫助線(xiàn)程預(yù)取控制參數(shù)能夠根據(jù)階段變化作出調(diào)整。典型階段檢測(cè)技術(shù)通常將程序的執(zhí)行區(qū)間劃分成等長(zhǎng)的采樣間隔，一般以動(dòng)態(tài)執(zhí)行提交的指令數(shù)為劃分單位。在采樣期間收集與程序執(zhí)行相關(guān)的信息，收集完成之后計(jì)算兩個(gè)采樣間隔之間的相似性，然后根據(jù)相似性作出兩個(gè)采樣間隔是否處于同一個(gè)運(yùn)行階段的判斷。如果相似性大于一定的閾值即稱(chēng)程序運(yùn)行發(fā)生了階段行為變化。根據(jù)定義4，不同程序運(yùn)行階段之間的相似性可以用各階段的CPI均值來(lái)表示。當(dāng)程序的不同運(yùn)行階段之間的CPI均值相差ΔP大于一定的閾值時(shí)，即稱(chēng)為程序運(yùn)行階段發(fā)生了變化。

2.4 幫助線(xiàn)程預(yù)取獲益判定及方法

幫助線(xiàn)程預(yù)取是通過(guò)隱藏主線(xiàn)程應(yīng)用的片外訪(fǎng)存延遲來(lái)實(shí)現(xiàn)提高主線(xiàn)程執(zhí)行性能的目的，因此判定幫助線(xiàn)程預(yù)取是否有效可以從幫助線(xiàn)程預(yù)取是否帶來(lái)主線(xiàn)程性能提升的角度來(lái)衡量。如定義5所示，通過(guò)觀(guān)測(cè)在指定程序運(yùn)行階段Pi內(nèi)在開(kāi)啟幫助線(xiàn)程預(yù)取和不開(kāi)啟預(yù)取情況下CPI的差值ΔCPI的變化來(lái)判斷預(yù)取的獲益情況。當(dāng)幫助線(xiàn)程落后于主線(xiàn)程或是領(lǐng)先主線(xiàn)程過(guò)多時(shí)，會(huì)造成共享緩存污染的情況，此時(shí)勢(shì)必會(huì)干擾主線(xiàn)程的片外訪(fǎng)存行為，造成主線(xiàn)程性能的下降。因此，通過(guò)觀(guān)測(cè)主線(xiàn)程動(dòng)態(tài)CPI指標(biāo)的變化就能夠直觀(guān)地刻畫(huà)主線(xiàn)程性能的變化情況，也就能夠客觀(guān)描述幫助線(xiàn)程預(yù)取的獲益情況。

3 幫助線(xiàn)程預(yù)取的實(shí)時(shí)在線(xiàn)評(píng)價(jià)算法

在幫助線(xiàn)程預(yù)取中引入反饋機(jī)制的主要目的是在程序運(yùn)行過(guò)程中能夠根據(jù)程序執(zhí)行的動(dòng)態(tài)階段行為和幫助線(xiàn)程的獲益情況對(duì)幫助線(xiàn)程的預(yù)取參數(shù)值作出調(diào)整，從而有效控制幫助線(xiàn)程的預(yù)取質(zhì)量。自適應(yīng)幫助線(xiàn)程預(yù)取的反饋信息主要包括兩方面：一是程序的動(dòng)態(tài)階段變化信息；二是幫助線(xiàn)程預(yù)取是否獲益的信息。

幫助線(xiàn)程預(yù)取的自適應(yīng)反饋評(píng)價(jià)算法如下所示。

算法 幫助預(yù)取自適應(yīng)反饋評(píng)價(jià)算法。

輸入: 階段檢測(cè)區(qū)間CPI采樣數(shù)據(jù)，當(dāng)前執(zhí)行進(jìn)度。 輸出: 自適應(yīng)決策。

1)

//進(jìn)入階段檢測(cè)和反饋決策

2)

計(jì)算ΔP;

//階段判定

3)

計(jì)算預(yù)取獲益Prefetch_benifit=ΔCPI

4)

if(Prefetch_benifit<0)then

//預(yù)取負(fù)獲益

5)

if((1-Current_progress)>Progressth)then

//當(dāng)前執(zhí)行進(jìn)度

6)

Init parameter train engine;

7)

Phase=1;

//重新進(jìn)入?yún)?shù)訓(xùn)練期

8)

else

9)

Disable Helper Thread；

10)

endif

11)

else

//預(yù)取正獲益

12)

if (ΔP>ΔPthreshold)then

//判斷階段是否變化

13)

if((1-Current_progress)>Progressth)then

//當(dāng)前執(zhí)行進(jìn)度

14)

Init parameter train engine;

15)

Phase=1;

//重新進(jìn)入?yún)?shù)訓(xùn)練期

16)

else

//接近末尾，沒(méi)必要重新優(yōu)化

17)

Apply CurrentK,P;Phase=3;

//參數(shù)保持不變，進(jìn)入?yún)?shù)應(yīng)用期

18)

endif

19)

else

//程序階段沒(méi)有變化

20)

Apply CurrentK,P;Phase=3;

21)

endif

22)

endif

//if prefetch benefit

幫助線(xiàn)程預(yù)取的自適應(yīng)反饋評(píng)價(jià)算法的核心思想是在程序熱點(diǎn)模塊執(zhí)行過(guò)程中，周期性地引入反饋機(jī)制，并對(duì)反饋信息進(jìn)行條件判定，根據(jù)不同的判定結(jié)果，幫助線(xiàn)程的預(yù)取作出不同的控制決策。算法決策輸出有3種情況：1)重新進(jìn)入?yún)?shù)選擇優(yōu)化階段；2)關(guān)閉幫助線(xiàn)程預(yù)取；3)保持當(dāng)前狀態(tài)不變。

在幫助線(xiàn)程預(yù)取的自適應(yīng)反饋評(píng)價(jià)算法的反饋執(zhí)行過(guò)程主要有以下兩個(gè)步驟：

1)首先判斷當(dāng)前幫助線(xiàn)程預(yù)取是否獲益，主要判斷定義5中ΔCPI的變化。如果預(yù)取獲益為負(fù)，即ΔCPI<0，此時(shí)根據(jù)熱點(diǎn)模塊執(zhí)行的當(dāng)前進(jìn)度情況決定是否進(jìn)入重新優(yōu)化階段。如果熱點(diǎn)模塊剩余的執(zhí)行比例不足以完成一個(gè)完整的參數(shù)的訓(xùn)練和參數(shù)應(yīng)用周期，那么在預(yù)取獲益為負(fù)時(shí)，直接關(guān)閉幫助線(xiàn)程預(yù)取；否則進(jìn)入?yún)?shù)訓(xùn)練期，進(jìn)入重新優(yōu)化階段。

2)如果預(yù)取獲益為正，即ΔCPI>0，此時(shí)將進(jìn)行程序的階段行為判斷，主要判斷ΔP指標(biāo)的變化。如果程序的運(yùn)行階段行為發(fā)生變化，即ΔP>ΔPthreshold，此時(shí)根據(jù)當(dāng)前執(zhí)行進(jìn)度作出是否進(jìn)入重新優(yōu)化階段的決策；如果程序階段沒(méi)有發(fā)生變化或是程序剩余比例不足以完成一個(gè)優(yōu)化周期，那么當(dāng)前的配置參數(shù)保持不變。

4 實(shí)驗(yàn)評(píng)測(cè)與分析

4.1 實(shí)驗(yàn)環(huán)境與方法

表2提供了本文實(shí)驗(yàn)平臺(tái)的關(guān)鍵系統(tǒng)結(jié)構(gòu)信息和操作系統(tǒng)內(nèi)核。

表2 實(shí)驗(yàn)平臺(tái)參數(shù)及配置

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

基準(zhǔn)測(cè)試程序及輸入?yún)?shù)如表3所示，其中Gcc和Mcf來(lái)自于CPUSPEC2006，Mst和Em3d來(lái)自于OLDEN基準(zhǔn)測(cè)試程序集。所有的性能指標(biāo)均在Q6600平臺(tái)上進(jìn)行驗(yàn)證測(cè)試。

表3 基準(zhǔn)測(cè)試程序和輸入集

基準(zhǔn)測(cè)試程序的運(yùn)行時(shí)間通過(guò)在原程序的開(kāi)頭和結(jié)尾分別插樁時(shí)間函數(shù)，計(jì)算被測(cè)試程序的整體運(yùn)行時(shí)間。實(shí)驗(yàn)中通過(guò)使用LinuxCPUaffinity接口將目標(biāo)應(yīng)用綁定在共享緩存的處理核上。在IntelQ6600平臺(tái)，將程序綁定在處理核組(0，1)或(2，3)。幫助線(xiàn)程的構(gòu)造在源代碼級(jí)通過(guò)手工構(gòu)造生成。幫助線(xiàn)程預(yù)取QoS動(dòng)態(tài)采樣及其性能指標(biāo)的評(píng)測(cè)通過(guò)采用開(kāi)源工具庫(kù)perfmon2[16]來(lái)實(shí)現(xiàn)。該工具利用多核平臺(tái)的PMU部件的事件計(jì)數(shù)中斷來(lái)達(dá)到對(duì)主線(xiàn)程執(zhí)行過(guò)程中的CPU性能數(shù)據(jù)采樣的目的。數(shù)據(jù)的采樣操作均在操作系統(tǒng)內(nèi)核級(jí)完成，對(duì)用戶(hù)空間運(yùn)行的主線(xiàn)程性能影響不是很大。

4.2 實(shí)驗(yàn)結(jié)果與分析

4.2.1 熱點(diǎn)模塊的程序階段行為分析

本節(jié)通過(guò)實(shí)驗(yàn)采樣原始串行應(yīng)用程序的熱點(diǎn)模塊在執(zhí)行過(guò)程中發(fā)生的UNHALTED_CPU_CYCLES和RETIRED_INSTRUCTIONS兩個(gè)性能事件的數(shù)據(jù)，然后計(jì)算CPI性能指標(biāo)，描述應(yīng)用程序熱點(diǎn)模塊所存在的程序階段行為特征。實(shí)驗(yàn)以Q6600平臺(tái)為平臺(tái)環(huán)境，以Mcf、Em3d和Mst程序?yàn)槔?，采樣周期?00萬(wàn)條指令。圖2(a)至圖2(c)分別是Mcf、Em3d和Mst三個(gè)測(cè)試程序的熱點(diǎn)模塊CPI采樣結(jié)果，采樣周期為100萬(wàn)條指令。

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

圖2 基準(zhǔn)測(cè)試程序的熱點(diǎn)模塊CPI采樣結(jié)果

然而，當(dāng)對(duì)采樣數(shù)據(jù)局部放大時(shí)，三個(gè)測(cè)試程序的CPI分布如圖3所示。圖3中是前100個(gè)采樣點(diǎn)數(shù)據(jù)。幫助線(xiàn)程預(yù)取動(dòng)態(tài)調(diào)節(jié)算法的基礎(chǔ)就是假設(shè)在同一個(gè)程序階段內(nèi)程序的性能保持相對(duì)穩(wěn)定。從實(shí)驗(yàn)結(jié)果可以看出，三個(gè)程序的局部的CPI變化相對(duì)很小，因此可以用局部等長(zhǎng)的執(zhí)行間隔近似評(píng)價(jià)不同預(yù)取策略的預(yù)取質(zhì)量好壞。

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

4.2.2 幫助線(xiàn)程預(yù)取動(dòng)態(tài)反饋評(píng)價(jià)算法解析

4.2.1節(jié)對(duì)程序熱點(diǎn)模塊的階段行為特征分析發(fā)現(xiàn)，Mst程序的熱點(diǎn)模塊在動(dòng)態(tài)執(zhí)行過(guò)程中，CPI呈現(xiàn)下降趨勢(shì)。從圖2(c)中的采樣數(shù)據(jù)看，串行程序熱點(diǎn)模塊的CPI采樣數(shù)據(jù)從最開(kāi)始的13左右浮動(dòng)到最后下降到2～3左右。程序的CPI采樣表現(xiàn)出較大的差異。因此本節(jié)將以Mst程序?yàn)槔?，?duì)幫助線(xiàn)程預(yù)取動(dòng)態(tài)反饋評(píng)價(jià)算法的執(zhí)行過(guò)程進(jìn)行解析，以驗(yàn)證程序的正確性。

1)算法輸入?yún)?shù)閾值。

算法閾值ΔPthreshold=5%，即兩次階段檢測(cè)期間的CPI均值差異超過(guò)5%時(shí)，即認(rèn)為程序的執(zhí)行階段發(fā)生了變化。Progressthreshold是指熱點(diǎn)模塊運(yùn)行過(guò)程中，至少需要有Progressthreshold比例的程序還未執(zhí)行時(shí)，才重新進(jìn)入?yún)?shù)訓(xùn)練期，進(jìn)行參數(shù)的重新選擇和優(yōu)化。算法中將Progressthreshold設(shè)置為參數(shù)訓(xùn)練期長(zhǎng)度的2倍，即至少要保證參數(shù)訓(xùn)練完成，并能夠應(yīng)用一個(gè)訓(xùn)練周期。在此次執(zhí)行中，Progressthreshold=0.34%。

2)算法執(zhí)行過(guò)程解析。

表4是Mst程序應(yīng)用動(dòng)態(tài)反饋評(píng)價(jià)算法的數(shù)據(jù)計(jì)算過(guò)程。當(dāng)程序受到系統(tǒng)平臺(tái)、操作系統(tǒng)、緩存狀態(tài)等因素的影響時(shí)，程序的CPI性能數(shù)據(jù)也會(huì)發(fā)生變化，算法能夠根據(jù)幫助線(xiàn)程預(yù)取獲益和程序的階段行為作出自適應(yīng)調(diào)整，因此算法再次執(zhí)行時(shí)所得數(shù)據(jù)不一定與表4完全相同，即算法具有自適應(yīng)性特征。

首先對(duì)表4中各列數(shù)據(jù)的涵義和計(jì)算方法解釋如下。

第1列，反饋點(diǎn)表示信息反饋的次數(shù)，由于Mst程序的熱點(diǎn)模塊被調(diào)用了1萬(wàn)次，以熱點(diǎn)函數(shù)的1次調(diào)用為執(zhí)行樣本，每調(diào)用1000次進(jìn)行一次信息反饋，因此，反饋點(diǎn)共有10個(gè)。

第2列，參數(shù)值組合是指參數(shù)K和參數(shù)P的取值組合([K]-[P]),是反饋評(píng)價(jià)算法在執(zhí)行過(guò)程中選擇出的適應(yīng)當(dāng)前運(yùn)行階段的較好參數(shù)值組合。

第3，4列，程序執(zhí)行進(jìn)度以熱點(diǎn)模塊的調(diào)用次數(shù)衡量，即當(dāng)前是第X次調(diào)用，那么當(dāng)前的執(zhí)行進(jìn)度即為(X/10 000)×100%。程序剩余比例用1減去當(dāng)前進(jìn)度得到。

第5列表示動(dòng)態(tài)采樣得到的CPI均值。每次進(jìn)入反饋算法之后，連續(xù)執(zhí)行10個(gè)采樣執(zhí)行樣本，然后計(jì)算10次采樣CPI的均值?？梢钥吹絇0反饋點(diǎn)是首次進(jìn)入反饋，算法只是在關(guān)閉幫助線(xiàn)程預(yù)取的情況下([0]-[0])，采樣主線(xiàn)程的CPI數(shù)據(jù)以備之后階段檢測(cè)使用，之后程序轉(zhuǎn)向參數(shù)訓(xùn)練期繼續(xù)執(zhí)行。

當(dāng)再次進(jìn)入反饋點(diǎn)后，需要獲得2個(gè)采樣CPI均值，即開(kāi)啟幫助線(xiàn)程預(yù)取時(shí)的CPI均值和關(guān)閉幫助線(xiàn)程預(yù)取時(shí)的CPI均值。例如反饋點(diǎn)P1中，[460]-[115]即為應(yīng)用該組參數(shù)值時(shí)，主線(xiàn)程在采樣區(qū)間內(nèi)的CPI均值，該值用于預(yù)取獲益判定函數(shù)的計(jì)算。P1中的[0]-[0]是指關(guān)閉幫助線(xiàn)程預(yù)取時(shí)采樣主線(xiàn)程的CPI均值，主要用于階段檢測(cè)判定函數(shù)的計(jì)算。

第6列，ΔP是階段檢測(cè)判定函數(shù)的值，當(dāng)ΔP>ΔPthreshold并且熱點(diǎn)模塊待執(zhí)行的比例大于Progressthreshold時(shí)，才重新進(jìn)入?yún)?shù)訓(xùn)練期，重新根據(jù)當(dāng)前執(zhí)行階段進(jìn)行參數(shù)值組合的優(yōu)選。ΔP的計(jì)算通過(guò)定義4公式計(jì)算。例如反饋點(diǎn)P1的ΔP計(jì)算是(13.855 60-13.802 48)/13.802 48×100%=0.38%。采用的CPI均值數(shù)據(jù)是關(guān)閉預(yù)取時(shí)的CPI均值。

第7列，ΔCPI是預(yù)取獲益判定函數(shù)的值。計(jì)算方法為當(dāng)前反饋點(diǎn)內(nèi)關(guān)閉預(yù)取的CPI均值與打開(kāi)預(yù)取的CPI均值之差。ΔCPI主要用于判定程序當(dāng)前運(yùn)行階段幫助線(xiàn)程預(yù)取是否獲益。

表4 預(yù)取動(dòng)態(tài)反饋評(píng)價(jià)算法解析過(guò)程(Mst為例)

在明確了表4各列的涵義之后，算法的執(zhí)行過(guò)程即是表中從反饋點(diǎn)P0到反饋點(diǎn)P9的過(guò)程。從P0到P9的過(guò)程中，在P4、P5、P6、P7和P8反饋點(diǎn)分別進(jìn)入了參數(shù)訓(xùn)練期進(jìn)行自適應(yīng)的參數(shù)選擇和優(yōu)化。在P0到P3反饋點(diǎn)區(qū)間，幫助線(xiàn)程的控制參數(shù)保持不變。算法執(zhí)行的結(jié)果與Mst熱點(diǎn)模塊程序階段采樣實(shí)驗(yàn)結(jié)果一致。通過(guò)對(duì)Mst熱點(diǎn)模塊的階段行為分析發(fā)現(xiàn)，Mst程序在運(yùn)行的開(kāi)始階段，CPI保持相對(duì)平穩(wěn)，同樣幫助線(xiàn)程預(yù)取的自適應(yīng)反饋評(píng)價(jià)算法的結(jié)果在CPI平穩(wěn)時(shí)，保持幫助線(xiàn)程的控制參數(shù)不變。應(yīng)用自適應(yīng)預(yù)取反饋算法之后，Mst熱點(diǎn)模塊的性能加速比為1.496。傳統(tǒng)靜態(tài)枚舉方法使得Mst程序熱點(diǎn)模塊的性能加速比為1.524。動(dòng)態(tài)自適應(yīng)方法與靜態(tài)枚舉方法相比，性能相差1.8%，其主要原因在于動(dòng)態(tài)自適應(yīng)反饋算法具有額外的階段檢測(cè)開(kāi)銷(xiāo)和采樣開(kāi)銷(xiāo)，算法的性能可以通過(guò)減少反饋次數(shù)、調(diào)節(jié)ΔPthreshold和Progressthreshold閾值等進(jìn)一步縮小算法的額外開(kāi)銷(xiāo)。

5 結(jié)語(yǔ)

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

References)

[1] 張建勛,古志民.幫助線(xiàn)程預(yù)取技術(shù)研究綜述[J].計(jì)算機(jī)科學(xué),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] 張建勛,古志民,胡瀟涵,等.面向非規(guī)則大數(shù)據(jù)分析應(yīng)用的多核幫助線(xiàn)程預(yù)取方法[J].通信學(xué)報(bào),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] 歐國(guó)東.基于線(xiàn)程的數(shù)據(jù)預(yù)取技術(shù)研究[D].長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué),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。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61070029, 61370062)；天津職業(yè)技術(shù)師范大學(xué)科研啟動(dòng)基金資助項(xiàng)目(KYQD1619)。

張建勛(1978—)，男，河北保定人，副教授，博士，主要研究方向：多核計(jì)算、緩存性能優(yōu)化； 古志民(1964—)，男，山西運(yùn)城人，教授，博士生導(dǎo)師，博士，CCF會(huì)員，主要研究方向：多核系統(tǒng)結(jié)構(gòu)、緩存優(yōu)化、節(jié)能和性能分析。

1001-9081(2017)01-0114-06

10.11772/j.issn.1001-9081.2017.01.0114

TP302.7

A