MODEL FOR HIERARCHICAL MEMORY.

Alok Aggarwal, Bowen Alpern, Ashok K. Chandra, Marc Snir

Research output: Contribution to journalConference articlepeer-review

Abstract

We introduce the Hierarchical Memory Model (HMM) of computation. It is intended to model computers with multiple levels in the memory hierarchy. Tight lower and upper bounds are given in this model for the time complexity of searching, sorting, matrix multiplication and FFT. Efficient algorithms 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 HMMs where memory access time is given by an arbitrary (nondescreasing) function. Tight upper and lower bounds are obtained for HMMs with polynomial memory access time; the algorithms for searching, FFT and matrix multiplication are shown to be optimal for arbitrary memory access time. Online memory management algorithms for the HMM model are also considered.

Original languageEnglish (US)
Pages (from-to)305-314
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - Dec 1 1987
Externally publishedYes

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'MODEL FOR HIERARCHICAL MEMORY.'. Together they form a unique fingerprint.

Cite this