Distributed SBP Cholesky factorization algorithms with near-optimal scheduling

ABSTRACT

The minimal block storage Distributed Square Block Packed (DSBP) format for distributed memory computing on symmetric and triangular matrices is presented. Three algorithm variants (Basic, Static, and Dynamic) of the blocked right-looking Cholesky factorization are designed for the DSBP format, implemented, and evaluated. On our target machine, all variants outperform standard full-storage implementations while saving almost half the storage. Communication overhead is shown to be virtually eliminated by the Static and Dynamic variants, both of which take advantage of hardware parallelism to hide communication costs. The Basic variant is shown to yield comparable or slightly better performance than the full-storage ScaLAPACK routine PDPOTRF while clearly outperformed by both Static and Dynamic. Models of execution assuming zero communication costs and overhead are developed. For medium- and larger-sized problems, the Static schedule is near optimal on our target machine based on comparisons with these models and measurements of synchronization overhead.

REFERENCES

• 1: Agarwal, R. C. and Gustavson, F. G. 1988. A parallel implementation of matrix multiplication and LU factorization on the IBM 3090. In Aspects of Computation on Asynchronous and Parallel Processors, M. Wright, Ed. IFIP, North-Holland, Amsterdam, The Netherlands, 217--221.
• 2: R. C. Agarwal , F. G. Gustavson, Vector and parallel algorithms for Cholesky factorization on IBM 3090, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.225-233, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76287]
• 3: R. C. Agarwal , F. G. Gustavson , M. Zubair, A high-performance matrix-multiplication algorithm on a distributed-memory parallel computer, using overlapped communication, IBM Journal of Research and Development, v.38 n.6, p.673-681, Nov. 1994
• 4: Baboulin, M., Giraud, L., and Gratton, S. 2005a. A parallel distributed solver for large dense symmetric systems: Applications to geodesy and electromagnetism problems. Int. J. High Perform. Comput. Appl./19, 353--363.
• 5: Baboulin, M., Giraud, L., Gratton, S., and Langou, J. 2005b. A distributed packed storage for large parallel calculations. Tech. rep. TR/PA/05/30. CERFACS, Toulouse, France.
• 6: Richard P. Brent , Franklin T. Luk, Computing the Cholesky Factorization Using a Systolic Architecture, Cornell University, Ithaca, NY, 1982
• 7: Ron Brightwell , Keith D. Underwood, An analysis of the impact of MPI overlap and independent progress, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006251]
• 8: Buttari, A., Langou, J., Kurzak, J., and Dongarra, J. 2007. A class of parallel tiled linear algebra algorithms for multicore architectures. Tech. rep. UT-CS-07-600. University of Tennessee, Knoxville, TN.
• 9: Ernie Chan , Enrique S. Quintana-Orti , Gregorio Quintana-Orti , Robert van de Geijn, Supermatrix out-of-order scheduling of matrix operations for SMP and multi-core architectures, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248397]
• 10: Jaeyoung Choi , Jack J. Dongarra , L. Susan Ostrouchov , Antoine P. Petitet , David W. Walker , R. Clint Whaley, Design and Implementation of the ScaLAPACK LU, QR, and Cholesky Factorization Routines, Scientific Programming, v.5 n.3, p.173-184, August 1996
• 11: Dackland, K., Elmroth, E., Kågström, B., and Van Loan, C. 1992. Parallel block factorizations on the shared memory multiprocessor IBM 3090 VF/600J. Int. J. Supercomput. Appl. 6.1, 69--97.
• 12: Dackland, K., Elmroth, E., and Kågström, B. 1993. A ring--oriented approach for block matrix factorizations on shared and distributed memory architectures. In SIAM Conference on Parallel Processing for Scientific Computing, R. S. et al, Ed. SIAM Publications, Philadelphia, PA, 330--338.
• 13: Ed D''Azevedo , Jack Dongarra, Packed Storage Extension for ScaLAPACK, University of Tennessee, Knoxville, TN, 1998
• 14: Jack J. Dongarra , Lain S. Duff , Danny C. Sorensen , Henk A. Vander Vorst, Numerical Linear Algebra for High Performance Computers, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1998
• 15: Geist, G. A. and Heath, M. T. 1985. Parallel Cholesky factorization on a hypercube multiprocessor. Tech. rep. ORNL--6190. Oak Ridge National Lab., Oak Ridge, TN.
• 16: Apostolos Gerasoulis , Izzy Nelken, Scheduling Linear Algebra Parallel Algorithms on MIMD Architectures, Proceedings of the Fourth SIAM Conference on Parallel Processing for Scientific Computing, p.68-95, December 11-13, 1989
• 17: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 18: Kazushige Goto , Robert A. van de Geijn, Anatomy of high-performance matrix multiplication, ACM Transactions on Mathematical Software (TOMS), v.34 n.3, p.1-25, May 2008 [doi>10.1145/1356052.1356053]
• 19: Ananth Y. Grama , Anshul Gupta , Vipin Kumar, Isoefficiency: Measuring the Scalability of Parallel Algorithms and Architectures, IEEE Parallel & Distributed Technology: Systems & Technology, v.1 n.3, p.12-21, August 1993 [doi>10.1109/88.242438]
• 20: Gustavson, F. G., Gunnels, J. A., and Sexton, J. C. 2007a. Minimal data copy for dense linear algebra factorization. In PARA 2006: State of the Art in Scientific and Parallel Computing, B. Kågström et al., Eds. Lecture Notes in Computer Science, vol. 4699. Springer, Berlin, Germany, 540--549.
• 21: Gustavson, F. G., Karlsson, L., and Kågström, B. 2007b. Three algorithms for Cholesky factorization on distributed memory using packed storage. In PARA 2006: State of the Art in Scientific and Parallel Computing, B. Kågström et al., Eds. Lecture Notes in Computer Science, vol 4699. Springer. Berlin, Germany, 550--559. Also IBM Tech. rep. RC24137.
• 22: MPI Forum. 1995. MPI: A message passing interface standard. http://www.mpi-forum.org/.
• 23: Dianne P. O'Leary , G. W. Stewart, Data-flow algorithms for parallel matrix computation, Communications of the ACM, v.28 n.8, p.840-853, Aug. 1985 [doi>10.1145/4021.4025]
• 24: Strazdins, P. 1998. A comparison of lookahead and algorithmic blocking techniques for parallel matrix factorization. Tech. rep. TR-CS-98-07. Canberra 0200 ACT, Australia.
• 25: van de Geijn, R. A. 1997. Using PLAPACK. MIT Press, Cambridge, MA.

INDEX TERMS

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

Additional Classification:
  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: Reliability and robustness; Algorithm design and analysis

General Terms:
Algorithms, Performance

Keywords:
Cholesky factorization, Real symmetric matrices, distributed square block format, packed storage, parallel algorithms, parallel computing, positive definite matrices