表调度算法的并行化研究

摘要：

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

关键词：表调度、并行算法、任务调度

所属期刊栏目：31

分类号：TP3;TN4

资助基金：国家自然科学基金60273075

在线出版日期：2005-01-04（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：166-168,175