Today's computer systems are more powerful than ever, but have become so complex that it is now difficult for programmers to produce high-performance software. Even slight changes in programs or differences in a user's system can cause dramatic slowdowns. Currently, there is no way to guarantee that a program will perform as well as it did during testing. This situation makes it extremely difficult to track down the sources of inefficiencies or repair them. The result is reduced power and computational efficiency on servers, and a degraded user experience on client platforms.
This research aims to deliver reliable performance on modern computer systems. By introducing randomness into the way a computer runs programs, a reliably performant system will significantly reduce the probability that any small change will have a large impact on performance. For instance, consider a cache miss caused by a conflict. With standard caches, repeated access to the same elements would always cause misses, degrading performance. In a randomized cache or with randomized object placement, it would be very unlikely for the same line to be repeatedly evicted. The investigators are designing and evaluating the use of both randomized algorithms in software and hardware, separately and in combination, to remedy the numerous sources of pathological behavior in modern systems. The result will enable performance-portable applications that are immune to unfortunate interactions with microprocessor components.
Enhanced safety and efficiency features in cars and planes have the potential to save thousands of lives and millions of dollars each year, but the computational power of existing real-time systems cannot meet the demands of these new applications. Modern processors are vastly more powerful than typical real-time systems, but the hardware designs that make these processors so fast are directly at odds with the requirements for real-time systems. A particularly unlucky task or combination of tasks can lead a processors into a "bad state" where programs run ten or a hundred times slower than normal. Conventional real-time systems are forced to assume that tasks will always run in this bad state, leaving significant computational resources unused just in case the system does run slowly. This project makes the performance of modern hardware predictable and probabilistically analyzable, enabling "probabilistic real-time systems": systems that can use significantly more of a processor's computational power in exchange for a vanishingly small probability of a missed deadline due to "bad states". Our approach is to constantly shuffle software components so that repeatedly ending up in a bad state---and thus running too slow---is as unlikely as winning the lottery hundreds of times in a row. Probabilistic real-time systems can use the increased computational power of modern hardware---power that is required for new safety and efficiency applications---without significantly sacrificing timing guarantees. Applications include reducing fuel cost via more efficient steering and engine controls, and adding safety by incorporating sophisticated models of airflow to reduce turbulence or predicting vehicle trajectories to avoid collisions. This project also represents a fundamental shift in the way computer scientists approach performance evaluation. While computer hardware is composed of many simple, well-understood components, the dynamic interactions of these components make it impossible to reliably reason about software performance. Other disciplines rely on careful experimental design and powerful statistical techniques to draw conclusions in the face of uncertainty, but there are significant technical obstacles to the adoption of these techniques for performance evaluation. Our work makes it possible for computer scientists to perform rigorous experiments, and provides a sound statistical framework for drawing conclusions from these experiments.
