JZUS - Journal of Zhejiang University SCIENCE

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

Share this article to： More <<< Previous Article \|Next Article >>>

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.

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>

Similar articles

- Go to

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

Reference