  Techniques to evaluate a program's cache performance fall into two camps: 1.
Traditional trace-based cache simulators precisely account for sophisticated
real-world cache models and support arbitrary workloads, but their runtime is
proportional to the number of memory accesses performed by the program under
analysis. 2. Relying on implicit workload characterizations such as the
polyhedral model, analytical approaches often achieve problem-size-independent
runtimes, but so far have been limited to idealized cache models.
  We introduce a hybrid approach, warping cache simulation, that aims to
achieve applicability to real-world cache models and problem-size-independent
runtimes. As prior analytical approaches, we focus on programs in the
polyhedral model, which allows to reason about the sequence of memory accesses
analytically. Combining this analytical reasoning with information about the
cache behavior obtained from explicit cache simulation allows us to soundly
fast-forward the simulation. By this process of warping, we accelerate the
simulation so that its cost is often independent of the number of memory
accesses.
