DeepLearningで使われるallreduceのアルゴリズム

DeepLearningで利用されているallreduceのアルゴリズム

allreduceのアルゴリズムについて調べたかったので， 自分の観測できた範囲でまとめて行こうと思います． その道のプロではないので，コメントなど頂けると幸いです．

ring-all-reduce

baiduが提唱したアルゴリズムでring上に順々にallreduceしていく．
１プロセスあたりのデータ送信量は2(P−1)/P∗N．(Pはrank数，Nはデータ数)
この記事がわかりやすい．
nccl 2.3もこのアルゴリズムで実装されているがそのせいで？マルチノード環境で性能がスケールしなかったのではないか？

hierarchical allreduce論文

以下の図がイメージしやすい．最初にグループ内でreduce，そしてグループ間でring-allreduceを実行し, 最終結果を各グループ内でbroadcastを実施する．

2D-Torus all-reduce

sonyの論文に載っている. 図２がイメージしやすい．以下の３つの手順
1. 水平方向にreduce-scatterを実行
2. 垂直方向にallreduce実行
3. Allgatherを実行

水平方向のGPU数をX, 垂直方向のGPU数をY，合計 N = X * Y とする． ２D-Torus allreduceは2(X-1) 回GPU-GPU opが実行される． ring-allreduceだと2(N-1)回 , hierarchical allreduceは2D torusと同じだが，2D Torusで２番めに実行される垂直方向のallreduceのデータサイズはX倍少ない．

double binary trees

もともとMPIで提唱されていたアルゴリズムで，nccl 2.4で利用されている．
下記のように２つのツリーを重ね合わせると，ルートランクを除いてすべてのランクに２つの親と２つの子がいる．
２つのツリーを利用してそれぞれデータの半分を処理する場合は，各ランクはデータの半分を２回受信しデータの半分を２回送信する．らしいが．．具体的にはどんな感じだ？