基于異構(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）。