Two Heuristic Approaches for Mapping Parallel Applications on Distributed Computing Systems

Attiya, Gamal M.; Morsi, Ibrahim Z.

doi:10.21608/mjeer.2010.66545

Two Heuristic Approaches for Mapping Parallel Applications on Distributed Computing Systems

Document Type : Original Article

Authors

Gamal M. Attiya ¹
Ibrahim Z. Morsi ²

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

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

10.21608/mjeer.2010.66545

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] 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.

[2] 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

[3] 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.

[4] 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.

[5] 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.