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_k（k=1~n，n为DAG数量）中任务依赖关系确定优先级，将每个DAG_k优先级最高的任务放入准备队列；2）公平调度子系统负责将准备队列中不同DAG的任务根据公平性原则进行重新排序，选择优先级最高的任务准备调度；3）处理器分配子系统负责将待调度任务分配到最合适的处理器执行任务。

2 L-Fairness算法实现 2.1 初始优先级判别子系统

一个DAG工作流可以表示为G=（V，E，C），其中，V是任务节点集合，E是任务节点间有向边的集合，C是有向边的权值集合。有向边（i，j）表示任务节点n_i和n_j之间的先后执行关系，即n_i必须在n_j之前完成，有向边上的权值表示任务之间数据传递的平均时间。向上权值表示任务节点n_i到退出任务节点n_exit的最长路径长度，向上权值从退出任务节点开始，可被递归地定义为：

${r_u}\left( {{n_i}} \right) = {\bar w_i} + \mathop {{\rm{max}}}\limits_{{n_j} \in h\left( {{n_i}} \right)} \left( {{c_{\left( {i, j} \right)}} + {r_u}\left( {{n_j}} \right)} \right)$

(1)

${r_u}\left( {{n_{{\rm{exit}}}}} \right) = {{\bar w}_{{\rm{exit}}}}$

(2)

其中，h（n_i）表示任务n_i的直接后继节点集合，w_i表示任务n_i在不同节点执行的平均完成时间，c_(i,j)表示有依赖关系的任务n_i和n_j之间数据传递的平均时间。由于当前任务的所有前驱任务的r_u比当前任务的r_u大，将向上权值由大到小排序并依次执行任务，可以保证有先后依赖关系的任务不因为依赖限制而产生等待，因此每个DAG中任务的初始优先级可由r_u来表示。通过如图 2所示的两个工作流实例DAG-A和DAG-B调度来说明本文提出的L-Fairness算法流程。假设节点资源数为3，在两个DAG中任务A_i（i=1~10）和B_i（i=1~5）在节点P_i（i=1，2，3）上的执行时间如表 1所示，其中时间单位为1。由式（1）可计算并得到每个任务的向上权值排序并将其作为初始优先级。

2.2 公平调度子系统

L-Fairness算法的核心内容为准备队列中任务的调度，准备队列中的任务来自于不同的DAG。经典Fairness算法^[12]依据滞后度来决定准备队列的任务优先级，当任务具有相同的滞后度时采用剩余完成时间决定优先级，这样会导致任务量小的DAG长时间处于等待状态。本文在Fairness算法的基础上提出L-Fairness算法，其主要改进为使准备队列选择滞后度小的任务调度，当滞后度相同时选择完成度小的任务调度，当完成度相同时选择剩余执行时间长的任务调度。DAG_k的滞后度定义为：

$S\left( k \right) = \frac{{{M_{{\rm{own}}}}\left( {{k_{{t_i}}}} \right)}}{{{M_{{\rm{multi}}}}\left( {{k_{{t_i}}}} \right)}}$

(3)

其中，${M_{{\rm{own}}}}\left( {{k_{{t_i}}}} \right)$表示DAG_k在单独使用资源时调度第t_i个任务的完成时间，${M_{{\rm{multi}}}}\left( {{k_{{t_i}}}} \right)$表示DAG_k在混合调度时调度第t_i个任务的完成时间。DAG_k的完成度定义为：

$F\left( k \right) = \frac{{{t_i}}}{{{n_k}}}$

(4)

其中，n_k表示DAG_k的任务总数，当滞后度相同时，完成度小的任务优先执行。DAG_k的剩余完成时间定义为：

$T\left( k \right) = {D_{\left( {k, {\rm{own}}} \right)}} - {M_{{\rm{own}}}}\left( {{k_{{t_i}}}} \right)$

(5)

其中，D_{（k，own）}表示DAG_k单独使用资源时执行整个任务流所需的时间，当滞后度和完成度相同时，剩余完成时间长的任务优先执行。

2.3 处理器分配子系统

由于每个EDA任务对license种类、数量及资源需求不同，因此需要将任务调度到合适的高性能集群节点上执行^[18-20]。EDA任务分为不需要license、需要浮动license以及需要固定license这3种类型。如果某些EDA工具的license绑定在固定集群节点上，则为固定license，当EDA任务需要固定license时必须匹配到有相应license的集群节点上以确保任务顺利执行。如果EDA工具的license与节点不进行绑定，用户只要获得license授权就可在任意节点使用，则为浮动license。在保证license的前提下，任务根据最早完成时间选择节点执行。不同任务在处理器节点P_i上的license情况如表 2所示。如果任务A_i或B_i在对应处理器节点P_i上有相应的license则值为1，否则为0。每个任务应该至少有一个节点的license满足要求。待执行任务在选择节点执行时，首先排除license为0的节点，然后依次计算任务在对应license为1时各个节点的最早完成时间，选择最早完成时间最短的节点执行任务。

图 3（a）、图 3（b）表示使用HEFT^[4]算法单独调度DAG-A、DAG-B的调度结果。图 3（c）、图 3（d）表示DAG-A和DAG-B混合调度时使用Fairness算法和L-Fairness算法的调度结果。可以看出，当使用Fairness算法调度时，由于A₆执行完之前DAG-A的剩余执行时间比DAG-B长，因此DAG-B长时间处于等待状态，从而造成不公平调度，而使用L-Fairness算法可缩短DAG-B任务的等待时间。

3 不公平度指标计算

不公平度是多DAG调度中衡量调度性能的重要指标。如果不考虑公平性，则可能会使任务量小的DAG完成时间反而比任务量大的DAG长^[12]。DAG_k执行完成后的滞后度定义为：

$S\left( k \right) = \frac{{{D_{\left( {k, {\rm{own}}} \right)}}}}{{{D_{\left( {k, {\rm{multi}}} \right)}}}}$

(6)

其中，${D_{\left( {k, {\rm{multi}}} \right)}}$表示DAG_k在混合调度时整个任务流执行完成所需的时间。混合调度算法p的不公平度为：

$U\left( p \right) = \mathop \sum \limits_{\forall k \in E} \left| {S\left( k \right) - A} \right|$

(7)

其中，A表示所有DAG滞后度的平均值，E表示给定的多个DAG的集合，即：

$A = \frac{{\sum\limits_{\forall k \in E} {S\left( k \right)} }}{{\left| n \right|}}$

(8)

可见，U越小，调度公平度越高。Fairness算法和L-Fairness算法的调度结果对比如表 3所示。可以看出，L-Fairness算法在不公平度、资源利用率与执行时间上均比Fairness算法更具优势。

算法  L-Fairness算法

输入  待调度的DAG集合A，可用资源集合R

输出  集合A中DAG的公平混合调度方案（存储在S_multi中）

1.Procedure L-Fairness（A，R）

2.在R资源上使用HEFT算法单独调度运行A中每个待调度的DAG；

3.将这些调度结果存储在S_own中；

4.将每个DAG标记为未调度并放入集合U中；

5.S_multi← Ø/*多个DAG混合调度结果初始为空*/

6.依次将U中每个DAG_k的r_u最高的任务t_i放入准备队列P，并将t_i从DAG_k中删除；

7.while P≠ Ø do

8.根据式（3）~式（5）依次计算P中每个任务的滞后度、完成度和剩余完成时间；

9.执行滞后度最小的任务m，当有多个滞后度最小的任务时，从滞后度最小的多个任务中选择完成度最小的一个任务，否则从滞后度和完成度均最小的任务中选择剩余完成时间最长的任务执行；

10.由表 1和表 2依次计算任务m在具有license的计算节点上的最早完成时间，选择最早完成时间最短的节点执行并存储在S_multi中；

11.将已执行任务从P中删除并将对应DAG_k中r_u最高的任务t_i添加到P中；

12.if（t_i是DAG_k中最后一个任务）then

13.从U中删除DAG_k；

14.end if

15.end while

16.return S_multi

17.end Procedure

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结构均为随机生成，因此调度算法的比较结果更具普适性。

5 结束语

本文提出一种适用于多EDA任务流的L-Fairness算法。基于经典Fairness算法进行优化，当任务滞后度一致时，该算法将任务完成度作为DAG任务选择的依据，避免任务数少的DAG任务长时间处于等待状态，从而提升用户服务质量并保证调度公平性，同时使得EDA工具的license资源满足EDA任务流调度需求。实验结果表明，与Fairness算法及FIFO相比，改进的L-Fairness算法的调度性能最优。但EDA任务流中的子任务执行顺序将根据L-Fairness算法确定，如果执行过程中子任务出现异常，则整个任务流将重新执行，并且L-Fairness算法未考虑任务调优时需多次执行子任务的情况，因此下一步将研究子任务迭代优化的EDA任务流实时调度算法。