Procrastination for leakage-aware rate-monotonic scheduling on a dynamic voltage scaling processor

ABSTRACT

As the dynamic voltage scaling (DVS) technique provides system engineers the flexibility to trade-off the performance and the energy consumption, DVS has been adopted in many computing systems. However, the longer a job executes, the more energy in the leakage current the device/processor consumes for the job. To reduce the energy consumption resulting from the leakage current, a system might enter the dormant mode. This paper targets energy-efficient rate-monotonic scheduling for periodic real-time tasks on a uniprocessor DVS system with non-negligible leakage power consumption. An on-line simulated scheduling strategy and a virtually blocking time strategy are developed for procrastination scheduling to reduce energy consumption. The proposed algorithms derive a feasible schedule for real-time tasks with worst-case guarantees for any input instance. Experimental results show that our proposed algorithms could derive energy-efficient solutions.

REFERENCES

• 1: Tarek A. AlEnawy , Hakan Aydin, Energy-Constrained Scheduling for Weakly-Hard Real-Time Systems, Proceedings of the 26th IEEE International Real-Time Systems Symposium, p.376-385, December 05-08, 2005 [doi>10.1109/RTSS.2005.18]
• 2: Hakan Aydin , Rami Melhem , Daniel Mossé , Pedro Mejía-Alvarez, Determining Optimal Processor Speeds for Periodic Real-Time Tasks with Different Power Characteristics, Proceedings of the 13th Euromicro Conference on Real-Time Systems, p.225, June 13-15, 2001
• 3: 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
• 4: Philippe Baptiste, Scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.364-367, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109598]
• 5: Enrico Bini , Giorgio Buttazzo , Giuseppe Lipari, Speed Modulation in Energy-Aware Real-Time Systems, Proceedings of the 17th Euromicro Conference on Real-Time Systems (ECRTS'05), p.3-10, July 06-08, 2005 [doi>10.1109/ECRTS.2005.29]
• 6: D. Chen, A. K. Mok, and T.-W. Kuo. Utilization bound revisited. IEEE Transactions on Computers, 52(3):351--361, March 2003.
• 7: Jian-Jia Chen , Heng-Ruey Hsu , Tei-Wei Kuo, Leakage-Aware Energy-Efficient Scheduling of Real-Time Tasks in Multiprocessor Systems, Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'06), p.408-417, April 04-07, 2006 [doi>10.1109/RTAS.2006.25]
• 8: Jian-Jia Chen , Tei-Wei Kuo, Voltage Scaling Scheduling for Periodic Real-Time Tasks in Reward Maximization, Proceedings of the 26th IEEE International Real-Time Systems Symposium, p.345-355, December 05-08, 2005 [doi>10.1109/RTSS.2005.44]
• 9: J.-J. Chen, T.-W. Kuo, and H.-I. Lu. Power-saving scheduling for weakly dynamic voltage scaling devices. In Workshop on Algorithms and Data Structures (WADS), pages 338--349, 2005.
• 10: Jian-Jia Chen , Tei-Wei Kuo , Chi-Sheng Shih, 1 + ε approximation clock rate assignment for periodic real-time tasks on a voltage-scaling processor, Proceedings of the 5th ACM international conference on Embedded software, September 18-22, 2005, Jersey City, NJ, USA [doi>10.1145/1086228.1086273]
• 11: Jian-Jia Chen , Tei-Wei Kuo , Chia-Lin Yang, Profit-driven uniprocessor scheduling with energy and timing constraints, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.968072]
• 12: R. Davis , A. Wellings, Dual priority scheduling, Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS '95), p.100, December 05-07, 1995
• 13: Inki Hong , Darko Kirovski , Gang Qu , Miodrag Potkonjak , Mani B. Srivastava, Power optimization of variable voltage core-based systems, Proceedings of the 35th annual conference on Design automation, p.176-181, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277088]
• 14: Sandy Irani , Sandeep Shukla , Rajesh Gupta, Algorithms for power savings, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 15: 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]
• 16: Ravindra Jejurikar , Rajesh Gupta, Procrastination scheduling in fixed priority real-time systems, Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 11-13, 2004, Washington, DC, USA
• 17: Ravindra Jejurikar , Rajesh Gupta, Dynamic slack reclamation with procrastination scheduling in real-time embedded systems, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065612]
• 18: Ravindra Jejurikar , Rajesh Gupta, Dynamic voltage scaling for systemwide energy minimization in real-time embedded systems, Proceedings of the 2004 international symposium on Low power electronics and design, August 09-11, 2004, Newport Beach, California, USA [doi>10.1145/1013235.1013261]
• 19: Ravindra Jejurikar , Cristiano Pereira , Rajesh Gupta, Leakage aware dynamic voltage scaling for real-time embedded systems, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996650]
• 20: Woonseok Kim , Jihong Kim , Sang Lyul Min, Preemption-aware dynamic voltage scaling in hard real-time systems, Proceedings of the 2004 international symposium on Low power electronics and design, August 09-11, 2004, Newport Beach, California, USA [doi>10.1145/1013235.1013328]
• 21: Y.-H. Lee, K. P. Reddy, and C. M. Krishna. Scheduling techniques for reducing leakage power in hard real-time systems. In 15th Euromicro Conference on Real-Time Systems (ECRTS), pages 105--112, 2003.
• 22: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 23: Jane W. S. W. Liu, Real-Time Systems, Prentice Hall PTR, Upper Saddle River, NJ, 2000
• 24: Pedro Mejia-Alvarez , Eugene Levner , Daniel Mossé, Adaptive scheduling server for power-aware real-time tasks, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.2, p.284-306, May 2004 [doi>10.1145/993396.993400]
• 25: Linwei Niu , Gang Quan, Reducing both dynamic and leakage energy consumption for hard real-time systems, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023854]
• 26: Padmanabhan Pillai , Kang G. Shin, Real-time dynamic voltage scaling for low-power embedded operating systems, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 27: 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]
• 28: G. Quan , X. Hu, Minimum Energy Fixed-Priority Scheduling for Variable Voltage Processor, Proceedings of the conference on Design, automation and test in Europe, p.782, March 04-08, 2002
• 29: Gang Quan , Linwei Niu , Xiaobo Sharon Hu , Bren Mochocki, Fixed Priority Scheduling for Reducing Overall Energy on Variable Voltage Processors, Proceedings of the 25th IEEE International Real-Time Systems Symposium (RTSS'04), p.309-318, December 05-08, 2004 [doi>10.1109/REAL.2004.23]
• 30: J. M. Rabaey, A. Chandrakasan, and B. Nikolic. Digital Integrated Circuits. Prentice Hall, 2nd edition, 2002.
• 31: Cosmin Rusu , Rami Melhem , Daniel Mossé, Maximizing the System Value while Satisfying Time and Energy Constraints, Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02), p.246, December 03-05, 2002
• 32: C. Rusu, R. Melhem, and D. Mossé. Multiversion scheduling in rechargeable energy-aware real-time systems. In EuroMicro Conference on Real-Time Systems (ECRTS'03), pages 95--104, 2003.
• 33: Saowanee Saewong , Ragunathan (Raj) Rajkumar, Practical Voltage-Scaling for Fixed-Priority RT-Systems, Proceedings of the The 9th IEEE Real-Time and Embedded Technology and Applications Symposium, p.106, May 27-30, 2003
• 34: 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]
• 35: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 36: Ruibin Xu , Dakai Zhu , Cosmin Rusu , Rami Melhem , Daniel Mossé, Energy-efficient policies for embedded clusters, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 37: 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
• 38: 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]
• 39: Fan Zhang , Samuel T. Chanson, Blocking-aware processor voltage scheduling for real-time tasks, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.2, p.307-335, May 2004 [doi>10.1145/993396.993401]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

General Terms:
Algorithms

Keywords:
dynamic voltage scaling, energy-aware systems, fixed-priority scheduling, leakage-aware scheduling, rate-monotonic scheduling, scheduling