[發明專利]基于改進遺傳算法的異構多核節能任務調度方法

無效

• 申請號: 201110386958.5
• 申請日: 2011-11-30
• 公開（公告）號: CN102508708A
• 公開（公告）日: 2012-06-20
• 發明（設計）人: 徐成;陳曉明;曾理寧;馬炳周;朱曄;李濤;張良;舒攀
• 申請（專利權）人: 湖南大學
• 主分類號: G06F9/46
• 分類號: G06F9/46;G06N3/12
• 代理公司: 湖南兆弘專利事務所 43008
• 代理人: 趙洪;周長清

1.一種基于改進遺傳算法的異構多核節能任務調度方法，其特征在于，由用來確定任務優先級的改進遺傳算法以及基于縮放優先級的節能調度算法組成，其流程為：(1)進行種群信息初始化；(2)進入循環體通過遺傳算法確定任務優先級；(3)根據任務DAG圖和劃分策略，確定任務在處理器上的調度順序；(4)根據任務節省能量與延長時間之間的關系，在可行的任務調度基礎上進行動態電壓縮放；(5)計算當前群體適應度并排序；(6)采用改進的遺傳算法對種群進行更新，確定新的任務優先級，如果滿足終止條件則退出，否則繼續迭代。

2.根據權利要求1所述的基于改進遺傳算法的異構多核節能任務調度方法，其特征在于：所述步驟(1)中，將任務優先級轉換為按一定順序組織的染色體，其中染色體的編碼采用一維位串形式，編碼長度為任務圖中任務節點數n，每個基因表示對應任務的調度優先級，取值范圍為[0，n-1]，數值越低對應優先級越高，對于優先級相同的任務，則根據任務編號進行排序。

3.根據權利要求1所述的基于改進遺傳算法的異構多核節能任務調度方法，其特征在于，所述步驟(6)的流程為：

(6.1)對群體進行選擇操作，從當前群體中選出個體，作為父代進行交叉和變異操作；選擇算子執行步驟如下：

(6.1.1)根據遺傳算法中群體數目等參數計算需要選擇的個體數目Nsel；

(6.1.2)根據前面排序的排序結果，選擇位于隊列前部的Nsel/2個個體；

(6.1.3)采用隨機算法，在隊列中其余個體中均勻產生Nsel/2個個體；

(6.1.4)將上述(6.1.2)和(6.1.3)產生的共Nsel個個體作為選擇結果進行交叉和變異，選擇過程結束；

(6.2)進行交叉操作：采用兩點交叉算子；

(6.3)變異操作：變異算子是對個體中某個基因在有效值范圍內進行隨機變換，也即隨機改變某個任務的執行優先級；

(6.4)群體更新，執行步驟如下：

(6.4.1)計算新生成個體的調度能耗Echild；

(6.42)比較Echild和其父輩的調度能耗Eparent，分兩種情況考慮：如果Echild小于Eparent，則選擇新產生的染色體；如果Echild大于等于Eparent，則以概率Preceive接受新的染色體，Preceive的計算方法下式：

Preceive=e-(Echild-Eparent)/TT=1PΣi=1P(Ei-E‾)2]]>

其中，e為自然常數，Ei為個體i所對應的能耗，為群體平均執行能耗，P為群體規模；

(6.4.3)用新選擇的染色體去更新群體；

(6.4.4)如果還有新的染色體未處理，則轉到(6.4.1)，否則結束群體更新。

4.根據權利要求1或2或3所述的基于改進遺傳算法的異構多核節能任務調度方法，其特征在于，所述基于縮放優先級的節能調度算法的流程為：

(4.1)進行算法初始化；

(42)將所有任務賦以最高電壓；

(4.3)采用優先級鏈表調度算法進行任務調度，算法根據任務映射、電壓級別和任務優先級等輸入信息，確定性地輸出任務調度策略、執行時間和能耗，不能調度則返回一個無效值；

(4.4)對最高電壓級別的調度結果進行判斷，如果執行時間大于等于截止時間，說明該調度不存在縮放空間，返回調度能量；

(4.5)進行電壓反復縮放過程，其中對每個可以縮放的任務進行如下操作：

降低一個電壓級別后進行優先級鏈表調度，如果滿足截止期，則計算任務Ti在當前電壓下的縮放優先級，優先級為下式：

ZoomPriority(i,k)=Kcoe·E(Ti,Pj,Vk)-E(Ti,Pj,Vk-1)t(Ti,Pj,Vk-1)-t(Ti,Pj,Vk)]]>

式中，ZoomPriority(i，k)：任務T_i在當前電壓下的縮放優先級。K_coe為比例系數，E(T_i，P_j，V_k)：任務T_i在處理器P_j中以電壓等級V_k運行的能耗。t(T_i，P_j，V_k)：任務T_i在處理器P_j中以電壓等級V_k運行的時間；

(4.6)記錄目前為止最大可縮放優先級及其對應的調度結果；

(4.7)對可行的最優縮放任務降低一個電壓級別，并更新當前最優能耗，如果沒找到可縮放任務則返回當前最優能耗值，算法退出。