Locality Phase Prediction
Xipeng Shen, Yutao Zhong, and Chen Ding
ABSTRACT
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 executions.
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.
Copyright notice