Two Heuristic Approaches for Mapping Parallel Applications on Distributed Computing Systems

Shouman, Marwa; Attiya, Gamal M.; Morsi, Ibrahim Z.

doi:10.21608/mjeer.2008.65226

Two Heuristic Approaches for Mapping Parallel Applications on Distributed Computing Systems

Document Type : Original Article

Authors

¹ Dept. of Computer Science and Eng., Faculty of Elect., Eng., Minufiya University

² * Dept. of Computer Science and Eng., Faculty of Elect., Eng., Minufiya University

³ Dept. of Electrical Engineering, Faculty of Engineering, Minufiya University

10.21608/mjeer.2008.65226

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 21^st 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 12^th 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.