Login
Computer Science @ Rochester
Monday, April 26, 2004
11:00 AM
CSB 209
Ph.D. Thesis Proposal
Xipeng Shen
University of Rochester
Study of Program "Seasons"---Program Temporal Analysis
Recent years have seen a strong trend of dynamic techniques in both computer architecture and software optimization areas. Dynamic techniques require temporal behavior analysis to forecast program behaviors. This proposal proposes a novel method---locality phase analysis---to overcome the three big challenges facing all program temporal behavior analysis: locality of phases, prediction performance, and analysis on object-oriented and parallel programs.

Our experiment on sequential imperative programs show the successes of locality phase analysis. Our method predicts the locality phases of a program through profiling and run-time prediction. By profiling a training input, the analysis sifts through all accesses to all data elements using variable-distance sampling, wavelet filtering, and optimal phase partitioning. It then identifies the phase hierarchy through grammar compression. Finally, it inserts phase markers into a program using binary rewriting. When the instrumented program runs, it uses the first few executions of a phase to predict all its later executions. For programs with consistent phase behavior, the new method predicts the phase length and locality with near perfect accuracy for executions that are orders of magnitude larger. Compared with methods based on code, intervals and their combinations, the new analysis is unique because it uses both code and locality information and does not use fixed-size windows.

The goal of this proposal is to extend locality phase analysis to a wider range---object-oriented and parallel programs. This study will yield better understanding and new optimization opportunities to those programs. It may generate remarkable effects on modern adaptation techniques for increasing performance, reducing energy, and other improvements to the computer system design.