Accession Number : ADA196912
Title : Efficient Analysis of Caching Systems
Descriptive Note : Doctoral thesis
Corporate Author : AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH
Personal Author(s) : Thompson, James G.
Report Date : 1988
Pagination or Media Count : 262
Abstract : 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.
Descriptors : *COMPUTER FILES , *SYSTEMS ANALYSIS , CONSISTENCY , DISKS , EFFICIENCY , HIERARCHIES , MEMORY DEVICES , MULTIPROCESSORS , NETWORKS , PROCESSING EQUIPMENT , SIZES(DIMENSIONS) , STACKING
Subject Categories : COMPUTER HARDWARE
Distribution Statement : APPROVED FOR PUBLIC RELEASE