Campus Units
Electrical and Computer Engineering, Mathematics
Document Type
Article
Publication Version
Accepted Manuscript
Publication Date
11-9-2018
Journal or Book Title
IEEE Communications Letters
DOI
10.1109/LCOMM.2018.2880213
Abstract
Distributed matrix multiplication is widely used in several scientific domains. It is well recognized that computation times on distributed clusters are often dominated by the slowest workers (called stragglers). Recent work has demonstrated that straggler mitigation can be viewed as a problem of designing erasure codes. For matrices A and B, the technique essentially maps the computation of ATB into the multiplication of smaller (coded) submatrices. The stragglers are treated as erasures in this process. The computation can be completed as long as a certain number of workers (called the recovery threshold) complete their assigned tasks. We present a novel coding strategy for this problem when the absolute values of the matrix entries are sufficiently small. We demonstrate a tradeoff between the assumed absolute value bounds on the matrix entries and the recovery threshold. At one extreme, we are optimal with respect to the recovery threshold and on the other extreme, we match the threshold of prior work. Experimental results on cloud-based clusters validate the benefits of our method.
Rights
Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Copyright Owner
IEEE
Copyright Date
2018
Language
en
File Format
application/pdf
Recommended Citation
Tang, Li; Konstantinidis, Konstantinos; and Ramamoorthy, Aditya, "Erasure coding for distributed matrix multiplication for matrices with bounded entries" (2018). Electrical and Computer Engineering Publications. 201.
https://lib.dr.iastate.edu/ece_pubs/201
Comments
This is a manuscript of an article published as Tang, Li, Kostas Konstantinidis, and Aditya Ramamoorthy. "Erasure coding for distributed matrix multiplication for matrices with bounded entries." IEEE Communications Letters (2018). DOI: 10.1109/LCOMM.2018.2880213. Posted with permission.