It is well known that the increasing gap between processor and main-memory speeds is one of the primary bottlenecks to good overall computer-system performance. The traditional solution to this problem is to build small, fast memories (caches) to hold recently-used data and instructions close to the processor for quicker access [64]. During the past decade, microprocessor clock rates have increased at a rate of 40% per year, while main-memory (DRAM) speeds have increased at a rate of only about 11% per year [76]. This trend has made modern computer systems increasingly dependent on caches. A case in point: disabling the cache of the VAX 11/780, a machine introduced in the late 1970’s, would have increased its workload run times by a factor of only 1.6 [32], while disabling the cache of the HP 9000/735, a more recent machine introduced in the early 1990’s, would cause workloads to slow by a factor of 15 [76].