Efficient Analysis of Caching Systems

摘要

This dissertation describes innovative techniques for efficiently analyzing a wide variety of cache designs, and uses these techniques to study caching in a network file system. The techniques are significant extensions to the stack analysis technique (Mattson et al., 1970) which computes the read miss ratio for all cache sizes in a single trace-driven simulation. Stack analysis is extended to allow the one-pass analysis of: 1) writes in a write-back cache, including periodic write-back and deletions, important factors in file system cache performance; 2) sub-block or sector caches, including load-forward prefetching; 3) multi-processor caches in a shared-memory system, for an entire class of consistency protocols, including all of the well-known protocols; and 4) client caches in a network file system, using a new class of consistency protocols. The techniques are completely general and apply to all levels of the memory hierarchy, from processor caches to disk and file system caches. The dissertation also discusses the use of hash tables and binary trees within the simulator to further improve performance for some types of traces. Using these techniques, the performance of all cache sizes can be computed in little more than twice the time required to simulate a single cache size, and often in just 10% more time. (KR)