A model for hierarchical memory

TLDR

The paper introduces the Hierarchical Memory Model (HMM), a computational framework designed to represent computers with multiple memory hierarchy levels. The HMM assumes memory access time grows logarithmically with address size, exploits locality by loading data into fast memory for repeated use, and is generalized to arbitrary nondecreasing access functions with online LRU management across hierarchy levels. The authors establish tight lower and upper bounds for searching, sorting, matrix multiplication, and FFT in the HMM, prove that circuit simulation suffers from poor locality, and show that optimal algorithms—including an LRU-based online memory manager—achieve these bounds even for arbitrary polynomial access times.

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.