Locality Phase Prediction
Xipeng Shen, Yutao Zhong, and Chen Ding
As computer memory hierarchy becomes adaptive, its performance
increasingly depends on forecasting the dynamic program locality.
This paper presents a method that predicts the locality phases of a
program by a combination of locality profiling and run-time
prediction. By profiling a training input, it identifies locality
phases by sifting through all accesses to all data elements using
variable-distance sampling, wavelet filtering, and optimal phase
partitioning. It then constructs a phase hierarchy through grammar
compression. Finally, it inserts phase markers into the program
using binary rewriting. When the instrumented program runs, it uses
the first few executions of a phase to predict all its later
Compared with existing methods based on program code and execution
intervals, locality phase prediction is unique because it uses
locality profiles, and it marks phase boundaries in program code.
The second half of the paper presents a comprehensive evaluation.
It measures the accuracy and the coverage of the new technique and
compares it with best known run-time methods. It measures its
benefit in adaptive cache resizing and memory remapping. Finally,
it compares the automatic analysis with manual phase marking. The
results show that locality phase prediction is well suited for
identifying large, recurring phases in complex programs.
Download the paper in pdf format.