IP Library › Granted Patent US 12,293,298
Granted Patent B2
US 12,293,298 · App. 16/985,121 · Granted May 6, 2025

Reducing training times of deep neural networks through efficient hybrid parallelism

Inventor: Venmugil Elango (Redmond, WA)
Assignee: Baidu USA LLC
G06N3/10G06F9/3885G06N3/04
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,293,298
App. No.
16/985,121
Granted
May 6, 2025
Kind
B2
Abstract

Presented are systems and methods to automatically find efficient parallelization strategies for deep neural networks (DNNs). A computation graph comprising an efficiently ordered sequence of vertices aids in computing the best parallelizing strategy in a relatively short time. Effectiveness of the parallelization strategies is evaluated on various DNNs, and the performance of the strategies proposed by various embodiments is compared against data parallelism, expert-designed strategies, and other state-of-the-art approaches. Experimental results demonstrate that the proposed strategies outperform a baseline data parallelism strategy and achieve better performance than expert-designed strategies and state-of-the-art approaches.

Claims (35)

1. A non-transitory computer-readable medium or media comprising one or more sequences of instructions which, when executed by at least one processor, causes steps to be performed comprising:

representing a deep neural network (DNN) as a computation graph, in which a vertex of the computation graph represents a layer of the DNN;

for one or more vertices in a set of vertices, initializing a right-dependent set of vertices, a terminal set of vertices, and a set of unsequenced vertices;

for each vertex, performing steps comprising:

iteratively selecting from the set of unsequenced vertices a vertex having a least right- dependent set cardinality, and assigning the selected vertex to a sequence of vertices; and

updating the terminal set of vertices and the right-dependent set of vertices such that sizes of the right-dependent set of vertices in a computation graph are correctly maintained;

outputting the sequence of vertices as an ordered sequence of vertices; and

training the DNN, in which the layers of the DNN are ordered for training using the ordered sequence of vertices.

2. The non-transitory computer-readable medium or media of claim 1 wherein an edge of the computation graph represents data flow between vertices that are connected by the edge.

3. The non-transitory computer-readable medium or media of claim 1 wherein the computation graph comprises a left-reachable set of vertices defined as being reachable from a vertex through an undirected path.

4. The non-transitory computer-readable medium or media of claim 3 wherein the vertex is associated with one or more valid configurations.

5. A computer-implemented method comprising:

representing a deep neural network (DNN) as a computation graph, in which a vertex of the computation graph represents a layer of the DNN;

for one or more vertices in a set of vertices, initializing a right-dependent set of vertices, a terminal set of vertices, and a set of unsequenced vertices;

for each vertex, performing steps comprising:

iteratively selecting from the set of unsequenced vertices a vertex having a least right-dependent set cardinality, and assigning the selected vertex to a sequence of vertices; and

updating the terminal set of vertices and the right-dependent set of vertices such that sizes of the right-dependent set of vertices in a computation graph are correctly maintained;

outputting the sequence of vertices as an ordered sequence of vertices; and

training the DNN, in which the layers of the DNN are ordered for training using the ordered sequence of vertices.

6. The computer-implemented method of claim 5 wherein an edge of the computation graph represents data flow between vertices that are connected by the edge.

7. The computer-implemented method of claim 5 wherein the computation graph comprises a left-reachable set of vertices defined as being reachable from a vertex through an undirected path.

8. The computer-implemented method of claim 7 wherein the vertex is associated with one or more valid configurations.

9. A system comprising:

one or more processors; and

a non-transitory computer-readable medium or media comprising one or more sets of instructions which, when executed by at least one of the one or more processors, causes steps to be performed comprising:

representing a deep neural network (DNN) as a computation graph, in which a vertex of the computation graph represents a layer of the DNN;

for one or more vertices in a set of vertices, initializing a right-dependent set of vertices, a terminal set of vertices, and a set of unsequenced vertices;

for each vertex, performing steps comprising:

iteratively selecting from the set of unsequenced vertices a vertex having a least right-dependent set cardinality, and assigning the selected vertex to a sequence of vertices; and

updating the terminal set of vertices and the right-dependent set of vertices such that sizes of the right-dependent set of vertices in a computation graph are correctly maintained;

outputting the sequence of vertices as an ordered sequence of vertices; and

training the DNN, in which the layers of the DNN are ordered for training using the ordered sequence of vertices.

10. The system of claim 9 wherein an edge of the computation graph represents data flow between vertices that are connected by the edge.

11. The system of claim 9 wherein the computation graph comprises a left-reachable set of vertices defined as being reachable from a vertex through an undirected path.

12. The system of claim 11 wherein the vertex is associated with one or more valid configurations.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Aug 17, 2020
From: ELANGO, VENMUGIL
To: BAIDU USA LLC
Reel/Frame 053507/0184 →
Continuity (2)
Provisional Application 62930518 · Nov 4, 2019
Related Publication 20210133591A1 · May 6, 2021
References Cited (29)
CN 107688493A · 2018 [cited by applicant]
CN 108090565A · 2018 [cited by applicant]
CN 108292374A · 2018 [cited by applicant]
WO 2017083399A2 · 2017 [cited by applicant]
WO 2018125429A1 · 2018 [cited by applicant]
Ma et al. , “NeuGraph: Parallel Deep Neural Network Computation on Large Graphs” (Jul. 2019) (Year: 2019). [cited by examiner]
Jia et al., “Exploring Hidden Dimensions in Parallelizing Convolutional Neural Networks”, (2018) (Year: 2018). [cited by examiner]
Wu et al.,“Google's Neural Machine Translation System: Bridging the Gapbetween Human and Machine Translation,” arXiv preprint arXiv:1609.08144, 2016. (23pgs). [cited by applicant]
Keskar et al., “On large-batch training for deep learning: Generalization gap and sharp minima,” arXiv preprint arXiv:1609.04836, 2017. (16 pgs). [cited by applicant]
Dean et al.,“Large scale distributed deep networks,” in Advances in Neural Information Processing Systems 25 (NIPS), 2012. (9pgs). [cited by applicant]
A. Krizhevsky, “One weird trick for parallelizing convolutional neural networks,” arXiv preprint arXiv:1404.5997, 2014. (7pgs). [cited by applicant]
Jia et al.,“Beyond Data and Model Parallelism for Deep Neural Networks,” arXiv preprint arXiv:1807.05358, 2018. (15pgs). [cited by applicant]
Mirhoseini et al.,“Device Placement Optimization with Reinforcement Learning,” arXiv preprint arXiv:1706.04972, 2017. (11pgs). [cited by applicant]
Jia et al.,“Exploring Hidden Dimensions in Parallelizing Convolutional Neural Networks,” arXiv preprint arXiv:1802.04924, 2018. (11pgs). [cited by applicant]
M. Wolfe, “More iteration space tiling,” [online], [Retrieved Mar. 25, 2021]. Retrieved from Internet <URL:http://doi.acm.org/10.1145/76263.76337> in Proceedings of the 1989 ACM/IEEE Conference on Supercomputing. [Abstr… [cited by applicant]
Huang et al.,“GPipe: Efficient Training of Giant Neural Networks using Pipeline Parallelism,” arXiv preprint arXiv:1811.06965, 2018. (11pgs). [cited by applicant]
Elango et al.,“Diesel: DSL for Linear Algebra and Neural Net Computations on GPUs,” in Proceedings of the 2nd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages, ser. MAPL 2018. (11pgs). [cited by applicant]
Vasilache et al.,“Tensor Comprehensions: Framework-AgnosticHigh-Performance Machine Learning Abstractions,” arXiv preprint arXiv:1802.04730, 2018. (37pgs). [cited by applicant]
Narayanan et al.,“PipeDream: Generalized Pipeline Parallelism for DNN Training,” in Proceedings of the 27th ACM Symposium on Operating Systems Principles (SOSP), 2019. (15pgs). [cited by applicant]
Krizhevsky et al.,“ImageNet Classification with Deep Convolutional Neural Networks,” in Advances in Neural Information Processing Systems 25, 2012. (9pgs). [cited by applicant]
Szegedy et al.,“Going deeper with convolutions,” arXiv preprint arXiv:1409.4842, 2014. (12pgs). [cited by applicant]
Mikolov et al.,“Recurrent neural network based language model,” in Eleventh annual conference of the international speech communication association, 2010. (4pgs). [cited by applicant]
Vaswani et al.,“Attention Is All You Need,” arXiv preprint arXiv:1706.03762, 2017. (15pgs). [cited by applicant]
Deng et al.,“Imagenet:A large-scale hierarchical image database,” in 2009 IEEE Conference on Computer Vision and Pattern Recognition [Abstract], 2009. (3pgs). [cited by applicant]
Chelba et al.,“One Billion Word Benchmark for Measuring Progress inStatistical Language Modeling,” arXiv preprint arXiv:1312.3005, 2014. (6pgs). [cited by applicant]
“Workshop on statistical machine translation,” [online], [Retrieved Mar. 25, 2021]. Retrieved from Internet <URL:http://www.statmt.org/wmt14/> (6pgs). [cited by applicant]
Shazeer et al., “Mesh-TensorFlow:Deep Learning for Supercomputers,” arXiv preprint arXiv:1811.02084, 2018. (16pgs). [cited by applicant]
Mirhoseini et al., “A hierarchical model for device placement,” in 6th International Conference on Learning Representations (ICLR), 2018. (11pgs). [cited by applicant]
Chinese Office Action dated Dec. 25, 2023, in Chinese Application No. 202011209924.4 (17pgs). [cited by applicant]
Cited By (1)
US 12,724,593