A new heuristic for task scheduling in heterogeneous computing environment |
| |
Authors: | Ehsan Ullah Munir Jian-zhong Li Sheng-fei Shi Zhao-nian Zou and Qaisar Rasool |
| |
Institution: | [1]School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China [2]Department of Computer Science, COMSATS Institute of lnformation Technology, Wah Cantt 47040, Pakistan |
| |
Abstract: | Heterogeneous computing (HC) environment utilizes diverse resources with different computational capabilities to solve computing-intensive applications having diverse computational requirements and constraints. The task assignment problem in HC environment can be formally defined as for a given set of tasks and machines,assigning tasks to machines to achieve the minimum makespan. In this paper we propose a new task scheduling heuristic,high standard deviation first (HSTDF),which considers the standard deviation of the expected execution time of a task as a selection criterion. Standard deviation of the ex-pected execution time of a task represents the amount of variation in task execution time on different machines. Our conclusion is that tasks having high standard deviation must be assigned first for scheduling. A large number of experiments were carried out to check the effectiveness of the proposed heuristic in different scenarios,and the comparison with the existing heuristics (Max-min,Sufferage,Segmented Min-average,Segmented Min-min,and Segmented Max-min) clearly reveals that the proposed heuristic outperforms all existing heuristics in terms of average makespan. |
| |
Keywords: | Heterogeneous computing Task scheduling Greedy heuristics High standard deviation first (HSTDF) heuristic |
本文献已被 维普 万方数据 SpringerLink 等数据库收录! |
|