论文部分内容阅读
在基于有向图的并行计算中，给定图剖分后，如何设计结点调度方案使得并行执行时间最短，是典型的NP完全问题．针对此问题，文中提出一种新的基于顺逆交替迭代技术的启发式调度算法，并给出该算法的并行实现．严格的理论推导证明，新算法在一定的假设条件下，从任何初始调度方案出发，均可以单调收敛．在数百个处理器上的并行数值实验表明，与常用的调度算法相比，新算法可在付出很少的开销代价下显著提高整体并行效率．