[發明專利]一種基于遺傳算法的異構多核處理器任務分配與調度策略

有效

• 申請號: 201911315383.0
• 申請日: 2019-12-18
• 公開（公告）號: CN111061569B
• 公開（公告）日: 2023-05-09
• 發明（設計）人: 方娟;章佳興
• 申請（專利權）人: 北京工業大學
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06N3/126;G06F1/329
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 吳蔭芳

1.一種基于遺傳算法的異構多核處理器系統任務分配與調度策略，所述的異構多核處理器的任務分配與調度包括全局任務調度器中的任務分配和各個處理單元上的本地調度，包括以下步驟：首先將全局任務調度器中的一個任務按照各個子任務的順序和通信信息轉換為一個有向無環圖，這個有向無環圖用一個DAG圖表示；然后將各個子任務發送到各個處理單元，每個處理單元按照本地任務序列進行處理；最后在執行過程中運用改進的遺傳算法對任務分配與調度方案進行優化，找到接近最優解的任務分配與調度方案，得到的方案可以運用于下一次該任務的分配與調度，其特征在于：所述的改進的遺傳算法包括以下步驟：

第一步：初始化遺傳算法參數，并根據系統模型特點生成初始種群，初始種群的每個個體代表一種任務分配方案，所述種群生成方法具體如下：

(i)根據DAG任務圖計算所有任務的高度值H(T_i)；

(ii)將所有任務隨機分配給異構多核處理單元；

(iii)將每個核心上被隨機分配的任務按照(i)中所得到的H(T_i)從小到大排序，排序結果即為該處理單元上任務的執行順序；

(iv)若初始種群規模達到要求，則執行步驟二；否則轉回(ii)；

第二步：計算種群中所有個體的適應度函數值(Fitness?Function)，并根據適應度由大到小的順序對種群中的所有個體進行排序；

第三步：染色體交叉(Crossover)產生新的種群，具體為：對步驟二中排序后的相鄰的兩條染色體進行交叉操作產生后代，對產生的后代與其親代重新計算適應度，并根據適應度由大到小的順序選擇出新的種群，且新種群規模與親代種群規模保持一致；

第四步:染色體變異(Mutation)產生新種群，變異概率P_m如下給出：

其中，Fit_max是指種群中所有調度方案里最大的適應度函數值，Fit_S是指調度方案S的適應度，Fit是指種群中所有調度方案的平均適應度函數值，變異的具體操作為：對于每一個個體產生一個[0,1]之間的一個隨機數p，若p大于變異概率P_m，則該個體進行變異操作，單個染色體變異的過程具體為：該染色體的隨機位置對應值得改變，該值的改變對應著子任務執行的處理器編號的改變；對變異后的個體與其親代重新計算適應度函數值，并根據適應度由大到小的順序選擇出新的種群，且新種群規模與親代種群規模保持一致；

第五步：若達到最大迭代次數，則輸出適應度函數最大的任務分配方案；否則分別尋找連續多代種群的最優解，然后根據連續多代種群最優解之間的漢明距離判斷是否潛在早熟收斂情況，若未發生早熟則轉入第三步；若發生早熟現象則啟用注入策略后轉入第二步。

2.根據權利要求1所述的一種基于遺傳算法的異構多核處理器系統任務分配與調度策略，其特征在于：步驟二中所述的第S個個體，即調度方案S(0≤S≤Scale-1)的適應度函數計算公式如下：

其中，Scale為當前種群的規模，E_total(S)為該任務在按照調度方案S執行時異構多核處理器產生的功耗，E_sum為當前種群功耗總和。