A Scheduling Algorithm for Fork-Join DAG in Bus-based and Heterogeneous Environment
作者单位：Department of Computer Science College of Electronic and Information Engineering Tongji University
会议名称：《2012年计算机应用与系统建模国际会议》
会议日期：2012年
学科分类：08[工学] 081201[工学-计算机系统结构] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）]
关 键 词：Task scheduling Task duplication Heterogeneous Bus-based Fork-join task graph
摘 要：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. What’s more, many algorithms don’t consider the competition caused by bus-based clusters and the heterogeneous of processors in real applications. This paper presents a new algorithm for ForkJoin 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.