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

摘 要：針對現存任務(wù)調度算法優(yōu)先級選取過(guò)于單一、冗余任務(wù)處理較晚的問(wèn)題，提出一種基于加權優(yōu)先級的任務(wù)調度算法-WPTS算法。該算法綜合考慮任務(wù)3個(gè)屬性的加權值以決定任務(wù)被處理的先后次序，從而克服了任務(wù)選取時(shí)的單一性問(wèn)題。在將任務(wù)分配到處理器的過(guò)程中，保證任務(wù)優(yōu)先調度到完成時(shí)間最早的處理器上。同時(shí)，引入冗余任務(wù)處理過(guò)程，及時(shí)消除冗余任務(wù)，達到對處理器空閑時(shí)間段進(jìn)行有效回收、減少處理器調度長(cháng)度的效果。性能對比實(shí)驗表明，WPTS算法較CPFD算法、HCPFD算法和HDEFT算法能取得更好的性能。

0 引 言

異構多核處理器以其芯片面積利用率高、處理器功耗低、應用程序的并行化程度高等諸多優(yōu)勢成為處理器體系結構發(fā)展的一個(gè)重要方向，同時(shí)它的出現給計算機學(xué)科發(fā)展帶來(lái)了新的挑戰。研究發(fā)現多核處理器任務(wù)調度的優(yōu)劣對處理器的執行時(shí)間、任務(wù)調度長(cháng)度、處理器的功耗等諸多性能產(chǎn)生直接影響。因此，多核處理器的任務(wù)調度作為影響操作系統性能的重要因素成為近年來(lái)系統結構方向的熱點(diǎn)研究問(wèn)題之一。當前對異構多核處理器上任務(wù)調度的研究很少考慮任務(wù)優(yōu)先級的選取對調度結果的影響以及使用復制技術(shù)的任務(wù)調度算法會(huì )產(chǎn)生冗余任務(wù)的問(wèn)題。

本文深入分析了CPFD、HCPFD和HDEFT這3種最具有代表性的任務(wù)調度算法，并在總結目前任務(wù)調度算法存在的缺點(diǎn)基礎上，根據異構多核處理器系統結構的特點(diǎn)，設計了基于加權優(yōu)先級的任務(wù)調度算法(weighted prioritytask scheduling,WPTS)，算法以3個(gè)參數構成的加權值作為任務(wù)的優(yōu)先級，將任務(wù)排序構成任務(wù)調度列表，然后依次將任務(wù)映射到處理器上，并在映射過(guò)程中對任務(wù)進(jìn)行優(yōu)化處理，最后通過(guò)預先設定的性能評價(jià)參數對算法進(jìn)行實(shí)驗驗證。本研究能有效改善原有任務(wù)調度算法的不足，提升了多核處理器在實(shí)際應用中的性能，對異構多核處理器上靜態(tài)任務(wù)調度技術(shù)的發(fā)展具有重大理論和現實(shí)意義。

1 WPTS算法設計

1.1 3種現有高效算法的分析

目前基于異構多核處理器取得較好調度性能的算法有CPFD算法、HCPFD算法和HDEFT算法。CPFD算法使用任務(wù)節點(diǎn)到入口節點(diǎn)的最長(cháng)路徑b-level作為任務(wù)調度的優(yōu)先級，將任務(wù)調度到具有最早完成時(shí)間的處理器上，其時(shí)間復雜度是O (v4)，v是DAG圖中任務(wù)節點(diǎn)的數目。

HCPFD算法以關(guān)鍵任務(wù)和任務(wù)的最晚開(kāi)始時(shí)間劃分任務(wù)的優(yōu)先級，將任務(wù)分配到使其完成時(shí)間最早的處理器節點(diǎn)上，在任務(wù)到處理器的映射階段優(yōu)先考慮使用處理器上的空閑時(shí)間段來(lái)處理任務(wù)，其時(shí)間復雜度為O (pv2)，p是任務(wù)調度中處理器的總個(gè)數。HDEFT算法在任務(wù)分配階段采用sumu (vi)作為任務(wù)優(yōu)先級，在任務(wù)到處理器的映射階段使用任務(wù)插入和復制技術(shù)，其時(shí)間復雜度為O (pv2)。

CPFD算法和HCPFD算法的調度性能不夠理想，原因在于算法只選擇唯一任務(wù)屬性作為任務(wù)的優(yōu)先級，沒(méi)有考慮任務(wù)間的約束關(guān)系和通信開(kāi)銷(xiāo)等影響調度性能的重要因素。HDEFT算法時(shí)間復雜度不高，但沒(méi)有對使用任務(wù)復制技術(shù)后存在的冗余任務(wù)進(jìn)行處理，冗余任務(wù)延長(cháng)了總的任務(wù)調度完成時(shí)間，浪費了處理器資源。

本文在總結并分析上述算法不足的基礎上，設計出WPTS算法，并給出任務(wù)調度實(shí)驗以驗證新算法的正確性和有效性。

1.2 WPTS算法執行過(guò)程

WPTS算法的執行分為兩個(gè)階段：任務(wù)優(yōu)先級計算和任務(wù)到處理器的映射。其中第一階段包括任務(wù)合并、任務(wù)分層和任務(wù)權值計算3個(gè)過(guò)程，第二階段包括任務(wù)分配到處理器和任務(wù)調度結果優(yōu)化兩個(gè)過(guò)程，如圖1所示。

圖1 WPTS算法執行過(guò)程

1.3 WPTS算法實(shí)現原理

1.3.1 任務(wù)優(yōu)先級計算階段

(1)任務(wù)優(yōu)先級計算階段的設計思想任務(wù)合并是將任務(wù)中較獨立、任務(wù)間通信開(kāi)銷(xiāo)較大的任務(wù)進(jìn)行合并優(yōu)化。對DAG圖進(jìn)行深度優(yōu)先搜索,當任務(wù)vi只有一個(gè)直接后繼節點(diǎn)vj、任務(wù)vj只有一個(gè)直接前驅節點(diǎn)vi,且c (vi,vj)≥wj,k,即任務(wù)vi、vj間的通信開(kāi)銷(xiāo)大于任務(wù)vj在所有處理器上的平均執行開(kāi)銷(xiāo),則合并任務(wù)vi、vj,并記為vi*,vi*的計算開(kāi)銷(xiāo)為vi、vj計算開(kāi)銷(xiāo)的總和,在隨后的調度中任務(wù)vi*被作為整體處理。

任務(wù)分層是為方便后續任務(wù)權值的計算。用level標記任務(wù)在DAG圖中的層數,設置入口節點(diǎn)任務(wù)l(shuí)evel=0,從上到下遍歷任務(wù)DAG圖,計算任務(wù)節點(diǎn)到入口節點(diǎn)的最大通信邊數目,以此作為任務(wù)的level值。非入口節點(diǎn)任務(wù)vi的level值為其所有前驅節點(diǎn)的最大level值加1,計算公式如下所示level(vi)=Max (level(vj))+1,vj∈pred (vi)(1)在任務(wù)權值計算過(guò)程中,WPTS算法綜合考慮任務(wù)各屬性對任務(wù)優(yōu)先級排序的影響,選擇使用平均計算開(kāi)銷(xiāo)和通信開(kāi)銷(xiāo)作為任務(wù)的優(yōu)先級參數。平均計算開(kāi)銷(xiāo)ACC是任務(wù)在所有處理器上計算開(kāi)銷(xiāo)的平均值,計算公式如式(2)所示。通信開(kāi)銷(xiāo)包括平均數據傳輸開(kāi)銷(xiāo)ADTC和平均數據接收開(kāi)銷(xiāo)ADRC,計算公式如式(3)和式(4)所示,式中x為vi直接后繼節點(diǎn)數量,y為vi直接前驅節點(diǎn)數量

定義weight (vi)為任務(wù)vi的權值,它是任務(wù)的ADTC、ADRC、ACC之和,對每個(gè)處在level=i層的任務(wù)來(lái)說(shuō)weight(vi)的計算公式如公式下所示weight(vi)=ADTC (vi)+ADRC (vi)+ACC (vi)(5)(2)任務(wù)優(yōu)先級計算階段流程

任務(wù)優(yōu)先級計算流程如圖2所示。

圖2　任務(wù)優(yōu)先級計算階段流程

任務(wù)優(yōu)先級計算階段完成后，所有的任務(wù)已經(jīng)按照優(yōu)先級從高到低的次序加入到調度列表中，可以繼續執行任務(wù)到處理器映射階段的步驟。

1.3.2 任務(wù)到處理器映射階段

(1)任務(wù)到處理器映射階段的設計思想

任務(wù)到處理器映射階段包括任務(wù)映射到處理器和處理圖2 任務(wù)優(yōu)先級計算階段流程器上的冗余任務(wù)處理。

在任務(wù)映射到處理器的過(guò)程中，遍歷所有處理器，直接將任務(wù)vi分配到具有最早完成時(shí)間的處理器上，其完成時(shí)間記為EFT1;將vi分配具有空閑時(shí)間段的處理器上且不使用任務(wù)復制技術(shù)的最早完成時(shí)間為EFT2;記使用復制任務(wù)技術(shù)復制任務(wù)vi的直接前驅節點(diǎn)到vi所處的處理器空閑時(shí)間段上最早完成時(shí)間為EFT3.比較三者的值，將任務(wù)vi分配到具有最小完成時(shí)間的處理器上。EFT1、EFT2、EFT3的計算公式如下