李美蓉 趙銀亮

1(西安航空學(xué)院 陜西 西安 710077) 2(西安交通大學(xué) 陜西 西安 710049)

0 引 言

隨著多核和眾核技術(shù)的出現(xiàn)，如何利用并行技術(shù)挖掘程序中潛在的并行性已成為研究熱點(diǎn)。推測多線程SpMT(Speculative Multithreading)，也稱線程級推測，作為一種自動化并行技術(shù)，能夠從串行程序中抽取出多個(gè)線程，通過在多核框架中對它們進(jìn)行推測并行來縮短程序的有效執(zhí)行時(shí)間[1-4]。由于采用推測并行而非真正意義上的并行執(zhí)行，此技術(shù)允許處于推測狀態(tài)的線程間存在模糊的數(shù)據(jù)依賴關(guān)系。若在推測并行之前能準(zhǔn)確確定所激發(fā)線程的推測時(shí)機(jī)，則能有效隱藏這些數(shù)據(jù)依賴關(guān)系，帶來大幅度的并行性能提升。否則不準(zhǔn)確的推測時(shí)機(jī)會造成線程間頻繁的數(shù)據(jù)依賴違規(guī)現(xiàn)象，將影響后繼線程分派及推測并行的速度，甚至導(dǎo)致并行性能下降。

一般地，循環(huán)結(jié)構(gòu)在串行程序中占有較大比例的執(zhí)行時(shí)間。若將每個(gè)循環(huán)迭代看作一個(gè)線程體作為推測對象，則能得到循環(huán)級推測[5-8]。本文重點(diǎn)對循環(huán)級推測展開研究。為了準(zhǔn)確判定每個(gè)循環(huán)的推測時(shí)機(jī)，很多性能預(yù)測和性能優(yōu)化技術(shù)得到了廣泛地研究。編譯器作為其中一個(gè)典型代表，因具有完整的源程序信息和相關(guān)編譯優(yōu)化技術(shù)等優(yōu)勢，常用于預(yù)測循環(huán)推測時(shí)機(jī)的首選[9]。多數(shù)基于編譯端的循環(huán)級推測技術(shù)常借助于程序剖析技術(shù)預(yù)先得到一些程序執(zhí)行信息，如循環(huán)迭代次數(shù)、數(shù)據(jù)依賴個(gè)數(shù)、循環(huán)迭代指令數(shù)和緩存命中次數(shù)等，再利用這些信息來預(yù)測循環(huán)并行性能，以性能預(yù)測結(jié)果作為循環(huán)推測依據(jù)。并行性能預(yù)測主要采用估算誤推測代價(jià)實(shí)現(xiàn)。Wang等[5]主要利用線程間的數(shù)據(jù)依賴概率、值通信延遲和線程自身的創(chuàng)建開銷三者來估算誤推測代價(jià)。Liu等[7]則側(cè)重于分析線程粒度、數(shù)據(jù)依賴距離、線程創(chuàng)建以及激發(fā)所帶來的性能影響作用。在計(jì)算誤推測時(shí)，Dou等[10]又引入了對運(yùn)行時(shí)線程撤銷重啟和推測緩沖區(qū)溢出等因素的分析。而Liu等[11]增加了推測數(shù)據(jù)預(yù)取計(jì)算，量化了撤銷線程所帶來的并行收益大小。Gao等[12]利用編譯時(shí)的誤推測代價(jià)模型指導(dǎo)循環(huán)重構(gòu)算法對循環(huán)迭代間的數(shù)據(jù)依賴關(guān)系進(jìn)行重構(gòu)，提高循環(huán)推測并行的效率。此外，Mitosis[13]采用一種預(yù)計(jì)算切片技術(shù)，在循環(huán)推測之前利用數(shù)據(jù)流分析技術(shù)計(jì)算激發(fā)線程所需的預(yù)計(jì)算片段，預(yù)先得到運(yùn)行時(shí)所需的寄存器值，減少數(shù)據(jù)依賴違規(guī)發(fā)生的概率。Zhai等[14]則采用編譯時(shí)激進(jìn)的指令調(diào)度和指令同步技術(shù)，減少指針變量間的關(guān)鍵傳播路徑，優(yōu)化循環(huán)推測性能。

除了以上編譯相關(guān)技術(shù)外，還有不少研究采取編譯時(shí)和運(yùn)行時(shí)兩者相結(jié)合的手段來判定循環(huán)推測時(shí)機(jī)。Gao等[6]先借助于編譯器貪心地選擇同一循環(huán)中多個(gè)不同嵌套層作為候選推測對象，然后利用運(yùn)行時(shí)動態(tài)監(jiān)測到的執(zhí)行延遲和撤銷次數(shù)來最終判定具有最優(yōu)并行性能的循環(huán)嵌套層，從而指導(dǎo)后續(xù)推測對象的選擇。Li等[15]在前者的基礎(chǔ)上，增加了編譯時(shí)的循環(huán)性能評估模型，并在運(yùn)行時(shí)依據(jù)串行執(zhí)行時(shí)間預(yù)測結(jié)果來選擇最優(yōu)的循環(huán)嵌套層，確定循環(huán)推測次序。Luo等[16]側(cè)重于利用硬件機(jī)制構(gòu)建動態(tài)性能監(jiān)測框架，通過分析循環(huán)推測時(shí)一級數(shù)據(jù)緩存的行為特征變化預(yù)測循環(huán)的并行收益大小，以選擇循環(huán)的推測時(shí)機(jī)。部分研究采用循環(huán)特征優(yōu)化技術(shù)改善循環(huán)推測時(shí)機(jī)，文獻(xiàn)[17]利用編譯端生成的“code-bones”指導(dǎo)循環(huán)運(yùn)行時(shí)進(jìn)行動態(tài)重構(gòu)生成高效的循環(huán)推測并行代碼。Shen等[8]則提出采用線程間取值以及亂序提交等相關(guān)技術(shù)降低循環(huán)的各種推測代價(jià)開銷。也有少數(shù)研究完全依賴硬件來判定循環(huán)的推測時(shí)機(jī)，文獻(xiàn)[18]提出了一種名叫Cascadia的動態(tài)推測多線程框架，僅利用運(yùn)行時(shí)監(jiān)測到的IPC作為評估標(biāo)準(zhǔn)，用于指導(dǎo)嵌套循環(huán)推測對象選擇。而Salamanca等[19]則采用硬件事務(wù)內(nèi)存實(shí)現(xiàn)對循環(huán)推測框架的支持，優(yōu)化循環(huán)推測對象的選擇，提升循環(huán)并行性能。

以上循環(huán)級推測方面的研究雖然能帶來不少性能的提升，但存在的問題在于這些研究在確定循環(huán)推測時(shí)機(jī)時(shí)并未考慮硬件資源對候選循環(huán)推測對象自身特征以及不同程序階段特征變化的影響作用，總是假定所有推測對象需求相同的硬件資源。一旦循環(huán)被推測并行，在整個(gè)推測周期內(nèi)需要維護(hù)固定大小的并行粒度，即采用相同數(shù)目的處理器核推測并行，不能根據(jù)自身推測結(jié)果自適應(yīng)調(diào)整處理器資源，減少不合理的推測失敗帶來的額外開銷。

針對此問題，本文提出了一種面向循環(huán)級推測的并行粒度調(diào)節(jié)框架。此框架以推測級為單位，通過對運(yùn)行在不同處理器核上的推測線程進(jìn)行基于硬件的性能剖析之后，構(gòu)建了一個(gè)基于推測代價(jià)的評估模型，量化各推測級的并行收益大小。并將此評估結(jié)果作為循環(huán)并行粒度選擇的依據(jù)，動態(tài)調(diào)整每個(gè)循環(huán)推測對象所需的處理器核資源，優(yōu)化循環(huán)推測時(shí)機(jī)的選擇。

1 執(zhí)行模型和整體框架

在推測系統(tǒng)中，每個(gè)循環(huán)都是在執(zhí)行模型的支持下推測并行。一般地，執(zhí)行模型中僅需維持一個(gè)非推測線程，其他都是處于推測狀態(tài)的線程。其中，非推測線程負(fù)責(zé)維護(hù)程序的串行語義，通過驗(yàn)證和提交直接后繼推測線程的數(shù)據(jù)來保證程序的正確性。驗(yàn)證和提交工作通常在非推測線程執(zhí)行結(jié)束時(shí)進(jìn)行。一旦某后繼推測線程被驗(yàn)證和提交后，非推測線程會將自身的非推測權(quán)限傳遞給它，并釋放所占用的處理器核資源。也就是說，在整個(gè)推測生命周期中，每個(gè)線程的狀態(tài)始終在不斷地變化，并且取決于當(dāng)前整個(gè)循環(huán)的推測上下文環(huán)境。而處于推測狀態(tài)的線程一般有多個(gè)，為了判定其推測程度，本文采用推測級來區(qū)分處于不同推測狀態(tài)的線程對象，并按照線程激發(fā)和分派的次序來確定推測級。非推測線程的推測級最低，其所激發(fā)的直接后繼線程次之，其他后繼線程以此類推。一旦某線程被激發(fā)并分派到某個(gè)處理器核上后，在驗(yàn)證和提交之前并未發(fā)生任何數(shù)據(jù)依賴違規(guī)現(xiàn)象，則認(rèn)為是推測成功；否則若出現(xiàn)數(shù)據(jù)讀后寫現(xiàn)象，需要撤銷當(dāng)前違規(guī)線程及其所有后繼，并利用所得到的正確數(shù)據(jù)進(jìn)行再次推測，保證程序本身的正確性。

圖1給出了本文的整體框架，共分為編譯時(shí)和運(yùn)行時(shí)兩個(gè)階段。編譯階段負(fù)責(zé)選擇候選循環(huán)推測對象，主要借助于編譯時(shí)循環(huán)并行性能預(yù)測手段得到。運(yùn)行階段負(fù)責(zé)對候選循環(huán)進(jìn)行并行粒度調(diào)節(jié)和處理器核的重新分派。共包含五個(gè)模塊。首先，利用處理器核調(diào)度模型為每個(gè)循環(huán)分配所需數(shù)目的處理器核，在循環(huán)推測并行中，采用基于硬件的性能監(jiān)測工具對循環(huán)進(jìn)行性能剖析，并對剖析信息進(jìn)行分析和校正。接著，利用所得到的性能分析結(jié)果，構(gòu)建一個(gè)推測代價(jià)評估模型，并以推測級為單位，對當(dāng)前所采用的并行粒度進(jìn)行量化分析。然后，在循環(huán)并行粒度選擇算法的作用下重新計(jì)算當(dāng)前循環(huán)所需的最優(yōu)并行粒度大小。最后，將調(diào)整后的并行粒度值傳遞給處理器核的動態(tài)調(diào)節(jié)模塊，指導(dǎo)后續(xù)循環(huán)調(diào)用進(jìn)行處理器核的重新分派。

圖1 面向循環(huán)級推測的并行粒度調(diào)節(jié)框架

2 推測代價(jià)評估

2.1 推測級計(jì)算

通常一個(gè)循環(huán)中的所有線程在激發(fā)后總是被分派到相鄰連續(xù)的處理器核上進(jìn)行反復(fù)推測并行。為了標(biāo)識它們，本文引入了推測級的概念。當(dāng)一個(gè)剛激發(fā)線程被分派到某個(gè)處理器核上之后，其推測級的大小采用當(dāng)前激發(fā)線程所在處理器核位置(即處理器核編號)與非推測線程所在處理器核位置兩者之間的差值來計(jì)算：

(1)

其中：curr_cxt和non_spec_cxt分別表示當(dāng)前激發(fā)線程所在處理器核編號和非推測線程所在處理器核編號；max_num_cxt表示所允許并行的處理器核數(shù)目的最大值。本文總是假定非推測線程所屬的推測級的大小為0，而推測線程所屬的推測級的大小取決于當(dāng)前所分派到的處理器核編號。

圖2給出了一個(gè)循環(huán)的執(zhí)行流程片段。圖中T1到T8相當(dāng)于從循環(huán)中激發(fā)的八個(gè)線程對象。假設(shè)T1初始時(shí)處于非推測狀態(tài)，處理器核[P0，P3]取值為[0，3]，則利用以上計(jì)算公式可知，由T1所激發(fā)的直接后繼T2的推測級為1，T3和T4的推測級分別為2和3。在第1節(jié)中提到當(dāng)T1執(zhí)行結(jié)束時(shí)，會向直接后繼傳遞非推測權(quán)限，同時(shí)釋放所占用的處理器核資源。此時(shí)，T4的直接后繼T5會被分派到當(dāng)前T1所在的處理器核上執(zhí)行，依次類推。在這種情況下，隨著循環(huán)迭代次數(shù)的增加，每個(gè)處理器核上會執(zhí)行多個(gè)不同的線程對象，且它們在不同的上下文環(huán)境中會擁有不同的推測級。若要量化當(dāng)前所選并行粒度帶來的性能影響作用，很顯然以處理器核為單位是不合適的，需要以推測級為單位來計(jì)算，對處于相同推測級的所有線程進(jìn)行性能分析和代價(jià)評估，以尋找候選循環(huán)所需的較優(yōu)并行粒度大小。

圖2 推測循環(huán)的執(zhí)行流程

2.2 代價(jià)模型

本文采用Luo等[16]所提出的基于硬件的性能計(jì)數(shù)器對每個(gè)線程進(jìn)行執(zhí)行周期分解，共分解為六個(gè)部分：提交循環(huán)體內(nèi)非推測指令執(zhí)行延遲(Busy)、指令本身執(zhí)行延遲(ExeStall)、取指令執(zhí)行延遲(iFetch)、訪問數(shù)據(jù)緩沖執(zhí)行延遲(dCache)、線程撤銷執(zhí)行延遲(Squash)，以及其他推測帶來的執(zhí)行延遲(Others)。將分解后的結(jié)果與未并行之前的源程序的串行執(zhí)行時(shí)間相比，僅需校正數(shù)據(jù)緩沖執(zhí)行延遲就能得到較為準(zhǔn)確的并行性能預(yù)測結(jié)果。為了預(yù)測每個(gè)推測級中所有線程所帶來的性能開銷，本文又將分解結(jié)果劃分為四大類：基本正類開銷(ObasicPosi,j)、基本負(fù)類開銷(ObasicNegi,k)、推測正類開銷(OspecPosi,l)和推測負(fù)類開銷(OspecNegi,m)。ObasicPosi,j由Busy、ExeStall、iFetch以及dCache中除去所需校正的那部分執(zhí)行延遲四個(gè)部分得到；ObasicNegi,k由Others中線程激發(fā)、線程提交、線程同步以及執(zhí)行因推測而引入的額外指令的執(zhí)行延遲得到；OspecPosi,l由校正訪問數(shù)據(jù)緩沖行為中因推測而減少的那部分開銷得到；Onolimitsi,m由校正訪問數(shù)據(jù)緩沖行為中因推測而增加的那部分開銷得到。因此，一個(gè)推測級中所有線程在推測并行中所帶來的總正向開銷(Onolimitsi)和總負(fù)向開銷(Onegi)可利用式(2)和式(3)計(jì)算得到。

Oposi=∑ObasicPosi,j+∑OspecPosi,l

(2)

Onegi=∑ObasicNegi,k+∑OspecNegi,m

(3)

對于一個(gè)推測級來說，當(dāng)利用以上分解結(jié)果得到所有的正負(fù)開銷之后，則很容易對當(dāng)前并行粒度下此推測級的并行性能進(jìn)行評估。式(4)給出了基于推測級的推測代價(jià)模型。若一個(gè)推測級的總正向開銷大于等于總負(fù)向開銷時(shí)，說明屬于此推測級的線程對象適合在當(dāng)前并行粒度下高效推測并行，此時(shí)認(rèn)為它們能帶來并行收益提升；否則，說明屬于此推測級的線程對象在當(dāng)前并行粒度下不能高效推測并行，與得到的并行收益相比，帶來了過多的額外推測代價(jià)，需要盡量減少這種推測級的存在。

(4)

(5)

本文采用循環(huán)性能登記表來保存每個(gè)循環(huán)所有推測級的代價(jià)評估結(jié)果。表中包含以下表項(xiàng)信息：循環(huán)標(biāo)識符、循環(huán)迭代次數(shù)、當(dāng)前循環(huán)調(diào)用并行粒度大小和上次循環(huán)調(diào)用并行粒度大小、累計(jì)的總正向開銷大小、累計(jì)的總負(fù)向開銷大小、非推測所占比例值以及所預(yù)測的并行收益大小。當(dāng)前循環(huán)調(diào)用并行粒度大小和上次循環(huán)調(diào)用并行粒度大小由第3節(jié)的循環(huán)并行粒度選擇算法計(jì)算得到；循環(huán)并行收益大小主要通過預(yù)測的串行執(zhí)行時(shí)間與實(shí)際得到的并行執(zhí)行時(shí)間兩者的差值計(jì)算得到[16]，其他則利用運(yùn)行時(shí)的性能剖析以及以上代價(jià)評估相關(guān)公式即可得到。

3 循環(huán)并行粒度選擇

每個(gè)循環(huán)在推測并行之前，處理器核調(diào)度機(jī)制需要根據(jù)當(dāng)前循環(huán)所選定的并行粒度大小來分配所需的處理器核資源。為了尋找每個(gè)循環(huán)所需的最優(yōu)并行粒度值，本文引入了一種循環(huán)并行粒度選擇算法，如算法1所示。此算法共包含三種選擇方案：激進(jìn)遞減模式、漸進(jìn)遞減模式和非遞減模式。激進(jìn)遞減模式是一種快速收斂的并行粒度選擇策略，主要利用基于推測級的推測代價(jià)模型對推測級的性能評估結(jié)果來判定所需的并行粒度大小。相應(yīng)地，漸進(jìn)遞減模式是一種相對緩慢的并行粒度選擇策略，主要從相鄰兩次連續(xù)的循環(huán)調(diào)用所估算的并行收益大小的比較結(jié)果來確定所需的并行粒度大小。而在非遞減模式下，此時(shí)不再做任何并行粒度大小的調(diào)整，從而也表明本算法已經(jīng)找到了循環(huán)所需的最優(yōu)并行粒度值。

算法1循環(huán)并行粒度選擇

輸入：循環(huán)性能登記表

輸出：循環(huán)所需的并行粒度大小

1.currLoop←findLoopId(loopId);

2. ifcurrLoop不存在then;

3. returnmax_num_cxt;

4. end if

5.lastAssigned←currLoop.assigned;

6. ifcurrLoop正處于激進(jìn)遞減模式then

7.lastRatio←currLoop.nonspecRatio;

8.currLoop.nonspecRatio←計(jì)算當(dāng)前循環(huán)的nonspecRatio的值；

9. iflastRatio>currLoop.nonspecRatiothen

10.currLoop.lastAssigned←lastAssigned;

11. repeat

12.i←i+1;

13. untilcosti<0;

14. else

15.currLoop進(jìn)入漸進(jìn)遞減模式;

16.currLoop.assigned←currLoop.lastAssigned-1;

17. end if

18. else ifcurrLoop正處于漸進(jìn)遞減模式then

19. ifcurrLoop.lastBenefit≤currLoop.benefitthen

20.currLoop.lastBenefit←currLoop.benefit;

21.currLoop.lastAssigned←lastAssigned;

22.currLoop.assigned←lastAssigned-1;

23. else

24.currLoop進(jìn)入非遞減模式；

25.currLoop.assigned←currLoop.lastAssigned;

26. end if

27. end if

28. returncurrLoop.assigned;

在為循環(huán)選擇并行粒度之前，算法1需要先根據(jù)循環(huán)標(biāo)識符在循環(huán)性能登記表中查找當(dāng)前循環(huán)是否存在。若不存在，表明此循環(huán)從未參與過推測并行，此時(shí)系統(tǒng)會把所有的處理器核資源分配它，即允許該循環(huán)采用最大并行粒度值來推測并行。否則，若當(dāng)前循環(huán)處于激進(jìn)遞減模式下并行，則需根據(jù)運(yùn)行時(shí)執(zhí)行周期分解所收集到的性能剖析信息，采用基于推測級的推測代價(jià)評估結(jié)果來進(jìn)一步判定。如果此次循環(huán)調(diào)用擁有較小的非推測比值，表明當(dāng)前所采用的并行粒度能帶來性能提升，則將繼續(xù)激進(jìn)地對每個(gè)推測級進(jìn)行代價(jià)計(jì)算，直到計(jì)算到不利于推測并行的推測級為止。顯然所保留的推測級的個(gè)數(shù)即為下次循環(huán)調(diào)用時(shí)所需的并行粒度大小。反之，如果此次循環(huán)調(diào)用中非推測比值較大，與之前所得到的結(jié)果相比，證明較優(yōu)的并行粒度取值應(yīng)存在于兩者之間，此時(shí)需要在兩者之間采用漸進(jìn)遞減模式來逐步地逼近到最優(yōu)的并行粒度結(jié)果。在漸進(jìn)遞減模式下，主要側(cè)重于考慮循環(huán)本身得到的并行性能開銷。每次循環(huán)調(diào)用結(jié)束時(shí)，只需與上次循環(huán)調(diào)用計(jì)算得到的并行收益大小進(jìn)行比較即可。若當(dāng)前循環(huán)調(diào)用具有較大的并行收益，表明在此模式下還未找到最優(yōu)的并行粒度結(jié)果，則繼續(xù)遞減當(dāng)前的并行粒度大小。否則，直接在后續(xù)循環(huán)調(diào)用中復(fù)用上次循環(huán)調(diào)用的并行粒度大小即可，此時(shí)整個(gè)循環(huán)也將直接進(jìn)入到非遞減模式下推測并行。

算法1中currLoop表示當(dāng)前采取并行粒度選擇的循環(huán)對象，loopId表示相應(yīng)的循環(huán)標(biāo)識符，函數(shù)findLoopId用于在循環(huán)性能登記表中查找當(dāng)前循環(huán)所需的并行粒度大??；currLoop.assigned和currLoop.lastAssigned分別指當(dāng)前所選擇的并行粒度值和上次循環(huán)調(diào)用得到的并行粒度值，兩者可以從循環(huán)性能登記表中直接得到。而currLoop.nonspecRatio和costi指非推測所占比例值和第i個(gè)推測級的代價(jià)計(jì)算結(jié)果，則可從第2.2節(jié)中計(jì)算獲取到。最后，currLoop.benefit和currLoop.lastBenefit分別表示當(dāng)前循環(huán)調(diào)用和上次循環(huán)調(diào)用所計(jì)算得到的并行收益大小。

當(dāng)一個(gè)循環(huán)的循環(huán)迭代次數(shù)隨著循環(huán)調(diào)用次數(shù)的增加而不斷變化時(shí)，而又由于同一循環(huán)在不同循環(huán)迭代次數(shù)下經(jīng)常展現(xiàn)出不同的并行收益結(jié)果，若僅在算法中包含某次循環(huán)調(diào)用的循環(huán)迭代次數(shù)，將會影響系統(tǒng)對并行粒度大小的正確判定。因此，本文又進(jìn)一步擴(kuò)展了循環(huán)性能登記表，在表中包含了每個(gè)循環(huán)在所有可能的循環(huán)迭代次數(shù)下的相關(guān)性能表項(xiàng)信息。每次循環(huán)調(diào)用時(shí)，先通過查表確定所屬的循環(huán)迭代次數(shù)，再進(jìn)行并行粒度大小的選擇。而對于每種循環(huán)迭代次數(shù)所需的最優(yōu)并行粒度值，可利用循環(huán)并行粒度選擇算法計(jì)算得到。

4 處理器核的動態(tài)調(diào)節(jié)機(jī)制

從循環(huán)并行粒度選擇算法得到所需的并行粒度大小后，需要根據(jù)此結(jié)果來調(diào)整處理器核資源，保證每個(gè)循環(huán)所分派的線程對象能在所允許的推測級上正確地推測并行。算法2給出了相應(yīng)的處理器核映射位置計(jì)算流程。若當(dāng)前循環(huán)的某個(gè)線程對象要激發(fā)并分派其直接后繼對象時(shí)，需要先查循環(huán)性能登記表獲取到當(dāng)前循環(huán)的并行粒度大小。若不存在，從第3節(jié)可知，系統(tǒng)會默認(rèn)當(dāng)前循環(huán)分配到了最大數(shù)目的處理器核資源，即該循環(huán)中所有線程將在所有的處理器核資源推測并行。此時(shí)當(dāng)前線程對象所在處理器核的下一個(gè)相鄰處理器核，將認(rèn)為是即將分派的具體位置。由于處理器核數(shù)目有限，一旦處理器核資源被釋放之后，會立即被后繼其他激發(fā)線程所占用，也就是說，所有的處理器核排成循環(huán)隊(duì)列進(jìn)行資源的循環(huán)利用。

算法2計(jì)算激發(fā)線程映射位置

輸入：循環(huán)性能登記表

輸出：所映射的處理器核編號1.currLoop←findLoopId(loopId);

2. ifcurrLoop不存在then

3. return(curr_cxt+1) modmax_num_cxt;

4. else

5.currAssigned←currLoop.assigned;

6.startID←currLoop.startID;

7.dist←curr_cxt-startID+max_num_cxt;

8.dist←distmodmax_num_cxt;

9.nextDist←(dist+1) modcurrAssigned;

10. return(startID+nextDist)modmax_num_cxt;

11. end if

在算法2中，若當(dāng)前循環(huán)在查找之前已被調(diào)用過，則可在表中找到當(dāng)前循環(huán)所需的并行粒度大小。在這種情況下，剛激發(fā)線程即將映射到的處理器位置需要依據(jù)表中登記的信息來進(jìn)一步確定。首先，從表中得到當(dāng)前循環(huán)所分配到的起始核編號，即當(dāng)前循環(huán)第一個(gè)線程所執(zhí)行的處理器核編號，用于確定處理器核的邊界范圍。接下來，利用當(dāng)前線程所在處理器核和起始核兩者距離的差值來判定推測程度，即獲取到當(dāng)前線程所屬的推測級。再結(jié)合當(dāng)前循環(huán)的并行粒度大小，很容易計(jì)算出其后繼對象所屬的推測級。在此基礎(chǔ)上，有了起始核的邊界限定，再加上當(dāng)前后繼對象的推測級大小，則能很快得到最終所要映射到的處理器核位置。在處理器核映射過程中，至于那些未分派出去的處理器核，本文僅讓其處于空閑狀態(tài)即可。其主要原因在于，這些處理器核并不會對處于推測狀態(tài)的其他核帶來任何性能影響。

5 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證所提出方法的有效性，本文共采用了兩種循環(huán)推測系統(tǒng)，分別是基于CMP的循環(huán)推測系統(tǒng)和基于SMT的循環(huán)推測系統(tǒng)。兩者均采用Open64編譯器來選擇循環(huán)，循環(huán)選擇的策略是性能預(yù)測[5]，首先利用程序剖析技術(shù)得到循環(huán)嵌套信息，控制依賴和數(shù)據(jù)依賴信息，接著根據(jù)這些信息來估算循環(huán)推測并行中所產(chǎn)生的同步代價(jià)和推測失敗代價(jià)，以預(yù)測循環(huán)的并行性能大小，最終以此預(yù)測結(jié)果作為多層嵌套循環(huán)選擇的依據(jù)。由于編譯時(shí)很難得到準(zhǔn)確估算結(jié)果，本文對所有循環(huán)嵌套層進(jìn)行貪心選擇。表1分別給出了CMP和SMT這兩種循環(huán)推測系統(tǒng)的處理器參數(shù)配置信息?；贑MP的循環(huán)推測系統(tǒng)采用SimpleScalar模擬器框架，而基于SMT的循環(huán)推測系統(tǒng)則采用SMTSIM模擬器框架。前者最多允許16個(gè)線程同時(shí)在CMP處理器核上推測并行，即在此推測系統(tǒng)中循環(huán)并行粒度的最大值為16。而后者則最多允許6個(gè)線程同時(shí)在SMT處理器核上推測并行。原因在于，在SMT處理器核上并行的所有線程總是共享相同的處理器核資源，過多的線程數(shù)目會造成激烈的資源競爭，影響整體性能提升。

表 1 處理器配置信息

本文共采用了SPEC CPU基準(zhǔn)測試程序集中的8個(gè)測試程序，分別將它們運(yùn)行在這兩種循環(huán)推測系統(tǒng)中，圖3和圖4分別給出了相應(yīng)的程序加速比計(jì)算結(jié)果。Only Compiler Used指僅采用編譯端的循環(huán)性能預(yù)測結(jié)果作為循環(huán)選擇的依據(jù)，不允許出現(xiàn)多個(gè)循環(huán)嵌套的現(xiàn)象。被選擇的循環(huán)在整個(gè)推測并行期間總是采用相同數(shù)量的處理器核資源直到并行結(jié)束。Compiler Hint允許在編譯端貪心地選擇多個(gè)循環(huán)嵌套層，真正的并行目標(biāo)則依據(jù)運(yùn)行時(shí)循環(huán)性能量化結(jié)果來進(jìn)一步判定[16]。Compiler Hint+Benefit Guided指在前者的基礎(chǔ)上，僅可采用循環(huán)并行粒度選擇算法中的漸進(jìn)遞減模式依據(jù)循環(huán)并行收益大小調(diào)整處理器核資源的數(shù)目。而Ours則采用循環(huán)并行粒度選擇算法中的三種選擇方案共同調(diào)整處理器核資源的數(shù)目。Oracle指在理想情況下假定每個(gè)循環(huán)總是在最優(yōu)的并行粒度作用下所得到的加速比性能。

圖3 基于CMP的循環(huán)級推測的加速比性能比較

圖4 基于SMT的循環(huán)級推測的加速比性能比較

從圖3和圖4可以很容易看出，Only Compiler Used是五種方法中性能提升最少的，此方法主要取決于編譯時(shí)循環(huán)性能預(yù)測的準(zhǔn)確性。由于編譯時(shí)尚未真正并行所有循環(huán)，若選擇不合適的循環(huán)會產(chǎn)生嚴(yán)重性能影響，甚至加速比小于1，即并行執(zhí)行時(shí)間大于串行執(zhí)行時(shí)間。在此方法下crafty、gzip、perlbmk和vortex這四個(gè)程序的加速比值均小于1。而Compiler Hint側(cè)重于利用動態(tài)性能評估手段來確定真正的推測對象。由于運(yùn)行時(shí)很容易監(jiān)測到較準(zhǔn)確的循環(huán)推測特征，且貪心地選擇多個(gè)循環(huán)嵌套層會允許更多的循環(huán)成為候選推測對象。因此，與前者相比，整體性能有了較顯著地提升。Compiler Hint+Benefit Guided在此基礎(chǔ)上能依據(jù)每次循環(huán)調(diào)用的并行收益計(jì)算結(jié)果動態(tài)調(diào)節(jié)所分配的處理器核資源的數(shù)目。主要目的在于減少不合適的并行粒度分配帶來的額外推測代價(jià)開銷，經(jīng)過多次并行粒度調(diào)整后，基于SMT的循環(huán)推測系統(tǒng)均有較大幅度的性能提升。而基于CMP的循環(huán)推測系統(tǒng)由于處理器核的數(shù)目較多，遞減速度較慢，性能提升有限。而Ours則采用了激進(jìn)遞減、漸進(jìn)遞減和非遞減三種方案的組合來選擇并行粒度大小，一方面采用激進(jìn)遞減能有效地加速并行粒度的搜索過程得到快速收斂，另一方面也可以采用漸進(jìn)遞減逐步逼近將要到達(dá)的最優(yōu)并行粒度值。采用此方法后，gcc、mcf、gzip和perlbmk等多數(shù)程序都能取得較高的加速比值。與Compiler Hint相比，CMP和SMT這兩種推測系統(tǒng)在增加了并行粒度調(diào)整后平均加速比值分別提高了約9.43%和20.04%。

并行粒度調(diào)節(jié)方法不僅能有效改善并行循環(huán)的加速比性能，而且對其能耗開銷也有顯著的影響作用。圖5和圖6分別給出了CMP和SMT這兩種循環(huán)推測系統(tǒng)的能耗計(jì)算結(jié)果。能耗大小主要通過在模擬器端集成Wattch能耗分析模型[20]計(jì)算得到。且將收集到的能耗值與原始未并行之前的串行結(jié)果做歸一化對比。

圖5 基于CMP的循環(huán)級推測能耗開銷比較

圖6 基于SMT的循環(huán)級推測能耗開銷比較

從整體上看，由于線程同步、推測指令執(zhí)行延遲以及推測失敗等原因，以上方法計(jì)算得到的能耗值都相對較大一些，且隨著循環(huán)推測性能的改善，明顯呈現(xiàn)遞減的趨勢。結(jié)合圖3和圖4可知，程序的加速比性能和能耗開銷兩者之間還存在密切的關(guān)系。Only Compiler Used是以上所有方法中性能估算最不準(zhǔn)確的，因此，它的加速比值最小，能耗開銷相對來說是最大的。Compiler Hint次之，雖然它能利用動態(tài)性能量結(jié)果總能選擇到性能較優(yōu)的循環(huán)嵌套層，有效地減少了不必要的推測代價(jià)，但卻不能保證所選推測對象在當(dāng)前給定并行粒度作用下充分發(fā)揮了自身潛在的并行性。而Compiler Hint+Benefit Guided和Ours在前者基礎(chǔ)上增加了并行粒度調(diào)節(jié)方法，允許推測對象根據(jù)自身性能自適應(yīng)地調(diào)整并行粒度的大小，優(yōu)化資源配置，減少了不合理的資源分配得到的額外能耗開銷。與Compiler Hint相比，Ours采用激進(jìn)遞減模式能在較短時(shí)間內(nèi)快速搜索到較優(yōu)的并行粒度值，因此，能較大幅度地降低能耗開銷。此外，所有程序在CMP框架下的能耗值要大于其在SMT框架下的能耗值，主要原因在于，基于CMP的循環(huán)推測系統(tǒng)中具有較大的線程基數(shù)，搜索時(shí)間相對較長，且當(dāng)搜索到較優(yōu)并行粒度值時(shí)，處于空閑狀態(tài)的處理器核的數(shù)目較多，也會產(chǎn)生一定的能耗開銷。

圖7對ammp程序的某個(gè)循環(huán)在基于CMP的循環(huán)推測系統(tǒng)中的執(zhí)行情況展開分析。對于當(dāng)前循環(huán)ammp-200來說，按照并行粒度選擇算法的要求，首先為其分配的默認(rèn)值為16，讓它在最大并行粒度值下推測并行。當(dāng)它運(yùn)行結(jié)束時(shí)，根據(jù)推測代價(jià)評估模型計(jì)算性能的正向開銷和負(fù)向開銷。從圖中可知，很明顯在這種情況下總負(fù)向開銷所占比值具有較大值，需要采用激進(jìn)遞減模式立即調(diào)整并行粒度大小。重復(fù)此過程，當(dāng)并行粒度值取10時(shí)，總正向開銷和總負(fù)向開銷所占比值相當(dāng)，且非推測所占比值下降到最低點(diǎn)，此時(shí)加速比值取得最大值。若繼續(xù)遞減，可從圖中觀察到非推測所占比值會逐步上升，而加速比值卻在快速下降，表明當(dāng)前循環(huán)中很多激發(fā)線程因缺乏足夠的處理器核資源不得不推遲推測時(shí)機(jī)，降低了其本身的并行性。因此，合理選擇循環(huán)并行粒度大小在整個(gè)循環(huán)推測過程中至關(guān)重要。

圖7 ammp-200的并行粒度調(diào)節(jié)結(jié)果

6 結(jié) 語

本文提出一種基于推測代價(jià)評估的推測多線程并行粒度調(diào)節(jié)方法。此方法不以處理器核為單位，而是以推測級為單位，依據(jù)基于硬件的性能剖析技術(shù)所得到的循環(huán)性能剖析結(jié)果，構(gòu)建推測代價(jià)評估模型用于量化不同推測級在所選并行粒度作用下所帶來的正向和負(fù)向性能代價(jià)開銷。并將此代價(jià)評估結(jié)果作為循環(huán)并行粒度選擇的重要判定依據(jù)。在激進(jìn)遞減、漸進(jìn)遞減和非遞減三種選擇策略共同作用下，實(shí)現(xiàn)循環(huán)并行粒度的自適應(yīng)調(diào)整和處理器核資源的動態(tài)調(diào)節(jié)。實(shí)驗(yàn)結(jié)果表明，自適應(yīng)的并行粒度選擇不僅能揭示出程序潛在的并行性，而且能有效地減少不必要的推測失敗所帶來的額外能耗開銷。