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

有效

• 申請號: 201510400552.6
• 申請日: 2015-07-09
• 公開（公告）號: CN105138309B
• 公開（公告）日: 2018-07-17
• 發明（設計）人: 趙銀亮;王啟明;李美蓉
• 申請（專利權）人: 西安交通大學
• 主分類號: G06F9/38
• 分類號: G06F9/38
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 徐文權

本發明公開了一種基于CMP的推測多線程機制下的多推測路徑線程劃分方法，該方法線程劃分是以過程為單位的，對每一個過程，劃分時會限制線程結束點在過程的控制無關節點，限制線程激發點在過程的互斥路徑段，以使得線程的激發受到更嚴格的限制；同時，對相互互斥的路徑段上的激發點，讓其對應到同一個線程結束點下，并在線程結束點后插入連續的多個預計算片段；預計算片段的內容隨推測路徑和激發點的變化而互異；模擬器在運行時執行不同的推測路徑，會根據推測路徑上對應的激發點選取對應的預計算片段進行執行。該方法能在多條路徑上進行線程劃分，從而增加了可推測并行執行的分支覆蓋率。

技術領域

本發明屬于計算機領域，涉及基于CMP的推測多線程技術，特別是涉及基于CMP的推測多線程機制下的多推測路徑線程劃分方法。

背景技術

推測多線程(Speculative Multithreading，SpMT)是一種軟硬件協同工作的程序自動并行化技術，它能夠提高通用串行輸入程序在多核硬件上的執行效率。編譯器對串行輸入程序采用激進的線程劃分策略，并不完全保證各個線程之間獨立，而是允許線程之間有一定的數據依賴和控制依賴。在線程執行過程中由多核硬件檢測線程運行狀態，如檢測到依賴違規，硬件則使程序自動從錯誤中恢復，以此來保證程序的正確性。

線程之間的依賴通過值預測技術解決。通過編譯技術分析得到當前線程的live_in數據，然后分析線程發起點到當前線程開始執行點之間的代碼片段，獲取live_in變量的依賴指令集。在當前線程被分配到新的核上執行時，先執行這部分依賴指令，以此對live_in變量的值進行預測。這種先被執行的部分依賴指令，通常稱為預計算片段(Pre-computation slice,P-slice)。包括預計算片段在內的值預測技術能夠很大程度上解決線程間的依賴問題。

在推測多線程的技術中，線程推測是在某一條或幾條分支路徑上進行的，這些分支路徑也被稱為推測路徑。推測路徑的選取過程包含了分支預測過程，其能直接影響程序的控制依賴，以及間接地影響數據依賴。當選取的推測路徑與程序的實際運行軌跡相同的時候，程序的控制依賴被直接消除，而通過值預測技術提取的預計算片段此時能夠較大概率地消除數據依賴，從而總體上使得推測執行的正確性較大地得到提高。反之，如果選取的推測路徑與程序的實際運行軌跡出現較大的不一致，會造成程序由于控制依賴被直接撤銷，或者降低了預計算片段提取依賴指令的準確性，最終使得程序的推測執行被撤銷。因此，推測路徑的選取要盡量能預測到程序執行的軌跡。

發明內容

本發明目的在于解決線程劃分過程中由于多推測路徑而導致的不同路徑之間激發的線程相互干擾而造成較大概率撤銷的問題，提供一種基于CMP的推測多線程機制下的多推測路徑線程劃分方法，以保證線程劃分在多路徑下進行時能夠覆蓋更多的分支，獲得更高的推測并行性，同時減少由于值預測失敗而造成的撤銷。

本發明通過以下技術方案來實現：

一種基于CMP的推測多線程機制下的多推測路徑線程劃分方法，對于串行輸入程序進行線程劃分的方法，其步驟如下：

1)編譯器會在對串行輸入程序進行線程劃分之前依據程序剖析器剖析運行的結果尋找執行概率大于閾值branch_probability∈[0.10,0.25]的路徑作為推測路徑，只在選取的推測路徑上進行線程劃分，推測路徑是一條或者多條；

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