Gradient Coding With Dynamic Clustering for Straggler-Tolerant Distributed Learning
Gradient Coding With Dynamic Clustering for Straggler-Tolerant Distributed Learning
复制标题
DOI：
10.1109/tcomm.2022.3166902
复制
发表时间：
2021-03
影响因子：
8.3
通讯作者：
Baturalp Buyukates;Emre Ozfatura;S. Ulukus;Deniz Gündüz
中科院分区：
文献类型：
--
作者：
Baturalp Buyukates;Emre Ozfatura;S. Ulukus;Deniz Gündüz
分布式实现对于加速大规模机器学习应用至关重要。分布式梯度下降（GD）被广泛用于通过将数据集分布在多个工作者之间来并行化学习任务。分布式同步GD中每次迭代完成时间的一个重要性能瓶颈是分散的工作者。编码分布式计算技术最近被引入，以减轻离散和加速GD迭代分配冗余计算的工人。在本文中，我们介绍了一种新的范例的动态编码计算，分配冗余数据的工人获得的灵活性，动态选择一组可能的代码取决于过去的离散行为。特别是，我们提出了梯度编码（GC）与动态聚类，称为GC-DC，并调节在每个集群中的掉队者的数量，在每次迭代时动态形成的集群。随着时间相关的离散行为，GC-DC随着时间的推移适应离散行为;特别是，在每次迭代中，GC-DC的目标是基于过去的离散行为尽可能均匀地将离散者分布在集群中。对于同构和异构的工人模型，我们数值表明，GC-DC提供了显着的改善，在平均每次迭代完成时间没有增加的通信负载相比，原来的GC计划。
Distributed implementations are crucial in speeding up large scale machine learning applications. Distributed gradient descent (GD) is widely employed to parallelize the learning task by distributing the dataset across multiple workers. A significant performance bottleneck for the per-iteration completion time in distributed synchronous GD is straggling workers. Coded distributed computation techniques have been introduced recently to mitigate stragglers and to speed up GD iterations by assigning redundant computations to workers. In this paper, we introduce a novel paradigm of dynamic coded computation, which assigns redundant data to workers to acquire the flexibility to dynamically choose from among a set of possible codes depending on the past straggling behavior. In particular, we propose gradient coding (GC) with dynamic clustering, called GC-DC, and regulate the number of stragglers in each cluster by dynamically forming the clusters at each iteration. With time-correlated straggling behavior, GC-DC adapts to the straggling behavior over time; in particular, at each iteration, GC-DC aims at distributing the stragglers across clusters as uniformly as possible based on the past straggler behavior. For both homogeneous and heterogeneous worker models, we numerically show that GC-DC provides significant improvements in the average per-iteration completion time without an increase in the communication load compared to the original GC scheme.