> [!abstract] 概要 > Cassini は機械学習クラスタ向けのネットワーク対応ジョブスケジューラである。Cassini は、異なるジョブの通信パターンをネットワークリンク上に配置する際に考慮する新しい幾何抽象を導入する。そのために Cassini は Affinity グラフを使い、共通のネットワークリンクを共有するジョブ群の通信位相を互いにインターリーブさせるタイムシフト値の系列を求める。24 サーバのテストベッドで行った 13 種の代表的な機械学習モデルによる実験では、最新のスケジューラと比較して、Cassini はジョブの平均・テール完了時間をそれぞれ最大 1.6× / 2.5× 改善することを示す。さらに Cassini がクラスタ内の ECN マーク済みパケット数を最大 33× 削減することも示す。 ## 論文情報 | 項目 | 内容 | |---|---| | 著者 | Sudarsanan Rajasekaran, Manya Ghobadi (MIT), Aditya Akella (UT Austin) | | 会議 | 21st USENIX NSDI 2024 | | 開催日 | 2024年4月16〜18日、カリフォルニア州サンタクララ | | URL | https://www.usenix.org/conference/nsdi24/presentation/rajasekaran | | コード | http://cassini.csail.mit.edu | ## 概要 分散 DNN 訓練ワークロードは、ネットワーク通信のオーバーヘッドが訓練イテレーション時間の大部分を占めるほどになっている。しかし既存のスケジューラ(Themis、Pollux など)はジョブ配置時にジョブ間の通信パターンの干渉を考慮しない。Cassini はこの問題に対して「通信パターンの幾何抽象化」と「互換性スコア」による配置評価を導入し、既存スケジューラに対してプラグイン的に機能拡張する。 ## 問題設定 GPU クラスタで複数の訓練ジョブが同一ネットワークリンクを共有すると、AllReduce などの通信集約フェーズが衝突して輻輳が生じる。Cassini の観察によれば: 1. DNN 訓練ジョブのネットワーク需要は訓練パラメータが一定である限りイテレーションをまたいで反復する 2. 1 イテレーション内に複数の上昇フェーズ(Up)と下降フェーズ(Down)が存在する 3. データ並列・パイプライン並列・テンソル並列・ハイブリッド並列のいずれもこのパターンに従う 例: GPT-1(データ並列、4 GPU)では forward フェーズは通信ほぼゼロ、backprop + AllReduce フェーズで 50 Gbps 近くに達する。GPT-3(ハイブリッド並列)では 1 イテレーションに 6 つの Up-Down フェーズが生じる。 ![[Pasted image 20260619143325.png]] ジョブ間でタイムシフトを適切に挿入すると、VGG19 2 ジョブの例では 90 パーセンタイルテール反復時間が 1.26× 短縮した。 ## 提案手法 ### 幾何抽象化(Geometric Abstraction) 訓練イテレーション時間を周長とする円にネットワーク需要時系列を巻きつける。すると異なるイテレーションの Up/Down フェーズが円の同じ角度に重なって現れる。複数ジョブが同一リンクを共有する場合、各ジョブを対応する「統一円(unified circle)」(反復時間の最小公倍数を周長とする)に置き、円を回転させることで通信需要の和がリンク容量を超えない最大互換性スコアを求める。 互換性スコア: `score = 1 − average(Excess(demandα))` ここで `Excess` はリンク容量超過分。完全互換のとき score = 1。高度に非互換のとき score は負値になりうる。 最適化定式化(表 1): - 最大化: 全角度にわたる超過帯域幅需要の平均を最小化する(式 2) - 制約: 各角度での全ジョブ帯域幅需要の和が `demandα` 以下(式 3)、回転角 `Δ_j` は `[0, 2π/r_j]` の範囲内(式 4) - 出力: 各ジョブの回転角 `Δ_j` → タイムシフト `t_j = (Δ_j / 2π) × p_l mod iter_time_j` ### Affinity グラフとクラスタ規模展開 大規模クラスタでは同一ジョブが複数リンクを通過し、異なるリンクで異なるタイムシフト値が得られる問題(クラスタ規模整合問題)が生じる。Cassini は二部グラフ `G = (U, V, E)` を導入する: - `U`: 他ジョブとリンクを共有するジョブ集合 - `V`: 複数ジョブを運ぶリンク集合 - 辺の重み: リンクにおけるジョブのタイムシフト値 BFS ベースの Affinity グラフ走査(アルゴリズム 1)により、ループのない Affinity グラフで全ジョブに一意なタイムシフトを割り当てることを保証する(Theorem 1: 正確性と一意性)。ループを含む配置候補は破棄される。 ### 既存スケジューラへの組み込み(Themis を例に) 1. **ステップ 1**: Themis の競売フェーズで、単一配置ではなく最大 N 件の配置候補を返す 2. **ステップ 2**: 各候補に対して Affinity グラフを構築し互換性スコアを並列計算、上位候補を選択してアルゴリズム 1 でタイムシフトを算出(アルゴリズム 2) 3. **ステップ 3**: Themis エージェントがタイムシフトを受け取り、次イテレーション開始時刻を遅延させて適用。ドリフト発生時は自動調整(平均調整頻度 < 2 回/分) 改変規模: Themis に対して約 1000 行(うち約 300 行が配置候補生成部)。 ### 角度離散化精度 5° の離散化精度がタイムシフト精度 100% と低計算オーバーヘッドの最良点(スイートスポット)であると確認。粗粒度(64°/128°)では精度が落ちる一方、細粒度(1°)では実行時間が増大する。 ## 新規性 1. 訓練ジョブの周期的通信パターンを「円形幾何抽象」で捉え、ジョブ間互換性を単一の連続最適化問題に落とした初の定式化 2. 単一リンクの互換性スコアをクラスタ規模に拡張する Affinity グラフとその BFS 走査アルゴリズム、ならびに正確性・一意性の形式証明(Theorem 1) 3. 既存スケジューラへのプラグイン設計: ハイパーパラメータや GPU 割り当て数には介入せず、配置とタイムシフトのみを変更 4. 渋滞制御プロトコル(DCQCN)・スイッチ/NIC の特別サポートを要しない透明な実装 5. 先行ワークショップ論文(HotNets'22)を大幅に拡張し、モデル並列・クラスタ規模対応・形式証明を追加 ## 実験設定 - クラスタ: 24台の ASUS ESC4000A-E10、各 NVIDIA A100 GPU (40 GB HBM2) × 1、Mellanox ConnectX5 50 Gbps NIC × 1 - ネットワーク: Tofino スイッチで 13 論理スイッチ・48 双方向リンクの 2:1 過剰加入トポロジをエミュレート - DNN モデル: VGG11/16/19、ResNet50、WideResNet101、BERT、RoBERTa、XLM、CamemBERT、GPT-1/2/3、DLRM の 13 モデル - 並列化: VGG/ResNet/BERT 系は PyTorch DistributedDataParallel(データ並列)、DLRM/GPT 系は DeepSpeed ハイブリッド並列 - トレース: Poisson トレース(負荷 80〜100%)・動的トレース・スナップショットトレース - 比較手法: Themis / Th+Cassini / Pollux / Po+Cassini / Random / Ideal ## 実験結果 ### データ並列ジョブ混在(Poisson トレース) - Th+Cassini vs Themis: 平均反復時間 **1.6×** 改善、99 パーセンタイルテール **1.8×** 改善 - Th+Cassini の性能は理想スケジューラ(専用クラスタ)と同程度 ### モデル並列ジョブ(Poisson トレース) - Th+Cassini vs Themis: 平均 **1.2×**、99 パーセンタイル **1.6×** 改善 ### ECN 削減(動的トレース) - Th+Cassini vs Themis: データ並列で平均 + 99p テール反復時間 **1.5× / 2.2×** 改善 - DLRM の ECN マーク数: Themis 比 **27×**、Pollux 比 **33×** 削減 - モデル並列動的トレースで ECN を最大 **29×** 削減 ### 部分互換性(スナップショットトレース) - 互換性スコア 1.0〜0.9 では大幅な反復時間削減 - スコア 0.6 になると改善幅は縮小し、Cassini はそのような組み合わせの同一リンク配置を回避 ### マルチ GPU サーバ(動的トレース) - 1 サーバ 2 GPU 構成: Th+Cassini vs Themis で平均・99p テール **1.4× / 1.9×** 改善 ### タイムシフト調整頻度 - 全スナップショットで平均 2 回/分未満。通常の訓練でタイムシフトが大きく崩れないことを確認 ## 考察 Cassini が改善できない主な条件: 1. **全リンクを単一ジョブが専有**できる完全局所配置は Cassini の介入余地がない(Ideal と同等) 2. **互換性スコアが低い**ジョブを同一リンクに置かざるを得ない場合は改善幅が小さい 3. **ML 以外の従来データセンターワークロード**との共存は設計スコープ外 Cassini が想定する制約: - GPU はジョブ間で共有しない(マルチテナント GPU は設計外だが最適化定式化に組み込める) - ML 訓練トラフィックと非 ML トラフィックが同一ネットワークを共有しない - 現代の大規模訓練クラスタでは専用 GPU NIC と CPU NIC の分離が一般的 ## 強み / 弱点・課題 **強み**: - 既存スケジューラへのプラグイン設計で実装コストが小さい - ハードウェア変更・渋滞制御プロトコル変更なしで機能する - DP/PP/TP/ハイブリッド並列のすべてに対応する汎用幾何抽象化 - Theorem 1 による正確性・一意性の形式保証 **弱点・課題**: - 非 ML ワークロードとのネットワーク共有には対応していない - クラスタ規模拡大に伴い互換性スコアの低いジョブ対が増加した場合の挙動は未検証 - 各ジョブのプロファイリング(イテレーション時間・リンク使用量)が必要 - GPU マルチテナンシーへの拡張は将来課題