CFP last date
22 April 2024
Reseach Article

Static Workload Distribution of Parallel Applications in Heterogeneous Distributed Computing Systems with Memory and Communication Capacity Constraints

by Marwa Shouman, Gamal Attiya, Ibrahim Z. Morsi
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 34 - Number 6
Year of Publication: 2011
Authors: Marwa Shouman, Gamal Attiya, Ibrahim Z. Morsi
10.5120/4095-5977

Marwa Shouman, Gamal Attiya, Ibrahim Z. Morsi . Static Workload Distribution of Parallel Applications in Heterogeneous Distributed Computing Systems with Memory and Communication Capacity Constraints. International Journal of Computer Applications. 34, 6 ( November 2011), 18-24. DOI=10.5120/4095-5977

@article{ 10.5120/4095-5977,
author = { Marwa Shouman, Gamal Attiya, Ibrahim Z. Morsi },
title = { Static Workload Distribution of Parallel Applications in Heterogeneous Distributed Computing Systems with Memory and Communication Capacity Constraints },
journal = { International Journal of Computer Applications },
issue_date = { November 2011 },
volume = { 34 },
number = { 6 },
month = { November },
year = { 2011 },
issn = { 0975-8887 },
pages = { 18-24 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume34/number6/4095-5977/ },
doi = { 10.5120/4095-5977 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:20:23.322757+05:30
%A Marwa Shouman
%A Gamal Attiya
%A Ibrahim Z. Morsi
%T Static Workload Distribution of Parallel Applications in Heterogeneous Distributed Computing Systems with Memory and Communication Capacity Constraints
%J International Journal of Computer Applications
%@ 0975-8887
%V 34
%N 6
%P 18-24
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
Abstract

This paper addresses the problem of static load balancing in heterogeneous distributed computing systems taking into account both memory and communication capacity constraints. The load balancing problem is first modeled as an optimization problem. Then, a heuristic approach, called Adaptive Genetic Algorithm (AGA), is proposed 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 Branch-and-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 Transac-tion Clustering Heuristics for Distributed Systems,” Informa¬tion 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.
Index Terms

Computer Science
Information Sciences

Keywords

Load Balancing Simulated Annealing Genetic Algorithm Heuristics Mapping