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

article

Adaptive scheduling server for power-aware real-time tasks

Authors:

Pedro Mejia-Alvarez,

Daniel MosséAuthors Info & Claims

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

Pages 284 - 306

https://doi.org/10.1145/993396.993400

Published: 01 May 2004 Publication History

Abstract

In this paper, we propose a novel scheduling framework for a dynamic real-time environment with energy constraints. This framework dynamically adjusts the CPU voltage/frequency so that no task in the system misses its deadline and the total energy savings of the system are maximized. In this paper, we consider only realistic, discrete-level speeds.Each task in the system consumes a certain amount of energy, which depends on a speed chosen for execution. The process of selecting speeds for execution while maximizing the energy savings of the system requires the exploration of a large number of combinations, which is too time consuming to be computed online. Thus, we propose an integrated heuristic methodology, which executes an optimization procedure in a low computation time. This scheme allows the scheduler to handle power-aware real-time tasks with low cost while maximizing the use of the available resources and without jeopardizing the temporal constraints of the system. Simulation results show that our heuristic methodology is able to generate power-aware scheduling solutions with near-optimal performance.

References

[1]

Amstrong, R. D., Kung, D. S., Sinha, P., and Zoltners, A. A. 1983. A computational study of a multiple-choice knapsack algorithm. ACM Transactions on Mathematical Software 9, 2, 184--198.

Digital Library

[2]

Arm. 2003.

[3]

Aydin, H., Melhem, R., Mossé, D., and Mejia-Alvarez, P. 2001a. Determining optimal processor speeds for periodic real-time tasks with different power characteristics. In Proceedings of the IEEE EuroMicro Conference on Real-Time Systems. IEEE Computer Society Press.

[4]

Aydin, H., Melhem, R., Mossé, D., and Mejia-Alvarez, P. 2001b. Dynamic and aggressive scheduling techniques for power-aware real-time systems. In IEEE Real-Time Systems Symposium. IEEE Computer Society Press.

[5]

Burd, T. D., Pering, T. A., Stratakos, A. J., and Brodersen, R. W. 2000. A dynamic voltage scaled microprocessor system. IEEE Journal of Solid-State Circuits 35, 11 (Nov.), 1571.

[6]

Buttazzo, G. and Sensini, F. 1999. Optimal deadline assignment for scheduling soft aperiodic tasks in hard real-time environments. IEEE Transactions on Computers 48, 10 (Oct.).

Digital Library

[7]

Chandrakasan, A.P., Sheng, S., and Brodersen, R. W. 1992. Low-power CMOS digital design. IEEE J. of Solid-State Circuits 27.

[8]

D'Atri, G. 1977. The generalized knapsack problem. In Communication at the Annual Meeting of CNR-GNIM, Rimini, Italy.

[9]

Dudani, A., Mueller, F., and Zhu, Y. 2002. Energy-conserving feedback EDF scheduling for embedded systems with real-time constraints. In ACM SIGPLAN Joint Conference on Languages, Compilers and Tools for Embedded Systems (LCTES'02). ACM Press.

[10]

Gruian, F. and Kuchcinski, K. 2001. LEneS: task scheduling for low energy systems using variable supply voltage processors. In Proceedings of the Asia South Pacific---DAC Conference.

[11]

Hong, I., Kirovski, D., Qu, G., Potkonjak, M., and Srivastava, M. 1998a. Power optimization of variable voltage core-based systems. In Design Automation Conference.

[12]

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

[13]

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. IEEE Computer Society Press.

[14]

Intel. Strong ARM SA-1100 Microprocessor Developer's Manual. INTEL.

[15]

Intel-ACPI. 2003. ACPI Specification. http://developer.intel.com/technology/IAPC/tech.

[16]

Intel-Xscale. 2003. http://developer.intel.com/design/xscale/.

[17]

Ishihara, T. and Yasuura, H. 1998. Voltage scheduling problem for dynamically varying voltage processors. In Proceedings of the International Symposium on Low Power Electronics and Design.

[18]

Joseph, M. and Pandya, P. 1986. Finding response times in a real-time system. Computer Journal 29, 390--395.

[19]

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 IEEE Real-Time Technology and Applications Symposium. IEEE Computer Society Press.

[20]

Lawler, E. 1979. Fast approximation algorithms for knapsack problems. Mathematics of Operations Research 4, 339.

Digital Library

[21]

Lipari, G. and Buttazzo, G. 2000. Schedulability analysis of periodic and aperiodic tasks with resource constraints. Journal of System Architecture 46, 327.

Digital Library

[22]

Liu, C. L. and Layland, J. 1973. Scheduling algorithms for multiprogramming in hard real-time environments. Journal of the ACM 20, 1 (Jan.).

Digital Library

[23]

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

[24]

Martello, S. and Toth, P. 1990. Knapsack Problems. Algorithms and Computer Implementations. Wiley.

[25]

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 (COLP'00).

[26]

Pillai, P. and Shin, K. G. 2001. Real-time dynamic voltage scaling for low-power embedded operating systems. In Proceedings of the 18th ACM Symposium on Operating System Principles (SOSP'01). ACM Press.

[27]

Pisinger, D. 1995. A minimal algorithm for the multiple-choice knapsack problem. European Journal of Operational Research 83.

[28]

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

[29]

Shin, D., Kim, W., Jeon, J., Kim, J., and Min, S.L. 2002. SIMDVS: An integrated simulation environment for performance evaluation of dynamic voltage scaling algorithms. In Proceedings of the Workshop on Power-Aware Computer Systems (PACS'02).

[30]

Sinha, P. and Zoltners, A. 1978. The multiple choice knapsack problem. Journal of the Operations Research Society of Japan 21, 59.

[31]

Swaminathan, V. and Chakrabarty, K. 2001. Investigating the effect of voltage-switching on low-energy task scheduling in hard real-time systems. In Proceedings of the Asia South Pacific---DAC Conference.

[32]

Transmeta. 2003.

[33]

Yao, F., Demers, A., and Shenker, S. 1995. A scheduling model for reduced CPU energy. In Proceedings of the IEEE Annual Foundations of Computer Science.

Cited By

Jiang WSong ZZhan JLiu DWan J(2022)Layerwise Security Protection for Deep Neural Networks in Industrial Cyber Physical SystemsIEEE Transactions on Industrial Informatics10.1109/TII.2022.315511218:12(8797-8806)Online publication date: Dec-2022
https://doi.org/10.1109/TII.2022.3155112
Teng FYu LLiu XLai P(2022)Tight Lower bound on power consumption for scheduling real-time periodic tasks in core-level DVFS systemsParallel Computing10.1016/j.parco.2022.102892110:COnline publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.parco.2022.102892
Ali IJo YLee SLee WKim K(2020)Reducing Dynamic Power Consumption in Mixed-Critical Real-Time SystemsApplied Sciences10.3390/app1020725610:20(7256)Online publication date: 16-Oct-2020
https://doi.org/10.3390/app10207256
Show More Cited By

Index Terms

Adaptive scheduling server for power-aware real-time tasks
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems

Recommendations

Node Scaling Scheduling of Real-Time Tasks in a Power-Aware Datacenter
HPCC-CSS-ICESS '15: Proceedings of the 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conf on Embedded Software and Systems

Power consumption of datacenters, especially of large-scale systems, has a growing concern nowadays due to economic and ecological reasons. In this paper, we propose a power-aware mechanism based on DVS that takes into account energy conservation of ...
Leakage-Aware Reallocation for Periodic Real-Time Tasks on Multicore Processors
FCST '10: Proceedings of the 2010 Fifth International Conference on Frontier of Computer Science and Technology

It is an increasingly important issue to reduce the energy consumption of computing systems. In this paper, we consider partition based energy-aware scheduling of periodic real-time tasks on multicore processors. The scheduling exploits dynamic voltage ...
Analysis on quantum-based fixed priority scheduling of real-time tasks
ICUIMC '09: Proceedings of the 3rd International Conference on Ubiquitous Information Management and Communication

Fixed priority schedulers are widely used for real-time systems, and there were efforts to improve the schedulability. Preemption threshold scheduling is one of such efforts with a dual priority scheme. It increases the schedulability by introducing ...

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 3, Issue 2

May 2004

225 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/993396

Issue’s Table of Contents

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

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 May 2004

Published in TECS Volume 3, Issue 2

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

81
Total Citations
View Citations
1,302
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)2

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jiang WSong ZZhan JLiu DWan J(2022)Layerwise Security Protection for Deep Neural Networks in Industrial Cyber Physical SystemsIEEE Transactions on Industrial Informatics10.1109/TII.2022.315511218:12(8797-8806)Online publication date: Dec-2022
https://doi.org/10.1109/TII.2022.3155112
Teng FYu LLiu XLai P(2022)Tight Lower bound on power consumption for scheduling real-time periodic tasks in core-level DVFS systemsParallel Computing10.1016/j.parco.2022.102892110:COnline publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.parco.2022.102892
Ali IJo YLee SLee WKim K(2020)Reducing Dynamic Power Consumption in Mixed-Critical Real-Time SystemsApplied Sciences10.3390/app1020725610:20(7256)Online publication date: 16-Oct-2020
https://doi.org/10.3390/app10207256
Zhang XXiao XHe LMa YHuang YLiu XXu WLiu C(2019)PIFA: An Intelligent Phase Identification and Frequency Adjustment Framework for Time-Sensitive Mobile Computing2019 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS.2019.00013(54-64)Online publication date: Apr-2019
https://doi.org/10.1109/RTAS.2019.00013
Agrawal S(2016)A lazy DVS approach for dynamic real time systemACM SIGBED Review10.1145/3015037.301503813:4(7-12)Online publication date: 3-Nov-2016
https://dl.acm.org/doi/10.1145/3015037.3015038
Yu LTeng FMagoulès F(2016)Node Scaling Analysis for Power-Aware Real-Time Tasks SchedulingIEEE Transactions on Computers10.1109/TC.2015.248522965:8(2510-2521)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1109/TC.2015.2485229
Sayuti MIndrusiak L(2015)A Function for Hard Real-Time System Search-Based Task Mapping OptimisationProceedings of the 2015 IEEE 18th International Symposium on Real-Time Distributed Computing10.1109/ISORC.2015.37(66-73)Online publication date: 13-Apr-2015
https://dl.acm.org/doi/10.1109/ISORC.2015.37
Teng FYu LLi T(2015)Node Scaling Scheduling of Real-Time Tasks in a Power-Aware DatacenterProceedings of the 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conf on Embedded Software and Systems10.1109/HPCC-CSS-ICESS.2015.76(96-101)Online publication date: 24-Aug-2015
https://dl.acm.org/doi/10.1109/HPCC-CSS-ICESS.2015.76
Ali ISeo JHoon Kim K(2015)A Dynamic Power-Aware Scheduling of Mixed-Criticality Real-Time Systems2015 IEEE International Conference on Computer and Information Technology; Ubiquitous Computing and Communications; Dependable, Autonomic and Secure Computing; Pervasive Intelligence and Computing10.1109/CIT/IUCC/DASC/PICOM.2015.63(438-445)Online publication date: Oct-2015
https://doi.org/10.1109/CIT/IUCC/DASC/PICOM.2015.63
(2015)Compositional power-aware real-time scheduling with discrete frequency levelsJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2015.05.00361:7(269-281)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1016/j.sysarc.2015.05.003
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