Analytical modeling of cache behavior for affine programs
Analytical modeling of cache behavior for affine programs
复制标题
仿射程序缓存行为的分析建模
DOI：
10.1145/3158120
复制
发表时间：
2017
影响因子：
--
通讯作者：
P. Sadayappan
中科院分区：
文献类型：
--
作者：
Wenlei Bao;S. Krishnamoorthy;L. Pouchet;P. Sadayappan
优化编译器实现程序转换策略，旨在通过利用数据缓存层次结构来减少进出主存的数据移动。然而，而不是试图最大限度地减少高速缓存未命中的数量，非常近似的成本模型使用，由于缺乏精确的编译时模型的分层高速缓存未命中。高速缓存未命中分析的当前实践状态是基于精确的模拟。然而，模拟需要与数据集/问题大小成比例的时间，以及要评估的不同缓存配置的数量。本文采取了一种根本不同的方法，通过专注于静态控制流的多面体程序。而不是依赖于昂贵的模拟，一个封闭的形式的解决方案，在一组关联缓存层次结构的未命中建模。该解决方案可以在编译时启用程序转换选择以优化缓存未命中。已经开发了一个实施这一方法的工具，并用于验证框架。
Optimizing compilers implement program transformation strategies aimed at reducing data movement to or from main memory by exploiting the data-cache hierarchy. However, instead of attempting to minimize the number of cache misses, very approximate cost models are used, due to the lack of precise compile-time models for misses for hierarchical caches. The current state of practice for cache miss analysis is based on accurate simulation. However, simulation requires time proportional to the dataset/problem size, as well as the number of distinct cache configurations of interest to be evaluated. This paper takes a fundamentally different approach, by focusing on polyhedral programs with static control flow. Instead of relying on costly simulation, a closed-form solution for modeling of misses in a set associative cache hierarchy is developed. This solution can enable program transformation choice at compile time to optimize cache misses. A tool implementing the approach has been developed and used for validation of the framework.