Blogs (1) >>
POPL 2019
Sun 13 - Sat 19 January 2019 Cascais, Portugal
Fri 18 Jan 2019 17:21 - 17:43 at Sala II - Program Analysis II Chair(s): Michael Emmi

For applications in worst-case execution time analysis and in security, it is desirable to statically classify memory accesses into those that result in cache hits, and those that result in cache misses. Among cache replacement policies, the least recently used (LRU) policy has been studied the most and is considered to be the most predictable.

The state-of-the-art in LRU cache analysis presents a tradeoff between precision and analysis efficiency: The classical approach to analyzing programs running on LRU caches, an abstract interpretation based on an range abstraction, is very fast but can be imprecise. An exact analysis was recently presented, but, as a last resort, it calls a model checker, which is expensive.

In this paper, we develop an analysis based on abstract interpretation that comes close to the efficiency of the classical approach, while achieving exact classification of all memory accesses as the model-checking approach. Compared with the model-checking approach we observe speedups of several orders of magnitude. As a secondary contribution we show that LRU cache analysis problems are in general NP-complete.

Fast and exact analysis for LRU caches (presentation.pdf)451KiB

Fri 18 Jan
Times are displayed in time zone: Greenwich Mean Time : Belfast change

16:37 - 17:43: Program Analysis IIResearch Papers at Sala II
Chair(s): Michael EmmiSRI International
16:37 - 16:59
Efficient Automated Repair of High Floating-Point Errors in Numerical Libraries
Research Papers
Xin YiNational University of Defense Technology, Liqian ChenNational University of Defense Technology, Xiaoguang MaoNational University of Defense Technology, Tao JiNational University of Defense Technology
Link to publication DOI Media Attached File Attached
16:59 - 17:21
Efficient Parameterized Algorithms for Data Packing
Research Papers
Krishnendu ChatterjeeIST Austria, Amir Kafshdar GoharshadyIST Austria, Nastaran OkatiFerdowsi University of Mashhad, Andreas PavlogiannisEPFL, Switzerland
Link to publication DOI Pre-print Media Attached File Attached
17:21 - 17:43
Fast and exact analysis for LRU caches
Research Papers
Valentin TouzeauUniv. Grenoble Alpes, Claire MaizaVerimag, France, David MonniauxCNRS, VERIMAG, Jan ReinekeSaarland University
Link to publication DOI Media Attached File Attached