CodedReduce: A Fast and Robust Framework for Gradient Aggregation in Distributed Learning

doi:10.1109/TNET.2021.3109097

Return

CodedReduce: A Fast and Robust Framework for Gradient Aggregation in Distributed Learning

2022-02-01

Amirhossein Reisizadeh *

Saurav Prakash

Ramtin Pedarsani

Avestimehr, Amir Salman

DOI：10.1109/TNET.2021.3109097

Original

Original request for help

Save

Abstract

En 中文

We focus on the commonly used synchronous Gradient Descent paradigm for large-scale distributed learning, for which there has been a growing interest to develop efficient and robust gradient aggregation strategies that overcome two key system bottlenecks: communication bandwidth and stragglers' delays. In particular, Ring-AllReduce (RAR) design has been proposed to avoid bandwidth bottleneck at any particular node by allowing each worker to only communicate with its neighbors that are arranged in a logical ring. On the other hand, Gradient Coding (GC) has been recently proposed to mitigate stragglers in a master-worker topology by allowing carefully designed redundant allocation of the data set to the workers. We propose a joint communication topology design and data set allocation strategy, named CodedReduce (CR), that combines the best of both RAR and GC. That is, it parallelizes the communications over a tree topology leading to efficient bandwidth utilization, and carefully designs a redundant data set allocation and coding strategy at the nodes to make the proposed gradient aggregation scheme robust to stragglers. In particular, we quantify the communication parallelization gain and resiliency of the proposed CR scheme, and prove its optimality when the communication topology is a regular tree. Moreover, we characterize the expected run-time of CR and show order-wise speedups compared to the benchmark schemes. Finally, we empirically evaluate the performance of our proposed CR design over Amazon EC2 and demonstrate that it achieves speedups of up to 27.2x and 7.0x, respectively over the benchmarks GC and RAR.

Keywords:

Bandwidth

Topology

Resilience

Distance learning

Computer aided instruction

Encoding

Training

Distributed learning

communication topology

gradient aggregation