Imperial College London
Portrait Picture

ProfessorDenizGunduz

Faculty of Engineering, Department of Electrical and Electronic Engineering

Professor in Information Processing
 
 
 
//

Contact

 

+44 (0)20 7594 6218d.gunduz Website

 
 
//

Assistant

 

Ms Joan O'Brien +44 (0)20 7594 6316

 
//

Location

 

1016Electrical EngineeringSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@article{Hasircioglu:2021:10.1109/jsait.2021.3105365,
author = {Hasircioglu, B and Gomez-Vilardebo, J and Gunduz, D},
doi = {10.1109/jsait.2021.3105365},
journal = {IEEE Journal on Selected Areas in Information Theory},
pages = {814--829},
title = {Bivariate polynomial coding for efficient distributed matrix multiplication},
url = {http://dx.doi.org/10.1109/jsait.2021.3105365},
volume = {2},
year = {2021}
}
Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - Coded computing is an effective technique to mitigate “stragglers” in large-scale and distributed matrix multiplication. In particular, univariate polynomial codes have been shown to be effective in straggler mitigation by making the computation time depend only on the fastest workers. However, these schemes completely ignore the work done by the straggling workers resulting in a waste of computational resources. To reduce the amount of work left unfinished at workers, one can further decompose the matrix multiplication task into smaller sub-tasks, and assign multiple sub-tasks to each worker, possibly heterogeneously, to better fit their particular storage and computation capacities. In this work, we propose a novel family of bivariate polynomial codes to efficiently exploit the work carried out by straggling workers. We show that bivariate polynomial codes bring significant advantages in terms of upload communication costs and storage efficiency, measured in terms of the number of sub-tasks that can be computed per worker. We propose two bivariate polynomial coding schemes. The first one exploits the fact that bivariate interpolation is always possible on a rectangular grid of evaluation points. We obtain such points at the cost of adding some redundant computations. For the second scheme, we relax the decoding constraints and require decodability for almost all choices of the evaluation points. We present interpolation sets satisfying such decodability conditions for certain storage configurations of workers. Our numerical results show that bivariate polynomial coding considerably reduces the average computation time of distributed matrix multiplication. We believe this work opens up a new class of previously unexplored coding schemes for efficient coded distributed computation.
AU  - Hasircioglu,B
AU  - Gomez-Vilardebo,J
AU  - Gunduz,D
DO  - 10.1109/jsait.2021.3105365
EP  - 829
PY  - 2021///
SN  - 2641-8770
SP  - 814
TI  - Bivariate polynomial coding for efficient distributed matrix multiplication
T2  - IEEE Journal on Selected Areas in Information Theory
UR  - http://dx.doi.org/10.1109/jsait.2021.3105365
UR  - https://ieeexplore.ieee.org/document/9519610
UR  - http://hdl.handle.net/10044/1/101297
VL  - 2
ER  -
Download