Design and Performance Analysis of Partial Computation Output Schemes for Accelerating Coded Machine Learning
Publication in refereed journal

Times Cited
Web of Science0WOS source URL (as at 15/04/2024) Click here for the latest count
Altmetrics Information

Other information
AbstractCoded machine learning is a technique to use codes, such as (n,q) -maximum-distance-separable ( (n,q) -MDS) codes, to reduce the negative effect of stragglers by requiring q out of n workers to complete their computation. However, the MDS scheme incurs significant inefficiency in wasting stragglers' unfinished computation and keeping faster workers idle. Accordingly, this paper proposes to fragment each worker's load into small pieces and utilizes all workers' partial computation outputs (PCO) to reduce the overall runtime. While easy-to-implement, the theoretical runtime performance analysis of our PCO scheme is challenging. We present new bounds and asymptotic analysis to prove that our PCO scheme always reduces the overall runtime for any random distribution of workers' speeds, and its performance gain over the MDS scheme can be arbitrarily large under high variability of workers' speeds. Moreover, our analysis shows another advantage: the PCO scheme's performance is robust and insensitive to system parameter variations, while the MDS scheme has to know workers' speeds for carefully optimizing q . Finally, our realistic experiments validate that the PCO scheme reduces the overall runtime from that of the MDS scheme by at least 12.3%, and we implement our PCO scheme for solving a typical machine learning problem of linear regression.
All Author(s) ListXu Xinping, Lin Xiaojun, Duan Lingjie
Journal nameIEEE Transactions on Network Science and Engineering
Volume Number10
Issue Number2
Pages1119 - 1130
LanguagesEnglish-United States

Last updated on 2024-16-04 at 00:36