AF: Small: Algorithmic Energy Management in New Information Technologies

University Of Pittsburgh, Pittsburgh PA

Investigators

Abstract

Due to the convergence of several trends (most notably Moore's law) about a decade ago, the related quantities of power, energy, and temperature rapidly emerged as the most important computational resources and constraints in many information technologies. We are thus about a decade into a green computing revolution in which many information technologies are being redesigned with energy consumption as a first class design criterion. One of the many technological challenges that arise as part of this green computing revolution are new algorithmic resource management problems, in which the resource that must be managed is energy related. Over the last several decades, when computer instructions ("time") and computer memory ("space") were the dominant computational resources, computer science researchers developed many techniques for designing time and space efficient algorithms, and for analyzing the time and space required by particular algorithms on simple models of a computer. The ability to reason abstractly about time and space in simple computational models is undoubtedly a valuable skill for computer scientists and software engineers. However, the physics of energy is sufficiently different than the physics of time and space that the standard models for studying time and space as computational resources do not seem to be the appropriate models for studying energy as a computational resource. Thus the PI will develop new models for studying energy as a computational resource. Necessitated by the nonlinear nature of the relationship between energy and performance, the PI will develop new nonlinear algorithmic design and analysis techniques. The long term payoff of the project is expected to be an algorithmic theory of energy as a computational resource in simple models. This theory will eventually be taught to future software engineers, and will serve these software engineers, when faced with problems in which power/energy/temperature is the key scarce resource, just as the current algorithmic theory of time as a computational resource now serves them. The project will support training several undergraduate and Ph.D. students at the University of Pittsburgh in algorithmic energy management. The project will support visits by outside Ph.D. students and post-docs interested in beginning or continuing a research program in algorithmic energy management. The PI will participate regularly in green computing academic conferences and will facilitate communication between the algorithmic and computer systems research communities. The PI will specifically investigate algorithmic energy management problems within four information technology settings: 1. Online scheduling of power heterogeneous processors: Simulation studies indicate that heterogeneous multiprocessor architectures potentially offer higher performance than current homogeneous multiprocessor architectures. It is also known that traditional priority scheduling algorithms that work well for single processor and uniform processor architectures do not work well for heterogeneous multiprocessor architectures. The main goal is to find algorithms that provably work well for heterogeneous multiprocessor architectures. 2. Computing optimal energy tradeoff schedules for speed scalable processors: Energy and time performance are generally conflicting goals. The goal is to understand and efficiently compute schedules that optimally balance these conflicting demands. 3. Computing near energy optimal routings in networks of speed scalable routers with shutdown: The two most common energy management mechanisms are power heterogeneous components and components that may be shut down. When these are both included in a computer network, the standard routing problem becomes more complex as the energy used per router is neither concave nor convex. The goal is to understand and efficiently compute good routings in this setting. 4. Energy efficient circuits: Near threshold computing is a potential approach to more energy efficient computing on the circuit level. However, while lowering the supply voltage decreases power, it increases the probability of functional failures, thus necessitating more fault-tolerant (and thus larger) circuits. The goal is to understand and efficiently compute the most energy efficient way to balance the competing demands of the energy used per gate and the number of gates.