Prediction in Projection: Computer Performance Forecasting, a Dynamical Systems Approach

摘要

Recent work in the field of dynamical systems provides evidence that computer systems are nonlinear-deterministic dynamical systems. This implies the existence of a deterministic update rule, which, in turn, implies the existence of a deterministic forecasting rule for the state variables of a running computer. Even a short-term prediction of these quantities, if accurate, could be effective in tailoring system resources on-the-fly to the dynamics of a computing application. For example, a good prediction of processor load could allow a computer to increase its energy efficiency by dynamically turning off unused CPUs, and then turning them back on based on the programs predicted needs. To explore this, I use a custom measurement infrastructure, delay-coordinate embedding and nonlinear time-series analysis to forecast processor load and cache performance of a set of simple C programs running on an Intel Core2 Duo. This proved to be quite effective. However, the use of traditional embedding techniques `on the flyu27 is impractical due to the time required to correctly perform the processing and post-processing of the data. My alternative to this is to use arbitrary low-dimensional projections. While this is not consistent with the requirements in the current literature, recent work by Mischaikow suggests that this alternative might work. I verified this conjecture, showing that forecasts based on two-dimensional projections are largely as effective as strategies that use the full embedded dynamics. This is in contrast to the current view in the nonlinear dynamics community that a one-to-one delay map is sufficient for successful prediction using delay coordinate embedding. My results suggest that this may not be a necessary condition. The success of the projection-based forecasting schemes brings into questions the need for full topological conjugacy in forecasting schema. The results presented here suggest ways of improving computer design at a systems level; they also provide evidence to support the use of semi-conjugacies in forecasting schemes.