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

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

0 引 言

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

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

1 WPTS算法設(shè)計(jì)

1.1 3種現(xiàn)有高效算法的分析

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

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

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

本文在總結(jié)并分析上述算法不足的基礎(chǔ)上，設(shè)計(jì)出WPTS算法，并給出任務(wù)調(diào)度實(shí)驗(yàn)以驗(yàn)證新算法的正確性和有效性。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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