research-article

Temperature- and energy-constrained scheduling in multitasking systems: a model checking approach

Authors:

Prabhat MishraAuthors Info & Claims

ISLPED '10: Proceedings of the 16th ACM/IEEE international symposium on Low power electronics and design

Pages 85 - 90

https://doi.org/10.1145/1840845.1840863

Published: 18 August 2010 Publication History

Abstract

The ongoing scaling of semiconductor technology is causing severe increase of on-chip power density and temperature in microprocessors. This has raised urgent requirement for both power and thermal management during each level of system design. In this paper, we propose a formal technique based on model checking using extended timed automata to solve the processor frequency assignment problem in a temperature- and energy- constrained multitasking system. The state space explosion problem is alleviated by transforming and solving a Pseudo-Boolean satisfiability problem. Our approach is capable of finding efficient solutions under various constraints and applicable to other problem variants as well. Our method is independent of any system and task characteristics. Experimental results demonstrate the usefulness of our approach.

References

[1]

R. Alur et al., A theory of timed automata. Theor. Comput. Sci., 126(2):183--235, 1994.

Digital Library

[2]

H. Aydin et al., Determining optimal processor speeds for periodic real-time tasks with different power characteristics. ECRTS, 2001.

Digital Library

[3]

H. Aydin et al., Power-aware scheduling for periodic real-time tasks. IEEE Trans. Comput., 53(5):584--600, 2004.

Digital Library

[4]

T. Bengtsson et al., Uppaal-a tool suite for automatic verification of real-time systems. DIMACS/SYCON workshop on Hybrid systems III : verification and control, 1996.

Digital Library

[5]

T. Berthold et al., Nonlinear pseudo-boolean optimization: Relaxation or propagation? SAT, 2009.

Digital Library

[6]

S. Borkar et al., Parameter variations and impact on circuits and microarchitecture. DAC, 2003.

Digital Library

[7]

E. Boros et al., Pseudo-boolean optimization. Discrete Appl. Math., 123(1-3):155--225, 2002.

Digital Library

[8]

J.-J. Chen et al., On the minimization fo the instantaneous temperature for periodic real-time tasks. RTAS, 2007.

Digital Library

[9]

J.-J. Chen et al., Energy-efficient scheduling for real-time systems on dynamic voltage scaling (dvs) platforms. RTCSA, 2007.

Digital Library

[10]

M. Chen et al., Efficient decision ordering techniques for SAT-based test generation. DATE, 2010.

Digital Library

[11]

E. Clarke et al., Model Checking. MIT Press, 1999.

Digital Library

[12]

M. J. Ellsworth. Chip power density and module cooling technology projections for the current decade. ITHERM, 2004.

[13]

E. Fersman et al., Timed automata with asynchronous processes: Schedulability and decidability. TACAS, 2002.

Digital Library

[14]

S. Gunther et al., Managing the impact of increasing microprocessor power consumption. ITJ, 5(1):1--9, 2001.

[15]

R. Jayaseelan et al., Temperature aware task sequencing and voltage scaling. ICCAD, 2008.

Digital Library

[16]

R. Jejurikar et al., Energy aware non-preemptive scheduling for hard real-time systems. ECRTS, 2005.

Digital Library

[17]

R. Jejurikar et al., Leakage aware dynamic voltage scaling for real-time embedded systems. DAC, 2004.

Digital Library

[18]

T. Liu et al., Thermal vs energy optimization for dvfs-enabled processors in embedded systems. ISQED, 2007.

Digital Library

[19]

A. Lungu et al., Multicore power management: Ensuring robustness via early-stage formal verification. MEMOCODE, 2009.

Digital Library

[20]

S. M. Martin et al., Combined dynamic voltage scaling and adaptive body biasing for lower power microprocessors under dynamic workloads. ICCAD, 2002.

Digital Library

[21]

Marvell. Marvell StrongARM 1100 processor. www.marvell.com.

[22]

C. Norström et al., Timed automata as task models for event-driven systems. RTCSA, 1999.

[23]

PBclasp. PBclasp. http://potassco.sourceforge.net/labs.html.

[24]

. Qin et al., Synchronized generation of directed tests using satisfiability solving. VLSI Design, 2010.

Digital Library

[25]

X. Shin et al., Dynamic voltage scaling of periodic and aperiodic tasks in priority-driven systems. ASP-DAC, 2004.

Digital Library

[26]

D. Shuklaet et al., A model checking approach to evaluating system level dynamic power management policies for embedded systems. HLDVT, 2001.

[27]

S. Skadron et al., Temperature-aware computer systems: Opportunities and challenges. IEEE Micro, 23(6):52--61, 2003.

Digital Library

[28]

K. Skadron et al., Temperature-aware microarchitecture: Modeling and implementation. ACM Trans. Archit. Code Optim., 1(1):94--125, 2004.

Digital Library

[29]

R. Viswanath et al., Thermal performance challenges from silicon to systems. ITJ, 4(3):1--16, 2000.

[30]

S. Wang et al., Reactive speed control in temperature-constrained real-time systems. ECRTS, 2006.

Digital Library

[31]

W. Wang et al., Leakage-aware energy minimization using dynamic voltage scaling and cache reconfiguration in real-time systems. VLSI Design, 2010.

Digital Library

[32]

W. Wang et al., PreDVS: preemptive dynamic voltage scaling for real-time systems using approximation scheme. DAC, 2010.

Digital Library

[33]

W. Wang et al., SACR: scheduling-aware cache reconfiguration for real-time embedded systems. VLSI Design, 2009.

Digital Library

[34]

N. Weste et al., CMOS VLSI Design: A Circuits and Systems Perspective. Addison Wesley, 2004.

Digital Library

[35]

L.-T. Yeh et al., Thermal Management of Microelectronic Equipment: Heat Transfer Theory, Analysis Methods, and Design Practices. ASME Press, 2002.

[36]

L. Yuan et al., Alt-dvs: Dynamic voltage scaling with awareness of leakage and temperature for real-time systems. AHS, 2007.

Digital Library

[37]

S. Zhang et al., Approximation algorithms for power minimization of earliest deadline first and rate monotonic schedules. ISLPED, 2007.

Digital Library

[38]

S. Zhang et al., Approximation algorithm for the temperature aware scheduling problem. ICCAD, 2007.

Digital Library

[39]

X. Zhong et al., System-wide energy minimization for real-time tasks: Lower bound and approximation. ICCAD, 2006.

Digital Library

Cited By

Jayasena AMishra P(2024)Directed Test Generation for Hardware Validation: A SurveyACM Computing Surveys10.1145/363804656:5(1-36)Online publication date: 12-Jan-2024
https://doi.org/10.1145/3638046
Ahmed AHuang YMishra P(2019)Cache Reconfiguration Using Machine Learning for Vulnerability-aware Energy OptimizationACM Transactions on Embedded Computing Systems10.1145/330976218:2(1-24)Online publication date: 2-Apr-2019
https://dl.acm.org/doi/10.1145/3309762
Qin XWang WMishra P(2019)TCECIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2012.219082431:8(1159-1168)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1109/TCAD.2012.2190824
Show More Cited By

Index Terms

Temperature- and energy-constrained scheduling in multitasking systems: a model checking approach
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems

Recommendations

Reachability Analysis of Cost-Reward Timed Automata for Energy Efficiency Scheduling
PMAM'14: Proceedings of Programming Models and Applications on Multicores and Manycores

As the ongoing scaling of semiconductor technology causing severe increase of on-chip power density in microprocessors, this leads for urgent requirement for power management during each level of computer system design. In this paper, we describe an ...
Reachability Analysis of Cost-Reward Timed Automata for Energy Efficiency Scheduling
PMAM'14: Proceedings of Programming Models and Applications on Multicores and Manycores

As the ongoing scaling of semiconductor technology causing severe increase of on-chip power density in microprocessors, this leads for urgent requirement for power management during each level of computer system design. In this paper, we describe an ...
Temperature-Aware On-Chip Networks

On-chip networks are becoming increasingly popular as a way to connect high-performance single-chip computer systems, but thermal issues greatly limit network design. This thermal modeling and simulation framework combines with a distributed runtime ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISLPED '10: Proceedings of the 16th ACM/IEEE international symposium on Low power electronics and design

August 2010

458 pages

ISBN:9781450301466

DOI:10.1145/1840845

General Chairs:
Vojin Oklobdzija
University of Texas, Dallas
,
Barry Pangle
Mentor Graphics
,
Naehyuck Chang
Seoul National University
,
Program Chairs:
Naresh Shanbhag
University of Illinois at Urbana-Champaign
,
Chris H. Kim
University of Minnesota

Copyright © 2010 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]

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

In-Cooperation

IEEE CAS

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 August 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISLPED'10

Sponsor:

SIGDA

ISLPED'10: International Symposium on Low Power Electronics and Design

August 18 - 20, 2010

Texas, Austin, USA

Acceptance Rates

Overall Acceptance Rate 398 of 1,159 submissions, 34%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
272
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jayasena AMishra P(2024)Directed Test Generation for Hardware Validation: A SurveyACM Computing Surveys10.1145/363804656:5(1-36)Online publication date: 12-Jan-2024
https://doi.org/10.1145/3638046
Ahmed AHuang YMishra P(2019)Cache Reconfiguration Using Machine Learning for Vulnerability-aware Energy OptimizationACM Transactions on Embedded Computing Systems10.1145/330976218:2(1-24)Online publication date: 2-Apr-2019
https://dl.acm.org/doi/10.1145/3309762
Qin XWang WMishra P(2019)TCECIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2012.219082431:8(1159-1168)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1109/TCAD.2012.2190824
Wang WDong GDeng ZZeng GLiu WXiong HBalaji PGuo MHuang Z(2014)Reachability Analysis of Cost-Reward Timed Automata for Energy Efficiency SchedulingProceedings of Programming Models and Applications on Multicores and Manycores10.1145/2578948.2560695(140-148)Online publication date: 7-Feb-2014
https://dl.acm.org/doi/10.1145/2578948.2560695
Wang WDong GDeng ZZeng GLiu WXiong HBalaji PGuo MHuang Z(2014)Reachability Analysis of Cost-Reward Timed Automata for Energy Efficiency SchedulingProceedings of Programming Models and Applications on Multicores and Manycores10.1145/2560683.2560695(140-148)Online publication date: 7-Feb-2014
https://dl.acm.org/doi/10.1145/2560683.2560695
Qin XMishra P(2014)TECSProceedings of the 2014 27th International Conference on VLSI Design and 2014 13th International Conference on Embedded Systems10.1109/VLSID.2014.44(216-221)Online publication date: 5-Jan-2014
https://dl.acm.org/doi/10.1109/VLSID.2014.44
Mohaqeqi MKargahi MMovaghar A(2014)Analytical Leakage-Aware Thermal Modeling of a Real-Time SystemIEEE Transactions on Computers10.1109/TC.2012.23763:6(1378-1392)Online publication date: Jun-2014
https://doi.org/10.1109/TC.2012.237
Chandnani LKapoor H(2013)Formal Approach for DVS-Based Power Management for Multiple Server System in Presence of Server Failure and RepairIEEE Transactions on Industrial Informatics10.1109/TII.2012.21986569:1(502-513)Online publication date: Feb-2013
https://doi.org/10.1109/TII.2012.2198656
Wang WRanka SMishra P(2011)A General Algorithm for Energy-Aware Dynamic Reconfiguration in Multitasking SystemsProceedings of the 2011 24th International Conference on VLSI Design10.1109/VLSID.2011.17(334-339)Online publication date: 2-Jan-2011
https://dl.acm.org/doi/10.1109/VLSID.2011.17

View Options

Get Access

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents