Locality analysis through static parallel sampling
Locality analysis through static parallel sampling
复制标题
DOI：
10.1145/3192366.3192402
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
Dong Chen;Fangzhou Liu;C. Ding;Sreepathi Pai
中科院分区：
文献类型：
--
作者：
Dong Chen;Fangzhou Liu;C. Ding;Sreepathi Pai
局部性分析很重要，因为访问内存比计算慢得多。编译时局部性分析可以比基于跟踪的局部性分析更快地为编译器或运行时系统提供详细的程序级反馈。本文描述了一种基于静态并行采样的局部性分析新方法。编译器分析基于循环的代码并生成采样器代码，该采样器代码运行以测量局部性。对于具有非线性数组引用甚至分支的复杂循环，我们的方法可以预测精确的缓存线粒度未命中比曲线。静态采样的精度和开销使用PolyBitch和比特反转环路进行了评估。我们的结果表明，通过随机采样2%的循环迭代，编译器可以构建几乎准确的错失率曲线，作为基于轨迹的分析。采样0.5%和1%的迭代可以达到很好的精度和效率，平均跟踪时间分别为0.6%到1%。我们的分析也可以并行化。该分析可以帮助诸如分片、程序协同定位、高速缓存提示选择之类的程序优化技术，并且有助于分析写入局部性和并行局部性。
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.