article

Rolling-horizon scheduling for energy constrained distributed real-time embedded systems

Authors:

Jianqing JiangAuthors Info & Claims

Journal of Systems and Software, Volume 85, Issue 4

Pages 780 - 794

https://doi.org/10.1016/j.jss.2011.10.008

Published: 01 April 2012 Publication History

Abstract

Energy-efficient scheduling approaches are critical to battery driven real-time embedded systems. Traditional energy-aware scheduling schemes are mainly based on the individual task scheduling. Consequently, the scheduling space for each task is small, and the schedulability and energy saving are very limited, especially when the system is heavily loaded. To remedy this problem, we propose a novel rolling-horizon (RH) strategy that can be applied to any scheduling algorithm to improve schedulability. In addition, we develop a new energy-efficient adaptive scheduling algorithm (EASA) that can adaptively adjust supply voltages according to the system workload for energy efficiency. Both the RH strategy and EASA algorithm are combined to form our scheduling approach, RH-EASA. Experimental results show that in comparison with some typical traditional scheduling schemes, RH-EASA can achieve significant energy savings while meeting most task deadlines (namely, high schedulability) for distributed real-time embedded systems with dynamic workloads.

References

[1]

AMD PowerNow!. http://www.amd.com/powernow.html.

[2]

http://mars3.jpl.nasa.gov/MPF/.

[3]

Modeling and evaluating energy-performance efficiency of parallel processing on multicore based power aware systems. In: Proc. the 5th High Performance Power Aware Computing workshop in conjunction with the 23th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2009), May, pp. 1-8.

[4]

PowerPack: energy profiling and analysis of high-performance systems and applications. IEEE Trans. Parallel Distrib. Syst. v21 iMay (5). 658-671.

[5]

Disign of fast and efficient energy-aware gradient-based scheduling algorithms for heterogeneous embedded multiprocessor systems. IEEE Trans. Parallel Distrib. Syst. v20 i1. 1-12.

[6]

Intel XScale http://www.intel.com.

[7]

CASPER: an integrated energy-driven approach for task graph scheduling on distributed embedded systems. In: Proc. the 16th Int'l Conf. Application-Specific Systems, Architecture and Processors (ASAP 2005), July, pp. 191-197.

[8]

Power-aware scheduling of bag-of-tasks applications with deadline constraints on DVS-enabled clusters. In: Proc. the 7th IEEE/ACM Int'l Symp. Cluster Computing and the Grid (CCGrid 2007), May, pp. 541-548.

[9]

Dynamic resource management in energy constrained heterogeneous computing systems using voltage scaling. IEEE Trans. Parallel Distrib. Syst. v19 iNovember (11). 1445-1457.

Digital Library

[10]

Near real-time parallel image processing using cluster computers. In: Proc. First Int'l Conf. Space Mission Challenges for Information Technology (SMC-IT 2003), July, pp. 13-16.

[11]

Real-time Systems. McGraw-Hill, USA.

[12]

Energy-aware scheduling of real-time tasks in wireless networked embedded systems. In: Proc. the 28th IEEE Int'l Symp. Real-Time Systems (RTSS 2007), December, pp. 15-24.

[13]

End-to-end energy management in networked real-time embedded systems. IEEE Trans. Parallel Distrib. Syst. v19 iNovember (11). 1498-1510.

Digital Library

[14]

Liu, J., Chou, P.H., Bagherzadeh, N., Kurdahi, F., 2001. Power-aware scheduling under timing constraints for mission-critical embedded systems. In: Proc. the Design Automation Conf. (DAC 2001), June. pp. 840-845.

[15]

Novel critical-path based low-energy scheduling algorithm for heterogeneous multiprocessor real-time embedded systems. In: Proc. the Int'l Conf. Parallel and Distributed Systems (ICPADS 2007), December, pp. 1-8.

[16]

Novel critical-path based low-energy scheduling algorithm for heterogeneous multiprocessor real-time embedded systems. In: Proc. the 13th Int'l Conf. Parallel and Distributed Systems (ICPADS 2007), December, pp. 1-8.

[17]

Load-matching adaptive task scheduling for energy efficiency in energy harvesting real-time embedded systems. In: Proc. the Int'l Symp. Low Power Electronics and Design (LSLPED 2010), August, pp. 325-330.

[18]

Power-efficient scheduling for heterogeneous distributed real-time embedded systems. IEEE Trans. Comput. Aid. Des. Integr. Circ. Syst. v26 iJune (6). 1161-1170.

[19]

Dynamic frequency and voltage scaling for a multiple-clock-domain microprocessor. IEEE Micro. v23 i6. 62-68.

[20]

An energy-efficient slack distribution technique for multimode distributed real-time embedded systems. IEEE Trans. Parallel Distrib. Syst. v16 iJuly (7). 650-662.

Digital Library

[21]

Dynamic mapping of a class of independent tasks onto heterogeneous computing systems. J. Parallel Distrib. Comput. v59 iNovember (2). 107-121.

[22]

A fault-tolerant dynamic scheduling algorithm for multiprocessor real-time systems and its analysis. IEEE Trans. Parallel Distrib. Syst. v9 i11. 1137-1152.

[23]

A hierarchical approach for energy efficient application design using heterogeneous embedded systems. In: Proc. the Int'l Conf. Compilers, Architecture and Synthesis for Embedded Systems (CASES 2003), October-November, pp. 243-254.

[24]

Energy efficiency and fairness tadeoffs in multi-resource multi-tasking embedded systems. In: Proc. the ACM Int'l Symp. Low Power Electronics and Design (ISLPED 2003), August, pp. 469-474.

[25]

Energy-aware routing protocol for heterogeneous wireless sensor networks. In: Proc. 16th Int'l Workshop Database and Expert Systems Applications (DEXA 2005), August, pp. 133-137.

[26]

A dynamic and reliability-driven scheduling algorithm for parallel real-time jobs executing on heterogeneous clusters. J. Parallel Distrib. Comput. v65 iAugust (8). 885-900.

[27]

Cost minimization while satisfying hard/soft timing constraints for heterogeneous embedded systems. ACM Trans. Des. Autom. Electron. Syst. v14 iMarch (2). 1-30.

[28]

Energy minimization with soft real-time and DVS for uniprocessor and multiprocessor embedded systems. In: Proc. the Design, Automation & Test in Europe Conference & Exhibition (DATE 2007), April, pp. 1-6.

[29]

"Energy-aware wireless microsensor networks. IEEE Signal Process. Mag. v19. 40-50.

[30]

Energy-efficient mapping and scheduling for DVS enabled distributed embedded systems. In: Proc. the 2002 Design, Automation and Test in Europe Conference and Exhibition (DATE 2002), March, pp. 514-521.

[31]

Real-time dynamic voltage loop scheduling for multi-core embedded systems. IEEE Trans. Circ. Syst. II: Express Briefs. v54 iMay (5). 445-449.

[32]

Shao, Z., 2005. High performance, low power and secure embedded systems. Ph.D. Dissertation. Dept. of Computer Science, Univ. of Texas, Dallas.

[33]

An approach for pre-runtime scheduling in embedded hard real-time systems with power constraints. In: Proc. the 16th Symp. Computer Architecture and High Performance Computing (SBAC-PAD 2004), October, pp. 188-195.

[34]

An environment for measuring and scheduling time-critical embedded systems with energy constraints. In: Proc. the 16th Int'l Conf. Software Engineering and Formal Methods (SEFM 2008), November, pp. 291-300.

[35]

Transmeta Crusoe http://www.tranmeta.com.

[36]

NP-complete scheduling problems. J. Comput. Syst. Sci. v10 iOctober (3). 384-393.

[37]

Feedback scheduling of real-time control tasks in power-aware embedded systems. In: Proc. the 2nd Int'l Conf. Embedded Software and Systems (ICESS 2005), December, pp. 513-519.

[38]

Solving energy-latency dilemma: task allocation for parallel applications in heterogeneous embedded systems. In: Proc. the 2006 Int'l Conf. Parallel Processing (ICPP 2006), August, pp. 12-22.

[39]

Joint dynamic voltage scaling and adaptive body biasing for heterogeneous distributed real-time embedded systems. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. v24. iJuly (7).

[40]

Energy-balanced task allocation for collaborative processing in wireless sensor netwroks. Mobile Netw. Appl. v10. 115-131.

[41]

Dynamic scheduling of imprecise-computation tasks in maximizing QoS under energy constraints for embedded systems. In: Proc. the Asia and South Pacific Design Automation Conference (ASP-DAC 2008), January, pp. 452-455.

[42]

Reliability-aware dynamic voltage scaling for energy-constrained real-time embedded systems. In: Proc. the IEEE Int'l Conf. Computer Design (ICCD 2008), October, pp. 633-639.

[43]

Scheduling with dynamic voltage/speed adjustment using slack reclamation in multi-processor real-time systems. IEEE Trans. Parallel Distrib. Syst. v14 iJuly (7). 686-700.

Digital Library

[44]

Towards adaptive power-aware scheduling for real-time tasks on DVS-enabled heterogeneous clusters. In: Proc. the 2010 IEEE/ACM Int'l Conf. Green Computing and Communications (GreenCom 2010), December, pp. 117-124.

[45]

QoS-aware fault-tolerant scheduling for real-time tasks on heterogeneous clusters. IEEE Trans. Comput. v60 iJune (6). 800-812.

Digital Library

[46]

Performance and energy aware cluster-level scheduling of compute-intensive jobs with unknown service times. Simul. Model. Pract. Theor. v19 iJune. 239-250.

Cited By

Terzopoulos GKaratza H(2018)Energy-efficient real-time heterogeneous cluster scheduling with node replacement due to failuresThe Journal of Supercomputing10.1007/s11227-013-1070-068:2(867-889)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.1007/s11227-013-1070-0
Zhang YCheng XChen LShen H(2018)Energy-efficient Tasks Scheduling Heuristics with Multi-constraints in Virtualized CloudsJournal of Grid Computing10.1007/s10723-018-9426-616:3(459-475)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s10723-018-9426-6
Lei HWang RZhang TLiu YZha Y(2016)A multi-objective co-evolutionary algorithm for energy-efficient scheduling on a green data centerComputers and Operations Research10.1016/j.cor.2016.05.01475:C(103-117)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1016/j.cor.2016.05.014

Recommendations

Scheduling and energy savings for small scale embedded FreeRTOS-based real-time systems
Abstract
Evaluating the effectiveness of system scheduling and energy savings in embedded real-time systems with low-computing resources is the problem addressed in this paper. In such systems, the characteristics of the implemented scheduling policy play ...
Energy efficient scheduling for real-time embedded systems
Efficient Scheduling Algorithms for Real-Time Multiprocessor Systems

Efficient scheduling algorithms based on heuristic functions are developed for scheduling a set of tasks on a multiprocessor system. The tasks are characterized by worst-case computation times, deadlines, and resources requirements. Starting with an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Systems and Software

Journal of Systems and Software Volume 85, Issue 4

April, 2012

258 pages

ISSN:0164-1212

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2011.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 01 April 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Terzopoulos GKaratza H(2018)Energy-efficient real-time heterogeneous cluster scheduling with node replacement due to failuresThe Journal of Supercomputing10.1007/s11227-013-1070-068:2(867-889)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.1007/s11227-013-1070-0
Zhang YCheng XChen LShen H(2018)Energy-efficient Tasks Scheduling Heuristics with Multi-constraints in Virtualized CloudsJournal of Grid Computing10.1007/s10723-018-9426-616:3(459-475)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s10723-018-9426-6
Lei HWang RZhang TLiu YZha Y(2016)A multi-objective co-evolutionary algorithm for energy-efficient scheduling on a green data centerComputers and Operations Research10.1016/j.cor.2016.05.01475:C(103-117)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1016/j.cor.2016.05.014

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents