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  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