Open Access Open Access  Restricted Access Subscription or Fee Access

Simulated Annealing based Heuristic Approach for Dynamic Load Balancing Problem on Heterogeneous Distributed Computing System

Bibhudatta Sahoo, Sanjay kumar Jena, Sudipta Mahapatra

Abstract


Load balancing problem on Heterogeneous Distributed Computing System (HDCs) deals with allocation of tasks to computing nodes, so that computing nodes are evenly loaded. Due the complexity of dynamic load balancing problem majority of researchers uses heuristic algorithm to obtain near optimal solutions. We have used consistent ETC (Expected Time to Compute) matrix in to study the performance of simulated annealing (SA) algorithm to minimize the makespan. Simulated annealing based resource allocation algorithm uses sliding widow techniques to select the tasks to be allocated to computing nodes after number of iterations. A new codification suitable for simulated annealing algorithm has been introduced for dynamic load balancing on HDCS. We have also presented three algorithms for move sets representations for SA. Several simulations run have been made on proposed simulated annealing algorithm for dynamic load balancing on HDCS, and compare with conventional first fit (FF), and randomized algorithm. The effect of simulated annealing based dynamic load balancing scheme has been on comparisons with first-fit, and randomized heuristic algorithm with task scalability.

Keywords


Dynamic Load Balancing, Simulated Annealing, Heterogeneous Distributed System, Makespan

Full Text:

PDF

References


Fidanova, Stefka. "Simulated annealing for grid scheduling problem." In Modern Computing, 2006. JVA'06. IEEE John Vincent Atanasoff 2006 International Symposium on, pp. 41-45. IEEE, 2006.

Wu, Min-You, Wei Shu, and Hong Zhang. "Segmented min-min: A static mapping algorithm for meta-tasks on heterogeneous computing systems." In Heterogeneous Computing Workshop, 2000.(HCW 2000) Proceedings. 9th, pp. 375-385. IEEE, 2000.

Clawson, James. "Distributed computing architecture." U.S. Patent 6,112,304, issued August 29, 2000.

Joanna Kolodziej , and Semee Ullah Khan,―Multi-level hierarchic genetic-based scheduling of independent job in dynamic heterogeneous grid environment‖, Information Science, vol. 214, pp.1-19, 2012.

R. Thamilselvan, and P. Balasubramanie, ―Analysis of various alternate crossover strategies for genetic algorithm to solve job shop scheduling problem‖, European Journal of Scientific Research, Vol. 64, No.4, 2011, pp.538-554.

Onno Boxma, Ger Koole, and Zhen Liu,‖Queueing-theoretic solution methods for models of parallel and distributed systems‖, Centrum voor Wiskunde en Informatica, Department of Operations Research, Statistics, and System Theory, 1994.

Francois Spies, ―Modeling of optimal load balancing strategy using queuing theory‖ Micro processing and Microprogramming, vol.41, 1996, pp.555-570.

Caffrey, James, and Graham Hitchings. "Makespan distributions in flow shop scheduling." International Journal of Operations & Production Management 15.3 (1995): 50-58.

R. Rindzevicius, D. Poškaitis, and B. Dekeris. "Performance measures analysis of M/M/m/K/N systems with finite customer population." Electr. Electr. Eng 3.67 (2006): 65-70.

Sivarama P. Dandamudi, Sensitivity evaluation of dynamic load sharing in distributed systems, IEEE Concurrency,6(3), 1998, 62-72.

Jie Li, & Hisao Kameda, Load balancing problems for multiclass tasks in distributed/parallel computer systems, IEEE Transactions on Computers, 47(3), 1998, 322-332.

Jong-Chen Chen, Guo-Xun Liao, Jr-Sung Hsie, Cheng-Hua Liao: A study of the contribution made by evolutionary learning on dynamic load-balancing problems in distributed computing systems. Expert Syst. Appl. 34(1): 357-365 (2008)

Sukumar Ghosh,. Distributed systems: an algorithmic approach. Vol. 13. Chapman & Hall/CRC, 2006.

M. Nikravan, and M. H. Kashani. "A genetic algorithm for process scheduling in distributed operating systems considering load balancing." In Proceedings 21st European Conference on Modelling and Simulation Ivan Zelinka, Zuzana Oplatkova, Alessandra Orsoni, ECMS. 2007.

A.J. Page, T.M. Keane, and T.J. Naughton. Multi-heuristic dynamic task allocation using genetic algorithms in a heterogeneous distributed system. Journal of parallel and distributed computing, 70(7):758–766, 2010.

Mitchell D. Theys, et al. "Mapping tasks onto distributed heterogeneous computing systems using a genetic algorithm approach." Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences (2001): 135-178.

Tracy D. Braun, Howard Jay Siegel, Noah Beck, Ladislau L. Bölöni, Muthucumaru Maheswaran, Albert I. Reuther, James P. Robertson et al. "A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems." Journal of Parallel and Distributed computing 61, no. 6 (2001): 810-837.

Tracy D. Braun, Howard Jay Siegel, and Anthony A. Maciejewski. "Static mapping heuristics for tasks with dependencies, priorities, deadlines, and multiple versions in heterogeneous environments." In Parallel and Distributed Processing Symposium., Proceedings International, IPDPS 2002, Abstracts and CD-ROM, pp. 78-85. IEEE, 2002.

Jon Kleinberg & Eva Tardos, Algorithm Design (Pearson Education Inc. 2006).

Jie Wu, Distributed system design,(CRC press, 1999)

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, 1979.

H. J. Siegel, and S. Ali, Techniques for mapping tasks tonodes in heterogeneous computing, Systems, Journal of Systems Architecture, 46(8), 2000, 627—639.

S. Ali; H.J. Siegel, M. Maheswaran, D. Hensgen; , "Task execution time modeling for heterogeneous computing systems ," Heterogeneous Computing Workshop, 2000. (HCW 2000) Proceedings. 9th , vol., no., pp.185-199, 2000.

Helen D. Karatza, & Ralph C. Hilzer, Load sharing in heterogeneous distributed systems, Proceedings of the Winter Simulation Conference, 1, San Diego California, 2002 Page(s): 2002, 489 – 496.

Genetic Algorithm and Direct Search Toolbox 2, User Guide, The MathWorks, Inc., US, 2009.

Kalyanmoy Deb, Optimization for Engineering Design: Algorithm and Examples, Prentice hall of India, 1998.

Gamal Attiya, and Yskandar Hamam, ―Task allocation for maximizing reliability of distributed system: A simulated annealing approach‖, Journal of parallel and Distributed Computing, vol.66, pp. 1259-1266, 2006

Cheng-Zhong Xu, and Francis CM Lau. "Iterative dynamic load balancing in multicomputers." Journal of the Operational Research Society (1994): 786-796.

Gamal Attiya, and Yskandar Hamam. "Two phase algorithm for load balancing in heterogeneous distributed systems." In Parallel, Distributed and Network-Based Processing, 2004. Proceedings. 12th Euromicro Conference on, pp. 434-439. IEEE, 2004.

Talbi, E-G., and Traian Muntean. "Hill-climbing, simulated annealing and genetic algorithms: a comparative study and application to the mapping problem." In System Sciences, 1993, Proceeding of the Twenty-Sixth Hawaii International Conference on, vol. 2, pp. 565-573. IEEE, 1993.

Bora Ucar, Cevdet Aykanat, Kamer Kaya, & Murat Ikinci, Task assignment in heterogeneous computing system, Journal of parallel and Distributed Computing, Vol.66, pp.32-46, 2006.

K. S. Trivedi, Probability and statistics with reliability, queuing and computer science applications, Prentice Hall of India, 2001.

Thomas V. Christensen, ―Heuristic Algorithms for NP-Complete Problems‖ Project report, Institute of Informatics and mathematical Modeling, Technical University of Denmark.2007.

Daniel Grosu, and Anthony T. Chronopoulos, ―Algorithmic Mechanisim Design for load balancing in Distributed system‖, IEEE transaction on system man and cybernetics-Part B: cybernetics, vol.34, No.1, PP. 77-84, 2004.

Suman, Balram, and Prabhat Kumar. "A survey of simulated annealing as a tool for single and multiobjective optimization." Journal of the operational research society , Vol.57, No. 10, pp.1143-1160, 2005.

R. H. J. M. Otten and L. P. P. P. van Ginneken. The Annealing Algorithm, Kluwer Academic Publishers, 1989.

K K. Hwang, G.C. Fox, and JJ Dongarra., ―Distributed and Cloud Computing: From Parallel Processing to the Internet of Things‖, Morgan Kaufmann, 2012.

A.Y. Zomaya and Y.H. Teh, ―Observations on using genetic algorithms for dynamic load-balancing‖, IEEE Trans. on Parallel and Dist. Systems, pp.899-911, September 2001.

S. Kirkpatrick, C.D. Gelatt Jg., M. P. Vecchi, ―Optimization by Simulated Annealing‖, Science 220, pp.671-680, 1983.

Bibhudatta Sahoo, Dillip Kumar and Sanjay Kumar Jena, ―Analysing the Impact of Heterogeneity with Greedy Resource Allocation Algorithms for Dynamic Load Balancing in Heterogeneous Distributed Computing System‖, International Journal of Computer Applications, Vol. 62, No.19, pp.25-34, January 2013. Published by Foundation of Computer Science, New York, USA

Wen-Chiung Lee, Chin-China Wu, and Peter Chen, ―A Simulated annealing approach to makespan minimization on identical parallel machines‖, International Journal of Advanced Manufacturing Technology, Vol.31, pp.328-334, 2006.

S. Kirkpatrick, ―Optimization by Simulated Annealing: Quantitative Studies‖, Journal of Statistical Physics, Vol.34, No.5/6, pp.975-986, 1984.

Amir Masoud Rahmani and Mojtaba Rezvani, ―A Novel Genetic Algorithm for Static Task Scheduling in Distributed Systems‖, International Journal of Compute Theory and Engineering, Vol.1, No1, April 2009.

R. L. Haupt, and S.E. Haupt, ―Practical genetic algorithm‖, John Willy and Sons, 2004.

Helen D. Karatza Ralph C. Hilzer ―Load Sharing in Heterogeneous Distributed Systems‖ Proceeding of the winter simulation conference, 2002, pp.489-496.


Refbacks

  • There are currently no refbacks.