More Web Proxy on the site http://driver.im/

article

Energy-efficient CPU scheduling for multimedia applications

Authors:

Klara NahrstedtAuthors Info & Claims

ACM Transactions on Computer Systems (TOCS), Volume 24, Issue 3

Pages 292 - 331

https://doi.org/10.1145/1151690.1151693

Published: 01 August 2006 Publication History

Abstract

This article presents the design, implementation, and evaluation of EScheduler, an energy-efficient soft real-time CPU scheduler for multimedia applications running on a mobile device. EScheduler seeks to minimize the total energy consumed by the device while meeting multimedia timing requirements. To achieve this goal, EScheduler integrates dynamic voltage scaling into the traditional soft real-time CPU scheduling: It decides at what CPU speed to execute applications in addition to when to execute what applications. EScheduler makes these scheduling decisions based on the probability distribution of cycle demand of multimedia applications and obtains their demand distribution via online profiling.We have implemented EScheduler in the Linux kernel and evaluated it on a laptop with a variable-speed CPU and typical multimedia codecs. Our experimental results show four findings: first, the cycle demand distribution of our studied codecs is stable or changes slowly. This stability implies the feasibility to perform our proposed energy-efficient scheduling with low overhead. Second, EScheduler delivers soft performance guarantees to these codecs by bounding their deadline miss ratio under the application-specific performance requirements. Third, EScheduler reduces the total energy of the laptop by 14.4% to 37.2% relative to the scheduling algorithm without voltage scaling and by 2% to 10.5% relative to voltage scaling algorithms without considering the demand distribution. Finally, EScheduler saves energy by 2% to 5% by explicitly considering the discrete CPU speeds and the corresponding total power of the whole laptop, rather than assuming continuous speeds and cubic speed-power relationship.

References

[1]

Acticom. 2002. Paris (cif): A standard video sequence used for video and picture evaluation purposes. Go online to http://www.acticom.info/1472.html.]]

[2]

Adve, S. et al. 2002. The Illinois GRACE Project: Global Resource Adaptation through CoopEration. In Proceedings of the Workshop on Self-Healing, Adaptive and self-MANaged Systems (New York, NY).]]

[3]

AMD. 2001. Mobile AMD Athlon 4 processor model 6 CPGA data sheet. Go online to http://www.amd.com.]]

[4]

Anderson, J. M. et al. 1997. Continuous profiling: Where have all the cycles gone? ACM Trans. Comput. Sys. 15, 4 (Nov.), 357--390.]]

[5]

Anzinger, G. et al. 2004. High resolution POSIX timers. Go online to http://high-res-timers. sourceforge.net/.]]

[6]

Aydin, H., Melhem, R., Mosse, D., and Alvarez, P. 2001. Dynamic and aggressive scheduling techniques for power-aware real-time systems. In Proceedings of the 22nd IEEE Real-Time Systems Symposium (London, U. K.). 95--105.]]

[7]

Banachowski, S., Wu, J., and Brandt, S. 2004. Missed deadline notification in best-effort schedulers. In Proceedings of the Multimedia Computing and Networking Conference (San Jose, CA). 123--135.]]

[8]

Banga, G., Druschel, P., and Mogul, J. 1999. Resource containers: A new facility for resource management in server systems. In Proceedings of the 3rd Symposium on Operating System Design and Implementation (New Orleans, LA). 45--58.]]

[9]

Bavier, A., Montz, A., and Peterson, L. 1998. Predicting MPEG execution times. In Proceedings of the International Conference on Measurement and Modeling of Computer Systems (Madison, WI). 131--140.]]

[10]

Benini, L., Bogliolo, A., and Micheli, G. D. 2000. A survey of design techniques for system-level dynamic power management. IEEE Trans. VLSI Syst. 8, 3 (June), 299--316.]]

[11]

Brandt, S. and Nutt, G. J. 2002. Flexible soft real-time processing in middleware. Real-Time Sys. 22, 1--2.]]

[12]

Chandra, A., Adler, M., Goyal, P., and Shenoy, P. 2000. Surplus fair scheduling: A proportional-share CPU scheduling algorithm for symmetric multiprocessors. In Proceedings of the 4th Symposium on Operating System Design and Implementation (San Diego, CA). 45--58.]]

[13]

Chandrakasan, A., Sheng, S., and Brodersen, R. W. 1992. Low-power CMOS digital design. IEEE J. Solid-State Circ. 27, 473--484.]]

[14]

Chu, H. H. and Nahrstedt, K. 1999. CPU service classes for multimedia applications. In Proceedings of the IEEE International Conference on Multimedia Computing and Systems (Florence, Italy). 296--301.]]

[15]

Compaq, Intel, Microsoft, Phoenix, and Toshiba. 2000. Advanced configuration and power interface specification. Go online to http://www.teleport.com/acpi/spec.htm.]]

[16]

Corner, M., Noble, B., and Wasserman, K. 2001. Fugue: Time scales of adaptation in mobile video. In Proceedings of the SPIE Multimedia Computing and Networking Conference (San Jose, CA). 75--87.]]

[17]

Duda, K. and Cheriton, D. 1999. Borrowed-virtual-time (BVT) scheduling: Supporting latency-sensitive threads in a general purpose scheduler. In Proceedings of the 17th Symposium on Operating Systems Principles (Charleston, SC). 261--276.]]

[18]

Flautner, K. and Mudge, T. 2002. Vertigo: Automatic performance-setting for linux. In Proceedings of the 5th Symposium on Operating Systems Design and Implementation (Boston, MA). 105--116.]]

[19]

Flinn, J., de Lara, E., Satyanarayanan, M., Wallach, D., and Zwaenepoel, W. 2001. Reducing the energy usage of office applications. In Proceedings of the Middleware 2001 (Heidelberg, Germany). 252--272.]]

[20]

Flinn, J. and Satyanarayanan, M. 2004. Managing battery lifetime with energy-aware adaptation. ACM Trans. Comput. Syst. 22, 2 (May), 137--179.]]

[21]

Gardner, K. 1999. Probabilistic analysis and scheduling of critical soft real-time systems. PhD dissertation. Department of Computer Science, University of Illinois at Urbana-Champaign, Urban, IL.]]

[22]

Govil, K., Chan, E., and Wasserman, H. 1995. Comparing algorithm for dynamic speed-setting of a low-power CPU. In Proceedings of the Annual International Conference on Mobile Computing and Networking (Berkeley, CA). 13--25.]]

[23]

Goyal, P., Guo, X., and Vin, H. 1996. A hierarchical CPU scheduler for multimedia operating systems. In Proceedings of the Symposium on Operating System Design and Implementation (Seattle, WA). 120--130.]]

[24]

Gruian, F. 2001. Hard real-time scheduling for low energy using stochastic data and DVS processors. In Proceedings of the International Symposium on Low-Power Electronics and Design (Huntington Beach, CA).]]

[25]

Grunwald, D., Levis, P., Farkas, K., Morrey III, C., and Neufeld, M. 2000. Policies for dynamic clock scheduling. In Proceedings of the Symposium on Operating System Design and Implementation (San Diego, CA). 73--86.]]

[26]

Gurumurthi, S., Sivasubramaniam, A., and Kandemir, M. 2003. DRPM: Dynamic speed control for power management in server class disks. In Proceedings of the 30th Annual International Symposium on Computer Architecture (San Diego, CA).]]

[27]

Hamann, C. et al. 2001. Quality-assuring scheduling-using stochastic behavior to improve resource utilization. In Proceedings of the 22nd IEEE Real-Time Systems Symposium (London, U. K.). 119--128.]]

[28]

Intel. 2004. Pentium M Processor. Go online to http://developer.intel.com/design/mobile/datashts/261203.pdf.]]

[29]

Ishihara, T. and Yasuura, H. 1998. Voltage scheduling problem for dynamically variable voltage processors. In Proceedings of the International Symposium on Low-Power Electronics and Design (Monterey, CA).]]

[30]

Jones, M., Rosu, D., and Rosu, M. 1997. CPU reservations and time constraints: Efficient, predictable scheduling of independent activities. In Proceedings of the 16th Symposium on Operating Systems Principles (St-Malo, France). 198--211.]]

[31]

Kravets, R. and Krishnan, P. 1998. Power management techniques for mobile communication. In Proceedings of the 4th ACM International Conference on Mobile Computing and Networking (Dallas, TX).]]

[32]

Krishna, C. and Lee, Y. 2000. Voltage-clock-scaling techniques for low power in hard real-time systems. In Proceedings of the IEEE Real-Time Technology and Applications Symposium (Washington, DC). 156--165.]]

[33]

Lebeck, A. R., Fan, X., Zeng, H., and Ellis, C. S. 2000. Power aware page allocation. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems (Cambridge, MA).]]

[34]

Leslie, I. M., McAuley, D., Black, R., Roscoe, T., Barham, P. T., Evers, D., Fairbairns, R., and Hyden, E. 1996. The design and implementation of an operating system to support distributed multimedia applications. IEEE J. Select. Areas Commun. 14, 7, 1280--1297.]]

[35]

Liu, C. L. and Layland, J. W. 1973. Scheduling algorithms for multiprogramming in a hard real-time environment. J. Assoc. Comput. Mach. 20, 1 (Jan.), 46--61.]]

[36]

Lorch, J. and Smith, A. 2001. Improving dynamic voltage scaling algorithms with PACE. In Proceedings of the ACM SIGMETRICS 2001 Conference (Cambridge, MA).]]

[37]

Lorch, J. and Smith, A. 2003. Operating system modifications for task-based speed and voltage scheduling. In Proceedings of the the 1st International Conference on Mobile Systems, Applications, and Services (San Francisco, CA) 215--229.]]

[38]

Miyoshi, A., Lefurgy, C., Hensbergen, E. V., Rajamony, R., and Rajkumar, R. 2002. Critical power slope: Understanding the runtime effects of frequency scaling. In Proceedings of the 16th Annual ACM International Conference on Supercomputing (New York City, NY). 35--44.]]

[39]

Mohapatra, S., Cornea, R., Dutt, N., Nicolau, A., and Venkatasubramanian, N. 2003. Integrated power management for video streaming to mobile devices. In Proceedings of the ACM Multimedia (Berkeley, CA). 582--591.]]

[40]

Nieh, J. and Lam, M. S. 2003. A smart scheduler for multimedia applications. ACM Trans. Comput. Syst. 21, 2, 117--163.]]

[41]

Pering, T., Burd, T., and Brodersen, R. 1998. The simulation and evaluation of dynamic voltage scaling algorithms. In Proceedings of the International Symposium on Low Power Electronics and Design (Monterey, CA). 76--81.]]

[42]

Pering, T., Burd, T., and Brodersen, R. 2000. Voltage scheduling in the lpARM microprocessor system. In Proceedings of the International Symposium on Low Power Electronics and Design (Rapallo, Italy). 96--101.]]

[43]

Pillai, P. and Shin, K. G. 2001. Real-time dynamic voltage scaling for low-power embedded operating systems. In Proceedings of the 18th Symposium on Operating Systems Principles (Banff, Alta., Canada). 89--102.]]

[44]

Pisinger, D. 1995. A minimal algorithm for the multiple-choice Knapsack problem. European J. Operation. Res. 83, 394--410.]]

[45]

Rajkumar, R., Juvva, K., Molano, A., and Oikawa, S. 1998. Resource kernels: A resource-centric approach to real-time systems. In Proceedings of the SPIE Multimedia Computing and Networking Conference.]]

[46]

Sha, L., Rajkumar, R., and Lehoczky, J. 1990. Priority inheritance protocols: An approach to real-time synchroniztion. IEEE Trans. Comput. 39, 9 (Sept.), 1175--1185.]]

[47]

Simunic, T. et al. 2001. Dynamic voltage scaling and power management for portable systems. In Proceedings of the Design Automation Conference (Las Vegas, CA). 524--529.]]

[48]

Sinha, A. and Chandrakasan, A. 2001. Dynamic voltage scheduling using adaptive filtering of workload traces. In Proceedings of the 4th International Conference on VLSI Design (Bangalore, India). 221--226.]]

[49]

Urgaonkar, B., Shenoy, P., and Roscoe, T. 2002. Resource overbooking and application profiling in shared hosting platforms. In Proceedings of the 5th Symposium on Operating Systems Design and Implementation (Boston, MA). 239--254.]]

[50]

Wang, S., Xuan, D., Bettati, R., and Zhao, W. 2001. Differentiated services with statistical real-time guarantees in static-priority scheduling networks. In Proceedings of the 22nd IEEE Real-Time Systems Symposium (London, U.K.). 289--298.]]

[51]

Weiser, M., Welch, B., Demers, A., and Shenker, S. 1994. Scheduling for reduced CPU energy. In Proceedings of the Symposium on Operating Systems Design and Implementation (Monterey, CA). 13--23.]]

[52]

Xu, R., Xi, C., Melhem, R., and Mosse, D. 2004. Practical PACE for embedded systems. In Proceedings of the ACM International Conference on Embedded Software (Pisa, Italy). 54--63.]]

[53]

Yuan, W. and Nahrstedt, K. 2003. Energy-efficient soft real-time CPU scheduling for mobile multimedia systems. In Proceedings of the 19th Symposium on Operating Systems Principles (Bolton Landing, NY). 149--163.]]

[54]

Yuan, W. and Nahrstedt, K. 2004a. Practical voltage scaling for mobile multimedia devices. In Proceedings of the ACM Multimedia (New York, NY). 924--931.]]

[55]

Yuan, W. and Nahrstedt, K. 2004b. Process group management in cross-layer adaptation. In Proceedings of the Multimedia Computing and Networking Conference (San Jose, CA).]]

[56]

Yuan, W., Nahrstedt, K., Adve, S., Jones, D., and Kravets, R. 2003. Design and evaluation of a cross-layer adaptation framework for mobile multimedia systems. In Proceedings of the Multimedia Computing and Networking Conference (San Jose, CA) 1--13.]]

[57]

Yuan, W., Nahrstedt, K., Adve, S., Jones, D., and Kravets, R. 2006. GRACE-1: Cross-layer adaptation for multimedia quality and battery energy. IEEE Trans. Mobile Comput. 5, 7, 79--815.]]

[58]

Zeng, H., Fan, X., Ellis, C., Lebeck, A., and Vahdat, A. 2002. ECOSystem: Managing energy as a first class operating system resource. In Proceedings of the 10th International Conference on ASPLOS (San Jose, CA). 123--132.]]

[59]

Zhang, X., Wang, Z., Gloy, N., Chen, J., and Smith, M. 1997. System support for automated profiling and optimization. In Proceedings of the Symposium on Operating Systems Principles (Saint-Malo, France). 15--26.]]

[60]

Zhu, D., Moss, D., and Melhem, R. 2004. Power aware scheduling for AND/OR graphs in real-time systems. IEEE Trans. Parallel Distrib. Syst. 15, 9, 849--864.]]

Cited By

Zhao LZhang JHu YQian LSun X(2024)Analysis on Tail-Distribution of End-to-End Latency in MEC-Based Tactile Teleoperation Systems2024 IEEE Wireless Communications and Networking Conference (WCNC)10.1109/WCNC57260.2024.10570967(1-6)Online publication date: 21-Apr-2024
https://doi.org/10.1109/WCNC57260.2024.10570967
Zhang YGong YGuo Y(2024)Energy-Efficient Resource Management for Multi-UAV-Enabled Mobile Edge ComputingIEEE Transactions on Vehicular Technology10.1109/TVT.2024.3379298(1-11)Online publication date: 2024
https://doi.org/10.1109/TVT.2024.3379298
Giannessi RBiondi ABiasci A(2024)RT-Mimalloc: A New Look at Dynamic Memory Allocation for Real-Time Systems2024 IEEE 30th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS61025.2024.00022(173-185)Online publication date: 13-May-2024
https://doi.org/10.1109/RTAS61025.2024.00022
Show More Cited By

Index Terms

Energy-efficient CPU scheduling for multimedia applications
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Embedded systems
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Scheduling
    2. Software system structures
      1. Embedded software
      2. Real-time systems software

Recommendations

Modeling CPU energy consumption for energy efficient scheduling
GCM '10: Proceedings of the 1st Workshop on Green Computing

In the past few years, we have seen the rising popularity of multi-core systems, including the 4, 6, and 8-cores present in i7 processors from Intel, and the 8 and 12 cores present in Magny-Cours processors from AMD. There is a general trend that newer ...
Energy-efficient soft real-time CPU scheduling for mobile multimedia systems
SOSP '03

This paper presents GRACE-OS, an energy-efficient soft real-time CPU scheduler for mobile devices that primarily run multimedia applications. The major goal of GRACE-OS is to support application quality of service and save energy. To achieve this goal, ...
Energy-efficient soft real-time CPU scheduling for mobile multimedia systems
SOSP '03: Proceedings of the nineteenth ACM symposium on Operating systems principles

This paper presents GRACE-OS, an energy-efficient soft real-time CPU scheduler for mobile devices that primarily run multimedia applications. The major goal of GRACE-OS is to support application quality of service and save energy. To achieve this goal, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computer Systems

ACM Transactions on Computer Systems Volume 24, Issue 3

August 2006

121 pages

ISSN:0734-2071

EISSN:1557-7333

DOI:10.1145/1151690

Issue’s Table of Contents

Copyright © 2006 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2006

Published in TOCS Volume 24, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

103
Total Citations
View Citations
2,438
Total Downloads

Downloads (Last 12 months)73
Downloads (Last 6 weeks)6

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhao LZhang JHu YQian LSun X(2024)Analysis on Tail-Distribution of End-to-End Latency in MEC-Based Tactile Teleoperation Systems2024 IEEE Wireless Communications and Networking Conference (WCNC)10.1109/WCNC57260.2024.10570967(1-6)Online publication date: 21-Apr-2024
https://doi.org/10.1109/WCNC57260.2024.10570967
Zhang YGong YGuo Y(2024)Energy-Efficient Resource Management for Multi-UAV-Enabled Mobile Edge ComputingIEEE Transactions on Vehicular Technology10.1109/TVT.2024.3379298(1-11)Online publication date: 2024
https://doi.org/10.1109/TVT.2024.3379298
Giannessi RBiondi ABiasci A(2024)RT-Mimalloc: A New Look at Dynamic Memory Allocation for Real-Time Systems2024 IEEE 30th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS61025.2024.00022(173-185)Online publication date: 13-May-2024
https://doi.org/10.1109/RTAS61025.2024.00022
Masciari ENapolitano E(2024)The Environmental Cost of High Performance Computing System Simulation2024 32nd Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP)10.1109/PDP62718.2024.00048(289-292)Online publication date: 20-Mar-2024
https://doi.org/10.1109/PDP62718.2024.00048
Kim DJeong SKang J(2024)Energy-Efficient Secure Offloading System Designed via UAV-Mounted Intelligent Reflecting Surface for Resilience EnhancementIEEE Internet of Things Journal10.1109/JIOT.2023.333691911:3(3768-3778)Online publication date: 1-Feb-2024
https://doi.org/10.1109/JIOT.2023.3336919
Zhou MZhang MYang HYates R(2024)Age-minimal CPU SchedulingIEEE INFOCOM 2024 - IEEE Conference on Computer Communications10.1109/INFOCOM52122.2024.10621420(401-410)Online publication date: 20-May-2024
https://doi.org/10.1109/INFOCOM52122.2024.10621420
Xie MYe JZhang GNi X(2024)Deep Reinforcement Learning-based computation offloading and distributed edge service caching for Mobile Edge ComputingComputer Networks10.1016/j.comnet.2024.110564250(110564)Online publication date: Aug-2024
https://doi.org/10.1016/j.comnet.2024.110564
Ma XXu MLi QLi YZhou AWang SMa XXu MLi QLi YZhou AWang S(2024)Edge Computing Based Computation Offloading5G Edge Computing10.1007/978-981-97-0213-8_4(63-79)Online publication date: 3-Jan-2024
https://doi.org/10.1007/978-981-97-0213-8_4
Ghosh SRaha ARaghunathan V(2023)Energy-Efficient Approximate Edge Inference SystemsACM Transactions on Embedded Computing Systems10.1145/358976622:4(1-50)Online publication date: 31-Mar-2023
https://dl.acm.org/doi/10.1145/3589766
Kang YWang HKim BXie JZhang XHan Z(2023)Time Efficient Offloading Optimization in Automotive Multi-Access Edge Computing Networks Using Mean-Field GamesIEEE Transactions on Vehicular Technology10.1109/TVT.2022.322988872:5(6460-6473)Online publication date: May-2023
https://doi.org/10.1109/TVT.2022.3229888
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents