Communication-optimal parallel and sequential Cholesky decomposition: extended abstract
Communication-optimal parallel and sequential Cholesky decomposition: extended abstract
复制标题
通信最优并行和顺序 Cholesky 分解：扩展摘要
DOI：
10.1137/090760969
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
O. Schwartz
中科院分区：
文献类型：
--
作者：
Grey Ballard;J. Demmel;Olga Holtz;O. Schwartz
数值算法有两种开销：算术和通信，我们所说的是在内存层次结构的级别之间移动数据(在顺序情况下)，或者在连接处理器的网络上(在并行情况下)。通信成本通常控制着算法成本，因此设计最小化通信的算法是很有意义的。本文首先将已知的(O(N3))矩阵乘法的通信成本下界(带宽和时延)推广到Cholesky，用于求解稠密对称正定线性方程组。其次，我们将各种Cholesky实现的成本与此下限进行了比较，并得出以下结论：
(1)Cholesky的“幼稚”序列算法既不能达到带宽下界，也不能达到延迟下界。
(2)LAPACK中的顺序分块算法(具有合适的块大小)，以及各种递归算法[AP00，GJ01，AGW01，ST04]，以及基于Toldo[Tol97]工作的算法，都可以获得带宽下限。
(3)如果LAPACK算法用于分块数据结构而不是列或行矩阵数据结构，则LAPACK算法也可以达到延迟界，而Toledo算法不能。
(4)基于[AP00]的递归顺序算法以“缓存无关”的方式获得了多级存储层次结构中每一级的带宽和延迟下界。
(5)在ScaLAPACK库中并行实现Cholesky(同样具有正确的块大小)获得了带宽和延迟下界，均在多对数因子内。
结合[DGHL08a，DGHL08b，DGX08]中的结果，给出了稠密线性代数的三种基本因式分解O(N3)实现的一套完整的通信优化算法：带枢轴的LU、QR和Cholesky。但它通过优化任意数量的存储器层次结构级别的通信，超越了以前在顺序逻辑单元和QR上的工作。
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(n3)) 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(n3) 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.