Computation scheduling for distributed machine learning with straggling workers - Mohammadi,Amiri M; Gunduz,D (Institute of Electrical and Electronics Engineers, 2019)
We study scheduling of computation tasks acrossnworkers in a large scale distributed learning problem. Computa-tion speeds of the workers are assumed to be heterogeneous andunknown to the master, and redundant computations are assignedto the workers in order to tolerate straggling workers. We con-sider sequential computation and instantaneous communicationfrom each worker to the master, and each computation round,which can model a single iteration of the stochastic gradientdescent (SGD) algorithm, iscompletedonce the master receivesk≤ndistinct computations, referred to as thecomputationtarget. Our goal is to characterize theaverage completion timeas a function of thecomputation load, which denotes the portionof the dataset available at each worker, and the computationtarget. We propose two computation scheduling schemes thatspecify the computation tasks assigned to each worker, as wellas their order of execution. We also establish a lower bound onthe minimum average completion time. Numerical results showa significant reduction in the average computation time over theexisting coded and uncoded computing schemes.