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)