Sage Journals: Discover world-class research

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.

Impact of Hierarchical Memory Systems On Linear Algebra Algorithm Design

Abstract

Get full access to this article

References