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.