# Understanding Stragglers in Large Model Training Using What-if Analysis > [!abstract] 概要 > 大規模言語モデル(LLM)の学習は今日もっとも要求の高い分散計算のひとつであり、しばしば数千の GPU を必要とし、マシン間で頻繁に同期する。このようなワークロードパターンは、少数の遅いワーカーによって学習が停滞するストラグラーに対して脆弱である。ByteDance では、ストラグラーは必ずしもハードウェア障害によって引き起こされるわけではなく、複数の複雑な要因から生じうることを発見した。本研究は、ByteDance の LLM 学習クラスタから収集した 5 か月分のトレースを用いて、LLM 学習におけるストラグラー問題を包括的に調査することを目的とする。中核的な方法論は、ストラグラーが存在しないシナリオをシミュレートし、実際のケースと対比する What-if 分析である。この方法を用いて次の問いを検討する:(1) ストラグラーはどの程度の頻度で学習ジョブに影響を与え、ジョブの性能にどう影響するか、(2) ストラグラーは時間的または空間的なパターンを示すか、(3) ストラグラーの潜在的な根本原因は何か。 ## 論文情報 - 媒体: 19th USENIX Symposium on Operating Systems Design and Implementation(OSDI '25)、2025-07-07〜09、Boston, MA, USA(pp. 483–498) - 著者・所属: - [[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]]) - corresponding authors: Haibin Lin, Jinyang Li - url: https://www.usenix.org/conference/osdi25/presentation/lin-jinkun - コード: [[StragglerAnalysis]](`https://github.com/ByteDance-Seed/StragglerAnalysis`、artifact branch、commit 8efcd7f、Python 3.11) - 既存一次ノート(詳細日本語メモ): [[papers/2025__OSDI__Understanding Stragglers in Large Model Training Using What-if Analysis|2025__OSDI__Understanding Stragglers...]] ## 概要 LLM 学習クラスタにおけるストラグラー(遅延ワーカー)の実態を、ByteDance の 5 か月分のトレース(3079 ジョブ)を用いて包括的に調査した研究である。ストラグラーが存在しないシナリオをシミュレートする What-if 分析を核心手法として採用し、ストラグラーの頻度・パターン・根本原因を体系的に解明する。分析パイプラインの一部はストラグラー監視システム [[SMon]] として実クラスタに展開されている。プロファイラには内製ツール [[NDTimeline]] を用いる。 ## 問題設定 - 入力: 分散 LLM 学習ジョブの実行トレース(各オペレーションのタイムスタンプ・種別・ランク情報を含む)。 - 出力: ストラグラーがジョブ完了時間に与える影響量(スローダウン比)と、根本原因の帰属。 - 前提条件: データ並列(DP)・パイプライン並列(PP)・テンソル並列(TP)・コンテキスト並列(CP)を組み合わせたハイブリッド並列の同期学習ループ。ハードウェアは均質(NVIDIA DGX ライク、サーバあたり 8 GPU、NVLink/PCIe 相互接続、3 層 CLOS ネットワーク、オーバープロビジョニング)。 - ストラグラーの定義: 全ワーカーが同じ時間で割り当て作業を終えれば straggler-free。ある理由で遅れるワーカーをすべてストラグラーと見なす(ハードウェア障害だけでなく、全ワーカーを一様に止める GC ポーズ、データスキューや重み分割の不均衡による負荷偏りも含む広い定義)。 - 課題の本質: LLM 学習は頻繁なマシン間同期を必要とするため、1 台の遅いワーカーが全体を停滞させる。MapReduce 等の非同期前提のバックアップワーカー方式は密同期では性能を損ない適用困難。クリティカルパス分析も均質並列ワークロードでは多数の経路が同程度にクリティカルになり破綻する(Coz が指摘)。 ## 提案手法 ### What-if 分析パイプライン ストラグラーが存在しない代替タイムラインをトレースベースでシミュレートし、実トレースと対比して影響を定量化する。主要コンポーネントは 3 つ。 1. **オペレーション時間推定**: トレース内オペレーションを (training step, microbatch, PP rank, DP rank) の 4 次元テンソル(OpDuration)として整理し(オペレーション種別ごとに 1 テンソル)、各要素に理想的な実行時間を割り当てる。 - 同種オペレーションは同じワークロードを処理するため、ストラグラー不在なら理想 OpDuration の全要素が等しくなる。計算オペレーションは等値化対象グループの**平均値**、通信オペレーションは**中央値**を理想値とする(通信は外部要因で稀に極端に長くなり平均を歪めるため中央値が適する)。 - 通信オペレーションは traced duration を「転送時間(transfer-duration)」と「ブロッキング時間(blocking-duration、集団通信のピア待ち)」に分解し、集団内の全ピアの最大開始時刻を自身の終了時刻から引いて転送時間を推定。OpDuration には転送時間のみ格納する。 2. **依存関係モデル**: 各ワーカーが複数のストリームでオペレーションを実行するとモデル化する。計算ストリーム、DP 通信ストリーム(params-sync/grads-sync)、PP 通信 4 ストリーム(forward-recv $R_F$・backward-recv $R_B$・forward-send $S_F$・backward-send $S_B$)。依存は (a) 同一ストリーム内の逐次依存、(b) DP 通信と計算の依存(params-sync → 最初の forward-compute、最後の backward-compute → grads-sync)、(c) PP 通信と計算の依存(receive → compute、compute → send)、(d) クロスランク通信依存(同一 PP ランクの DP ランク群が params/grads-sync 集団を構成、隣接 PP ランクが P2P ペアを構成。集団・P2P は全ピアが launch するまでデータ転送を開始できない)。 3. **シミュレーション**: 依存が満たされ次第オペレーションを launch する。計算オペレーションは start + OpDuration を終了時刻とする。通信オペレーションは集団/P2P の全ピアの launch を待ち、最大 launch 時刻 + 転送時間を終了時刻とする。シミュレートされた JCT を実トレースと比較する。 ### 帰属の指標 スローダウン比 $S$: $S \triangleq T / T_{\text{ideal}}$ $T$ は実トレースを未改変のまま再シミュレートした JCT(シミュレーション誤差の補正用)、$T_{\text{ideal}}$ は全ストラグラーを理想化したときの JCT。リソース浪費率は次式で、ジョブが GPU を占有するためスローダウンが直接 GPU 時間の浪費に換算できる。 $\frac{T - T_{\text{ideal}}}{T} = 1 - \frac{1}{S}$ オペレーション種別ごとのスローダウン $S_t$ は、種別 $t$ の OpDuration だけ理想化せず残したときの JCT $T_{\text{ideal}}^{-t}$ を用いて $S_t \triangleq T_{\text{ideal}}^{-t} / T_{\text{ideal}}$。ワーカー別スローダウン $S_w \triangleq T_{\text{ideal}}^{-w} / T_{\text{ideal}}$。問題ワーカー帰属指標 $M_W$ は、スローダウン上位 3% のワーカー集合 $W$ を理想化したときの性能回復量を、全ワーカー理想化時の回復量で正規化したもの $M_W = (T - T_{\text{ideal}}^{W}) / (T - T_{\text{ideal}})$。ステージ分割帰属指標 $M_S$ は最終 PP ステージのみ理想化したときの寄与 $M_S = (T - T_{\text{ideal}}^{\text{lastStage}}) / (T - T_{\text{ideal}})$。$M_W$ の計算は全ワーカー分のシミュレーションが高価なため、DP ランク・PP ランク単位のスローダウンの小さい方を各ワーカーに割り当てる近似で $\text{DP degree} \times \text{PP degree}$ から $\text{DP degree} + \text{PP degree}$ 回へ削減する。 ## 新規性 - **大規模実トレースへの What-if 分析の適用**: 5 か月・3079 ジョブの実トレースに対し、ストラグラーの影響量をジョブ単位・ステップ単位・オペレーション種別単位で定量化し、根本原因を統計的に帰属する。 - 非同期前提の従来ストラグラー対策(バックアップワーカー、非同期 SGD、更新ドロップ)が密同期の LLM 学習に適用困難である点、クリティカルパス分析が均質並列ワークロードで破綻する点を明示し、トレースベースのシミュレーションで回避する。 - 分析パイプラインを実用監視システム [[SMon]] へ昇華し、本番運用で検証した。 ## 実験設定 - 期間: 2024-01-01 〜 2024-05-31(5 か月)。LLM 事前学習ジョブのトレース。 - 対象: 128 GPU 以上を使うジョブのみ。フィルタ後 3079 ジョブ。≥256 GPU が 31.7%、≥512 GPU が 18.3%、≥5000 GPU が 3.6%。全 LLM 学習ジョブの GPU 時間の約半分をカバー。Dense・MoE、短・長コンテキストを含む。 - 学習システム: オープンソース [[Megatron-LM]] のカスタム版(DP/PP/TP/CP を組み合わせ。CP は内製実装)。 - プロファイラ: 内製 [[NDTimeline]]。既定で学習ステップの 10% をサンプリングし、forward/backward-compute と通信(params-sync, grads-sync, forward/backward-send/recv)の start/end を記録(表1)。マシン間クロック同期によりオペレーションを整列。 - 評価指標: スローダウン比 $S$、リソース浪費率、$S_t$、$S_w$、$M_W$、$M_S$。 - トレースの取捨選択: 繰り返し失敗するジョブ(15 回超の再起動)13.9% を除外、what-if 分析に失敗したジョブ 50.0%(コマンドライン解析不能 28%、ステップ不足 28%、トレース破損 25%)を除外、シミュレーション誤差 > 5% のジョブを除外。最終カバレッジは 38.2% のジョブ・56.4% の GPU 時間。 ## 実験結果 - **蔓延度(図3)**: 42.5% のジョブが ≥10% スローダウン。> 10% のジョブが ≥21.3%(p90)の GPU 時間を浪費、約 1% のジョブが ≥45.0%(p99)を浪費。全 GPU 時間の 10.4% がストラグラーで浪費。p50 浪費率 7.8%。 - **時間的パターン(図4)**: ストラグラージョブ(S > 1.1)内のステップ単位スローダウンは持続的。正規化スローダウンの中央値 1.0、p90 でも 1.06。一時的な環境要因でなく持続的な問題が主因であり、少数ステップのサンプリングで十分かつ費用対効果が高いことを示す。 - **オペレーション種別帰属(図5)**: 計算オペレーションのスローダウンが浪費の大半を占める。通信の影響は軽微(専用クラスタの広帯域・内製ネットワーク最適化が理由)。FALCON とは逆の結論。PP レベル通信は DP レベルよりやや影響大(DP 通信はオーバーラップで吸収される一方、PP 通信の warmup/cooldown はクリティカルパス上)。 - **ジョブサイズ相関(図なし、§4.4)**: ジョブ規模とスローダウンに明確な正相関なし。大規模ジョブは on-call チームが手厚く最適化、長コンテキストジョブは深刻だが小規模、といった交絡が示唆される。S > 3 の大スローダウンはすべて大規模ジョブで、3% 未満のワーカーが原因かつ計算オペレーションの遅延が主。 - **問題ワーカー($M_W$、図6)**: 上位 3% のワーカーがスローダウンの 50% 超を説明するのはストラグラージョブのわずか 1.7%。問題ワーカーは主因ではない。ただし問題ワーカーが主因の少数ケースではスローダウンが大きく(平均 3.04 対 全体平均 1.28)。 - **ステージ分割不均衡($M_S$、§5.2、図7)**: 39.3% のジョブで最終 PP ステージが過半のスローダウン($M_S \ge 0.5$)を引き起こす(PP 不使用 21.1% は $M_S=0$ とする)。損失層が Transformer 層より重い(9 層構成ジョブでロジット計算が Transformer 層の 9 倍超、最終ステージの forward/backward-compute が平均ステージの 2.07/1.41 倍)。Llama 3 と同様に最終ステージへ層を $\varepsilon$ 減らす対策を使うが手動チューニングが難しく、手動分割でも 9.9% 高速化(最終ステージ forward-compute がなお 1.55 倍)にとどまる。 - **シーケンス長不均衡(§5.3、図8〜12)**: forward-backward 相関 ≥0.9 を閾値に、21.4% のジョブが影響、平均スローダウン 1.34。self-attention の計算量が $O(\sum s_i^2)$ のため、マイクロバッチ内シーケンス長のばらつきが計算時間のばらつきに直結(図9 で線形性を実証)。最大シーケンス長が大きいほど深刻(図12)。**緩和策**: 多方向数分割問題として貪欲法でシーケンスを再分配し $\sum s_i^2$ を均等化(DistTrain 類似)。32K 最大シーケンス長のジョブで **23.9% のスループット改善**(プロトタイプ)。DP レベルの不均衡は解消するが PP レベルの不均衡は残る。 - **Python GC(§5.4、図13)**: stop-the-world GC ポーズ(100ms オーダー)が forward-compute をブロック(backward-compute は C++ から launch されるため影響なし)。各 Python プロセスが別々のタイミングで GC を起こし、1 ワーカーのポーズがジョブ全体を止める。ワーカー数増加で悪化。**緩和策**: 自動 GC を切り、ユーザ指定間隔(ステップ単位)で全ワーカー同期して計画 GC を実行。128 DP ランクのジョブで 500 ステップごとの GC により **12.6% 改善**。ただし適切な GC 間隔の選定が難しく(大きすぎると OOM、小さすぎると低速)、既定では無効。GC ポーズはジョブ進行とともに増大(メモリリーク疑い)。 - **その他の根本原因(§5.5)**: CUDA メモリフラグメンテーション(cudaFree/cudaMalloc 増加で compute が低速化、稀)、false kernel dependency(reduce-scatter カーネルが無関係なカーネルの launch をブロック、`CUDA_DEVICE_MAX_CONNECTIONS` 増で緩和)。両者は既知の性能問題だが、ストラグラーの原因と判明したのは本研究が初。 - **シミュレーション忠実度(§6)**: シミュレートした元タイムラインの平均ステップ時間と実測の差は中央値 1.3%・p90 5.5%。人工的にストラグラーを注入した検証で、実測スローダウン 1.16/1.40/2.03 に対し推定 1.21/1.42/1.98。 - **SMon の実用効果(§8)**: NDTimeline プロファイリング後に自動実行され、ワーカースローダウンをヒートマップ(x=DP rank, y=PP rank、Pingmesh 類似)で可視化。根本原因ごとに固有のパターンを示す(図14: (a) ワーカー障害、(b) ステージ分割不均衡、(c) シーケンス長不均衡)。重要ジョブの大スローダウン時に on-call チームへアラート。展開初月に、ファールティマシン 3 件・シーケンス長不均衡 1 件・ステージ分割不均衡 1 件を検知・対処。 ## 考察 ストラグラーの主因が通信でなく計算であることは、ByteDance クラスタの広帯域ネットワーク(オーバープロビジョニング・内製最適化)が通信ボトルネックを事実上除去していることを示す。一方で Python ランタイムやアルゴリズム的不均衡(ステージ分割・シーケンス長)というソフトウェア起因の問題が支配的に残る。これは、従来のヘルスメトリクス(ハードウェア健全性チェック)では大半のストラグラーを検知・予防できないことを意味する。What-if 分析はシミュレーションベースであるため、ジョブを再実行せず反事実シナリオを評価でき、5 か月・3000 ジョブ超の実トレースに統計的に適用できる。 ## 強み - ByteDance 本番クラスタ(最大 5000+ GPU)の 5 か月実トレースに基づく高い実証的妥当性。FALCON が大規模ジョブ 27 トレースの手動分析にとどまるのに対し、562 ジョブが ≥512 GPU を使う大規模かつ半自動の分析。 - What-if 分析により、スローダウンを根本原因ごと(ワーカー・オペレーション種別・最終ステージ)に帰属・定量化できる。 - シーケンス長不均衡(23.9% 改善)・計画 GC(12.6% 改善)という具体的緩和策を提示。 - 分析パイプラインを SMon として本番展開し、初月に実障害を検知した実用性。 ## 弱点・課題 - TP/CP グループ内のストラグラーは NDTimeline の粗粒度プロファイリングでは分析不能(TP/CP の遅延は遅いマイクロバッチとして現れ、理想時間が推定できない)。 - GC 緩和策はジョブごとのパラメータチューニングが必要で、スケーラブルな自動化が未達。既定で無効。 - ステージ分割不均衡の根本解決(層単位の再分割の粒度制約、vocabulary size 増大との兼ね合い)は未解決。 - トレース取捨選択で 38.2% のジョブ・56.4% の GPU 時間しかカバーせず、ストラグラーの蔓延度・深刻度を過小評価しうる。 - ByteDance 特有の均質ハードウェア・広帯域・専用クラスタへの依存があり、ヘテロジニアス環境や輻輳ネットワーク下への外挿性は不明(FALCON の共有クラスタとは設定が異なり結論も異なる)。