Caches As Filters: A Framework for the Analysis of Caching Systems

This paper introduces a new analytical framework for analyzing and designing caches. It consists of four major parts: TSpec notation, into which reference traces can be transformed; equivalence classes, which abstract away chance effects of address bindings and specific inputs; the functional filter model, which operates on TSpec traces and provides a formal description of cache operation; and new metrics, which evaluate cache performance. This paper gives an overview of TSpec notation and equivalence classes, and then illustrates how the functional filter model can be used to derive better understanding of cache behavior. 1