Communication Costs of Strassen's Matrix Multiplication.
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 pe...
| Publicado en: | Communications of the ACM Vol. 57; no. 2; pp. 107 - 115 |
|---|---|
| Autores principales: | , , , |
| Formato: | Artículo |
| Publicado: |
Association for Computing Machinery
Feb2014
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=94282238&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 94282238 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00010782 ACM jtl: Communications of the ACM issn: 00010782 maglogo: N pubinfo: dt: Feb2014 vid: 57 iid: 2 pid: 68 pub: Association for Computing Machinery artinfo: ui: 94282238 10.1145/2556647.2556660 ppf: 107 ppct: 8 formats: tig: atl: Communication Costs of Strassen's Matrix Multiplication. aug: au: Ballard, Grey Demmel, James Holtz, Olga Schwartz, Oded affil: Electrical Engineering and Computer Science Department, University of California, Berkeley, CA. Department of Mathematics and Computer Science Division, University of California, Berkeley, CA. Department of Mathematics, University of California, Berkeley, CA, and Institut für Mathematik, Technische Universitat Berlin, Germany. su: Algorithms Run time systems (Computer science) Memory hierarchy (Computer science) Computer input-output equipment Parallel algorithms Matrices (Mathematics) Communication models Partitions (Mathematics) Recursive functions sug: subj: Algorithms Run time systems (Computer science) Memory hierarchy (Computer science) Computer input-output equipment Parallel algorithms Matrices (Mathematics) Communication models Partitions (Mathematics) Recursive functions ab: 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. Matrix multiplication is one of the most fundamental problems in scientific computing and in parallel computing. Applying expansion analysis to Strassen's and other fast matrix multiplication algorithms, we obtain the first lower bounds on their communication costs. These bounds show that the current sequential algorithms are optimal but that previous parallel algorithms communicate more than necessary. Our new parallelization of Strassen's algorithm is communication-optimal and outperforms all previous matrix multiplication algorithms. pubtype: Periodical doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2014 holdings: @attributes: islocal: N |
|---|