# トポロジ考慮型スケジューリング ## 定義 トポロジ考慮型スケジューリング(Topology Aware Scheduling、TAS)は、データセンターの物理的な階層構造(ラック・ブロック等)をノードラベルの規約として表現し、ワークロードの Pod をできるだけ近接したノード集合へ配置することで Pod 間通信帯域を最適化するスケジューリング手法である。[[Kueue]] の実装([[@2024__KEP__KEP-2724 Topology Aware Scheduling]])は、管理者が `Topology` CRD でラベルの階層(最大 8 レベル)を宣言し、ユーザーが PodTemplate アノテーションで「必須(required)」「優先(preferred、満たせなければ段階的に上位レベルへ緩和)」「制約なし(unconstrained)」のいずれかを要求する 2 層 API を採る。同じラベル値がグローバルに一意である必要はなく(異なる block に同名の rack があってもよい)、階層構造はあくまでノード集合の相対的な近接関係を表すためだけに使われる。(Source: [[@2024__KEP__KEP-2724 Topology Aware Scheduling]]) ## 横断的知見 - **割当は必ず階層の最下位レベル単位で確定させる、という設計制約がレース条件を防ぐ**: TAS は PodSetAssignment を常にトポロジの最下位レベル(例: rack)で確定させる。これは、block 単位で割り当てた別ワークロードが実際には 2 rack にまたがって kube-scheduler にバインドされ、その後 rack 単位で要求する別ワークロードが「空きがある」と誤判定されて実際にはスケジュールできない、というレース条件を防ぐための決定である。この制約は `TopologyAssignment` のデータ構造設計全体(v1beta1 の `Domains` リストも v1beta2 の `Slices` 圧縮表現も)を貫く前提になっている。(Source: [[@2024__KEP__KEP-2724 Topology Aware Scheduling]]) - **配置アルゴリズムの選択(BestFit/LeastFreeCapacity/BalancedPlacement)は、単なる実装詳細ではなく通信パターンとの適合性の問題である**: BestFit は空き容量の多いドメインから優先しつつ最後のドメインだけ最適化する貪欲法、LeastFreeCapacity は逆に空きの少ないドメインから優先して埋める。両者とも「求められた Pod 数を収める」ことだけを目的とするため、all-to-all 通信(Allgather 等)のような GPU 間通信パターンでは、収まりはしても偏った配置(例: 容量 10・10 のドメインに 12 Pod を (10, 2) で配置)がクロスドメイン通信を増やす。BalancedPlacement は隣接 2 レベルに限定してこの偏りを避け、可能な限り均等に分配することで通信効率を優先する。単一の「最適配置」アルゴリズムは存在せず、ワークロードの通信パターンに応じてアルゴリズムを選ぶ必要がある。(Source: [[@2024__KEP__KEP-2724 Topology Aware Scheduling]]) - **ノード障害からの回復戦略は、ワークロードの所有構造(誰が Pod を再作成できるか)に応じて分岐する**: JobSet・LeaderWorkerSet のように Workload のコントローラが Pod を再作成できる構造では、失敗ノードを検知して新しい割当を計算し直す再割当が有効に機能する。しかし bare pod・Deployment レプリカのように Workload が単一 Pod と運命を共にする構造では、Workload 自体が Pod と一緒に削除されるため、計算し直した割当を消費できる将来の Pod が存在しない。この場合に再割当を行うと、実際にまだ Pod が動いているノードを「空き」として誤って会計し(過剰 admission)、かつ新しい割当先ノードを他のワークロードから奪ってしまう(二重の会計破損)。`SkipReassignmentForPodOwnedWorkloads` はこの構造的な違いを feature gate で明示的に切り分けている。(Source: [[@2024__KEP__KEP-2724 Topology Aware Scheduling]]) - **決定論的な配置アルゴリズムは、通常のクォータスケジューリングより桁違いに高い頻度でスケジューリングサイクル内の競合を起こす**: Kueue のスケジューリングは nomination(各 Workload を独立評価)→ evaluation(順に実際の admission)の 2 段階を取るが、通常の ResourceFlavor が「大きな資源プール」であるのに対し TAS は個々のノード単位の決定論的配置(主に BestFit)を行うため、先に evaluation された Workload がトポロジ容量を消費してしまい、後続の Workload が nomination 時には fit していたのに evaluation 時には fit しなくなる衝突がずっと頻繁に起きる。この差は「粒度が細かく決定論的なスケジューリングほど、2 段階評価アーキテクチャの整合性コストが上がる」という一般的な教訓を示しており、実際に多数の ClusterQueue を持つ環境で Workload が数時間 suspended のまま停滞する障害を引き起こした。(Source: [[@2024__KEP__KEP-2724 Topology Aware Scheduling]]) - **ProvisioningRequest との統合は、「予約」と「配置確定」を意図的に分離する 2 パス設計を要求する**: Cluster Autoscaler がまだ存在しないノードを準備している段階では、TAS はトポロジ割当を計算できない(対象ノードのラベル値が未確定なため)。Kueue はここで quota だけを予約し、AdmissionCheck が Ready になった時点で "second pass" として TAS 割当を計算するという 2 段階構成を取る。これは KEP-4381 の DRA が「デバイスの割当」という別軸の資源要求を扱うのと対照的に、TAS が「まだ存在しない資源(将来のノード)への配置制約」という時間軸の問題を抱えていることを示す。(Source: [[@2024__KEP__KEP-2724 Topology Aware Scheduling]]) - **[[GPUクラスタスケジューリング]] が扱う局所性(locality)の問題意識を、Kubernetes ネイティブな宣言的 API として体系化したものと位置づけられる**: [[Philly]]([[@2019__USENIX ATC__Analysis of Large-Scale Multi-Tenant GPU Clusters for DNN Training Workloads]])は局所性制約を待ってから緩和する運用上のヒューリスティックとして局所性を扱い、[[HiveD]] はセル階層による事前予約(Virtual Private Cluster)で共有異常を防いだ。TAS はこれらの問題意識を、ノードラベルという Kubernetes ネイティブな抽象化の上に、required/preferred の 2 段階要求・多層スライス制約・BalancedPlacement という具体的な API とアルゴリズムの集合として実装した後発の取り組みと読める。ただし TAS は単一ワークロードの配置制約に閉じており、HiveD の VC 抽象が扱う「テナント間の階層的な予約保証」までは踏み込んでいない。(Source: [[@2024__KEP__KEP-2724 Topology Aware Scheduling]], [[GPUクラスタスケジューリング]]) - **トポロジ考慮型スケジューリングの原型は、Kubernetes以前にHPC単一クラスタのグラフマッピング問題として定式化されていた**: [[@2017__SC__Topology-Aware GPU Scheduling for Learning Workloads in Cloud Environments]](SC17)は、KEP-2724のTASに7年先行し、ジョブの通信要求グラフと物理GPUトポロジグラフ(Network→Machine→Socket→GPUの階層、TASのラック/ブロック階層に相当)を二部グラフマッピングする点で問題の骨格が同一である。ただしTASがノードラベルという宣言的APIで「必須/優先」の2層要求を表現するのに対し、SC17論文は通信コスト・同居干渉・資源断片化の3項を単一の効用関数(式2)に重み付き結合し、Fiduccia-Mattheysesベースの再帰的二分割で最適化する点でより古典的な組合せ最適化のアプローチを取る。TASが「配置か否か」の宣言的制約を扱うのに対し、SC17は効用値そのものを最適化目標にしており、配置アルゴリズムの設計思想(宣言的制約 vs. 効用関数最適化)という軸で両者は対照的である。(Source: [[@2017__SC__Topology-Aware GPU Scheduling for Learning Workloads in Cloud Environments]], [[@2024__KEP__KEP-2724 Topology Aware Scheduling]]) - **同居干渉(interference)は、局所性(通信コスト)や断片化と並ぶ独立した最適化項として扱われるべきである**: SC17論文は、通信集約的な小バッチジョブを2つ同居させると単独実行比で最大約30%のスローダウンが生じることを実測し、干渉度(I、式4)を効用関数の独立した項として組み込んだ。TASのKEPは配置制約(required/preferred)と障害回復戦略を扱うが、同居ジョブ間の性能干渉を効用として明示的に定量化する仕組みは持たない。GPU間通信最適化に特化したスケジューラでは、「どこに置くか」(局所性)だけでなく「何と同居させるか」(干渉)を独立変数として持つ必要があることをSC17論文の実測が裏付けている。(Source: [[@2017__SC__Topology-Aware GPU Scheduling for Learning Workloads in Cloud Environments]]) - **配置を保留する(postpone)ポリシーは、待ち時間を悪化させるという直感に反して待ち時間自体を改善しうる**: SC17論文のTOPO-AWARE-Pは、効用が閾値未満のジョブを次のスケジューリング周期まで配置保留するが、プロトタイプ評価では即時配置するTOPO-AWAREより待ち時間を含めた総合スローダウンで優れた(良い配置により先行ジョブが早く完了し、後続ジョブの配置余地が早く生まれる連鎖効果)。これは、TASのProvisioningRequest統合が「予約」と「配置確定」を2パスに分離する設計判断や、Kueueのnomination/evaluation 2段階アーキテクチャとも通じる、「即時性を犠牲にしてでも配置の質を上げる方が結果的にスループットを改善する」という一般的な教訓を示す。(Source: [[@2017__SC__Topology-Aware GPU Scheduling for Learning Workloads in Cloud Environments]], [[@2024__KEP__KEP-2724 Topology Aware Scheduling]]) ## 未解決の問い - SC17論文の効用関数ベースの最適化(通信コスト・干渉・断片化の重み付き結合)と、KEP-2724 TASの宣言的制約(required/preferred)は、単一のスケジューラ設計に統合できるか。効用関数を宣言的APIの背後の実装として使う設計はあり得るか。 - HiveD の Virtual Private Cluster(テナント間の階層的予約保証)と TAS の required/preferred アノテーション(単一ワークロードの配置制約)を組み合わせたとき、マルチテナント環境での共有異常はどこまで防げるか。TAS 単体ではテナント間の予約保証までは扱わない。 - BalancedPlacement は現状 2 隣接レベルにのみ適用される制約を持つ。多層トポロジ制約(`PodsetSliceRequiredTopologyConstraints`)と組み合わせたとき、3 層以上にわたる均等配置はどう定式化されるか。 - スケジューリングサイクル内競合(`TASRecomputeAssignmentWithinSchedulingCycle` が修正した問題)は、TAS 以外の「粒度が細かく決定論的な」将来のスケジューリング拡張(例: DRA のデバイス単位割当)でも同種の問題を再発させるか。 - [[Dynamic Resource Allocation (DRA)]] の `pcieRoot`・`pciBusID` 標準属性によるノード内トポロジ(NUMA/PCIe)整合と、TAS のノード間トポロジ(ラック/ブロック)整合は、現状別々の API・別々の KEP で進んでいる。両者を単一の階層(ホスト内 PCIe ルート → ホスト → rack → block)として統合的に表現する将来設計はあり得るか。 ## 関連 - ソース: [[@2024__KEP__KEP-2724 Topology Aware Scheduling]] / [[@2017__SC__Topology-Aware GPU Scheduling for Learning Workloads in Cloud Environments]] - エンティティ: [[Kueue]] / [[Kubernetes]] / [[Marcelo Amaral]] - 概念: [[GPUクラスタスケジューリング]] / [[Dynamic Resource Allocation (DRA)]] ## 出典 - [[@2024__KEP__KEP-2724 Topology Aware Scheduling]](KEP全文。API・配置アルゴリズム・ノード障害対応・ProvisioningRequest統合・スケジューリングサイクル内再計算) - [[@2017__SC__Topology-Aware GPU Scheduling for Learning Workloads in Cloud Environments]](§3 Pack vs. Spread実測、§4 TOPO-AWARE/TOPO-AWARE-Pアルゴリズムと効用関数、§5 プロトタイプ・大規模シミュレーション評価)