Communication-Optimal Parallel 2.5D Matrix Multiplication and LU Factorization Algorithms精品.pdf

Communication-Optimal Parallel 2.5D Matrix Multiplication and LU Factorization Algorithms Edgar Solomonik and James Demmel Department of Computer Science University of California at Berkeley, Berkeley, CA, USA solomon@, demmel@ Abstract. Extra memory allows parallel matrix multiplication to be done with asymptotically less communication than Cannon’s algorithm and be faster in practice. “3D” algorithms arrange the p processors in a 3D array, and store redundant copies of the matrices on each of p 1/3 layers. ‘2D” algorithms such as Cannon’s algorithm store a single copy of the matrices on a 2D array of processors. We generalize these 2D and 3D algorithms by introducing a new class of “2.5D algorithms”. For matrix multiplication, we can take advantage of any amount of extra memory to store c copies of the data, for any c ∈ {1, 2, ..., p 1/3}, to reduce the bandwidth cost of Cannon’s algorithm by a factor of c1/2 and the latency cost by a factor c3/2 . We also show that these costs reach the lower bounds, modulo polylog(p ) factors. We introduce a novel algorithm for 2.5D LU decomposition. To the best of our knowledge, this LU algo- rithm is the first to minimize communication along the critical path of execution in the 3D case. Our 2.5D LU algorithm uses communication- avoiding pivoting, a stable alternative to partial-pivoting. We prove a novel lower bound on the latency cost of 2.5D and 3D LU factorization, showing that while c copies of the data can also reduce the bandwidth by a factor of c1/2 , the latency must increase by a factor of c1/2 , so