李美蓉 趙銀亮

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

0 引 言

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

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

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

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

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

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

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

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

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

2 推測代價評估

2.1 推測級計算

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

(1)

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

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

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

2.2 代價模型

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

Oposi=∑ObasicPosi,j+∑OspecPosi,l

(2)

Onegi=∑ObasicNegi,k+∑OspecNegi,m

(3)

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

(4)

(5)

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

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

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

7.lastRatio←currLoop.nonspecRatio;

8.currLoop.nonspecRatio←計算當前循環(huán)的nonspecRatio的值；

9. iflastRatio>currLoop.nonspecRatiothen

10.currLoop.lastAssigned←lastAssigned;

11. repeat

12.i←i+1;

13. untilcosti<0;

14. else

15.currLoop進入漸進遞減模式;

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

17. end if

18. else ifcurrLoop正處于漸進遞減模式then

19. ifcurrLoop.lastBenefit≤currLoop.benefitthen

20.currLoop.lastBenefit←currLoop.benefit;

21.currLoop.lastAssigned←lastAssigned;

22.currLoop.assigned←lastAssigned-1;

23. else

24.currLoop進入非遞減模式；

25.currLoop.assigned←currLoop.lastAssigned;

26. end if

27. end if

28. returncurrLoop.assigned;

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

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

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

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

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

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

5 實驗結果

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

表 1 處理器配置信息

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

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

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

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

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

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

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

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

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

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

6 結 語

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