Power-aware Scheduling in Networked Embedded Systems (under construction)

Real-time Computation Using Dynamic Voltage and Frequency Scaling

Dynamic voltage and Frequency scaling (DVS) is an effective approach to power reduction by scaling the processor voltage and frequency when the system is not fully loaded. Many of today's laptop, embedded devices are powered by processor with this DVS features. In [1], we proposed techniques for energy-optimization for a general task model. The major contributions are:
  1. A generalization of several represented algorithms for aperiodic, sporadic tasks (a special type of aperiodic tasks), and periodic tasks.
  2. An adaptive scaling policy is proposed for more energy savings. The solution has a low time-complexity and can be easily integrated into existing schedulers. It can be applied to both worst case based scheduling and on-line slack management when tasks finish earlier than estimated.
  3. We propose to use statistical real-time guarantee to lower the computation capacity given a set of sporadic tasks (or to admit more tasks given a fixed capacity). We achieve this by analyzing the tail distribution of the load distribution.

Real-time Communication in AWGN Wireless Channels

Similar technique is available for energy-efficient packet scheduling by slowing down transmission rate in real-time wireless communication, such as dynamic modulation scaling. In [2], I proposed energy-efficient packet scheduling policy for an input process with a general distribution. We decided the policy by the use of input autocorrelation. Capacity bound subject to a deadline miss rate or an outage probability is derived for unimodal distributions, Poisson and Gaussian distributions for example.

An energy-aware policy saves energy by slowing down the speed of packet transmission. Meanwhile, slowing down transmission speed may lead to unexpected packet drops. I studied the impact of transmission slowing down on packet drops as a result of power outages and buffer overflows and proposed a strategy to bound the number of packet drops [3].

System-wide Energy Minimization

The technique of processor or wireless transmission slowdown only considers a single component of a system. A computer system usually has multiple components and they consume energy even if not in use. Although the energy consumption of the processor or wireless transmitter is reduced, energy consumed by other components may increase as a result of elongated task execution time or packet transmission time. Take CPU task scheduling as an example, the impact of standby power on processor speed slowdown shows that there exists a critical speed for an application. Below the speed, processor slowdown may no longer be beneficial from the system point of view.

Under a practical processor with discrete speed levels, I proved that system-wide energy minimization is NP-hard for a group of periodic real-time tasks, and NP-hard in the strong sense for online aperiodic tasks. I proposed an algorithm that can find the optimal solution in pseudo-polynomial time; an approximation scheme that provides bounded performance degradation with running time polynomial in the number of tasks and a predefined performance ratio [4].

References:

  1. Xiliang Zhong and Cheng-Zhong Xu, "Energy-Aware Modeling and Scheduling of Real-Time Tasks for Dynamic Voltage Scaling" IEEE Real-time Symposium (RTSS 2005, Extended work accepted by IEEE Trans. Computer), Miami, FL, Dec. 2005
  2. Xiliang Zhong and Cheng-Zhong Xu, "Delay-Constrained Energy-Efficient Wireless Packet Scheduling with QoS Guarantee " IEEE Globecom, Saint Louis, MO, Nov. 2005
  3. Xiliang Zhong and Cheng-Zhong Xu, "Energy-Efficient Wireless Packet Scheduling with Quality of Service Control" IEEE Trans. on Mobile Computing (Accepted)
  4. X. Zhong and C.-Z. Xu, System-Wide Energy Minimization for Real-Time Tasks: Lower Bound and Approximation, IEEE/ACM International Conference on Computer-Aided Design (ICCAD 2006, extended work accepted by ACM Trans. on Embedded Computing), San Jose, CA, Nov. 2006.