Tech Report CS-93-08
Space-Time Tradeoffs in Memory Hierarchies
John E. Savage
March 1994
Abstract:
The speed of CPUs is accelerating rapidly, outstripping that of peripheral storage devices and making it increasingly difficult to keep CPUs busy. Multilevel memory hierarchies, scaled to simulate single-level memories, are increasing in importance. In this paper we introduce the Memory Hierarchy Game, a multilevel pebble game simulating data movement in memory hierarchies. We derive upper and lower bounds on the I/O and computation time for a number of problems, including matrix multiplication and the Fourier transform, and discuss conditions on hierarchies under which they act as fast memories.
(complete text in pdf or gzipped postscript)