2018

GossipGraD: Scalable Deep Learning using Gossip Communication based Asynchronous Gradient Descent

Daily, Jeff, Vishnu, Abhinav, Siegel, Charles et al.

Understand

In this paper, we present GossipGraD - a gossip communication protocol based Stochastic Gradient Descent (SGD) algorithm for scaling Deep Learning (DL) algorithms on large-scale systems.

The salient features of GossipGraD are: 1) reduction in overall communication complexity from {\Theta}(log(p)) for p compute nodes in well-studied SGD to O(1), 2) model diffusion such that compute nodes exchange their updates (gradients) indirectly after every log(p) steps, 3) rotation of communication partners for facilitating direct diffusion of gradients, 4) asynchronous distributed shuffle of samples during the feedforward phase in SGD to prevent over-fitting, 5) asynchronous communication of gradients for further reducing the communication cost of SGD and GossipGraD.
We implement GossipGraD for GPU and CPU clusters and use NVIDIA GPUs (Pascal P100) connected with InfiniBand, and Intel Knights Landing (KNL) connected with Aries network.
We evaluate GossipGraD using well-studied dataset ImageNet-1K (~250GB), and widely studied neural network topologies such as GoogLeNet and ResNet50 (current winner of ImageNet Large Scale Visualization Research Challenge (ILSVRC)).

Built on

H. Robbins and D. Siegmund, “A convergence theorem for non negative almost supermartingales and some applications,” in Herbert Robbins Selected Papers . Springer, 1985, pp. 111–135
1985
Earlier work this paper cites.
W. Gropp, E. Lusk, N. Doss, and A. Skjellum, “A High-Performance, Portable Implementation of the MPI Message Passing Interface Standard,” Parallel Computing , vol. 22, no. 6, pp. 789–828, 1996
1996
Earlier work this paper cites.
A. Geist, W. Gropp, S. Huss-Lederman, A. Lumsdaine, E. L. Lusk, W. Saphir, T. Skjellum, and M. Snir, “MPI-2: Extending the message-passing interface,” in Euro-Par, Vol. I , 1996, pp. 128–135
1996
Earlier work this paper cites.
D. Saad, “Online algorithms and stochastic approximations,” Online Learning , vol. 5, 1998
1998
Earlier work this paper cites.
Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” Proceedings of the IEEE , vol. 86, no. 11, pp. 2278–2324, 1998
1998
Earlier work this paper cites.
K. C. Kiwiel, “Convergence and efficiency of subgradient methods for quasiconvex minimization,” Mathematical programming , vol. 90, no. 1, pp. 1–25, 2001
2001
Earlier work this paper cites.
R. Collobert, S. Bengio, and J. Marithoz, “Torch: A modular machine learning software library,” 2002
2002
Earlier work this paper cites.
S. Sur, H.-W. Jin, L. Chai, and D. K. Panda, “Rdma read based rendezvous protocol for mpi over infiniband: design alternatives and benefits.” in PPOPP , 2006, pp. 32–39
2006
Earlier work this paper cites.
G. E. Hinton and S. Osindero, “A fast learning algorithm for deep belief nets,” Neural Computation , vol. 18, p. 2006, 2006
2006
Earlier work this paper cites.
G. E. Hinton and R. R. Salakhutdinov, “Reducing the dimensionality of data with neural networks,” Science , vol. 313, no. 5786, pp. 504–507, Jul. 2006. [Online]. Available: http://www.ncbi.nlm.nih.gov/sites/entrez?db=pubmed&uid=16873662&cmd=showdetailview&indexed=google
2006
Earlier work this paper cites.
Y. Bengio, P. Lamblin, D. Popovici, and H. Larochelle, “Greedy layer-wise training of deep networks,” in Advances in Neural Information Processing Systems 19 , B. Schölkopf, J. C. Platt, and T. Hoffman, Eds. MIT Press, 2007, pp. 153–160. [Online]. Available: http://papers.nips.cc/paper/3048-greedy-layer-wise-training-of-deep-networks.pdf
2007
Earlier work this paper cites.
A. Krizhevsky, “Learning multiple layers of features from tiny images,” University of Toronto, Tech. Rep., 2009
2009
Earlier work this paper cites.
J. Bergstra, O. Breuleux, F. Bastien, P. Lamblin, R. Pascanu, G. Desjardins, J. Turian, D. Warde-Farley, and Y. Bengio, “Theano: a CPU and GPU math expression compiler,” in Proceedings of the Python for Scientific Computing Conference (SciPy) , Jun. 2010, oral Presentation
2010
Earlier work this paper cites.
T. Hoefler, T. Schneider, and A. Lumsdaine, “Characterizing the Influence of System Noise on Large-Scale Applications by Simulation,” in International Conference for High Performance Computing, Networking, Storage and Analysis (SC’10) , Nov. 2010
2010
Earlier work this paper cites.
P. Vincent, H. Larochelle, I. Lajoie, Y. Bengio, and P.-A. Manzagol, “Stacked denoising autoencoders: Learning useful representations in a deep network with a local denoising criterion,” J. Mach. Learn. Res. , vol. 11, pp. 3371–3408, Dec. 2010. [Online]. Available: http://dl.acm.org/citation.cfm?id=1756006.1953039
2010
Earlier work this paper cites.
A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” in Advances in Neural Information Processing Systems 25 , F. Pereira, C. Burges, L. Bottou, and K. Weinberger, Eds. Curran Associates, Inc., 2012, pp. 1097–1105. [Online]. Available: http://papers.nips.cc/paper/4824-imagenet-classification-with-deep-convolutional-neural-networks.pdf
2012
Earlier work this paper cites.
F. Bastien, P. Lamblin, R. Pascanu, J. Bergstra, I. J. Goodfellow, A. Bergeron, N. Bouchard, and Y. Bengio, “Theano: new features and speed improvements,” Deep Learning and Unsupervised Feature Learning NIPS 2012 Workshop, 2012
2012
Earlier work this paper cites.
J. Dean, G. S. Corrado, R. Monga, K. Chen, M. Devin, Q. V. Le, M. Z. Mao, M. Ranzato, A. Senior, P. Tucker, K. Yang, and A. Y. Ng, “Large scale distributed deep networks,” in Proceedings of the 25th International Conference on Neural Information Processing Systems , ser. NIPS’12. USA: Curran Associates Inc., 2012, pp. 1223–1231. [Online]. Available: http://dl.acm.org/citation.cfm?id=2999134.2999271
2012
Earlier work this paper cites.
J. Dean, G. Corrado, R. Monga, K. Chen, M. Devin, M. Mao, M. Ranzato, A. Senior, P. Tucker, K. Yang, Q. V. Le, and A. Y. Ng, “Large scale distributed deep networks,” in Advances in Neural Information Processing Systems 25 , P. Bartlett, F. Pereira, C. Burges, L. Bottou, and K. Weinberger, Eds., 2012, pp. 1232–1240. [Online]. Available: http://books.nips.cc/papers/files/nips25/NIPS2012_0598.pdf
2012
Earlier work this paper cites.
Y. LeCun, C. Cortes, and C. J. Burges, “The mnist database of handwritten digits, 1998,” Available electronically at http://yann.lecun.com/exdb/mnist , 2012
2012
Earlier work this paper cites.
T. Tieleman and G. Hinton, “Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude,” COURSERA: Neural networks for machine learning , vol. 4, no. 2, pp. 26–31, 2012
2012
Earlier work this paper cites.
A. Bhatele, K. Mohror, S. H. Langer, and K. E. Isaacs, “There goes the neighborhood: Performance degradation due to nearby jobs,” in Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis , ser. SC ’13. New York, NY, USA: ACM, 2013, pp. 41:1–41:12. [Online]. Available: http://doi.acm.org/10.1145/2503210.2503247
2013
Earlier work this paper cites.
Q. Ho, J. Cipar, H. Cui, J. K. Kim, S. Lee, P. B. Gibbons, G. A. Gibson, G. R. Ganger, and E. P. Xing, “More effective distributed ml via a stale synchronous parallel parameter server,” in Proceedings of the 26th International Conference on Neural Information Processing Systems , ser. NIPS’13. USA: Curran Associates Inc., 2013, pp. 1223–1231. [Online]. Available: http://dl.acm.org/citation.cfm?id=2999611.2999748
2013
Earlier work this paper cites.

Similar

P. Baldi, P. Sadowski, and D. Whiteson, “Searching for Exotic Particles in High-Energy Physics with Deep Learning,” Nature Commun. , vol. 5, p. 4308, 2014
2014
Cited alongside, same era.
Y. Jia, E. Shelhamer, J. Donahue, S. Karayev, J. Long, R. Girshick, S. Guadarrama, and T. Darrell, “Caffe: Convolutional architecture for fast feature embedding,” arXiv preprint arXiv:1408.5093 , 2014
Original
2014
Cited alongside, same era.
T. Chilimbi, Y. Suzue, J. Apacible, and K. Kalyanaraman, “Project adam: Building an efficient and scalable deep learning training system,” in 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14) . Broomfield, CO: USENIX Association, 2014, pp. 571–582. [Online]. Available: https://www.usenix.org/conference/osdi14/technical-sessions/presentation/chilimbi
2014
Cited alongside, same era.
A. Agarwal, E. Akchurin, C. Basoglu, G. Chen, S. Cyphers, J. Droppo, A. Eversole, B. Guenter, M. Hillebrand, R. Hoens, X. Huang, Z. Huang, V. Ivanov, A. Kamenev, P. Kranen, O. Kuchaiev, W. Manousek, A. May, B. Mitra, O. Nano, G. Navarro, A. Orlov, M. Padmilac, H. Parthasarathi, B. Peng, A. Reznichenko, F. Seide, M. L. Seltzer, M. Slaney, A. Stolcke, Y. Wang, H. Wang, K. Yao, D. Yu, Y. Zhang, and G. Zweig, “An introduction to computational networks and the computational network toolkit,” Tech. Rep. MSR-TR-2014-112, August 2014. [Online]. Available: http://research.microsoft.com/apps/pubs/default.aspx?id=226641
2014
Cited alongside, same era.
M. Li, D. G. Andersen, A. Smola, and K. Yu, “Communication efficient distributed machine learning with the parameter server,” in Proceedings of the 27th International Conference on Neural Information Processing Systems , ser. NIPS’14. Cambridge, MA, USA: MIT Press, 2014, pp. 19–27. [Online]. Available: http://dl.acm.org/citation.cfm?id=2968826.2968829
2014
Cited alongside, same era.
Y. N. Dauphin, R. Pascanu, C. Gulcehre, K. Cho, S. Ganguli, and Y. Bengio, “Identifying and attacking the saddle point problem in high-dimensional non-convex optimization,” in Advances in neural information processing systems , 2014, pp. 2933–2941
2014
Cited alongside, same era.
——, “One weird trick for parallelizing convolutional neural networks,” CoRR , vol. abs/1404.5997, 2014. [Online]. Available: http://arxiv.org/abs/1404.5997
Original
2014
Cited alongside, same era.
A. Agarwal, E. Akchurin, C. Basoglu, G. Chen, S. Cyphers, J. Droppo, A. Eversole, B. Guenter, M. Hillebrand, R. Hoens, X. Huang, Z. Huang, V. Ivanov, A. Kamenev, P. Kranen, O. Kuchaiev, W. Manousek, A. May, B. Mitra, O. Nano, G. Navarro, A. Orlov, M. Padmilac, H. Parthasarathi, B. Peng, A. Reznichenko, F. Seide, M. L. Seltzer, M. Slaney, A. Stolcke, Y. Wang, H. Wang, K. Yao, D. Yu, Y. Zhang, and G. Zweig, “An introduction to computational networks and the computational network toolkit,” Tech. Rep. MSR-TR-2014-112, August 2014. [Online]. Available: http://research.microsoft.com/apps/pubs/default.aspx?id=226641
2014
Cited alongside, same era.
M. Bianchini and F. Scarselli, “On the complexity of neural network classifiers: A comparison between shallow and deep architectures,” IEEE Transactions on Neural Networks and Learning Systems , vol. 25, no. 8, pp. 1553 – 1565, 2014
2014
Cited alongside, same era.
C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich, “Going deeper with convolutions,” in CVPR 2015 , 2015. [Online]. Available: http://arxiv.org/abs/1409.4842
Original
2015
Cited alongside, same era.
M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, I. Goodfellow, A. Harp, G. Irving, M. Isard, Y. Jia, R. Jozefowicz, L. Kaiser, M. Kudlur, J. Levenberg, D. Mané, R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, J. Shlens, B. Steiner, I. Sutskever, K. Talwar, P. Tucker, V. Vanhoucke, V. Vasudevan, F. Viégas, O. Vinyals, P. Warden, M. Wattenberg, M. Wicke, Y. Yu, and X. Zheng, “TensorFlow: Large-scale machine learning on heterogeneous systems,” 2015, software available from tensorflow.org. [Online]. Available: http://tensorflow.org/
2015
Cited alongside, same era.
C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna, “Rethinking the inception architecture for computer vision,” CoRR , vol. abs/1512.00567, 2015. [Online]. Available: http://arxiv.org/abs/1512.00567
Original
2015
Cited alongside, same era.

Then

K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition , 2016, pp. 770–778
2016
Later among the works it cites.
A. Vishnu, C. Siegel, and J. Daily, “Distributed tensorflow with mpi,” arXiv preprint arXiv:1603.02339 , 2016
Original
2016
Later among the works it cites.
H. Cui, H. Zhang, G. R. Ganger, P. B. Gibbons, and E. P. Xing, “Geeps: Scalable deep learning on distributed gpus with a gpu-specialized parameter server,” in Proceedings of the Eleventh European Conference on Computer Systems , ser. EuroSys ’16. New York, NY, USA: ACM, 2016, pp. 4:1–4:16. [Online]. Available: http://doi.acm.org/10.1145/2901318.2901323
2016
Later among the works it cites.
M. Blot, D. Picard, M. Cord, and N. Thome, “Gossip training for deep learning,” CoRR , vol. abs/1611.09726, 2016. [Online]. Available: http://arxiv.org/abs/1611.09726
Original
2016
Later among the works it cites.
D. Das, S. Avancha, D. Mudigere, K. Vaidyanathan, S. Sridharan, D. D. Kalamkar, B. Kaul, and P. Dubey, “Distributed deep learning using synchronous stochastic gradient descent,” CoRR , vol. abs/1602.06709, 2016. [Online]. Available: http://arxiv.org/abs/1602.06709
Original
2016
Later among the works it cites.
P. H. Jin, Q. Yuan, F. N. Iandola, and K. Keutzer, “How to scale distributed deep learning?” CoRR , vol. abs/1611.04581, 2016. [Online]. Available: http://arxiv.org/abs/1611.04581
Original
2016
Later among the works it cites.
NVIDIA Corporation, “NVIDIA/caffe, forked from BVLC/caffe,” https://github.com/NVIDIA/caffe, 2016
2016
Later among the works it cites.
Intel Corporation, “intel/caffe, forked from BVLC/caffe,” https://github.com/intel/caffe, 2016
2016
Later among the works it cites.
S. Zheng, Q. Meng, T. Wang, W. Chen, N. Yu, Z. Ma, and T. Liu, “Asynchronous stochastic gradient descent with delay compensation for distributed deep learning,” CoRR , vol. abs/1609.08326, 2016. [Online]. Available: http://arxiv.org/abs/1609.08326
Original
2016
Later among the works it cites.
P. Goyal, P. Dollár, R. Girshick, P. Noordhuis, L. Wesolowski, A. Kyrola, A. Tulloch, Y. Jia, and K. He, “Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour,” ArXiv e-prints , Jun. 2017
2017
Later among the works it cites.
M. Cho, U. Finkler, S. Kumar, D. Kung, V. Saxena, and D. Sreedhar, “PowerAI DDL,” ArXiv e-prints , Aug. 2017
2017
Later among the works it cites.
A. A. Awan, K. Hamidouche, J. M. Hashmi, and D. K. Panda, “S-caffe: Co-designing mpi runtimes and caffe for scalable deep learning on modern gpu clusters,” in Proceedings of the 22Nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming , ser. PPoPP ’17. New York, NY, USA: ACM, 2017, pp. 193–205. [Online]. Available: http://doi.acm.org/10.1145/3018743.3018769
2017
Later among the works it cites.
“Caffeonspark github project,” https://github.com/yahoo/CaffeOnSpark , accessed: 2017-01-23
2017
Later among the works it cites.
P. Chaudhari, C. Baldassi, R. Zecchina, S. Soatto, and A. Talwalkar, “Parle: parallelizing stochastic gradient descent,” ArXiv e-prints , Jul. 2017
2017
Later among the works it cites.
“Paddlepaddle,” https://github.com/paddlepaddle/paddle , accessed: 2017-01-23
2017
Later among the works it cites.
“Amazon dsstne github project,” https://github.com/amzn/amazon-dsstne , accessed: 2017-01-23
2017
Later among the works it cites.
Y. You, A. Buluc, and J. Demmel, “Scaling Deep Learning on GPU and Knights Landing clusters,” ArXiv e-prints , Aug. 2017
2017
Later among the works it cites.
X. Pan, J. Chen, R. Monga, S. Bengio, and R. Józefowicz, “Revisiting distributed synchronous SGD,” CoRR , vol. abs/1702.05800, 2017. [Online]. Available: http://arxiv.org/abs/1702.05800
Original
2017
Later among the works it cites.
A. Ichinose, A. Takefusa, H. Nakada, and M. Oguchi, “Pipeline-based processing of the deep learning framework caffe,” in Proceedings of the 11th International Conference on Ubiquitous Information Management and Communication , ser. IMCOM ’17. New York, NY, USA: ACM, 2017, pp. 97:1–97:8. [Online]. Available: http://doi.acm.org/10.1145/3022227.3022323
2017
Later among the works it cites.
Y. You, Z. Zhang, C. Hsieh, J. Demmel, and K. Keutzer, “Imagenet training in minutes,” CoRR, abs/1709.05011 , 2017
Original
2017
Later among the works it cites.
Y. You, I. Gitman, and B. Ginsburg, “Scaling sgd batch size to 32k for imagenet training,” arXiv preprint arXiv:1708.03888 , 2017
Original
2017
Later among the works it cites.
T. Akiba, S. Suzuki, and K. Fukuda, “Extremely large minibatch sgd: Training resnet-50 on imagenet in 15 minutes,” arXiv preprint arXiv:1711.04325 , 2017
Original
2017
Later among the works it cites.
P. Goyal, P. Dollár, R. Girshick, P. Noordhuis, L. Wesolowski, A. Kyrola, A. Tulloch, Y. Jia, and K. He, “Accurate, large minibatch sgd: Training imagenet in 1 hour,” arXiv preprint arXiv:1706.02677 , 2017
Original
2017
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…