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.
Normal 0 false false false EN-US X-NONE X-NONE The main goal of this grant was to explore algorithms and computational methods that take energy consumption into account, and explore ways to minimize energy use while performing various computational tasks. A wide number of topics has been considered, ranging from energy consumption in wireless communication to energy consumption in data processing and cloud computing. One of the highlights of work funded by this grant was the resolution of an important problem of wireless radio synchronization among N processors. There are multiple additional results that acknowledge this grant, but due to space constraints we highlight only one of these results. As background, having a radio on is energy-wise very expensive, and it is beneficial to power the radio down as much as possible by wireless processors. A fascinating question of how N processors can synchronize their clocks while minimizing time that is required to achieve this task was considered in two papers. In the article authored by Milan Bradonjic, Eddie Kohler, Rafail Ostrovsky titled "Near-optimal radio use for wireless network synchronization". Theoretical Computer Science 453: 14-28 (2012) we show that square root of N uses of radio utilization is necessary for each processor. This paper achieved near-optimal solution, but used a randomized algorithm. In the follow-up paper authored by Leonid Barenboim, Shlomi Dolev, and Rafail Ostrovsky, titled "Deterministic and Energy-Optimal Wireless Synchronization." DISC 2011: 237-251, we show that an optimum solution of square root of N time steps is possible, using a deterministic algorithm. Hence, taken together, these two papers completely resolve the important practical question of optimal radio use for wireless processor synchronization.
