[發明專利]一種基于機器學習的推測多線程劃分方法

有效

• 申請號: 201510661837.5
• 申請日: 2015-10-14
• 公開（公告）號: CN105373424B
• 公開（公告）日: 2018-10-30
• 發明（設計）人: 趙銀亮;吉爍;李玉祥;侍加強;劉延昭;呂挫挫
• 申請（專利權）人: 西安交通大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 岳培華

1.一種基于機器學習的推測多線程劃分方法，其特征在于，包括以下步驟：

1)從非規則程序集中提取程序特征，并將提取的程序特征注釋到程序的控制流圖CFG上，同時以數組結構來存儲程序關鍵路徑上的基本塊，得到以帶注釋的圖聯合數組的方式表達的程序集；

2)基于SUIF編譯器構造程序控制流圖CFG，并用程序剖析信息和結構化分析方法將構造的程序控制流圖依次轉化為加權控制流圖WCFG和超級塊控制流圖SCFG，然后對程序集分別進行循環部分和非循環部分的線程劃分，得到由程序特征和最優劃分方案構成的訓練樣本集；

其中，SCFG即為循環部分被轉化為單入口和單出口抽象節點的加權控制流圖，WCFG即為注釋分支概率、路徑、循環概率的程序控制流圖；

3)提取待劃分非規則程序的特征，利用基于圖的相似性比較算法計算待劃分的非規則程序特征與訓練樣本集的程序特征的相似性，得到最相似的樣本程序，然后對最相似的樣本程序的劃分閾值進行加權計算，并將計算結果作為最優劃分閾值應用到待劃分非規則程序中完成推測多線程劃分。

2.根據權利要求1所述的基于機器學習的推測多線程劃分方法，其特征在于，所述步驟1)中依據影響程序加速比的因素從非規則程序集中提取程序特征，并使用圖G和數組A聯合的數據結構來存儲程序特征；其中影響程序加速比的因素包括線程粒度、負載均衡、數據依賴以及控制依賴；提取的程序特征包括動態指令數、循環概率、分支概率、數據依賴數和數據依賴距離；圖G是帶注釋的控制流圖，圖G中的節點的屬性為動態指令數，邊的屬性為由循環分支概率、數據依賴數、數據依賴距離組成的三元組；數組A中的元素A_i表示關鍵路徑上的基本塊。

3.根據權利要求1所述的基于機器學習的推測多線程劃分方法，其特征在于，所述步驟2)中在進行循環部分的線程劃分時，根據剖析器分析得到的迭代次數、循環體大小以及循環體之間的數據依賴數來決定循環部分的劃分，只有當激發下一次迭代是盈利的，才將每個迭代指定為一個候選線程；并且在劃分循環部分時，依據線程粒度和數據依賴數將候選線程的激發點SP插入到循環體內，將準控制無關點CQIP即候選線程的起始點插入到循環分支指令前。

4.根據權利要求3所述的基于機器學習的推測多線程劃分方法，其特征在于，判斷激發下一次迭代是盈利的標準為：循環體的線程粒度ThreadSize∈[3,32]，且迭代之間的數據依賴數DDC∈[3,9]。

5.根據權利要求1所述的基于機器學習的推測多線程劃分方法，其特征在于，所述步驟2)中在進行非循環部分的線程劃分時，將當前候選線程初始化為空，以起始點作為當前線程劃分的參考點，獲得從起始點到最近一個后向支配節點的最可能路徑，僅當最可能路徑上所有基本塊的動態指令數滿足經驗值設定的線程粒度閾值范圍條件，并且與后繼待劃分部分的最優依賴數小于經驗值設定的閾值時，則獲得由最可能路徑上的節點構成的候選線程；若大于線程粒度上限，則將被進一步劃分；若小于線程粒度下限，則當前起始點的最近后向支配節點不會激發新的線程，將最可能路徑上的節點加入到當前候選線程；每一步遞歸將當前參考點的最近后向支配節點作為當前候選線程的起始點，直到當前非循環部分的結束節點結束為止。

6.根據權利要求1所述的基于機器學習的推測多線程劃分方法，其特征在于，所述步驟2)中分別針對循環部分和非循環部分進行線程劃分，得到程序的劃分方案，然后對程序特征及其相應的最優劃分方案進行聯合表達，得到訓練樣本集；其中劃分方案表示為線程粒度上限、線程粒度下限、數據依賴數、激發距離上限和激發距離下限的五維閾值組合，訓練樣本T表示為其中，表示第i個程序的程序特征，表示第i個程序對應的最優劃分，N表示程序總個數。