一种基于分簇复制的DAG任务图调度算法

摘要：

并行任务调度是影响机群计算效率的关键因素之一,机群环境DAG(Directed Acyclic Graph)任务图调度是一个NP完全问题,只能寻求启发式算法.已有的研究中,图解重构算法在允许任务复制的条件下,通过对DAG图递归分解与子图重构,初步实现了一个可行的调度方案.该文在此基础上,提出了以调度长度增量为依据的任务复制策略,利用该策略调整受制约节点的同簇前驱,解决了任务簇间的时间制约问题,缩短了调度长度;通过合理地选择任务簇进行合并,增大任务簇的粒度,提高了处理器的利用率.提出的以任务簇扩展-合并为特征、以分簇复制为手段的DAG图调度算法,改进和拓展了图解重构方法.实例分析表明本算法复杂度与TDS (Task Duplication Scheduling)相同,但性能更优.

关键词：机群计算、任务图、任务调度、分簇复制

所属期刊栏目：32

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

资助基金：国家自然科学基金60173026;教育部科学技术研究重点项目105071;海高校网格技术E-研究院资助项目200301-1

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

页数：共4页

页码：126-128,134