| 相关任务图的一种有效并行调度算法 |
| |
| 引用本文： | 尚明生.相关任务图的一种有效并行调度算法[J].计算机工程,2005,31(14):18-20,29. |
| |
| 作者姓名： | 尚明生 |
| |
| 作者单位： | 电子科技大学计算机科学与工程学院,成都,610054 |
| |
| 基金项目： | 国家自然科学基金资助项目(A0324638) |
| |
| 摘 要： | 对3个典型的表调度算法：MCP算法，ETF算法和BDCP算法进行了分析，发现它们均不能确保任务最早调度。通过综合考虑IBN、CBN和OBN3类结点对调度结果的影响，提出了一个更加有效的基于关键路径的表调度算法，该算法能够确保关键路径结点具有最早启动时间，从而能有效缩短任务图的调度长度。分析和仿真结果表明，该调度算法不仪具有合理的算法复杂性，而且能有效地缩短相关任务图的调度长度，优于MCP、ETF、BDCP算法。
|
| 关 键 词： | 并行算法 表调度算法 DAG图 关键路径 多处理机系统 |
| 文章编号： | 1000-3428(2005)14-0018-03 |
Efficient Algorithm for Scheduling Dependent Task Graphs on Multi-processor System |
| |
| SHANG Mingsheng.Efficient Algorithm for Scheduling Dependent Task Graphs on Multi-processor System[J].Computer Engineering,2005,31(14):18-20,29. |
| |
| Authors: | SHANG Mingsheng |
| |
| 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. |
| |
| Keywords: | Parallel algorithm List scheduling algorithm DAG graph Critical path Multi-processor system |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
