Refining Cache Behavior Prediction Using Cache Miss Paths
Authors: Kartik Nagar, Y.N.Srikant
Abstract:
Worst Case Execution Time (WCET) is an important metric for programs running on
real-time systems, and finding precise estimates of a program's WCET is crucial to
avoid wastage of hardware resources and to improve the schedulability of task sets.
Caches have a major impact on a program's execution time, and accurate estimation of
a program's cache behavior can lead to significant reduction in its estimated WCET.
The traditional approach to cache analysis generally targets the worst-case cache
behavior of individual cache accesses, and provides a safe hit-miss classification
for every individual access. In this work, we show that these classifications are
not sufficient to precisely capture cache behavior, since they apply to individual
accesses, and often, more precise predictions can be made about groups of accesses.
Further, memory accesses inside loops may show the worst-case behavior only for a
subset of the iteration space. In order to predict such behavior in a scalable
fashion, we use the fact that the cache behavior of an access mostly depends only
on the memory accesses made in the immediate vicinity, and hence we analyze a small,
fixed size neighborhood of every access with complete precision and summarize the
resulting information in the form of cache miss paths. A variety of analyses are
then performed on the cache miss paths to make precise predictions about cache
behavior. We also demonstrate precision issues in Abstract Interpretation based Must
and Persistence cache analysis which can be easily solved using cache miss paths.
Experimental results over a wide range of benchmarks demonstrate precision
improvement in WCET of multi-path programs over AI-based approaches, and we also
show how to integrate our approach with other micro-architectural analysis such as
pipeline analysis.
pdf