[發明專利]一種眾核處理器結構上避免無關依賴的線程劃分方法

有效

• 申請號: 201410007139.9
• 申請日: 2014-01-07
• 公開（公告）號: CN103699365A
• 公開（公告）日: 2014-04-02
• 發明（設計）人: 王耀彬;劉志勤;陳菲;彭莉娟;李凌;趙旭劍
• 申請（專利權）人: 西南科技大學
• 主分類號: G06F9/38
• 分類號: G06F9/38
• 代理公司: 北京眾合誠成知識產權代理有限公司 11246
• 代理人: 龔燮英

技術領域

本發明屬于微處理器體系結構設計領域，尤其涉及一種眾核處理器結構上避免無關依賴的線程劃分方法。

背景技術

眾核處理器結構是對片上可擴展能力達到數千個核、計算能力達到萬億次級的微處理芯片體系結構發展道路的探索。其計算資源密度更高，片上通信開銷顯著降低，能夠實現芯片結構和性能高度的可擴展性，很好地應對納米工藝代芯片設計的功耗、線延遲和設計復雜性問題。

線程劃分是指將串行程序劃分成若干線程（線程是程序中一些相關指令的離散序列，它與其他指令序列的執行彼此獨立）,在片上多個處理器核心上并行執行來提高性能。眾核結構上的線程劃分是眾核體系結構能否發揮效率的關鍵。

目前在學術界采用眾核設計思想的研究項目主要有麻省理工的Raw,斯坦福大學的SmartMemories,康奈爾大學的CoreFusion，得克薩斯大學奧斯汀分校的TRIPS和TFLEX，以及華盛頓大學的WaveScalar等。工業界的開發項目主要有IBM、Sony和Toshiba合作開發的Cell，Intel的Polaris和Larrabee，IBM的Cyclops-64，NVIDIA的CUDA等。

在線程劃分的原理上，當前這些方案基本采用了通過循環展開、尾部復制和謂詞執行等技術將指令基本塊合并為更大的超塊作為線程，通過將這些線程推測執行以提高程序的并行性。所述的超塊是指利用謂詞執行等技術將若干個基本塊集合在一起形成的一段指令序列，僅有唯一的控制流入口，可有多個出口。而所述的推測執行是指通過放松線程間的依賴關系對程序并行執行的限制，將線程放到多個不同的處理器核上推測地并行執行，從而充分挖掘程序的并行潛力。

他們的共同特點都是由編譯軟件做數據依賴剖析，并根據指令間的依賴關系將計算映射到硬件上，使得在并行性開發和負載平衡兩方面取得折衷。所述的剖析是一種記錄程序過去的執行來搜集信息，從而分析得到程序運行時特征的方法。它提供的信息能夠指導編譯器或者程序員去執行那些帶有預見性的優化。通過軟件手段確定程序動態執行特征，從而實現更加合理有效的線程劃分。

但是當前的眾核線程劃分方案都帶來了代碼膨脹和線程同步開銷過大的問題。其原因在于這些方案基本采用循環迭代和超塊等粒度作為線程劃分的基本單位，其線程劃分方法均以指令基本塊為最小單位，對基本塊內自身的無關依賴未作分離。由此帶來的推測線程間不必要依賴引入了大量無關開銷。

發明內容

本發明的目的在于提供一種眾核處理器結構上避免無關依賴的線程劃分方法，旨在解決目前眾核線程劃分機制都采用循環迭代和超塊等粒度作為線程劃分的基本單位，其線程劃分方法均以指令基本塊為最小單位，對基本塊內自身的無關依賴未作分離，由此帶來的推測線程間不必要依賴引入了大量無關開銷的問題。

本發明是這樣實現的，一種眾核處理器結構上避免無關依賴的線程劃分方法包括如下步驟：

步驟一、程序剖析，確定具有并行潛力的循環結構；

步驟二、確定該循環迭代體的控制流圖；

步驟三、確定該循環迭代體的數據流圖；

步驟四、確定派生推測線程的數目；

步驟五、通過依賴分離，進行線程劃分；

步驟六、進行線程封裝。

進一步，所述的步驟一通過程序剖析技術選擇出占據程序運行時間較多的一個或者多個循環結構，將其迭代體作為進一步劃分的備選。

進一步，所述的步驟二確定并保存備選迭代體內指令間的控制流方向。

進一步，所述的步驟三確定并保存備選迭代體內指令間的數據依賴關系。

進一步，所述的步驟四分析數據流走向，確定需要派生的推測線程數N。

進一步，步驟五所述的通過依賴分離，進行線程劃分的具體步驟如下：

步驟一、依據數據流圖中的依賴關系走向，通過反復劃分節點到N個超級節點來進行N路圖分割，進行初步的N個推測線程劃分；

步驟二、遍歷通過依賴分離進行線程劃分的步驟一中初步創建的N個超級節點，通過復制共用指令，完成最終的N個“自給自足”的推測線程劃分。

進一步，步驟六所述的進行線程封裝的具體步驟如下：

步驟一、在每個推測線程的頭部插入狀態檢查點即CKP指令，用以保持當前狀態，支持推測執行后的回退操作；

步驟二、在CKP指令之后插入線程派生指令，用以在執行時派生推測線程；

步驟三、在每個推測線程的尾部插入同步指令，用以支持推測執行的提交操作。

本發明的有益效果如下：