# Efficient Algorithms for Device Placement of DNN Graph Operators

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jun 2020.

## Built on by (most cited first, 24 of 24)

- [Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LM](https://mlsanity.com/paper/2104.04473/) (2021)
- [PanGu-α: Large-scale Autoregressive Pretrained Chinese Language Models with Auto-parallel Computation](https://mlsanity.com/paper/2104.12369/) (2021)
- [GSPMD: General and Scalable Parallelization for ML Computation Graphs](https://mlsanity.com/paper/2105.04663/) (2021)
- [Decentralized Training of Foundation Models in Heterogeneous Environments](https://mlsanity.com/paper/2206.01288/) (2022)
- [Software-Hardware Co-design for Fast and Scalable Training of Deep Learning Recommendation Models](https://mlsanity.com/paper/2104.05158/) (2021)
- [DFX: A Low-latency Multi-FPGA Appliance for Accelerating Transformer-based Text Generation](https://mlsanity.com/paper/2209.10797/) (2022)
- [Towards Efficient Post-training Quantization of Pre-trained Language Models](https://mlsanity.com/paper/2109.15082/) (2021)
- [Accelerating Recommendation System Training by Leveraging Popular Choices](https://mlsanity.com/paper/2103.00686/) (2021)
- [Persia: An Open, Hybrid System Scaling Deep Learning-based Recommenders up to 100 Trillion Parameters](https://mlsanity.com/paper/2111.05897/) (2021)
- [DreamShard: Generalizable Embedding Table Placement for Recommender Systems](https://mlsanity.com/paper/2210.02023/) (2022)
- [Benchmarking Ultra-Low-Power μNPUs](https://mlsanity.com/paper/2503.22567/) (2025)
- [Pre-train and Search: Efficient Embedding Table Sharding with Pre-trained Neural Cost Models](https://mlsanity.com/paper/2305.01868/) (2023)
- [Characterizing the Efficiency of Distributed Training: A Power, Performance, and Thermal Perspective](https://mlsanity.com/paper/2509.10371/) (2025)
- [Tango: rethinking quantization for graph neural network training on GPUs](https://mlsanity.com/paper/2308.00890/) (2023)
- [Integrated Hardware Architecture and Device Placement Search](https://mlsanity.com/paper/2407.13143/) (2024)
- [Collage: Seamless Integration of Deep Learning Backends with Automatic Placement](https://mlsanity.com/paper/2111.00655/) (2021)
- [DistIR: An Intermediate Representation and Simulator for Efficient Neural Network Distribution](https://mlsanity.com/paper/2111.05426/) (2021)
- [Baechi: Fast Device Placement of Machine Learning Graphs](https://mlsanity.com/paper/2301.08695/) (2023)
- [UniAP: Unifying Inter- and Intra-Layer Automatic Parallelism by Mixed Integer Quadratic Programming](https://mlsanity.com/paper/2307.16375/) (2023)
- [Optimizing Large Model Training through Overlapped Activation Recomputation](https://mlsanity.com/paper/2406.08756/) (2024)
- [Moirai: Towards Optimal Placement for Distributed Inference on Heterogeneous Devices](https://mlsanity.com/paper/2312.04025/) (2023)
- [CollaPipe: Adaptive Segment-Optimized Pipeline Parallelism for Collaborative LLM Training in Heterogeneous Edge Networks](https://mlsanity.com/paper/2509.19855/) (2025)
- [Routing for Large ML Models](https://mlsanity.com/paper/2503.05324/) (2025)
- [NEST: Network- and Memory-Aware Device Placement For Distributed Deep Learning](https://mlsanity.com/paper/2603.06798/) (2026)

## Abstract (arXiv)

Modern machine learning workloads use large models, with complex structures, that are very expensive to execute. The devices that execute complex models are becoming increasingly heterogeneous as we see a flourishing of domain-specific accelerators being offered as hardware accelerators in addition to CPUs. These trends necessitate distributing the workload across multiple devices. Recent work has shown that significant gains can be obtained with model parallelism, i.e, partitioning a neural network's computational graph onto multiple devices. In particular, this form of parallelism assumes a pipeline of devices, which is fed a stream of samples and yields high throughput for training and inference of DNNs. However, for such settings (large models and multiple heterogeneous devices), we require automated algorithms and toolchains that can partition the ML workload across devices. In this paper, we identify and isolate the structured optimization problem at the core of device placement of DNN operators, for both inference and training, especially in modern pipelined settings. We then provide algorithms that solve this problem to optimality. We demonstrate the applicability and efficiency of our approaches using several contemporary DNN computation graphs.