The Library
Communication lower bounds for distributed-memory matrix multiplication
Tools
Ironya, Dror, Sivan, Toledo and Tiskin, Alexander (2004) Communication lower bounds for distributed-memory matrix multiplication. Journal of Parallel and Distributed Computing, Volume 64 (Number 9). pp. 1017-1026. doi:10.1016/j.jpdc.2004.03.021 ISSN 0743-7315.
PDF
sdarticle4.pdf - Published Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (262Kb) |
Official URL: http://dx.doi.org/10.1016/j.jpdc.2004.03.021
Abstract
We present lower bounds on the amount of communication that matrix multiplication algorithms must perform on a distributed-memory parallel computer. We denote the number of processors by P and the dimension of square matrices by n. We show that the most widely used class of algorithms, the so-called two-dimensional (2D) algorithms, are optimal, in the sense that in any algorithm that only uses O(n(2)/p) words of memory per processor, at least one processor must send or receive Omega(n(2)/p(1/2)) words. We also show that algorithms from another class, the so-called three-dimensional (3D) algorithms, are also optimal. These algorithms use replication to reduce communication. We show that in any algorithm that uses Omega(n(2)/p(2/3)) words of memory per processor, at least one processor must send or receive Omega(n(2)/p(2/3)) words. Furthermore, we show a continuous tradeoff between the size of local memories and the amount of communication that must be performed. The 2D and 3D bounds are essentially instantiations of this tradeoff. We also show that if the input is distributed across the local memories of multiple nodes without replication, then Omega(n(2)) words must cross any bisection cut of the machine. All our bounds apply only to conventional o(n(3)) algorithms. They do not apply to Strassen's algorithm or other Theta(n(3)) algorithms.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Journal of Parallel and Distributed Computing | ||||
Publisher: | Elsevier Science BV | ||||
ISSN: | 0743-7315 | ||||
Official Date: | September 2004 | ||||
Dates: |
|
||||
Volume: | Volume 64 | ||||
Number: | Number 9 | ||||
Number of Pages: | 10 | ||||
Page Range: | pp. 1017-1026 | ||||
DOI: | 10.1016/j.jpdc.2004.03.021 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Open Access (Creative Commons) | ||||
Date of first compliant deposit: | 4 December 2015 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |