Type of Document Dissertation Author Wu, Haisang Author's Email Address email@example.com URN etd-08242005-145355 Title Energy-Efficient, Utility Accrual Real-Time Scheduling Degree PhD Department Electrical and Computer Engineering Advisory Committee
Advisor Name Title Ravindran, Binoy Committee Chair Athanas, Peter M. Committee Member Jensen, E. Douglas Committee Member Martin, Thomas L. Committee Member Mishra, Amitabh Committee Member Sarin, Subhash C. Committee Member Keywords
- Overload Scheduling
- Dynamic Voltage Scaling
- Utility Accrual Scheduling
- Time/Utility Functions
- Energy-Efficient Scheduling
- Real-Time Scheduling
Date of Defense 2005-07-29 Availability unrestricted AbstractIn this dissertation, we consider timeliness and energy optimization in battery-powered, mobile embedded real-time systems. We focus on real-time systems that operate in environments with dynamically uncertain properties, including context-dependent activity execution times and arbitrary activity arrival patterns. We consider an application model where activities are subject to time/utility function (or TUF) time constraints, mutual exclusion constraints on concurrent sharing of non-CPU resources, timeliness requirements including assurances on individual activity timeliness behavior, and system-level energy consumption requirements including a non-exhaustable energy budget.
To account for uncertainties in activity properties in dynamic systems, we stochastically describe activity execution demands, and describe activity arrival behaviors using the unimodal arbitrary arrival model, which allows unbounded arrival frequencies. We consider the scheduling optimality criteria of: (1) probabilistically satisfying lower bounds on individual activities' maximal timeliness utilities, and (2) maximizing system-level energy efficiency, while ensuring that the system's energy consumption never exhausts the energy budget and resource mutual exclusion constraints are satisfied.
For this multi-criteria scheduling problem, we present a DVS (dynamic voltage scaling)-based, real-time scheduling algorithm called the Energy-Bounded Utility Accrual Algorithm (or EBUA). Since the scheduling problem is NP-hard, EBUA heuristically (and dynamically) allocates CPU cycles to activities, computes activity schedules, and scales CPU voltage and frequency with a polynomial-time cost. If activities' cumulative execution demands exceed the available CPU time or may exhaust the system's energy budget, the algorithm defers and rejects jobs in a controlled fashion, minimizing system-level energy consumption and maximizing total accrued utility.
We analytically establish several properties of EBUA. We prove that the algorithm never exhausts the specified energy budget. Further, we establish EBUA's timeliness optimality during under-loads, freedom from deadlocks, and correctness in mutually exclusive resource sharing. In particular, we prove that the algorithm's timeliness behavior subsumes the optimal timeliness behavior of deadline scheduling as a special case, and identify the conditions under which lower bounds on individual activity utilities are satisfied. In addition, we upper bound the time needed for mutually exclusively accessing shared resources under EBUA.
We conduct experimental studies by simulating the algorithm on the DVS-enabled AMD k6 processor model, and by implementing it on QNX Neutrino 6.2.1 RTOS. Our experimental results validate our analytical results. Further, they confirm EBUA's superiority over other energy-efficient real-time scheduling algorithms on timeliness and energy consumption behaviors.
Filename Size Approximate Download Time (Hours:Minutes:Seconds)
28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access Wu_Hao_T_2012.pdf 29.97 Mb 02:18:44 01:11:21 01:02:26 00:31:13 00:02:39
If you have questions or technical problems, please Contact DLA.