Polynomial codes: An optimal design for high-dimensional coded matrix multiplication

Qian Yu, Mohammad Ali Maddah-Ali, A. Salman Avestimehr

Research output: Contribution to journalConference articlepeer-review

293 Scopus citations

Abstract

We consider a large-scale matrix multiplication problem where the computation is carried out using a distributed system with a master node and multiple worker nodes, where each worker can store parts of the input matrices. We propose a computation strategy that leverages ideas from coding theory to design intermediate computations at the worker nodes, in order to optimally deal with straggling workers. The proposed strategy, named as polynomial codes, achieves the optimum recovery threshold, defined as the minimum number of workers that the master needs to wait for in order to compute the output. This is the first code that achieves the optimal utilization of redundancy for tolerating stragglers or failures in distributed matrix multiplication. Furthermore, by leveraging the algebraic structure of polynomial codes, we can map the reconstruction problem of the final output to a polynomial interpolation problem, which can be solved efficiently. Polynomial codes provide order-wise improvement over the state of the art in terms of recovery threshold, and are also optimal in terms of several other metrics including computation latency and communication load. Moreover, we extend this code to distributed convolution and show its order-wise optimality.

Original languageEnglish (US)
Pages (from-to)4404-4414
Number of pages11
JournalAdvances in Neural Information Processing Systems
Volume2017-December
StatePublished - 2017
Externally publishedYes
Event31st Annual Conference on Neural Information Processing Systems, NIPS 2017 - Long Beach, United States
Duration: Dec 4 2017Dec 9 2017

Bibliographical note

Publisher Copyright:
© 2017 Neural information processing systems foundation. All rights reserved.

Fingerprint

Dive into the research topics of 'Polynomial codes: An optimal design for high-dimensional coded matrix multiplication'. Together they form a unique fingerprint.

Cite this