Competitive snoopy caching
Anna R. Karlin, Mark S. Manasse, Larry Rudolph et al. · Annual Symposium on Foundations of Computer Science · 1986
In a snoopy cache multiprocessor system, each processor has a cache in which it stores blocks of data. Each cache is connected to a bus used to communicate with the other caches and with main memory. For several of the proposed models of snoopy caching, we present new on-line algorithms which decide, for each cache, which blocks to retain and which to drop in order to minimize communication over the bus. We prove that, for any sequence of operations, our algorithms' communication costs are within a constant factor of the minimum required for that sequence; for some of our algorithms we prove that no on-line algorithm has this property with a smaller constant.
Cited by 103 works. doi:10.1109/sfcs.1986.14
Authors
References
- A study of replacement algorithms for a virtual-storage computer
- Amortized efficiency of list update and paging rules
- Using cache memory to reduce processor-memory traffic
- Using cache memory to reduce processor-memory traffic
- A low-overhead coherence solution for multiprocessors with private cache memories
- Implementing a cache consistency protocol
- Dynamic decentralized cache schemes for mimd parallel processors
- A low-overhead coherence solution for multiprocessors with private cache memories
- Tightly coupled multiprocessor system speeds memory-access times
- Dynamic decentralized cache schemes for mimd parallel processors