[發(fā)明專利]基于CMP的推測多線程機(jī)制下的多推測路徑線程劃分方法

有效

• 申請?zhí)枺?/td>: 201510400552.6
• 申請日: 2015-07-09
• 公開（公告）號(hào): CN105138309B
• 公開（公告）日: 2018-07-17
• 發(fā)明（設(shè)計(jì)）人: 趙銀亮;王啟明;李美蓉
• 申請（專利權(quán)）人: 西安交通大學(xué)
• 主分類號(hào): G06F9/38
• 分類號(hào): G06F9/38
• 代理公司: 西安通大專利代理有限責(zé)任公司 61200
• 代理人: 徐文權(quán)

1.一種基于CMP的推測多線程機(jī)制下的多推測路徑線程劃分方法，其特征在于，用于對于串行輸入程序進(jìn)行線程劃分，其步驟如下：

1)編譯器會(huì)在對串行輸入程序進(jìn)行線程劃分之前依據(jù)程序剖析器剖析運(yùn)行的結(jié)果尋找執(zhí)行概率符合閾值條件的路徑作為推測路徑，閾值條件是執(zhí)行概率大于閾值branch_probability∈[0.10,0.25]，只在選取的多條推測路徑上進(jìn)行線程劃分；

2)將串行輸入程序的過程體的控制流圖切分成線程體粒度大于閾值thread_size_lower∈[15,25]的控制流圖子圖，控制流圖子圖的切分點(diǎn)作為由控制流圖子圖生成的線程單元的結(jié)束點(diǎn)；在線程單元的結(jié)束點(diǎn)插入CQIP指令，其表示當(dāng)前線程單元的執(zhí)行結(jié)束；

3)在推測路徑的互斥子路徑段，尋找能使線程之間的數(shù)據(jù)依賴數(shù)目小于閾值dependence_threshold∈[2,5]并且線程激發(fā)距離大于閾值spawning_distance_lower∈[3,8]的位置作為新線程激發(fā)點(diǎn)，在此激發(fā)新的線程單元執(zhí)行，激發(fā)距離表示候選的線程激發(fā)點(diǎn)與線程結(jié)束點(diǎn)之間的距離；在線程激發(fā)點(diǎn)插入線程激發(fā)控制指令SPAWN指令，其作用是激發(fā)新的線程單元；SPAWN指令格式為SPAWN addr，addr表示新的線程單元的指令起始地址；

4)在每一個(gè)尚未被激發(fā)的新的線程單元的開始部分插入預(yù)計(jì)算片段，每一段預(yù)計(jì)算片段與由SPAWN指令和CQIP指令組成的指令對對應(yīng)；

所述的互斥子路徑段的語義如下：

1)互斥子路徑段是相鄰兩個(gè)CQIP指令之間的控制流圖子圖的邊的集合的子集，互斥子路徑段包含的指令集合，不跨越多個(gè)線程體，只在一個(gè)線程體內(nèi)部；

2)一條路徑上的屬于互斥子路徑段的部分與該控制流圖子圖其他路徑無任何交集；

所述的預(yù)計(jì)算片段其特征如下：

1)一段預(yù)計(jì)算片段由PSLICE_ENTRY指令標(biāo)記起始，由PSLICE_EXIT指令標(biāo)記結(jié)束；PSLICE_ENTRY指令的地址與激發(fā)運(yùn)行當(dāng)前線程單元的SPAWN指令的addr值相等；

2)每一段互斥子路徑段上的SPAWN指令，在激發(fā)新線程之前，對應(yīng)有一段預(yù)計(jì)算片段，預(yù)計(jì)算片段是對應(yīng)互斥子路徑段上的SPAWN指令到CQIP指令之間的指令集合的精簡集；預(yù)計(jì)算片段為當(dāng)前線程在SPAWN指令到CQIP指令之間的livein變量的定義指令組成的指令集合；

3)相互互斥的多個(gè)互斥子路徑段上的SPAWN指令對應(yīng)的預(yù)計(jì)算片段都被放置在同一個(gè)CQIP指令的后面，每一個(gè)SPAWN指令的addr值與其中一段預(yù)計(jì)算片段的PSLICE_ENTRY指令地址相等。

2.如權(quán)利要求1所述的基于CMP的推測多線程機(jī)制下的多推測路徑線程劃分方法，其特征在于，所述的控制流圖子圖的切分點(diǎn)屬于過程的控制無關(guān)基本塊，即從過程的入口節(jié)點(diǎn)到過程的出口節(jié)點(diǎn)的任何路徑都經(jīng)過該基本塊；通過切分點(diǎn)的切分，使控制流圖子圖的粒度大于thread_size_lower∈[15,25]，而對其粒度上限不作直接約束。

3.如權(quán)利要求1所述的基于CMP的推測多線程機(jī)制下的多推測路徑線程劃分方法，其特征在于，模擬器端在執(zhí)行時(shí)，互斥子路徑段上的SPAWN指令能根據(jù)addr值跳轉(zhuǎn)到對應(yīng)的PSLICE_ENTRY指令開始執(zhí)行一段預(yù)計(jì)算片段，并且執(zhí)行完這段預(yù)計(jì)算片段后，由模擬器的硬件檢測后續(xù)指令是否是PSLICE_ENTRY指令，若是，則繼續(xù)跳過其后的預(yù)計(jì)算片段，若不是，則表示開始執(zhí)行常規(guī)的線程體內(nèi)容。