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.