王 静，陈 岚，张 贺，王海永

（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之间的调度问题。……