A Modified Genetic Algorithm for Load Balancing in Heterogeneous Distributed Computing Systems | ||||
| Menoufia Journal of Electronic Engineering Research | ||||
| Article 1, Volume 21, Issue 1, January 2011, Page 1-18 | ||||
| Document Type: Original Article | ||||
| DOI: 10.21608/mjeer.2011.63698 | ||||
 View on SCiNiTO | ||||
| Authors | ||||
| Marwa Shouman1; Gamal M. Attiya1; Ibrahim Z. Morsi2 | ||||
| 1Dept. of Computer Science and Eng., Faculty of Elect., Eng., Minufiya University | ||||
| 2Dept. of Electrical Engineering, Faculty of Engineering, Minufiya University. | ||||
| Abstract | ||||
| This paper addresses the problem of static load balancing in heterogeneous distributed computing systems taking into account both memory and communication capacity constraints. It first models the load balancing problem as an optimization problem. It then presents a modified genetic algorithm, called Adaptive Genetic Algorithm (AGA), to solve the problem. The performance of the proposed algorithm is evaluated by simulation studies on randomly generated instances and the results are compared with that obtained by applying both the Genetic Algorithm (GA) and the Simulated Annealing (SA). Also, the qualities of the results are compared with the optimal solutions that obtained by applying the Brach-and-Bound (BB) algorithm. | ||||
| References | ||||
|
[1] C.-C. Hui and S. T. Chanson, “Allocating Task Interaction Graph to Processors in Heterogeneous Networks,” IEEE Transactions on Parallel and Distributed Systems, Vol. 8, No. 9, pp. 908-925, September 1997. [2] M. Kafil and I. Ahmed “Optimal Task Assignment in Heterogeneous Distributed Computing Systems,” IEEE Concurrency, Vol.6, No.3, pp.42- 51, July-September 1998. [3] A. Tom and C. S. R. Murthy “Optimal task allocation in distributed systems by graph matching and state space search,” J. of Systems and Software, Vol. 46, No. 1, pp. 59–75, April 1999. [4] Nirmeen A. Bahnasawy, Gamal M. Attiya, Mervat Mosa and Magdy A. Koutb, "A Modified A* Algorithm for Allocating Tasks in Heterogeneous Distributed Computing Systems" International Journal of Computing, Vol. 8, Issue 2, pp. 50-57, 2009. [5] Y.-C. Ma and C.-P. Chung, “A Dominance Relation Enhanced Branchand-Bound Task Allocation,” J. of Systems and Software, Vol. 58, No. 2, pp.125-134, Sep. 2001 [6] G. Attiya and Y. Hamam “Static Task Assignment in Distributed Computing Systems,” A book chapter in "Information processing: Recent Mathematical Advances in Optimization and Control", Chapter XIX, pages 241-258. Presses de l'Ecole des Mines de Paris, Paris, 2005, ISBN: 2911762568. [7] G. Attiya and Y. Hamam. “Optimal Allocation of Tasks onto Networked Heterogeneous Computers using minimax Criterion,” International Network Optimization Conference (INOC'03), pp. 25-30, Evry/Paris, France, 2003. [8] P. Bourvy, J. Chassin, M. dobruck, L.Hluch , E. Luque, and T. Margalef, “Mapping and Load Balancing on Distributed Memory Systems,” Proceedings of the Eight Symposium on Microcomputer and Microprocessor Applications, Vol. 1, pp. 315-324,1994. [9] P. Bouvry, J. Chassin, and D. Trystram, “Efficient Solution for Mapping Parallel Programs,” Proceedings of EuroPar'95, LNCS: 379-390, August 1995. [10] L. Wang, H. J. Siegel, V. P. Roychowdhury, and A. A. Maciejewski, “Task Matching and Scheduling in Heterogeneous Computing Environments Using a Genetic-Algorithm-Based Approach,” J. of Parallel and Dist. Computing, vol.47, pp.8–22, 1997. [11] J. Aguilar and E. Gelenbe, “Task Assignment and Transaction Clustering Heuristics for Distributed Systems,” Information Sciences, Vol. 97, No.1- 2, pp.199–219, March 1997.
[12] M. H. Zaharia, F. Leon, D. Gâlea, “Parallel Genetic Algorithms for Cluster Load Balancing,” Proceedings ECIT2004 - Third European Conference on Intelligent Systems and Technologies, Iasi, Romania, July 21-23, 2004. [13] Bibhudatta Sahoo, Sudipta Mohapatra, and Sanjay Kumar Jena, "A 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. ISBN: 1-60132-084-1 [14] Kamaljit Kaur, Amit Chabra, and Gurvinder Singh, "Modified Genetic Algorithm for Task Scheduling in Homogenous Parallel System using Heuristics," International Journal of Soft Computing 5 (2), pp. 42-51, 2010. ISSN: 1816-9503. [15] M.shouman, G.M.Attiya, and I.Z.Morsi, "Two Heuristic Approaches for Mapping Parallel Application on Distributed Computing Systems" Menoufia Journal of Electronic Engineering Research (MJEER), Vol. 18, no. 2, pp. 85-98, July 2008. [16] Y. Hamam and K.S. Hindi, “Assignment of Program Modules to Processors: A Simulated Annealing Approach,” European Journal of Operational Research, Vol. 122, No. 2, pp.509-513, April 2000. [17] Gamal Attiya and Yskandar HAMAM, "Task Allocation for maximizing reliability of distributed Systems: A Simulated Annealing Approach", Journal of parallel and distributed computing (JPDC), Vol. 66, No. 10, pp. 1259-1266, October 2006. [18] G. Attiya and Y. Hamam, “Two Phase Algorithm for Load Balancing in Heterogeneous Distributed Systems,” IEEE Proceedings of 12th Euromicro Conference on Parallel, Distributed and Network based Processing (PDP2004), pp. 434-439, A Coruna, Spain, Feb. 11-13, 2004. [19] M. A. Senar, A. Ripoll, A. Corts, E. Luque, “Clustering and Reassignment–Based Mapping Strategy for Message-Passing Architectures,” Journal of System Architecture, Vol. 48, No. 8-10, pp.267- 283, March 2003. [20] Á. E. Eiben, R. Hinterding, and Z. Michalewicz, “Parameter control in evolutionary algorithms,” IEEE Trans. Evol. Comput., vol. 3, pp. 124-141, Jul. 1999 | ||||
|
Statistics Article View: 120 |
||||
