Reduced-Order Dynamical Models for Effective Power Management in Computer Systems

该项目涉及用于降低微处理器芯片功耗的降阶建模和预测技术。这些系统的现代电源管理解决方案采用极其简单的控制策略-例如，如果处理器的负载超过某个阈值，则将时钟频率降低固定的预定量。控制理论和非线性动力学团体开发的方法早已超越了这种复杂程度。特别是，基于模型的预测可以极大地改善电力管理，但前提是所涉及的模型是准确的。例如，如果一个人可以预测到一个特定的计算线程将在接下来的0.6秒内停滞不前，等待来自计算机内存的数据，那么就可以在那段时间内将该线程置于低功率保持状态。然而，预测像现代计算机这样的复杂的非线性动力系统的未来行为是一个严重的挑战-如果一个人使用假设线性和/或时间不变性的数学，这几乎是不可能的，直到最近在计算机系统社区中一直是这样的规则。本文提出的方法使用了一种新的降阶建模策略，该策略首先将时间序列数据转换为称为tau-Return映射的2D表示。这种表示的力量在于，它显式地展示了时间关系，将时间序列中的时间模式‘展开’到一个空间维度。对转换后的数据进行处理的预测模型可用于创建对多核处理器中处理器和内存负载的准确预测：这些信息可用于动态调整计算以适应资源，反之亦然。微处理器芯片是当今使用的最关键的工程系统之一，降低其功耗在无处不在计算的现代世界中是一个重要的挑战。为了有效地管理电力使用，必须能够动态地使计算适应资源。监控是解决这个问题的一个关键因素：例如，如果知道多核处理器中的哪些处理单元繁忙，哪些处理单元空闲，就可以将工作从前者重新路由到后者。预测是另一个关键因素：反应性地进行这种重新分配是好的，但主动地进行-基于对这些负载和水平的预测--会好得多。然而，现代计算机系统的复杂性使得预测变得非常困难。这些系统有大量的内部变量，这些变量以复杂的、非线性的方式相互作用，并且只有几个变量可以被监控。这里提出的方法使用数学映射从这些可以从运行中的计算机测量的狭窄数据流中梳理出重要的时间关系。它使用充分尊重底层系统复杂性和非线性的数学方法在这个新的空间建立预测模型-不同于通常将计算机系统视为线性和时不变的传统方法。它使用这些预测模型，通过根据可用资源定制计算负载来节省电力，反之亦然。这项工作的潜在影响是重大的，特别是考虑到最近多核处理器的设计演变和移动设备的快速扩散。由于计算机是如此常见和关键，这项工作有可能为科学、工程和更远的领域做出贡献。

This project concerns reduced-order modeling and forecasting techniques for reducing power use in microprocessor chips. Modern power management solutions for these systems employ extremely simple control strategies---e.g., lowering the clock frequency by a fixed, pre-determined amount if a processor's load crosses some threshold. The methods developed by the control theory and nonlinear dynamics communities have long since moved beyond this level of sophistication. Model-based prediction, in particular, could enable vastly improved power management, but only if the models involved are accurate. If one could predict that a particular thread of computation would be bogged down for the next 0.6 seconds waiting for data from the computer's memory, for instance, one could put that thread on a low-power hold for that time period. Prediction of the future behavior of a complex nonlinear dynamical system like a modern computer is a serious challenge, however---and it is all but impossible if one uses mathematics that assumes linearity and/or time invariance, as has been the rule until recently in the computer systems community. The approach proposed here uses a novel reduced-order modeling strategy that first transforms the time-series data into a 2D representation called a tau-return map. The power of this representation is that it brings out temporal relationships explicitly, `unfolding' the temporal patterns in the time series into a spatial dimension. Forecast models working on this transformed data can be used to create accurate predictions of processor and memory loads in multicore processors: information that can be used to dynamically adapt the computation to the resources, and vice versa.Reducing the power use of microprocessor chips, one of the most critical classes of engineered systems in use today, is an important challenge in the modern world of ubiquitous computation. In order to manage power use effectively, one must be able to dynamically adapt the computation to the resources. Monitoring is one key element in solving that problem: if one knew which processing units in a multi-core processor were busy and which ones were idle, for instance, one could re-route work from the former to the latter. Forecasting is another key element: doing that kind of reallocation reactively is good, but doing it PROACTIVELY---based on a prediction of those loads and levels---would be far better. The complexity of modern computer systems makes prediction very difficult, however. These systems have large numbers of internal variables that interact in complex, nonlinear ways, and only a few of those variables can be monitored. The approach proposed here uses a mathematical mapping to tease the important temporal relationships out of these narrow streams of data that can be measured from a running computer. It builds forecast models in that new space using mathematics that fully respects the complexity and nonlinearity of the underlying system---unlike traditional approaches, which generally treat computer systems as linear and time-invariant. It uses those forecast models to save power by tailoring the computational load to the available resources, and vice versa. The potential impact of this work is significant, particularly in view of the recent design evolution of multicore processors and the rapid proliferation of mobile devices. Because computers are so common and so critical, this work has the potential to contribute to science, engineering, and well beyond.