Data-parallelism has been widely used in order to distribute the training of large Deep Neural Networks (DNN) among multiple workers (GPU/TPU). In the data-parallel context, a large proportion of the training time is spent on collective communication to synchronize gradients between model replicas on each device. It was observed that not all gradients are necessary for the model convergence and the gradient tensor could be greatly sparsified in order to reduce the communication volume. Prior works have proposed to sparsify gradients depending on their magnitude, approach commonly called top-k. However, top-k incurs computation overhead of bitonic sorting and has scalability issues on Ring All-Reduce due to the necessity to send indices. In this work, we show that random gradient pruning can achieve convergence at minimal accuracy loss. Moreover, we propose Skip-Reduce -- a novel approach to perform gradient pruning that does not rely on sending indices and instead modifies the underlying communication algorithm. Our approach has no computational overhead and is scalable on any number of devices.
데이터 병렬 방식의 학습은 대규모 DNN 모델의 학습을 여러 개의 연산 장치로 분산시키는 데에 널리 이용되고 있다. 데이터 병렬 방식에서는 각 연산 장치의 DNN 모델 복사본 간에 그레디언트를 동기화하기 위한 집합 통신이 학습 시간에서 큰 비중을 차지한다. 그러나, 모델 수렴에 모든 그레디언트가 필수적으로 요구되지 않으며, 따라서 그레디언트 텐서를 크게 희소화하여 통신량을 줄일 수 있다. 기존 연구에서는 크기 기반의 그레디언트 프루닝 방식을 제안하였고, 이는 top-k라고도 불린다. 그러나, top-k는 비토닉 정렬의 계산 부하와 통신에 포함되는 인덱스 정보 때문에 Ring All-Reduce에서 확장성 문제가 있다. 본 연구에서는 무작위 그레디언트 프루닝이 최소 정확도 손실을 보장하는 것을 보였으며, 인덱스 정보 없이 하위 통신 알고리즘을 수정함으로써 그레디언트 프루닝을 수행하는 새로운 방법인 Skip-Reduce를 제안한다. 제안된 방식은 계산 부하가 없으며, 매우 높은 확장성을 가진다.
