摘要： 对3个典型的表调度算法:MCP算法,ETF算法和BDCP算法进行了分析,发现它们均不能确保任务最早调度。通过综合考虑IBN、CBN和OBN3类结点对调度结果的影响,提出了一个更加有效的基于关键路径的表调度算法,该算法能够确保关键路径结点具有最早启动时间,从而能有效缩短任务图的调度长度。分析和仿真结果表明,该调度算法不仅具有合理的算法复杂性,而且能有效地缩短相关任务图的调度长度,优于MCP、ETF、BDCP算法。

关键词: 并行算法, 表调度算法, DAG图, 关键路径, 多处理机系统

Abstract: Three typical list scheduling algorithms: MCP algorithm, ETF algorithm and BDCP algorithm cannot guarantee the earliest schedulingfor dynamic critical tasks. By integrated considering the influence of three kinds of task nodes, i.e. IBN, CBN and OBN, this paper proposes animproved list scheduling algorithm. The proposed algorithm can insure scheduling CPN as soon as it is ready, thus shortens the scheduling length ofthe task graph greatly. Simulation results are presented to valid the performance.

中图分类号: 

• TP301.6