高级检索
孟宪福, 刘伟伟. 基于选择性复制前驱任务的DAG调度算法[J]. 计算机辅助设计与图形学学报, 2010, 22(6): 1056-1062.
引用本文: 孟宪福, 刘伟伟. 基于选择性复制前驱任务的DAG调度算法[J]. 计算机辅助设计与图形学学报, 2010, 22(6): 1056-1062.
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): 1056-1062.
Citation: 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): 1056-1062.

基于选择性复制前驱任务的DAG调度算法

A DAG Scheduling Algorithm Based on Selected Duplication of Precedent Tasks

  • 摘要: 针对异构环境下相关任务的静态调度问题,以最小化调度长度为主要目标,结合表调度与基于复制的调度思想提出了选择性任务复制调度算法.在任务调度过程中,利用处理器的空闲时间,通过有选择地复制能提前当前任务开始执行时间的父任务来减少任务之间信息传递的通信延迟,有利于后续任务的及时调度,从而缩短整个任务图的并行完成时间.实验结果表明,文中算法在通信量比较大的情况下在时间上优于复杂度相同的HEFT,HNDP及DDS算法,且随着任务图中通信时间/计算时间比值的增加,其优越性也越来越明显.

     

    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 earliest starting time of the current candidate task to reduce the inter-processor communication cost and its waiting time of the processor.By this way,the overall run-time of application is shortened.The experimental results show that STDH outperforms HEFT,HNDP and DDS in terms of finish time.Besides,while the ratio of total communication cost and total computation cost of the task graph becomes larger,STDH's advantage is more distinct.

     

/

返回文章
返回