飢餓を決めるのは平均ジョブ幅ではなく、クラスタ全体を要するジョブが1本でもあるかどうか

GPUクラスタのスケジューリング飢餓を引き起こす原因を切り分けるEnglish

この結論は後の研究で条件付きになり、判定器も置き換わりました

「需要分布のsupportがクラスタ全体を含むと飢餓する」は、EP-0008で同時実行ジョブ数に条件付けられた主張に書き換えられました。同じ確率・同じプール・同じ負荷のまま背景の粒度だけを変えると、飢餓は流量0.307から0.997へ消えます。supportは原因ではなく代理変数でした。さらに飢餓の判定に使っていた統計量そのものがEP-0011で無効と判明し、EP-0012で置き換えられています。機構の2×2分離（サイズ優先＋貪欲な詰め込みの組み合わせだけが壊れる）は有効です。

この記事が出した運用規則は、後に取り下げました。 EP-0004が2つの公開トレースの需要分布を測り、Phillyのどの仮想クラスタにもプールを占め切るジョブが来ていないことを示したためです。この記事が要求する前提は、実測データでは満たされていません。「クラスタ全体を要するジョブが来るか確認せよ」という規則は取り下げ、プール容量に対する比の判定に置き換えました。EP-0004は、この記事が自分で挙げた反証条件も満たしています。下に書いた仕組みそのものはモデルの中では変わらず成立します。狭まったのは、それが届く範囲です。 この記事は2026-09-13時点で何を主張したかの記録として、書き換えずに残します。

現在わかっていること

前の2本の研究の結果が食い違っていました。EP-0001では、平均ジョブ幅3.26で最大ジョブがクラスタの半分を要する構成で、greedy SRPTが勝ちました。EP-0002では、平均ジョブ幅がより小さい2.37なのに、クラスタ全体を要するジョブを含む構成で、greedy SRPTがそのクラスを飢餓させました。平均は逆を指しています。

そこで平均ジョブ幅を4.076に固定し、分布の届く範囲だけを変えました。結果は正反対でした。 最大ジョブがクラスタの半分で頭打ちになる構成は安定します（最も遅いクラスの平均JCT 3.31）。同じ平均で、クラスタ全体を要するジョブを3%含む構成は飢餓します（最も遅いクラスの平均JCT 655.7）。決めているのは平均ではなく、分布がクラスタ全体まで届いているかどうかでした。

必要な比率は驚くほど低く、30,000本中15本（0.0005）で十分です。さらに、優先度規則と充填規則を2×2で組み合わせて調べると、失敗にはサイズ優先と貪欲な詰め込みの両方が必要でした。どちらか一方だけでは起きません。preemptionは原因ではなく、むしろ害を和らげる側に働きます。

したがって当時の運用上の読み方は、「大きいジョブが何%あるか」ではなく「クラスタ全体を要するジョブが1本でもあるか」になりました。ただし上の通り、この規則はEP-0004で取り下げています。

図で見る

この研究が示すこと

• 指定したモデルの中では、平均ジョブ幅ではなく「分布がクラスタ全体まで届いているか」が2つの結果を分ける。
• 優先度規則と充填規則の2×2は、失敗の原因をサイズ優先と貪欲な詰め込みの組み合わせに局在させる。preemptionはわずかに害を和らげる。

この研究が示さないこと

• 運用トレース上での飢餓は示しません。また、ジョブがプールの1/2を超えて全体未満という範囲での飢餓も示していません。
• 「クラスタ全体を要するジョブの有無を確認せよ」という運用規則は、EP-0004の後に取り下げました。

なぜ重要か

「大きいジョブが多いワークロードは素朴なスケジューラを壊す」は比率についての言明で、容量計画の対応を促します——大きいジョブの比率を監視せよ、と。しかし本当の引き金がクラスタ全体を要求するジョブクラスの存在であるなら、運用上の規則は別物で、はるかに鋭くなります。問うべきは何本あるかではなく、1本でもあるかどうかです。

監視すべき対象も変わります。全体の平均が異常に気づけなくなるのは、まさにクラスタ全体ジョブが希少な領域であり、そこは見落としが最も起きやすい領域でもあります。

何を調べたか

1. クラスタ全体を要するジョブの飢餓を引き起こしているのは、平均ジョブ幅か、それとも必要GPU数の分布がクラスタ規模Nまで届いていることか。
2. その飢餓は、サイズ優先によるのか、貪欲な仕事保存によるのか、両方が揃ったときだけか。

方法

必要GPU数1〜32への重みは theta = 0.4 の形を保ったまま 1 - p64 へ正規化し、残りの確率質量 p64 を、64サーバのクラスタで必要GPU数64のところへ置きます。変わるのは分布の届く範囲だけです。

対照群の形状パラメータは数値解で求め、平均ジョブ幅が p64 = 0.03 の構成と一致するようにしました。飢餓が平均を追うなら、対照群も飢餓しなければなりません。

仕組みを切り分ける要因計画は、優先度規則と充填規則を交差させます。greedy SRPT（サイズ優先・貪欲充填）、ServerFilling-SRPT（サイズ優先・厳密充填）、FCFS（到着順・貪欲）、ServerFilling-FCFS（到着順・厳密）、加えてEASY backfill（到着順＋予約）と、preemptionを使わないgreedy SRPT。負荷2点、シード5本、30,000ジョブ、全セルで120,000ジョブの観測長を確認しました。432回の実行です。

予測はSHA-256 2f3b1808d806e9af888acaa77a7e00f7e9af86a13d58e42ac75e514a91157d05 で封印し、結果ファイルが存在しない状態でコミットしました。前の研究の教訓を踏まえ、安定性の判定器そのものを封印ファイルの detector に書き込んでいます。

結果

平均を揃えた対照群が決着をつけます。 平均ジョブ幅は同じ、結果は逆です。

必要な比率は非常に低い。 p64 = 0.0005、すなわち30,000本中15本のクラスタ全体ジョブで、greedy SRPTは両方の負荷で既にそのクラスを飢餓させます。64 GPUクラスの平均JCTは312.5、EASY backfillは5.40、ServerFillingは1.21です。

壊れるのは組み合わせだけ。 rho 0.85での64 GPUクラスのflow balanceです。1.0は、到着と同じ速さで完了していることを意味します。

サイズ優先だけでは飢餓せず、貪欲充填だけでも飢餓しません。両方揃うと飢餓します。想定される仕組みはこうです。クラスタ全体を要するジョブは、残り時間が全体で最小になったときにしか開始できません。ところがその残り時間は決して減りません——走らないからです。到着順の優先度は、先頭ジョブが後続を止めることでクラスタが空くため、この罠を逃れます。厳密充填は、大きい順に詰めることで最大ジョブに枠を確保するため逃れます。

遅延は「大きい」のではなく「上限がない」。 観測長を4倍にすると、飢えているクラスの平均JCTは2.83倍になり、1 GPUクラスは1.02倍にとどまります。

preemptionは原因ではありません。 preemptionを使わない版のほうが悪く、flow balanceはちょうど0.000です。到着が続く間、クラスタ全体ジョブは1本も完了しません。preemptionは、いったん先頭に到達しさえすればクラスタを掌握できるため、害を和らげる側に働きます。

全体指標が気づけない範囲には境界があります。 greedy SRPTとEASY backfillの平均JCT比は、p64 が0、0.0005、0.002、0.008と進むにつれて0.756、0.800、0.982、1.695と動きます。p64 = 0.002 では比0.982で、健全な方式と区別がつきません。しかしクラスタ全体クラスは63倍悪化しています。p64 = 0.008 になると全体指標にも現れます。つまりこの指標は、問題のクラスが希少であるうちだけ気づけません。

何が変わったか

EP-0002は「分布がNまで届いていること」を仮説として提示しました。平均を揃えた対照群によって、これは切り分けられた結果になりました。運用上の読み方も、比率から「あるか／ないか」へ変わります。問うべきは、クラスタ全体を要するジョブが何本あるかではなく、1本でもあるかどうかです。

さらに2点あります。preemptionは「悪化要因の疑い」から「害を和らげる要因の実証」へ移りました。そして「全体指標はクラスの飢餓を見ない」という主張には条件が付きました——そのクラスが希少である間に限る、という条件です。

何が失敗したか

封印した10本のうち3本が外れました。

R10は際どいところで落ちました。完了率は1.000、中断もなく、flow balanceは観測長とともに改善しています。閾値を後から動かさなかったので、外れとして残します。

解析上の欠陥を1つ、結果を見た後に直しました。採点が厳しくなる方向です。観測長の比較が当初、単一シードの長時間実行を5シードの短時間平均で割っており、シード間の変動が成長率に混入していました。現在は同一シード同士で比較します。R10の判定は変わりませんでした。

証拠の範囲

言えること： このシミュレータとこれらの需要構成の下で、貪欲なサイズ優先スケジューリングにおけるクラスタ全体ジョブの飢餓が、需要分布の平均ではなく「届く範囲」に従うこと。クラスタ全体ジョブの比率0.0005で現れること。サイズ優先と貪欲な仕事保存の両方を要すること。preemptionが原因ではなく、害を和らげる側に働くこと。

言えないこと： 運用クラスタについての主張。必要GPU数の格子は2のべき乗なので、「クラスタの半分」と「クラスタ全体」の間（33〜63）は検証していません。再実行コストは0、サービス時間は指数分布です。実トレースは使っておらず、そもそも実在のGPUクラスタにクラスタ全体ジョブのクラスが存在するのか——この発見が実務上意味を持つための前提——は、ここでは検証していません。

まだ分からないこと

• 閾値がちょうど必要GPU数 = Nなのか、N/2より上のどこかから始まるのか。格子上には32と64しかありません。
• 再実行コストが0でないとき、preemptionによる緩和が消えるか。
• サービス時間が重い裾を持つとき、全体指標が気づき始める比率が変わるか。
• preemptionを使わない版が同じ理由で飢餓するのか、単に中断できないためか。
• 実トレースの需要分布。最優先の未解決項目で、PhillyやAlibaba PAIにおけるクラスタ全体ジョブの比率は、0.0005という閾値と直接比較できます。

この結論が崩れるとき

• 独立に実装したシミュレータで、平均を揃えた対照群が飢餓する。その場合、平均ジョブ幅が原因として復活します。
• クラスタ全体ジョブを含む構成が、いずれかの負荷でgreedy SRPTのもと安定に動く。
• 観測長をさらに延ばすと、飢えているクラスのJCTが収束する。
• ServerFilling-FCFSまたはFCFSがクラスタ全体クラスを飢餓させる。その場合、優先度と充填の切り分けが崩れます。
• 公開トレースにクラスタ全体ジョブのクラスが存在しない。その場合、この発見はモデルについては真だが、実務には無関係ということになります。これは実際に起きました。EP-0004を参照してください。

自分で確かめる

データと採点の簡易確認

python -m pip install -r requirements-reproduce.txt
python scripts/reproduce.py --quick gpu-phase

完全な再実行

cd reproduction/gpu-scheduling-phase
python run_e4.py
python analyze_e4.py

run_e4.py は全セルで120,000ジョブの観測長確認を含むため、裁定していない仮定に依存する判定はありません。

証拠とデータ

• 公開再現パッケージ
• 封印済みPRED-003（判定器を含む）
• E4の採点
• E4のレポート（平均を揃えた対照群を含む）
• 内部の元Episodeのハッシュ：ca6a566b0396730d61e2ec33a48c5cfd1a12b6246dcd2a43e5e03f067b0ff3de

外部からの検証

• 独立再現：0
• 再現失敗：0
• 公開後に確認されたbug：0
• 未解決の批判：0

次の実験

公開されている運用トレースで、クラスタ全体ジョブの比率を測ります。Blox経由のPhilly、Kubernetesスケジューラシミュレータ経由のAlibaba PAIで、0.0005という閾値と比較します。それが済むまで、この発見はモデルを記述しているのであって、実在のクラスタを記述してはいません。副次的な実験として、2のべき乗の制約を外し、クラスタの半分と全体の間のどこに飢餓の境界があるかを特定します。

（この実験はEP-0004として実施され、上の運用規則を取り下げる結果になりました。）

ここに至るまで