Energy-Efficient, Utility Accrual Scheduling under Resource Constraints for Mobile Embedded Systems
VIRGINIA POLYTECHNIC INST AND STATE UNIV BLACKSBURG DEPT OF ELECTRICAL AND COMPUTER ENGINEERING
Pagination or Media Count:
We present an energy-efficient, utility accrual, real-time scheduling algorithm called the Resource-constrained Energy-Efficient Utility Accrual Algorithm or ReUA. ReUA considers an application model where activities are subject to timeutility function TUF time constraints, resource dependencies including mutual exclusion constraints, and statistical performance requirements including activity timeliness utility bounds that are probabilistically satisfied. Further, ReUA targets mobile embedded systems where system-level energy consumption is also a major concern. For such a model, we consider the scheduling objectives of 1 satisfying the statistical performance requirements and 2 maximizing the system-level energy efficiency. At the same time, resource dependencies must be respected. Since the problem is NP-hard, ReUA makes resource allocations using statistical properties of application cycle demands and heuristically computes schedules with a polynomial-time cost. We analytically establish several timeliness and non-timeliness properties of the algorithm. Further, our simulation experiments illustrate the algorithms effectiveness.
- Electrical and Electronic Equipment
- Statistics and Probability
- Operations Research
- Computer Hardware