基于EDA多任務(wù)流的調(diào)度算法研究

王 靜，陳 嵐，張 賀，王海永

（1.中國科學(xué)院微電子研究所，北京 100029；2.中國科學(xué)院大學(xué)，北京 100049；3.三維及納米集成電路設(shè)計自動化技術(shù)北京市重點(diǎn)實(shí)驗室，北京 100029）

0 概述

隨著超大規(guī)模集成電路的發(fā)展，電子設(shè)計自動化（Electronic Design Automation，EDA）技術(shù)在高性能集群上的公平調(diào)度問題受到研究人員的廣泛關(guān)注［1］。EDA包含RTL仿真、邏輯綜合、靜態(tài)時序分析、布局布線、寄生參數(shù)提取和物理驗證等仿真任務(wù)，這些任務(wù)之間有先后依賴關(guān)系［2］，可以組成EDA任務(wù)流。有向無環(huán)圖（Directed Acyclic Graph，DAG）［3］是任務(wù)流中常用的描述方法，其調(diào)度問題被證明是NP完全問題［4］。

近年來，HEFT［5］、PETS［6］、PEFT［7-8］、CPOP［9］和TDNH［10］等單DAG任務(wù)調(diào)度問題已發(fā)展成熟，而多DAG任務(wù)調(diào)度問題逐漸成為研究熱點(diǎn)。傳統(tǒng)多DAG調(diào)度方法是將所有DAG放入一個隊列中按順序依次完成調(diào)度，但其不能充分利用集群資源。為提高資源利用率，文獻(xiàn)［11］提出將多個DAG合并為一個DAG，并按照單DAG算法調(diào)度，但由于每個DAG的結(jié)構(gòu)不同，因此其存在不公平調(diào)度問題。文獻(xiàn)［12］提出Fairness算法，該算法依據(jù)任務(wù)滯后度來決定準(zhǔn)備隊列的任務(wù)優(yōu)先級，當(dāng)任務(wù)具有相同的滯后度時采用剩余完成時間決定優(yōu)先級，這樣會導(dǎo)致剩余完成時間短的任務(wù)長時間處于等待狀態(tài)。文獻(xiàn)［13］在任務(wù)具有相同滯后度時，使用已執(zhí)行時間與總時間的比值作為優(yōu)先級，但其未考慮比值相同的情況以及l(fā)icense調(diào)度，不適用于EDA任務(wù)流并且未考慮用戶服務(wù)質(zhì)量問題。文獻(xiàn)［14］提出DAG公平調(diào)度算法，該算法考慮了用戶服務(wù)質(zhì)量，但未考慮license調(diào)度問題。文獻(xiàn)［15］使用動態(tài)調(diào)度模型解決不同時間到達(dá)的DAG調(diào)度問題，但該模型僅適用于多個結(jié)構(gòu)相似DAG之間的調(diào)度問題。文獻(xiàn)［16］提出基于最小化數(shù)據(jù)傳輸時間和任務(wù)完成時間的多DAG調(diào)度算法，該算法避免了額外的數(shù)據(jù)傳輸開銷，但會導(dǎo)致負(fù)載不均衡問題。文獻(xiàn)［17］基于Fairness算法提出網(wǎng)格環(huán)境下的動態(tài)多DAG調(diào)度算法，該算法使用關(guān)鍵路徑確定優(yōu)先級并采用回填策略分配節(jié)點(diǎn)，提高了調(diào)度公平性，但未考慮license調(diào)度問題，不適用于EDA任務(wù)流。為保證調(diào)度公平性并提高用戶服務(wù)質(zhì)量，本文在Fairness算法的基礎(chǔ)上添加任務(wù)完成度作為任務(wù)選擇依據(jù)，同時將EDA任務(wù)組建成任務(wù)流并抽象為DAG結(jié)構(gòu)，提出面向EDA任務(wù)流調(diào)度的公平調(diào)度算法L-Fairness。

1 多DAG調(diào)度系統(tǒng)

動態(tài)多DAG任務(wù)調(diào)度系統(tǒng)模型如圖1所示。該系統(tǒng)由初始優(yōu)先級判別子系統(tǒng)、公平調(diào)度子系統(tǒng)和處理器分配子系統(tǒng)3個部分組成：1）初始優(yōu)先級判別子系統(tǒng)針對每個DAG（kk=1～n，n為DAG數(shù)量）中任務(wù)依賴關(guān)系確定優(yōu)先級，將每個DAGk優(yōu)先級最高的任務(wù)放入準(zhǔn)備隊列；2）公平調(diào)度子系統(tǒng)負(fù)責(zé)將準(zhǔn)備隊列中不同DAG的任務(wù)根據(jù)公平性原則進(jìn)行重新排序，選擇優(yōu)先級最高的任務(wù)準(zhǔn)備調(diào)度；3）處理器分配子系統(tǒng)負(fù)責(zé)將待調(diào)度任務(wù)分配到最合適的處理器執(zhí)行任務(wù)。

圖1 多DAG調(diào)度系統(tǒng)模型Fig.1 Model of multi-DAG scheduling system

2 L-Fairness算法實(shí)現(xiàn)

2.1 初始優(yōu)先級判別子系統(tǒng)

一個DAG工作流可以表示為G=（V，E，C），其中，V是任務(wù)節(jié)點(diǎn)集合，E是任務(wù)節(jié)點(diǎn)間有向邊的集合，C是有向邊的權(quán)值集合。有向邊（i，j）表示任務(wù)節(jié)點(diǎn)ni和nj之間的先后執(zhí)行關(guān)系，即ni必須在nj之前完成，有向邊上的權(quán)值表示任務(wù)之間數(shù)據(jù)傳遞的平均時間。向上權(quán)值表示任務(wù)節(jié)點(diǎn)ni到退出任務(wù)節(jié)點(diǎn)nexit的最長路徑長度，向上權(quán)值從退出任務(wù)節(jié)點(diǎn)開始，可被遞歸地定義為：

其中，h（n）i表示任務(wù)ni的直接后繼節(jié)點(diǎn)集合表示任務(wù)ni在不同節(jié)點(diǎn)執(zhí)行的平均完成時間，c(i，j)表示有依賴關(guān)系的任務(wù)ni和nj之間數(shù)據(jù)傳遞的平均時間。由于當(dāng)前任務(wù)的所有前驅(qū)任務(wù)的ru比當(dāng)前任務(wù)的ru大，將向上權(quán)值由大到小排序并依次執(zhí)行任務(wù)，可以保證有先后依賴關(guān)系的任務(wù)不因為依賴限制而產(chǎn)生等待，因此每個DAG中任務(wù)的初始優(yōu)先級可由ru來表示。通過如圖2所示的兩個工作流實(shí)例DAG-A和DAG-B調(diào)度來說明本文提出的L-Fairness算法流程。假設(shè)節(jié)點(diǎn)資源數(shù)為3，在兩個DAG中任務(wù)A（ii=1～10）和B（ii=1～5）在節(jié)點(diǎn)P（ii=1，2，3）上的執(zhí)行時間如表1所示，其中時間單位為1。由式（1）可計算并得到每個任務(wù)的向上權(quán)值排序并將其作為初始優(yōu)先級。

圖2 DAG工作流實(shí)例Fig.2 DAG workflows examples

表1 DAG-A 和DAG-B 工作流的執(zhí)行時間比較Table 1 Comparison of execution time of DAG-A and DAG-B workflows

2.2 公平調(diào)度子系統(tǒng)

L-Fairness算法的核心內(nèi)容為準(zhǔn)備隊列中任務(wù)的調(diào)度，準(zhǔn)備隊列中的任務(wù)來自于不同的DAG。經(jīng)典Fairness算法［12］依據(jù)滯后度來決定準(zhǔn)備隊列的任務(wù)優(yōu)先級，當(dāng)任務(wù)具有相同的滯后度時采用剩余完成時間決定優(yōu)先級，這樣會導(dǎo)致任務(wù)量小的DAG長時間處于等待狀態(tài)。本文在Fairness算法的基礎(chǔ)上提出L-Fairness算法，其主要改進(jìn)為使準(zhǔn)備隊列選擇滯后度小的任務(wù)調(diào)度，當(dāng)滯后度相同時選擇完成度小的任務(wù)調(diào)度，當(dāng)完成度相同時選擇剩余執(zhí)行時間長的任務(wù)調(diào)度。DAGk的滯后度定義為：

其中，nk表示DAGk的任務(wù)總數(shù)，當(dāng)滯后度相同時，完成度小的任務(wù)優(yōu)先執(zhí)行。DAGk的剩余完成時間定義為：

其中，D（k，own）表示DAGk單獨(dú)使用資源時執(zhí)行整個任務(wù)流所需的時間，當(dāng)滯后度和完成度相同時，剩余完成時間長的任務(wù)優(yōu)先執(zhí)行。

2.3 處理器分配子系統(tǒng)

由于每個EDA任務(wù)對license種類、數(shù)量及資源需求不同，因此需要將任務(wù)調(diào)度到合適的高性能集群節(jié)點(diǎn)上執(zhí)行［18-20］。EDA任務(wù)分為不需要license、需要浮動license以及需要固定license這3種類型。如果某些EDA工具的license綁定在固定集群節(jié)點(diǎn)上，則為固定license，當(dāng)EDA任務(wù)需要固定license時必須匹配到有相應(yīng)license的集群節(jié)點(diǎn)上以確保任務(wù)順利執(zhí)行。如果EDA工具的license與節(jié)點(diǎn)不進(jìn)行綁定，用戶只要獲得license授權(quán)就可在任意節(jié)點(diǎn)使用，則為浮動license。在保證license的前提下，任務(wù)根據(jù)最早完成時間選擇節(jié)點(diǎn)執(zhí)行。不同任務(wù)在處理器節(jié)點(diǎn)Pi上的license情況如表2所示。如果任務(wù)Ai或Bi在對應(yīng)處理器節(jié)點(diǎn)Pi上有相應(yīng)的license則值為1，否則為0。每個任務(wù)應(yīng)該至少有一個節(jié)點(diǎn)的license滿足要求。待執(zhí)行任務(wù)在選擇節(jié)點(diǎn)執(zhí)行時，首先排除license為0的節(jié)點(diǎn)，然后依次計算任務(wù)在對應(yīng)license為1時各個節(jié)點(diǎn)的最早完成時間，選擇最早完成時間最短的節(jié)點(diǎn)執(zhí)行任務(wù)。

表2 不同任務(wù)在各個節(jié)點(diǎn)上的license情況Table 2 Status of license for different tasks on each node

圖3（a）、圖3（b）表示使用HEFT［4］算法單獨(dú)調(diào)度DAG-A、DAG-B的調(diào)度結(jié)果。圖3（c）、圖3（d）表示DAG-A和DAG-B混合調(diào)度時使用Fairness算法和L-Fairness算法的調(diào)度結(jié)果?？梢钥闯?，當(dāng)使用Fairness算法調(diào)度時，由于A6執(zhí)行完之前DAG-A的剩余執(zhí)行時間比DAG-B長，因此DAG-B長時間處于等待狀態(tài)，從而造成不公平調(diào)度，而使用L-Fairness算法可縮短DAG-B任務(wù)的等待時間。

圖3 不同算法調(diào)度結(jié)果比較Fig.3 Comparison of scheduling results of different algorithms

3 不公平度指標(biāo)計算

不公平度是多DAG調(diào)度中衡量調(diào)度性能的重要指標(biāo)。如果不考慮公平性，則可能會使任務(wù)量小的DAG完成時間反而比任務(wù)量大的DAG長［12］。DAGk執(zhí)行完成后的滯后度定義為：

其中，D(k，multi)表示DAGk在混合調(diào)度時整個任務(wù)流執(zhí)行完成所需的時間?；旌险{(diào)度算法p的不公平度為：

其中，A表示所有DAG滯后度的平均值，E表示給定的多個DAG的集合，即：

可見，U越小，調(diào)度公平度越高。Fairness算法和L-Fairness算法的調(diào)度結(jié)果對比如表3所示?？梢钥闯觯琇-Fairness算法在不公平度、資源利用率與執(zhí)行時間上均比Fairness算法更具優(yōu)勢。

表3 Fairness算法和L-Fairness算法的調(diào)度結(jié)果比較Table 3 Comparison of scheduling results between Fairness algorithm and L-Fairness algorithm

算法L-Fairness算法

4 仿真結(jié)果與分析

本文從資源利用率、平均完成時間和不公平度3個方面對Fairness算法、L-Fairness算法以及FIFO進(jìn)行比較，其中FIFO表示多個DAG任務(wù)使用HEFT算法依次完成調(diào)度。由于Fairness算法及FIFO均未考慮license，因此需在選擇節(jié)點(diǎn)時添加license判斷。

圖4為2個隨機(jī)產(chǎn)生的DAG在2個～4個處理器上的調(diào)度結(jié)果。圖5為2個～4個隨機(jī)產(chǎn)生的DAG在3個處理器上的調(diào)度結(jié)果。DAG中任務(wù)層數(shù)、每一層任務(wù)數(shù)、不同層任務(wù)之間的通信時間以及每個任務(wù)在不同節(jié)點(diǎn)上的執(zhí)行時間均隨機(jī)產(chǎn)生。由此可知，改進(jìn)L-Fairness算法的資源利用率最高、平均完成時間最短且不公平度最小。與經(jīng)典Fairness算法相比，L-Fairness算法的平均資源利用率提高了6.7%，不公平度和平均完成時間分別降低了46.2%和14.9%。由于本文所使用的DAG結(jié)構(gòu)均為隨機(jī)生成，因此調(diào)度算法的比較結(jié)果更具普適性。

圖4 相同數(shù)量DAG在不同數(shù)量處理器上的調(diào)度結(jié)果Fig.4 Scheduling results of the same number of DAGs on different number of processors

圖5 不同數(shù)量DAG在相同數(shù)量處理器上的調(diào)度結(jié)果Fig.5 Scheduling results of different number of DAGs on the same number of processors

5 結(jié)束語

本文提出一種適用于多EDA任務(wù)流的L-Fairness算法?；诮?jīng)典Fairness算法進(jìn)行優(yōu)化，當(dāng)任務(wù)滯后度一致時，該算法將任務(wù)完成度作為DAG任務(wù)選擇的依據(jù)，避免任務(wù)數(shù)少的DAG任務(wù)長時間處于等待狀態(tài)，從而提升用戶服務(wù)質(zhì)量并保證調(diào)度公平性，同時使得EDA工具的license資源滿足EDA任務(wù)流調(diào)度需求。實(shí)驗結(jié)果表明，與Fairness算法及FIFO相比，改進(jìn)的L-Fairness算法的調(diào)度性能最優(yōu)。但EDA任務(wù)流中的子任務(wù)執(zhí)行順序?qū)⒏鶕?jù)L-Fairness算法確定，如果執(zhí)行過程中子任務(wù)出現(xiàn)異常，則整個任務(wù)流將重新執(zhí)行，并且L-Fairness算法未考慮任務(wù)調(diào)優(yōu)時需多次執(zhí)行子任務(wù)的情況，因此下一步將研究子任務(wù)迭代優(yōu)化的EDA任務(wù)流實(shí)時調(diào)度算法。