A MODIFIED A* ALGORITHM FOR ALLOCATING TASK IN HETEROGENEOUS DISTIRBUTED COMPUTING SYSTEMS

Authors

  • Nirmeen A. Bahnasawy
  • Gamal M. Attiya
  • Mervat Mosa
  • Magdy A. Koutb

DOI:

https://doi.org/10.47839/ijc.8.2.666

Keywords:

Parallel processing, task assignment, distributed computers, heterogeneous processors.

Abstract

Distributed computing can be used to solve large scale scientific and engineering problems. A parallel application could be divided into a number of tasks and executed concurrently on different computers in the system. This paper provides an optimal task assignment algorithm under memory constraints to minimize required time of finishing a parallel application. The proposed algorithm is based on the optimal assignment sequential search (OASS) of the A* algorithm with additional modifications. This modified algorithm yields optimal solution, lower time complexity, reduces the turnaround time of the application and considerably faster compared with the sequential search algorithm.

References

A. K. Tripathi, B. K. Sarker, N. Kumar and D. P. Vidyanhi, “Multiple Task Allocation with Load Considerations”, Int. Journal of Information and Computing Science (IJICS), Vo1. 3, No, pp.3634, 2000.

Gamal Attiya and Yskandar Hamam, “Optimal Allocation of Tasks onto Networked Heterogeneous Computers Using Minimax Criterion”, Proceedings of International Network Optimization Conference (INOC,03), pp. 25-30, Evry/Paris, France, 2003.

Gamal Attiya and Yskandar Hamam, “Hybrid Algorithm for Mapping Parallel Applications in Distributed Systems”, Fifth International Conference on PRAM, Poland, 7-10 September 2003.

Gamal Attiya and Yskandar Hamam, “Performance Oriented Allocation in Heterogeneous Distributed Systems”, European Simulation and Modeling (ESM 2003) Conference, University of Naples II, Naples, Italy, pp. 27-29 October 2003.

Gamal Attiya and Yskandar Hamam, “Task Allocation for Maximizing Reliability of Distributed Systems: A simulated Annealing Approach”, J. Parallel Distributed Computer, 66, pp. 1259-1266, 2006.

Haluk Topcuoglu, Salim Hariri, and Min-You Wu, “Performance- Effective and Low-Complexity Task Scheduling for Heterogeneous Computing”, (IEEE Transactions on Distributed Systems, vol. 13. no. 3 march 2002.

I. Ahmed, Y Kwak, and M.-Y. Wu, “Analysis, Evaluation, and Comparison of Algorithms for Scheduling Task Graphs on Parallel Processors”, 2nd Int’l Symposium on Parallel architectures, Algorithms, and Networks, I-SPAN. Beijing. China. Proc. Of the 1996.

Kamer Kaya a, Bora Ucar a, Cevdet Aykanat, Murat Ikinci, “Task assignment in heterogeneous computing systems” J. Parallel Distributed Computers. 66, pp. 32 – 46, (2006).

L. W. Dowdy, E.Rosti, E. Smirni, G. Serazzi, and K. C. Sevcik, “Processor Saving Scheduling Policies for Multiprocessor Systems” IEEE Trans. Comput., vol. 47, no. 2, Feb 1998.

M. Kafil, “An Optimal Task Assignment Algorithms in Distributed Computing Systems”, IEEE Concurrency, 98, pp 42-49, September 1998.

M. Mezmaz, N. Melab, and E.-G. Talbi, “An Efficient Load Balancing Strategy for Grid-Based Branch and Bound Algorithm”, Parallel Computing 33, pp. 302-313. February 2007.

S. Woo, S. Yang, S. Kim, and T. Han, “Task Scheduling in Distributed computing Systems with a Genetic Algorithm”, IEEE, New York, 1997.

Sih, E.A.Lee, “A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures”, IEEE Trans. Parallel Distributed Systems4, pp. 175-186, February 1993.

W. Boyer, G. Hura, “A New Min-Span Heuristic Algorithm for Task Scheduling in Heterogeneous Systems” Proceedings of the Sixth Biennial World conference On Integrated Design and Process Technology, 23. pp. 69, June 2002.

Yskandar Hamam, Khalil S. Hindi, “Assignment of Program Modules to Processors: A Simulated Annealing Approach”, European Journal of Operational Research 122, pp. 509-513. 2000.

Yu-Kwong Kwok, Ishfaq Ahmad, “On Multiprocessor Task Scheduling Using Efficient State Space Search Approaches”, J. Parallel Distributed Computing 65, pp. 1515-1532, (2005).

Yi-Wen Zhong, Jian-Gang Yang, and Heng-Nian, “A Hybrid Genetic Algorithm for Tasks Scheduling in Heterogeneous Computing Systems” Proceedings of the Third International Conference on Machine Learning and Cybernetics, Shanghai, PP. 26-29, August 2004.

Z.-C. Shen and W.-H. Tsai, “A Graph Matching Approach to Optimal Task Assignment in Distributed Computing System Using a Minimax Criterion”, IEEE Trans. Computers, Vol. C-34, No. 3, Mar., pp. 197–203 1985.

Downloads

Published

2014-08-01

How to Cite

Bahnasawy, N. A., Attiya, G. M., Mosa, M., & Koutb, M. A. (2014). A MODIFIED A* ALGORITHM FOR ALLOCATING TASK IN HETEROGENEOUS DISTIRBUTED COMPUTING SYSTEMS. International Journal of Computing, 8(2), 50-57. https://doi.org/10.47839/ijc.8.2.666

Issue

2009, Volume 8, Issue 2

Section

Articles

License

International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:
•    Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
•    Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
•    Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.