相关任务图的一种有效并行调度算法

摘要：

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

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

所属期刊栏目：31

分类号：TP314(计算技术、计算机技术)

资助基金：国家自然科学基金A0324638

在线出版日期：2005-08-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：18-20,29