Open Access Open Access  Restricted Access Subscription or Fee Access

Improved Genetic Algorithm (IGA) for Scheduling Task Graphs in Multiprocessor Systems

Kamaljit Kaur, Amit Chhabra, Gurvinder Singh

Abstract


The problem of multiprocessor scheduling can be stated as finding a schedule for a general task graph to be executed on a multiprocessor system such that the schedule length can be minimized. The last job must be completed as early as possible. Multiprocessor task scheduling is an important and computationally difficult problem. Multiprocessor computing environment requires an efficient algorithm to determine when and on which processor a given task should execute. A task can be partitioned into a group of subtasks and represented as a DAG (Directed Acyclic Graph), that problem can be stated as finding a schedule for a DAG to be executed in a parallel multiprocessor system. The problem of scheduling and mapping meta-tasks to a machine is shown to be NP-complete. The solutions of NP-complete problems are based on heuristics approach. The execution time requirements of the applications’ tasks are assumed to be stochastic. Genetic algorithm (GA) is one of the widely used techniques for constrained optimization. Performance of genetic algorithm can be improved with the introduction of some knowledge about the scheduling problem represented by the use of a min-min heuristic. In this paper the problem of same completion time and same precedence is resolved by using concept of Bottom-level (b-level). This combined approach named as improved genetic algorithm (IGA) based on min-min heuristic and b-level precedence resolution is finally compared with a pure genetic algorithm, min-min heuristic and First Come First Serve (FCFS) approach. Results of the experiments show that the improved genetic algorithm produces much better results in terms of quality of solutions.

Keywords


DAG, multiprocessor scheduling, genetic algorithm, heuristics, min-min, NP-complete.

Full Text:

PDF

References


Ishfaq Ahmad, Yu-Kwong Kwok, Min-You Wu, “Analysis, Evaluation, and Comparison of Algorithms for Scheduling Task Graphs on Parallel Processors”, Proceedings of the 1996 International Symposium on Parallel Architectures, Algorithms and Networks, Page: 207, 1996, ISBN: 0-8186-7460-1, IEEE Computer Society Washington, DC, USA.

Yu-Kwong Kwok and Ishfaq Ahmad, “Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors”, ACM Computing Surveys, vol. 31, Issue. 4, December 1999, ISSN: 0360-0300, ACM New York, NY, USA.

D. E. Goldberg, “Genetic algorithms in search, optimization & machine learning”, Addison Wesley, 1990.

Melanie Mitchell, “An Introduction to Genetic algorithms”, The MIT Press, February 1998.

Tracy D. Braunt, Howard Jay Siegel, Noah Beck, Bin Yao, Richard F. Freund, “A Comparison Study of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems”, Journal of Parallel and Distributed Computing, Volume 61, Issue 6, June 2001, Pages: 810-837, ISSN: 0743-7315, Academic Press, Inc. Orlando, FL, USA.

Ricardo C. Correa, Afonso Ferreira, Pascal Rebreyend, “Scheduling Multiprocessor Tasks With Genetic Algorithms”, IEEE Transactions on Parallel and Distributed Systems, Vol. 10, Issue. 8, August 1999, Pages: 825-837, ISSN: 1045-9219, IEEE Press Piscataway, NJ, USA.

Edwin S. H. Hou, Nirwan Ansari, Hong Ren, “A Genetic Algorithm for Multiprocessor Scheduling”, IEEE Transactions on Parallel and Distributed Systems, vol. 5, Issue. 2, February2003, Pages: 113-120, ISSN: 1045-9219, IEEE Press Piscataway, NJ, USA.

Amir Masoud Rahmani, Mohammad Ali Vahedi, “A novel Task Scheduling in Multiprocessor Systems with Genetic Algorithm by using Elitism stepping method”, Science and Research branch, Tehran, Iran, May 26, 2008.

Martin Grajcar, “Genetic List Scheduling Algorithm for Scheduling and Allocating on a Loosely Coupled Heterogeneous Multiprocessor System”, Proceedings of the 36th annual ACM/IEEE Design Automation Conference, New Orleans, Louisiana, United States, Pages: 280 – 285, 1999, ISBN: 1-58133-109-7, ACM New York, NY, USA.

Martin Grajcar, “Strengths and Weaknesses of Genetic List Scheduling for Heterogeneous Systems”, IEEE Computer Society, Proceedings of the Second International Conference on Application of Concurrency to System Design, Page: 123, ISBN: 0-7695-1071-X, IEEE Computer Society Washington, DC, USA, 2001.

Hesam Izakian, Ajith Abraham, Vaclav Snasel, “Comparison of Heuristics for scheduling Independent Tasks on Heterogeneous Distributed Environments”, Proceedings of the 2009 International Joint Conference on Computational Sciences and Optimization, Volume 01, Pages: 8-12, 2009, ISBN:978-0-7695-3605-7, IEEE Computer Society Washington, DC, USA.

Yi-Hsuan Lee and Cheng Chen, “A Modified Genetic Algorithm for Task Scheduling in Multiprocessor Systems”, Proc. of 6th International Conference Systems and Applications, pp. 382-387, 1999.

Amir Masoud Rahmani and Mojtaba Rezvani, “A Novel Genetic Algorithm for Static Task Scheduling in Distributed Systems”, International Journal of Computer Theory and Engineering, Vol. 1, No. 1, April 2009, 1793-8201.

Michael Rinehart, Vida Kianzad and Shuvra S. Bhattacharyya, “A modular Genetic Algorithm for Scheduling Task Graphs”, Technical Report UMIACS-TR-2003-66, Institute for Advanced Computer Studies University of Maryland at College Park, June 2003.

Pai-Chou Wang, W. Korfhage, “Process Scheduling with Genetic Algorithms”, Proceedings of the 7th IEEE Symposium on Parallel and Distributed Processing, Page: 638, ISBN: 0-8186-7195-5, October 2005, IEEE Computer Society Washington, DC, USA.

Prof. Sanjay R Sutar, Jyoti P. Sawant, Jyoti R. Jadhav, “Task Scheduling For Multiprocessor Systems Using Memetic Algorithms”, http://www.comp.brad.ac.uk/het-net/tutorials/P27.pdf

Andrew J. Page and Thomas J. Naughton, “Framework for Task scheduling in heterogeneous distributed computing using genetic algorithms”, 15th Artificial Intelligence and Cognitive Science Conference, 2004, Castlebar, Co. Mayo, Ireland, isbn = 1-902277-89-9 pages = 137-146.

Clayton S. Ferner and Robert G. Babb, “Automatic Choice of Scheduling Heuristics for Parallel/Distributed Computing”, IOS Press Amsterdam, The Netherlands, Volume 7, Issue 1, Pages: 47 – 65, January 1999, ISSN:1058-9244.

C.L. McCreary, A.A. Khan, J. Thompson, M.E. McArdle, “A Comparison of Heuristics for Scheduling DAGs on Multiprocessors”, Eighth International Proceedings on Parallel Processing Symposium, pages: 446-451, Location: Cancun, ISBN: 0-8186-5602-6, DOI: 10.1109/IPPS.2002.288264, 06 August 2002.

Javier Carretero, Fatos Xhafa, Ajith Abraham, “Genetic Algorithm Based Schedulers for Grid Computing Systems”, International Journal of Innovative Computing, Information and Control, ICIC International, Vol.3, No. 6, ISSN 1349-4198, pp. 1053-1071, December 2007.

Annie s. Wu, Han Yu, Shiyuan Jin, Kuo-Chi Lin, and Guy Schiavone, “An Incremental Genetic Algorithm Approach to Multiprocessor Scheduling”, IEEE Transactions on Parallel and Distributed Systems, Vol.15, No. 9, On page(s): 824 – 834, ISSN: 1045-9219, INSPEC Accession Number:8094176, Digital Object Identifier: 10.1109/TPDS.2004.38, 13 September 2004.

Michael Bohler, Frank Moore, Yi Pan, “Improved Multiprocessor Task Scheduling Using Genetic Algorithms”, Proceedings of the Twelfth International FLAIRS Conference, WPAFB, OH 45433, American Association for Artificial Intelligence, 1999.

Marin Golub, Suad Kasapovic, “Scheduling Multiprocessor Tasks with Genetic Algorithms”, OACTA Press, from proceeding (351) Applied Informatics, 2002.

M. Nikravan and M. H. Kashani, “A Genetic Algorithm for Process Scheduling in Distributed Operating Systems considering Load Balancing”, Proceedings 21st European Conference on Modelling and Simulation Ivan Zelinka, Zuzana Oplatkova, Alessandra Orsoni, ECMS 2007, ISBN 978-0-9553018-2-7, ISBN 978-0-9553018-3-4 (CD).

Shuang E Zhou, Yong Liu, Di Jiang, “A Genetic-Annealing Algorithm for Task Scheduling Based on Precedence Task Duplication”, CIT, Proceedings of the Sixth IEEE International Conference on Computer and Information Technology, Page: 117, 2006, ISBN: 0-7695-2687-X, IEEE Computer Society Washington, DC, USA.

G. Coulouris, J. Dollimore, and T. Kindberg. Distributed systems: concepts and design. Addison Wesley, Essex, England, 2005.

H. A. James. Scheduling in Metacomputing Systems. PhD thesis, University of Adelaide, Adelaide,Australia, 1999.

T. D. Braun, H. J. Siegel, N. Beck, L. B¨ol¨oni, M. Maheswaran, A. I. Reuther, J. P. Robertson, M. D. Theys, and B. Yao. A taxonomy for describing matching and scheduling heuristics for mixed-machine heterogeneous computing systems. In Reliable Distributed Systems, 1998. Proceedings. Seventeenth IEEE Symposium on, pages 330–335, West Lafayette, IN, 1998.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.