Wang, Weiyang, et al. "Topoopt: Co-optimizing network topology and parallelization strategy for distributed training jobs." arXiv preprint arXiv:2202.00433 (2022).
[paper]
概要
どんなもの?
- Metaにおける分散DNNトレーニングジョブの解析
- それをもとにした、分散DNNに適したネットワークトポロジと並列戦略の最適化
先行研究と比べてどこがすごい?
- 既存研究ではネットワークトポロジを固定して、分散DNNの並列戦略のみを考えている
- このペーパーでは並列戦略だけでなくネットワークトポロジの最適化も考えた
- これは光スイッチ(OCS)をネットワークに組み込むことによるネットワークの再構成(Reconfiguration)の実用性が増してきているから
- 求めた通信ルーティングを、実際に通信機能をNCCLに組み込んで実機で評価
技術や手法のキモはどこ?
- TotientPermsというring構造の拡張による構成を提案、（ある仮定のもと）サーバー間のホップ数の最大値のオーダーを見積もった
- 幾何的性質を使っていい感じにトポロジを作成する
どうやって有効だと検証した?
- FlexNetPacket simulatorにより、TopoOpt(提案アーキテクチャ)、OCS-reconfig(50 msごとに構成を切り替える), Ideal Switch, Fat-tree, Oversau Fat-tree, Sip-ML, Expanderと
- training iteration time, Interconnect cost を比較
議論はある?
- AllReduce用のサブトポロジの構築方法がヒューリスティック的であり、これでどれほど良いトポロジが得られているのか?(最適なものから離れているのか？)が気になる
- 部分的な(全サーバーが参加しない)AllReduceに対してはうまく適用できなそう？
- 並列戦略探索にFlexFlowエンジンを使用しているが、これはモデル並列の並列戦略のため、データ並列の向けのトポロジ探索にはなっていない
以下詳細
分散DNNトレーニングジョブの解析
並列戦略によってトラフィックパターンは異なる
通信のタイプ分け
- MP転送: モデルの並列処理に関連し、主に順伝播と逆伝播時に計算される活性化と勾配転送
- AllReduce転送: データの並列時の異なるサーバ間での勾配同期、またモデル（テンソル）並列の順伝播と逆伝播でも使用される
図は縦がsource、 横がdestination、色がトラフィック量
ネットワークトポロジと並列戦略の最適化
並列戦略とネットワークトポロジを交互に最適化させることで計算量削減
FlexFlow
MCMC (マルコフ連鎖モンテカルロ) 探索アルゴリズムを使用 未読のため、詳細分からず...
TOPOOPT System Design
- serverはd個のNICを持ち、それぞれがd個の光スイッチに接続されている
- 実験では4 portを持つNIC（右図）を用いてd=4の構成を作成
- 1つのOptical Switchで1つのサブトポロジを作成→それを組み合わせる
トポロジの最適化
AllReduce用とモデル並列用のサブトポロジを組み合わせる
- トラフィックの量（通信関数の実行回数）に応じて、AllReduce用とモデル並列用のサブトポロジ数を決定
- Ring-AllReduce のトポロジを確保するために、AllReduce転送には少なくとも1つのサブトポロジを作成
- AllReduce用のトポロジ
- AllReduceのグループごとに複数のTotientPerms(後述)を作成
- MP用のトポロジ
- トラフィック量に応じた最大マッチング(後述)
AllReduce転送用のサブトポロジ
- TotientPerms: n(サーバー数)と違いに素な数pを用いてp飛ばしで接続すると、n個のサーバをちょうど1回だけ経由して一周できる(Ring構造の拡張)
- 1つのTotientPermを1つのOptical Switchで作成
- geometric sequence (隣り合う2つの項の比が項番号によらず等しい数列)に従ってpを選択してTotientPermを組み合わせることで、直径（最大ホップ）のオーダーを求められる
MP転送用のサブトポロジ
https://demonstrations.wolfram.com/TheBlossomAlgorithmForWeightedGraphs/
ルーティングの最適化 > AllReduce
- Coin Changeアルゴリズムを用いて最小ホップのルーティングを求める(お釣り(サーバ番号差分)を最小のコイン（サブトポロジ)で返すことに相当)
- +1, +3, +7のTotientPermsで例示
- (水色) 0→11(1+3+7)
- (緑色) 0→5(1+1+3)
関連記事
*1:Deep Learning Recommendation Model
*2:Jia, Zhihao, Matei Zaharia, and Alex Aiken. "Beyond Data and Model Parallelism for Deep Neural Networks." Proceedings of Machine Learning and Systems 1 (2019): 1-13.
