3D coded SUMMA: Communication-efficient and robust parallel matrix multiplication

Haewon Jeong; Yaoqing Yang; Vipul Gupta; Christian Engelmann; Tze Meng Low; Viveck Cadambe; Kannan Ramchandran; Pulkit Grover

doi:10.1007/978-3-030-57675-2_25

3D coded SUMMA: Communication-efficient and robust parallel matrix multiplication

Haewon Jeong, Yaoqing Yang, Vipul Gupta, Christian Engelmann, Tze Meng Low, Viveck Cadambe, Kannan Ramchandran, Pulkit Grover

Intelligent Systems and Facilities

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

In this paper, we propose a novel fault-tolerant parallel matrix multiplication algorithm called 3D Coded SUMMA that achieves higher failure-tolerance than replication-based schemes for the same amount of redundancy. This work bridges the gap between recent developments in coded computing and fault-tolerance in high-performance computing (HPC). The core idea of coded computing is the same as algorithm-based fault-tolerance (ABFT), which is weaving redundancy in the computation using error-correcting codes. In particular, we show that MatDot codes, an innovative code construction for parallel matrix multiplications, can be integrated into three-dimensional SUMMA (Scalable Universal Matrix Multiplication Algorithm [30]) in a communication-avoiding manner. To tolerate any two node failures, the proposed 3D Coded SUMMA requires ~50% less redundancy than replication, while the overhead in execution time is only about 5–10%.

Original language	English
Title of host publication	Euro-Par 2020
Subtitle of host publication	Parallel Processing - 26th International Conference on Parallel and Distributed Computing, Proceedings
Editors	Maciej Malawski, Krzysztof Rzadca
Publisher	Springer
Pages	392-407
Number of pages	16
ISBN (Print)	9783030576745
DOIs	https://doi.org/10.1007/978-3-030-57675-2_25
State	Published - 2020
Event	26th International European Conference on Parallel and Distributed Computing, Euro-Par 2020 - Warsaw, Poland Duration: Aug 24 2020 → Aug 28 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12247 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	26th International European Conference on Parallel and Distributed Computing, Euro-Par 2020
Country/Territory	Poland
City	Warsaw
Period	08/24/20 → 08/28/20

Funding

This work was sponsored by the U.S. Department of Energy’s Office of Advanced Scientific Computing Research. This manuscript has been authored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan (http://energy.gov/ downloads/doe-public-access-plan).. Acknowledgements and Data Availability Statement. This project was supported partially by NSF grant CCF 1763657 and supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, program managers Robinson Pino and Lucy Nowell. This manuscript has been authored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. The datasets and code generated during and/or analysed during the current study are available in the Figshare repository: https://doi.org/10.6084/m9.figshare.12560 330 [19].

Funders	Funder number
DOE Public Access Plan
United States Government
National Science Foundation	CCF 1763657
U.S. Department of Energy
Office of Science
Advanced Scientific Computing Research	DE-AC05-00OR22725

Keywords

Algorithm-based fault tolerance
Coded computing
Communication-efficient algorithms
Error detection and correction
Fault-tolerant algorithms
Parallel matrix multiplication

Access to Document

10.1007/978-3-030-57675-2_25

Cite this

Jeong, H., Yang, Y., Gupta, V., Engelmann, C., Low, T. M., Cadambe, V., Ramchandran, K., & Grover, P. (2020). 3D coded SUMMA: Communication-efficient and robust parallel matrix multiplication. In M. Malawski, & K. Rzadca (Eds.), Euro-Par 2020: Parallel Processing - 26th International Conference on Parallel and Distributed Computing, Proceedings (pp. 392-407). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12247 LNCS). Springer. https://doi.org/10.1007/978-3-030-57675-2_25

Jeong, Haewon ; Yang, Yaoqing ; Gupta, Vipul et al. / 3D coded SUMMA : Communication-efficient and robust parallel matrix multiplication. Euro-Par 2020: Parallel Processing - 26th International Conference on Parallel and Distributed Computing, Proceedings. editor / Maciej Malawski ; Krzysztof Rzadca. Springer, 2020. pp. 392-407 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6ff6aa7e3bca43ab8f55b3dcc225e823,

title = "3D coded SUMMA: Communication-efficient and robust parallel matrix multiplication",

abstract = "In this paper, we propose a novel fault-tolerant parallel matrix multiplication algorithm called 3D Coded SUMMA that achieves higher failure-tolerance than replication-based schemes for the same amount of redundancy. This work bridges the gap between recent developments in coded computing and fault-tolerance in high-performance computing (HPC). The core idea of coded computing is the same as algorithm-based fault-tolerance (ABFT), which is weaving redundancy in the computation using error-correcting codes. In particular, we show that MatDot codes, an innovative code construction for parallel matrix multiplications, can be integrated into three-dimensional SUMMA (Scalable Universal Matrix Multiplication Algorithm [30]) in a communication-avoiding manner. To tolerate any two node failures, the proposed 3D Coded SUMMA requires ~50% less redundancy than replication, while the overhead in execution time is only about 5–10%.",

keywords = "Algorithm-based fault tolerance, Coded computing, Communication-efficient algorithms, Error detection and correction, Fault-tolerant algorithms, Parallel matrix multiplication",

author = "Haewon Jeong and Yaoqing Yang and Vipul Gupta and Christian Engelmann and Low, {Tze Meng} and Viveck Cadambe and Kannan Ramchandran and Pulkit Grover",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2020.; 26th International European Conference on Parallel and Distributed Computing, Euro-Par 2020 ; Conference date: 24-08-2020 Through 28-08-2020",

year = "2020",

doi = "10.1007/978-3-030-57675-2_25",

language = "English",

isbn = "9783030576745",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "392--407",

editor = "Maciej Malawski and Krzysztof Rzadca",

booktitle = "Euro-Par 2020",

}

Jeong, H, Yang, Y, Gupta, V, Engelmann, C, Low, TM, Cadambe, V, Ramchandran, K & Grover, P 2020, 3D coded SUMMA: Communication-efficient and robust parallel matrix multiplication. in M Malawski & K Rzadca (eds), Euro-Par 2020: Parallel Processing - 26th International Conference on Parallel and Distributed Computing, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12247 LNCS, Springer, pp. 392-407, 26th International European Conference on Parallel and Distributed Computing, Euro-Par 2020, Warsaw, Poland, 08/24/20. https://doi.org/10.1007/978-3-030-57675-2_25

3D coded SUMMA: Communication-efficient and robust parallel matrix multiplication. / Jeong, Haewon; Yang, Yaoqing; Gupta, Vipul et al.
Euro-Par 2020: Parallel Processing - 26th International Conference on Parallel and Distributed Computing, Proceedings. ed. / Maciej Malawski; Krzysztof Rzadca. Springer, 2020. p. 392-407 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12247 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - 3D coded SUMMA

T2 - 26th International European Conference on Parallel and Distributed Computing, Euro-Par 2020

AU - Jeong, Haewon

AU - Yang, Yaoqing

AU - Gupta, Vipul

AU - Engelmann, Christian

AU - Low, Tze Meng

AU - Cadambe, Viveck

AU - Ramchandran, Kannan

AU - Grover, Pulkit

N1 - Publisher Copyright: © Springer Nature Switzerland AG 2020.

PY - 2020

Y1 - 2020

N2 - In this paper, we propose a novel fault-tolerant parallel matrix multiplication algorithm called 3D Coded SUMMA that achieves higher failure-tolerance than replication-based schemes for the same amount of redundancy. This work bridges the gap between recent developments in coded computing and fault-tolerance in high-performance computing (HPC). The core idea of coded computing is the same as algorithm-based fault-tolerance (ABFT), which is weaving redundancy in the computation using error-correcting codes. In particular, we show that MatDot codes, an innovative code construction for parallel matrix multiplications, can be integrated into three-dimensional SUMMA (Scalable Universal Matrix Multiplication Algorithm [30]) in a communication-avoiding manner. To tolerate any two node failures, the proposed 3D Coded SUMMA requires ~50% less redundancy than replication, while the overhead in execution time is only about 5–10%.

AB - In this paper, we propose a novel fault-tolerant parallel matrix multiplication algorithm called 3D Coded SUMMA that achieves higher failure-tolerance than replication-based schemes for the same amount of redundancy. This work bridges the gap between recent developments in coded computing and fault-tolerance in high-performance computing (HPC). The core idea of coded computing is the same as algorithm-based fault-tolerance (ABFT), which is weaving redundancy in the computation using error-correcting codes. In particular, we show that MatDot codes, an innovative code construction for parallel matrix multiplications, can be integrated into three-dimensional SUMMA (Scalable Universal Matrix Multiplication Algorithm [30]) in a communication-avoiding manner. To tolerate any two node failures, the proposed 3D Coded SUMMA requires ~50% less redundancy than replication, while the overhead in execution time is only about 5–10%.

KW - Algorithm-based fault tolerance

KW - Coded computing

KW - Communication-efficient algorithms

KW - Error detection and correction

KW - Fault-tolerant algorithms

KW - Parallel matrix multiplication

UR - http://www.scopus.com/inward/record.url?scp=85090094091&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-57675-2_25

DO - 10.1007/978-3-030-57675-2_25

M3 - Conference contribution

AN - SCOPUS:85090094091

SN - 9783030576745

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 392

EP - 407

BT - Euro-Par 2020

A2 - Malawski, Maciej

A2 - Rzadca, Krzysztof

PB - Springer

Y2 - 24 August 2020 through 28 August 2020

ER -

Jeong H, Yang Y, Gupta V, Engelmann C, Low TM, Cadambe V et al. 3D coded SUMMA: Communication-efficient and robust parallel matrix multiplication. In Malawski M, Rzadca K, editors, Euro-Par 2020: Parallel Processing - 26th International Conference on Parallel and Distributed Computing, Proceedings. Springer. 2020. p. 392-407. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-57675-2_25

3D coded SUMMA: Communication-efficient and robust parallel matrix multiplication

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this