基于異構多核處理器的靜態(tài)任務(wù)調度研究（一）

式中：AST (vi,pn)-任務(wù)vi在處理器pn上的實(shí)際開(kāi)始時(shí)間;AFT (vi,pk)-任務(wù)vi在處理器pk上的實(shí)際完成時(shí)間;vpar-最后一個(gè)與任務(wù)vi通信的任務(wù);Avail(pn)-處理器pn執行完分配到其上的所有任務(wù)的時(shí)間。

通過(guò)對DAG圖的深入研究發(fā)現，某層冗余任務(wù)的處理在其下一層任務(wù)到處理器的映射之后執行效果最好，如對level=1層任務(wù)調度完成后對level=0層任務(wù)進(jìn)行冗余判斷，將任務(wù)分配到處理器和冗余任務(wù)處理兩個(gè)過(guò)程交替執行，直到冗余任務(wù)列表為空。

(2)任務(wù)到處理器映射流程任務(wù)到處理器映射流程如圖3所示。

(3)任務(wù)到處理器映射階段具體步驟

步驟1 初始化level=0,判斷任務(wù)調度列表TL在level層的任務(wù)是否調度完畢，如果是則跳轉到步驟5;否則向下執行步驟2.

步驟2 取任務(wù)調度列表TL的首任務(wù)記為vi,遍歷所有處理器，如果處理器存在空閑時(shí)間段且滿(mǎn)足vi插入條件，則將vi分配到空閑時(shí)間段，并計算其最小最早完成時(shí)間，記為EFT1;否則向下執行步驟3.

步驟3 計算將vi分配到所有處理器上的最小最早完成時(shí)間，記為EFT2.如果處理器上存在空閑時(shí)間段且能使用任務(wù)復制技術(shù)，則計算在處理器上復制vi的前驅獲得最小最早完成時(shí)間，記為EFT3,繼續執行步驟4.

步驟4 選擇EFT1、EFT2、EFT3的最小值，并將任務(wù)分配到具有最早完成時(shí)間的處理器上，從調度列表中刪除vi,建立冗余任務(wù)列表RTL,將被復制的任務(wù)加入到RTL中，格式為vi,0~vi,k,vi為被復制的任務(wù)節點(diǎn)，k為任務(wù)所在處理器的編號。

步驟5 判斷RTL中是否有(level-1)層任務(wù)，如果是則跳轉到步驟6;否則跳轉到步驟8.

步驟6 取RTL首任務(wù)節點(diǎn)，記為vi,k,判斷刪除任務(wù)vi,k后vi,k直接后繼節點(diǎn)的最早開(kāi)始時(shí)間是否延遲，如果延遲，判定任務(wù)vi,k非冗余任務(wù)，從RTL中刪除vi,k,跳轉到步驟5;否則判定任務(wù)vi,k為冗余節點(diǎn)，從RTL中刪除vi,k,從任務(wù)映射圖中刪除vi,k,跳轉到步驟7繼續執行。

步驟7 判斷任務(wù)vi,k的后繼任務(wù)能否提前執行，如果能則將其前移執行，修改任務(wù)映射圖，跳轉到步驟5;否則，直接跳轉到步驟5.

步驟8 如果level

2 WPTS算法時(shí)間復雜度分析

任務(wù)合并過(guò)程是對DAG圖進(jìn)行一次深度優(yōu)先遍歷，因此其時(shí)間復雜度為O (v+e)，v為DAG圖中任務(wù)的數量，e為有向邊的數目。任務(wù)分層是從上到下計算每個(gè)節點(diǎn)的level值，時(shí)間復雜度為O (n+e)，n為任務(wù)合并后DAG圖中任務(wù)的數量。任務(wù)權值計算對DAG圖進(jìn)行廣度優(yōu)先遍圖3 任務(wù)到處理器映射階段流程歷，計算任務(wù)節點(diǎn)的weight值和尋找關(guān)鍵路徑節點(diǎn)，時(shí)間復雜度為O (n2)，因此任務(wù)優(yōu)先級計算階段的時(shí)間復雜度為O (v+e)+O (n+e)+O (n2);任務(wù)到處理器的映射階段考慮了處理器空閑時(shí)間段插入和任務(wù)復制技術(shù)，因此每層任務(wù)被映射到處理器上的時(shí)間復雜度為O (kp)，k為每層的任務(wù)數量，p為處理器的數量，冗余任務(wù)處理的時(shí)間復雜度為O (k2)，將所有任務(wù)映射到處理器上并完成調度結果優(yōu)化所需的時(shí)間復雜度為O (kpm+k2 m)，m 為任務(wù)DAG圖的層數，其在最壞情況下等于任務(wù)數量v.

圖3　任務(wù)到處理器映射階段流程

綜上所述，WPTS算法的時(shí)間復雜度為O (v+e)+O(n+e)+O (n2)+O (kpm+k2 m)，即O (v3)，算法沒(méi)有提高時(shí)間復雜度，且能有效處理使用任務(wù)復制技術(shù)帶來(lái)的冗余任務(wù)，減少任務(wù)的調度長(cháng)度，避免處理器資源的浪費。