Fri 22 Jun 2018 11:50 - 12:15 at Grand Ballroom AB - Optimization and Locality Chair(s): Milind Kulkarni

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
Times are displayed in time zone: (GMT-04:00) Eastern Time (US & Canada) change

11:00 - 12:15: PLDI Research Papers - Optimization and Locality at Grand Ballroom AB
Chair(s): Milind KulkarniPurdue University
pldi-2018-papers11:00 - 11:25
Aravind AcharyaIndian Institute of Science, Bangalore, Uday BondhugulaIndian Institute of Science, Albert CohenInria, France / ENS, France
Media Attached
pldi-2018-papers11:25 - 11:50
Simon MollSaarland University, Germany, Sebastian HackSaarland University, Germany
Media Attached
pldi-2018-papers11:50 - 12:15
Dong ChenUniversity of Rochester, Fangzhou LiuUniversity of Rochester, Chen DingUniversity of Rochester, Sreepathi PaiUniversity of Rochester
Media Attached