A Scheduling Algorithm for Fork-Join DAG in Bus-based and Heterogeneous Environment
The Fork-Join task graph is one of the basic modeling structures for parallel processing.However,many previous scheduling algorithms ignore to economize processors and minimize the total completion time.Whats more,many algorithms dont consider the competition caused by bus-based clusters and the heterogeneous of processors in real applications.This paper presents a new algorithm for Fork-Join task graph,considering economy of processors and minimization of the total completion time,the non-parallel communication,and heterogeneous environment as well.We propose a task scheduling algorithm based on task duplication which randomly generated a number of Fork-Join task graphs by producing the task execution time and communication time.Simulation results show that the proposed algorithm has less total completion time and less number of processors than other compared algorithms for more practical applications.
Task scheduling Task duplication Heterogeneous Bus-based Fork-join task graph
Lisheng Wang Liguo Chen Kete Wang
Department of Computer Science College of Electronic and Information Engineering Tongji University Shanghai, China
国际会议
沈阳
英文
702-705
2012-07-27（万方平台首次上网日期，不代表论文的发表时间）