同构计算环境中一种快速有效的静态任务调度算法

摘要：

快速有效的调度任务是多处理器计算环境中的一个关键问题.目前任务调度算法中刻画任务依赖关系最流行的模型是DAG.在以前的文献中,提出了一种新的更实际、更普遍的TTIG模型及其相应的MATE算法(基于同构计算环境).延伸了TTIG模型,并提出基于同构系统的新的算法及两种启发式方法(GBHA1和GBHA2).GBHA以组的形式尽量消除图中回路,因而能获得任务图的全局信息,具有更好的调度性能.在模拟实验中,将此算法与MATE和其他同构环境中基于DAG的有效调度算法,在不同测试条件下进行了比较,结果显示GBHA在性能上明显优于MATE,与基于DAG模型的调度算法比较而言,在性能方面各有千秋,但在算法时间复杂度方面具有显著的优势.

关键词：任务调度、表调度、启发式方法

所属期刊栏目：42

分类号：TP301(计算技术、计算机技术)

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

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

页数：共8页

页码：118-125