Two Heuristic Approaches for Mapping Parallel Applications on Distributed Computing Systems | ||
| Menoufia Journal of Electronic Engineering Research | ||
| Article 1, Volume 18, Issue 2, December 2008, Pages 85-98 | ||
| Document Type: Original Article | ||
| DOI: 10.21608/mjeer.2008.65226 | ||
| Authors | ||
| Marwa Shouman1; Gamal M. Attiya2; Ibrahim Z. Morsi3 | ||
| 1Dept. of Computer Science and Eng., Faculty of Elect., Eng., Minufiya University | ||
| 2* Dept. of Computer Science and Eng., Faculty of Elect., Eng., Minufiya University | ||
| 3Dept. of Electrical Engineering, Faculty of Engineering, Minufiya University | ||
| Abstract | ||
| The performance of a parallel application running on a Distributed Computing System (DCS) is basically affected by the distribution of workload over the various processors in the system. This problem is known to be NP-hard in most cases and complicates farther with increasing number of tasks and/or computers. This paper presents two heuristic algorithms; Simulated Annealing (SA) and Genetic Algorithm (GA), to solve the mentioned problem. The qualities of the resulting distribution are compared with that obtained by applying the Branch–and-Bound (BB) technique | ||
| 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] 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
[5] G. Attiya and Y. Hamam “Static Task Assignment in Distributed Computing Systems,” The 21st IFIP TC 7 Conference on System Modeling and Optimization Conference, France, 2003.
[6] G. Attiya and Y. Hamam. “Optimal Allocation of Tasks onto Networked Heterogeneous Computers using Minimax Criterion,” International Network Optimization Conference (INOC'03), Evry/Paris, France, 2003.
[7] P. Bourvy, J. Chassin, M. dobruck, L.Hluch , E. Luque, and T. Margalef, “Mapping and Load Balancing on Distributed Memory Systems,” Proc., of the Eight Symposium on Microcomputer and Microprocessor Applications, Vol. 1, pp. 315-324,1994.
[8] P. Bouvry, J. Chassin, and D. Trystram, “Efficient Solution for Mapping Parallel Programs,” Proceedings of EuroPar'95, LNCS: 379-390, August 1995.
[9] 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.
[10] 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, A Coruna, Spain, Feb. 11-13, 2004.
[11] 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.
[12] 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.
[13] 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.
[14] C. A. Bohn and G. B. Lamont, “Load Balancing for Heterogeneous Clusters of PCs,” Future Generation Computer Systems, Vol.18, No. 3, pp.389–400, January 2002.
[15] G. Attiya and Y. Hamam, "Task Allocation for Maximizing Reliability of Distributed Systems: A Simulated Annealing Approach," Journal of parallel and Distributed Computing, Vol. 66, pp.1259-1266, Oct. 2006.
[16] Erol Gelene and arakesh Kushwaha, “Dynamic Load Balancing in Distributed Systems,”, Modeling, Analysis, and Simulation of Computer and Telecommumication System , MASCOTS'94., pp.245-249, Jan 1994.
[17] A. Cortes, A. Ripoll, M. A. Sena and E. Luque, "Performance Comparison of Dynamic Load Balancing Strategies for Distributed Computing", the 32nd Hawaii International Conference on System Sciences, 1999.
[18] S. Kirkpatrick, C. D. Gelatt and J. M. P. Vecchi, “Optimization by Simulated Annealing,” Sciences, Vol. 220, pp. 671-680, May 1983.
[19] E. Aarts and J. Korst, “Simulated Annealing and Boltzmann Machines,” John Wiley and Sons, New York, 1989.
[20] 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.
[21] M. Srinivas, and L. M. Patnaik, “Genetic algorithms: A survey,” IEEE Computer, Vol. 27, No. 6, pp. 17–26, June 1994.
[22] J. L. Ribeiro Filho, and P. C. Treleaven, “Genetic-algorithm programming environments,” IEEE Computer, vol. 27, No. 6, pp.28– 43, June 1994.
[23] J. Michael Johnson and Yahya Rahmat-Samii, "Genetic algorithms in Engineering Electromagnetics,” IEEE.Antennas and Propagation Magazine, vol.39, No. 4, pp.7-21, 1997. | ||
|
Statistics Article View: 123 |
||
