Impact of Hierarchical Memory Systems On Linear Algebra Algorithm Design

Abstract

Linear algebra algorithms based on the BLAS or ex tended BLAS do not achieve high performance on mul tivector processors with a hierarchical memory system because of a lack of data locality. For such machines, block linear algebra algorithms must be implemented in terms of matrix-matrix primitives (BLAS3). Designing ef ficient linear algebra algorithms for these architectures requires analysis of the behavior of the matrix-matrix primitives and the resulting block algorithms as a func tion of certain system parameters. The analysis must identify the limits of performance improvement possible via blocking and any contradictory trends that require trade-off consideration. We propose a methodology that facilitates such an analysis and use it to analyze the per formance of the BLAS3 primitives used in block methods. A similar analysis of the block size-perfor mance relationship is also performed at the algorithm level for block versions of the LU decomposition and the Gram-Schmidt orthogonalization procedures.

Get full access to this article

View all access options for this article.

References

Belady, L. 1966. A study of replacement algorithms for virtual storage computers. IBM Syst. J. 5(2):78-101.

Berry, M. , Gallivan, K. , Harrod, W. , Jalby, W. , Lo, S. , Meier, U. , Phillipe, B. , and Sameh, A. 1986. Parallel numerical algorithms on the CEDAR system. CSRD Report 581 Urbana: University of Illinois at Urbana-Champaign, CSRD.

Calahan, D. 1986. Block-oriented, local-memory-based linear equation solution on the CRAY-2: uni-processor algorithms. In Proceedings of ICPP 1986. Washington D.C.: IEEE Computer Society Press, pp. 375-378.

Cheong, H. , and Veidenbaum, A. 1987. The performance of software managed multiprocessor cache on parallel numerical algorithms. In Proceedings of the International Conference on Supercomputing 1987. New York: Springer Verlag.

Dongarra, J. , Bunch, J. , Moler, C. , and Stewart, G.W. 1979. LINPACK user's guide. Philadelphia : SIAM Publications.

Dongarra, J. , DuCroz, J. , Hammarling, S. , and Hanson, R. 1984. A proposal for an extended set of Fortran basic linear algebra subprograms. Technical Memo 41. Argonne, Ill.: Argonne National Laboratory, Mathematics and Computer Science Division.

Gajski, D. , Kuck, D. , Lawrie, D. , and Sameh, A. 1983. CEDAR: a large scale multiprocessor. In Proceedings ICPP 1983. Washington, D.C.: IEEE Computer Society Press, pp. 524-529.

Gallivan, K. , Jalby, W. , and Meier, U. 1986. The use of BLAS3 in linear algebra on a parallel processor with a hierarchical memory. CSRD Report 610. Urbana: University of Illinois at Urbana-Champaign , CSRD. (Also in SIAM J. Sci. Stutist. Comput., 1987. 8(6):1079-1084.)

Gallivan, K. , Jalby, W. , Meier, U. , and Sameh, A. 1986. The impact of hierarchical memory systems on linear algebra algorithm design. CSRD Report 625 Urbana: University of Illinois at Urbana-Champaign, CSRD.

10.

Gannon, D. , Jalby, W. , and Gallivan, K. 1987. Strategies for cache and local memory management by global program transformation. In Proceedings of the International Conference on Supercomputing 1987. New York : Springer Verlag.

11.

Gannon, D. , and Van Rosendale, J. 1984. On the impact of communication complexity on the design of parallel numerical algorithms. IEEE Trans. Comput. C-33(12): 1180-1195.

12.

Golub, G. , and Van Loan, C. 1983. Matrix computations. Baltimore : The Johns Hopkins University Press.

13.

Hockney, R.W. , and Jesshope, C.R. 1981. Parallel computers. Bristol, U.K.: Adam Hilger Ltd.

14.

Hong, J.W. , and Kung, H.T. 1981. I/O complexity: the red-blue pebble game. In Proceedings of the 13th Annual Symposium on Theory of Computing . New York: ACM, pp. 326-333.

15.

Ipsen, I. , and Saad, Y. 1985. The impact of parallel architectures on the solution of eigenvalue problems. YALEU/DCS/ RR-444. New Haven, Conn. : Yale University, Dept. of Computer Science.

16.

Keyes, D. , and Gropp, W. 1985. A comparison of domain decomposition techniques for elliptic partial differential equations and their parallel implementation. YALEU/DCS/ RR-48. New Haven, Conn.: Yale University, Dept. of Computer Science.

17.

Kogge, P. 1981. The architecture of pipelined computers. New York: McGraw-Hill.

18.

Kuck, D. , Davidson, E. , Lawrie, D. , and Sameh, A. 1986. Parallel supercomputing today and the CEDAR approach . Science 231:967-974.

19.

Peters, G. , and Wilkinson, J. 1975. On the stability of Gauss-Jordan elimination with pivoting . Comm. ACM 18:20-24.

20.

Saad, Y. , and Schultz, M. 1985. Parallel methods for solving banded linear systems. YALEU/DCS/RR-887 . New Haven, Conn.: Yale University, Dept. of Computer Science.

21.

Sameh, A. 1982. Solving the linear least squares problem on a linear array of processors. In Algorithmically specialized computer organizatiom , edited by L. Snyder , L. Jamieson , D. Gannon , and H. Siegel. New York: Academic Press, pp. 191-200.

22.

Seitz, C. 1985. The cosmic cube. Comm. ACM 28:22-33.

23.

Yew, P.C. 1986. Architecture of the CEDAR parallel supercomputer. CSRD Report 609 Urbana: University of Illinois at Urbana-Champaign, CSRD.