CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Analysing the Impact of Heterogeneity with Greedy Resource Allocation Algorithms for Dynamic Load Balancing in Heterogeneous Distributed Computing System

by Bibhudatta Sahoo, Dilip Kumar, Sanjay Kumar Jena
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 62 - Number 19
Year of Publication: 2013
Authors: Bibhudatta Sahoo, Dilip Kumar, Sanjay Kumar Jena
10.5120/10190-5070

Bibhudatta Sahoo, Dilip Kumar, 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. 62, 19 ( January 2013), 25-34. DOI=10.5120/10190-5070

@article{ 10.5120/10190-5070,
author = { Bibhudatta Sahoo, Dilip Kumar, Sanjay Kumar Jena },
title = { Analysing the Impact of Heterogeneity with Greedy Resource Allocation Algorithms for Dynamic Load Balancing in Heterogeneous Distributed Computing System },
journal = { International Journal of Computer Applications },
issue_date = { January 2013 },
volume = { 62 },
number = { 19 },
month = { January },
year = { 2013 },
issn = { 0975-8887 },
pages = { 25-34 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume62/number19/10190-5070/ },
doi = { 10.5120/10190-5070 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:12:58.474520+05:30
%A Bibhudatta Sahoo
%A Dilip Kumar
%A Sanjay Kumar Jena
%T Analysing the Impact of Heterogeneity with Greedy Resource Allocation Algorithms for Dynamic Load Balancing in Heterogeneous Distributed Computing System
%J International Journal of Computer Applications
%@ 0975-8887
%V 62
%N 19
%P 25-34
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Heterogeneous Distributed systems have been an active research area in computer science for the last two decade, task allocation and load balancing have been a major issue associated with such systems. The load-balancing problem, attempts to compute the assignment with smallest possible makespan (i. e. the completion time at the maximum loaded computing node). This paper presents and discusses the dynamic load balancing problem on Heterogeneous Distributed Computing System (HDCS) and analyzes the impact of heterogeneity on computing capability of node on task allocation problem. Since the task assignment problem in NP hard, greedy heuristic algorithms are used to study the impact of heterogeneity on computing resources. The task model is presented as consistent ETC (Expected Time to Compute) matrix in four different heterogeneous computing environments to study the performance of heuristic algorithms to minimize the makespan.

References
  1. Sivarama P. Dandamudi, Sensitivity evaluation of dynamic load sharing in distributed systems, IEEE Concurrency,6(3), 1998, 62-72.
  2. Jie Li, & Hisao Kameda, Load balancing problems for multiclass tasks in distributed/parallel computer systems, IEEE Transactions on Computers, 47(3), 1998, 322-332.
  3. Gamal Attiya & Yskandar Hamam, Two phase algorithm for load balancing in heterogeneous distributed systems, Proc. 12th IEEE EUROMICRO conference on Parallel, Distributed and Network-based processing, Coruna, Spain 2004, 434-439.
  4. Jon Kleinberg & Eva Tardos, Algorithm Design (Pearson Education Inc. 2006).
  5. 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.
  6. Jie Wu, Distributed system design,(CRC press, 1999)
  7. Y. Zhang, H. Kameda & S. L. Hung, Comparison of dynamic and static load-balancing strategies in heterogeneous distributed systems, IEE proceedings in Computer and Digital Techniques,144(2), 1997, 100-106.
  8. Bora Ucar, Cevdet Aykanat, Kamer Kaya, & Murat Ikinci, Task assignment in heterogeneous computing system, Journal of parallel and Distributed Computing, 66, 2006, 32-46.
  9. Marta Beltran, Antonio Guzman, & Jose Luis Bosque, Dealing with heterogeneity in load balancing algorithm, Proc. 5th IEEE International Symposium on Parallel and Distributed Computing, Timisoara, Romania, 2006, 123-132.
  10. B. A. Shirazi, A. R. Hurson, & K. M. Kavi, Scheduling and load balancing in parallel and distributed systems, CS press, 1995.
  11. K. S. Trivedi, Probability and statistics with reliability, queuing and computer science applications, Prentice Hall of India, 2001.
  12. Bibhudatta Sahoo, S. Mohapatra, S. K. Jena, "Genetic Algorithm Based Dynamic Load Balancing Scheme for Heterogeneous Distributed Systems ",Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA 2008, Las Vegas, Nevada, USA, July 14-17, 2008, 2 Volumes. CSREA Press 2008, ISBN 1-60132-084-1
  13. A. Y. Zomaya, & Y. H. Teh, Observations on using genetic algorithms for dynamic load-balancing, IEEE Transactions on Parallel and Distributed Systems, 12(9), 2001, 899-911.
  14. H. J. Siegel, and S. Ali, Techniques for mapping tasks to nodes in heterogeneous computing, Systems, Journal of Systems Architecture, 46(8), 2000, 627—639.
  15. 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.
  16. M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen, and R. F. Freund, " Dynamic mapping of a class of independent tasks into heterogeneous computing, special Issues on Software Support for Distributed Computing, Vol. 59, No. 2, pp. 107-131, Nov. 1999.
  17. 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.
  18. Francois Spies, "Modeling of optimal load balancing strategy using queuing theory" Micro processing and Microprogramming, vol. 41, 1996, pp. 555-570.
  19. Caffrey, James, and Graham Hitchings. "Makespan distributions in flow shop scheduling. " International Journal of Operations & Production Management 15. 3 (1995): 50-58.
  20. Rindzevicius, R. , 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.
  21. Smith, David K. "Calculation of steady-state probabilities of M/M queues: further approaches. " Journal of Applied Mathematics and Decision Sciences 6. 1 (2002): 43-50.
  22. Thomas V. Christensen, "Heuristic Algorithms for NP-Complete Problems" Project report, Institute of Informatics and mathematical Modelling, Technical University of Denmark. 2007.
  23. B Krishna Kumar, S. Pavai Madheswari, and K. S. Venkatakrishnan. . "Transient solution of an M/M/2 Queue with Heterogeneous Server Subject to Catastrophes. " Journal of Information and Management Sciences, Vol. (18), no(1) (2007): 63-80.
  24. 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.
  25. 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)
  26. Daniel Grosu, and Anthony T. Chronopoulos, "Algorithmic Mechanism 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.
  27. Chin-Ching Chiu, Chung-Hsien Hsu, and Yi-Shiung Yeh, "A genetic algorithm for reliability-oriented task Assignment with k duplications in distributed systems", IEEE Transaction on reliability, vol. 55, No. 1, pp. 105-117, March 2006
  28. A. J. Page and T. J. Naughton, "Framework for Task Scheduling in Heterogeneous Distributed Computing Using Genetic Algorithms," Artificial Intelligence Review, vol. 24, pp. 415–429, November 2005.
  29. Tracy D. Braun, 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, vol. 61, pp. 810-837, 2001
  30. 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.
Index Terms

Computer Science
Information Sciences

Keywords

Load Balancing Makespan Resource Allocation Heterogeneous Distributed Systems Expected Time to Compute (ETC)

Powered by PhDFocusTM