| 《计算机学报》文章摘要 全文下载 | |
| 文章题目 | 有向图并行计算中一种新的结点调度算法 |
| 作者 | 张爱清 莫则尧 |
| 作者单位 | (北京应用物理与计算数学研究所高性能计算中心 北京 100094) |
| 发表年份 | 2009 |
| 发表月份 | 11期(2178—2186) |
| 文章摘要 | 摘要 在基于有向图的并行计算中，给定图剖分后，如何设计结点调度方案使得并行执行时间最短，是典型的NP完全问题.针对此问题，文中提出一种新的基于顺逆交替迭代技术的启发式调度算法，并给出该算法的并行实现.严格的理论推导证明，新算法在一定的假设条件下，从任何初始调度方案出发，均可以单调收敛.在数百个处理器上的并行数值实验表明，与常用的调度算法相比，新算法可在付出很少的开销代价下显著提高整体并行效率. 关键词 有向图；并行计算；结点调度算法；顺逆交替迭代技术 中图法分类号 TP301 DOI号: 10.3724/SP.J.1016.2009.02178 |