基于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任务流实时调度算法。