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{Amiri:2019:10.1109/TSP.2019.2952051,
author = {Amiri, MM and Gunduz, D},
doi = {10.1109/TSP.2019.2952051},
journal = {IEEE Transactions on Signal Processing},
pages = {6270--6284},
title = {Computation scheduling for distributed machine learning with straggling workers},
url = {http://dx.doi.org/10.1109/TSP.2019.2952051},
volume = {67},
year = {2019}
}
Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - We study scheduling of computation tasks across n workers in a large scale distributed learning problem with the help of a master. Computation and communication delays are assumed to be random, and redundant computations are assigned to workers in order to tolerate stragglers. We consider sequential computation of tasks assigned to a worker, while the result of each computation is sent to the master right after its completion. Each computation round, which can model an iteration of the stochastic gradient descent (SGD) algorithm, is completed once the master receives k distinct computations, referred to as the computation target. Our goal is to characterize the average completion time as a function of the computation load, which denotes the portion of the dataset available at each worker, and the computation target. We propose two computation scheduling schemes that specify the tasks assigned to each worker, as well as their computation schedule, i.e., the order of execution. Assuming a general statistical model for computation and communication delays, we derive the average completion time of the proposed schemes. We also establish a lower bound on the minimum average completion time by assuming prior knowledge of the random delays. Experimental results carried out on Amazon EC2 cluster show a significant reduction in the average completion time over existing coded and uncoded computing schemes. It is also shown numerically that the gap between the proposed scheme and the lower bound is relatively small, confirming the efficiency of the proposed scheduling design.
AU  - Amiri,MM
AU  - Gunduz,D
DO  - 10.1109/TSP.2019.2952051
EP  - 6284
PY  - 2019///
SN  - 1053-587X
SP  - 6270
TI  - Computation scheduling for distributed machine learning with straggling workers
T2  - IEEE Transactions on Signal Processing
UR  - http://dx.doi.org/10.1109/TSP.2019.2952051
UR  - http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000502992600007&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
UR  - https://ieeexplore.ieee.org/document/8892615
UR  - http://hdl.handle.net/10044/1/86603
VL  - 67
ER  -
Download