Tree Gradient Coding
Tree Gradient Coding
复制标题
DOI：
10.1109/isit.2019.8849431
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Amirhossein Reisizadeh;Saurav Prakash;Ramtin Pedarsani;A. Avestimehr
中科院分区：
文献类型：
--
作者：
Amirhossein Reisizadeh;Saurav Prakash;Ramtin Pedarsani;A. Avestimehr
扩展分布式机器学习系统面临两个主要瓶颈——落后者造成的延迟和有限的通信带宽。最近，已经提出了许多编码理论策略来缓解这些瓶颈。特别是，提出了梯度编码（GC）方案，通过为落后者提供鲁棒性来加速同步主从设置中的分布式梯度下降算法。然而，用于分布式学习的主从架构的一个主要缺点是主节点的带宽争用，这会随着集群大小的增加而显着降低性能。在本文中，我们提出了一种用于分布式梯度聚合的名为树梯度编码（TGC）的新框架，它可以并行化树拓扑上的通信，同时提供落后的鲁棒性。作为我们的主要贡献，我们描述了给定树拓扑和离散弹性的 TGC 的最小计算负载，并设计了一种实现此最佳计算负载的树梯度编码算法。此外，我们还提供了在 Amazon EC2 上进行的实验结果，其中 TGC 与 GC 相比，将训练时间加快了 18.8 倍。
Scaling up distributed machine learning systems face two major bottlenecks – delays due to stragglers and limited communication bandwidth. Recently, a number of coding theoretic strategies have been proposed for mitigating these bottlenecks. In particular, the Gradient Coding (GC) scheme was proposed to speed up distributed gradient descent algorithm in a synchronous master-worker setting by providing robustness to stragglers. A major drawback of the master-worker architecture for distributed learning is however, the bandwidth contention at the master, which can significantly deteriorate the performance as the cluster size increases. In this paper, we propose a new framework named Tree Gradient Coding (TGC) for distributed gradient aggregation, which parallelizes communication over a tree topology while providing straggler robustness. As our main contribution, we characterize the minimum computation load for TGC for a given tree topology and straggler resiliency, and design a tree gradient coding algorithm that achieves this optimal computation load. Furthermore, we provide results from experiments over Amazon EC2, where TGC speeds up the training time by up to 18.8× in comparison to GC.