Group Brief

ExPERTS- A collaborative research group that develops scheduling algorithms to minimize the energy/power consumption of real-time embedded systems. Our main tool for energy conservation is Dynamic Voltage Scaling (DVS), varying the supply voltage of system processors during runtime.

Participants

University of Notre Dame
 Xiaobo (Sharon) Hu
Danny Z. Chen
Bren Mochocki
University of South Carolina
 Gang Quan
Synopsys, Inc.
 Yumin Zang

Projects

This collaborated research effort attempts to develop scheduling algorithms to minimize the energy/power consumption of hard real-time embedded systems utilizing the energy conservation method called Dynamic Voltage Scaling (DVS) on one or more DVS processors. The research proposed offers both heuristics for achieving feasible schedules and optimal-voltage scheduling techniques for a variety of systems configurations and scheduling policies, e.g. Earliest Deadline First (EDF) and Rate Monotonic (RM) priority assignments, while taking into account actual processor limitations such as time/energy transition and voltage level discretization.

  • Heuristic, Fixed-Priority Scheduling: We present a technique to determine voltage settings for a DVS processor that utilized a fixed priority assignment to schedule jobs.Our approach also produces the minimum constant voltage needed to feasibly schedule the entire job set.This approach leads to significant energy savings compared with previously presented approaches [2].
  • Optimal, Fixed-Priority Scheduling: We present an approach to find the least-energy voltage schedule for executing real-time jobs on a DVS processor according to a fixed priority, preemptive policy.The significance of our approach is that the theoretical limit in terms of energy savings for such systems is established, which can thus serve as the standard to evaluate the performance of various heuristic approaches [3].
  • Heuristic, EDF Scheduling with a realistic DVS Processor Model: We show that for hard, real-time applications, disregarding actual processor properties, such as transition overhead (the time and energy incurred when changing voltage/frequency levels) and voltage discretization (voltage/frequency levels are limited to a discrete set)...[4].
  • Integrated Task Scheduling and Voltage Selection on Multiple Processors: For this work, a two-phase framework that integrates voltage selection and task scheduling together was developed to maximize the energy saved when executing a dependent task set on one or more DVS processors [5].The IP can be solved optimally in polynomial time for the continuous case and some special discrete voltage level cases, or it can be solved efficiently with a heuristic method for the general discrete voltage case.
  • CAD Tools: We are developing Computer Aided Design tools to both aid us in the research and development of new scheduling algorithms, and to aid the end system designer in the development of actual systems.The cad tool consists of three parts: (1) A task creation studio used to either create custom made task sets or to randomly generate a set with desired statistical properties, (2) A scheduler that can take as input a task set developed by (1), a physical processor description and a desired scheduling method to produce a valid voltage schedule, and (3) a simulator that uses the schedules generated from (2) and a physical processor description to determine if the schedule is valid, and find the exact energy consumption.
  • Hardware Experimentation Bed: We are in the process of testing the effectiveness of our scheduling algorithms on Intel's Xscale 80200 Evaluation Platform.This platform was first modified for full voltage scaling by a research group in UCLA's EE department.

References

  1. B. Mochocki, X. Hu. G. Quan. "A Realistic Variable Voltage Scheduling Model for Real-Time Applications." ICCAD 2002.
  2. G. Quan and X. Hu. "Minimum Energy Fixed-Priority Scheduling for Variable Voltage Processors." DATE 2002
  3. G. Quan and X. Hu. "Energy Efficient Fixed-Priority Scheduling for Hard Real-Time Systems." DAC, pages 828-833, 2001.
  4. UCLA, EE research group. "Forming a Xscale 80200 Evaluation Platform based DVS system." http://www.ee.ucla.edu/~shalabh/pads/vscaling.html
  5. F. Yao, A. Demers, and S. Shenker. "A Scheduling Model for Reduced CPU Energy." FOCS, pages 375-384, 1995.
  6. Y. Zang, X. Hu, and D. Chen. "Task scheduling and voltage selection for energy minimization." DAC, 2002.
  7. Y. Zang, X. Hu, and D. Chen. "Energy Minimization of Real-time Tasks on Variable Voltage Processors with Transition Energy Overhead." ASPDAC, 2003