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

Efficient Algorithm for Scheduling Dependent Task Graphs on Multi-processor System

作　　者：尚明生[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,成都610054

出　　处：《计算机工程》2005年第14期18-20,29,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(A0324638)

摘　　要：对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.

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

分 类 号：TP314[自动化与计算机技术—计算机软件与理论]