[發明專利]一種單指令集異構多核系統靜態任務調度方法

無效

• 申請號: 201210391276.8
• 申請日: 2012-10-16
• 公開（公告）號: CN102866912A
• 公開（公告）日: 2013-01-09
• 發明（設計）人: 徐遠超;譚旭;范東睿;張浩;王達;宋風龍;張志敏
• 申請（專利權）人: 首都師范大學
• 主分類號: G06F9/46
• 分類號: G06F9/46
• 代理公司: 北京慧泉知識產權代理有限公司 11232
• 代理人: 王順榮;唐愛華

1.一種單指令集異構多核系統靜態任務調度方法，其特征在于：該方法具體步驟如下：步驟一：種群初始化

遺傳算法初始種群的產生有兩種方法，一是沒有任何條件限制，隨機的產生初始種群；二是種群的產生必須滿足一定的要求，在滿足這些條件的前提下再隨機的產生初始種群；根據具體問題選擇相應的方法；

設n為處理器數量，m為總的任務數，當染色體S的u(·)部分為任務的全局排序時，種群初始化步驟如下：

（1）產生一個新的染色體S；

（2）初始化染色體S的v(·)部分，其中的每一個基因位均為隨機數，類型為整數，取值范圍為[0,n-1]；

（3）初始化染色體S的u(·)部分，取值為1,2,…,m的一個排列，鑒于全局排序存在的問題，這里在u(·)部分使用局部排序，用于確定兩個沒有依賴關系的任務之間的執行順序；因此，任何一個隨機序列都是有效的，不需要判斷個體是否有效，種群初始化的過程因此變得簡單；

（4）當種群規模達到設定值時，退出初始化，否則，轉向（1）繼續產生新個體；

步驟二：計算適應度值

要實現的調度目標是尋找一個調度策略，將m個子任務分配到n個處理器核上，合理安排各個子任務的執行次序，使得各子任務在滿足依賴關系圖的約束下，整個任務的完成時間盡量短，功耗盡量低；多目標優化遺傳算法不需要像權重法那樣設置權重系數，仍然同單目標優化遺傳算法那樣分別計算多個目標的適應度值，采用Pareto方法來判斷一個解是否是非劣解；異構多核系統的調度目標是總的任務完成時間和功耗，因此需要同時計算兩個適應度值；適應度值的計算是在甘特圖的基礎上完成的，甘特圖的生成還要以及執行時間矩陣Θ、通信延遲矩陣Ψ、任務分配矩陣Ω，任務先序關系矩陣Λ；

1）任務完成時間

假設一個有效的調度策略S，將T中的m個任務分配到n個處理器核上，那么任務T_i在處理器核C_j上的執行時間滿足：

Begin(Ti,Cj)=maxTk∈pred(Ti)[Finish(Tk,Cr)+(1-ωir)*ψki]]]>

Finish(T_i,C_j)=Begin(T_i,C_j)+θ_ij?????（5）

公式（5）中，Begin(T_i,C_j)和Finish(T_i,C_j)分別表示任務T_i在處理器C_j核上的開始執行時刻和結束執行時刻，假設任務T_k∈pred(T_i)被分配到處理器核C_r上；根據公式（5）得到所有任務的結束執行時刻；某個調度策略S下的總的任務完成時間為最后一個任務的結束時間，令Γ(S)=max(Finish(T_i,C_j))，任務調度的目標之一是尋找一個調度策略S，使得Γ(S)最小；

2）系統能耗模型

處理器核的功耗主要來自三個方面：動態功耗P_dyn、靜態功耗P_static和短路功耗P_short；動態功耗來自處理器核內部各元件正常工作時的功耗；靜態功耗是來自亞閾值漏電流和柵極漏電流產生的功耗；短路功耗是晶體管在邏輯門打開的瞬間產生的功耗；處理器核的功耗主要由P_dyn決定，約占70%，動態功耗用公式表示為P_dyn=KCV²f，其中，K是晶體管的翻轉次數，C是晶體管的裝載電容，f是時鐘頻率，V是供電電壓；隨著工藝的發展，動態功耗在降低，使得靜態功耗所占比重增大；每個處理器核都有一個電壓和頻率成對匹配的離散有限集合，頻率和電壓已知后估算出每個處理器核的動態功耗P={P_{dyn_0},P_{dyn_1},…,P_{dyn_n}}，根據靜態功耗與動態功耗的大致比例關系，粗略地估算每個處理器核的靜態功耗P={P_{static_0},P_{static_1}，…,P_{static_n}}，暫且忽略短路功耗；當調度序列確定后，每個處理器核的正常工作時間及空閑時間就確定了，假設每個處理器核的正常工作時間為T_work={T_{work_0},T_{work_1},…,T_{work_n}}，空閑時間為T_idle={T_{idle_0},T_{idle_1},…,T_{idle_n}}，則完成全部任務所消耗的能量任務調度的目標之二是尋找一個調度策略S，使得energy(S)最小；

步驟三：選擇算子操作

選擇操作是將種群中優秀個體選出，將劣質個體淘汰，遺傳算法的選擇操作就是基于個體適應度值的選擇，適應度值大的個體被選中的概率大，適應度值小的個體被淘汰的概率大；常見的選擇方法有隨機遍歷抽樣、局部選擇、錦標賽選擇、輪盤賭選擇；這里使用帶放回即with?replacement的二選一錦標賽選擇法；具體流程是：在精英種群中隨機抽取兩個個體，記錄其中適應度高的個體，然后再把它們全部放回到精英種群中，如果選擇N個個體，則重復N次；

步驟四：交叉算子操作

交叉算子是為了擴大算法的搜索空間，避免算法過早地收斂于某個局部最優解，防止早熟；在用于任務調度的交叉算子中，要保證任務集不增不減，同時還要保證交叉運算后的調度序列依然滿足任務之間的先序關系；

提出交叉算子僅作用于染色體的v(·)部分，u(·)部分在種群初始化后不再變化，原因在于任務之間的先后順序是通過任務先序關系矩陣來保證的，u(·)部分定義的先后順序只是一種補充；具體算法如下：

（1）從種群中隨機選擇個體S；

（2）從個體S中隨機選擇兩個任務，T_x和T_y；

（3）如果任務T_x和T_y所在的處理器核不同，即v(x)≠v(y)，則進行交叉，否則，直接轉入（4）；

（4）退出交叉運算；

步驟五：變異算子操作

在異構多核處理器任務分配中，不能采用傳統的隨機變異操作，變異算子必須保證任務總數和種類不變、處理器核的范圍也不變；這里的變異算子限定只作用在v(·)上，相當于將任務遷移；具體算法如下：

（1）從種群中隨機選擇個體S；

（2）從個體S的v(·)中隨機選擇1個基因位i；

（3）隨機產生一個整數m∈[0,N-1]，其中N是處理器核的數量；

（4）令v(·)=m；

（5）退出變異運算。