Shortest-path algorithms for real-time scheduling of FIFO tasks with minimal energy use

ABSTRACT

We present an algorithm for scheduling a set of nonrecurrent tasks (or jobs) with FIFO real-time constraints so as to minimize the total energy consumed when the tasks are performed on a dynamically variable voltage processor. Our algorithm runs in linear time and thus, in this case, is an improvement over the classical algorithm of Yao et al. It was inspired by considering the problem as a shortest-path problem. We also propose an algorithm to deal with the case where the processor has only a limited number of clock frequencies. This algorithm gives the optimum schedule with the minimum number of speed changes, which is important when the speed switching overhead cannot be neglected. All our algorithms are linear in the number of tasks if the arrivals and deadlines are sorted and otherwise need O(N log N) time. These complexities are shown to be the best possible. Finally, we extend our results to fluid tasks and to nonconvex cost functions.

REFERENCES

• 1: Hakan Aydi , Pedro Mejía-Alvarez , Daniel Mossé , Rami Melhem, Dynamic and Aggressive Scheduling Techniques for Power-Aware Real-Time Systems, Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS'01), p.95, December 03-06, 2001
• 2: Boissonnat, J. and Yvinec, M. 1995. Géométrie Algorithmique. Ediscience International.
• 3: Es Salhiene, M., Fesquet, L., and Renaudin, M. 2003. Adaptation dynamique de la puissance des systèmes embarqués: les systèmes asynchrones surclassent les systèmes synchrones. In journées d'études Faible Tension---Faible Consommation (FTFC'03). 51--58.
• 4: Gruian, F. 2001. On energy reduction in hard real-time systems containing tasks with stochastic execution times. In IEEE Workshop on Power Management for Real-Time and Embedded Systems. 11--16.
• 5: Gruian, F. 2002. Energy-centric scheduling for real-time systems. Ph.D. thesis, Lund Institute of Technology, Sweden.
• 6: Inki Hong , Miodrag Potkonjak , Mani B. Srivastava, On-line scheduling of hard real-time tasks on variable voltage processor, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.653-656, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289105]
• 7: Tohru Ishihara , Hiroto Yasuura, Voltage scheduling problem for dynamically variable voltage processors, Proceedings of the 1998 international symposium on Low power electronics and design, p.197-202, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280894]
• 8: Jackson, J. 1955. Scheduling a production line to minimize maximum tardiness. Tech. Rept., University of California. Report 43.
• 9: Jacob R. Lorch , Alan Jay Smith, Improving dynamic voltage scaling algorithms with PACE, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.50-61, June 2001, Cambridge, Massachusetts, United States
• 10: Mossè, D., Aydin, H., Childers, B., and Melhem, R. 2000. Compiler-assisted dynamic power-aware scheduling for real-time applications. In Workshop on Compiler and Operating Systems for Low-Power.
• 11: Gang Quan , Xiaobo Hu, Energy efficient fixed-priority scheduling for real-time systems on variable voltage processors, Proceedings of the 38th conference on Design automation, p.828-833, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379074]
• 12: Dongkun Shin , Jihong Kim , Seongsoo Lee, Intra-Task Voltage Scheduling for Low-Energy, Hard Real-Time Applications, IEEE Design & Test, v.18 n.2, p.20-30, March 2001 [doi>10.1109/54.914596]
• 13: Youngsoo Shin , Kiyoung Choi, Power conscious fixed priority scheduling for hard real-time systems, Proceedings of the 36th ACM/IEEE conference on Design automation, p.134-139, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309901]
• 14: John A. Stankovic , Krithi Ramamritham , Marco Spuri, Deadline Scheduling for Real-Time Systems: Edf and Related Algorithms, Kluwer Academic Publishers, Norwell, MA, 1998
• 15: Yao, F. 2003. Complexity of the Yao Demers Shenker algorithm. Private communication.
• 16: F. Yao , A. Demers , S. Shenker, A scheduling model for reduced CPU energy, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.374, October 23-25, 1995
• 17: Han-Saem Yun , Jihong Kim, On energy-optimal voltage scheduling for fixed-priority hard real-time systems, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.3, p.393-430, August 2003 [doi>10.1145/860176.860183]
• 18: Fan Zhang , Samuel T. Chanson, Processor Voltage Scheduling for Real-Time Tasks with Non-Preemptible Sections, Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02), p.235, December 03-05, 2002

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Performance

Keywords:
Real-time systems, low-power design, scheduling, voltage scaling