Communication-optimal parallel 2.5D matrix multiplication and LU factorization algorithms

Edgar Solomonik, James Demmel

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 p1/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,...,⌊p1/3⌋}, to reduce the bandwidth cost of Cannon's algorithm by a factor of c 1/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 algorithm 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 that the 2D LU algorithm (c = 1) in fact minimizes latency. We provide implementations and performance results for 2D and 2.5D versions of all the new algorithms. Our results demonstrate that 2.5D matrix multiplication and LU algorithms strongly scale more efficiently than 2D algorithms. Each of our 2.5D algorithms performs over 2X faster than the corresponding 2D algorithm for certain problem sizes on 65,536 cores of a BG/P supercomputer.

Original languageEnglish (US)
Title of host publicationEuro-Par 2011 Parallel Processing - 17th International Conference, Proceedings
Pages90-109
Number of pages20
EditionPART 2
DOIs
StatePublished - 2011
Externally publishedYes
Event17th International Conference on Parallel Processing, Euro-Par 2011 - Bordeaux, France
Duration: Aug 29 2011Sep 2 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 2
Volume6853 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other17th International Conference on Parallel Processing, Euro-Par 2011
Country/TerritoryFrance
CityBordeaux
Period8/29/119/2/11

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Communication-optimal parallel 2.5D matrix multiplication and LU factorization algorithms'. Together they form a unique fingerprint.

Cite this