| Electrical & Electronic Engineering |
|
|
|
|
| A new heuristic for task scheduling in heterogeneous computing environment |
| Ehsan Ullah MUNIR, Jian-zhong LI, Sheng-fei SHI, Zhao-nian ZOU, Qaisar RASOOL |
| School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China; Department of Computer Science, COMSATS Institute of Information 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 expected 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.
|
|
Received: 02 January 2008
|
|
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
