Low Overhead Online Phase Predictor and Classifier

It is well known that programs exhibit time varying behavior. For example, some parts of the execution are memory bound while others are CPU bound. Periods of stable behavior are called program phases. Classifying the program behavior by the average over the whole execution can therefore be misleading, i.e., the program would appear to be neither CPU bound nor memory bound. As several important dynamic optimizations are done differently depending on the program behavior, it is important to keep track of what phase the program is currently executing and to predict what phase it will enter next. In this master thesis we develop a general purpose online phase prediction and classification library. It keeps track of what phase the program is currently executing and predicts what phase the program will enter next. Our library is non-intrusive, i.e., the program behavior is not changed by the presence of the library, and transparent, i.e., it does not require the tracked application to be recompiled, and architecture-independent, i.e., the same phase will be detected regardless of the processor type. To keep the overhead at a minimum we use hardware performance counters to capture the required program statistics. Our evaluation shows that we can capture and classify program phase behavior with on average less then 1% overhead, and accurately predict which program phase the application will enter next