時間予測に特化したジョブスケジューラの研究

概要

人間は日常生活において予測可能性を求めている。自宅から職場までの通勤時間、Amazon の配送到着時間、Uber の到着時間など、様々な場面で「いつ完了するか」という情報を重視している．

クラウドコンピューティングにおいても同様の予測可能性を提供できないでしょうか？このような予測機能があれば、ユーザーは異なるクラウドプラットフォームやサービスを比較・選択する際の判断材料となり、SkyPilot のようなクラウド間ブローカーとの連携も可能になる。つまり、計算資源の選択における意思決定支援となる．

背景

クラウドジョブの完了時間予測の難しさ

クラウド環境でジョブの完了時刻を予測することが困難な理由は以下の通り：

• ハードウェア障害の可能性
• 共有リソースと専用リソースの運用の違い
• 各ジョブの特性や規模に関する情報不足

特に重要なのは、スケジューラが無制限のプリエンプション（実行中のジョブを中断して後着のジョブにリソースを譲る機能）を使用すると、ジョブ完了時間予測（JCTpred）の信頼性が大幅に低下すること．

現在のスケジューラは公平性や平均 JCT、締切対応のためにプリエンプションを多用している． その結果として予測可能性が犠牲になっている．

Humans desire predictability in their daily lives: from knowing how long their home-to-office commute will be to the arrival time of an Amazon package or an Uber ride.

人は日常生活で時間の予測を望んでいる．アマゾンがいつくるか，ウーバーがいつくるか，など． 予測可能性と性能・公平性の間にはトレードオフ関係がある． 既存の手法はこのトレードオフの両極端に位置している．

クラウドも同様の予測可能性を提供できるのか？という問いが生じる． このような予測は，ユーザが異なるクラウドプラットフォームや，クラウド内のサービスを比較・選択する手助けとなり，SkyPilot のような新興のクラウド間ブローカーと連携することもできる． つまり，どのクラウド計算資源を利用するかの意思決定支援になる．

クラウドにおけるジョブの完了時刻の予測が困難になる理由

• ハードウェアの故障
• 共有リソースと専用リソースの違い
• 各ジョブのサイズや特性の情報の欠如などである． 前提：クラウドのようにユーザごとに専用 GPU を割り当てるのではなく，スケジューリングによって共有される．

重要：スケジューラが無制限のプリエンプション（先に来たジョブを中断して後から来たジョブに資源を譲る） を使うと，完了時間予測（JCTpred）が信頼できなくなる．

プリエンプションを多用して公平性や平均 JCT，締切対応に適応しているが，その結果，ジョブの完了時刻が予測しづらくなっている．

予測性と性能・公平性との間にはトレードオフがある 既存の手法はその両極端に位置している．

予測性と性能公平性のトレードオフで，間の点をとるスケジュールを実現できないか？ またトレードオフから自由に運用者が選べないか？

提案

PCS：予測性と性能を両立させるアプローチ

重み付きフェアキューイング（WFQ）をベースに，予測性と性能をどちらも両立させる． キューに並ばせて重みで順番を変える WFQ（ダブルエフキュー）

なぜ時間予測が必要か？

時間予測は外しまくっているのが現状． 時間がわかれば，イライラもしないし，どのクラウドを使うのが向いているかがわかる． 大量に繰り返しジョブを投入する場合も，時間がわかった方が判断が取りやすい．

「それって，デッドラインスケジューリングでよくない？」

予測性（JCTpred）とデッドラインは根本的に異なる デッドラインはユーザが締切を提案するので，ユーザが責任を課す． そうするとユーザは貪欲になり，締切を厳しくする．その結果，公平なスケジューリングが崩れる．

ML のジョブは，事前にスループット（1 ステップあたりの時間）をプロファイルしておけば，安定して時間を予測しやすいという特徴がある．

プリエンプションの具体的なパターン

1. 優先度に基づく中断 　優先度の高いジョブが到着すると，現在実行中のジョブを一時停止したり，待機キューの順番を後ろに下げたりすることがある． 　これは平均 JCT の短縮やデッドライン対応のために用いられている（例：Tiresias, Chronus）．
2. 弾力的なシェアリング（Elastic Sharing） 　 GPU の割当を細かく分けて，多数のジョブを同時実行させる手法である．新しいジョブが来ると，既存のジョブの GPU 割当量が減らされる． 　リソース効率や公平性の向上のために使われている（例：Themis など）．

固定されたトレードオフ

FIFO では，後から来たジョブが前のジョブに影響を与えないため，完了時間の予測は 100%可能である． 予約方式でも同様に予測できるが，実際の GPU 利用率は下がる傾向にある．

しかし，こうした方式は以下のような性能問題を抱える：

• FIFO では「先頭の巨大ジョブ」が他のすべてのジョブをブロックしてしまう（HOL blocking）．
• 予約ベースでは，GPU が無駄になる時間が増えてしまい，資源効率が悪化する．

これらの方式は，調整（チューニング）によって予測性と性能のバランスを取ることができない． 固定されたトレードオフに縛られており，柔軟性に欠ける．

小さな例（図 1）を使って，3 つのスケジューラ（FIFO, Tiresias, Themis）の比較を行っている．4 つのジョブ（J1〜J4）を 1 つの GPU で順に処理する場合を想定し，以下の結果が得られた：

この比較から明らかなように，「予測性と性能・公平性の両立は難しく，現状の手法は極端に振れている」ことがわかる．理想的なスケジューラは，これらのトレードオフをバランス良く調整できるものである．

既存スケジューラの特徴

Tiresias

• 目的：ジョブの平均完了時間（JCT）を短縮することを重視したスケジューラ
• 特徴：
  • 優先度の高い（通常は短い）ジョブを優先的にスケジュールするプリエンプションを行う
  • すでに実行中のジョブがいても、新しい短いジョブが来ればそれを割り込ませる設計になっている
• 長所：
  • 平均 JCT が最も短い（全体の完了時間が早くなる）
• 短所：
  • 公平性は中程度（大きいジョブが不利）
  • JCT 予測が非常に困難で、最大 46%の予測誤差が発生

Themis

• 目的：公平性を最重視するスケジューラ
• 特徴：
  • 全てのジョブが同程度の待ち時間になるように設計されている
  • Elastic GPU Sharing（GPU を細かく分割して同時利用させる）などの手法も用いる
• 長所：
  • 公平性が最も高い（誰も損をしない）
• 短所：
  • 性能（JCT）は中程度
  • JCT 予測誤差は 24%程度とやや大きい（プリエンプションの影響）

PCS：提案手法の詳細

前章までより，プリエンプションが制限されており，公平性と性能，予測性のバランスを取ることができるスケジューラが必要である．

PCS は，高レベルの目標を受け取る「好み指定インターフェース（preference interface）」と，それを満たすような構成を見つけ出す「重み付きフェアキューイング（WFQ）」に基づいている．

1. Preference Interface

   • クラスタ運用者が「予測性重視」「性能重視」などの目標を指定できるインターフェース．

2. Preference Solver

   • 指定された目標に従って，WFQ の構成（キュー数，重みなど）を探索し，パレート最適な構成群（トレードオフの一覧）を返す．

3. WFQ ベースのスケジューラ

   • 構成済みの WFQ を用いて，実ジョブをスケジューリング．ユーザには JCT 予測（JCTpred）を返す．

PCS のパラメータ

以下の 3 パラメータを変更することにより、様々なトレードオフを実現できる。

1. キュー数（Number of Queues）

   WFQ における基本的な単位は「キュー」である。 キュー数が少なすぎると、異なる種類のジョブが同じキューに入り、干渉（interference）によって予測性が低下する。 一方、多すぎると、GPU の分割が細かくなりすぎてリソースの利用効率が下がる。 したがって、キュー数は予測性と効率のトレードオフにおいて重要なパラメータとなる。

2. キューへのジョブの割り当て（Queue Assignment）

   PCS は、ジョブの要求関数（demand function）に基づいてジョブをキューに割り当てる。 要求関数とは、「GPU 数とスループットの関係」を示す関数であり、ジョブが何枚の GPU でどの程度の性能が出るかを表す。

   要求関数が似ているジョブを同じキューに割り当てることで、同じようなスピードで進むジョブ同士が集まり、キュー内の予測が容易になる。 これは、キュー内の実行時間のばらつきを減らすという効果を持つ。

3. キュー重み（Queue Weights）

   各キューには、GPU リソースの割り当て量を決める重み（weight）が与えられる。 たとえば、全体で 8 枚の GPU があり、3 つのキューにそれぞれ(2:4:2)という重みが割り当てられていれば、それぞれのキューには(2 枚, 4 枚, 2 枚)の GPU が割り当てられることになる。

   重みによるリソース割り当てが明示的に管理されることで、キューごとのスループットが安定し、ジョブの完了時間の予測可能性が向上する。

PCS のアルゴリズム

1. トレードオフ空間の探索（Exploring the Tradeoff Space）

   まず、PCS は様々な WFQ 構成（異なるキュー数、割当方針、重み）をシミュレーション上で試し、それぞれにおける性能・公平性・予測性の値を評価する．

2. 好みによるフィルタリング（Filtering via Preferences）

   次に、クラスタ管理者（ユーザ）は、どのメトリクスを重視するか（例：予測誤差を最小化，公平性をある閾値以上に，など）を好み（preference）として指定する．

   PCS はこの好みに従って、探索済みの構成群から要件を満たすものだけを選び出す．

3. 実行時の JCT 予測とスケジューリング（Prediction and Scheduling at Runtime）

   最後に、選ばれた構成を用いて，WFQ ベースのスケジューラがジョブを実行する． 各ジョブの要求関数とキュー内状態に基づいて，JCT 予測（JCTpred）を生成し，ユーザに返す．

   スケジューリングは構成された WFQ に従って行われ、各キューの GPU 割当・ジョブ順序はあらかじめ決められた通りに実行される．

要求関数

たとえば、あなたが AI を学習させるときに、「GPU を 1 枚だけ使うと 10 時間かかるけど、2 枚使えば 5 時間で終わる。でも 3 枚にしても 4 時間ぐらいしか変わらない…」みたいなことがある WFQ のスケジューリングの下では，ジョブが要求する GPU 数に応じて，ジョブの実行速度（スループット）が変化する．

したがって，PCS においては，各ジョブが「GPU リソースの割り当てに応じて，どれだけのスループットが得られるか」を記述した関数，すなわち要求関数（demand function）を用いる．

この関数は，以下の 2 つの用途で利用される： 1. ジョブのキュー割当て（Queue Assignment）： 　 PCS は，要求関数が似ているジョブを同じキューに割り当てることで，キュー内でのスループットのばらつきを小さくし，予測性を高める． 2. JCT 予測（JCT Prediction）： 　ジョブが与えられた GPU 数と，その要求関数に基づき，完了に必要な時間（JCTpred）を予測する．

評価

この章では，次の問いに答える：

• Q1. PCS は予測性を改善できるか？
• Q2. PCS は性能・公平性と予測性の間でパレート効率的な構成を見つけられるか？
• Q3. PCS は実用的な環境でも動作するか？

PCS は，既存のスケジューラ（Tiresias，Themis，AFS）と比べて圧倒的に優れた予測精度を示した： • 予測誤差（Prederr）を最大で 50 ～ 800% 低減 • FIFO と比較しても，性能を保ちながら誤差 0%に近い予測が可能