Characterizing and predicting program behavior and its variability
Evelyn Duesterwald, Călin Caşcaval, Sandhya Dwarkadas · 2004
To reach the next level of performance and energy efficiency, optimizations are increasingly applied in a dynamic and adaptive manner. Current adaptive systems are typically reactive and optimize hardware or software in response to detecting a shift in program behavior. We argue that program behavior variability requires adaptive systems to be predictive rather than reactive. In order to be effective, systems need to adapt according to future rather than most recent past behavior. We explore the potential of incorporating prediction into adaptive systems. We study the time-varying behavior of programs using metrics derived from hardware counters on two different microarchitectures. Our evaluation shows that programs do indeed exhibit significant behavior variation even at a granularity of millions of instructions. In addition, while the actual behavior across metrics may be different, periodicity in the behavior is shared across metrics. We exploit these characteristics in the design of on-line statistical and table-based predictors. We introduce a new class of predictors, cross-metric predictors, that use one metric to predict another, thus making possible an efficient coupling of multiple predictors. We evaluate these predictors on the SPECcpu2000 benchmark suite and show that table-based predictors outperform statistical predictors by as much as 69% on benchmarks with high variability.
Cited by 108 works. doi:10.1109/pact.2003.1238018
Authors
References
- Automatically characterizing large scale program behavior
- SPEC CPU2000: measuring CPU performance in the New Millennium
- POWER4 system microarchitecture
- Dynamo
- Choosing Representative Slices of Program Execution for Microarchitecture Simulations: A Preliminary Application to the Data Stream
- An integrated circuit/architecture approach to reducing leakage in deep-submicron high-performance I-caches
- Basic block distribution analysis to find periodic behavior and simulation points in applications
- Using generational garbage collection to implement cache-conscious data placement
- The Software-Cache Connection
- Managing multi-configuration hardware via dynamic working set analysis