A model for hierarchical memory

Citations Over TimeTop 10% of 1987 papers

Abstract

In this paper we introduce the Hierarchical Memory Model (HMM) of computation. It is intended to model computers with multiple levels in the memory hierarchy. Access to memory location x is assumed to take time ⌈ log x ⌉. Tight lower and upper bounds are given in this model for the time complexity of searching, sorting, matrix multiplication and FFT. Efficient algorithms in this model utilize locality of reference by bringing data into fast memory and using them several times before returning them to slower memory. It is shown that the circuit simulation problem has inherently poor locality of reference. The results are extended to HMM's where memory access time is given by an arbitrary (nondecreasing) function. Tight upper and lower bounds are obtained for HMM's with polynomial memory access time; the algorithms for searching, FFT and matrix multiplication are shown to be optimal for arbitrary memory access time. On-line memory management algorithms for the HMM model are also considered. An algorithm that uses LRU policy at the successive “levels” of the memory hierarchy is shown to be optimal.

Related Papers

• → Algorithms and Data Structures for External Memory(2006)175 cited
• → External Memory Algorithms(1998)26 cited
• External memory algorithms : DIMACS Workshop External Memory Algorithms and Visualization, May 20-22, 1998(1999)
• An efficient algorithm to compute the viewshed on DEM terrains stored in the external memory(2007)
• → LEDA-SM: External Memory Algorithms and Data Structures in theory and practice(2001)2 cited