摘要
对3个典型的表调度算法:MCP算法,ETF算法和BDCP算法进行了分析,发现它们均不能确保任务最早调度。通过综合考虑IBN、CBN和OBN3类结点对调度结果的影响,提出了一个更加有效的基于关键路径的表调度算法,该算法能够确保关键路径结点具有最早启动时间,从而能有效缩短任务图的调度长度。分析和仿真结果表明,该调度算法不仅具有合理的算法复杂性,而且能有效地缩短相关任务图的调度长度,优于MCP、ETF、BDCP算法。
Three typical list scheduling algorithms: MCP algorithm, ETF algorithm and BDCP algorithm cannot guarantee the earliest scheduling for dynamic critical tasks. By integrated considering the influence of three kinds of task nodes, i.e. IBN, CBN and OBN, this paper proposes an improved list scheduling algorithm. The proposed algorithm can insure scheduling CPN as soon as it is ready, thus shortens the scheduling length of the task graph greatly. Simulation results are presented to valid the performance.
出处
《计算机工程》
EI
CAS
CSCD
北大核心
2005年第14期18-20,29,共4页
Computer Engineering
基金
国家自然科学基金资助项目(A0324638)
关键词
并行算法
表调度算法
DAG图
关键路径
多处理机系统
Parallel algorithm
List scheduling algorithm
DAG graph
Critical path
Multi-processor system
