Efficient householder QR factorization for superscalar processors

ABSTRACT

To extract the potential promised by superscalar processors, algorithm designers must streamline memory references and allow for efficient data reuse throughout the memory hierarchy. Two parameterized Householder QR factorization algorithms are presented that take into account the caches and registers typical of such processors. Guidelines are developed for choosing parameter values that obtain near-optimal cache and register utilization. The new algorithms are implemented and performance-tuned on an Intel Pentium Pro system, a single thin POWER2 node of the IBM Scalable Parallel system 2 (SP2), and a single R8000 processor of a Silicon Graphs POWER Challenge XL.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 2: Christian Bischof , Charles van Loan, The WY representation for products of householder matrices, SIAM Journal on Scientific and Statistical Computing, v.8 n.1, p.2-13, January 2, 1987 [doi>10.1137/0908009]
• 3: BJORCK, A. 1990. Least squares methods. In Handbook of NumericalAnalysis, P. Ciarlet and J. Lions, Eds. Elsevier North-Holland, Inc., New York, NY, 465-652.
• 4: CARRIG, J. J. AND MEYER, G. G. 1996. Two tunable Householder QR decomposition algorithms. Tech. Rep. 96-14, Electrical and Computer Engineering, Johns Hopkins University, Baltimore, MD.
• 5: Jack J. Dongarra , Jeremy Du Croz , Sven Hammarling , Richard J. Hanson, An extended set of FORTRAN basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.1-17, March 1988 [doi>10.1145/42288.42291]
• 6: GALLIVAN, K., JALBY, W., MEIER, U., AND SAMEH, A.H. 1988. Impact of hierarchical memory systems on linear algebra algorithm design. Int. J. Supercomput. Appl. High Perform. Eng. 2, 1, 12-48.
• 7: GOLUB, G. AND WILKINSON, J. 1966. Note on the iterative refinement of least squares solutions. Numer. Math. 9, 139-148.
• 8: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 9: Alston S. Householder, Unitary Triangularization of a Nonsymmetric Matrix, Journal of the ACM (JACM), v.5 n.4, p.339-342, Oct. 1958 [doi>10.1145/320941.320947]
• 10: INTEL. 1995. Programmer's Reference Manual. Pentium Pro family developer's manual, vol. 2. Intel Corporation, Santa Clara, CA.
• 11: LAWSON, C. L. AND HANSON, R.J. 1974. Solving Least Squares Problems. Prentice-Hall, Inc., Upper Saddle River, NJ.
• 12: Robert Schreiber , Charles van Loan, A storage-efficient WY representation for products of householder transformations, SIAM Journal on Scientific and Statistical Computing, v.10 n.1, p.53-57, January 1989 [doi>10.1137/0910005]
• 13: SILICON GRAPHICS. 1994. POWER CHALLENGE technical report. Silicon Graphics, Incorporated, Mountain View, CA.
• 14: WHITE, S. W. AND DHAWAN, S. 1995. POWER2: The next generation of the RISC System/ 6000 family. Draft prepared for PowerPC and POWER2: Technical Aspects of the New IBM RISC System/6000. IBM Corp., Riverton, NJ.
• 15: M. E. Wolf , M. S. Lam, A Loop Transformation Theory and an Algorithm to Maximize Parallelism, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.452-471, October 1991 [doi>10.1109/71.97902]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

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

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency; Algorithm design and analysis

General Terms:
Algorithms, Performance

Keywords:
Householder QR factorization, cache model, register model