## Memo ## Memo with LLM ### 論文情報 - **タイトル**: Understanding Stragglers in Large Model Training Using What-if Analysis - **著者と所属**: - Jinkun Lin, Zhanghan Wang, Aurojit Panda, Jinyang Li（New York University） - Ziheng Jiang, Zuquan Song, Sida Zhao, Menghan Yu, Chenyuan Wang, Wei Jia, Zherui Liu, Shuguang Wang, Haibin Lin, Xin Liu（ByteDance Seed） - Zuocheng Shi（Zhejiang University） - Xiang Shi（ByteDance） - **カンファレンス**: 19th USENIX Symposium on Operating Systems Design and Implementation (OSDI '25) - **発表年**: 2025年7月、Boston, MA, USA（pp. 483–498） ### 論文概要 LLM学習クラスタにおけるストラグラー（遅延ワーカー）の実態を、ByteDanceの5か月分のトレース（3,079ジョブ）を用いて包括的に調査した研究である。ストラグラーが存在しないシナリオをシミュレートする**What-if分析**を核心手法として採用し、ストラグラーの頻度・パターン・根本原因を体系的に解明している。この分析から得られた知見は、ストラグラー監視システム **SMon** として実際のクラスタに展開されている。 ### 詳細解説 #### 問題設定 **入力**: 分散LLM学習ジョブの実行トレース（各オペレーションのタイムスタンプ・種別・ランク情報を含む） **出力**: ストラグラーがジョブ完了時間に与える影響量（スローダウン比）と根本原因の帰属 **前提条件**: - データ並列（DP）・パイプライン並列（PP）・テンソル並列（TP）を組み合わせた分散学習環境 - 同期的な学習ループ（全ワーカーが各ステップでバリアを共有） - ハードウェアは均質（DGXライク、NVLink/PCIe、3層CLOSネットワーク） **課題の本質**: LLM学習は頻繁なマシン間同期を必要とするため、1台の遅いワーカーが全体のスループットを低下させる。しかし従来の障害検出（ハードウェア異常の特定）では不十分であり、複雑な要因に起因するストラグラーは検出・対処が困難である。 #### 提案手法 ##### アーキテクチャ: What-if分析パイプライン ストラグラーが存在しない理想的なシナリオをシミュレートし、実際の実行時間と比較することでストラグラーの影響を定量化する。 **3つの主要コンポーネント:** 1. **オペレーション時間推定**: トレース内の各オペレーションに「理想的な実行時間」を割り当てる - 計算オペレーション: 同一DP/PPランク内の同一オペレーションの平均値 - 通信オペレーション: ブロッキング時間を除いた「転送時間」のみ（中央値） 2. **依存関係モデル**: 並列実行の複雑な依存グラフを以下のストリームで表現 - 計算ストリーム（forward/backward compute） - DP通信ストリーム（params-sync、grads-sync） - PP通信ストリーム4本（forward-send/recv、backward-send/recv） 3. **シミュレーション**: 依存関係グラフに沿い、理想的な時間を使って実行タイムラインを再構築 ##### アルゴリズム/手法の詳細 **スローダウン比 S**: $S = T / T_{\text{ideal}}$ $T$: 実際のジョブ完了時間、$T_{\text{ideal}}$: シミュレーション上の理想的な完了時間 **リソース浪費率**: $\text{waste} = (T - T_{\text{ideal}}) / T = 1 - 1/S$ **オペレーション種別ごとのスローダウン** $S_t$: 特定オペレーション種別のみ理想化した場合のスローダウン比（他は実際値を使用） **ワーカー別帰属指標 $M_W$**: 最も遅い3%のワーカーを理想化した場合の性能回復量 / 全ワーカーを理想化した場合の性能回復量 **パイプラインステージ帰属指標 $M_S$**: 最後のPPステージのみ理想化した場合の性能回復量 / 全ワーカーを理想化した場合の性能回復量 ##### 実装上の工夫 - 通信オペレーションの「転送時間」と「ブロッキング時間」を分離することで、ネットワーク自体の遅延とワーカー待ちによる遅延を区別する - DPランク間・PPランク間の集合通信（AllReduce等）をシミュレーション内でピアとの同期として正確にモデル化 #### 新規性 **既存手法の課題**: - 従来のストラグラー対策はMapReduceなど非同期ワークロードを前提としており、投機的実行やタスク再実行が有効だった - LLM学習は密な同期を必要とするため、これらの手法は適用困難 - クリティカルパス分析は均質並列ワークロードでは全ワーカーがクリティカルパスに存在するため意味をなさない - ハードウェア障害検出のみに頼ったアプローチでは、ソフトウェア起因のストラグラーを見逃す **本研究の解決策**: - What-if分析によりストラグラーの影響量をジョブ単位・ステップ単位・オペレーション種別単位で定量化 - 5か月間・3,079ジョブの大規模実トレースに基づき、根本原因を統計的に帰属 - SMon という実用的な監視システムへの昇華 #### 実験設定 **実験環境**: - DGXライクサーバー: 8 GPU/サーバー、NVLink/PCIe相互接続 - ネットワーク: 3層CLOSトポロジー（オーバープロビジョニング）、高帯域幅 - ジョブ分離: 専有GPU割り当て、均質ハードウェア **データセット**: - **期間**: 2024年1月〜5月（5か月） - **ツール**: NDTimeline（ByteDance内製プロファイリングツール） - **サンプリング**: 学習ステップの10%を採取 - **総ジョブ数**: 3,079ジョブ - ≥256 GPU使用: 31.7% - ≥512 GPU使用: 18.3% - ≥5,000 GPU使用: 3.6% - **カバレッジ**: クラスタGPU時間の約50% - **モデル種別**: Dense・MoE（短・長コンテキスト） **フィルタリング後**: 38.2%のジョブ・56.4%のGPU時間をカバーする有効トレースを解析 **評価指標**: スローダウン比 $S$、リソース浪費率、各帰属指標 $M_W$、$M_S$ #### 実験結果 ##### 定量的評価 **ストラグラーの蔓延度（Figure 3）**: - **42.5%のジョブ**が≥10%のスローダウンを経験 - **約1%のジョブ**が≥45%のGPU時間を浪費 - **集計浪費量**: 全GPU時間の10.4%がストラグラーにより損失 **時間的パターン（Figure 4）**: - ストラグラージョブ内でのステップ単位スローダウンは一貫して持続（中央値の正規化スローダウン=1.0、90パーセンタイル=1.06） - 一時的でなく持続的な原因が支配的であり、10%サンプリングが有効であることを示唆 **オペレーション種別帰属（Figure 5）**: - **計算オペレーションのスローダウン**がリソース浪費の約80%を占める - 通信オペレーションのスローダウンは影響軽微（専用クラスタの高帯域幅が理由） **ジョブサイズ相関**: ジョブ規模（GPU数）とストラグラー深刻度に明確な正相関なし ##### 根本原因分析 **ハードウェア/ソフトウェア障害（$M_W$、Figure 6）**: - 最も遅い3%のワーカーが<50%のスローダウンを引き起こすのは、ストラグラージョブの**98.3%** - 問題ワーカーが主因となるジョブはわずか**1.7%** **パイプラインステージ分割不均衡（$M_S$、Figure 7）**: - **39.3%のジョブ**で最終PP段階が≥50%のスローダウンを引き起こす - 損失層がTransformer層の**9倍**の計算量を必要とすることが原因 - 実験: 9層ジョブに手動チューニングを適用しても1.55倍の負荷削減にとどまる **シーケンス長不均衡（Figure 8-12）**: - **21.4%のジョブ**が影響を受け、平均スローダウン1.34 - Self-attentionの計算量がO(∑s_i²)であるため、シーケンス長のばらつきが計算時間のばらつきに直結 - Figure 9: マイクロバッチ計算時間と∑s_i²の線形相関を実証 - 長コンテキストジョブで深刻度が急増（Figure 12） - **提案緩和策**: 貪欲法でシーケンスを再分配し∑s_i²を均等化→プロトタイプで**23.9%のスループット改善** **Python Garbage Collection（Figure 13）**: - Pythonランタイムのstop-the-world GC一時停止（100msオーダー）がforward-computeカーネルをブロック - 学習進行とともにポーズ時間が増加（メモリリーク疑い） - **展開済み緩和策**: GCを計画的に実施（全ワーカーで同期的に実行） - 128 DPランクジョブで500ステップごとにGCを実施→**12.6%改善** - ただしジョブ単位チューニングが必要でデフォルト有効化されていない **その他（Section 5.5）**: - CUDAメモリフラグメンテーション: 稀だが深刻（cudaFree/cudaMallocコールの増加） - falseカーネル依存: Reduce-scatterカーネルが無関係なカーネルをブロック → `CUDA_DEVICE_MAX_CONNECTIONS`チューニングで緩和 ##### 実用システム: SMon What-if分析パイプラインをオンライン監視システムとして実装: - NDTimelineプロファイルを自動解析 - ワーカースローダウンをヒートマップで可視化（Figure 14） - ヒートマップパターンから根本原因を自動推定 - (a) ワーカー障害: 特定ランクに持続的なスローダウン - (b) ステージ不均衡: 最終PPステージ全体にスローダウン - (c) シーケンス長不均衡: ランダムなDPランクに毎ステップ変動するスローダウン - 展開初月で3件のファールティマシン、1件のシーケンス長不均衡、1件のステージ分割不均衡を検出・対処 #### 考察 (Discussion) ##### 結果の解釈 ストラグラーの主因が通信でなく計算であることは、ByteDanceクラスタの高帯域幅ネットワーク（オーバープロビジョニング）が通信ボトルネックを事実上除去していることを示す。一方でPythonランタイム・アルゴリズム的不均衡（ステージ分割・シーケンス長）といったソフトウェア起因の問題が依然として支配的である。 ##### 優位性の根拠 What-if分析はシミュレーションベースであるため、実際にジョブを再実行することなく反事実シナリオを評価できる。これにより大規模な実トレースへの適用が可能になり、5か月・3,000ジョブ以上のデータを統計的に処理できる。 ##### 限界と例外 - トレースのサンプリング（10%のステップ）により、非常に短命なストラグラーは検出できない可能性がある - What-if分析はオペレーション間の独立性を一定程度仮定しており、複数要因が複雑に絡み合うケースでは過少/過大評価が生じうる - GC緩和策のように、解決策がジョブ固有のパラメータチューニングを必要とするケースでは、全ジョブへの自動適用が困難 #### 強み (Strengths) - 実際の大規模本番クラスタ（ByteDance、最大5,000+ GPU）からの5か月間の実トレースに基づく高い実証的妥当性 - What-if分析という新規手法により、ストラグラーの影響を「根本原因ごとに帰属・定量化」できる点 - SMon として実システムに展開し、初月に実際の障害事例を検出した実用性 - シーケンス長不均衡への緩和策（23.9%改善）という具体的な解決策を提示 #### 弱点・課題 (Weaknesses / Limitations) - GC緩和策はジョブごとのパラメータチューニングが必要であり、スケーラブルな自動化が未達成 - ステージ分割不均衡への根本的解決（層単位の再分割、vocabulary sizeとの兼ね合い）は未解決のまま - ByteDanceの特定クラスタ環境（均質ハードウェア、高帯域ネットワーク）への依存があり、ヘテロジニアス環境や混雑ネットワーク下での結論の外挿性は不明 - トレース収集のオーバーヘッドやサンプリング戦略の詳細が一部未開示 ## Abstract 大規模言語モデル（LLM）の学習は、今日最も要求の高い分散計算のひとつであり、しばしば数千のGPUを必要とし、マシン間での頻繁な同期を伴う。このようなワークロードパターンは、少数の遅いワーカーによって学習が停滞するストラグラーに対して脆弱である。ByteDanceでは、ストラグラーは必ずしもハードウェア障害によって引き起こされるわけではなく、複数の複雑な要因から生じうることを発見している。本研究は、ByteDanceのLLM学習クラスタから収集した5か月分のトレースを用いて、LLM学習におけるストラグラー問題を包括的に調査することを目的とする。中核的な方法論は、ストラグラーが存在しないシナリオをシミュレートし、実際のケースと対比するWhat-if分析である。この方法を用いて、次の問いを検討する：（1）ストラグラーがどの程度の頻度で学習ジョブに影響を与え、ジョブのパフォーマンスにどのような影響を与えるか；（2）ストラグラーは時間的または空間的なパターンを示すか；（3）ストラグラーの潜在的な根本原因は何か。