基于異構(gòu)多核處理器的靜態(tài)任務(wù)調(diào)度研究(一)
式中:AST (vi,pn)-任務(wù)vi在處理器pn上的實際開始時間;AFT (vi,pk)-任務(wù)vi在處理器pk上的實際完成時間;vpar-最后一個與任務(wù)vi通信的任務(wù);Avail(pn)-處理器pn執(zhí)行完分配到其上的所有任務(wù)的時間。
通過對DAG圖的深入研究發(fā)現(xiàn),某層冗余任務(wù)的處理在其下一層任務(wù)到處理器的映射之后執(zhí)行效果最好,如對level=1層任務(wù)調(diào)度完成后對level=0層任務(wù)進行冗余判斷,將任務(wù)分配到處理器和冗余任務(wù)處理兩個過程交替執(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,遍歷所有處理器,如果處理器存在空閑時間段且滿足vi插入條件,則將vi分配到空閑時間段,并計算其最小最早完成時間,記為EFT1;否則向下執(zhí)行步驟3.
步驟3 計算將vi分配到所有處理器上的最小最早完成時間,記為EFT2.如果處理器上存在空閑時間段且能使用任務(wù)復(fù)制技術(shù),則計算在處理器上復(fù)制vi的前驅(qū)獲得最小最早完成時間,記為EFT3,繼續(xù)執(zhí)行步驟4.
步驟4 選擇EFT1、EFT2、EFT3的最小值,并將任務(wù)分配到具有最早完成時間的處理器上,從調(diào)度列表中刪除vi,建立冗余任務(wù)列表RTL,將被復(fù)制的任務(wù)加入到RTL中,格式為vi,0~vi,k,vi為被復(fù)制的任務(wù)節(jié)點,k為任務(wù)所在處理器的編號。
步驟5 判斷RTL中是否有(level-1)層任務(wù),如果是則跳轉(zhuǎn)到步驟6;否則跳轉(zhuǎn)到步驟8.
步驟6 取RTL首任務(wù)節(jié)點,記為vi,k,判斷刪除任務(wù)vi,k后vi,k直接后繼節(jié)點的最早開始時間是否延遲,如果延遲,判定任務(wù)vi,k非冗余任務(wù),從RTL中刪除vi,k,跳轉(zhuǎn)到步驟5;否則判定任務(wù)vi,k為冗余節(jié)點,從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算法時間復(fù)雜度分析
任務(wù)合并過程是對DAG圖進行一次深度優(yōu)先遍歷,因此其時間復(fù)雜度為O (v+e),v為DAG圖中任務(wù)的數(shù)量,e為有向邊的數(shù)目。任務(wù)分層是從上到下計算每個節(jié)點的level值,時間復(fù)雜度為O (n+e),n為任務(wù)合并后DAG圖中任務(wù)的數(shù)量。任務(wù)權(quán)值計算對DAG圖進行廣度優(yōu)先遍圖3 任務(wù)到處理器映射階段流程歷,計算任務(wù)節(jié)點的weight值和尋找關(guān)鍵路徑節(jié)點,時間復(fù)雜度為O (n2),因此任務(wù)優(yōu)先級計算階段的時間復(fù)雜度為O (v+e)+O (n+e)+O (n2);任務(wù)到處理器的映射階段考慮了處理器空閑時間段插入和任務(wù)復(fù)制技術(shù),因此每層任務(wù)被映射到處理器上的時間復(fù)雜度為O (kp),k為每層的任務(wù)數(shù)量,p為處理器的數(shù)量,冗余任務(wù)處理的時間復(fù)雜度為O (k2),將所有任務(wù)映射到處理器上并完成調(diào)度結(jié)果優(yōu)化所需的時間復(fù)雜度為O (kpm+k2 m),m 為任務(wù)DAG圖的層數(shù),其在最壞情況下等于任務(wù)數(shù)量v.
圖3 任務(wù)到處理器映射階段流程
綜上所述,WPTS算法的時間復(fù)雜度為O (v+e)+O(n+e)+O (n2)+O (kpm+k2 m),即O (v3),算法沒有提高時間復(fù)雜度,且能有效處理使用任務(wù)復(fù)制技術(shù)帶來的冗余任務(wù),減少任務(wù)的調(diào)度長度,避免處理器資源的浪費。
評論