Genetic Algorithm for Task Scheduling on Distributed Heterogeneous Computing System

E. Ilavarasan; P. Thambidurai

doi:10.15866/irea.v3i4.8207

Genetic Algorithm for Task Scheduling on Distributed Heterogeneous Computing System

^(*) Corresponding author

DOI's assignment:
the author of the article can submit here a request for assignment of a DOI number to this resource!
Cost of the service: euros 10,00 (for a DOI)

Abstract

Distributed heterogeneous computing system are increasingly being employed for critical applications, such as aircraft control, industrial process control, and banking systems. Efficient application scheduling is a key issue for achieving high performance in this system. The problem is generally addressed in terms of task scheduling, where the tasks are the schedulable units of a program. The task scheduling problem has been extensively studied and a large number of scheduling heuristics have been presented in the literature. In this paper we propose a new task-scheduling algorithm namely, Genetic Algorithm for Task Scheduling (GATS) on heterogeneous computing system, which provides optimal results for applications represented by directed acyclic graph. The performance of the algorithm is illustrated by comparing the schedule length, speedup, and efficiency with existing algorithms such as CPOP, HEFT and PSGA. The comparison study based on randomly generated graphs and graphs of three real world applications such as Gaussian Elimination Algorithm, Fast Fourier Transformation, and Gauss Jordan algorithm shows that GATS algorithm substantially outperforms existing algorithms.
Copyright © 2015 Praise Worthy Prize - All rights reserved.

Keywords

Task Graph; DAG; Scheduling; Heterogeneous Computing System; Schedule Length

Full Text:

PDF

References

R.L. Graham, L.E. Lawler, J.K. Lenstra, and A.H. Kan, Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey, Annals of Discrete Mathematics, pp. 287-326, 1979.
http://dx.doi.org/10.1016/s0167-5060(08)70356-x

M.R.Gary and D.S.Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W.H.Freeman and Co., 1979.
http://dx.doi.org/10.2307/2273574

H.EI-Rewini and T.G.Lewis, Scheduling Parallel Program Tasks onto Arbitrary Target Machines, Journal of parallel and Distributed Computing, Vol .9, pp.138-153, 1990.
http://dx.doi.org/10.1016/0743-7315(90)90042-n

M.Iverson, F.Ozguner and G.Follen, Parallelizing Existing Applications in a Distributed Heterogeneous Environments, Proc. Heterogeneous Computing Workshop, pp.93-100, 1995.

Y.Kwok and I.Ahmed, Dynamic Critical-Path Scheduling: An Effective technique for Allocating task graphs to Multiprocessors, IEEE Trans. on Parallel and Distributed Systems, Vol. 7, No.5, pp.506-521, May 1996.
http://dx.doi.org/10.1109/71.503776

H. Topcuglou, S. Hariri and M.Y. Wu, Performance Effective and Low-Complexity Task Scheduling for Heterogeneous Computing, IEEE Trans. on Parallel and Distributed Systems, Vol. 13, No.3, Feb’ 2002.
http://dx.doi.org/10.1109/71.993206

A. Gerasoulis and T. Yang A Comparison of Clustering Heuristics for Scheduling Directed Acyclic Graphs onto Multiprocessors,, J. Parallel and Distributed Computing, Vol. 16, No. 4, pp. 276-291, Dec. 1992.
http://dx.doi.org/10.1016/0743-7315(92)90012-c

M. Kafil and I. Ahmed, Optimal Task Assignment in Heterogeneous Distributed Computing Systems, IEEE Concurrency, Vol. 6, No. 3, pp. 42-51, July-Sept. 1998.
http://dx.doi.org/10.1109/4434.708255

Sanjeev Basker and Prashanth C.SaiRanga, Scheduling Directed A-cyclic Task Graphs on Heterogeneous Network of Workstations to Minimize Schedule Length, Proc. ICPPW, 2003.
http://dx.doi.org/10.1109/icppw.2003.1240359

Rashmi Bajaj and D.P. Agrawal, Improving Scheduling of Tasks in a Heterogeneous Environments, IEEE Trans. on Parallel and Distributed Systems, Vol. 15, No.2, Feb’ 2004.
http://dx.doi.org/10.1109/tpds.2004.1264795

I. Ahmad and M.K. Dhodhi,, Multiprocessor Scheduling in a Genetic Paradigm, Parallel Computing, Vol. 22, pp. 395-406, 1996.
http://dx.doi.org/10.1016/0167-8191(95)00068-2

R.C. Correa, A. Ferreira, and P. Rebreyend, Scheduling Multiprocessor Tasks with Genetic Algorithms, IEEE Trans. Parallel and Distributed Systems, Vol. 10, No. 8, pp. 825-837, 1999.
http://dx.doi.org/10.1109/71.790600

M.K. Dhodhi, I. Ahmad, and I. Ahmad, A Multiprocessor Scheduling Scheme Using Problem-Space Genetic Algorithms, Proc. IEEE Int’l Conf. Evolutionary Computation, pp. 214-219, 1995.
http://dx.doi.org/10.1109/icec.1995.489147

E.S. Hou, N. Ansari, and H. Ren, A Genetic Algorithm for Multiprocessor Scheduling, IEEE Trans. Parallel and Distributed Systems, Vol. 5, No. 2, pp. 113-120, 1994.
http://dx.doi.org/10.1109/71.265940

Annie S.Wu, Han Yu, Shiyuan Jin, Kuo-Chi Lin, An Incremental Genetic Algorithm Approach to Multiprocessor Scheduling, IEEE Trans. on Parallel and Distributed Systems, Vol. 15, No.9, Sep. 2004.
http://dx.doi.org/10.1109/tpds.2004.38

M.K. Dhodhi, I.Ahmad, A. Yatama, “An Integrated Technique for Task Matching and Scheduling onto Distributed Heterogeneous Computing Systems, Journal of parallel and distributed computing, Vol. 62, pp. 1338-1361, 2002.
http://dx.doi.org/10.1006/jpdc.2002.1850

T. Tsuchiya, T. Osada, and T. Kikuno, Genetic-Based Multiprocessor Scheduling Using Task Duplication, Microprocessors and Microsystems, Vol. 22, pp. 197-207, 1998.
http://dx.doi.org/10.1016/s0141-9331(98)00079-9

A.Y. Zomaya, C. Ward, and B. Macey, Genetic Scheduling for Parallel Processor Systems: Comparative Studies and Performance Issues, IEEE Trans. Parallel and Distributed Systems, Vol. 10, no. 8, pp. 795-812, 1999.
http://dx.doi.org/10.1109/71.790598

Refbacks

There are currently no refbacks.

Username
Password
Remember me