李靜梅，王 雪，韓啟龍

(哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150001)

1 概述

多核處理器的產(chǎn)生為處理器性能的提升開辟了新的空間。如何將任務(wù)分配到具有不同計(jì)算性能的處理器內(nèi)核上執(zhí)行，從而獲得最短的調(diào)度長(zhǎng)度是影響異構(gòu)多核處理器性能發(fā)揮的關(guān)鍵問題之一［1］。

任務(wù)調(diào)度問題是NP 完全問題，無法在多項(xiàng)式時(shí)間內(nèi)獲得最優(yōu)解［2］。目前，應(yīng)用最為普遍的任務(wù)調(diào)度算法為啟發(fā)式任務(wù)調(diào)度算法，獲得的是近似最優(yōu)解［3］。啟發(fā)式任務(wù)調(diào)度算法包括表調(diào)度算法、任務(wù)復(fù)制算法和聚簇算法［4］。單獨(dú)應(yīng)用一種啟發(fā)式調(diào)度算法都存在適應(yīng)面受限以及調(diào)度性能不高的缺點(diǎn)。所以，在實(shí)際應(yīng)用中，往往在一個(gè)調(diào)度算法中結(jié)合多種啟發(fā)式算法，借鑒各算法的優(yōu)點(diǎn)，突破單一算法帶來的性能瓶頸，提高調(diào)度效率。

基于以上研究背景，本文提出一種異構(gòu)多核處理器(Multi-core Processor，CMP)啟發(fā)式綜合任務(wù)調(diào)度算法IHTSHMP(Integrated Heuristic Task Scheduling Algorithm for Heterogeneous Multi-core Processor)。該算法以表調(diào)度算法為基礎(chǔ)，從任務(wù)調(diào)度全局出發(fā)，設(shè)定任務(wù)調(diào)度優(yōu)先級(jí)，按照優(yōu)先級(jí)構(gòu)造任務(wù)調(diào)度列表。在調(diào)度過程中，利用任務(wù)復(fù)制技術(shù)進(jìn)行調(diào)度優(yōu)化。最后采用區(qū)間插入的方式將任務(wù)分配到處理器內(nèi)核上執(zhí)行，提高處理器利用率。

2 啟發(fā)式任務(wù)調(diào)度算法分析

本文的研究成果是基于表調(diào)度算法和任務(wù)復(fù)制算法提出的一種改進(jìn)的高效啟發(fā)式綜合任務(wù)調(diào)度算法。為更好地?cái)⑹霰疚牡难芯砍晒?，現(xiàn)對(duì)表調(diào)度算法和任務(wù)復(fù)制算法進(jìn)行分析，并著重分析其各自的優(yōu)缺點(diǎn)。

2.1 表調(diào)度算法

通常將表調(diào)度算法的執(zhí)行過程分為2 個(gè)部分:任務(wù)優(yōu)先級(jí)排序和映射任務(wù)到目標(biāo)處理器。首先依據(jù)優(yōu)先級(jí)權(quán)值的大小將任務(wù)添加到任務(wù)調(diào)度列表中，其次根據(jù)設(shè)定調(diào)度規(guī)則依序?qū)⒄{(diào)度列表中的任務(wù)分配到相應(yīng)的處理器內(nèi)核上執(zhí)行［5-6］。表調(diào)度算法是一種高效的啟發(fā)式算法，具有算法實(shí)現(xiàn)簡(jiǎn)單、調(diào)度額外開銷小和可預(yù)測(cè)性好等性能優(yōu)勢(shì)，在任務(wù)調(diào)度問題中應(yīng)用廣泛［7］。盡管表調(diào)度算法在性能提升方面有所裨益，但是優(yōu)化過程缺乏針對(duì)性，單純使用表調(diào)度技術(shù)很難得到理想的調(diào)度結(jié)果。表調(diào)度具體工作流程如圖1 所示。

圖1 表調(diào)度流程

2.2 任務(wù)復(fù)制算法

任務(wù)復(fù)制算法是指在任務(wù)調(diào)度過程中按照設(shè)定條件，將符合條件的任務(wù)冗余地復(fù)制到處理器內(nèi)核上，減少核間依賴任務(wù)的通信時(shí)延［8］。任務(wù)復(fù)制技術(shù)可有效縮短任務(wù)整體的完成時(shí)間，在本質(zhì)上是一種犧牲空間來?yè)Q取時(shí)間收益的方法。任務(wù)復(fù)制的關(guān)鍵在于如何選擇復(fù)制的任務(wù)。根據(jù)復(fù)制任務(wù)的個(gè)數(shù)，可以將任務(wù)復(fù)制算法分為單復(fù)制［9］和多復(fù)制［10］2 種，前者僅復(fù)制對(duì)當(dāng)前任務(wù)開始時(shí)間影響最大的節(jié)點(diǎn)到處理器內(nèi)核，后者復(fù)制多個(gè)符合條件的前驅(qū)任務(wù)。

在多核處理器系統(tǒng)中，利用任務(wù)復(fù)制將通信時(shí)延較大的核間開銷轉(zhuǎn)化為核內(nèi)開銷，縮短了任務(wù)執(zhí)行長(zhǎng)度。由于使用任務(wù)復(fù)制技術(shù)需要對(duì)任務(wù)前驅(qū)節(jié)點(diǎn)進(jìn)行搜索和對(duì)節(jié)點(diǎn)信息進(jìn)行存儲(chǔ)，因此任務(wù)復(fù)制算法可能會(huì)增加調(diào)度算法的時(shí)間復(fù)雜性和空間復(fù)雜性，若使用不當(dāng)會(huì)造成系統(tǒng)性能的下降。截至目前，任務(wù)復(fù)制算法雖然具有復(fù)雜性高的缺點(diǎn)，卻因其在減少通信開銷時(shí)間方面的貢獻(xiàn)而被廣泛應(yīng)用于任務(wù)調(diào)度算法中。

3 IHTSHMP 算法

本文針對(duì)現(xiàn)有啟發(fā)式任務(wù)調(diào)度算法存在的缺點(diǎn)與不足，提出一種異構(gòu)CMP 啟發(fā)式綜合任務(wù)調(diào)度算法IHTSHMP。IHTSHMP 算法采用表調(diào)度為主要思想將任務(wù)調(diào)度分為優(yōu)先級(jí)排序和任務(wù)分配2 個(gè)階段。首先利用全局調(diào)度優(yōu)化思想，設(shè)定優(yōu)先級(jí)權(quán)值，并以此為依據(jù)構(gòu)建任務(wù)執(zhí)行列表。其次在任務(wù)分配階段利用任務(wù)復(fù)制技術(shù)復(fù)制任務(wù)的關(guān)鍵前驅(qū)節(jié)點(diǎn)，并以區(qū)間插入式的分配方式將任務(wù)分配到處理器內(nèi)核上執(zhí)行，進(jìn)一步優(yōu)化任務(wù)調(diào)度效率。

3.1 調(diào)度模型

調(diào)度模型包括任務(wù)模型和處理器模型，假設(shè)任務(wù)數(shù)為N，處理器內(nèi)核數(shù)為M。

(1)任務(wù)模型

為分析任務(wù)間的依賴關(guān)系，采用圖論中的有向無環(huán)圖(Directed Acyclic Graph，DAG)來表示任務(wù)的執(zhí)行屬性及依賴關(guān)系。

DAG 任務(wù)圖G=(V，E，τ，c)為一個(gè)四元組。其中，V 為長(zhǎng)度為N 的任務(wù)節(jié)點(diǎn)集合;元素ni表示集合中的第i 個(gè)元素，0≤i≤N -1;E 為任務(wù)圖中有向邊的集合，表示任務(wù)之間的依賴關(guān)系;τ 為任務(wù)執(zhí)行時(shí)間的集合，元素τ(ni，pu)表示任務(wù)ni在內(nèi)核pu上的執(zhí)行時(shí)間，在DAG 任務(wù)圖中表現(xiàn)為節(jié)點(diǎn)的權(quán)值;c 為依賴任務(wù)之間通信時(shí)延的集合，元素cij表示任務(wù)ni和nj之間的通信時(shí)延大小，在DAG 任務(wù)圖中表現(xiàn)為有向邊的權(quán)值。如圖2 所示為一個(gè)具有10 個(gè)節(jié)點(diǎn)的DAG 任務(wù)圖。

圖2 具有10 個(gè)節(jié)點(diǎn)的DAG 任務(wù)圖

在DAG 任務(wù)圖中，對(duì)于任意任務(wù)ni都有直接前驅(qū)節(jié)點(diǎn)集合prep(ni)、關(guān)鍵前驅(qū)節(jié)點(diǎn)fprep(ni)、后繼節(jié)點(diǎn)集合succ(ni)、在任意核pu上的最開始時(shí)間est(ni，pu)和最早完成時(shí)間eft(ni，pu)5 個(gè)重要屬性。其中，est(ni，pu)和eft(ni，pu)的定義分別如式(1)、式(2)所示。在式(1)中，p_avail 為處理器內(nèi)核可利用時(shí)間，即處理器可以接受并執(zhí)行任務(wù)的開始時(shí)間。

(2)處理器模型

本文的研究平臺(tái)是異構(gòu)多核處理器，假設(shè)處理器結(jié)構(gòu)為片上全相連網(wǎng)狀結(jié)構(gòu)，任意2 個(gè)內(nèi)核之間可以直接通信。定義處理器內(nèi)核集合P，集合元素pu為第u 個(gè)內(nèi)核，1≤u≤M。

3.2 優(yōu)先級(jí)計(jì)算

關(guān)鍵路徑是DAG 任務(wù)圖的最長(zhǎng)路徑，是獲得任務(wù)圖最短調(diào)度長(zhǎng)度的瓶頸所在，所以對(duì)關(guān)鍵任務(wù)的合理調(diào)度也顯得尤為重要。IHTSHMP 算法首先在調(diào)度的各個(gè)環(huán)節(jié)都賦予關(guān)鍵路徑節(jié)點(diǎn)最高優(yōu)先級(jí)。此外，針對(duì)現(xiàn)有表調(diào)度算法中依據(jù)任務(wù)的局部信息定義任務(wù)優(yōu)先級(jí)，致使后續(xù)的關(guān)鍵任務(wù)無法優(yōu)先調(diào)度的問題，本文算法提出一種以優(yōu)先級(jí)權(quán)值weighti定義任務(wù)優(yōu)先級(jí)的方式。優(yōu)先級(jí)權(quán)值的選取充分考慮到整個(gè)任務(wù)圖拓?fù)浣Y(jié)構(gòu)，定義為任務(wù)在當(dāng)前格局下向后關(guān)鍵路徑的執(zhí)行時(shí)間，并按權(quán)值降序排序任務(wù)優(yōu)先級(jí)。優(yōu)先級(jí)權(quán)值weighti的計(jì)算方式如式(3)所示:

其中，cp_value(ni)的定義如式(4)所示;ncp表示當(dāng)前任務(wù)節(jié)點(diǎn)的直接后繼關(guān)鍵路徑節(jié)點(diǎn)。

3.3 任務(wù)分配

為簡(jiǎn)化算法復(fù)雜度，選擇任務(wù)完成時(shí)間最早的處理器內(nèi)核為目標(biāo)處理器內(nèi)核。在此基礎(chǔ)上，IHTSHMP 算法采用任務(wù)復(fù)制的分配思想和區(qū)間插入的分配方式對(duì)任務(wù)分配階段進(jìn)行優(yōu)化。使用多復(fù)制的任務(wù)復(fù)制技術(shù)，循環(huán)判斷任務(wù)是否滿足復(fù)制條件。若復(fù)制關(guān)鍵前驅(qū)節(jié)點(diǎn)可以提早任務(wù)的最早開始時(shí)間，則復(fù)制其到處理器內(nèi)核上，更新任務(wù)的關(guān)鍵前驅(qū)節(jié)點(diǎn)。判斷不采用任務(wù)復(fù)制情況下的任務(wù)最早完成時(shí)間est(ni)和采用任務(wù)復(fù)制2 種情況下的任務(wù)最早完成時(shí)間est2(ni)。若est(ni)＞est2(ni)，則復(fù)制關(guān)鍵前驅(qū)節(jié)點(diǎn)到處理器內(nèi)核。est2(ni)的計(jì)算方法如式(5)所示。

任務(wù)復(fù)制過程如圖3 所示。區(qū)間插入是指在任務(wù)分配時(shí)，將任務(wù)分配到2 個(gè)已調(diào)度任務(wù)之間的處理器內(nèi)核空閑時(shí)間段上。它是提高處理器利用率的有效手段。特別地，將處理器內(nèi)核最后一個(gè)任務(wù)完成且可執(zhí)行新任務(wù)的時(shí)間作為一個(gè)處理器空閑區(qū)間的開始時(shí)間，其結(jié)束時(shí)間為∞。

圖3 任務(wù)復(fù)制過程

若滿足式(6)，則將任務(wù)分配到該空閑時(shí)間段上執(zhí)行。

其中，Spaces和Spacee分別為處理器內(nèi)核空閑時(shí)間段的開始時(shí)間和結(jié)束時(shí)間。

4 性能測(cè)試

將本文算法與基于關(guān)鍵前驅(qū)復(fù)制的CPFD(Critical Path Fast Duplication)算法［11］和選擇性任務(wù)復(fù)制的表調(diào)度STDH(Selected Task Duplication for Heterogeneous System)算法［12］在同等條件下進(jìn)行模擬實(shí)驗(yàn)。為進(jìn)一步進(jìn)行性能驗(yàn)證，本文引入調(diào)度長(zhǎng)度比率(Schedule Length Ratio，SLR)和加速比speedup 作為算法性能評(píng)估參數(shù)。

(1)關(guān)鍵路徑是DAG 任務(wù)圖的最長(zhǎng)路徑，是任務(wù)調(diào)度長(zhǎng)度的瓶頸所在。SLR 反映了任務(wù)圖相對(duì)于關(guān)鍵路徑的執(zhí)行情況。SLR 的計(jì)算公式rSLR如式(7)所示。

其中，makespan 表示任務(wù)圖的調(diào)度長(zhǎng)度，即任務(wù)映射圖中最后一個(gè)任務(wù)的完成時(shí)間;CP 為各關(guān)鍵路徑節(jié)點(diǎn)在各處理器內(nèi)核上平均執(zhí)行開銷之和。關(guān)鍵路徑作為任務(wù)圖中最長(zhǎng)的一條執(zhí)行路徑，是整個(gè)任務(wù)調(diào)度長(zhǎng)度的瓶頸所在，SLR 越小則證明任務(wù)調(diào)度算法的性能越好。

(2)加速比speedup 反映的是程序的并行化執(zhí)行程度。定義為任務(wù)的串行執(zhí)行時(shí)間與任務(wù)圖實(shí)際調(diào)度長(zhǎng)度的比值，加速比越大則證明算法并行化程度越高，調(diào)度性能越好。speedup 的計(jì)算方式如式(8)所示。

本文采用隨機(jī)任務(wù)圖作為測(cè)試用例，對(duì)算法性能進(jìn)行驗(yàn)證。為控制產(chǎn)生任務(wù)圖的形狀和大小等屬性，對(duì)任務(wù)圖的參數(shù)取值范圍進(jìn)行設(shè)定。設(shè)定任務(wù)圖中任務(wù)個(gè)數(shù)N={20，30，40，50，60，70，80，90，100};任務(wù)圖中節(jié)點(diǎn)的最大出度α={1，2，5，10，100};任務(wù)圖中任務(wù)的通信時(shí)間與執(zhí)行時(shí)間比值參數(shù)CCR={0.1，0.5，1.0，5.0，10.0};任務(wù)在不同處理器內(nèi)核上執(zhí)行時(shí)間差異度參數(shù)β={0.1，0.5，1，1.5，2}。通過對(duì)以上參數(shù)的設(shè)定，產(chǎn)生1 125 組任務(wù)圖類型。從每組類型中隨機(jī)地選擇10 個(gè)任務(wù)圖，此時(shí)可以生成11 250 個(gè)任務(wù)圖。對(duì)產(chǎn)生的11 250 個(gè)任務(wù)圖在模擬平臺(tái)上進(jìn)行調(diào)度，評(píng)測(cè)算法性能。

將IHTSHMP 算法與已有CPFD 算法和STDH 算法分別在不同任務(wù)數(shù)和不同通信計(jì)算比率(Communication Computation Ratio，CCR)的情況下對(duì)3 種算法的speedup 和SLR 性能進(jìn)行對(duì)比分析。得到算法在不同任務(wù)數(shù)情況下的平均speedup 和平均SLR 結(jié)果對(duì)比圖，分別如圖4 和圖5 所示;不同CCR情況下的平均speedup 和平均SLR 結(jié)果對(duì)比圖，分別如圖6 和圖7 所示。

圖4 不同任務(wù)數(shù)下的平均加速比對(duì)比

圖5 不同任務(wù)數(shù)下的平均SLR 對(duì)比

圖6 不同CCR 下的平均加速比對(duì)比

圖7 不同CCR 下的平均SLR 對(duì)比

由圖4 和圖5 所示，在不同任務(wù)數(shù)的情況下，IHTSHMP 算法始終保持較高的調(diào)度性能，與CPFD 算法和STDH 算法相比，IHTSHMP 算法加速比speedup約分別提高17.20%和9.81%，調(diào)度下界比SLR 約分別降低15.40%和8.15%。由圖6 和圖7 所示，在不同CCR 下，IHTSHMP 算法性能較為平穩(wěn)，與CPFD 算法和STDH 算法相比，加速比speedup 約分別提高16.35%和9.08%，調(diào)度下界比SLR 約分別降低14.53%和8.10%。由實(shí)驗(yàn)結(jié)果對(duì)比分析可知，IHTSHMP 算法有效優(yōu)化任務(wù)調(diào)度性能。

5 結(jié)束語(yǔ)

本文提出一種異構(gòu)CMP 架構(gòu)下的啟發(fā)式綜合任務(wù)調(diào)度算法。該算法綜合2 種啟發(fā)式算法完成任務(wù)調(diào)度過程，克服了現(xiàn)有算法中存在的不足，提高調(diào)度效率，在優(yōu)先級(jí)權(quán)值設(shè)定時(shí)，充分考慮任務(wù)拓?fù)鋱D結(jié)構(gòu)，提高了全局調(diào)度效率;在任務(wù)分配時(shí)，采取了對(duì)于減少依賴任務(wù)通信延遲有效的多任務(wù)復(fù)制技術(shù)和對(duì)于提升處理器利用率有效的區(qū)間插入方式，進(jìn)一步優(yōu)化調(diào)度。性能測(cè)試結(jié)果表明，本文算法能有效減少任務(wù)調(diào)度長(zhǎng)度，充分發(fā)揮異構(gòu)CMP 的優(yōu)勢(shì)。

［1］李靜梅，張 博.基于混合粒子群優(yōu)化的CMP 線程調(diào)度方法［J］.計(jì)算機(jī)工程，2012，38(20):113-115.

［2］Ullman J D.NP-complete Scheduling Problem ［J］.Journal of Computer and System Sciences，1975，10(3):384-393.

［3］梁洪濤，袁由光，方 明.一種基于任務(wù)全局遷移的靜態(tài)調(diào)度算法［J］.計(jì)算機(jī)研究與發(fā)展，2006，43(5):797-804.

［4］Prashanth C，Ranga S.Algorithms for Task Scheduling in Heterogeneous Computing Environments ［D］.Alabama，USA:Auburn University，2006.

［5］Palmer A，Sinnen O.Scheduling Algorithm Based on Force Directed Clustering ［C］//Proc.of the 9th International Conference on Parallel and Distributed Computing，Applications and Technologies.［S.l.］:IEEE Press，2008:311-318.

［6］邢建生，王永吉，劉軍祥，等.一種靜態(tài)最少優(yōu)先級(jí)分配算法［J］.軟件學(xué)報(bào)，2007，18(7):1844-1854.

［7］Hwang R，Gen M，Katayama H.A Comparison of Multiprocessor Task Scheduling Algorithms with Communication Costs［J］.Computer ＆ Operations Research，2008，35(3):976-993.

［8］林劍檸，吳慧中，陳學(xué)勤.基于任務(wù)復(fù)制的網(wǎng)格任務(wù)調(diào)度算法［J］.計(jì)算機(jī)科學(xué)，2006，33(6):89-92.

［9］何 琨，趙 勇，黃文奇.基于任務(wù)復(fù)制的分簇與調(diào)度算法［J］.計(jì)算機(jī)學(xué)報(bào)，2008，31(5):733-740.

［10］Darbha S，Agrawal D P.Optimal Scheduling Algorithm for Distributed-memory Machines［J］.IEEE Transactions on Parallel and Distributed Systems，1998，9(1):87-95.

［11］Ahmad I，Kwok Y K.On Exploiting Task Duplication in Parallel Program Scheduling［J］.IEEE Transactions on Parallel and Distributed Systems，1998，9(9):872-877.

［12］孟憲福，劉偉偉.基于選擇性復(fù)制前驅(qū)任務(wù)的DAG 調(diào)度算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)報(bào)，2010，22(6):1056-1062.