中文摘要：

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

英文摘要：

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.