基于EDA多任務流的調度算法研究

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

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

0 概述

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

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

1 多DAG調度系統

動態多DAG任務調度系統模型如圖1所示。該系統由初始優先級判別子系統、公平調度子系統和處理器分配子系統3個部分組成：1）初始優先級判別子系統針對每個DAG（kk=1～n，n為DAG數量）中任務依賴關系確定優先級，將每個DAGk優先級最高的任務放入準備隊列；2）公平調度子系統負責將準備隊列中不同DAG的任務根據公平性原則進行重新排序，選擇優先級最高的任務準備調度；3）處理器分配子系統負責將待調度任務分配到最合適的處理器執行任務。

圖1 多DAG調度系統模型Fig.1 Model of multi-DAG scheduling system

2 L-Fairness算法實現

2.1 初始優先級判別子系統

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

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

圖2 DAG工作流實例Fig.2 DAG workflows examples

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

2.2 公平調度子系統

L-Fairness算法的核心內容為準備隊列中任務的調度，準備隊列中的任務來自于不同的DAG。經典Fairness算法［12］依據滯后度來決定準備隊列的任務優先級，當任務具有相同的滯后度時采用剩余完成時間決定優先級，這樣會導致任務量小的DAG長時間處于等待狀態。本文在Fairness算法的基礎上提出L-Fairness算法，其主要改進為使準備隊列選擇滯后度小的任務調度，當滯后度相同時選擇完成度小的任務調度，當完成度相同時選擇剩余執行時間長的任務調度。DAGk的滯后度定義為：

其中，nk表示DAGk的任務總數，當滯后度相同時，完成度小的任務優先執行。DAGk的剩余完成時間定義為：

其中，D（k，own）表示DAGk單獨使用資源時執行整個任務流所需的時間，當滯后度和完成度相同時，剩余完成時間長的任務優先執行。

2.3 處理器分配子系統

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

表2 不同任務在各個節點上的license情況Table 2 Status of license for different tasks on each node

圖3（a）、圖3（b）表示使用HEFT［4］算法單獨調度DAG-A、DAG-B的調度結果。圖3（c）、圖3（d）表示DAG-A和DAG-B混合調度時使用Fairness算法和L-Fairness算法的調度結果。可以看出，當使用Fairness算法調度時，由于A6執行完之前DAG-A的剩余執行時間比DAG-B長，因此DAG-B長時間處于等待狀態，從而造成不公平調度，而使用L-Fairness算法可縮短DAG-B任務的等待時間。

圖3 不同算法調度結果比較Fig.3 Comparison of scheduling results of different algorithms

3 不公平度指標計算

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

其中，D(k，multi)表示DAGk在混合調度時整個任務流執行完成所需的時間。混合調度算法p的不公平度為：

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

可見，U越小，調度公平度越高。Fairness算法和L-Fairness算法的調度結果對比如表3所示。可以看出，L-Fairness算法在不公平度、資源利用率與執行時間上均比Fairness算法更具優勢。

表3 Fairness算法和L-Fairness算法的調度結果比較Table 3 Comparison of scheduling results between Fairness algorithm and L-Fairness algorithm

算法L-Fairness算法

4 仿真結果與分析

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

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

圖4 相同數量DAG在不同數量處理器上的調度結果Fig.4 Scheduling results of the same number of DAGs on different number of processors

圖5 不同數量DAG在相同數量處理器上的調度結果Fig.5 Scheduling results of different number of DAGs on the same number of processors

5 結束語

本文提出一種適用于多EDA任務流的L-Fairness算法。基于經典Fairness算法進行優化，當任務滯后度一致時，該算法將任務完成度作為DAG任務選擇的依據，避免任務數少的DAG任務長時間處于等待狀態，從而提升用戶服務質量并保證調度公平性，同時使得EDA工具的license資源滿足EDA任務流調度需求。實驗結果表明，與Fairness算法及FIFO相比，改進的L-Fairness算法的調度性能最優。但EDA任務流中的子任務執行順序將根據L-Fairness算法確定，如果執行過程中子任務出現異常，則整個任務流將重新執行，并且L-Fairness算法未考慮任務調優時需多次執行子任務的情況，因此下一步將研究子任務迭代優化的EDA任務流實時調度算法。