This methodology has three primary components. The first is the development of a formal system for describing memory traces (sequences of addresses). This notation consists of constructs for common reference patterns and standard operators for combining them. With it, trace descriptions can be written to highlight the structure in the underlying reference stream. These descriptions are used in several ways: for human-to-human communication (the trace descriptions are compact, yet human-readable), for specifying input to a "trace generator", or, as noted below, as a formal system that can be manipulated to expose the effect of various parts of a memory hierarchy.
The second component is a formal framework for the analysis. This framework is inspired by viewing caches as filters that transform one trace (Tin) into a second trace (Tout) containing only a subset of the addresses in the first (Tout = F(Tin)). By defining F as a transformation on the formal description of a trace, we expect to be able to analytically predict the combined behavior of various cache structures and hierarchical organizations.
The third component consists of quantitative metrics that highlight the dynamic behavior of a reference stream and its interaction with different levels in the cache hierarchy. Specifically, we are interested in metrics that are more indicative of the quality of a cache system than simple hit rate. The two such metrics we have developed to date, instantaneous hit rate and instantaneous locality, are described in the MASCOTS'98 paper, "Caches As Filters: A New Approach to Cache Analysis" by Weikle, McKee, and Wulf. Initial results suggest these measures provide a good basis for assessing whether a cache has been effective. More research is required to directly relate these and other, non-aggregate measures to how a cache system should be designed.