Communication-optimal parallel and sequential Cholesky decomposition

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Communication-optimal parallel and sequential Cholesky decomposition: extended abstract

Full text

Pdf (447 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures table of contents

Calgary, AB, Canada

SESSION: High-performance parallel computation table of contents

Pages 245-252

Year of Publication: 2009

ISBN:978-1-60558-606-9

Authors

Grey Ballard	University of California, Berkeley, CA, USA
James Demmel	University of California, Berkeley, CA, USA
Olga Holtz	University of California, Berkeley, CA, USA
Oded Schwartz	Technische Universitaet Berlin, Berlin, Germany

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 40, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1583991.1584054 What is a DOI?

ABSTRACT

Numerical algorithms have two kinds of costs: arithmetic and communication, by which we mean either moving data between levels of a memory hierarchy (in the sequential case) or over a network connecting processors (in the parallel case). Communication costs often dominate arithmetic costs, so it is of interest to design algorithms minimizing communication. In this paper we first extend known lower bounds on the communication cost (both for bandwidth and for latency) of conventional (O(n³)) matrix multiplication to Cholesky, which is used for solving dense symmetric positive definite linear systems. Second, we compare the cost of various Cholesky implementations to this lower bound, and draw the following conclusions:

(1) "Naïve" sequential algorithms for Cholesky attain neither the bandwidth nor latency lower bounds.

(2) The sequential blocked algorithm in LAPACK (with the right block size), as well as various recursive algorithms [AP00, GJ01, AGW01, ST04], and one based on work of Toledo [Tol97], can attain the bandwidth lower bound.

(3) The LAPACK algorithm can also attain the latency bound if used with blocked data structures rather than column-wise or row-wise matrix data structures, though the Toledo algorithm cannot.

(4) The recursive sequential algorithm due to [AP00] attains the bandwidth and latency lower bounds at every level of a multi-level memory hierarchy, in a "cache-oblivious" way.

(5) The parallel implementation of Cholesky in the ScaLAPACK library (again with the right block-size) attains both the bandwidth and latency lower bounds to within a poly-logarithmic factor.

Combined with prior results in [DGHL08a, DGHL08b, DGX08] this gives a complete set of communication-optimal algorithms for O(n³) implementations of three basic factorizations of dense linear algebra: LU with pivoting, QR and Cholesky. But it goes beyond this prior work on sequential LU and QR by optimizing communication for any number of levels of memory hierarchy.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	E. Anderson , Z. Bai , C. Bischof , J. Demmel , J. Dongarra , J. Du Croz , A. Greenbaum , S. Hammarling , A. McKenney , S. Ostrouchov , D. Sorensen, LAPACK's user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
	2	Bjarne Stig Andersen , Jerzy Waśniewski , Fred G. Gustavson, A recursive formulation of Cholesky factorization of a matrix in packed storage, ACM Transactions on Mathematical Software (TOMS), v.27 n.2, p.214-244, June 2001 [doi>10.1145/383738.383741]
	3	Nawaaz Ahmed , Keshav Pingali, Automatic Generation of Block-Recursive Codes, Proceedings from the 6th International Euro-Par Conference on Parallel Processing, p.368-378, August 29-September 01, 2000
	4	Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
	5	N. Béreux. Out-of-core implementations of cholesky factorization: Loop-based versus recursive algorithms. SIAM Journal on Matrix Analysis and Applications, 30(4):1302--1319, 2008.
	6	Michael A. Bender , Gerth Stølting Brodal , Rolf Fagerberg , Riko Jacob , Elias Vicari, Optimal sparse matrix dense vector multiplication in the I/O-model, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248391]
	7	Grey Ballard , James Demmel , Olga Holtz , Oded Schwartz, Communication-optimal parallel and sequential Cholesky decomposition: extended abstract, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada [doi>10.1145/1583991.1584054]
	8	Jack J. Dongarra , L. S. Blackford , J. Choi , A. Cleary , E. D'Azeuedo , J. Demmel , I. Dhillon , S. Hammarling , G. Henry , A. Petitet , K. Stanley , D. Walker , R. C. Whaley, ScaLAPACK user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
	9	Rezaul Alam Chowdhury , Vijaya Ramachandran, Cache-oblivious dynamic programming, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.591-600, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109622]
	10	J. Demmel, L. Grigori, M. Hoemmen, and J. Langou. Communication-optimal parallel and sequential QR and LU factorizations. UC Berkeley Technical Report EECS-2008-89, Aug 1, 2008; Submitted to SIAM. J. Sci. Comp., 2008.
	11	J. Demmel, L. Grigori, M. Hoemmen, and J. Langou. Implementing communication-optimal parallel and sequential QR and LU factorizations. submitted to SIAM. J. Sci. Comp., 2008.
	12	Laura Grigori , James W. Demmel , Hua Xiang, Communication avoiding Gaussian elimination, Proceedings of the 2008 ACM/IEEE conference on Supercomputing, November 15-21, 2008, Austin, Texas
	13	E. Elmroth, F. G. Gustavson, I. Jonsson, and B. Kågström. Recursive blocked algorithms and hybrid data structures for dense matrix library software. 46(1):3--45, March 2004.
	14	Matteo Frigo , Charles E. Leiserson , Harald Prokop , Sridhar Ramachandran, Cache-Oblivious Algorithms, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.285, October 17-18, 1999
	15	Fred G. Gustavson , Isak Jonsson, High Performance Cholesky Factorization via Blocking and Recursion That Uses Minimal Storage, Proceedings of the 5th International Workshop on Applied Parallel Computing, New Paradigms for HPC in Industry and Academia, p.82-91, June 18-20, 2000
	16	Hong Jia-Wei , H. T. Kung, I/O complexity: The red-blue pebble game, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.326-333, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802486]
	17	IEEE standard for floating-point arithmetic. IEEE Std. 754-2008, pages 1--58, 29 2008.
	18	Dror Irony , Sivan Toledo , Alexander Tiskin, Communication lower bounds for distributed-memory matrix multiplication, Journal of Parallel and Distributed Computing, v.64 n.9, p.1017-1026, September 2004 [doi>10.1016/j.jpdc.2004.03.021]
	19	Ivan Simecek , Pavel Tvrdik, Analytical Model for Analysis of Cache Behavior during Cholesky Factorization and Its Variants, Proceedings of the 2004 International Conference on Parallel Processing Workshops, p.190-197, August 15-18, 2004 [doi>10.1109/ICPPW.2004.29]
	20	Sivan Toledo, Locality of Reference in LU Decomposition with Partial Pivoting, SIAM Journal on Matrix Analysis and Applications, v.18 n.4, p.1065-1081, Oct. 1997 [doi>10.1137/S0895479896297744]