Communication costs of Strassen's matrix multiplication
Abstract
Algorithms have historically been evaluated in terms of the number of arithmetic operations they performed. This analysis is no longer sufficient for predicting running times on today's machines. Moving data through memory hierarchies and among processors requires much more time (and energy) than performing computations. Hardware trends suggest that the relative costs of this communication will only increase. Proving lower bounds on the communication of algorithms and finding algorithms that attain these bounds are therefore fundamental goals. We show that the communication cost of an algorithm is closely related to the graph expansion properties of its corresponding computation graph.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Feb 01, 2014
- Source ID
- 10.1145/2556647.2556660
Entities
People
- Grey Ballard
- James Demmel
- Oded Schwartz
- Olga Holtz
Organizations
- Alexander von Humboldt Foundation
- Defense Advanced Research Projects Agency
- European Research Council
- Intel Corporation
- Microsoft
- NEC
- National Instruments
- National Science Foundation Division of Mathematical Sciences
- Nokia
- Nvidia
- Samsung Group
- Technische Universität Berlin
- United States Department of Energy
- University of California
- University of California, Berkeley