IEICE Transactions on Information and Systems

IEICE Transactions on Information and Systems 2007 E90-D(4):736-744; doi:10.1093/ietisy/e90-d.4.736

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by SUN, W. Articles by INOGUCHI, Y. Search for Related Content Social Bookmarking          What's this?

Copyright © 2007 The Institute of Electronics, Information and Communication Engineers

Regular Section -- Papers -- Computer Systems

Dynamic Task Flow Scheduling for Heterogeneous Distributed Computing: Algorithm and Strategy^*

Wei SUN¹, Yuanyuan ZHANG² and Yasushi INOGUCHI³

¹ The author is with the School of Information Science, JAIST, Nomi-shi, 923–1292 Japan. E-mail: sun-wei{at}jaist.ac.jp, ² The author is with the Peta-Scale Computing Research Center, Fujitsu Laboratories Ltd., Kawasaki-shi, 211–8588 Japan., ³ The author is with the Center of Information Science, JAIST, Nomi-shi, 923–1292 Japan.

Heterogeneous distributed computing environments are well suited to meet the fast increasing computational demands. Task scheduling is very important for a heterogeneous distributed system to satisfy the large computational demands of applications. The performance of a scheduler in a heterogeneous distributed system normally has something to do with the dynamic task flow, that is, the scheduler always suffers from the heterogeneity of task sizes and the variety of task arrivals. From the long-term viewpoint it is necessary and possible to improve the performance of the scheduler serving the dynamic task flow. In this paper we propose a task scheduling method including a scheduling strategy which adapts to the dynamic task flow and a genetic algorithm which can achieve the short completion time of a batch of tasks. The strategy and the genetic algorithm work with each other to enhance the scheduler's efficiency and performance. We simulated a task flow with enough tasks, the scheduler with our strategy and algorithm, and the schedulers with other strategies and algorithms. We also simulated a complex scenario including the variant arrival rate of tasks and the heterogeneous computational nodes. The simulation results show that our scheduler achieves much better scheduling results than the others, in terms of the average waiting time, the average response time, and the finish time of all tasks.

Key Words: heterogeneous distributed computing, task scheduling, task flow, genetic algorithm, scheduling strategy

---

Manuscript received June 28, 2006. Manuscript revised November 20, 2006.

^* This research is conducted as a program for the "21st Century COE Program" by Ministry of Education, Culture, Sports, Science and Technology, Japan.

References

[1] R.F. Freund and H.J. Siegel, "Heterogeneous processing," IEEE Comput., vol.26, no.6, pp.184–199, June 1993.

[2] I. Foster and C. Kesselman, The Grid: Blueprint for a New Computing Infrastructure, Morgan Kaufmann Publishers, San Fransisco, CA, 1999.

[3] D. Fernandez-Baca, "Allocating modules to processors in a distributed system," IEEE Trans. Softw. Eng., vol.11, pp.1427–1436, Nov. 1989.

[4] T.D. Braun, S. Ali, H.J. Seigel, D. Hensgen, and R.F. Freund, "Dynamic mapping of a class of independent tasks onto heterogeneous computing system," J. Parallel Distrib. Comput., vol.59, pp.107–131, 1999.

[5] T.D. Braun, H.J. Seigel, N. Beck, L.L. Boloni, M. Maheswaran, A.I. Reuther, J.P. Robertson, M.D. Theys, B. Yao, D. Hensgen, and R.F. Freund, "A comparison study of static mapping heuristic for a class of meta-task on heterogeneous computing systems," Proc. 8th Heterogeneous Computing Workshop, San Juan, Puerto Rico, 1999.

[6] T.D. Braun, H.J. Seigel, N. Beck, L.L. Boloni, M. Maheswaran, A.I. Reuther, J.P. Robertson, M.D. Theys, B. Yao, D. Hensgen, and R.F. Freund, "A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems," J. Parallel Distrib. Comput., vol.61, pp.810–837, 2001.

[7] W. Sun, Y. Zhang, and Y. Inoguchi, "Practical task flow scheduling for high throughput computational Grid," Proc. 35th Int'l Conf. Parallel Processing Workshop, pp.291–297, 2006.

[8] A.Y. Zomaya and Y.H. Teh, "Observations on using genetic algorithms for dynamic load-balancing," IEEE Trans. Parallel Distrib. Syst., vol.12, no.9, pp.899–911, Sept. 2001.

[9] A.Y. Zomaya, C. Ward, and B. Macey, "Genetic scheduling for parallel processor system: Comparative studies and performance issues," IEEE Trans. Parallel Distrib. Syst., vol.10, no.8, pp.795–812, Aug. 1999.

[10] A.J. Page and T.J. Naughton, "Dynamic task scheduling using genetic algorithms for heterogeneous distributed computing," Proc. 19th IEEE/ACM Intl. Parallel and Distributed Processing Symposium, p.189a, Denver, Colorado, 2005.

[11] A. Chien, B. Calder, S. Elbert, and K. Bhatia, "Entropia: Architecture and performance of an enterprise desktop grid system," J. Parallel Distrib. Comput., vol.63, pp.597–610, 2001.

[12] C. Weng and X. Lu, "Heuristic scheduling for bag-of-tasks applications in combination with QoS in the computational grid," J. Future Generation Computer System, vol.21, pp.271–280, 2003.

[13] J.H. Holland, Adaptation in Natural and Artificial System, Univ. of Michigan Press, 1975.

[14] P.C. Chu and J.E. Beasley, "A genetic algorithm for the generalised assignment problem," Computer Oper. Res., vol.24, pp.17–23, 1997.

[15] G. Syswerda, "Uniform crossover in genetic algorithms," Proc. 3rd Int'l Conf. on Genetic Algorithms, pp.2–9, 1989.

[16] R. Buyya and M. Murshed, "GridSim: A toolkit for the modeling and simulation of distributed resource management and scheduling for Grid computing," J. Concurrency and Computation: Practice and Experience, pp.1–32, 2002.

[17] F. Howell and R. McNab, "SimJava: A discrete event simulation package for Java with applications in computer systems modelling," First Int'l Conf. Web-baesed Modelling and Simulation, San Diego, CA, Jan. 1998.

[18] http://www.supercluster.org/research/traces/

[19] B. Rylander, Computational Complexity and the Genetic Algorithm, Ph.D. Dissertation, University of Idaho, USA, June 2001.

[20] D. Wright, "Cheap cycle from the desktop to the dedicated cluster: Combining opportunistic and dedicated scheduling with Condor," Proc. Int'l Conf. on Linux Cluster: the HPC Revolution, June 2001.

[21] S.J. Chapin, D. Katramatos, J. Karpovich, and A.S. Grimshaw, "The legion resource management system," Proc. 5th Workshop on Job Scheduling Strategies for Parallel Processing, vol.1659, pp.162–178, April 1999.

[22] L. He, S.A. Jarvis, D.P. Spooner, H. Jiang, D.N. Dillenberger, and G.R. Nudd, "Allocating non-real-time and soft real time jobs in multiclusters," IEEE Trans. Parallel Distrib. Syst., vol.17, no.2, pp.99–112, Feb. 2006.

[23] V. Berten, J. Goossens, and E. Jeannot, "On the distribution of sequential jobs in random broking for heterogeneous computational Grids," IEEE Trans. Parallel Distrib. Syst., vol.17, no.2, pp.113–124, Feb. 2006.

CiteULike    Connotea    Del.icio.us    What's this?

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by SUN, W. Articles by INOGUCHI, Y. Search for Related Content Social Bookmarking          What's this?