表调度算法的并行化研究

当目标处理器个数大于2时，调度任意结构并行任务图并获取最优解的问题是np完全难题。表调度算法作为一类代表性的启发式任务调度算法具有调度性能较好而时间复杂度较低的优点。但当任务图的规模较大时表调度算法的耗时也很可观，无疑并行表调度算法是一种好的解决方法。本文在串行算法lbp的基础上提出了一个新的表调度并行算法plbp，该算法在保证与串行算法同样调度性能的前提下，时间复杂度有较大的改善。同时，与已有的表调度并行算法相比较，plbp算法有更小的时间复杂度。