Luận án tiến sĩ: Power-aware scheduling for real-time embedded systems

POWER-AWARE SCHEDULING FOR REAL-TIME EMBEDDED SYSTEMS by Linwei Niu Master of Science State University of New York at Stony Brook, 2001 Bachelor of Science Beijing University, China, 1998 Submitted in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy in the Department of Computer Science and Engineering College of Engineering and Information Technology University of South Carolina 2006 Gaye—— Major Professbt ag. Chairman, Examining Committee Le án Committee Member Comntittee Mémber (2.z— Dean of The Graduate School UMI Number: 3245425 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted.

Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. ® UMI UMI Microform 3245425 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code.

ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 Acknowledgments First of all, I would like to express my sincere gratitude to my advisor, Dr. Gang Quan, for his invaluable hard work, guidance, support and encouragement throughout my graduate study at the University of South Carolina. Without him, none of the work would have been possible.

At the same time, I would like to thank Dr. Srihari Nelakuditi, and Dr. Antonello Monti for serving on my committee and for their valuable and constructive comments for my dissertation. I would like to thank all other faculty members and the staff for their valuable help and support throughout my graduate study at the University of South Car- olina.

I addition, I would like to thank all my friends in Columbia for their warm friendship, which made my life at the University of South Carolina memorable. Finally, Iam grateful to my parents. Although they are far away from me, they always give me unconditional love and support, which made my hard times much easier. ii Abstract Driven by the remarkable evolution of IC technology and the ever-increasing human appetite for higher computing power, the dramatically increased power /energy consumption for real-time embedded systems has presented a profound challenge to researchers and developers.

Battery-operated embedded devices, which have already been ubiquitous, demand low power consumption to extend the bat- tery life and thus the mission cycles. Even for power-rich platforms, rapidly el- evated power consumption raised serious concerns regarding the reliability and packaging /cooling cost as a result of the heat dissipation. It is fair to say that en- ergy reduction has become one of the most critical design issues in the design of next generation real-time embedded systems. Power/energy reduction for real-time embedded systems is a challenging prob- lem that requires research efforts in all fronts be pursued to form the effective so- lution.

Tremendous research studies have been conducted on reducing the power /energy consumption. They differ by their abstraction levels, underlying architec- tures, and design perspectives. In our research, we seek to address this problem at the operating system level. Specifically, we believe that real-time scheduling plays a critical role in power/energy reduction not only because most embedded sys- tems have real-time requirements, but also because significant energy savings can be achieved by taking advantage of the knowledge in application characteristics and underlying architectures known at this level.

The goal of our research is to study and develop appropriate real-time schedul- iii ing techniques that can exploit the advanced power manageable features in state- of-the-art architecture to minimize the power/energy consumption while satisfy- ing other design requirements at the same time. The contributions of the disser- tation include: (i) we developed several advanced power-aware scheduling al- gorithms for hard real-time systems with emphasis on reducing both dynamic and leakage power consumption; (ii) We extended the system model from sim- ple hard real-time systems to soft real-time systems with more complicated Qual- ity of Service constraints; (iii) We also developed efficient scheduling algorithms to minimize the system-wide energy consumption with peripheral devices taken into consideration. Experimental results have demonstrated that our techniques greatly outperform existing ones. The problems discussed in this dissertation are rather general in real-time embedded system designs, and these methodologies and techniques are important both in the theoretical and practical sense.

iv Contents Acknowledgments ii Abstract iii List of Figures xii 1 Introduction 11 Real-Time Embedded Systems.2 The Power Consumption in Embedded Systems .3 Power-Aware Design Techniques in Embedded Systems .4 Real-Time Scheduling.1 Power-Aware Scheduling on Hard Real-Time Systems 18 1.2 Power-Aware Scheduling on Soft Real-Time Systems. ch HH he he 27 2 Leakage-Aware Scheduling 2. ee HQ HH Ha an Ra 2. ee es 23 Prelminaries.So ẶẶ Q SỈ PowerModel.

Ặ eee eee eee 35 2.4 The General Approach. eee ee he he 38 2.1 Computing The LST for The EDF-Based JobSet .2 Computing The LST for The FP-Based Job Set. eee ee ees 54 2. {So Number ofldlelntervals.3 Overall Energy Reduction.4 Energy Reduction with Higher Threshold Speed.

ch HH HH HH HH kh Ha 62 DVS Scheduling for Real-Time Systems with QoS-Guarantee 65 31 Introduction ©. ch HH HH kh ha 71 3.1 System Models and Problem Formulation.2 ee ee Motivatons.4 Mandatory/OptionalJob Parttionng .41 Static Partiioning Strategy with (m,k)-Pattern.2 Dynamic Partitioning Strategy With (mm, k)-Pattern Adjustment 88 3.5 DVS Scheduling for The Task Set with ee ee tt .1 The Offline Phase. ee ee es 0.2 The Online Phase. ee es 98 vi 3.1 Experimental Results for Synthesized Task Sets .2 Experimental Results from Real Applications.

ee ee 106 DPD Scheduling for Real-Time Systems with QoS-Guarantee 107 41. ch HH he hi hở 111 421 System Models. ee eee te ee ee 111 4. eee ee es 112 4.

Meeting The (m,k)-Constraints .4 Delaying The Execution of Mandatory Jobs. ch HH HH h HH nh 126 4.1 Experimental Results for Synthesized Task Sets .2 Experimental Results from Real Applications. ee 133 Combining DVS and DPD Scheduling for Real-Time Systems with QoS- Guarantee 135 51 Introducton. ee es 136 52 Preliminary.

‹ ‹ che HH HH he ng 138 521 - ch SystemModel. HH nh nen 138. HH HH he 140 5.3 The Hybrid Partitioning Strategy. eee eee eee 141 53.1 The Feasibility Condiion .2 The Pattern Assignment ++ 0s eee -.

147 The Dynamic Scheduling Algorthm. ee es 153 vii 5.1 Experimental Results for Synthesized Task Sets .2 Experimental Results for Real Applications. 159 6 Conclusions and Future Work 161 Bibliography 164 Viii List of Figures 1. Embedded systems everywhere.6eee ee eee ees 1.2 Embedded systems dominate the 32-bit market [55].3 Growth for the embedded system market by 2009 [154].4 Low Operating Power (LOP) Device Power Increment [72] .5 The performance/power gaps tend to become larger in the future [14] 2.1 (a) A job set with five jobs scheduled with EDF.

(d) The job schedule with Sty = OB. Q Q Q Q Q nu ch nh kg k k k ko cà Ko R K K Ko Ko th ho ky 36 2.2 (a) The delay bound.5, using the minimum of the latest start times of the jobs arriving before Tz as LST for the job set causes J> to miss its deadline. (c) The idle intervals are not effec- tively merged using T;s = 6, computed based on the completion time of the jobs according to the DVS voltage schedule. (d) With Trs = 8, all the idle intervals are merged into one single interval and all jobs can meet their deadlines.3 (a) A job set with four jobs scheduled with FP, and the LST is com- puted as 3 according to Lemma 1(s* = 0.

(b) Delay the job set until t = 6 and every job can meet its deadline. (d) Delay execution of the job set till t = 8 and J, misses its deadline.4 The average total energy consumption by the different approaches.5 The average total energy consumption by the different approaches.6 The average idle energy consumption by the different approaches with s4, =0.1 The greedy approach in [64] fails to guarantee the schedulability of an underloaded task set.2 Examples of mandatory jobs based on R-patterns, E-patterns, and ER-patterns.4 (a) Executing only the mandatory jobs of task set according to their ER.patterns; (b) Dynamically restarting the E”-Pattern at t = 8 for Tạ. chkh kh kh 91 3.5 (a)The original mandatory jobs according to the Z”-pattern of task 7;; (b) The mandatory jobs of 7; after restarting the #” pattern.6 (a) The average total energy consumption by the different approaches; (b) The average number of effective jobs by the different approaches.7 (a) Energy consumption for webphone by the different approaches on IBM PowerPC 405LP processor model; (b) The average number of effective jobs for webphone by the different approaches on IBM PowerPC 405LP processor model.8 (a) Energy consumption for CNC by the different approaches on IBM PowerPC 405LP processor model; (b) The average number of effective jobs for CNC by the different approaches on IBM PowerPC 405LP processor model. eee ee eee 104 3.9 (a) Energy consumption for INS by the different approaches on IBM PowerPC 405LP processor model; (b) The average number of effec- tive jobs for INS by the different approaches on IBM PowerPC 405LP ee processor model.1 (a) The EDF schedule for three tasks according to E-patterns; (b) The EDF schedule for same tasks based on R-patterns; (c) A better schedule for the same task set.2 (a) Three tasks scheduled based on their R-Pattern; (b) Jz, cannot be delayed according to Theorem 8; (c) Delaying the mandatory jobs to t = 23 ( [114]) cannot remove the idle interval; (d) Delaying the mandatory jobs to t = 27 and eliminating the idle interval.3 The average number of idle intervals by different approaches.4 The average total energy consumption by different approaches when (a) Pact = Poacti (bP) Paact = 10Ppacte ss ee ee es 129 4.5 The average total energy consumption by different approaches.6 (a) The average total energy consumption for CNC by different ap- proaches; (b) The average number of idle intervals for CNC by dif- ferent approaches.7 (a) The average total energy consumption for INS by different ap- proaches; (b) The average number of idle intervals for INS by differ- entapproaches.8 (a) The average total energy consumption for Webphone by different approaches; (b) The average number of idle intervals for Webphone .1 (a) Executing the mandatory jobs of task set (7¡ = (4,4,2, 2, 4); Ta = (8, 8, 4, 2, 4);) according to their E-patterns; (b) Executing the manda- tory jobs of the same task set according to their R-patterns; (c) Ex- ecuting the mandatory jobs of the same task set according to their hyb-patterns.2 (a) The average total energy consumption by the different approaches; (b) The energy comparison for different shut-down interval length; (c) The energy comparison for different preemption control tech- NIQUES.3 (a) The average total energy consumption by the different approaches; (b) The energy comparison for different shut-down interval length; (c) The energy comparison for different preemption control tech- THQUES.

6 Q Q Q SH HH HH HH HH Ko 157 xii Chapter 1 Introduction This chapter first gives a brief introduction on real-time embedded systems, fol- lowed by the power consumption issues in embedded systems. Thereafter, we survey the state of the art in the research of power-aware design methodology, real-time scheduling and power-aware scheduling. We then discuss the contribu- tion of our research. This chapter ends with the description of the organization of this dissertation.1 Real-Time Embedded Systems An embedded system is a special-purpose computer system built into a larger sys- tem for the purpose of controlling and monitoring the system [11, 58].