The week's pick
Reseach Article
Improved Task Scheduling on Parallel System using Genetic Algorithm
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 39 - Number 17 |
| Year of Publication: 2012 |
| Authors: Jasbir Singh, Gurvinder Singh |
10.5120/4912-7449
|
Jasbir Singh, Gurvinder Singh . Improved Task Scheduling on Parallel System using Genetic Algorithm. International Journal of Computer Applications. 39, 17 ( February 2012), 17-22. DOI=10.5120/4912-7449
Abstract
Parallel Processing refers to the concept of speeding-up the execution of a task by dividing the task into multiple fragments that can execute simultaneously, each on its own processor i.e. it is the simultaneous processing of the task on two or more processors in order to obtain faster results. It can be effectively used for tasks that involve a large number of calculations, have time constraints and can be divided into a number of smaller tasks. The scheduling problem deals with the optimal assignment of a set of tasks onto parallel multiprocessor system and orders their execution so that the total completion time is minimized. The efficient execution of the schedule on parallel multiprocessor system takes the structure of the application and the performance characteristics of the proposed algorithm. Many heuristics and approximation algorithms have been proposed to fulfill the scheduling task. It is well known NP-complete problem. This study proposes a genetic based approach to schedule parallel tasks on heterogeneous parallel multiprocessor system. The scheduling problem considered in this study includes - next to search for an optimal mapping of the task and their sequence of execution and also search for an optimal configuration of the parallel system. An approach for the simultaneous optimization of all these three components of scheduling method using genetic algorithm is presented and its performance is evaluated in comparison with the First Come First Serve (FCFS), Shortest Job First (SJF), Round Robin (RR), Priority and Largest Job First (LJF) scheduling methods.
References
- Sara Baase, Allen Van Gelder,”Computer Algorithms”, Published by Addison Wesley, 2000.
- Sartaj Sahni, ”Algorithms Analysis and Design”, Published by Galgotia Publications Pvt. Ltd., New Delhi, 1996.
- Anup Kumar, Sub Ramakrishnan, Chinar Deshpande, Larry Dunning, “ IEEE Conference on Parallel processing”, 1994Page no.83-87.
- Ananth Grama, Georage Karypis, Anshul Gupta, Vipin Kumar,“Introduction to parallel computing”, Published by Pearson Education, 2009.
- Kalyanmoy Deb,”Optimization for Engineering Design”, Published by PHI, 2003.
- Dezso Sima, Terence Fountain, Peter Kacsuk, “ Advanced Computer Architectures”, Published by Pearson Education, 2009.
- David E. Goldberg,”Genetic Algorithms in Search, Optimization and Machine Learning”, Published by Pearson Education, 2004, Page No.60-83.
- Mitchell, Melanie,” An Introduction to Genetic Algorithm, Published Bu MIT Press 1996
- Michael J Qumn, “Parallel Computing Theory and Practices, 2nd Edition”, Published by Tata McGraw Hill Education Private Ltd, Page No. 346-364.
- Michael J Qumn, “Parallel Programming”, Published by Tata McGraw Hill Education Private Ltd, Page No. 63-89.
- John L Hennessy, David A Pattern, “Computer Architecture, 3rd Edition”, Published by Morgan Kaufmann & Elsevier India, Page No. 528-590.
- David E Culler, “Parallel Computer Architecture”, Published by Morgan Kaufmann & Elsevier India.
- J P Hayes, “Computer Architecture and Organization”, Published by McGraw Hill International Edition.
- J D Carpinalli, “Computer System Organization & Architecture”, Published by Pearson Education.
- Sung-Ho Woo, Sung-Bong Yang, Shin-Dug Kim, and tack-Don Han ,” IEEE Trans on parallel System, 1997, Page 301-305.
- M.Salmani Jelodar, S.N.Fakhraie, S.M.fakharie, M.N. Ahmadabadi,” IEEE Proceeding, 2006, Page No 340-347.
- Man Lin and Laurence tianruo Yang,”IEEE Proceeding”, 1999, Page No 382-387
- Yajun Li, Yuhang yang, Maode Ma, Rongbo Zhu, “ IEEE Proceeding”, 2008.
- YI-Wen Zhong, Jian-Gang Yang, Heng-Nlan QI,” IEEE Proceeding”, August 2004, Page No. 2463-2468.
- Imtiaz Ahmad, Muhammad K. Dhodhi and Arif Ghafoor,” IEEE Proceeding”, 1995, Page No. 49-53.
- Ceyda Oguz and M.Fikret Ercan,” IEEE Proceeding”, 2004, Page No. 168-170
- Kai Hwang & Faye A. Briggs,”Computer Architecture and Parallel Processing”, Published by McGraw Hill ,1985.Page No. 445-47, 612.
- Andrei R. & Arjan J.C. van Gemund, “Fast and Effective Task Scheduling in Heterogeneous Systems”, IEEE Proceeding, 2000.
- Michael Bohler, Frank Moore, Yi Pan, “Improved Multiprocessor Task Scheduling Using Genetic Algorithms”, Proceedings of the Twelfth International FLAIRS Conference, 1999.
- Andrew J. page,” Adaptive Scheduling in Heterogeneous Distributed Computing System”,
- Jameela Al-Jaroodi, Nader Mohamed, Hong Jiang and David Swanson,” Modeling Parallel Applications Performance on Heterogeneous Systems”, Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS’03)
- Yu-Kwong and Ishraq Ahmad, “Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors”, ACM Computing Surveys, Vol. 31, No. 4, December 1999
- Wai-Yip Chan and Chi-Kwong Li, “Scheduling Tasks in DAG to Heterogeneous Processor System”, Proceeding IEEE 1998.
- Wojciech Cencek, “High-Performance Computing on Heterogeneous Systems”, Computational Methods in Science and Technology, 1999
- C.P Ravikumar, A.K Gupta,” IEEE proc. Comput. Digit. Tech., Vol 142, No. 2”, March 1995, Page No. 81-86.
Index Terms
Keywords