Feedback scheduling of real-time divisible loads in clusters

Abstract

Quality of Service (QoS) provisioning for divisible loads in clusters can be enabled using real-time scheduling theory, but is based on an important assumption: that the scheduler knows the execution time of every task in the workload. Information from production clusters, however, shows that estimated execution times of tasks are often inaccurate. Most of the work on scheduling divisible loads on clusters is based on this information, and therefore maybe of limited use when applied in practice. In this paper, we present our ongoing work to develop an EDF (earliest deadline first) scheduling algorithm with a feedback mechanism that is able to solve this problem. The objective of the new algorithm is to provide QoS provisioning of divisible loads when estimated execution times of tasks are inaccurate.

References

1. M. Drozdowski. Estimating execution time of distributed applications. In Proceedings of the Parallel Processing and Applied Mathematics : 4th International Conference, PPAM 2001 Naleczow, Poland, September 9-12, 2001. Revised Paper , pages 593-596. Springer Berlin / Heidelberg, 2002.
2. X. Lin, Y. Lu, J. Deogun, and S. Goddard. Real-time divisible load scheduling with different processor available times. In Proceedings of the 2007 International Conference on Parallel Processing (ICPP 2007).
3. X. Lin, Y. Lu, J. Deogun, and S. Goddard. Enhanced real-time divisible load scheduling with different processor available times. In 14th International Conference on High Performance Computing, December 2007.
4. X. Lin, Y. Lu, J. Deogun, and S. Goddard. Real-time divisible load scheduling for cluster computing. In Proceedings of the 13th IEEE Real-Time and Embedded Technology and Application Symposium, pages 303-314, Bellevue, WA, April 2007.
5. D. Swanson. Personal communication. Director, UNL Research Computing Facility (RCF) and UNL CMS Tier-2 Site, August 2005.
6. R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. Whalley, G. Bernat, C. Ferdinand, R. Heckman, T. Mitra, F. Mueller, I. Puaut, P. Puschner, J. Staschulat, and P. Stenstrom. The worst-case execution time problem - overview of methods and survey of tools. In ACM Transactions on Embedded Computing Systems (Accepted January 2007).
7. C.-T. Yang, P.-C. Shih, C.-F. Lin, C.-H. Hsu, and K.-C. Li. A chronological history-based execution time estimation model for embarrassingly parallel applications on grids. In Proceedings of the Parallel and Distributed Processing and Applications , pages 425-430. Springer Berlin / Heidelberg, 2005.

Index Terms

• Computer systems organization

  • Embedded and cyber-physical systems

    • Embedded systems

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Operational analysis

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Process management

          • Scheduling

    • Software system structures

      • Embedded software

      • Real-time systems software

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Scheduling algorithms

    • Online algorithms

      • Online learning algorithms

        • Scheduling algorithms

  • Theory and algorithms for application domains

    • Machine learning theory

      • Reinforcement learning

        • Sequential decision making