Modern optimizing compiler design integrates program transformation strategies aimed at reducing data movement to/from main memory, exploiting the data cache hierarchy. But in reality, the effect of these transformations on the actual cache miss count is ignored in compilers, due to the lack of precise compile-time models of misses for hierarchical caches. Going a step further, when considering real-life systems, the data is vulnerable to hardware faults (e.g., bit flip) when it is stored in a cache without automatic error detection/correction. Determining the cache vulnerability of a program requires the computation of the lifetime of each data element in the cache, and the current state of practice for both cache miss analysis as well as vulnerability analysis is based on accurate simulation.
This paper takes a fundamentally different approach, made possible by focusing on polyhedral programs with static control flow: instead of relying on costly simulation, this paper develops the first closed-form solution for exact modeling of misses in a set-associative cache hierarchy. It then develops the first closed-form solution to cache vulnerability analysis for general polyhedral programs, enabling simulation-less selection of program transformations at compile-time to optimize cache misses, vulnerability, or a mix of both. A push-button tool implementing the approach is developed and used for extensive validation of the complete framework.
Conference DayThu 11 JanDisplayed time zone: Tijuana, Baja California change
10:30 - 12:10
|Inference of Static Semantics for Incomplete C Programs|
Leandro T. C. MeloUFMG, Rodrigo Geraldo RibeiroUFOP, Marcus Rodrigues de AraújoUFMG, Fernando Magno Quintão PereiraUFMGPre-print
|Optimal Dyck Reachability for Data-dependence and Alias Analysis|
|Data-centric Dynamic Partial Order Reduction|
|Analytical Modeling of Cache Behavior for Affine Programs|