Efficient Algorithms for Device Placement of DNN Graph Operators

By Jakub Tarnawski, Amar Phanishayee, Nikhil R. Devanur, Divya Mahajan, Fanny Nina Paravecino. 2020

81 citations recorded by the source corpus.

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.

Subfields: Computer Vision and Pattern Recognition, Electrical and Electronic Engineering, Efficiency & Compression

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Electrical and Electronic Engineering

In Efficiency & Compression

Citations in the corpus

GSPMD: General and Scalable Parallelization for ML Computation Graphs (2021, methodology): “Pipelining algorithms [13, 15, 22, 24, 36] focus on one type of parallelism, while GSPMD can be used either to express similar ideas with the help of vectorization (Section 3.”
PanGu-α: Large-scale Autoregressive Pretrained Chinese Language Models with Auto-parallel Computation (2021, methodology): “The second regime is pipeline model parallelism [24, 25, 26, 27, 28], which partitions the total layers to stages, and then places stages to different devices, as shown in Figure 4(c).”
Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LM (2021, background): “[41] all auto-partition model training graphs over multiple devices with the help of cost models.”
Software-hardware co-design for fast and scalable training of deep learning recommendation models (2021, methodology): “Building on this direction of auto-parallelization, these recent papers [39, 60] use optimal synthesis and reinforcement learning to find optimized device placement to further improve parallelism without the need for manual intervention.”
High-performance, Distributed Training of Large-scale Deep Learning Recommendation Models (2021, methodology): “Building on this direction of auto-parallelization, these recent papers [36, 54] use optimal synthesis and reinforcement learning to find optimized device placement to further improve parallelization without the need for manual intervention.”