# Matrix multiplication on multidimensional torus networks

### Edgar Solomonik and James Demmel

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/EECS-2012-28

February 22, 2012

### http://www.eecs.berkeley.edu/Pubs/TechRpts/2012/EECS-2012-28.pdf

Blocked matrix multiplication algorithms such as Cannon’s algorithm and SUMMA have a 2-dimensional communication structure. We introduce a generalized ’Split-Dimensional’ version of Cannon’s algorithm (SD-Cannon) with higher-dimensional and bidirectional communication structure. This algorithm is useful for higher-dimensional torus interconnects that can achieve more injection bandwidth than single-link bandwidth. On a bidirectional torus network of dimension d, SD-Cannon can lower the algorithmic bandwidth cost by a factor of up to d. With rectangular collectives, SUMMA also achieves the lower bandwidth cost but has a higher latency cost. We use Charm++ virtualization to efficiently map SD-Cannon on unbalanced and odd-dimensional torus network partitions. Our performance study on Blue Gene/P demonstrates that an MPI version of SD-Cannon can exploit multiple communication links and improve performance.

BibTeX citation:

@techreport{Solomonik:EECS-2012-28, Author = {Solomonik, Edgar and Demmel, James}, Title = {Matrix multiplication on multidimensional torus networks}, Institution = {EECS Department, University of California, Berkeley}, Year = {2012}, Month = {Feb}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2012/EECS-2012-28.html}, Number = {UCB/EECS-2012-28}, Abstract = {Blocked matrix multiplication algorithms such as Cannon’s algorithm and SUMMA have a 2-dimensional communication structure. We introduce a generalized ’Split-Dimensional’ version of Cannon’s algorithm (SD-Cannon) with higher-dimensional and bidirectional communication structure. This algorithm is useful for higher-dimensional torus interconnects that can achieve more injection bandwidth than single-link bandwidth. On a bidirectional torus network of dimension d, SD-Cannon can lower the algorithmic bandwidth cost by a factor of up to d. With rectangular collectives, SUMMA also achieves the lower bandwidth cost but has a higher latency cost. We use Charm++ virtualization to efficiently map SD-Cannon on unbalanced and odd-dimensional torus network partitions. Our performance study on Blue Gene/P demonstrates that an MPI version of SD-Cannon can exploit multiple communication links and improve performance.} }

EndNote citation:

%0 Report %A Solomonik, Edgar %A Demmel, James %T Matrix multiplication on multidimensional torus networks %I EECS Department, University of California, Berkeley %D 2012 %8 February 22 %@ UCB/EECS-2012-28 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2012/EECS-2012-28.html %F Solomonik:EECS-2012-28