摘 要：針對現(xiàn)存任務調度算法優(yōu)先級選取過于單一、冗余任務處理較晚的問題，提出一種基于加權優(yōu)先級的任務調度算法-WPTS算法。該算法綜合考慮任務3個屬性的加權值以決定任務被處理的先后次序，從而克服了任務選取時的單一性問題。在將任務分配到處理器的過程中，保證任務優(yōu)先調度到完成時間最早的處理器上。同時，引入冗余任務處理過程，及時消除冗余任務，達到對處理器空閑時間段進行有效回收、減少處理器調度長度的效果。性能對比實驗表明，WPTS算法較CPFD算法、HCPFD算法和HDEFT算法能取得更好的性能。
0 引 言
異構多核處理器以其芯片面積利用率高、處理器功耗低、應用程序的并行化程度高等諸多優(yōu)勢成為處理器體系結構發(fā)展的一個重要方向，同時它的出現(xiàn)給計算機學科發(fā)展帶來了新的挑戰(zhàn)。研究發(fā)現(xiàn)多核處理器任務調度的優(yōu)劣對處理器的執(zhí)行時間、任務調度長度、處理器的功耗等諸多性能產(chǎn)生直接影響。因此，多核處理器的任務調度作為影響操作系統(tǒng)性能的重要因素成為近年來系統(tǒng)結構方向的熱點研究問題之一。當前對異構多核處理器上任務調度的研究很少考慮任務優(yōu)先級的選取對調度結果的影響以及使用復制技術的任務調度算法會產(chǎn)生冗余任務的問題。
本文深入分析了CPFD、HCPFD和HDEFT這3種最具有代表性的任務調度算法，并在總結目前任務調度算法存在的缺點基礎上，根據(jù)異構多核處理器系統(tǒng)結構的特點，設計了基于加權優(yōu)先級的任務調度算法（weighted prioritytask scheduling,WPTS），算法以3個參數(shù)構成的加權值作為任務的優(yōu)先級，將任務排序構成任務調度列表，然后依次將任務映射到處理器上，并在映射過程中對任務進行優(yōu)化處理，最后通過預先設定的性能評價參數(shù)對算法進行實驗驗證。本研究能有效改善原有任務調度算法的不足，提升了多核處理器在實際應用中的性能，對異構多核處理器上靜態(tài)任務調度技術的發(fā)展具有重大理論和現(xiàn)實意義。
1 WPTS算法設計
1.1 3種現(xiàn)有高效算法的分析
目前基于異構多核處理器取得較好調度性能的算法有CPFD算法、HCPFD算法和HDEFT算法。CPFD算法使用任務節(jié)點到入口節(jié)點的最長路徑b-level作為任務調度的優(yōu)先級，將任務調度到具有最早完成時間的處理器上，其時間復雜度是O （v4），v是DAG圖中任務節(jié)點的數(shù)目。
HCPFD算法以關鍵任務和任務的最晚開始時間劃分任務的優(yōu)先級，將任務分配到使其完成時間最早的處理器節(jié)點上，在任務到處理器的映射階段優(yōu)先考慮使用處理器上的空閑時間段來處理任務，其時間復雜度為O （pv2），p是任務調度中處理器的總個數(shù)。HDEFT算法在任務分配階段采用sumu （vi）作為任務優(yōu)先級，在任務到處理器的映射階段使用任務插入和復制技術，其時間復雜度為O （pv2）。
下載文檔
