Thompson and Smith describe stack algorithms for the analysis of cache memories. They adopt the view that cache memories occupy one level in a hierarchy of memory types. The authors use trace-driven simulation to extend the stack analysis technique to the write-back and to sector or subblock caches, and they observe that “the ability to collect transfer ratios, considering both reads and writes, for all memory sizes in a single pass reduces simulation time by as much as 90% compared to running 8–10 individual simulations, making this metric much more reasonable to collect.”

This well-illustrated paper excels by virtue of its clarity and completeness. The authors have taken a theoretical approach, and they address an audience of professionals. This subject is of major interest to computer systems designers, especially those working on multiprocessor caches and network file systems.