HPCジョブスケジューリング（Slurm）

なぜHPCにはOSのスケジューラと別物が要るのか

一般的なOSのプロセススケジューラは、1台のマシン上でCPU時間をミリ秒単位に細かく切り替えて複数プロセスに割り当てます。HPCクラスタが解く問題はこれとは性質が違います。数百〜数万ノードという有限で希少な資源を、数分から数日かかる単一の並列ジョブにまとめて占有させ、ジョブが終わるまで横取りしない（あるいは慎重にしか横取りしない）運用が基本です。この役割を担うのが Slurm（Simple Linux Utility for Resource Management）に代表されるワークロードマネージャです。

Slurm の基本モデルは3層で理解できます。

ユーザー → sbatch/srun でジョブ投入
  ↓
キュー（パーティション単位、優先度付きの待ち行列）
  ↓
スケジューラが「いつ・どのノード群を・どのジョブに」割り当てるか決定
  ↓
ノード上で実際にジョブが実行される

パーティションはノード群を用途別に区切った論理グループ（例: GPUノード群、大容量メモリノード群）で、ジョブはどのパーティションに投げるかを指定します。スケジューラの核心は、キューに並んだジョブの中から次に実行するジョブと配置先ノードをどう決めるかというアルゴリズムにあります。

単純FIFOの破綻とバックフィルの原理

最も素朴な方式は厳格FIFO（First-In-First-Out）、つまりキューに入った順に実行する方式です。しかし大規模並列計算では、ジョブごとに要求するノード数と実行時間（walltime）がばらばらです。先頭に1024ノード・24時間のジョブが並んでいて、その資源が今は空いていないとします。厳格FIFOでは、後ろに並ぶ「4ノードで10分」の小さなジョブも、先頭ジョブの順番が来るまで一切実行できません。これがクラスタ全体の稼働率を落とすヘッドオブラインブロッキングです。

この無駄を解消するのがバックフィル（backfill）スケジューリングです。考え方は次の通りです。

バックフィルの判断ロジック（概念）

1. 先頭の大きいジョブJに対し、必要ノード数が揃う「予約開始時刻」を試算する
2. その予約開始時刻までの間に、他の空きノードで
   「実行してもJの予約開始を遅らせない」ジョブが後方にあれば先取り実行する
3. 条件: 後方ジョブの要求walltimeが、Jの予約開始時刻までの残り時間に収まること

ポイントは、後方ジョブを割り込ませても先頭ジョブJの開始予定時刻そのものは動かさないという制約です。これにより「早いもの順」という公平性の建前を壊さずに、空きノードの遊休時間を埋められます。Slurm ではこの方式を backfill スケジューラプラグインが実装しており、ジョブの申告walltimeの正確さがバックフィル可否を左右します。walltime を過大申告すると、実際にはもっと早く終わるジョブでも申告値のまま「隙間に収まらない」と判定され、本来入れられたはずのバックフィル枠を逃します。

公平性と効率のトレードオフ ── 優先度計算の設計

FIFO順やバックフィルだけでは「早い者勝ち」に偏り、大口ユーザーが資源を独占して他ユーザーが待たされ続ける不公平が起こり得ます。これに対処するため、Slurm の実運用では**マルチファクタ優先度（multifactor priority）**を使い、複数の要因を重み付き合成してジョブの優先度スコアを決めます。

とりわけ fair-share は公平性の核です。各ユーザー・グループには資源配分の目標比率（shares）が割り当てられ、実際の使用量が目標を超えているほど、指数減衰的に優先度が下げられます。これにより「直近で使いすぎた人は一時的に後回しにされ、使っていない人が優先される」動的な均衡が生まれます。

ここで効率と公平性は正面から衝突します。Fair-shareを厳格にするほど、資源使用実績の低いユーザーの小さなジョブが優先され、クラスタ利用率の面では最適でない配置が増えることがあります。逆にスループット最適化を優先すると、資源をうまく使い切れる大口ユーザーに有利になり、小口ユーザーの待ち時間が伸びます。運用者は重み係数の調整でこのトレードオフの位置を選び取っているのであって、唯一の正解があるわけではありません。

MPIジョブのノード配置とトポロジ考慮

スケジューラがジョブを「いつ」実行するかを決めても、「どのノードに」配置するかも性能に直結します。MPIジョブは全プロセスが頻繁に通信するため、選ばれたノード集合のネットワーク上の位置関係（トポロジ）が実効性能を左右します。

ノード間通信のコストは階層的に増大します。

通信レイテンシ・帯域の階層（同一クラスタ内、粗い目安の序列）

  同一ノード内プロセス間（共有メモリ）    最速・低遅延
  同一ラック内ノード間（同一スイッチ配下） 中程度
  ラックをまたぐノード間（上位スイッチ経由） 遅い
  離れたアイランド/モジュール間            さらに遅い

MPI集団通信（Allreduce等）や隣接通信主体のステンシル計算では、プロセス間の通信パターンが密であるほど、この階層差がそのまま実行時間に跳ね返ります。ノードがネットワーク的に散らばって割り当てられると、本来ノード内で完結できたはずの通信までスイッチを何段も経由し、レイテンシとスイッチの輻輳が積み上がります。

これに対応するため、Slurm は --switches オプションなどでジョブが要求するノード群を特定のスイッチ階層内に収める制約を指定でき、トポロジ情報（topology.conf 等でクラスタのファットツリー構成等を記述）を踏まえて同一スイッチ配下にまとまったノードブロックを優先的に割り当てる配置を試みます。これは「空いている最初のノードを適当に集める」割当と比べ、通信の局所性を保つ点で有利です。

この表が示す通り、トポロジを考慮した配置は通信性能を上げる代わりに、条件に合う空きブロックが揃うまで開始を遅らせるというもう一段のトレードオフを持ち込みます。強スケーリング（同じ問題を多ノードに分割し実行時間短縮を狙う運用、詳細は強スケーリング・弱スケーリングの分析を参照）を狙うMPIジョブほど、1ノードあたりの計算量が減って通信が相対的に支配的になっていくため、この配置の巧拙が測定される並列効率に直接表れます。実務では、ノード数が多く通信が相対的に支配的になりやすいジョブほどトポロジ制約を優先し、ノード数が少なく通信が局所化しやすい・計算が支配的なジョブほど早期開始を優先する、という使い分けが行われます。

まとめ

• Slurmはパーティション単位でノードを区切り、キューに並んだジョブへ優先度とバックフィルの2層で資源を割り当てる。
• バックフィルは先頭ジョブの予約を保全したまま隙間を埋める仕組みで、正確なwalltime申告があって初めて機能する。
• 公平性（fair-share）と効率（スループット最大化）はマルチファクタ優先度の重み設計として現れる、単一の正解がないトレードオフである。
• MPIジョブの性能はいつ実行されるかだけでなく、どのノードに配置されるかにも左右され、トポロジ考慮配置は通信性能と引き換えに待ち時間を延ばしうる。