A model for hierarchical memory

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.

REFERENCES

• A85: A Aggarwal, Tradeoffs for VLSI models with subpolynomial delay, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.59-68, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22152]
• Ag86: R. Agarwal, Personal Communication, 1986.
• AHU74: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• AV86: A. Aggarwal , J. S. Vitter, The I/O complexity of sorting and related problems, 14th International Colloquium on Automata, languages and programming, p.467-478, July 1987, Karlsruhe, Germany
• Ba80: I. L. Baer, "Computer Systems Architecture," Computer Science Press, Potomac, MD, 1980.
• Ch76: C. K. Chow, "Determination of Cache's Capacity and its Matching Storage Hierarchy," iEEE Trans. on Computers, TC-25, No. 2, Feb. 1976, pp. 157-164.
• De68: Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
• De70: Peter J. Denning, Virtual Memory, ACM Computing Surveys (CSUR), v.2 n.3, p.153-189, Sept. 1970 [doi>10.1145/356571.356573]
• HDR80: W. J. }larding, M. H. MacDougall and W. j. Raymond, "Empirical Eslimation of Cache Miss Ratios as a Function of Cache Size," Tech. Report PN 820-420-700S, Amdahl Corp., Sept. 26, 1980.
• HK81: Hong Jia-Wei , H. T. Kung, I/O complexity: The red-blue pebble game, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.326-333, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802486]
• IBM86: IBM Engineering and Scientific Subroutine Library, Guide and Reference, Program No. 5668-863, SC23-0184-0, Feb. 1986.
• MC80: C. Mead and L. Conway, introduction to VLSI ~Fxtems, Addison-Wesley, 1980, pg. 316.
• MGS70: R. L. Mattson, J. Gacsei, D. R. Slutz and I. L. Traiger, "Evaluation Techniques for Storage Hierarchies," IBM Systems Journal, Vol. 9, No. 2, 1970, pp. 78-117.
• Si83: G. M. Sitberman, "Delayed-Staging Hierarchy Optimization," IEEE Trans. on Computers, TC-32, No. 11, Nov. 1983, pp. 1029-1037.
• Sm82: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• Sp78: F. J. Sparacio, "Data Processing System with Second Level Cache," IBM Tech. Disclosure Bulletin, Vol. 21, No. 6, 1978, pp. 2468-2469.
• ST85: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]

INDEX TERMS

Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Complexity hierarchies
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory, Verification