Computer Science – Data Structures and Algorithms
Scientific paper
2012-02-14
Computer Science
Data Structures and Algorithms
4 pages, 1 figure
Scientific paper
A parallel algorithm has perfect strong scaling if its running time on P processors is linear in 1/P, including all communication costs. Distributed-memory parallel algorithms for matrix multiplication with perfect strong scaling have only recently been found. One is based on classical matrix multiplication (Solomonik and Demmel, 2011), and one is based on Strassen's fast matrix multiplication (Ballard, Demmel, Holtz, Lipshitz, and Schwartz, 2012). Both algorithms scale perfectly, but only up to some number of processors where the inter-processor communication no longer scales. We obtain a memory-independent communication cost lower bound on classical and Strassen-based distributed-memory matrix multiplication algorithms. These bounds imply that no classical or Strassen-based parallel matrix multiplication algorithm can strongly scale perfectly beyond the ranges already attained by the two parallel algorithms mentioned above. The memory-independent bounds and the strong scaling bounds generalize to other algorithms.
Ballard Grey
Demmel James
Holtz Olga
Lipshitz Benjamin
Schwartz Oded
No associations
LandOfFree
Strong Scaling of Matrix Multiplication Algorithms and Memory-Independent Communication Lower Bounds does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Strong Scaling of Matrix Multiplication Algorithms and Memory-Independent Communication Lower Bounds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strong Scaling of Matrix Multiplication Algorithms and Memory-Independent Communication Lower Bounds will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-556042