Thu 11 Jan 2018 11:45 - 12:10 at Watercourt - Program Analysis I Chair(s): Tachio Terauchi

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.

Thu 11 Jan
Times are displayed in time zone: (GMT-07:00) Tijuana, Baja California change

10:30 - 12:10: Research Papers - Program Analysis I at Watercourt
Chair(s): Tachio TerauchiWaseda University
POPL-2018-papers10:30 - 10:55
POPL-2018-papers10:55 - 11:20
POPL-2018-papers11:20 - 11:45
Marek ChalupaMasaryk University, Krishnendu ChatterjeeIST Austria, Andreas PavlogiannisIST Austria, Kapil VaidyaIIT Bombay, Nishant SinhaIBM Research
POPL-2018-papers11:45 - 12:10
Wenlei BaoOhio State University, Sriram KrishnamoorthyPacific Northwest National Laboratories, Louis-Noël PouchetColorado State University, P. SadayappanOhio State University