Organizing matrices and matrix operations for paged memory systems

ABSTRACT

Matrix representations and operations are examined for the purpose of minimizing the page faulting occurring in a paged memory system. It is shown that carefully designed matrix algorithms can lead to enormous savings in the number of page faults occurring when only a small part of the total matrix can be in main memory at one time. Examination of addition, multiplication, and inversion algorithms shows that a partitioned matrix representation (i.e. one submatrix or partition per page) in most cases induced fewer page faults than a row-by-row representation. The number of page-pulls required by these matrix manipulation algorithms is also studied as a function of the number of pages of main memory available to the algorithm.

REFERENCES

• 1: Gerald H. Fine , Calvin W. Jackson , Paul V. Mc Isaac, Dynamic program behavior under paging, Proceedings of the 1966 21st national conference, p.223-228, January 1966 [doi>10.1145/800256.810701]
• 2: E. G. Coffman , L. C. Varian, Further experimental data on the behavior of programs in a paging environment, Communications of the ACM, v.11 n.7, p.471-474, July 1968 [doi>10.1145/363397.363398]
• 3: BELAPY, L. A. A study of replacement algorithms for a virtual storage computer. IBM Syst. J. 5, 2 (1966).
• 4: O'NEIL, R. W. Experience using a time-shared multi-programming system with dynamic address relocation hardware. Proc. AFIPS 1967 Spring Joint Comput. Conf., Vol. 30, Thompson Book Co., Washington, D.C., pp. 611-622.
• 5: John G. Kemeny , Thomas E. Kurtz, Basic Programming, John Wiley & Sons, Inc., New York, NY, 1980
• 6: Kenneth E. Iverson, A Programming Language., John Wiley & Sons, 1962
• 7: 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]
• 8: H. Hellerman, Addressing multidimensional arrays, Communications of the ACM, v.5 n.4, p.205-207, April 1962 [doi>10.1145/366920.366943]
• 9: J. H. Wilkinson, Error Analysis of Direct Methods of Matrix Inversion, Journal of the ACM (JACM), v.8 n.3, p.281-330, July 1961 [doi>10.1145/321075.321076]
• 10: FORSYTHE, G., AND MOLER, C.B. Computer Solugon of Linear Algebraic Systems. Prentice-Hall, Englewood Cliffs, N.J., 1967.
• 11: FADDEEV, D. K., 2aND FADDEEVA, V. N. Computational Methods of Linear Algebra. W. H. Freeman, SanFrancisco, 1963.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Virtual memory

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

General Terms:
Algorithms, Design, Theory

Keywords:
array processing, array storage allocation, matrix algorithms, paged memory systems, paging algorithms, storage allocation, virtual memory systems