| 基于选择性复制前驱任务的DAG调度算法 |
| |
| 引用本文： | 孟宪福,刘伟伟.基于选择性复制前驱任务的DAG调度算法[J].计算机辅助设计与图形学学报,2010,22(6). |
| |
| 作者姓名： | 孟宪福 刘伟伟 |
| |
| 作者单位： | 大连理工大学计算机科学与工程系,大连,116024 |
| |
| 基金项目： | 国家自然科学基金(60973014) |
| |
| 摘 要： | 针对异构环境下相关任务的静态调度问题,以最小化调度长度为主要目标,结合表调度与基于复制的调度思想提出了选择性任务复制调度算法.在任务调度过程中,利用处理器的空闲时间,通过有选择地复制能提前当前任务开始执行时间的父任务来减少任务之间信息传递的通信延迟,有利于后续任务的及时调度,从而缩短整个任务图的并行完成时间.实验结果表明,文中算法在通信量比较大的情况下在时间上优于复杂度相同的HEFT,HNDP及DDS算法,且随着任务图中通信时间/计算时间比值的增加,其优越性也越来越明显.
|
| 关 键 词： | 异构计算环境 任务调度 任务复制 完成时间 有向无环图 |
A DAG Scheduling Algorithm Based on Selected Duplication of Precedent Tasks |
| |
| Meng Xianfu,Liu Weiwei.A DAG Scheduling Algorithm Based on Selected Duplication of Precedent Tasks[J].Journal of Computer-Aided Design & Computer Graphics,2010,22(6). |
| |
| Authors: | Meng Xianfu Liu Weiwei |
| |
| Affiliation: | Department of Computer Science and Engineering/a>;Dalian University of Technology/a>;Dalian 116024 |
| |
| Abstract: | This paper addresses static scheduling of a directed acyclic graph(DAG)on a heterogeneous,bounded set of distributed processors to minimize the overall run-time of application.By combining list-based scheduling and task duplication,a new static scheduling algorithm,named as selected task-duplication for heterogeneous system(STDH),is proposed,which improves the performance of list-based algorithm with the duplication.By utilizing idle time of the processors,STDH duplicates the parent tasks for advancing the ... |
| |
| Keywords: | heterogeneous computing environment task scheduling task duplication finish time directed acyclic graph |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
