Abstract
Procrastination scheduling has gained importance for energy efficiency due to the rapid increase in the leakage power consumption. Under procrastination scheduling, task executions are delayed to extend processor shutdown intervals, thereby reducing the idle energy consumption. We propose algorithms to compute the maximum procrastination intervals for tasks scheduled by either the fixed priority or the dual priority scheduling policy. We show that dual priority scheduling always guarantees longer shutdown intervals than fixed priority scheduling. We further combine procrastination scheduling with dynamic voltage scaling to minimize the total static and dynamic energy consumption of the system. Our simulation experiments show that the proposed algorithms can extend the sleep intervals up to 5 times while meeting the timing requirements. The results show up to 18% energy gains over dynamic voltage scaling.
- Berkeley Predictive Technology Models and BSIM4 http://www-device.eeecs.berkeley.edu/research.html.Google Scholar
- T. A. AlEnawy and H. Aydin. Energy-constrained performance optimizations for real-time operating systems. In Workshop on Compilers and Operating System for Low Power, Sept. 2003.Google Scholar
- H. Aydin, R. Melhem, D. Mossé, and P. M. Alvarez. Dynamic and aggressive scheduling techniques for power-aware real-time systems. In Proceedings of IEEE Real-Time Systems Symposium, Dec. 2001. Google ScholarDigital Library
- S. Borkar. Design challenges of technology scaling. In IEEE Micro, pages 23--29, Aug 1999. Google ScholarDigital Library
- B. H. Calhoun, F. A. Honore, and A. Chandrakasan. Design methodology for fine-grained leakage control in mtcmos. In Proceedings of International Symposium on Low Power Electronics and Design, pages 104--109, Aug. 2003. Google ScholarDigital Library
- R. Davis and A. Wellings. Dual priority scheduling. In Proceedings of IEEE Real-Time Systems Symposium, pages 100--109, Dec. 1995. Google ScholarDigital Library
- X. Fan, C. Ellis, and A. Lebeck. The synergy between power-aware memory systems and processor voltage. In Workshop on Power-Aware Computing Systems, Dec. 2003. Google ScholarDigital Library
- F. Gruian. Hard real-time scheduling for low-energy using stochastic data and dvs processors. In Proceedings of International Symposium on Low Power Electronics and Design, pages 46--51, Aug. 2001. Google ScholarDigital Library
- IBM 405LP Processor. IBM Inc. (http://www-3.ibm.com/chips/products/powerpc/cores.Google Scholar
- Intel PXA250/PXA210 Processor. Intel Inc. (http://www.intel.com).Google Scholar
- Intel XScale Processor. Intel Inc. (http://developer.intel.com/design/intelxscale).Google Scholar
- S. Irani, S. Shukla, and R. Gupta. Algorithms for power savings. In Proceedings of Symposium on Discrete Algorithms, Jan. 2003. Google ScholarDigital Library
- R. Jejurikar and R. Gupta. Dual mode algorithm for energy aware fixed priority scheduling with task synchronization. In Workshop on Compilers and Operating System for Low Power, Sept. 2003.Google Scholar
- R. Jejurikar, C. Pereira, and R. Gupta. Leakage aware dynamic voltage scaling for real-time embedded systems. In Proceedings of the Design Automation Conference, Jun 2004. Google ScholarDigital Library
- M. Johnson, D. Somasekhar, and K. Roy. Models and algorithms for bounds on leakage in cmos circuits. In IEEE Transactions on CAD, pages 714--725, 1999. Google ScholarDigital Library
- W. Kim, J. Kim, and S. L. Min. A dynamic voltage scaling algorithm for dynamic-priority hard real-time systems using slack time analysis. In Proceedings of Design Automation and Test in Europe, Mar. 2002. Google ScholarDigital Library
- W. Kwon and T. Kim. Optimal voltage allocation techniques for dynamically variable voltage processors. In Proceedings of the Design Automation Conference, pages 125--130, 2003. Google ScholarDigital Library
- N. K. J. L. Yan, J. Luo. Combined dynamic voltage scaling and adaptive body biasing for heterogeneous distributed real-time embedded systems. In Proceedings of International Conference on Computer Aided Design, Nov. 2003. Google ScholarDigital Library
- H. G. Lee and N. Chang. Energy-aware memory allocation in heterogeneous non-volatile memory systems. In Proceedings of International Symposium on Low Power Electronics and Design, pages 420--423, Aug. 2003. Google ScholarDigital Library
- Y. Lee, K. P. Reddy, and C. M. Krishna. Scheduling techniques for reducing leakage power in hard real-time systems. In EcuroMicro Conf. on Real Time Systems, 2003.Google Scholar
- J. W. S. Liu. Real-Time Systems. Prentice-Hall, 2000. Google ScholarDigital Library
- C. Locke, D. Vogel, and T. Mesler. Building a predictable avionics platform in ada: a case study. In Proceedings IEEE Real-Time Systems Symposium, 1991.Google ScholarCross Ref
- S. Martin, K. Flautner, T. Mudge, and D. Blaauw. Combined dynamic voltage scaling and adaptive body biasing for lower power microprocessors under dynamic workloads. In Proceedings of International Conference on Computer Aided Design, Nov. 2002. Google ScholarDigital Library
- P. Mejia-Alvarez, E. Levner, and D. Mosse. Adaptive scheduling server for power-aware real-time tasks. ACM Transactions on Embedded Computing Systems, 2(4), Nov. 2003. Google ScholarDigital Library
- A. Miyoshi, C. Lefurgy, E. V. Hensbergen, R. Rajamony, and R. Rajkumar. Critical power slope: Understanding the runtime effects of frequency scaling. In Proceedings of International Conference on Supercomputing, Jun. 2002. Google ScholarDigital Library
- S. Mutoh, T. Douseki, Y. Matsuya, T. Aoki, S. Shigematsu, and J. Yamada. 1-v power supply highspeed digital circuit technology with multithreshold- voltage cmos. In IEEE Journal of Solid- State Circuits, pages 847--854, 1995.Google Scholar
- C. Neau and K. Roy. Optimal body bias selection for leakage improvement and process compensation over different technology generations. In Proceedings of International Symposium on Low Power Electronics and Design, Aug. 2003. Google ScholarDigital Library
- P. Pillai and K. G. Shin. Real-time dynamic voltage scaling for low-power embedded operating systems. In Proceedings of 18th Symposium on Operating Systems Principles, 2001. Google ScholarDigital Library
- J. Pouwelse, K. Langendoen, and H. Sips. Energy priority scheduling for variable voltage processors. In Proceedings of the 2001 International Symposium on Low Power Electronics and Design, pages 28--33, 2001. Google ScholarDigital Library
- G. Quan and X. Hu. Minimum energy fixed-priority scheduling for variable voltage processors. In Proceedings of Design Automation and Test in Europe, Mar. 2002. Google ScholarDigital Library
- C. Rusu, R. Melhem, and D. Mosse. Multi-version scheduling in rechargeable energy-aware real-time systems. In Proceedings of EuroMicro Conference on Real-Time Systems, 2003.Google Scholar
- C. Rusu, R. Melhem, and D. Mosse. Maximizing rewards for real-time applications with energy constraints. In ACM Transactions on Embedded Computer Systems, accepted. Google ScholarDigital Library
- C. Rusu, R. Melhem, and D. Mosse. Maximizing the system value while satisfying time and energy constraints. In Proceedings of IEEE Real-Time Systems Symposium, Dec. 2002. Google ScholarDigital Library
- Y. Shin, K. Choi, and T. Sakurai. Power optimization of real-time embedded systems on variable speed processors. In Proceedings of International Conference on Computer Aided Design, pages 365--368, Nov. 2000. Google ScholarDigital Library
- Transmeta Crusoe Processor. Transmeta Inc. (http://www.transmeta.com/technology).Google Scholar
- F. Yao, A. J. Demers, and S. Shenker. A scheduling model for reduced CPU energy. In Proceedings of IEEE Symposium on Foundations of Computer Science, pages 374--382, 1995. Google ScholarDigital Library
- H. Yun and J. Kim. On energy-optimal voltage scheduling for fixed-priority hard real-time systems. Trans. on Embedded Computing Sys., 2(3):393--430, 2003. Google ScholarDigital Library
- F. Zhang and S. T. Chanson. Processor voltage scheduling for real-time tasks with non-preemptible sections. In Proceedings of IEEE Real-Time Systems Symposium, Dec. 2002. Google ScholarDigital Library
Index Terms
- Procrastination scheduling in fixed priority real-time systems
Recommendations
Dynamic slack reclamation with procrastination scheduling in real-time embedded systems
DAC '05: Proceedings of the 42nd annual Design Automation ConferenceLeakage energy consumption is an increasing concern in current and future CMOS technology generations. Procrastination scheduling, where task execution can be delayed to maximize the duration of idle intervals, has been proposed to minimize leakage ...
Leakage aware dynamic voltage scaling for real-time embedded systems
DAC '04: Proceedings of the 41st annual Design Automation ConferenceA five-fold increase in leakage current is predicted with each technology generation. While Dynamic Voltage Scaling (DVS) is known to reduce dynamic power consumption, it also causes increased leakage energy drain by lengthening the interval over which ...
Procrastination scheduling in fixed priority real-time systems
LCTES '04: Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systemsProcrastination scheduling has gained importance for energy efficiency due to the rapid increase in the leakage power consumption. Under procrastination scheduling, task executions are delayed to extend processor shutdown intervals, thereby reducing the ...
Comments