# Themis : Fair and Efficient GPU Cluster Scheduling Navigation: [[GPUクラスタスケジューリング]] | [[GPUクラスタ運用]] | [[ネットワーク対応スケジューリング]] NSDI 2020 で発表された GPU クラスタスケジューリングの研究。複数ユーザーが GPU クラスタを共有するとき、既存の公平スケジューラは ML ワークロード固有の 2 特性——長時間ギャングスケジューリングと配置感度——を無視しているため公平性を達成できないことを示し、新たな公平性指標「仕上がり時間公平性(finish-time fairness)」とオークションベースの配分機構 Themis を提案する。(Source: `.raw/papers/nsdi20-paper-mahajan.pdf`) ## 背景と問題設定 ### ML ワークロードの特性 GPU クラスタを複数ユーザーが共有する環境では、DRF(Dominant Resource Fairness)や LAS(Least Attained Service)など確立したスケジューラが用いられてきた。しかし ML 訓練ジョブは次の 2 特性を持ち、これらの指標が公平性を保証できない。 1. **長時間タスクとギャングスケジューリング**: ML ジョブのタスクは中央値 3.75 時間と長く、全タスクを同時に走らせる必要がある。DRF はタスク完了時の空き資源を最小シェアのジョブに割り当てるが、タスク完了が稀なためリソース再配分の機会が少なく、後から到着したジョブが長時間待たされ共有インセンティブが著しく損なわれる。 2. **配置感度(placement sensitivity)**: モデルアーキテクチャによって、同一サーバ内配置を強く好むもの(VGG16: 4 GPU 同一サーバで 103.6 img/s 対 2 サーバ分散で 80.4 img/s)とほぼ無差別なもの(Inception-v3)が混在する。アプリケーションごとに配置感度が異なるため、同数の GPU を割り当てても性能が大きく異なり、嫉妬自由性やパレート効率性が損なわれる。 Microsoft の本番 GPU クラスタトレース分析から、ML アプリは約 10% が 1 ジョブ、約 90% がハイパーパラメータ探索(中央値 75 ジョブ)で構成され、中央値アプリ GPU 時間は 11.5 GPU 日、中央値タスクは 3.75 GPU 時間に達する。(Source: `.raw/papers/nsdi20-paper-mahajan.pdf` §2) ### 既存手法の問題の形式化 **定理 3.1**: 既存の公平スケジューラ(DRF、LAS)は、配置感度を無視するため、ML アプリに対する共有インセンティブ(SI)・パレート効率性(PE)・嫉妬自由性(EF)のすべてに違反する。 ## 提案手法 ### 仕上がり時間公平性(Finish-Time Fairness) 新たな公平性指標として **仕上がり時間公平性 r** を定義する。 $r = T_{\text{sh}} / T_{\text{id}}$ - $T_{\text{sh}}$: 共有クラスタでのアプリの仕上がり時間(配置劣化・キュー待ちを含む) - $T_{\text{id}}$: 独立した 1/N クラスタ(全資源を N 分割した個人専用クラスタ)での仕上がり時間 $r \leq 1$ であれば共有インセンティブを満たす。この指標は配置感度を $T_{\text{sh}}$ に自然に取り込み、長期間の公平性を測るため、ギャングスケジューリング必要性にも対応できる。(Source: `.raw/papers/nsdi20-paper-mahajan.pdf` §3.2) アプリの $r$ 推計には、アプリ自身が GPU 割り当てサブセットごとの $r$ 値を入札表(bid table)として提供する。スケジューラはこれを受け取り配分を決定する幅広いインターフェイスを用いる。 ### 部分割り当てオークション(Partial Allocation Auction) スケジューラ Themis の核心は**部分割り当てオークション(PA)**だ。入札の誠実な報告(方策確実性)を保証するため、PA は次の仕組みを使う。 1. **比例公平割り当て**: まず各アプリ $A_i$ に対して全アプリの評価関数積 $\prod_i 1/r_i(\vec{G}_i)$ を最大化する比例公平配分 $\vec{G}_{i,pf}$ を求める(PE 保証)。 2. **隠れた支払い(hidden payment)**: アプリ $A_i$ には比例公平配分の $c_i < 1$ の割合しか割り当てず、残りを隠れた支払いとして取り上げる。$c_i$ は「$A_i$ が参加することで他のアプリの集合評価がどの程度下がるか」に比例する(Pseudocode 1 参照)。これにより虚偽申告しても得にならず方策確実性(SP)が成立する。 3. **残余配分**: 隠れた支払いによる未割り当て GPU は、オークション不参加のアプリにランダムに配分し、ワーク保全性を確保する。 **定理 3.2**: 一回限りの PA は SP・PE・EF を保証するが SI は保証しない(隠れた支払いにより $r > 1$ になりうる)。(Source: `.raw/papers/nsdi20-paper-mahajan.pdf` §3.3) ### ラウンド繰り返しオークション SI を最大化するため、一回限りの PA をラウンドごとに繰り返す。 - **リース制**: 各 GPU にリース時間を設け(実験では 10 分が最適)、リース満了時に GPU を解放して再オークション。長時間タスクへのロックインを防ぐ。 - **ラウンドフィルタリング**: 各ラウンドでは現在の $r$ が最も悪い上位 $f$ 割のアプリのみをオークションに招く($f = 0.8$ が最適)。SI 違反に近いアプリを優先し、次第に SI を達成させる。残り $(1 - f)$ 割のアプリには未割り当て GPU をランダムに配分。 - **継続参加の自然な傾き**: オークションで敗れたアプリは $r$ が悪化し続けるため次ラウンドで参加する確率が上がる。長時間アプリは分母 $T_{\text{id}}$ が大きいため $r$ が緩やかに悪化し、短時間アプリの緊急性が高く評価される(利他的リソース放出)。 **定理 3.3**: ラウンド繰り返しオークションは PA の PE・EF・SP を保ち、SI を最大化する。(Source: `.raw/papers/nsdi20-paper-mahajan.pdf` §3.3) ## システム設計 ### 二層スケジューリングアーキテクチャ Themis は既存の 2 種のアーキテクチャを分析し、新しい「半オプティミスティック」設計を提案する。 | アーキテクチャ | 問題点 | |---|---| | 悲観的二層(Mesos 型) | 資源の可視性と割り当てが 1 アプリ単位で結びつき、複数アプリへの同時資源提示が不可能 | | 楽観的共有状態(Omega 型) | 可視性と割り当てが多アプリ同時に結びつき、大域的な公平性方策が実施しにくく高競合時に衝突解決コストが高い | Themis の **ARBITER** は中央の資源調停者として機能する。各 ML アプリには共置型 **AGENT** がおり、ARBITER-AGENT 間で次の 5 ステップを繰り返す。 1. ARBITER が全アプリに現在の $r$ 推計値を問い合わせる。 2. ARBITER が最も公平性の悪い上位 $f$ 割のアプリに資源の非拘束オファーを提示。 3. 各 AGENT が ARBITER に入札表(割り当てサブセットごとの $r$ 推計値)を返す。 4. ARBITER が PA アルゴリズムで落札者を決定し、各 AGENT に通知。 5. AGENT がアプリ内スケジューラ(ハイパーパラメータ最適化フレームワーク)に割り当てを伝える。 可視性(ステップ 1〜3)は多アプリ並列で行い、割り当て(ステップ 4〜5)は ARBITER が排他的に決定する「半オプティミスティック」制御。(Source: `.raw/papers/nsdi20-paper-mahajan.pdf` §4.2) ### AGENT と入札計算 AGENT は ARBITER から受け取ったオファーに対し、割り当てサブセットごとの $r$ を式(1)・(2)で推計し入札表を作成する。 - **単一ジョブアプリ**: 残りイテレーション数×イテレーション時間(配置スローダウン $S(\vec{G})$ を含む)で $T_{\text{sh}}$ を計算。$S(\vec{G})$ はオフラインプロファイリングで取得するか、同一サーバ/クロスサーバ/クロスラック 1.0/1.1/1.3 の初期推計値を使い逐次改善。 - **多ジョブアプリ(連続半減法 / 性能曲線停止)**: ハイパーパラメータ最適化の早期停止タイミングを見込んだフェーズ別 $T_{\text{sh}}$ を積算。HyperOpt・Hyperdrive・Google Vizier 等のフレームワークに共通する薄い API で計算値を収集。 (Source: `.raw/papers/nsdi20-paper-mahajan.pdf` §4.3) ## 実装 Apache Hadoop YARN 3.2.0 と Submarine フレームワーク上に実装。ARBITER は YARN Resource Manager の独立モジュールとして実装し、AGENT と gRPC でオファー・入札・落札通知を交換する。訓練プログラムは TensorFlow 製でハイパーパラメータ設定可能。割り当て変更時はモデルパラメータを HDFS にチェックポイントして最新状態から再開する。ARBITER の割り当て最適化には Gurobi を使用。(Source: `.raw/papers/nsdi20-paper-mahajan.pdf` §5) ## 評価 ### セットアップ - **実機テストベッド**: Microsoft Azure 上の 64 GPU、20 機クラスタ(NC12 × 8、2× Tesla K80; NC24 × 12、4× Tesla K80) - **シミュレータ**: 256 GPU 不均一クラスタ(16 台 8-GPU、6 台 4-GPU、16 台 1-GPU)のイベント駆動シミュレータ - **ワークロード 1**: Microsoft Philly トレースの 2 週間スナップショット(Hyperdrive ハイパーパラメータ探索ジョブ) - **ワークロード 2**: Workload 1 の到着時刻を再利用し、Hyperband の連続半減パターンでジョブを生成(タスク数を増加) - **モデル構成**: CV 10%(VGG16/AlexNet/ResNet50 等)、NLP 60%(GNMT/Transformer/Bi-Att-Flow 等)、Speech 30%(WaveNet/DeepSpeech) - **比較対象**: Gandiva(効率最大)・Tiresias(公平最大)・Optimus(総スループット最大)・SLAQ(集約モデル品質最大)・SRTF/SRSF(平均 JCT 最小) (Source: `.raw/papers/nsdi20-paper-mahajan.pdf` §6.1) ### 主要結果 - **公平性**: Themis は全ベースライン対比で最大仕上がり時間公平性指標 $r$ を 2.2〜3.25 倍改善。ワークロード 2 の実機実験では Tiresias の 2.25 倍以上の公平性を達成。 - **効率性**: GPU 総使用時間(同一ワークロード完遂に必要な GPU 時間の総量)はワークロード 1 で他スケジューラと同等、ワークロード 2 で Gandiva 比 4.8%、SLAQ 比 250% 改善。 - **配置スコア**: Themis はワークロード 2 で最良配置スコアを達成。Gandiva は貪欲な局所パッキング、Optimus は貪欲なスループット最大化のため大域最適に劣る。 - **競合増加の効果**: クラスタを半分・四分の一に縮小して競合を 2〜4 倍にすると Themis のみ SI を維持。他手法は急速に SI を違反。 - **推計誤差への耐性**: 入札値の誤差 ±20% でも最大 $r$ の変化は 10.76% 以内。 - **方策確実性の検証**: 1 アプリが意図的に虚偽申告(スローダウンを過大/過小報告)を行っても、PA の隠れた支払いにより虚偽申告者に利益が生じない。申告誤差が 34% を超えると隠れた支払いが急増し、リソースを大幅に失う。 - **システムオーバーヘッド**: AGENT の入札計算 中央値 29ms、95%ile 334ms。ARBITER の最適化計算 中央値 354ms、95%ile 1,398ms。割り当て変更のコンテナ追加・削減 中央値 35 秒。リース時間 10 分に対して無視できる水準。 (Source: `.raw/papers/nsdi20-paper-mahajan.pdf` §6) ### 感度分析 - **公平性ノブ $f$**: $f = 0.8$ が最大公平性と効率のバランス点。$f \to 1$ にすると公平性が逆に悪化(単一アプリのみオークションに参加し、配置制約により最適割り当てが不可能)。 - **リース時間**: 短いリースは公平性を高めるが、チェックポイント頻度と GPU 解放の頻度が増加してオーバーヘッドが増す。10 分が実用的最適。 (Source: `.raw/papers/nsdi20-paper-mahajan.pdf` §6.4) ## 関連研究との位置づけ - **DRF**(NSDI 2011): 瞬時公平性。タスク完了時に最小支配資源シェアのアプリに割り当て。長時間タスクと配置感度に対処できない。 - **Tiresias**(NSDI 2019): LAS(最低被サービス)方策でタスク長問題を緩和するが配置無視で PE・EF に違反。 - **Gandiva**(OSDI 2018): 内省的プロファイリングによる配置最適化と時間多重化。効率を優先し公平性を主目的としない。 - **Optimus**(EuroSys 2018): スループットスケーリング指標による資源配分。集約スループット最大化が目標で公平性は二次的。 - **Mesos**(NSDI 2011): 悲観的二層スケジューラ。Themis はリソースオファーの概念を継承しつつ多アプリ可視性を実現。 ## 関連 - ソース: [[@2024__NSDI__Cassini Network-Aware Job Scheduling in Machine Learning Clusters]] / [[@2019__USENIX ATC__Analysis of Large-Scale Multi-Tenant GPU Clusters for DNN Training Workloads]] - エンティティ: [[Aditya Akella]] / [[Amar Phanishayee]] / [[Shivaram Venkataraman]] / [[Kshiteej Mahajan]] / [[University of Wisconsin]] / [[Microsoft Research]] - 概念: [[GPUクラスタスケジューリング]] / [[GPUクラスタ運用]] / [[ネットワーク対応スケジューリング]] - 関連 MOC: [[分散深層学習 - MOC]] ## 出典 - `.raw/papers/nsdi20-paper-mahajan.pdf`(全文) - https://www.usenix.org/conference/nsdi20/presentation/mahajan