Competitive Snoopy Caching

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.

Authors

• Anna R. Karlin
• Mark S. Manasse
• Larry Rudolph
• Daniel Dominic Sleator

Keywords

• Costs
• Computer science
• Broadcasting
• Multiprocessing systems
• Memory architecture
• Cache memory
• Time measurement
• Writing
• Caching
• Online Algorithm
• Control Lines
• Hash Function
• Algorithm In This Paper
• Spanning Tree
• Written Back
• Read Operation
• Competitive Algorithm
• P Cycle