Locality analysis is important since accessing memory is much slower than computing. Compile-time locality analysis can provide detailed program-level feedback for compilers or runtime systems faster than trace-based locality analysis.
In this paper, we describe a new approach to locality analysis based on static parallel sampling. A compiler analyzes loop-based code and generates sampler code which is run to measure locality. Our approach can predict precise cache line granularity miss ratio curves for complex loops with non-linear array references and even branches. The precision and overhead of static sampling are evaluated using PolyBench and a bit-reversal loop. Our result shows that by randomly sampling 2% of loop iterations, a compiler can construct almost exact miss ratio curves as trace based analysis. Sampling 0.5% and 1% iterations can achieve good precision and efficiency with an average 0.6% to 1% the time of tracing respectively. Our analysis can also be parallelized. The analysis may assist program optimization techniques such as tiling, program co-location, cache hint selection and help to analyze write locality and parallel locality.
Fri 22 Jun
|11:00 - 11:25|
Aravind AcharyaIndian Institute of Science, Bangalore, Uday BondhugulaIndian Institute of Science, Albert CohenInria, France / ENS, FranceMedia Attached
|11:25 - 11:50|
|11:50 - 12:15|
Dong ChenUniversity of Rochester, Fangzhou LiuUniversity of Rochester, Chen DingUniversity of Rochester, Sreepathi PaiUniversity of RochesterMedia Attached