Dynamic Core Allocation for Malleable Jobs with Unknown Speed-up Parameters

技術要約：未知の加速パラメータを持つ可変型ジョブのための動的コア割り当て

問題提起
本論文は、マルチコア・コンピューティング・システムにおける動的なリソース割り当て問題を取り扱う。対象となるのは「可変型（malleable）」ジョブのストリームである。到着時に割り当てられるコア数が固定される「成形型（moldable）」ジョブとは異なり、可変型ジョブは実行中に処理能力を動的に再分配することが可能である。システムは、固定された数の同一コア（$c$）と、2つの観測可能なジョブ・クラスで構成される。各ジョブ・クラスは、割り当てられた容量 $z$ と、並列化の度合いを規定する未知のパラメータ $p$ に基づく、独自の未知の加速関数 $s(z; p)$ によって特徴付けられる。

目的は、システム内の長期平均ジョブ数（言い換えれば、定常状態における平均応答時間）を最小化することである。ここには基本的なトレードオフが存在する。すなわち、より多くのコアを割り当てることでジョブの完了は加速されるが、収穫逓減（例：アムダールの法則）により、割り当てコアが増えるにつれて限界利得は減少する。パラメータが既知かつ固定されている場合、最適なポリシー（各クラス内での等分配分を行うEQUIポリシーと、マルコフ決定過程から導出されるクラス間の最適比率）は既知であるが、本論文は、パラメータ $p_1$ および $p_2$ が未知であり、運用データから学習しなければならないシナリオに対処する。このギャップは、進化するワークロードやハードウェアのアップグレードによって特性が変化し得る、大規模な機械学習のクラウドGPU上でのトレーニングといった現代のアプリケーションによって動機付けられている。

手法
著者らは、パラメータ推定とポリシー最適化を交互に行う、反復的な学習・制御フレームワークを提案している。

1. システムモデル:

   • ジョブはポアソン過程（レート $\lambda$）で到着する。サービス要件は指数分布（レート $\mu$）に従う。
   • ジョブはクラス1（確率 $\alpha$）またはクラス2（確率 $1-\alpha$）に属する。
   • 加速関数 $s(z; p)$ は、$z \le 1$ では線形であり、$z > 1$ では凹関数かつ非減少である。2つの特定のモデル（アムダールの法則およびべき乗則モデル $s(z; p) = \max\{z, 1\}^p$）が検討されている。
   • 割り当てポリシー $\pi$ は、現在のシステム状態 $(n^{(1)}, n^{(2)})$ に基づき、クラス1のジョブに割り当てられるコアの割合を決定する。各クラス内では、コアは等分に共有される（EQUIポリシー）。

2. パラメータ推定（最尤推定）:

   • 学習メカニズムの中核は、状態依存的な到着間隔に基づく最尤推定量（MLE）である。
   • 各クラスの到着プロセスは、状態依存的なポアソン過程としてモデル化される。瞬時の到着率 $\delta^{(i)}$ は、ジョブ数 $n^{(i)}$、割り当てられたコア $c^{(i)}$、および未知のパラメータ $p_i$ に依存する。
   • 最尤法は、到着間隔を、システム状態（およびそれに伴う到着率）が一定に保たれる部分区間に分解することによって構築される。対数尤度は、観測された到着時刻とシステム状態のシーケンスの関数として明示的に導出される。
   • 著者らは、固定された割り当てポリシーの下で、これらのMLEが（観測される到着数が増加するにつれて）強一致性（真のパラメータにほとんど確実に収束すること）を持つことを証明している。この証明は、キューイングシステムの再生構造と、加速関数の $p$ に関するリプシッツ連続性に依拠している。

3. ポリシー最適化（MDP）:

   • パラメータが推定された後、マルコフ決定過程（MDP）のベルマン最適方程式を解くことで、最適な割り当てポリシーが計算される。
   • 状態空間は、各クラスのジョブ数によって定義される。アクション空間は、クラス1に割り当てられるコアの割合である。
   • コスト関数は、システム内の総ジョブ数である。MDPは、連続時間プロセスを離散時間相当に一様化した後、値反復法を用いて解かれる。

4. 学習アルゴリズム:
   論文では、このループを実装する2つの具体的なアルゴリズムを提案している。

   • アルゴリズム 1a: 直近の観測ウィンドウ（固定された到着数 $N_k$ で定義される）中に収集されたデータのみを使用して推定値を更新する。これにより、パラメータが変化する可能性のある非定常環境への適応が可能になる。
   • アルゴリズム 1b: 時刻 $t=0$ 以降に蓄積されたすべてのデータを使用して推定値を更新する。これは通常、定常的な設定においてより速い収束と高い精度をもたらすが、変化するパラメータへの適応性は低い。

主な貢献

• 可変型ジョブモデルの拡張: 本論文は、加速関数が既知であるという仮定を超え、未知の加速パラメータを学習するメカニズムを導入することで、古典的な可変型ジョブのコア割り当てモデルを拡張した。
• キューイングシステムにおける統計的推論: 状態依存的な到着間隔を用いて並列化特性を推定するための特定のMLE手順を開発し、固定ポリシー下での強一致性を証明した。
• 統合学習フレームワーク: 統計的推定と動的計画法ベースのポリシー更新を組み合わせた、2つの反復アルゴリズム（1aおよび1b）を提案し、分析した。
• 数値的検証: 広範な数値実験を通じて、提案手法が正確なパラメータ推定を実現し、比較的短い観測期間の後に準最適なシステム性能を達成することを実証した。また、並列化の度合いが低い（低い $p$ を持つ）ジョブのパラメータ推定は、高度に並列化されたジョブよりも困難であるという「準識別性（quasi-identifiability）」の問題を明らかにしている。

結果

• 収束: 数値実験により、推定値が真のパラメータに収束することが確認された。定常的な設定では、全データ履歴を使用するため、アルゴリズム1bは1aよりも速く収束する傾向がある。
• 適応性: パラメータが特定の時点で行き先を変える非定常実験において、アルゴリズム1aは進化するパラメータを追跡し、それに応じて割り当てポリシーを調整することに成功し、動的な環境における有用性を示した。
• 性能: 学習されたポリシーは、真のパラメータが最初から既知であった場合に達成される理論的最適値に近い平均応答時間を達成する。
• 推定の非対称性: 結果は、並列化の度合いが低い（より小さい $p$ を持つ）クラスのパラメータを推定することは、加速関数がコア割り当ての変化に対して弱い感度を持つ領域であるため、本質的に困難であり、収束が遅いことを示している。

意義
本論文は、加速関数が既知かつ静的であるという仮定に対処することで、その意義を主張している。パラメータをオンラインで学習するフレームワークを提供することで、リソース効率が極めて重要でありながらシステム特性が不確実な、現代の動的なコンピューティング環境（クラウドベースのAIトレーニングなど）に対する実用的な解決策を提示している。著者らは、本フレームワークが高次元のシステムに対しても自然に拡張可能であることを述べているが、関連するベルマン方程式を解くための計算量は大幅に増加するため、モデルの表現力と計算の実行可能性（トラクタビリティ）の間のトレードオフを強調している。本研究は、非定常な設定、一般的なサービス時間分布、およびスケーラブルな近似手法への将来の研究に向けた基礎を築くものである。