Full Text:   <2609>

CLC number: TP3

On-line Access: 

Received: 2008-01-02

Revision Accepted: 2008-06-19

Crosschecked: 2008-11-10

Cited: 8

Clicked: 5290

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
Open peer comments

Journal of Zhejiang University SCIENCE A 2008 Vol.9 No.12 P.1715-1723

http://doi.org/10.1631/jzus.A0820007


A new heuristic for task scheduling in heterogeneous computing environment


Author(s):  Ehsan Ullah MUNIR, Jian-zhong LI, Sheng-fei SHI, Zhao-nian ZOU, Qaisar RASOOL

Affiliation(s):  School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China; more

Corresponding email(s):   ehsanmunnir@gmail.com

Key Words:  Heterogeneous computing, Task scheduling, Greedy heuristics, High standard deviation first (HSTDF) heuristic


Ehsan Ullah MUNIR, Jian-zhong LI, Sheng-fei SHI, Zhao-nian ZOU, Qaisar RASOOL. A new heuristic for task scheduling in heterogeneous computing environment[J]. Journal of Zhejiang University Science A, 2008, 9(12): 1715-1723.

@article{title="A new heuristic for task scheduling in heterogeneous computing environment",
author="Ehsan Ullah MUNIR, Jian-zhong LI, Sheng-fei SHI, Zhao-nian ZOU, Qaisar RASOOL",
journal="Journal of Zhejiang University Science A",
volume="9",
number="12",
pages="1715-1723",
year="2008",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.A0820007"
}

%0 Journal Article
%T A new heuristic for task scheduling in heterogeneous computing environment
%A Ehsan Ullah MUNIR
%A Jian-zhong LI
%A Sheng-fei SHI
%A Zhao-nian ZOU
%A Qaisar RASOOL
%J Journal of Zhejiang University SCIENCE A
%V 9
%N 12
%P 1715-1723
%@ 1673-565X
%D 2008
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.A0820007

TY - JOUR
T1 - A new heuristic for task scheduling in heterogeneous computing environment
A1 - Ehsan Ullah MUNIR
A1 - Jian-zhong LI
A1 - Sheng-fei SHI
A1 - Zhao-nian ZOU
A1 - Qaisar RASOOL
J0 - Journal of Zhejiang University Science A
VL - 9
IS - 12
SP - 1715
EP - 1723
%@ 1673-565X
Y1 - 2008
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.A0820007


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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1] Ali, S., Siegel, H.J., Maheswaran, M., Ali, S., Hensgen, D., 2000. Task Execution Time Modeling for Heterogeneous Computing Systems. Proc. 9th Heterogeneous Computing Workshop, p.185-200.

[2] Braun, T.D., Siegel, H.J., Beck, N., Bölöni, L.L., Maheswaran, M., Reuther, A.I., Robertson, J.P., Theys, M.D., Yao, B., Hensgen, D., et al., 2001. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. J. Parall. Distrib. Comput., 61(6):810-837.

[3] Briceno, L.D., Oltikar, M., Siegel, H.J., Maciejewski, A.A., 2007. Study of an Iterative Technique to Minimize Completion Times of Non-makespan Machines. Proc. 17th Heterogeneous Computing Workshop, p.1-14.

[4] Cormen, T.H., Leirson, C.E., Rivest, R.L., 2001. Introduction to Algorithms. MIT Press, Cambridge, MA.

[5] Fernandez-Baca, D., 1989. Allocating modules to processors in a distributed system. IEEE Trans. on Software Eng., 15(11):1427-1436.

[6] Foster, I., Kesselman, C., 1998. The Grid: Blueprint for a New Computing Infrastructure. Morgan Kaufman Publishers, San Francisco, CA, USA.

[7] Freund, R.F., Gherrity, M., Ambrosius, S., Campbell, M., Halderman, M., Hensgen, D., Keith, E., Kidd, T., Kussow, M., Lima, J.D., et al., 1998. Scheduling Resources in Multi-user, Heterogeneous, Computing Environments with Smartnet. Proc. 7th Heterogeneous Computing Workshop, p.184-199.

[8] Ibarra, O.H., Kim, C.E., 1977. Heuristic algorithms for scheduling independent tasks on non-identical processors. J. ACM, 24(2):280-289.

[9] Kim, J.K., Shivle, S., Siegel, H.J., Maciejewski, A.A., Braun, T.D., Schneider, M., Tideman S., Chitta, R., Dilmaghani, R.B., Joshi, R., et al., 2007. Dynamically mapping tasks with priorities and multiple deadlines in a heterogeneous environment. J. Parall. Distrib. Comput., 67(2):154-169.

[10] Kwok, Y.K., Ahmad, I., 1999a. Benchmarking and comparison of the task graph scheduling algorithms. J. Parall. Distrib. Comput., 59(3):381-422.

[11] Kwok, Y.K., Ahmad, I., 1999b. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput. Surv., 31(4):406-471.

[12] Luan, C.J., Song, G.H., Zheng, Y., 2006. Application-adaptive resource scheduling in a computational grid. J. Zhejiang Univ. Sci. A, 7(10):1634-1641.

[13] Luo, P., Lu, K., Shi, Z.Z., 2007. A revisit of fast greedy heuristics for mapping a class of independent tasks onto heterogeneous computing systems. J. Parall. Distrib. Comput., 67(6):695-714.

[14] Maheswaran, M., Ali, S., Siegel, H.J., Hensgen, D., Freund, R.F., 1999. Dynamic mapping of a class of independent tasks onto heterogeneous computing system. J. Parall. Distrib. Comput., 59(2):107-131.

[15] Ritchie, G., Levine, J., 2004. A Hybrid Ant Algorithm for Scheduling Independent Jobs in Heterogeneous Computing Environments. Proc. 23rd Workshop of the UK Planning and Scheduling Special Interest Group, p.1-7.

[16] Sakellariou, R., Zhao, H., 2004. A Hybrid Heuristic for DAG Scheduling on Heterogeneous Systems. Proc. 18th Parallel and Distributed Processing Symp., p.111-123.

[17] Shivle, S., Sugavanam, P., Siegel, H.J., Maciejewski, A.A., Banka, T., Chindam, K., Dussinger, S., Kutruff, A., Penumarthy, P., Pichumani, P., et al., 2005. Mapping subtasks with multiple versions on an ad hoc grid. Parall. Comput., Special Issue Heterog. Comput., 31(7):671-690.

[18] Vazirani, V.V., 2002. Approximation Algorithms. Springer, Berlin, Germany.

[19] Wang, L., Siegel, H.J., Roychowdhury, V.P., Maciejewski, A.A., 1997. Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach. J. Parall. Distrib. Comput., 47(1):8-22.

[20] Wu, M.Y., Shu, W., Zhang, H., 2000. Segmented Min-min: A Static Mapping Algorithm for Meta-tasks on Heterogeneous Computing Systems. Proc. 9th Heterogeneous Computing Workshop, p.375-385.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE