表调度算法的并行化研究

On Parailelizing the List Scheduling Algorithm

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

When the number of processing units is more than 2,scheduling arbitrary task graph in order to obtain an optimizing solution is a NP-complete problem. As a heuristic scheduling algorithm,list scheduling algorithm has bet-ter performance and lower time complexity. But the run time of list scheduling algorithm becomes too long when the size of task graph become huge. Undoubtedly,parallelizing the list scheduling algorithm may reduce the time com-plexity. Based on serial list scheduling algorithm LBP, this paper presents a new parallel list scheduling algorithm PLBP. It can obtain the same performance as LBP and effectively improve the time complexity of LBP. At the same time,PLBP has lower time complexity comparing to the other parallel list scheduling algorithm in the literature.