Analysis of multi-megabyte secondary CPU cache memories
R. E. Kessler · Minds at UW (University of Wisconsin) · 1992
This dissertation investigates multi-megabyte secondary caches. In a multi-level cache hierarchy, secondary caches service processor memory references that cannot be serviced by smaller and faster primary caches. With faster processors and expanding main memories, a multi-megabyte cache is increasingly vital because it shields processor memory references from costly main memory accesses, even when the processor references a large address space. Multi-megabyte secondary caches allow processors to execute at the speeds they are capable of, even when there is a large processor-to-main-memory speed gap. This analysis uses a new collection of memory address traces that is appropriate for multi-megabyte cache simulation. These traces thoroughly characterize several large work-loads, and are long enough (billions of instructions) to overcome multi-megabyte cache cold-start. This dissertation includes the first comparison of two previously-proposed trace-sampling techniques that can reduce long-trace simulation requirements: set sampling and time sampling. Under a range of conditions, set sampling produces more accurate cache performance estimates with less trace data than time sampling. This dissertation examines many alternative cache designs. It shows that multi-megabyte secondary caches are extremely useful with large processor-to-main-memory speed gaps. Furthermore, associativity is needed for smaller secondary caches, but may not be necessary in multi-megabyte caches; multi-megabyte cache block sizes should be larger than for smaller caches, and the block size that equals the fixed latency and transfer time miss penality components is a good design point. Finally, this dissertation introduces and solves the problems caused by the interaction of virtual memory and real-indexed multi-megabyte caches. Since the placement of pages in main memory also places data in the cache, a poor page placement will cause poor cache performance. This dissertation introduces several new careful page mapping algorithms to improve the page placement, and shows that they eliminate 10%-20% of the direct-mapped real-indexed cache misses for the long traces. In other words, this dissertation develops software techniques that can make a hardware direct-mapped cache appear about 50% larger.