AF: Small: Algorithmic Energy Management in New Information Technologies

由于大约十年前几种趋势（最著名的是摩尔定律）的融合，功率、能量和温度的相关量迅速成为许多信息技术中最重要的计算资源和约束。因此，我们进入绿色计算革命大约十年，其中许多信息技术正在重新设计，能源消耗作为第一级设计标准。作为这场绿色计算革命的一部分而出现的许多技术挑战之一是新的算法资源管理问题，其中必须管理的资源是与能量相关的。在过去的几十年里，当计算机指令（"时间"）和计算机存储器（"空间"）是主要的计算资源时，计算机科学研究人员开发了许多技术来设计时间和空间有效的算法，并用于分析计算机的简单模型上的特定算法所需的时间和空间。对于计算机科学家和软件工程师来说，在简单的计算模型中抽象地推理时间和空间的能力无疑是一项宝贵的技能。然而，能量物理学与时间和空间物理学有着很大的不同，研究作为计算资源的时间和空间的标准模型似乎并不适合研究作为计算资源的能量，因此PI将开发新的模型来研究作为计算资源的能量。由于能量和性能之间关系的非线性性质，PI将开发新的非线性算法设计和分析技术。该项目的长期回报预计将是一个算法理论的能源作为一个计算资源在简单的模型。这一理论最终将被教授给未来的软件工程师，并将服务于这些软件工程师，当他们面临的问题中，功率/能量/温度是关键的稀缺资源，就像目前的算法理论的时间作为一种计算资源，现在为他们服务。匹兹堡大学算法能源管理专业的学生。该项目将支持外部博士的访问。有兴趣开始或继续算法能源管理研究计划的学生和博士后。PI将定期参加绿色计算学术会议，并将促进算法和计算机系统研究社区之间的沟通。PI将专门研究四种信息技术环境中的算法能源管理问题：1.电力异构处理器的在线调度：模拟研究表明，异构多处理器架构可能提供更高的性能比目前的同构多处理器架构。还已知的是，对于单处理器和统一处理器架构工作良好的传统优先级调度算法对于异构多处理器架构不工作良好。主要目标是找到可证明适用于异构多处理器体系结构的算法。计算速度可扩展处理器的最佳能量权衡计划：能量和时间性能通常是相互冲突的目标。我们的目标是理解和有效地计算时间表，最佳地平衡这些相互冲突的需求。3.在具有关机的速度可扩展路由器的网络中计算近能量最优路由：两种最常见的能量管理机制是功率异构组件和可能关机的组件。当这两者都包含在计算机网络中时，标准路由问题变得更加复杂，因为每个路由器使用的能量既不是凹的也不是凸的。我们的目标是理解和有效地计算在这种情况下良好的路由。4.高能效电路：近阈值计算是在电路级实现更高能效计算的潜在方法。然而，虽然降低电源电压会降低功率，但它会增加功能故障的可能性，因此需要更多的容错（因此更大）电路。我们的目标是理解和有效地计算最节能的方式来平衡每个门使用的能量和门的数量的竞争需求。

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.