1 of 33

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

Sabuj Laskar, Pranati Majhi, Sungkeun Kim,

Farabi Mahmud, Abdullah Muzahid, Eun Jung Kim

​

Texas A&M University

2 of 33

Importance of Distributed Deep Neural Network (DNN) Training

  • Exploding dataset and model size

​

​

  • Language Models
    • FLAN (More than 1 Trillion words)
  • Vision
    • JFT-3B (3 Billion images)

​

Source: Trends in Training Dataset Sizes (https://epochai.org/blog/trends-in-training-dataset-sizes)

2/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

3 of 33

Data-Parallel Distributed DNN Training

Forward

Back-Propagation

AllReduce

(reduce-scatter and all-gather)

Input Dataset

xPU

xPU

xPU

xPU

DNN Model

Weight Update

3/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

4 of 33

AllReduce for Mesh

Mesh topology widespread usage

  • Chip Multi-Processors (CMP)
  • Multi-Chip-Modules (MCMs), etc.

​

​

Chiplet count ( ) Communication ( )

Efficient AllReduce for mesh is important

Source: Zimmer+JSSC’2020

4/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

5 of 33

Types of AllReduce Algorithms

  • Ring-based Algorithms
  • Tree-based Algorithms

5/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

6 of 33

Ring AllReduce [Patarasuk and Yuan+JPDC’09]

0

1

3

2

Step 1

Step 3

Step 2

Local gradients

Partition to 4 chunks in a 4-node system

0

1

3

2

Step 1

Step 2

Step 3

Reduce-Scatter

(compute local gradients reduction)

All-Gather

(broadcast the reduced gradients)

Reduce

Reduce

Reduce

Reduce

Reduce

Reduce

Reduce

Reduce

Reduce

Reduce

Reduce

Reduce

6/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

7 of 33

Ring AllReduce in Mesh

1

2

5

6

3

7

4

8

9

10

11

12

13

14

15

16

1

2

4

5

3

6

7

8

9

Ring 1

Ring 2

4x4 Mesh

Even-sized

Mesh

3x3 Mesh

Unidirectional Ring

Unidirectional Ring

Bidirectional Ring

Bidirectional Ring

No Hamiltonian Cycle

Odd-sized

Mesh

1

2

5

6

3

7

4

8

9

10

11

12

13

14

15

16

1

2

5

6

3

7

4

8

9

10

11

12

13

14

15

16

1

2

4

5

3

6

7

8

9

7/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

8 of 33

MultiTree: A Tree-based AllReduce [Huang+ISCA’21]

2

1

3

4

Tree 2

3

2

4

1

Tree 3

1

2

4

3

1

2

4

3

Tree 1

4

1

3

2

Tree 4

1

2

4

3

Step 1

Step 2

Tree

Formation

2

1

3

4

Tree 2

3

2

4

1

Tree 3

1

2

Tree 1

4

1

3

2

Tree 4

3

4

2

1

Tree 1

4

3

1

2

Tree 2

1

4

2

3

Tree 3

2

3

1

4

Tree 4

Data

Reduce-Scatter

All-Gather

Unutilized

​

​

Reduce

Reduce

4

3

8/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

9 of 33

Limitations of Existing AllReduce Algorithms in Mesh

Algorithms

Even-sized Mesh

Odd-Sized Mesh

Applicability

Used Link Percentage

Applicability

Used Link Percentage

Unidirectional Ring

[Patarasuk and Yuan+JPDC’09]

Easy

29%

Easy

28%

Bidirectional Ring

[NCCL 2.0]

Easy

57%

Inapplicable

-

Ring-2D

[Ying+NIPS’18]

Hard

55%

Hard

53%

DBTree

[Sanders+JPC’09]

Hard

-

Hard

-

HDRM

[Dong+HPCA’20]

Inapplicable

-

Inapplicable

-

MultiTree [Huang+ISCA’21]

Easy

53%

Easy

51%

Ring-basedοΏ½Algorithms

For Bigraph

Tree-basedοΏ½Algorithms

9/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

10 of 33

Our Proposed Algorithms

  • RingBiOdd: Bidirectional ring all-reduce for odd-sized Mesh
    • To ensure bidirectional ring can be used for any Mesh
  • Three Tree AllReduce (TTO): Tree-based all-reduce with significantly higher link utilization
    • Sacrifice small computation to speed up communication significantly

10/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

11 of 33

Algorithm 1: RingBiOdd

1

2

4

5

3

6

7

8

9

Bidirectional Ring AllReduce For Odd-sized Mesh

11/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

12 of 33

Forming Bidirectional Rings in Odd-Sized Mesh

Ring 1

Ring 2

Start Node

Excluded Node for Ring Formation

1

2

4

5

3

6

7

8

9

8

9

Excluded Node Connections

Unused Links

Form a Hamiltonian cycle with (N-1) nodes

12/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

13 of 33

Reduce-Scatter Schedule for RingBiOdd

1

2

4

5

3

6

7

8

9

1

step 1

1

2

4

5

3

6

7

8

9

2

step 2

2

1

8

7

6

5

3

4

1

2

4

5

3

6

7

8

9

1

step 1

1

2

4

5

3

6

7

8

9

2

step 2

1

3

2

4

5

6

7

8

1

2

4

5

3

6

7

8

9

3

step 3

2

4

3

5

6

7

8

1

1

2

4

5

3

6

7

8

9

4

step 4

3

5

4

6

7

8

1

2

1

2

4

5

3

6

7

8

9

5

step 5

4

6

5

7

8

1

2

3

1

2

4

5

3

6

7

8

9

7

step 7

6

8

7

1

2

3

4

5

1

2

4

5

3

6

7

8

9

6

step 6

5

7

6

8

1

2

3

4

1

2

4

5

3

6

7

8

9

8

step 8

7

1

8

2

3

4

5

6

Reduce

Reduce

1

2

3

4

5

6

7

8

Splits data into N-1 chunks instead of N

13/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

14 of 33

Reduce-Scatter Schedule for RingBiOdd

1

2

4

5

3

6

7

8

9

1

step 1

1

2

4

5

3

6

7

8

9

3

step 3

3

2

1

8

7

6

4

5

1

2

4

5

3

6

7

8

9

2

step 2

1

3

2

4

5

6

7

8

1

2

4

5

3

6

7

8

9

3

step 3

2

4

3

5

6

7

8

1

1

2

4

5

3

6

7

8

9

4

step 4

3

5

4

6

7

8

1

2

1

2

4

5

3

6

7

8

9

5

step 5

4

6

5

7

8

1

2

3

1

2

4

5

3

6

7

8

9

7

step 7

6

8

7

1

2

3

4

5

1

2

4

5

3

6

7

8

9

6

step 6

5

7

6

8

1

2

3

4

1

2

4

5

3

6

7

8

9

8

step 8

7

1

8

2

3

4

5

6

Reduce

Reduce

1

2

3

4

5

6

7

8

1

2

4

5

3

6

7

8

9

2

step 2

2

1

8

7

6

5

3

4

13/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

15 of 33

Reduce-Scatter Schedule for RingBiOdd

1

2

4

5

3

6

7

8

9

1

step 1

1

2

4

5

3

6

7

8

9

4

step 4

4

3

2

1

8

7

5

6

1

2

4

5

3

6

7

8

9

2

step 2

1

3

2

4

5

6

7

8

1

2

4

5

3

6

7

8

9

3

step 3

2

4

3

5

6

7

8

1

1

2

4

5

3

6

7

8

9

4

step 4

3

5

4

6

7

8

1

2

1

2

4

5

3

6

7

8

9

5

step 5

4

6

5

7

8

1

2

3

1

2

4

5

3

6

7

8

9

7

step 7

6

8

7

1

2

3

4

5

1

2

4

5

3

6

7

8

9

6

step 6

5

7

6

8

1

2

3

4

1

2

4

5

3

6

7

8

9

8

step 8

7

1

8

2

3

4

5

6

Reduce

Reduce

1

2

3

4

5

6

7

8

1

2

4

5

3

6

7

8

9

3

step 3

3

2

1

8

7

6

4

5

13/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

16 of 33

Reduce-Scatter Schedule for RingBiOdd

1

2

4

5

3

6

7

8

9

1

step 1

1

2

4

5

3

6

7

8

9

5

step 5

5

4

3

2

1

8

6

7

1

2

4

5

3

6

7

8

9

2

step 2

1

3

2

4

5

6

7

8

1

2

4

5

3

6

7

8

9

3

step 3

2

4

3

5

6

7

8

1

1

2

4

5

3

6

7

8

9

4

step 4

3

5

4

6

7

8

1

2

1

2

4

5

3

6

7

8

9

5

step 5

4

6

5

7

8

1

2

3

1

2

4

5

3

6

7

8

9

7

step 7

6

8

7

1

2

3

4

5

1

2

4

5

3

6

7

8

9

6

step 6

5

7

6

8

1

2

3

4

1

2

4

5

3

6

7

8

9

8

step 8

7

1

8

2

3

4

5

6

Reduce

Reduce

1

2

3

4

5

6

7

8

1

2

4

5

3

6

7

8

9

4

step 4

4

3

2

1

8

7

5

6

13/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

17 of 33

Reduce-Scatter Schedule for RingBiOdd

1

2

4

5

3

6

7

8

9

1

step 1

1

2

4

5

3

6

7

8

9

6

step 6

6

5

4

3

2

1

7

8

1

2

4

5

3

6

7

8

9

2

step 2

1

3

2

4

5

6

7

8

1

2

4

5

3

6

7

8

9

3

step 3

2

4

3

5

6

7

8

1

1

2

4

5

3

6

7

8

9

4

step 4

3

5

4

6

7

8

1

2

1

2

4

5

3

6

7

8

9

5

step 5

4

6

5

7

8

1

2

3

1

2

4

5

3

6

7

8

9

7

step 7

6

8

7

1

2

3

4

5

1

2

4

5

3

6

7

8

9

6

step 6

5

7

6

8

1

2

3

4

1

2

4

5

3

6

7

8

9

8

step 8

7

1

8

2

3

4

5

6

Reduce

Reduce

1

2

3

4

5

6

7

8

1

2

4

5

3

6

7

8

9

5

step 5

5

4

3

2

1

8

6

7

13/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

18 of 33

Reduce-Scatter Schedule for RingBiOdd

1

2

4

5

3

6

7

8

9

1

step 1

1

2

4

5

3

6

7

8

9

7

step 7

7

6

5

4

3

2

8

1

1

2

4

5

3

6

7

8

9

2

step 2

1

3

2

4

5

6

7

8

1

2

4

5

3

6

7

8

9

3

step 3

2

4

3

5

6

7

8

1

1

2

4

5

3

6

7

8

9

4

step 4

3

5

4

6

7

8

1

2

1

2

4

5

3

6

7

8

9

5

step 5

4

6

5

7

8

1

2

3

1

2

4

5

3

6

7

8

9

7

step 7

6

8

7

1

2

3

4

5

1

2

4

5

3

6

7

8

9

6

step 6

5

7

6

8

1

2

3

4

1

2

4

5

3

6

7

8

9

8

step 8

7

1

8

2

3

4

5

6

Reduce

Reduce

1

2

3

4

5

6

7

8

1

2

4

5

3

6

7

8

9

6

step 6

6

5

4

3

2

1

7

8

13/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

19 of 33

Reduce-Scatter Schedule for RingBiOdd

1

2

4

5

3

6

7

8

9

1

step 1

1

2

4

5

3

6

7

8

9

8

step 8

8

7

6

5

4

3

1

2

1

2

4

5

3

6

7

8

9

2

step 2

1

3

2

4

5

6

7

8

1

2

4

5

3

6

7

8

9

3

step 3

2

4

3

5

6

7

8

1

1

2

4

5

3

6

7

8

9

4

step 4

3

5

4

6

7

8

1

2

1

2

4

5

3

6

7

8

9

5

step 5

4

6

5

7

8

1

2

3

1

2

4

5

3

6

7

8

9

7

step 7

6

8

7

1

2

3

4

5

1

2

4

5

3

6

7

8

9

6

step 6

5

7

6

8

1

2

3

4

1

2

4

5

3

6

7

8

9

8

step 8

7

1

8

2

3

4

5

6

Reduce

Reduce

1

2

3

4

5

6

7

8

1

2

4

5

3

6

7

8

9

7

step 7

7

6

5

4

3

2

8

1

N-1 steps for

N-node Mesh

13/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

20 of 33

Algorithm 2: TTO (Three Tree AllReduce)

1

2

4

5

3

6

7

8

9

Chunk Pipelining to Improve Link Utilization

14/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

21 of 33

Chunk Pipelining in 1D Mesh

1

2

3

4

1

2

3

4

2

1

3

4

3

2

4

1

4

3

2

1

Tree 1

Tree 2

Tree 3

Tree 4

t=1

t=2

t=3

4

3

2

1

1

2

3

4

Tree 1

Tree 4

t=2

t=4

t=6

2->1

2->3

1->2

4->3

3->2

3->4

t=3

2->1

2->3

1->2

4->3

3->2

3->4

t=4

2->1

2->3

1->2

4->3

3->2

3->4

t=5

2->1

2->3

1->2

4->3

3->2

3->4

t=6

2->1

2->3

1->2

4->3

3->2

3->4

t=7

2->1

2->3

1->2

4->3

3->2

3->4

t=8

2->1

2->3

1->2

4->3

3->2

3->4

t=9

2->1

2->3

1->2

4->3

3->2

3->4

t=10

2->1

2->3

1->2

4->3

3->2

3->4

t=11

2->1

2->3

1->2

4->3

3->2

3->4

t=12

2->1

2->3

1->2

4->3

3->2

3->4

t=13

2->1

2->3

1->2

4->3

3->2

3->4

t=14

2->1

2->3

1->2

4->3

3->2

3->4

t=15

2->1

2->3

1->2

4->3

3->2

3->4

t=2

2->1

2->3

1->2

4->3

3->2

3->4

t=1

All Possible Links

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

t=3

2->1

2->3

1->2

4->3

3->2

3->4

t=4

2->1

2->3

1->2

4->3

3->2

3->4

t=5

2->1

2->3

1->2

4->3

3->2

3->4

t=6

2->1

2->3

1->2

4->3

3->2

3->4

t=7

2->1

2->3

1->2

4->3

3->2

3->4

t=8

2->1

2->3

1->2

4->3

3->2

3->4

t=9

2->1

2->3

1->2

4->3

3->2

3->4

t=10

2->1

2->3

1->2

4->3

3->2

3->4

t=11

2->1

2->3

1->2

4->3

3->2

3->4

t=12

2->1

2->3

1->2

4->3

3->2

3->4

t=13

2->1

2->3

1->2

4->3

3->2

3->4

t=14

2->1

2->3

1->2

4->3

3->2

3->4

t=15

2->1

2->3

1->2

4->3

3->2

3->4

t=2

2->1

2->3

1->2

4->3

3->2

3->4

t=1

All Possible Links

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

2->1

2->3

1->2

4->3

3->2

3->4

Chunk 1

Chunk 2

Chunk 3

Chunk 4

Chunk 5

15/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

22 of 33

Challenges in 2D Mesh

  • Insights
    • Trees should be disjoint
    • Maximize the number of trees
      • The maximum possible disjoint tree is 3

1

2

4

5

3

6

7

8

9

1

2

4

5

3

6

7

8

9

Root Node

Node 1, 3, 7 and 9 need 3 links

Still Node 7 needs 3 links

Using corner nodes as roots

Using nodes other than corner nodes as roots

Impossible to make 3 trees with all nodesοΏ½One corner node is the bottleneck

Exclude one corner node: Sacrifice computation to speed up communication

16/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

23 of 33

Forming Three Disjoint Trees

1

2

4

5

3

6

7

8

9

1

4

7

8

9

2

5

6

3

9

8

7

4

1

6

5

2

3

3

2

6

9

5

1

4

8

Tree 1

Tree 9

Tree 3

Excluded Node

Root Node

t=1

t=2

t=3

t=4

Vertical, then Horizontal

Horizontal, then Vertical

Apply BFS from 3

1

2

4

5

3

6

7

8

9

Unused links after

forming Tree 1

1

2

4

5

3

6

7

8

9

Unused links after

forming Tree 9

1

2

4

5

3

6

7

8

9

Unused links after

forming Tree 3

17/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

24 of 33

System Configuration and Evaluation

  • Modeling and Configuration
    • Scale-Sim: Forward + Backward Propagation
    • BookSim2: Interconnection network
    • Topologies: Mesh
  • Workloads
    • Synthetic messages with different sizes for network bandwidth and scalability
    • DNN models for training performance
      • AlexNet, AlphaGoZero, FasterRCNN, GoogLeNet, NCF, ResNet152, Transformer
  • Comparisons
    • Ring AllReduce: Unidirectional ring allreduce [Patarasuk and Yuan+JPDC’09]
    • Ring-2D: Hierarchical ring allreduce [Ying+NIPS’18]
    • Double Binary Tree(DTree): Topology-oblivious tree-based [Sanders+JPC’09]
    • MultiTree: Topology-aware tree-based [Huang+ISCA’21]
    • RingBiEven: Bidirectional ring allreduce [NCCL 2.0]

18/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

25 of 33

Bandwidth Utilization

  • Dtree, Ring, and Ring-2D are unfriendly to Mesh

19/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

26 of 33

Bandwidth Utilization

RingBiOdd Speedup

1.9x over Ring

1.1x over Multitree

  • Dtree, Ring, and Ring-2D are unfriendly to Mesh
  • MultiTree, Bidirectional Rings have higher bandwidth utilization compared to baselines

19/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

27 of 33

Bandwidth Utilization

TTO Speedup

1.4x over Bidirectional Ring

1.6x over Multitree

  • Dtree, Ring, and Ring-2D are unfriendly to Mesh
  • MultiTree, RingBiOdd, and RingBiEven are bandwidth sub-optimal
  • TTO is the most bandwidth-optimal

19/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

28 of 33

DNNs Training Time on 8x8 Mesh

20/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

29 of 33

DNNs Training Time on 8x8 Mesh

DTree performs worse compared to others

20/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

30 of 33

DNNs Training Time on 8x8 Mesh

Bidirectional Ring

Speedup Over:

Ring: 1.29-1.97x

Multitree: 0.88-1.09x

20/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

31 of 33

DNNs Training Time on 8x8 Mesh

TTO Speedup Over:

Bidirectional Ring: 0.99-1.6x

Multitree: 0.98-1.54x

Speedup of AllReduce

Outweighs

Computation Overhead

20/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

32 of 33

Link Utilization Percentage

Link utilization percentage of

  • Unidirectional ring: average ~27%
  • Ring-2D and Bidirectional Rings: average ~50%
  • MultiTree: max ~95%, average ~50%
  • TTO: average ~83%

Thanks to the parallel scheduling of chunks which keeps most of the links busy

21/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

33 of 33

Conclusion

  • Identify inefficiencies in existing AllReduce algorithms for mesh topology
  • Propose two algorithms
    • RingBiOdd: Bidirectional ring AllReduce for odd-sized mesh
      • Training time reduction: 50% over Unidirectional Ring and 8% over MultiTree
    • TTO: Tree-based AllReduce for maximum link utilization
      • Training time reduction: 29% over Bidirectional Ring and 33% over MultiTree

​

​

​

Sabuj Laskar

Texas A&M University

sabuj.laskar@tamu.edu

22/22

Sabuj Laskar

Enhancing Collective Communication in MCM Accelerators for Deep Learning Training

Scan to get our paper