CIF: Small: Energy-Efficient Scheduling and Load Balancing

University Of California-Los Angeles, Los Angeles CA

Investigators

Abstract

Modern computer systems consume substantial amounts of energy, and energy costs for large computing facilities can reach into the billions of dollars. At the same time, battery power is a limiting factor for cellular phones and other small mobile devices. This proposal aims to design and implement scheduling and load-balancing algorithms which better optimize for energy-efficiency without sacrificing quality of service. Since these algorithms can be implemented in software (without the design or construction of new devices), they are a promising direction to deal with the growing demand for energy to power computation. Scheduling and load-balancing are naturally online problems, where tasks arrive during the run of the algorithm and are not known in advance. The intellectual merit of this proposal includes improving our techniques for producing provably competitive results in such online problems, as well as exploring new hybrid models in cases where the tasks are partially predictable. The proposal aims to produce algorithms under very general relationships between energy and task completion rate (prior work has generally assumed a quadratic relationship, which is not realistic) and to permit more general representations of quality of service. Algorithmic techniques for these problems include linear program rounding, online primal-dual, and flow-based analysis for variants of online weighted matching. The broader impact of this proposal involves the implementation and testing of algorithms, potentially leading to substantial savings in energy. The implementations also require dealing with a number of practical problems, such as collecting data about tasks on arrival (algorithms typically assume that information like priorities and workloads are known) and designing effective user interfaces. These will lead to a number of excellent undergraduate projects in which students can be exposed to advanced theoretical techniques in algorithm design while also producing energy-conserving software for real devices.