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

張建勛，古志民

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

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

幫助線程預(yù)取質(zhì)量的實(shí)時(shí)在線評(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è)置幫助線程控制參數(shù)值的繁雜耗時(shí)問題，提出了一種幫助線程預(yù)取質(zhì)量的實(shí)時(shí)在線評(píng)價(jià)方法。首先，明確了幫助線程的預(yù)取服務(wù)質(zhì)量(QoS)的目標(biāo)；其次，分析了幫助線程預(yù)取性能評(píng)價(jià)的動(dòng)態(tài)指標(biāo)，對(duì)幫助線程預(yù)取QoS進(jìn)行了建模分析；最后，提出一個(gè)幫助線程預(yù)取的動(dòng)態(tài)自適應(yīng)調(diào)節(jié)算法，算法根據(jù)程序的階段行為變化和動(dòng)態(tài)預(yù)取獲益變化等信息來判斷參數(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ì)幫助線程控制參數(shù)值作出自適應(yīng)控制和調(diào)節(jié)。

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

0 引言

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

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

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

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

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

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

幫助線程預(yù)取QoS評(píng)價(jià)的目的主要是為了改善主線程的片外訪存延遲，提升主線程的執(zhí)行性能。評(píng)價(jià)一個(gè)幫助線程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ì)主線程的性能提升情況，著重于對(duì)幫助線程預(yù)取結(jié)果的性能評(píng)價(jià)。動(dòng)態(tài)度量指標(biāo)主要用于實(shí)時(shí)在線對(duì)幫助線程的預(yù)取QoS進(jìn)行度量和評(píng)價(jià)，著重于對(duì)幫助線程預(yù)取過程的度量。

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

實(shí)現(xiàn)幫助線程預(yù)取策略的動(dòng)態(tài)調(diào)節(jié)，首先需要明確如何對(duì)不同的幫助線程預(yù)取策略的效果和預(yù)取性能進(jìn)行度量和比較。通過對(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)行過程中，可以將熱點(diǎn)模塊程序的運(yùn)行劃分成等長的運(yùn)行代碼段，每一個(gè)運(yùn)行代碼段用于評(píng)測(cè)一組預(yù)取控制參數(shù)值，然后通過觀察應(yīng)用主線程CPI的變化來度量和評(píng)價(jià)不同預(yù)取控制參數(shù)取值的預(yù)取性能好壞，這是本文幫助線程動(dòng)態(tài)QoS評(píng)價(jià)和預(yù)取控制策略調(diào)節(jié)的核心思想。本節(jié)以下部分主要介紹幫助線程預(yù)取質(zhì)量動(dòng)態(tài)調(diào)節(jié)所涉及的相關(guān)定義和術(shù)語。

定義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)通過觀察主線程CPI指標(biāo)的改進(jìn)情況來評(píng)價(jià)不同的預(yù)取QoS策略優(yōu)劣。式(1)中Unhalted_CPU_Cycles表示不停頓的CPU時(shí)鐘數(shù)，Retired_instructions表示采樣期間提交的指令數(shù)，二者均可以通過CPU的硬件性能監(jiān)視部件獲得。

定義2 熱點(diǎn)模塊M。對(duì)于應(yīng)用程序A中的任意模塊M，存在閾值ε1和ε2分別滿足Cycle(M)/Cycle(A)≥ε1和LLC_Miss(M)/LLC_MISS(A)≥ε2，則稱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)行過程中的一個(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)閉幫助線程預(yù)取操作，并采集n個(gè)采樣間隔內(nèi)的CPI數(shù)據(jù)，最后計(jì)算CPI均值來表征檢測(cè)期Pi內(nèi)的程序階段特征。設(shè)ΔPthreshold為一個(gè)閾值，當(dāng)ΔP>ΔPthreshold時(shí)，稱程序運(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在開啟預(yù)取狀態(tài)下的CPI采樣均值，二者之差用于判定預(yù)取是否獲益。在階段Pi內(nèi)采集n個(gè)執(zhí)行樣本的CPI數(shù)據(jù)，最后計(jì)算CPI均值來表征階段Pi內(nèi)主線程的性能情況。ΔCPI>0時(shí)，表示在幫助線程預(yù)取的作用下主線程取得了性能提升，即預(yù)取是正獲益；當(dāng)ΔCPI<0時(shí)，表示在幫助線程預(yù)取的作用下使得主線程性能下降，即預(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)真正用于幫助線程數(shù)據(jù)預(yù)取優(yōu)化的部分是參數(shù)應(yīng)用期，因此參數(shù)應(yī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)不開啟幫助線程預(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ù)為Train_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)用幫助線程預(yù)取之后，在程序階段Pj內(nèi)熱點(diǎn)模塊的執(zhí)行CPU時(shí)鐘近似表示為：

應(yīng)用幫助線程預(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均值，三者滿足約束條件(CPIj>CPItrain>CPIapp)。

通過以上建模分析，可以得出影響基于動(dòng)態(tài)采樣機(jī)制的幫助線程預(yù)取性能的兩個(gè)主要因素:其一是參數(shù)訓(xùn)練期與參數(shù)應(yīng)用期之間的比例關(guān)系；其二是幫助線程預(yù)取行為帶來的CPI改善程度。與靜態(tài)參數(shù)幫助線程預(yù)取優(yōu)化相比，盡管動(dòng)態(tài)方法引入了參數(shù)訓(xùn)練期的額外開銷，但是動(dòng)態(tài)方法中通過引入自適應(yīng)預(yù)取反饋機(jī)制，在幫助線程預(yù)取過程中能夠根據(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)整和輸入集變化等因素帶來參數(shù)值優(yōu)選難題。

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

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

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

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

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

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

幫助線程預(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

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

17)

Apply CurrentK,P;Phase=3;

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

18)

endif

19)

else

//程序階段沒有變化

20)

Apply CurrentK,P;Phase=3;

21)

endif

22)

endif

//if prefetch benefit

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

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

1)首先判斷當(dāng)前幫助線程預(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)閉幫助線程預(yù)?。环駝t進(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)化階段的決策；如果程序階段沒有發(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核每兩個(gè)共享一個(gè)容量為4Mb的L2緩存，將這兩4個(gè)CPU處理核分成兩組，分別是以{(0，1)(2，3)}表示。

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

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

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

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

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

本節(jié)通過實(shí)驗(yàn)采樣原始串行應(yīng)用程序的熱點(diǎn)模塊在執(zhí)行過程中發(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萬條指令。圖2(a)至圖2(c)分別是Mcf、Em3d和Mst三個(gè)測(cè)試程序的熱點(diǎn)模塊CPI采樣結(jié)果，采樣周期為100萬條指令。

從圖2(a)中可以看出，Mcf原始串行程序的熱點(diǎn)模塊Refresh_potential()在進(jìn)入熱點(diǎn)的開始階段，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í)行過程中，熱點(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ù)。幫助線程預(yù)取動(dòng)態(tài)調(diào)節(jié)算法的基礎(chǔ)就是假設(shè)在同一個(gè)程序階段內(nèi)程序的性能保持相對(duì)穩(wěn)定。從實(shí)驗(yàn)結(jié)果可以看出，三個(gè)程序的局部的CPI變化相對(duì)很小，因此可以用局部等長的執(zhí)行間隔近似評(píng)價(jià)不同預(yù)取策略的預(yù)取質(zhì)量好壞。

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

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

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

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

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

表4是Mst程序應(yīng)用動(dòng)態(tài)反饋評(píng)價(jià)算法的數(shù)據(jù)計(jì)算過程。當(dāng)程序受到系統(tǒng)平臺(tái)、操作系統(tǒng)、緩存狀態(tài)等因素的影響時(shí)，程序的CPI性能數(shù)據(jù)也會(huì)發(fā)生變化，算法能夠根據(jù)幫助線程預(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萬次，以熱點(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í)行過程中選擇出的適應(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)閉幫助線程預(yù)取的情況下([0]-[0])，采樣主線程的CPI數(shù)據(jù)以備之后階段檢測(cè)使用，之后程序轉(zhuǎn)向參數(shù)訓(xùn)練期繼續(xù)執(zhí)行。

當(dāng)再次進(jìn)入反饋點(diǎn)后，需要獲得2個(gè)采樣CPI均值，即開啟幫助線程預(yù)取時(shí)的CPI均值和關(guān)閉幫助線程預(yù)取時(shí)的CPI均值。例如反饋點(diǎn)P1中，[460]-[115]即為應(yīng)用該組參數(shù)值時(shí)，主線程在采樣區(qū)間內(nèi)的CPI均值，該值用于預(yù)取獲益判定函數(shù)的計(jì)算。P1中的[0]-[0]是指關(guān)閉幫助線程預(yù)取時(shí)采樣主線程的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ì)算通過定義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均值與打開預(yù)取的CPI均值之差。ΔCPI主要用于判定程序當(dāng)前運(yùn)行階段幫助線程預(yù)取是否獲益。

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

在明確了表4各列的涵義之后，算法的執(zhí)行過程即是表中從反饋點(diǎn)P0到反饋點(diǎn)P9的過程。從P0到P9的過程中，在P4、P5、P6、P7和P8反饋點(diǎn)分別進(jìn)入了參數(shù)訓(xùn)練期進(jìn)行自適應(yīng)的參數(shù)選擇和優(yōu)化。在P0到P3反饋點(diǎn)區(qū)間，幫助線程的控制參數(shù)保持不變。算法執(zhí)行的結(jié)果與Mst熱點(diǎn)模塊程序階段采樣實(shí)驗(yàn)結(jié)果一致。通過對(duì)Mst熱點(diǎn)模塊的階段行為分析發(fā)現(xiàn)，Mst程序在運(yùn)行的開始階段，CPI保持相對(duì)平穩(wěn)，同樣幫助線程預(yù)取的自適應(yīng)反饋評(píng)價(jià)算法的結(jié)果在CPI平穩(wěn)時(shí)，保持幫助線程的控制參數(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è)開銷和采樣開銷，算法的性能可以通過減少反饋次數(shù)、調(diào)節(jié)ΔPthreshold和Progressthreshold閾值等進(jìn)一步縮小算法的額外開銷。

5 結(jié)語

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

References)

[1] 張建勛,古志民.幫助線程預(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)用的多核幫助線程預(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] 歐國東.基于線程的數(shù)據(jù)預(yù)取技術(shù)研究[D].長沙：國防科學(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。

國家自然科學(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