Speeding Up Distributed Learning via Sparse and Flexible Coded Computing
Jingzhe Zhang, Xiaofan He, Huaiyu Dai · IEEE Transactions on Information Theory · 2024
Plagued by slow or failing workers (also known as stragglers), the speedup gain assumed by distributed learning often falls short. Although substantial efforts have been devoted to mitigating this straggling effect with coding-theoretic techniques, existing pioneering works often suffer from two issues: dense combination and inflexibility. In particular, a code that involves dense combination of sub-tasks may destroy sparsity and lead to heavy workload. In contrast, an inflexible code that conservatively designs its computation procedure according to the presumed maximum number of stragglers may entail unnecessary redundancy when the actual number of stragglers is small. To this end, a generic framework based on matrix splitting is proposed in this work to construct sparse and flexible codes. Specifically, by splitting an original sparse coding matrix into two sparser sub-matrices, a two-layer coded computation that maintains sparsity can be created accordingly. In the meantime, when the actual number of stragglers is small, the computation may be flexibly terminated at layer-one without executing layer-two, thereby avoiding unnecessary computation. Based on this framework, a novel flexible Bernoulli code is proposed. In addition, by deriving a lower bound in closed-form through the lens of a bipartite graph, its decoding probability is shown to be high and asymptotically one. Moreover, extensive simulations including an application in distributed learning of LeNet are conducted to validate the effectiveness of the proposed scheme.