Open Access Open Access  Restricted Access Subscription Access

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

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

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.

Keywords


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

Full Text:

PDF

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.


Refbacks

  • There are currently no refbacks.