有向图并行计算中一种新的结点调度算法

摘要

在有向图并行计算中,给定图剖分后,如何设计结点调度方案使并行执行时间最短,是典型的NP完全问题.针对此问题,本文提出一种新的基于顺逆交替迭代技术的启示性调度算法,并给出该算法的并行实现.严格的理论分析证明,新算法在结点等权重的假设下,从任何初始调度方案出发,均可以收敛到局部最优解.使用500个处理器的模型测试和使用128个处理器的粒子输运实际应用测试表明,比较于当前有向图并行计算研究中广泛采用的多种调度算法,新算法调度效果改进显著.