A Recursive Algorithm for Scheduling of Tasks in a Heterogeneous Distributed Environment
Optimal scheduling of parallel tasks with some precedence is critical for achieving high performance in heterogeneous computing system. The application scheduling is known to be NP-complete in general cases. The complexity of the problem increase when task scheduling is to be done in a heterogeneous environment This paper presents a recursive task scheduling algorithm for a bounded number of heterogeneous processors run on the network of Heterogeneous systems. It is three-phase task scheduling algorithm. The task-prioritizing phase is to is to compute the upward rank of each task and assign the priority to all tasks. The processor selection phase is to schedule the tasks onto the processors that give the latest start time for the task. The moving phase is to move all the possible tasks until the starting time of the entry task is zero. The performance of the algorithm is illustrated by comparing the scheduling length ratio, frequency of best results with the existing effectively scheduling algorithms, Heterogeneous Earliest Finish Time and Iterative List Scheduling algorithm.
scheduling algorithm heterogeneous recursive distributed system
Yan Kang Ying Lin
Department of Software Engineering School of Software, Yunnan University Kunming, Yunnan, China Department of Information Security School of Software, Yunnan University Kunming, Yunnan, China
国际会议
上海
英文
2112-2116
2011-10-15（万方平台首次上网日期，不代表论文的发表时间）