Energy-Efficient, Utility Accrual Scheduling Under Resource Constraints for Mobile Embedded Systems
October 2004
Haisang Wu, ECE Dept., Virginia Tech
Binoy Ravindran, ECE Dept., Virginia Tech
E. Douglas Jensen, The MITRE Corporation
Peng Li, ECE Dept., Virginia Tech
ABSTRACT
We present an energy-efficient, utility accrual, real-time
scheduling algorithm called the Resource-constrained Energy-
Efficient Utility Accrual Algorithm (or ReUA). ReUA con-
siders an application model where activities are subject
to time/utility 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 algorithm's effectiveness.
Additional Search Keywords
n/a
|
