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

• 作者: 乔伟光 曾国荪
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 机群计算 任务图 任务调度 分簇复制
• 年，卷（期）: 2006,（17）
• 所属期刊栏目: 软件技术与数据库
• 页码范围: 126-128,134
• 页数: 4页
• 分类号: TP338
• 字数: 2578字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2006.17.044

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	乔伟光	同济大学计算机科学及技术系	2	14	2.0	2.0
2	曾国荪	国家高性能计算机工程技术中心同济分中心	65	677	15.0	23.0