1986 · 104 citations · 12 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureParallel AlgorithmsParallel ComputingCachingCommunication OverheadInterprocess CommunicationMemory Hierarchy OptimizationParallel Computing SystemsShared-memory MultiprocessingCache OptimizationMain Memory Organization
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.
12
A study of replacement algorithms for a virtual-storage computer
L. A. Belady · IBM Systems Journal · 1966 · 1.7K citations
Using cache memory to reduce processor-memory traffic
James Goodman · 1998 · 396 citations
Using cache memory to reduce processor-memory traffic
James Goodman · 1983 · 305 citations