Elamur Research⌕
☰
home / papers / 2018 / Beyond Data and Model Parallelism for Deep Neural Networks

Beyond Data and Model Parallelism for Deep Neural Networks

Paper · 2018 · Zhihao Jia, Matei Zaharia and Alex Aiken

Summary

Training large DNNs is now routinely spread across many GPUs, yet mainstream frameworks mostly rely on plain data parallelism or model parallelism. Both waste performance. Replicating every layer is costly for parameter-heavy layers, and assigning whole operations to separate devices rules out splitting work inside an operation. The authors define a broader space of strategies, SOAP, in which each operation can be divided along the Sample, Operation, Attribute and Parameter dimensions; earlier approaches become special cases of it. Their system, FlexFlow, explores this space with an MCMC-based randomized search. Rather than running each candidate on hardware, it scores candidates with an execution simulator. The simulator profiles each operator type once per input size and updates earlier simulations incrementally instead of starting over. The authors tested FlexFlow on six real DNNs (image classification, text classification, language modeling and NMT) on two GPU clusters. It raised training throughput by up to 3.8× over existing methods, with search time counted, and it scaled better. The work matters because it turns parallelization from manual expert tuning into a cheap, automatic optimization that adapts to the hardware.

Key points

  • Baselines beaten:
    • Data parallelism, model parallelism and expert-designed strategies: throughput up to 3.3× higher and communication up to 5× lower.
    • Expert-designed strategies alone ("one weird trick" style): up to 2.3× faster.
    • OptCNN: 1.2–1.6× faster.
    • REINFORCE: 3.4–3.8× faster on REINFORCE's own hardware setup.
  • Search cost: REINFORCE needed 12–27 hours on 160 nodes with 4 GPUs each. FlexFlow found better strategies in 14–40 seconds using a single node for simulation.
  • Simulator accuracy:
    • Simulated and real execution times differed by under 30% in all measured runs.
    • The simulator kept the real ranking of strategies.
    • Delta simulation ran 2.2–6.9× faster than full simulation, and the gap grew with more devices.
  • Search quality:
    • On LeNet and a reduced RNNLM, each with about 10^11 strategies on 4 devices, FlexFlow found the global optimum. Exhaustive verification of this took 0.8 and 18 hours.
    • For all six DNNs on 2, 4 and 8 devices, the returned strategies were locally optimal.
  • Case studies:
    • For Inception-v3 on 4 P100 GPUs, the best strategy cut parameter synchronization by 75% and iteration time by 12% compared with data parallelism.
    • For NMT, FlexFlow placed embedding layers on few GPUs and split the softmax layer by channel.

Interesting ideas

  • I1. Cheap simulator as a search oracle. Profile each distinct operator once per input shape, then predict whole configurations from those measurements. This works because models reuse few operator types and their runtimes barely depend on the data. The same trick could speed up tuning of batch sizes, sharding or pipeline layouts for NLP training jobs.
  • I2. Judge a proxy by ranking, not absolute error. The simulator can be up to 30% off and still be useful, because the search only needs it to order strategies correctly. This is a sensible way to validate any surrogate model used to steer optimization.
  • I3. Incremental (delta) re-evaluation. When a search moves to a neighbouring candidate, update only the affected parts of the previous evaluation. Any local-search or MCMC loop over large configuration spaces could gain from this.
  • I4. A unified space that contains known methods. Framing all strategies as combinations of a few dimensions makes existing methods special cases, so the search can never do worse than them in principle. This design pattern is useful whenever several hand-crafted heuristics compete.
  • I5. Check the search against ground truth on small instances. The authors exhaustively solved small problems to compare with the global optimum and enumerated neighbours to confirm local optimality. Both checks transfer to evaluating any heuristic optimizer.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksComputer Vision and Pattern Recognition · 3,486 worksInformation Systems · 1,730 worksHardware and Architecture · 167 works

Cite

Cite as Zhihao Jia, Matei Zaharia and Alex Aiken. 2018. Beyond Data and Model Parallelism for Deep Neural Networks. SysML 2019.

The paper itself, not this page. BibTeX from the library's record of the work. arXiv 1807.05358

@inproceedings{jia2018beyond,
  title = {{Beyond Data and Model Parallelism for Deep Neural Networks}},
  author = {Zhihao Jia, Matei Zaharia and Alex Aiken},
  booktitle = {SysML 2019},
  year = {2018},
  eprint = {1807.05358},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1807.05358}
}

References

43 references, 16 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Movie review data. cs.cornell.edu/people/pabo/ movie-review-data/, 2005. find
  2. A New Lightweight, Modular, and Scalable Deep Learning Framework. https://caffe2.ai, 2016. ↗
  3. Conference on machine translation. http://www.statmt.org/wmt16, 2016. ↗
  4. Dense Linear Algebra on GPUs. https://developer.nvidia.com/cublas, 2016. Benchmarks. https: ↗
  5. TensorFlow //www.tensorflow.org/performance/benchmarks, 2017. find
  6. Tensors and Dynamic neural networks in Python with strong GPU acceleration. https://pytorch.org, 2017. ↗
  7. M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, M. Kudlur, J. Levenberg, R. Monga, S. Moore, D. G. Murray, B. Steiner, P. Tucker, V. Vasudevan, P. Warden, M. Wicke, Y. Yu, and X. Zheng. Tensorflow: A system for large-scale machine learning. In Pr…
  8. D. Amodei, S. Ananthanarayanan, R. Anubhai, J. Bai, E. Battenberg, C. Case, J. Casper, B. Catanzaro, Q. Cheng, G. Chen, J. Chen, J. Chen, Z. Chen, M. Chrzanowski, A. Coates, G. Diamos, K. Ding, N. Du, E. Elsen, J. Engel, W. Fang, L. Fan, C. Fougner, L. Gao, C. Gong, A. Hannun, T. Han, L. V. Johannes… — Deep Speech 2: End-to-End Speech Recognition in English and Mandarin
  9. D. Bahdanau, K. Cho, and Y. Bengio. Neural machine translation by jointly learning to align and translate. CoRR, abs/1409.0473, 2014.
  10. M. Bauer, S. Treichler, E. Slaughter, and A. Aiken. Legion: Expressing locality and independence with logical regions. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, 2012. find
  11. C. Chelba, T. Mikolov, M. Schuster, Q. Ge, T. Brants, and P. Koehn. One billion word benchmark for measuring progress in statistical language modeling. CoRR, abs/1312.3005, 2013.
  12. T. Chen, M. Li, Y. Li, M. Lin, N. Wang, M. Wang, T. Xiao, B. Xu, C. Zhang, and Z. Zhang. MXNet: A flexible and efficient machine learning library for heterogeneous distributed systems. CoRR, abs/1512.01274, 2015.
  13. S. Chetlur, C. Woolley, P. Vandermersch, J. Cohen, J. Tran, B. Catanzaro, and E. Shelhamer. cudnn: Efficient primitives for deep learning. CoRR, abs/1410.0759, 2014.
  14. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009. find
  15. 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 NIPS, 2012. find
  16. J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A large-scale hierarchical image database. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR, 2009. find
  17. W. R. Gilks, S. Richardson, and D. Spiegelhalter. Markov chain Monte Carlo in practice. CRC press, 1995. find
  18. I. Gog, M. Schwarzkopf, A. Gleave, R. N. M. Watson, and S. Hand. Firmament: Fast, centralized cluster scheduling at scale. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16), pages 99–115, Savannah, GA, 2016. USENIX Association. find
  19. P. Goyal, P. Dollár, R. B. Girshick, P. Noordhuis, L. Wesolowski, A. Kyrola, A. Tulloch, Y. Jia, and K. He. Accurate, large minibatch SGD: training imagenet in 1 hour. CoRR, abs/1706.02677, 2017. find
  20. A. Graves and N. Jaitly. Towards end-to-end speech recognition with recurrent neural networks. In Proceedings of the 31st International Conference on International Conference on Machine Learning, ICML’14, 2014. find
  21. W. K. Hastings. Monte carlo sampling methods using markov chains and their applications. Biometrika, 57(1):97–109, 1970. find
  22. 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, CVPR, 2016.
  23. G. Huang, Z. Liu, and K. Q. Weinberger. Densely connected convolutional networks. CoRR, abs/1608.06993, 2016. find
  24. M. Isard, V. Prabhakaran, J. Currey, U. Wieder, K. Talwar, and A. Goldberg. Quincy: Fair scheduling for distributed computing clusters. In Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles, SOSP ’09, pages 261–276. ACM, 2009. find
  25. Z. Jia, S. Lin, C. R. Qi, and A. Aiken. Exploring hidden dimensions in parallelizing convolutional neural networks. CoRR, abs/1802.04924, 2018. find
  26. Y. Kim. Convolutional neural networks for sentence classification. CoRR, abs/1408.5882, 2014.
  27. A. Krizhevsky. One weird trick for parallelizing convolutional neural networks. CoRR, abs/1404.5997, 2014.
  28. A. Krizhevsky, I. Sutskever, and G. E. Hinton. ImageNet classification with deep convolutional neural networks. In Proceedings of the 25th International Conference on Neural Information Processing Systems, NIPS, 2012.
  29. S. Lam and R. Sethi. Worst case analysis of two scheduling algorithms. SIAM Journal on Computing, 6, 1977. find
  30. Y. LeCun. LeNet-5, convolutional neural networks. URL: http://yann.lecun. com/exdb/lenet, 2015. ↗
  31. M. P. Marcus, M. A. Marcinkiewicz, and B. Santorini. Building a large annotated corpus of english: The penn treebank. Comput. Linguist., 19.
  32. A. Mirhoseini, A. Goldie, H. Pham, B. Steiner, Q. V. Le, and J. Dean. A hierarchical model for device placement. In International Conference on Learning Representations, 2018. find
  33. A. Mirhoseini, H. Pham, Q. V. Le, B. Steiner, R. Larsen, Y. Zhou, N. Kumar, M. Norouzi, S. Bengio, and J. Dean. Device placement optimization with reinforcement learning. 2017. find
  34. K. Papineni, S. Roukos, T. Ward, and W.-J. Zhu. Bleu: A method for automatic evaluation of machine translation. In Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, ACL ’02, 2002.
  35. O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, A. C. Berg, and L. Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115(3):211–252, 2015.
  36. O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, et al. Imagenet large scale visual recognition challenge. International Journal of Computer Vision, 2015.
  37. D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529:484–489, 2016. find
  38. K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. CoRR, abs/1409.1556, 2014.
  39. C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. E. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich. Going deeper with convolutions. CoRR, abs/1409.4842, 2014. find
  40. C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016. find
  41. S. Treichler, M. Bauer, R. Sharma, E. Slaughter, and A. Aiken. Dependent partitioning. In Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA’ 16. ACM, 2016. find
  42. Y. Wu, M. Schuster, Z. Chen, Q. V. Le, M. Norouzi, W. Macherey, M. Krikun, Y. Cao, Q. Gao, K. Macherey, J. Klingner, A. Shah, M. Johnson, X. Liu, L. Kaiser, S. Gouws, Y. Kato, T. Kudo, H. Kazawa, K. Stevens, G. Kurian, N. Patil, W. Wang, C. Young, J. Smith, J. Riesa, A. Rudnick, O. Vinyals, G. Corra… find
  43. W. Zaremba, I. Sutskever, and O. Vinyals. Recurrent neural network regularization. CoRR, abs/1409.2329, 2014.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/jia-2018-beyond-data-model-parallelism-deep/