# Accelerate Model Parallel Training by Using Efficient Graph Traversal Order in Device Placement

arXiv: https://arxiv.org/abs/2201.09676 · HTML: https://mlsanity.com/paper/2201.09676/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 37 references that are in the map.
- First posted on arXiv 21 Jan 2022.

## Builds on (most cited first, 18 of 18)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism](https://mlsanity.com/paper/1909.08053/) (2019)
- [Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation](https://mlsanity.com/paper/1609.08144/) (2016)
- [Efficient Neural Architecture Search via Parameter Sharing](https://mlsanity.com/paper/1802.03268/) (2018)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [Do Transformers Really Perform Bad for Graph Representation?](https://mlsanity.com/paper/2106.05234/) (2021)
- [Measuring the Effects of Data Parallelism on Neural Network Training](https://mlsanity.com/paper/1811.03600/) (2018)
- [Deep learning in remote sensing: a review](https://mlsanity.com/paper/1710.03959/) (2017)
- [Device Placement Optimization with Reinforcement Learning](https://mlsanity.com/paper/1706.04972/) (2017)
- [Placeto: Learning Generalizable Device Placement Algorithms for Distributed Machine Learning](https://mlsanity.com/paper/1906.08879/) (2019)
- [Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs](https://mlsanity.com/paper/1905.02494/) (2019)
- [GDP: Generalized Device Placement for Dataflow Graphs](https://mlsanity.com/paper/1910.01578/) (2019)
- [The TensorFlow Partitioning and Scheduling Problem: It's the Critical Path!](https://mlsanity.com/paper/1711.01912/) (2017)

## Abstract (arXiv)

Modern neural networks require long training to reach decent performance on massive datasets. One common approach to speed up training is model parallelization, where large neural networks are split across multiple devices. However, different device placements of the same neural network lead to different training times. Most of the existing device placement solutions treat the problem as sequential decision-making by traversing neural network graphs and assigning their neurons to different devices. This work studies the impact of graph traversal order on device placement. In particular, we empirically study how different graph traversal order leads to different device placement, which in turn affects the training execution time. Our experiment results show that the best graph traversal order depends on the type of neural networks and their computation graphs features. In this work, we also provide recommendations on choosing graph traversal order in device placement for various neural network families to improve the training time in model parallelization.