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

式中：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執(zhí)行完分配到其上的所有任務(wù)的時(shí)間。

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

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

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

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

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

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

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

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

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

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

步驟8 如果level

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

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

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

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