Type of Document	Dissertation
Author	Wu, Haisang
Author's Email Address	hswu02@vt.edu
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 Real-Time Scheduling Energy-Efficient Scheduling
Date of Defense	2005-07-29
Availability	unrestricted
Abstract In 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.
Files	Filename       Size       Approximate Download Time (Hours:Minutes:Seconds)     28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access    Dissertation_ERT_HaisangWu.pdf 1.10 Mb 00:05:04 00:02:36 00:02:17 00:01:08 00:00:05

If you have questions or technical problems, please Contact DLA.