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

article

Maximizing rewards for real-time applications with energy constraints

Authors:

Daniel MosséAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 2, Issue 4

Pages 537 - 559

https://doi.org/10.1145/950162.950166

Published: 01 November 2003 Publication History

Abstract

New technologies have brought about a proliferation of embedded systems, which vary from control systems to sensor networks to personal digital assistants. Many of the portable embedded devices run several applications, which typically have three constraints that need to be addressed: energy, deadline, and reward. However, many of these portable devices do not have powerful enough CPUs and batteries to run all applications within their deadlines. An optimal scheme would allow the device to run the most applications, each using the most amount of CPU cycles possible, without depleting the energy source while still meeting all deadlines. In this paper we propose a solution to this problem; to our knowledge, this is the first solution that combines the three constraints mentioned above. We devise two algorithms, an optimal algorithm for homogeneous applications (with respect to power consumption) and a heuristic iterative algorithm that can also accommodate heterogeneous applications (i.e., those with different power consumption functions). We show by simulation that our iterative algorithm is fast and within 1% of the optimal.

References

[1]

Aydin, H., Melhem, R., Mossé, D., and Alvarez, P. 2001a. Determining optimal processor speeds for periodic real-time tasks with different power characteristics. In Proceedings of the 13th Euromicro Conference on Real-Time Systems (ECRTS), Delft, Netherlands.

[2]

Aydin, H., Melhem, R., Mossé, D., and Alvarez, P. M. 2001b. Dynamic and aggressive scheduling techniques for power-aware real-time systems. In Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS'01), London, UK.

[3]

Aydin, H., Melhem, R., Mossé, D., and Alvarez, P. M. 2001c. Optimal reward-based scheduling for periodic real-time tasks. IEEE Transactions on Computers 50, 2 (Feb.), 111--130.

[4]

Chang, E. and Zakhor, A. 1993. Scalable video coding using 3D subband velocity coding and multi-rate quantization. IEEE Int. Conference On Acoustics, Speech and Signal Processing.

[5]

Chung, J.-Y., Liu, J. W.-S., and Lin, K.-J. 1993. Scheduling periodic jobs that allow imprecise results. IEEE Transactions on Computers 19, 9 (Sept.), 1156--1173.

[6]

Clark, R. K., Jensen, E. D., and Reynolds, F. D. 1992. Architectural overview of the alpha real-time distributed kernel. USENIX Workshop on MicroKernels and Other Kernel Architectures.

[7]

Dey, J. K., Kurose, J., and Towsley, D. 1996. On-line scheduling policies for a class of IRIS (increasing reward with increasing service) real-time tasks. IEEE Transactions on Computers 45, 7 (July), 802--813.

[8]

Dey, J. K., Kurose, J., Towsley, D., Krishna, C. M., and Girkar, M. 1993. Efficient online processor scheduling for a class of iris (increasing reward with increasing service) real-time tasks. In Proceedings of ACM SIGMETRICS Conference on Measurement an Modeling of Computer Systems, 217--228.

[9]

Ernst, R. and Ye, W. 1997. Embedded program timing analysis based on path clustering and architecture classification. In Computer-Aided Design(ICCAD), 598--604.

[10]

Feng, W. and Liu, J. W.-S. 1993. An extended imprecise computation model for time-constrained speech processing and generation. In Proceedings of the IEEE Workshop on Real-Time Applications.

[11]

Grass, J. and Zilberstein, S. 2000. A value-driven system for autonomous information gathering. Journal of Intelligent Information Systems 14, (Mar.), 5--27.

[12]

Gruian, F. 2001. Hard real-time scheduling using stochastic data and dvs processors. In Proceedings of International Symposium on Low Power Electronics and Design, 46--51.

[13]

Hong, I., Kirovski, D., Qu, G., Potkonjak, M., and Srivastava, M. 1998a. Power optimization of variable voltage core-based systems. In Proceedings of the 35th Design Automation Conference (DAC).

[14]

Hong, I., Potkonjak, M., and Srivastava, M. 1998b. On-line scheduling of hard real-time tasks on variable voltage processors. In Computer-Aided Design (ICCAD), 653--656.

[15]

Hong, I., Qu, G., Potkonjak, M., and Srivastava, M. 1998c. Synthesis techniques for low-power hard real-time systems on variable voltage processors. In Proceedings of the 19th IEEE Real-Time Systems Symposium (RTSS'98), Madrid.

[16]

Joseph, R. and Martonosi, M. 2001. Run-time power estimation in high-performance microprocessors. In The International Symposium on Low Power Electronics and Design (ISLPED).

[17]

Krishna, C. M. and Lee, Y. H. 2000. Voltage clock scaling adaptive scheduling techniques for low power in hard real-time systems. In Proceedings of the 6th IEEE Real-Time Technology and Applications Symposium (RTAS), Washington DC.

[18]

Krishna, C. M. and Shin, K. G. 1997. Real-Time Systems. McGraw-Hill, New-York.

[19]

Kumar, P. and Srivastava, M. 2001. Power-aware multimedia systems using run-time prediction. In Proceedings of the 14th International Conference on VLSI Design (VLSID), Bangalore, India.

[20]

Liu, C. L. and Layland, J. W. 1973. Scheduling algorithms for multiprogramming in hard real-time environment. Journal of ACM 20, 1 (Mar.), 46--61.

[21]

Liu, J. W.-S., Lin, K.-J., Shih, W.-K., Yu, A. C.-S., Chung, C., Yao, J., and Zhao, W. 1991. Algorithms for scheduling imprecise computations. IEEE Computer 24, 5 (May), 58--68.

[22]

Lorch, J. R. and Smith, A. J. 2001. Improving dynamic voltage scaling algorithms with pace. In Proceedings of the ACM SIGMETRICS 2001 Conference, Cambridge, MA.

[23]

Luenberger, D. 1984. Linear and Nonlinear Programming. Addison-Wesley, Reading MA.

[24]

Mossé, D., Aydin, H., Childers, B., and Melhem, R. 2000. Compiler-assisted dynamic power-aware scheduling for real-time applications. In Workshop on Compilers and Operating Systems for Low Power (COLP), Philadelphia, PA.

[25]

Rajkumar, R., Lee, C., Lehoczky, J. P., and Siewiorek, D. P. 1997. A resource allocation model for QoS management. In Proceedings of the 18th IEEE Real-Time Systems Symposium (RTSS'97).

[26]

Rajkumar, R., Lee, C., Lehoczky, J. P., and Siewiorek, D. P. 1998. Practical solutions for QoS-based resource allocation problems. In Proceedings of the 19th IEEE Real-Time Systems Symposium (RTSS'98).

[27]

Rusu, C., Melhem, R., and Mossé, D. 2002. Maximizing the system value while satisfying time and energy constraints. In Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02), Austin, TX.

[28]

Shih, W.-K., Liu, J. W.-S., and Chung, J.-Y. 1991. Algorithms for scheduling imprecise computations with timing constraints. SIAM Journal on Computing 20, 3, 537--552.

[29]

Shin, D., Kim, J., and Lee, S. 2001. Intra-task voltage scheduling for low-energy hard real-time applications. IEEE Design and Test of Computers 18, 3 (Mar.), 20--30.

[30]

Shin, Y. and Choi, K. 1999. Power conscious fixed priority scheduling for hard real-time systems. In Proceedings of the 36th Design Automation Conference (DAC).

[31]

Turner, C. J. and Peterson, L. L. 1992. Image transfer: An end-to-end design. In SIGCOMM Symposium on Communications Architectures and Protocols.

[32]

Vrbsky, S. V. and Liu, J. W. S. 1993. Approximate---A query processor that produces monotonically improving approximate answers. IEEE Transactions on Knowledge and Data Engineering 5, 12 (Dec.), 1056--1068.

[33]

Yao, F., Demers, A., and Shankar, S. 1995. A scheduling model for reduced cpu energy. IEEE Annual Foundations of Computer Science, 374--382.

Cited By

Hu BCao ZZhou M(2022)Energy-minimized Scheduling of Real-time Parallel Workflows on Heterogeneous Distributed Computing SystemsIEEE Transactions on Services Computing10.1109/TSC.2021.305475415:5(2766-2779)Online publication date: 1-Sep-2022
https://doi.org/10.1109/TSC.2021.3054754
Yu HHa YVeeravalli BChen FEl-Sayed H(2021)DVFS-Based Quality Maximization for Adaptive Applications With Diminishing ReturnIEEE Transactions on Computers10.1109/TC.2020.299724270:5(803-816)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1109/TC.2020.2997242
Huang KJing MJiang XChen SLi XTao WXiong DLiu Z(2020)Task-Level Aware Scheduling of Energy-Constrained Applications on Heterogeneous Multi-Core SystemElectronics10.3390/electronics91220779:12(2077)Online publication date: 5-Dec-2020
https://doi.org/10.3390/electronics9122077
Show More Cited By

Index Terms

Maximizing rewards for real-time applications with energy constraints
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

Minimizing expected energy consumption in real-time systems through dynamic voltage scaling

Many real-time systems, such as battery-operated embedded devices, are energy constrained. A common problem for these systems is how to reduce energy consumption in the system as much as possible while still meeting the deadlines; a commonly used power ...
An experimental evaluation of real-time DVFS scheduling algorithms
SYSTOR '12: Proceedings of the 5th Annual International Systems and Storage Conference

We implement and experimentally evaluate the timeliness and energy consumption behaviors of fourteen Real-Time Dynamic Voltage and Frequency Scaling (RT-DVFS) schedulers on two hardware platforms. The schedulers include CC-EDF, LA-EDF, REUA, DRA, and ...
Software architecture supporting integrated real-time systems

To achieve reliability, reusability, and cost reduction, a significant trend in building large complex real-time systems is to integrate separate application modules of different criticalities in a common hardware platform. An essential requirement of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems

ACM Transactions on Embedded Computing Systems Volume 2, Issue 4

November 2003

165 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/950162

Issue’s Table of Contents

Copyright © 2003 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 November 2003

Published in TECS Volume 2, Issue 4

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

69
Total Citations
View Citations
976
Total Downloads

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

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hu BCao ZZhou M(2022)Energy-minimized Scheduling of Real-time Parallel Workflows on Heterogeneous Distributed Computing SystemsIEEE Transactions on Services Computing10.1109/TSC.2021.305475415:5(2766-2779)Online publication date: 1-Sep-2022
https://doi.org/10.1109/TSC.2021.3054754
Yu HHa YVeeravalli BChen FEl-Sayed H(2021)DVFS-Based Quality Maximization for Adaptive Applications With Diminishing ReturnIEEE Transactions on Computers10.1109/TC.2020.299724270:5(803-816)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1109/TC.2020.2997242
Huang KJing MJiang XChen SLi XTao WXiong DLiu Z(2020)Task-Level Aware Scheduling of Energy-Constrained Applications on Heterogeneous Multi-Core SystemElectronics10.3390/electronics91220779:12(2077)Online publication date: 5-Dec-2020
https://doi.org/10.3390/electronics9122077
Chen FYu HHa Y(2020)Quality Estimation and Optimization of Adaptive Stereo Matching Algorithms for Smart VehiclesACM Transactions on Embedded Computing Systems10.1145/337278419:2(1-24)Online publication date: 10-Feb-2020
https://dl.acm.org/doi/10.1145/3372784
Quan ZWang ZYe TGuo S(2020)Task Scheduling for Energy Consumption Constrained Parallel Applications on Heterogeneous Computing SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2019.295953331:5(1165-1182)Online publication date: 1-May-2020
https://doi.org/10.1109/TPDS.2019.2959533
Esmaili ANazemi MPedram M(2019)Energy-aware Scheduling of Task Graphs with Imprecise Computations and End-to-end DeadlinesACM Transactions on Design Automation of Electronic Systems10.1145/336599925:1(1-21)Online publication date: 26-Nov-2019
https://dl.acm.org/doi/10.1145/3365999
Mo LKritikakou ASentieys O(2018)Controllable QoS for Imprecise Computation Tasks on DVFS Multicores With Time and Energy ConstraintsIEEE Journal on Emerging and Selected Topics in Circuits and Systems10.1109/JETCAS.2018.28520058:4(708-721)Online publication date: Dec-2018
https://doi.org/10.1109/JETCAS.2018.2852005
Li K(2018)Experimental study of energy and time constrained task scheduling with irregular speed and power levelsSustainable Computing: Informatics and Systems10.1016/j.suscom.2018.07.00619(61-71)Online publication date: Sep-2018
https://doi.org/10.1016/j.suscom.2018.07.006
Poursafaei FBazzaz MKafshdooz MEjlali A(2018)Slack clustering for scheduling frame-based tasks on multicore embedded systemsMicroelectronics Journal10.1016/j.mejo.2018.09.00281(144-153)Online publication date: Nov-2018
https://doi.org/10.1016/j.mejo.2018.09.002
Li K(2018)Scheduling parallel tasks with energy and time constraints on multiple manycore processors in a cloud computing environmentFuture Generation Computer Systems10.1016/j.future.2017.01.01082(591-605)Online publication date: May-2018
https://doi.org/10.1016/j.future.2017.01.010
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