[發(fā)明專利]一種基于機(jī)器學(xué)習(xí)的推測(cè)多線程劃分方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201510661837.5
• 申請(qǐng)日: 2015-10-14
• 公開(kāi)（公告）號(hào): CN105373424B
• 公開(kāi)（公告）日: 2018-10-30
• 發(fā)明（設(shè)計(jì)）人: 趙銀亮;吉爍;李玉祥;侍加強(qiáng);劉延昭;呂挫挫
• 申請(qǐng)（專利權(quán)）人: 西安交通大學(xué)
• 主分類號(hào): G06F9/48
• 分類號(hào): G06F9/48;G06F9/50
• 代理公司: 西安通大專利代理有限責(zé)任公司 61200
• 代理人: 岳培華

本發(fā)明公開(kāi)了一種基于機(jī)器學(xué)習(xí)的推測(cè)多線程劃分方法，先從非規(guī)則程序集中提取程序特征，應(yīng)用帶注釋的CFG圖聯(lián)合關(guān)鍵路徑來(lái)表示程序特征；然后用SUIF編譯器構(gòu)造程序的控制流圖，并轉(zhuǎn)化為加權(quán)控制流圖和超級(jí)塊控制流圖，對(duì)程序集進(jìn)行針對(duì)循環(huán)部分和非循環(huán)部分的線程劃分，得到由程序特征和最優(yōu)劃分方案構(gòu)成的訓(xùn)練樣本集；最后通過(guò)提取待劃分非規(guī)則程序的特征，并計(jì)算其與訓(xùn)練樣本中程序特征的相似性，對(duì)若干最相似樣本程序的劃分閾值進(jìn)行加權(quán)計(jì)算，獲得適應(yīng)于該非規(guī)則程序的最優(yōu)劃分方案。本發(fā)明依據(jù)程序特征來(lái)比較待劃分程序與樣本程序的相似性，將相似樣本的劃分方案應(yīng)用到待劃分程序中，對(duì)于并行化各類非規(guī)則程序具有更好的適應(yīng)性。

技術(shù)領(lǐng)域

本發(fā)明屬于計(jì)算機(jī)技術(shù)領(lǐng)域，涉及一種推測(cè)多線程技術(shù)，特別涉及一種基于機(jī)器學(xué)習(xí)的推測(cè)多線程劃分方法。

背景技術(shù)

隨著指令級(jí)并行遇到越來(lái)越多的瓶頸和片上多處理器的迅速發(fā)展，如何更加有效的利用核資源成為當(dāng)前研究熱點(diǎn)，推測(cè)多線程作為一種線程級(jí)并行技術(shù)得到迅速發(fā)展。特別是針對(duì)使用基于指針的數(shù)據(jù)結(jié)構(gòu)如圖和樹(shù)等進(jìn)行處理的非規(guī)則程序，其存在大量的只有在執(zhí)行時(shí)才能確定的模糊數(shù)據(jù)依賴關(guān)系，而線程級(jí)推測(cè)并行在允許存在控制和數(shù)據(jù)依賴的情況下，通過(guò)并行編譯器將非規(guī)則串行程序分解為多個(gè)線程單元，在執(zhí)行時(shí)將其依次分別分配給空閑的處理器核單元來(lái)并行執(zhí)行，而程序并行執(zhí)行的正確性則由底層的硬件根據(jù)相應(yīng)的執(zhí)行模型來(lái)保證。線程級(jí)推測(cè)技術(shù)擺脫了傳統(tǒng)并行化方法不能有效消解模糊數(shù)據(jù)依賴關(guān)系的局限，從而在并行化非規(guī)則程序方面展現(xiàn)出好的應(yīng)用前景。

在線程級(jí)推測(cè)執(zhí)行過(guò)程中，串行程序被劃分為多個(gè)推測(cè)線程并行執(zhí)行，每個(gè)線程分別執(zhí)行程序的不同部分，并嚴(yán)格按照串行語(yǔ)義順序執(zhí)行。推測(cè)多線程程序的執(zhí)行時(shí)，有且僅有一個(gè)線程為確定線程，該線程可以提交其執(zhí)行結(jié)果，而其他線程均為推測(cè)線程，線程間以前驅(qū)后繼的形式保持串行程序的語(yǔ)義。每個(gè)推測(cè)線程通過(guò)一對(duì)激發(fā)指令來(lái)標(biāo)識(shí)，通過(guò)引入預(yù)計(jì)算片段(Pre-computation Slice,P-slice)預(yù)測(cè)推測(cè)線程的live-ins變量(活躍變量，被線程體使用但其值并非由該線程定義值)的值。一對(duì)激發(fā)指令由線程激發(fā)點(diǎn)(Spawning Point,SP)和準(zhǔn)控制無(wú)關(guān)點(diǎn)(Control Quasi Independent Point,CQIP)，即新線程的起始點(diǎn)構(gòu)成，當(dāng)程序執(zhí)行到SP點(diǎn)時(shí)，若有空閑核資源，則分配線程到該處理器執(zhí)行；當(dāng)確定線程執(zhí)行到CQIP點(diǎn)時(shí)，將驗(yàn)證其直接后繼線程在P-slice產(chǎn)生的live-ins數(shù)據(jù)，若驗(yàn)證正確，則確定線程提交其執(zhí)行結(jié)果；若驗(yàn)證失敗，則撤銷此后繼推測(cè)線程及其所有推測(cè)子線程，然后跳過(guò)P-slice片段，將該后繼線程作為確定線程來(lái)執(zhí)行。

在推測(cè)多線程中如何合理地分解非規(guī)則串行程序?qū)τ谔岣呒铀俦扔泻艽蟮挠绊懀瑐鹘y(tǒng)的線程劃分方法主要應(yīng)用啟發(fā)式規(guī)則，通過(guò)對(duì)線程粒度、數(shù)據(jù)依賴距離等加以選擇控制來(lái)優(yōu)化程序的分解過(guò)程。其局限性在于不同的程序通常具有不同的結(jié)構(gòu)特征，而基于啟發(fā)式規(guī)則的方法以一種單一的優(yōu)化方案來(lái)對(duì)所有程序進(jìn)行優(yōu)化，因此不能保證所有的非規(guī)則程序均能獲得最優(yōu)的劃分。

發(fā)明內(nèi)容

本發(fā)明的目的在于克服上述現(xiàn)有應(yīng)用啟發(fā)式規(guī)則以一種單一的優(yōu)化方案來(lái)對(duì)所有程序進(jìn)行優(yōu)化的局限性，提供一種基于機(jī)器學(xué)習(xí)的推測(cè)多線程劃分方法，該方法能夠依據(jù)程序特征來(lái)優(yōu)化最優(yōu)劃分方案，對(duì)不同非規(guī)則程序具有更好的適應(yīng)性。

為達(dá)到上述目的，本發(fā)明采用以下技術(shù)方案：

一種基于機(jī)器學(xué)習(xí)的推測(cè)多線程劃分方法，包括以下步驟：

1)從非規(guī)則程序集中提取程序特征，并將提取的程序特征注釋到程序的控制流圖CFG上，同時(shí)以數(shù)組結(jié)構(gòu)來(lái)存儲(chǔ)程序關(guān)鍵路徑上的基本塊，得到以帶注釋的圖聯(lián)合數(shù)組的方式表達(dá)的程序集；

2)基于SUIF編譯器構(gòu)造程序控制流圖CFG，并用程序剖析信息和結(jié)構(gòu)化分析方法將構(gòu)造的程序控制流圖依次轉(zhuǎn)化為加權(quán)控制流圖WCFG和超級(jí)塊控制流圖SCFG，然后對(duì)程序集分別進(jìn)行循環(huán)部分和非循環(huán)部分的線程劃分，得到由程序特征和最優(yōu)劃分方案構(gòu)成的訓(xùn)練樣本集；