馬巧梅

寶雞文理學(xué)院 計(jì)算機(jī)學(xué)院，陜西 寶雞 721016

1 引言

按照摩爾定律[1-2]，半導(dǎo)體的發(fā)展已經(jīng)從單核時(shí)代轉(zhuǎn)變?yōu)槎嗪藭r(shí)代，如何加速串行程序，從而充分合理地利用豐富的核資源成為一個(gè)研究目標(biāo)。線程級(jí)推測(cè)（thread-level speculation，TLS）[3-4]能夠自動(dòng)將串行程序以激進(jìn)的方式劃分為多個(gè)線程，并允許線程間存在模糊控制依賴和數(shù)據(jù)依賴，多個(gè)線程在一個(gè)CMP（chip multiprocessor）上同時(shí)執(zhí)行，從而挖掘程序的線程級(jí)并行性。各種新的線程級(jí)推測(cè)方案應(yīng)運(yùn)而生，典型的方案包含Stanford大學(xué)研發(fā)的Hydra[5]、Wisconsin大學(xué)研發(fā)的Multiscalar[6]、UIUC研發(fā)的線程級(jí)推測(cè)系統(tǒng)POSH[7]、國(guó)防科技大學(xué)開(kāi)發(fā)的SMA（speculative multi-threading architecture）系統(tǒng)[8]、卡耐基梅隆大學(xué)的STAMPede[9]、Intel Barcelona研究院提出的Mitosis[10-11]、日本NEC公司的推測(cè)多線程系統(tǒng)Pinot[12]以及 Prophet[13-15]等。

線程劃分方法對(duì)程序加速比提升至關(guān)重要。傳統(tǒng)的線程劃分多采用啟發(fā)式規(guī)則進(jìn)行。文獻(xiàn)[16]在綜合考慮線程劃分的各種開(kāi)銷情況下使用一系列平衡最小割來(lái)劃分程序，且在每次分割之后調(diào)整程序控制流圖邊的權(quán)重。文獻(xiàn)[17]在給定計(jì)算架構(gòu)情況下定量比較不同的劃分算法，提出了一個(gè)新的動(dòng)態(tài)劃分算法Mex-slicing，雖然該算法整體性能超過(guò)其他動(dòng)態(tài)劃分算法，但在可預(yù)測(cè)性和代價(jià)方面難以達(dá)到平衡。然而，上述這些根據(jù)人工經(jīng)驗(yàn)知識(shí)得來(lái)的啟發(fā)式規(guī)則具有很大的局限性，且在指導(dǎo)線程劃分中往往對(duì)所用待劃分程序使用一套啟發(fā)式規(guī)則，導(dǎo)致單純地依靠啟發(fā)式規(guī)則進(jìn)行線程劃分，很難得到最優(yōu)線程劃分結(jié)果，而只能得到經(jīng)驗(yàn)上較優(yōu)的線程劃分結(jié)果。

為解決傳統(tǒng)啟發(fā)式規(guī)則在TLS中存在的不足，機(jī)器學(xué)習(xí)方法被成功引入到TLS中。文獻(xiàn)[18]提出一個(gè)可移動(dòng)編譯器利用機(jī)器學(xué)習(xí)方法匹配程序的并行性到多核處理器的方法，并開(kāi)發(fā)了兩個(gè)預(yù)測(cè)器，一個(gè)數(shù)據(jù)敏感的和一個(gè)數(shù)據(jù)不敏感的來(lái)為并行程序選擇最好的匹配。文獻(xiàn)[19]開(kāi)發(fā)了一個(gè)為數(shù)據(jù)并行應(yīng)用在出現(xiàn)額外負(fù)載情況下預(yù)測(cè)最優(yōu)線程數(shù)據(jù)的方法，并且開(kāi)發(fā)了一個(gè)綜合模型來(lái)減小額外負(fù)載的影響，提升平均加速比。文獻(xiàn)[20]提出一個(gè)基于學(xué)習(xí)的方法以代價(jià)敏感的方式分配并行的負(fù)載到計(jì)算平臺(tái)，該方法在決定負(fù)載分配之前用靜態(tài)程序特征來(lái)聚類程序。上述機(jī)器學(xué)習(xí)在TLS中的應(yīng)用主要集中在匹配、預(yù)測(cè)、負(fù)載分配等方面，而很少用于線程劃分。

本文提出利用機(jī)器學(xué)習(xí)方法從TLS樣本集中學(xué)習(xí)線程劃分知識(shí)，并根據(jù)新程序的特征預(yù)測(cè)其劃分方案，與傳統(tǒng)基于啟發(fā)式規(guī)則的線程劃分進(jìn)行了對(duì)比，探討了本文方法在線程劃分方面的優(yōu)勢(shì)。

2 執(zhí)行模型和啟發(fā)點(diǎn)

2.1 TLS執(zhí)行模型

TLS實(shí)現(xiàn)將串行程序并行化，并在多核平臺(tái)上并行執(zhí)行，從而提高加速比性能。圖1給出了TLS執(zhí)行模型[21-22]，在該模型中線程激發(fā)點(diǎn)（spawning point，sp）和準(zhǔn)控制無(wú)關(guān)點(diǎn)（control quasi-independent point，cqip）指令把串行程序映射成多線程程序。依據(jù)串行語(yǔ)義，在每一時(shí)刻只有一個(gè)線程允許提交數(shù)據(jù)到內(nèi)存，這個(gè)線程被稱作確定線程，而其他線程稱作推測(cè)線程（speculative thread）。各個(gè)推測(cè)線程由兩部分組成，即預(yù)計(jì)算片段（precomputation-slice，p-slice）和串行程序代碼。p-slice是一小段代碼，該代碼是由編譯器依據(jù)切片技術(shù)生成的，來(lái)預(yù)測(cè)推測(cè)線程中使用的live-ins（在定值之前還要被引用的變量集）。圖1顯示了SpMT執(zhí)行的4種情況。在圖1（a）中，推測(cè)多線程程序因?yàn)楹雎詓p-cqip，所以等同串行執(zhí)行程序。在圖1（b）中顯示的是推測(cè)執(zhí)行成功的情況：當(dāng)確定線程T1執(zhí)行到sp時(shí)，如果存在閑置的核資源，新推測(cè)線程T2被激發(fā)；否則，T2不被激發(fā)。當(dāng)T1執(zhí)行到cqip，將驗(yàn)證T2在p-slice中使用的live-ins。如果驗(yàn)證正確，則T1提交執(zhí)行結(jié)果，并釋放核資源。然后，確定執(zhí)行的權(quán)限從T1傳遞給T1直接后繼線程。圖1（c）給出T2驗(yàn)證失敗，推測(cè)執(zhí)行失敗，從而撤銷T2，預(yù)計(jì)算片段不被執(zhí)行的情況。圖1（d）給出了出現(xiàn)讀后寫（read after write，RAW）依賴違規(guī)時(shí)，在當(dāng)前狀態(tài)下重新啟動(dòng)該線程的情況。

Fig.1 TLS execution model圖1 TLS執(zhí)行模型

2.2 啟發(fā)點(diǎn)

圖2顯示了Olden基準(zhǔn)程序集[23]中health（）過(guò)程同一子過(guò)程13個(gè)劃分方案和過(guò)程加速比對(duì)應(yīng)圖。橫坐標(biāo)代表同一子過(guò)程的13種劃分方案，縱坐標(biāo)代表對(duì)應(yīng)的加速比。劃分方案用一個(gè)五維向量表示，該向量的組成將在第4章給出。圖2給出的啟發(fā)就是：過(guò)程的劃分方案影響著過(guò)程劃分后獲得的加速比。如何根據(jù)程序特征預(yù)測(cè)其劃分方案成為本文的一個(gè)研究目的。

Fig.2 13 partition schemes and speedups of procedures in health()圖2 health（）中13個(gè)過(guò)程劃分方案與過(guò)程加速比

3 劃分方法框架

將一個(gè)串行的程序劃分成為一個(gè)能夠并行執(zhí)行的多線程程序時(shí)，首先要提取程序特征，根據(jù)其特征獲取較優(yōu)的劃分方案，然后根據(jù)劃分方案進(jìn)行線程劃分。

圖3給出了基于程序特征的線程劃分框架圖。其中，虛線框顯示了KNN（K-nearest neighbor）算法從訓(xùn)練樣本中學(xué)習(xí)線程劃分知識(shí)，從而構(gòu)建預(yù)測(cè)模型的過(guò)程。預(yù)測(cè)模型構(gòu)建完成，通過(guò)待劃分程序的特征作為模型的輸入，預(yù)測(cè)出該程序的劃分方案，并在Prophet系統(tǒng)[14-15]中指導(dǎo)其劃分，生成多線程程序。然后在模擬器上完成評(píng)測(cè)，輸出程序結(jié)果和加速比值。

Fig.3 Scheme of thread partitioning based on program characteristics圖3 基于程序特征的線程劃分框架圖

該框架由5個(gè)主要部分構(gòu)成，分別是：

（1）程序特征的表達(dá)；

（2）劃分方案的表達(dá)；

（3）預(yù)測(cè)模型的構(gòu)建；

（4）線程劃分過(guò)程；

（5）實(shí)驗(yàn)評(píng)測(cè)。

下面將在劃分方案中分別描述5個(gè)組成部分。

4 劃分方案

4.1 程序特征的表達(dá)

基于程序特征的線程劃分方法需要由Prophet系統(tǒng)的profiler統(tǒng)計(jì)程序運(yùn)行時(shí)的信息，從而獲取其特征信息。如果指令是分支指令，則根據(jù)跳轉(zhuǎn)是否為循環(huán)回跳分別進(jìn)行處理，若是常規(guī)跳轉(zhuǎn)，將本次跳轉(zhuǎn)情況更新。若是回邊跳轉(zhuǎn)，則由當(dāng)前跳轉(zhuǎn)跨越的動(dòng)態(tài)指令數(shù)M與歷史記錄中的平均動(dòng)態(tài)指令數(shù)LD-1以及總迭代次數(shù)D計(jì)算循環(huán)平均動(dòng)態(tài)指令數(shù)LD；其次，如果該指令是過(guò)程返回指令，則由當(dāng)前函數(shù)本次調(diào)用的動(dòng)態(tài)指令數(shù)S與歷史記錄中的平均動(dòng)態(tài)指令數(shù)NC-1，以及總調(diào)用次數(shù)C計(jì)算平均動(dòng)態(tài)指令數(shù)NC；最后，profiler將結(jié)果注釋在該函數(shù)的profile信息探針函數(shù)對(duì)應(yīng)的信息域。

圖4顯示了profiler提取的特征初始存儲(chǔ)結(jié)構(gòu)。其中，c是動(dòng)態(tài)指令數(shù)，l是循環(huán)分支概率，b是分支概率，d1是分支指令個(gè)數(shù)，d2是跳轉(zhuǎn)指令個(gè)數(shù)，d3是加法/減法指令個(gè)數(shù)，d4是乘法/除法指令個(gè)數(shù)，n是程序基本塊個(gè)數(shù)。矩陣M中每一個(gè)元素是一個(gè)特征向量，該向量包括動(dòng)態(tài)指令數(shù)、循環(huán)分支概率、分支概率、分支指令個(gè)數(shù)、跳轉(zhuǎn)指令個(gè)數(shù)、加法/減法指令個(gè)數(shù)、乘法/除法指令個(gè)數(shù)和程序基本塊個(gè)數(shù)。

Fig.4 Expression of program characteristics圖4 程序特征表示

本文采用靜態(tài)和動(dòng)態(tài)特征來(lái)代表輸入樣本程序，為了方便計(jì)算歐氏距離，選用x1~x8這8個(gè)變量來(lái)分別代表樣本程序的特征，具體使用的特征變量以及它們的描述在表1中給出。

Table 1 Used characteristics and their descriptions表1 使用的特征和特征描述

4.2 劃分方案的表達(dá)

劃分方案的提取過(guò)程采用現(xiàn)有Prophet線程劃分[24]中非循環(huán)劃分和循環(huán)劃分算法提取。劃分算法（非循環(huán)劃分、循環(huán)劃分）的執(zhí)行流程可以用圖5中流程簡(jiǎn)圖進(jìn)行描述。從圖5中可以看出，線程粒度的上限（upper limit of thread granularity，ULoTG）、線程粒度的下限（lower limit of thread granularity，LLoTG）、依賴數(shù)（data dependence count，DDC）、激發(fā)距離的上限（upper limit of spawning distance，ULoSD）、激發(fā)距離的下限（lower limit of spawning distance，LLoSD）直接影響著線程劃分的過(guò)程，其中決策1和決策2是指不同的劃分決策（比如激發(fā)新線程、循環(huán)展開(kāi)、重新劃分等）。如果線程劃分過(guò)程中對(duì)新線程的劃分可以歸結(jié)為一個(gè)決策問(wèn)題，那么這5個(gè)閾值是決定該問(wèn)題答案的直接因素?？梢缘贸鲆粋€(gè)結(jié)論：5個(gè)閾值的變化直接影響著劃分的決策，從而影響著劃分的結(jié)果。因此基于此本文選定這5個(gè)閾值作為優(yōu)化的參數(shù)。

Fig.5 Flow chart of extracting partition schemes圖5 提取劃分方案的流程圖

劃分方案用H==表達(dá)。其中，LLoTG、ULoTG、DDC、LLoSD、ULoSD是線程劃分過(guò)程中影響劃分效果的5個(gè)主要參數(shù)。

4.3 預(yù)測(cè)模型的構(gòu)建

預(yù)測(cè)劃分方案的流程一般是首先獲取線程級(jí)推測(cè)的樣本集，然后當(dāng)一個(gè)新的程序?qū)⒁獎(jiǎng)澐謺r(shí)，首先提取程序中各個(gè)過(guò)程的特征，然后運(yùn)用KNN方法從樣本集預(yù)測(cè)將要?jiǎng)澐殖绦虻膭澐址桨浮?/p>

樣本集可以形式化表示為T={Xorig-i,Hpar-i}(i∈1,2,…,N)，在樣本集中，每個(gè)訓(xùn)練樣本都是由程序過(guò)程的特征向量Xorig和它所對(duì)應(yīng)的近似最佳劃分方案Hpar組成。每個(gè)特征向量Xorig=[x1,x2,…,xn]對(duì)應(yīng)于N維空間中的一個(gè)點(diǎn)，每個(gè)近似最優(yōu)的劃分結(jié)構(gòu)Hpar也是由一組參數(shù)組成，即Hpar=[h1,h2,h3,h4,h5]，其中h1表示線程粒度的下限，h2表示線程粒度的上限，h3表示數(shù)據(jù)依賴數(shù)，h4表示激發(fā)距離的下限，h5表示激發(fā)距離的上限。

當(dāng)兩個(gè)過(guò)程具有相同的特征，那么這兩個(gè)過(guò)程就要有相同的劃分方案，這是預(yù)測(cè)劃分方案的前提條件。基于KNN的劃分方案的預(yù)測(cè)，首先需要構(gòu)建預(yù)測(cè)模型，所有的訓(xùn)練樣本都存儲(chǔ)在訓(xùn)練樣本中，構(gòu)成了一個(gè)KNN預(yù)測(cè)模型?；贙NN的分類方法只是簡(jiǎn)單地把所有的訓(xùn)練樣本存儲(chǔ)起來(lái)，樣本的分類延遲到一個(gè)新的樣本需要分類的時(shí)候。當(dāng)一個(gè)新的程序需要?jiǎng)澐謺r(shí)，首先提取程序的特征，然后找到距離它最近的K個(gè)樣本，這里的距離公式使用的是歐氏距離，如式（1）所示。

式中，n表示特征向量的維數(shù)；xrj和xir分別代表xj和xi的第r個(gè)屬性值。

當(dāng)找到了K個(gè)最近鄰樣本，為了保證預(yù)測(cè)模型的正確性，輸入程序的過(guò)程類標(biāo)簽由K個(gè)最近鄰的類標(biāo)簽與它們的權(quán)重相乘并且相加起來(lái)得到。距離待劃分過(guò)程越近的過(guò)程，給它所賦予的權(quán)重就越大，而且要隨著特征向量間的距離增大，權(quán)重必須迅速衰減，但總權(quán)重必須為1。為了給K個(gè)最近鄰的類標(biāo)簽分配權(quán)值，引入了式（2），它是指數(shù)級(jí)函數(shù)ex的麥克勞林級(jí)數(shù)。

式（2）中的x設(shè)定為1，然后再把公式兩邊除以e，就會(huì)獲得式（3）：

基于式（3），可以推出分配的權(quán)重公式如下所示：

式（4）中的i表示待劃分的過(guò)程與K個(gè)最近鄰樣本距離遠(yuǎn)近的順序標(biāo)號(hào)。距離越近分配的權(quán)重越大，因?yàn)槭褂玫氖荗lden測(cè)試集，樣本集數(shù)量并不是很多，所以把K個(gè)最近鄰樣本中的K值設(shè)定為10，即只考慮距離待劃分過(guò)程的最近10個(gè)過(guò)程，加權(quán)求取待劃分過(guò)程的方案。

由于目標(biāo)函數(shù)Hpar是線程的劃分方案，其類標(biāo)簽對(duì)應(yīng)的是5個(gè)閾值。對(duì)于一個(gè)待劃分的過(guò)程xq，其類標(biāo)簽是K個(gè)最近鄰過(guò)程的類標(biāo)簽與它們各自的權(quán)重值之積并且相加，如式（5）所示：

式（5）中h?j(xq)表示待劃分過(guò)程的劃分方案的第j個(gè)閾值；hj(xi)表示在訓(xùn)練樣本中距離待劃分過(guò)程的由近及遠(yuǎn)順序的第i個(gè)過(guò)程的第j個(gè)閾值；weight(i)則是第i個(gè)過(guò)程的權(quán)重公式。

算法1基于KNN的劃分方案的預(yù)測(cè)算法

輸入：訓(xùn)練樣本（X代表特征向量，H代表劃分框架），xq新程序特征向量。

4.4 線程劃分過(guò)程

對(duì)于一個(gè)待劃分程序，已經(jīng)獲取其劃分方案，接下來(lái)就是運(yùn)用劃分方案進(jìn)行線程劃分。線程劃分是在程序的CFG（control flow graph）上進(jìn)行的。首先需要對(duì)程序的循環(huán)區(qū)域進(jìn)行劃分，循環(huán)區(qū)域劃分情況比較復(fù)雜，因?yàn)檠h(huán)可以分為內(nèi)層循環(huán)和外層循環(huán)，需要對(duì)它們分別進(jìn)行線程劃分。當(dāng)完成對(duì)循環(huán)區(qū)域線程劃分后，接下來(lái)就是將程序CFG中的循環(huán)區(qū)域歸結(jié)成超級(jí)塊，則原來(lái)的程序CFG變成了SCFG（super control flow graph）。然后在SCFG選取推測(cè)路徑，根據(jù)代價(jià)評(píng)估模型對(duì)非循環(huán)區(qū)域進(jìn)行線程劃分。最后還需要為每個(gè)已劃分好的線程構(gòu)造預(yù)計(jì)算片段，最終完成對(duì)程序的線程劃分。線程劃分的加速過(guò)程如圖6所示。

Fig.6 Effect of thread level speculation圖6 線程級(jí)推測(cè)加速效果

4.5 代價(jià)評(píng)估模型

在建立代價(jià)模型時(shí)，需要假設(shè)存在無(wú)限個(gè)處理器核數(shù)，這樣就不用考慮因處理器核數(shù)不足而產(chǎn)生線程撤銷問(wèn)題。在Prophet編譯系統(tǒng)中，每條指令只占一個(gè)時(shí)鐘周期，因此程序片段的執(zhí)行時(shí)間可以用片段中包含的指令條數(shù)表示。在一個(gè)線程執(zhí)行過(guò)程中，激發(fā)一個(gè)新的線程，激發(fā)路徑上有3條相關(guān)指令，如圖6所示。當(dāng)這兩個(gè)線程并行推測(cè)執(zhí)行時(shí)，即父線程在一個(gè)處理器核上執(zhí)行，子線程在另外一個(gè)處理器核上執(zhí)行時(shí)，子線程首先需要執(zhí)行預(yù)計(jì)算片段，預(yù)計(jì)算長(zhǎng)度表示為pslice，父線程到子線程的激發(fā)距離為sp_dis，激發(fā)路徑上包含的相關(guān)指令條數(shù)為dep_cnt，那么pslice可以用dep_cnt+C來(lái)表示，其中C表示創(chuàng)建預(yù)計(jì)算片段的開(kāi)銷。從圖6可以得出子線程的提取執(zhí)行時(shí)間，如式（6）所示：

式（6）只能體現(xiàn)出局部的加速效果，如果想得到全局的加速效果，即得到每條指令加速效果，則需要對(duì)提前的時(shí)間除以推測(cè)線程的指令條數(shù)。對(duì)于非循環(huán)區(qū)域劃分評(píng)價(jià)的定義如式（7）所示：

式中，w為權(quán)重因子；thread_size為推測(cè)線程的指令條數(shù)；evalue為評(píng)估值。

針對(duì)非循環(huán)區(qū)域劃分，首先提取程序的各個(gè)過(guò)程的特征，運(yùn)用機(jī)器學(xué)習(xí)的方法從已構(gòu)建好的TLS樣本集中預(yù)測(cè)程序的各個(gè)過(guò)程較優(yōu)的劃分方案，而預(yù)測(cè)的劃分方案由LLoTG、ULoTG、DDC、LLoSD、ULoSD組成。劃分方案就是對(duì)候選線程的一組約束條件，對(duì)程序進(jìn)行線程劃分過(guò)程中，候選線程需要滿足線程粒度、數(shù)據(jù)依賴數(shù)和激發(fā)距離這一組約束條件，并在滿足約束條件的情況下，每次劃分都是選擇evalue值最大的點(diǎn)作為線程劃分的邊界。

4.6 循環(huán)劃分

在開(kāi)始對(duì)循環(huán)區(qū)域進(jìn)行劃分之前，首先需要?dú)w結(jié)循環(huán)區(qū)域?yàn)橐粋€(gè)超級(jí)塊，如圖7所示。圖7（a）中各個(gè)節(jié)點(diǎn)代表基本塊，節(jié)點(diǎn)5→6→8→7→…→5→…是一個(gè)循環(huán)結(jié)構(gòu)，可以歸結(jié)為一個(gè)超級(jí)節(jié)點(diǎn)（即圖（b）中灰色節(jié)點(diǎn)5′）。在循環(huán)歸結(jié)后，本文開(kāi)展循環(huán)的劃分。為了充分挖掘循環(huán)區(qū)域的并行，對(duì)循環(huán)部分實(shí)行多處劃分。本文對(duì)循環(huán)的劃分分為兩類，即循環(huán)嵌套迭代劃分和循環(huán)內(nèi)部劃分。對(duì)于循環(huán)嵌套迭代，本文使用順序激發(fā)方式對(duì)其進(jìn)行劃分，即第i次循環(huán)迭代激發(fā)第i+1循環(huán)迭代(i∈N)。如果循環(huán)包含的指令條數(shù)較多，使用非循環(huán)劃分方法進(jìn)行劃分。

算法2循環(huán)區(qū)域劃分算法

輸入：循環(huán)入口節(jié)點(diǎn)。

輸出：已劃分的循環(huán)區(qū)域。

Fig.7 Progress of thread partitioning圖7 線程劃分過(guò)程

圖8是一個(gè)循環(huán)劃分示意圖，用于解釋循環(huán)區(qū)域劃分算法。如果循環(huán)體大于線程粒度上限h2，對(duì)循環(huán)體執(zhí)行非循環(huán)的劃分；如果是嵌套循環(huán)，首先找出最可能路徑，計(jì)算最優(yōu)依賴opt_ddc，表達(dá)內(nèi)層循環(huán)的指令數(shù)為size_of_loop以及激發(fā)距離spawn_dis；如果opt_ddc小于依賴數(shù)閾值h3，且size_of_loop取值在[h1,h2]之內(nèi)，spawn_dis在[h4,h5]之內(nèi)時(shí)，創(chuàng)建一個(gè)新線程。圖8中包含了內(nèi)層循環(huán)和外層循環(huán)，循環(huán)嵌套迭代顯示在虛線框里，而外層循環(huán)部分包含了較多的指令條數(shù)。為了挖掘程序的潛在并行性，本文在循環(huán)多處進(jìn)行劃分，如果循環(huán)體過(guò)小，循環(huán)需要展開(kāi)，然后按照非循環(huán)劃分方法對(duì)展開(kāi)的循環(huán)進(jìn)行劃分。最后識(shí)別回邊，歸結(jié)循環(huán)區(qū)域?yàn)閮?nèi)部循環(huán)，并對(duì)循環(huán)中連續(xù)迭代間數(shù)據(jù)依賴數(shù)進(jìn)行檢查，如果在下一次循環(huán)迭代處開(kāi)始一個(gè)線程是有利的，則在下一次循環(huán)迭代處創(chuàng)建一個(gè)新的線程。

Fig.8 Diagram of loop partitioning圖8 循環(huán)劃分示意圖

圖8中的虛線框部分經(jīng)過(guò)循環(huán)歸結(jié)，歸結(jié)成一個(gè)節(jié)點(diǎn)，得到一個(gè)以節(jié)點(diǎn)1為循環(huán)的開(kāi)始節(jié)點(diǎn)和以6→1為回邊的外層循環(huán)區(qū)域。如果拿掉回邊6→1，就得到一個(gè)非循環(huán)區(qū)域，這種情況使用非循環(huán)線程劃分方法進(jìn)行劃分。

4.7 非循環(huán)劃分

算法3非循環(huán)區(qū)域的劃分算法

在該代碼中，curr_thread代表當(dāng)前候選線程子圖，是當(dāng)前線程開(kāi)始基本塊（start_block）與上一個(gè)候選線程結(jié)束點(diǎn)之間的基本塊集合。由于數(shù)據(jù)依賴過(guò)大或者線程體太小，curr_thread中子圖不能單獨(dú)作為一個(gè)線程；如果start_block和上一線程end_block重合，則curr_thread為空。start_block的最近后向支配節(jié)點(diǎn)用pdom_block表示，start_block和pdom_block之間的推測(cè)路徑子圖用path表示。線程劃分過(guò)程中參考線程子圖中粒度和激發(fā)距離。線程子圖的粒度根據(jù)最大閾值h2和最小閾值h1，分為在粒度適中、粒度偏大、粒度偏小3種情況下如何劃分非循環(huán)區(qū)域。在圖9中，假設(shè)線程劃分的關(guān)鍵路徑是0—1—3—4—5—6。

（1）如果當(dāng)前線程（0—1）粒度在區(qū)間 [h1,h2]之內(nèi)，且激發(fā)距離在區(qū)間[h4,h5]之內(nèi)，并且它和后繼線程的數(shù)據(jù)依賴度不大于依賴數(shù)上限h3，則創(chuàng)建一個(gè)新的線程，如圖9（a）所示。

（2）如果當(dāng)前線程粒度偏大，即粒度在區(qū)間[h2,+∞)，則需要二次劃分start_block和pdom_block間的區(qū)域。對(duì)于基本塊0、1和2構(gòu)成的子圖，如果基本塊0的粒度在[h1,h2]之內(nèi)，并且與基本塊1到future_thread之間區(qū)域數(shù)據(jù)依賴數(shù)小于h3，則可以在基本塊1開(kāi)始處創(chuàng)建一個(gè)新線程，如圖9（b）所示。

（3）如果當(dāng)前線程粒度偏小，即粒度在區(qū)間(0,h1]，那么加入curr_thread子圖中的有path及pdom_block，同時(shí)分析劃分pdom_block的后向支配節(jié)點(diǎn)到end_block之間的域。此時(shí)，如果線程粒度和數(shù)據(jù)依賴度都符合要求，那么就在基本塊5的開(kāi)始處創(chuàng)建新線程，如圖9（c）所示。

5 實(shí)驗(yàn)評(píng)測(cè)

5.1 基準(zhǔn)程序

本文主要使用Olden基準(zhǔn)程序[24]作為測(cè)試用例，Olden測(cè)試集是Princeton大學(xué)提供的開(kāi)源的C語(yǔ)言程序測(cè)試包。Olden測(cè)試集不是以數(shù)值計(jì)算為主的應(yīng)用程序，其中包含了鏈表、樹(shù)、圖等各種比較復(fù)雜的控制流結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)，并行編譯器很難把這種非規(guī)則的程序自動(dòng)并行化，而且Olden測(cè)試集是開(kāi)源的代碼，獲取比較容易，因此選擇Olden作為測(cè)試程序。Olden基準(zhǔn)測(cè)試程序如表2描述。

Table 2 Descriptions of Olden benchmarks表2 Olden基準(zhǔn)程序描述

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

Fig.9 Diagram of nonloop partition圖9 非循環(huán)劃分示意圖

基于程序特征的線程劃分方法，首先需要提取程序各個(gè)過(guò)程的特征，然后在已構(gòu)建好的樣本集中學(xué)習(xí)線程的劃分方案，最后運(yùn)用劃分方案對(duì)程序進(jìn)行線程劃分。本文使用Olden測(cè)試集中程序的每個(gè)過(guò)程作為樣本，通過(guò)對(duì)程序中每個(gè)過(guò)程的特征組建，得到每個(gè)過(guò)程的特征向量，然后運(yùn)用專家經(jīng)驗(yàn)顯示劃分的方法，獲取程序中每個(gè)過(guò)程的最佳劃分方案，這樣樣本就以“特征向量+劃分方案”形式表示，將所有的樣本組合到一起就構(gòu)成了樣本集。

本文采用KNN算法獲取待劃分程序中每個(gè)過(guò)程的劃分方案。因?yàn)闇y(cè)試集和訓(xùn)練集使用相同的樣本集，所以使用“留一法”對(duì)機(jī)器學(xué)習(xí)進(jìn)行有效性驗(yàn)證。所謂的“留一法”就是當(dāng)測(cè)試Olden中的某個(gè)樣本時(shí)，這個(gè)樣本不能從樣本集中直接獲取，只能通過(guò)機(jī)器學(xué)習(xí)從其他樣本中預(yù)估得到。下面將以O(shè)lden中mst基準(zhǔn)測(cè)試程序?yàn)槔?，展示預(yù)測(cè)mst程序中的每個(gè)過(guò)程的劃分方案（依次表示線程間依賴數(shù)、線程粒度下限、線程粒度上限、激發(fā)距離上限、激發(fā)距離下限），如表3所示。首先剔除樣本集中mst程序的每個(gè)過(guò)程的樣本，避免加載自身的最優(yōu)劃分方案，然后提取mst程序中的每個(gè)過(guò)程的特征，從樣本集中學(xué)習(xí)得到每個(gè)過(guò)程的預(yù)測(cè)劃分方案。

Table 3 Partition schemes of samples and predictive partition schemes表3 樣本中的劃分方案與預(yù)測(cè)的劃分方案

接下來(lái)將用預(yù)測(cè)的劃分方案進(jìn)行線程劃分，為了說(shuō)明方便，以mst基準(zhǔn)測(cè)試程序的HashDelete過(guò)程為例，進(jìn)行線程劃分結(jié)果的展示。從預(yù)測(cè)劃分方案可知，劃分的線程間最大依賴數(shù)為3，線程粒度下限為9，線程粒度上限為45，激發(fā)距離下限為4，激發(fā)距離上限為20，其展示如圖10所示。

Fig.10 Partition diagram of HashDelete in mst圖10 mst的HashDelete過(guò)程的劃分示意圖

5.3 性能比較與分析

在基于程序特征的線程劃分過(guò)程中，首先是獲取程序特征，然后從樣本集中用機(jī)器學(xué)習(xí)的方法獲取劃分方案，即一組閾值，程序中的每個(gè)過(guò)程有一組不同的閾值，然后用這組閾值進(jìn)行線程劃分，最后把劃分后的線程放在Prophet模擬器上執(zhí)行，獲取每個(gè)程序的加速比。表4給出了基于啟發(fā)式規(guī)則的劃分方法、基于專家經(jīng)驗(yàn)的劃分方法和基于程序特征的劃分方法的加速比結(jié)果，其中Prophet模擬器的核數(shù)設(shè)置為4。

為了展示基于程序特征的線程劃分的有效性，本文選擇與原始基于啟發(fā)式規(guī)則的線程劃分方法進(jìn)行比較。因?yàn)榛趯＜医?jīng)驗(yàn)的劃分是一種顯式的劃分方法，它可以根據(jù)程序的控制依賴和數(shù)據(jù)依賴關(guān)系選擇合適的線程邊界，并且可以多次調(diào)整sp、cqip點(diǎn)的位置，一般情況下獲取的加速比都要好于隱式劃分，所以表4中的基于專家經(jīng)驗(yàn)獲取的加速效果比基于啟發(fā)式和基于程序特征的加速效果好。但基于專家經(jīng)驗(yàn)的線程劃分方法需要人工選擇線程邊界，如果全部使用這種方法劃分所有的串行非規(guī)則程序，基本上不可能實(shí)現(xiàn)，而Olden基準(zhǔn)程序集包含的程序并不多，通過(guò)手工標(biāo)注線程邊界是可行的，使用這種方法只是用來(lái)獲取線程較優(yōu)劃分方案，構(gòu)造TLS樣本集。因此進(jìn)行實(shí)驗(yàn)結(jié)果分析時(shí)，只比較基于原始的啟發(fā)式規(guī)則和基于程序特征的線程劃分方法的性能。接下來(lái)將對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，只選取Olden基準(zhǔn)程序集中的幾個(gè)程序進(jìn)行分析。

Table 4 Comparison results of speedups表4 加速比對(duì)比結(jié)果

程序bh主要的數(shù)據(jù)結(jié)構(gòu)是異構(gòu)八叉樹(shù)，存在著非常復(fù)雜的數(shù)據(jù)依賴關(guān)系，它的并行性既存在于循環(huán)結(jié)構(gòu)，也存在于非循環(huán)結(jié)構(gòu)。對(duì)于啟發(fā)式規(guī)則，使用相同的劃分方案劃分bh程序所有的過(guò)程，而對(duì)于基于程序特征的劃分方法，可以為程序中的每個(gè)過(guò)程預(yù)測(cè)出與自身特征相匹配的劃分方案，然后進(jìn)行線程劃分，但因?yàn)榇嬖谳^多的依賴關(guān)系，所以最終只獲得了19.54%的性能提升。

程序em3d的主要數(shù)據(jù)結(jié)構(gòu)是單向鏈表，其中循環(huán)結(jié)構(gòu)占據(jù)絕大部分，因此程序em3d的并行性主要來(lái)自于循環(huán)結(jié)構(gòu)。雖然基于程序特征的線程劃分方法可以獲取適合自身特征的劃分方案，但對(duì)循環(huán)區(qū)域的特征提取不夠充分，最終與啟發(fā)式劃分方法相比，僅僅獲取了13.17%的性能提升。

程序health的主要數(shù)據(jù)結(jié)構(gòu)是雙向鏈表，其中包含了循環(huán)結(jié)構(gòu)和非循環(huán)結(jié)構(gòu)。循環(huán)結(jié)構(gòu)是并行性的主要來(lái)源，與啟發(fā)式規(guī)則相比，程序health可以獲取適合其特征的劃分方案。對(duì)循環(huán)區(qū)域進(jìn)行劃分，雖然循環(huán)占據(jù)程序的大部分，但分析其循環(huán)區(qū)域，發(fā)現(xiàn)循環(huán)體較大，數(shù)據(jù)依賴簡(jiǎn)單，因此程序health獲取了18.27%的加速效果。

程序perimeter的主要數(shù)據(jù)結(jié)構(gòu)是四叉樹(shù)，程序中都是非循環(huán)結(jié)構(gòu)，沒(méi)有循環(huán)結(jié)構(gòu)。程序的并行性主要來(lái)自于函數(shù)以及函數(shù)體分解成多線程。因?yàn)楹茈y預(yù)測(cè)函數(shù)的返回值，所以這兩種劃分方法加速比效果都不好。和啟發(fā)式規(guī)則相比，基于程序特征的劃分方法為程序的每個(gè)過(guò)程選擇符合自身特征的劃分方案，并且劃分方案不受循環(huán)影響，對(duì)于非循環(huán)域采用的評(píng)估模型，為當(dāng)前程序找到較好的線程劃分邊界，因此最終程序執(zhí)行性能提升了18.23%。

程序treeadd的主要數(shù)據(jù)結(jié)構(gòu)是二叉樹(shù)，程序結(jié)構(gòu)簡(jiǎn)單，其中只包含4個(gè)過(guò)程，而且程序中并不包含任何循環(huán)結(jié)構(gòu)，只有非循環(huán)結(jié)構(gòu)，因此并行性都來(lái)自于非循環(huán)區(qū)域。通過(guò)基于程序特征的劃分方法可以為每個(gè)過(guò)程選取合適的劃分方案，但treeadd中存在較多遞歸函數(shù)調(diào)用和數(shù)據(jù)依賴，最終程序獲得了21.19%的性能提升。

程序bisort的主要數(shù)據(jù)結(jié)構(gòu)是二叉樹(shù)，本文通過(guò)對(duì)源碼的分析可知，程序中只包含3個(gè)循環(huán)體，并且執(zhí)行的只有2個(gè)循環(huán)體，而且循環(huán)體粒度都比較小。那么程序的并行性主要來(lái)自于非循環(huán)區(qū)域，雖然程序存在一定數(shù)量的數(shù)據(jù)依賴，但通過(guò)基于程序的特征劃分方法可以從程序中挖掘潛在的并行性，選擇程序中各個(gè)過(guò)程合適的劃分方案，對(duì)于非循環(huán)域采用評(píng)估模型，找到了較好的線程劃分邊界，最終基于程序特征的劃分方法獲取了27.47%的性能提升。

圖11展示了基于啟發(fā)式與基于程序特征的劃分方法獲取的加速比對(duì)比圖。從圖11中可以觀察出，本文基于程序特征的線程劃分方法在Olden測(cè)試集上的加速比與基于啟發(fā)式規(guī)則劃分方法的加速比在不同程度上都有一定的提高，但不同的程序，加速比性能提升幅度有比較明顯的差異?？傮w來(lái)說(shuō)，原始的基于啟發(fā)式規(guī)則的平均加速比為1.725，而本文基于程序特征的平均加速比為2.040，平均加速比提升了18.24%，這說(shuō)明基于程序特征的線程劃分方法對(duì)程序劃分有較好的效果。圖12顯示了部分SPEC2000和Olden基準(zhǔn)程序在不同核個(gè)數(shù)上執(zhí)行的加速比。

Fig.11 Comparison of speedups for Olden benchmarks圖11 Olden測(cè)試集加速比對(duì)比圖

Fig.12 Comparison of speedups for Olden and SPEC2000 benchmarks over different PEs圖12 Olden和SPEC2000測(cè)試程序在不同核數(shù)上的加速比對(duì)比圖

6 總結(jié)和展望

6.1 總結(jié)

本文在Prophet系統(tǒng)基礎(chǔ)上，提出了一種基于程序特征的線程劃分方法，將機(jī)器學(xué)習(xí)方法運(yùn)用到線程劃分中。根據(jù)程序特征從樣本集中預(yù)測(cè)線程的劃分方案，并利用預(yù)測(cè)的劃分方案進(jìn)行線程劃分，最后在Prophet模擬器上執(zhí)行劃分后的程序，驗(yàn)證其執(zhí)行性能。本文的研究?jī)?nèi)容和相關(guān)結(jié)論如下。

（1）構(gòu)建TLS樣本集

本文提出了構(gòu)建TLS樣本集的方法。TLS樣本集是由特征和劃分方案組成。特征是在程序的每個(gè)過(guò)程的控制流圖的推測(cè)路徑上提取的。對(duì)于TLS樣本中劃分方案獲取方法，采用了一種基于專家經(jīng)驗(yàn)顯式劃分的方法，對(duì)程序進(jìn)行顯式劃分，統(tǒng)計(jì)出程序中每個(gè)過(guò)程的較優(yōu)劃分方案。

（2）預(yù)測(cè)劃分方案

本文使用了機(jī)器學(xué)習(xí)中的KNN分類算法從已構(gòu)建的TLS樣本集中獲取待劃分程序的每個(gè)過(guò)程的較優(yōu)劃分方案。

（3）基于程序特征的線程劃分

本文提出了一種在獲取程序的每個(gè)過(guò)程的劃分方案的基礎(chǔ)上，利用劃分方案對(duì)程序進(jìn)行劃分的方法，并分別進(jìn)行了程序的非循環(huán)區(qū)域劃分和循環(huán)區(qū)域劃分。針對(duì)程序的非循環(huán)區(qū)域，建立一個(gè)評(píng)估模型，并根據(jù)評(píng)估模型對(duì)非循環(huán)區(qū)域進(jìn)行迭代劃分。針對(duì)循環(huán)區(qū)域，則分別進(jìn)行循環(huán)嵌套迭代和循環(huán)內(nèi)部劃分。對(duì)于嵌套循環(huán)，采用順序激發(fā)、嵌套迭代方式進(jìn)行線程劃分；對(duì)于循環(huán)內(nèi)部，則采用基于非循環(huán)區(qū)域劃分的方法進(jìn)行線程劃分。

（4）使用Olden基準(zhǔn)程序進(jìn)行測(cè)試

使用Olden基準(zhǔn)程序在Prophet系統(tǒng)上驗(yàn)證基于程序特征的線程劃分的效果，并與原有的劃分結(jié)果進(jìn)行比較。測(cè)試結(jié)果表明，根據(jù)程序特征獲取劃分方案，并用劃分方案進(jìn)行線程劃分的程序執(zhí)行加速比與原始的加速比平均提升了18.24%。

6.2 展望

隨著TLS的快速發(fā)展和人們對(duì)并行計(jì)算的關(guān)注增加，基于TLS的算法逐漸成為研究的熱點(diǎn)。在算法層次實(shí)現(xiàn)線程級(jí)推測(cè)，從而實(shí)現(xiàn)更高抽象層次來(lái)開(kāi)發(fā)并行性，克服了編程方面的一些困難。

在平臺(tái)方面，TLS逐漸從單機(jī)多核發(fā)展成分布式平臺(tái)，如Spark平臺(tái)上的解壓算法的線程級(jí)推測(cè)并行。

:

[1]Schaller R R.Moore’s law:past,present,and future[J].IEEE Spectrum,1997,34(6):52-59.

[2]Thompson S E,Parthasarathy S.Moore’s law:the future of Si microelectronics[J].Materials Today,2006,9(6):20-25.

[3]Shoji Y,Nunome A,Hirata H,et al.A large-scale speculation for the thread-level parallelization[C]//Proceedings of the 3rd International Conference on Applied Computing and Information Technology/the 2nd International Conference on Computational Science and Intelligence,Okayama,Jul 12-16,2015.Washington:IEEE Computer Society,2015:162-168.

[4]Estebanez A,Llanos D R,González-Escribano A.A survey on thread-level speculation techniques[J].ACM Computing Surveys,2016,49(2):1-39.

[5]Hammond L,Hubbert B A,Siu M,et al.The Stanford hydra CMP[J].IEEE Micro,2000,20(2):71-84.

[6]Sohi G S,Breach S E,Vijaykumar T N.Multiscalar processors[C]//Proceedings of the 22nd Annual International Symposium on Computer Architecture,Santa Margherita Ligure,Jun 22-24,1995.Washington:IEEE Computer Society,1995:414-425.

[7]Liu Wei,Tuck J,Ceze L,et al.POSH:a TLS compiler that exploits program structure[C]//Proceedings of the 2006 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming,New York,Mar 29-31,2006.New York:ACM,2006:158-167.

[8]Deng Kun.Research and implementation of multithread compiler optimization technology[D].Changsha:National University of Defense Technology,2001.

[9]Steffan J G,Colohan C B,Zhai A,et al.The STAMPede approach to thread-level speculation[J].ACM Transactions on Computer Systems,2005,23(3):253-300.

[10]Qui?ones C G,Madriles C,Sánchez F J,et al.Mitosis compiler:an infrastructure for speculative threading based on pre-computation slices[C]//Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation,Chicago,Jun 12-15,2005.New York:ACM,2005:269-279.

[11]Madriles C,Qui?ones C G,Sánchez F J,et al.Mitosis:a speculative multithreaded processor based on precomputation slices[J].IEEE Transactions on Parallel and Distributed Systems,2008,19(7):914-925.

[12]Ohsawa T,Takagi M,Kawahara S,et al.Pinot:speculative multi-threading processor architecture exploiting parallelism over a wide range of granularities[C]//Proceedings of the 38th Annual IEEE/ACM International Symposium on Microarchitecture,Barcelona,Nov 12-16,2005.Washington:IEEE Computer Society,2005:81-92.

[13]Chen Zheng,Zhao Yinliang,Pan Xiaoyu,et al.An overview of Prophet[C]//LNCS 5574:Proceedings of the 9th International Conference on Algorithms and Architectures for Parallel Processing,Taibei,China,Jun 8-11,2009.Berlin,Heidelberg:Springer,2009:396-407.

[14]Song Shaolong,Zhao Yinliang,Feng Boqin,et al.Prophet+:an extended multicore simulator for speculative multithreading[J].Journal of Xi’;an Jiaotong University,2010,44(10):13-17.

[15]Dong Zhaoyu,Zhao Yinliang,Wei Yuanke,et al.Prophet:a speculative multi-threading execution model with architectural support based on CMP[C]//Proceedings of the International Conference on Scalable Computing and Communications/the 8th International Conference on Embedded Computing,Dalian,Sep 25-27,2009.Washington:IEEE Computer Society,2009:103-108.

[16]Johnson T A,Eigenmann R,Vijaykumar T N.Min-cut program decomposition for thread-level speculation[C]//Proceedings of the 2004 ACM SIGPLAN Conference on Programming Language Design and Implementation,Washington,Jun 9-11,2004.New York:ACM,2004:59-70.

[17]Codrescu L,Wills D S.On dynamic speculative thread partitioning and the MEM-slicing algorithm[C]//Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques,Newport Beach,Oct 12-16,1999.Washington:IEEE Computer Society,1999:40-46.

[18]Wang Zheng,O'Boyle M F P.Mapping parallelism to multicores:a machine learning based approach[C]//Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming,Raleigh,Feb 14-18,2009.New York:ACM,2009:75-84.

[19]Grewe D,Wang Zheng,O'Boyle M F P.A workload-aware mapping approach for data-parallel programs[C]//Proceedings of the 6th International Conference on High Performance Embedded Architectures and Compilers,Heraklion,Jan 24-26,2011.New York:ACM,2011:117-126.

[20]Long Shun,Fursin G,Franke B.A cost-aware parallel workload allocation approach based on machine learning techniques[C]//LNCS 4672:Proceedings of the 2007 International Conference on Network and Parallel Computing,Dalian,Sep 18-21,2007.Berlin,Heidelberg:Springer,2007:506-515.

[21]Li Yuxiang,Zhao Yinliang,Wu Qiangsheng.A graph-based thread partition approach in speculative multithreading[C]//Proceedings of the 18th IEEE International Conference on High Performance Computing and Communications,the 14th IEEE International Conference on Smart City,the 2nd IEEE International Conference on Data Science and Systems,Sydney,Dec 12-14,2016.Piscataway:IEEE,2017:406-413.

[22]Li Yuxiang,Zhao Yinliang,Shi Jiaqiang.A hybrid samples generation approach in speculative multithreading[C]//Proceedings of the 18th IEEE International Conference on High Performance Computing and Communications,the 14th IEEE International Conference on Smart City,the 2nd IEEE International Conference on Data Science and Systems,Sydney,Dec 12-14,2016.Piscataway:IEEE,2017:35-41.

[23]Carlisle M C,Rogers A,Reppy J H,et al.Early experiences with Olden[C]//LNCS 768:Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing,Portland,Aug 12-14,1993.Berlin,Heidelberg:Springer,1993:1-20.

[24]Carlisle M C.Olden:parallelizing programs with dynamic data structures on distributed-memory machines[D].Princeton:Princeton University,2010.

附中文參考文獻(xiàn)：

[8]鄧鹍.前瞻多線程編譯優(yōu)化技術(shù)的研究與實(shí)現(xiàn)[D].長(zhǎng)沙:國(guó)防科學(xué)技術(shù)大學(xué),2001.

[14]宋少龍,趙銀亮,馮博琴,等.支持推測(cè)多線程的擴(kuò)展多核模擬器Prophet+[J].西安交通大學(xué)學(xué)報(bào),2010,44(10):13-17.