Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper presents a hybrid technique that combines List Scheduling (LS) with Genetic Algorithms (GA) for constructing non-preemptive schedules for soft real-time parallel applications represented as directed acyclic graphs (DAGs). The execution time requirements of the applications' tasks are assumed to be stochastic and are represented as probability distribution functions. The performance in terms of schedule lengths for three different genetic representation schemes are evaluated and compared for a number of different DAGs.The approaches presented here produce shorter schedules than HLFET, a popular LS approach for all of the sample problems. Of the three genetic representation schemes investigated, PosCT, the technique that allows the GA to learn which tasks to delay in order to allow other tasks to complete produced the shortest schedules for a majority of the sample DAGs.

REFERENCES

• 1: Abeni, L., and Buttazzo, G. QoS Guarantee Using Probabilistic Deadlines. In Proceedings of the IEEE Euromicro Conference on Real-Time Systems. 1999, 242--249.
• 2: Thomas L. Adam , K. M. Chandy , J. R. Dickson, A comparison of list schedules for parallel processing systems, Communications of the ACM, v.17 n.12, p.685-690, Dec 1974 [doi>10.1145/361604.361619]
• 3: 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, p.207, June 12-14, 1996
• 4: A. Atlas , A. Bestavros, Statistical Rate Monotonic Scheduling, Proceedings of the IEEE Real-Time Systems Symposium, p.123, December 02-04, 1998
• 5: Coffman, E. G. Computer and Job-Shop Scheduling Theory, John Wiley and Sons, New York, 1976.
• 6: Dandass, Y. S. A Genetic Algorithm for Scheduling Acyclic Digraph in the presence of Communication Contention. In Proceedings of the 17th Annual International Symposium on High Performance Computing Systems and Applications. 2003, 223--230.
• 7: Dandass, Y. S. Genetic List Scheduling for Soft Real-Time Parallel Applications. IEEE Congress on Evolutionary Computation. June 2004, 1164--1171.
• 8: Davis, L. Applying Adaptive Algorithms to Epistatic Domains. In Proceedings of the 9th International Joint Conference on Artificial Intelligence. 1985, 162--164.
• 9: Stochastic Scheduling of a Meta-task in Heterogeneous Distributed Computing, Proceedings of the 2001 International Conference on Parallel Processing Workshops, p.369, September 03-07, 2001
• 10: Mark K. Gardner , Jane W. Liu, Probabilistic analysis and scheduling of critical soft real-time systems, 1999
• 11: Gerasoulis, A., and Yang, T. A Comparison of Clustering Heuristics for Scheduling DAGs on Multiprocessors. Journal of Parallel and Distributed Computing, Vol. 16, No. 4. 1992, 276--291.
• 12: Gordon, V. S., and Whitley, D. Serial and Parallel Genetic Algorithms as Function Optimizers. Technical Report CS-93-114, Colorado State University, 1993.
• 13: Martin Grajcar, Strength and Weaknesses of Genetic List Scheduling for Heterogeneous Systems, Proceedings of the Second International Conference on Application of Concurrency to System Design, p.123, June 25-29, 2001
• 14: Jing-Jang Hwang , Yuan-Chieh Chow , Frank D. Anger , Chung-Yee Lee, Scheduling precedence graphs in systems with interprocessor communication times, SIAM Journal on Computing, v.18 n.2, p.244-257, April 1989 [doi>10.1137/0218016]
• 15: Yu-Kwong Kwok , Ishfaq Ahmad, Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.7 n.5, p.506-521, May 1996 [doi>10.1109/71.503776]
• 16: Yu-Kwong Kwok , Ishfaq Ahmad, Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm, Journal of Parallel and Distributed Computing, v.47 n.1, p.58-77, Nov. 25, 1997 [doi>10.1006/jpdc.1997.1395]
• 17: Jane W. S. W. Liu, Real-Time Systems, Prentice Hall PTR, Upper Saddle River, NJ, 2000
• 18: T.-S. Tia , Z. Deng , M. Shankar , M. Storch , J. Sun , L.-C. Wu , J. W.-S. Liu, Probabilistic performance guarantee for real-time tasks with varying computation times, Proceedings of the Real-Time Technology and Applications Symposium, p.164, May 15-17, 1995
• 19: M. Y. Wu , D. D. Gajski, Hypertool: A Programming Aid for Message-Passing Systems, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.330-343, July 1990 [doi>10.1109/71.80160]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Algorithms, Design, Performance

Keywords:
genetic algorithms, genetic list scheduling, soft real-time scheduling