CLC number: TP3
On-line Access:
Received: 2008-01-02
Revision Accepted: 2008-06-19
Crosschecked: 2008-11-10
Cited: 8
Clicked: 6364
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.
[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>