Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Fast and exact analysis for LRU caches   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 a 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.

26
The categories of this paper are: bayes-an
36
The categories of this paper are: cmp-lg
35
The categories of this paper are: mtrl-th
16
The categories of this paper are: stat
37
The categories of this paper are: supr-con
6
The categories of this paper are: astro-ph
33
The categories of this paper are: plasm-ph
4
The categories of this paper are: cond-mat
2
The categories of this paper are: math
5
The categories of this paper are: gr-qc
11
The categories of this paper are: hep-lat
31
The categories of this paper are: ao-sci
25
The categories of this paper are: patt-sol
10
The categories of this paper are: q-bio
32
The categories of this paper are: atom-ph
28
The categories of this paper are: alg-geom