# FAST: An Efficient Scheduler for All-to-All GPU Communication ## 論文情報 | 項目 | 内容 | |---|---| | 著者 | Yiran Lei (Carnegie Mellon University / MangoBoost), Dongjoo Lee (MangoBoost), Liangyu Zhao (University of Washington), Daniar Kurniawan, Chanmyeong Kim, Heetaek Jeong, Changsu Kim, Hyeonseong Choi (MangoBoost), Liangcheng Yu (University of Pennsylvania), Arvind Krishnamurthy (University of Washington), Justine Sherry (Carnegie Mellon University), Eriko Nurvitadhi (MangoBoost) | | 会議 | NSDI 2026(第 23 回 USENIX Symposium on Networked Systems Design and Implementation, 2026年5月4〜6日, Renton, WA) | | PDF | [[.raw/papers/nsdi26-lei-yiran.pdf]] | | URL | https://www.usenix.org/conference/nsdi26/presentation/lei-yiran | | コード | https://github.com/MangoBoost/FAST | ## 概要 FAST は、Mixture-of-Experts(MoE)などの現代的機械学習ワークロードにおいて深刻なボトルネックとなっている AllToAllv 集団通信を効率的にスケジューリングする初の多項式時間オンライン・スケジューラである。FAST はワークロードの歪み(skew)・動的性・異種 2 層ファブリック・インキャスト輻輳という四つの課題を、(i)高速なスケール内(scale-up)ファブリックによるサーバ内リバランスと、(ii)Birkhoff 分解を用いた均等・1 対 1 スケール外(scale-out)転送ステージという 2 フェーズで解決する。NVIDIA H200 と AMD MI300X の両テストベッドで既存手法を上回り、合成時間を数桁短縮する。 ## 問題設定 AllToAllv 通信は GPU エンドポイントが全員から全員へ異なるサイズのデータを交換する集団通信操作で、MoE モデルでは各 MoE 層ごとに 2 回呼び出され、訓練時間の 30–56% を占める。課題は 4 つある。 **ワークロード層の課題**: - **歪み(skew)**: MoE のゲーティング関数が一部エキスパートに偏った数のトークンを送るため、GPU 対間の転送量が最大 12× 以上ばらつく。一部 NIC が長時間待機するストラグラー効果が生じる。 - **動的性(dynamism)**: トークンルーティングは入力トークンと各 MoE 層のゲーティング関数で決まるため予測不能。数百ミリ秒ごとにトラフィックパターンが変化し、静的なスケジュールは機能しない。 **システム層の課題**: - **異種 2 層ファブリック**: スケール内(例: NVLink 900 GBps)とスケール外(例: Ethernet 800 Gbps)では帯域に約 1 桁の差があり、バランスの取れた割り当てを単純に適用しても実際の転送は不均等に終わる。 - **インキャスト輻輳(incast congestion)**: AllToAllv の密な通信パターンでは多数の送信元が同一 NIC のダウンリンクに集中し、スイッチキューを溢れさせ性能を低下させる。 **既存手法の限界**: TACCL・TE-CCL・SyCCL といったソルバーベースのスケジューラは NP 困難な定式化を採用しており、32 GPU でも数分〜数時間かかる。最速の SyCCL でも 16 GPU で 3.6 秒を要し、数百ミリ秒単位でパターンが変化する MoE では使えない。一方 NCCL 等の固定スケジュールは歪みやインキャストを無視し性能が低い。 ## 提案手法 ### 設計の核となる観察 スケール内帯域はスケール外より約 1 桁高速なため、スケール外に見せるワークロードをスケール内で整形(reshaping)できる。問題をスケール外の効率化に集中することで、NP 困難なグローバル最適化を多項式時間の 1 対 1 マッチング問題に帰着できる。 ### 2 フェーズのスケジューラ **フェーズ 1: サーバ内スケジューリング(バランシングと再配布)** 目的は GPU ごとの送受信量を均等にし、スケール外ファブリックが均一なワークロードを見るようにすること。2 ステップからなる。 1. **送信側バランシング**: サーバ内の過負荷 GPU から軽負荷 GPU へスケール内でデータを移し、スケール外の送信量を揃える。 2. **ピアトランスファー(peer transfer)**: 各送信 GPU は同じローカルインデックスの受信 GPU へデータを転送する(B0→A0, B1→A1)。受信量もバランスされる。ただしデータは正しいサーバには届くが、最終的な正しい GPU には届かない場合がある。 3. **サーバ内再配布(redistribution)**: スケール外転送完了後、スケール内を使って各ステージのデータを正しい GPU へ届ける。スケール内は約 1 桁高速なため、このオーバーヘッドは小さい。 この処理により 6×6 のような GPU レベル行列が 3×3 のサーバレベル行列に削減できる。 **フェーズ 2: サーバ間スケジューリング(均等・1 対 1 転送)** Birkhoff 分解(1946 年)をスケジューリングに再解釈して適用する。このアルゴリズムは任意のトラフィック行列を、各エントリが等しい値を持つ置換行列の加重和として表現する。スケジューリングの観点では、各置換行列がひとつの転送ステージ——「すべての能動的な送信元が一つの受信先へ同量のデータを送り、全員が同時に終わる」——に対応する。 Birkhoff 分解の特性: - **インキャスト回避**: 各ステージは 1 対 1 マッチングなのでインキャストが起きない - **最適性**: ボトルネックのサーバ(最大行和・最大列和を持つサーバ)が全ステージで常に活動し続けるため、理論的な完了時間の下限に達する - **多項式時間**: O(N⁵) の計算量で合成可能 従来の SpreadOut は各ステージを巡回的に選ぶため、ボトルネックサーバが特定のステージで待機させられ最適性を保証できないが、Birkhoff 分解は常に最適解を生む。 **パイプライン統合**: バランシング → ステージ 1 スケール外転送 → ステージ 1 再配布(ステージ 2 スケール外転送とオーバーラップ) → … という形でスケール外転送を可能な限り連続動作させ、スケール内操作を背景で隠蔽する。 ### 実装上の要点 - 分散動作: 全 GPU が同一のトラフィック行列から同一のスケジュールを独立に計算するため、中央コーディネータが不要。同期するのはトラフィック行列(コンパクトな整数配列)のみ。 - Megatron-LM への統合: Megatron-LM はすでに `num_global_tokens_per_expert` の All-Gather でトラフィック行列を構築しているため、FAST はこの既存情報を利用するだけで新たな通信を増やさない。 - NVIDIA H200 では CUDA IPC / NVSHMEM、AMD MI300X では RCCL を使って転送を実装。 ## 新規性 - **Birkhoff 分解を GPU 集団通信スケジューリングに初めて適用**: スイッチスケジューリングへの適用例は存在したが、GPU エンドポイントでの集団通信スケジューリングへの応用は本研究が初。 - **問題の単純化**: NP 困難な汎用スケジューリングを「スケール外に集中し、スケール内で歪みを吸収する」という方針で多項式時間問題に帰着。 - **動的ワークロードへの適用**: MoE の数百ミリ秒単位のパターン変化に対応できる初のオンライン・スケジューラ(64 GPU で 221 µs)。 ## 実験設定 **テストベッド**: - *NVIDIA クラスタ*: 4 サーバ × 8 GPU (NVIDIA H200)。400 Gbps InfiniBand。スケール内 NVLink 450 GBps、スケール外 50 GBps、比率 9:1。 - *AMD クラスタ*: 4 サーバ × 8 GPU (AMD MI300X)。100 Gbps RoCEv2 Ethernet (DCQCN)。スケール内 Infinity Fabric 448 GBps、スケール外 12.5 GBps、比率 35:1。 **ベースライン**: - ソルバーベース: TACCL, TE-CCL - 産業ライブラリ/ヒューリスティクス: NCCL, DeepEP, MSCCL (NVIDIA); RCCL, SpreadOut, MSCCL (AMD) **ワークロード**: Zipf 分布によるスケードAllToAllv、一様分布のランダム AllToAllv、Megatron-LM での実 MoE 訓練(expert parallelism 16/24/32、Top-K ルーティング K=1〜4)。 ## 実験結果 **AllToAllv 単体性能**: - NVIDIA テストベッド: スケード(skew factor 0.8)ワークロードで NCCL 比 1.2–1.3×、DeepEP 比 1.2–1.5×、TACCL 比 3× 以上の性能向上。 - AMD テストベッド: スケードワークロードで RCCL 比 1.3–2.6×、SpreadOut 比 2.5–2.8×、TACCL 比 2.9–3.8×、TE-CCL 比 3.6–4.7× の性能向上。RCCL はインキャストで著しく性能が低下。 **エンドツーエンド Megatron-LM MoE 訓練(AMD テストベッド)**: - Expert Parallelism を変化させた場合: RCCL 比 1.18–4.48× のスループット向上。EP が大きくなるほど RCCL はインキャスト輻輳で急激に劣化。 - Top-K ルーティングを変化させた場合: RCCL 比 1.75–7.88× の向上。K が増えると FAST は改善するが RCCL は逆に劣化。 **合成時間**: - FAST: 32 GPU で 25 µs、64 GPU で 221 µs、96 GPU で 805 µs。EP320(40 サーバ)でも 77 ms。 - 比較: SyCCL(最速のソルバーベース)が 16 GPU で 3.6 秒かかるのに対し、FAST は同規模で 3.1 µs——約 1,000 倍速。 **スケーリング(シミュレーション)**: 300 GPU まで最適値から 5% 以内を維持。スケール内/スケール外帯域比が大きいほど性能向上。 **バランシング/再配布オーバーヘッド**: 典型ワークロードで 5% 未満、極度スケード(skewness factor 0.9)でも 8% 未満。 **メモリオーバーヘッド**: ランダムワークロードで元の AllToAllv バッファの約 30% 増。NVIDIA H200 の 141 GB メモリに対し 0.22% 以下。 ## 考察 - **均等 AllToAllv への適用**: FAST は均等ワークロードではバランシング・再配布の小オーバーヘッドを加えるため、NCCL や DeepEP と同水準に留まる。FAST の優位はスケードワークロードに特化する。 - **他集団通信への適用外**: AllReduce・AllGather は静的・均等パターンが多く既存ライブラリで十分なため、FAST は意図的に AllToAllv に特化。 - **他のトポロジ**: 現在の実装は 2 層ファブリックに特化するが、スケール内でのリシェイプという核心思想は多層ネットワークにも自然に拡張可能。 - **輻輳制御との関係**: FAST は集団通信レイヤーで動作し、トランスポート層の輻輳制御と直交。理想的な輻輳制御下でもトラフィック歪みと NIC 利用率の改善により追加効果が得られる。 - **ハイブリッド並列化**: 純 expert parallelism への評価に留まる。テンソル並列・パイプライン並列との組み合わせはネットワーク共有の調整が必要で今後の課題。 ## 強み - 理論的根拠(Birkhoff 分解の最適性保証)と実用性(多項式時間・221 µs の合成)を両立している - NVIDIA・AMD の異種ハードウェアで実証 - 既存フレームワーク(Megatron-LM)への統合が中央コーディネータ不要で容易 - 数学的に最悪ケースの性能境界(B1/B2 × (m + m/n))を証明済み ## 弱点・課題 - 評価クラスタが 4 サーバ(32 GPU)に留まる実測(スケール実験はシミュレーション) - 均等 AllToAllv ではオーバーヘッドが生じ既存手法と同水準に落ちる - 非対称スケール内トポロジ(AMD MI250 のリング、NVIDIA V100 のハイブリッドキューブメッシュ)には SpreadOut ベースの代替が必要で、新旧 GPU への一般化に制約 - EP と tensor/pipeline 並列が混在するハイブリッド並列化への対応は未実装 - 段数が増えると同期オーバーヘッドが累積するが、段数最小化は NP 困難でアプローチは将来課題 ## 関連 - 集合通信スケジューリング: [[集合通信]] / [[NCCL]] / [[Megatron-LM]] - MoE との関連: [[Mixture-of-Experts]] / [[LLM分散学習]] / [[並列化戦略]] - スケード/ストラグラー: [[ストラグラー]] - エンティティ: [[MangoBoost]] / [[Carnegie Mellon University]] / [[University of Washington]] / [[University of Pennsylvania]] - 関連 MOC: [[分散深層学習 - MOC]] / [[AI Infra Telemetry - MOC]] ## 出典 - [[.raw/papers/nsdi26-lei-yiran.pdf]](全文)