When the Optimum Matters Less: Certified Near-Optimal Window-Count Selection for a Single ARINC-653 Partition

技術要約：単一ARINC-653パーティションにおける認定済み近最適ウィンドウ数選択

1. 問題定式化

本論文は、ARINC-653静的サイクルスケジュール（メジャーフレーム $H$）内の単一パーティションにおけるウィンドウ数 ($k$) の選択について扱う。パーティションにはフレームあたり総予算 $Q$ が割り当てられ、これは $k$ 個の等間隔なウィンドウに分割される。この決定には以下のトレードオフが伴う：

• 供給ギャップ（Supply Gaps）： $k$ を増やすと、最悪ケースの供給ギャップ（ジョブが再びパーティションを実行するまで待機する時間）が減少し、おおよそ $(H-Q)/k$ に比例して減少する。
• オーバーヘッド： 各ウィンドウはコンテキストスイッチのコスト $\delta$（状態の保存/復元、キャッシュ/TLBのリフィル）を伴う。したがって、$k$ 個のウィンドウはオーバーヘッドとして予算の $k\delta$ を消費する。

目的は、スケジューラビリティ（EDFまたは固定優先度ローカルスケジューリングの下での）を確保するために必要な最小予算 $Q_{min}(k)$ を最小化するウィンドウ数 $k^*$ を見つけることである。本論文では、以下の2種類の問題を区別している：

1. ポイント特定（Point Identification）： $Q_{min}(k)$ を最小化する正確な整数 $k^*$ を見つけること。
2. 集合認定（Set Certification）： 選定された候補 $\hat{k}$ が $\epsilon$-近最適集合 $W_\epsilon = \{k : Q_{min}(k) \le (1+\epsilon)Q^*\}$ （ここで $Q^* = Q_{min}(k^*)$）に属することを証明すること。

中心となる研究課題は、目的関数のランドスケープを考慮したとき、正確なポイント特定が必要なのか、それとも $\epsilon$-近最適集合への所属を認定することの方が十分かつ効率的なのかという点である。

2. 手法および解析的基礎

本研究では、周期リソースモデル（PRM）のような悲観的な抽象化ではなく、供給境界関数（SBF）に基づいた正確なスケジューラビリティ解析を用いている。

• 正確なSBF計算： 著者は、最小化するフェーズがウィンドウの終端で発生することを示す候補フェーズの結果（補題1）を導出している。これにより、整数グリッド上での $sbf_k(t)$ の正確な計算が可能になる。
• 残差を考慮した線形境界： 主要な解析的貢献は、ウィンドウレイアウトにおける整数残差効果を考慮した、SBFの線形下界（定理1）である。この境界は $sbf_k(t) \ge \alpha_k(t - \Delta_k) - r_k$ の形式をとり、$r_k$ は残差分布から導出されるスラック項である。
• 認定済み下界 ($L(k)$)： 本論文では、最小予算のための計算可能な必要性境界（定理2）を導入している。この境界 $L(k) = k\delta + L_0$（ここで $L_0$ は利用率と需要制約に依存する）は、$k$ のアフィン関数である。極めて重要なことに、これは正確なスケジューラビリティ解析を行うことなく、$O(|C| + |K|)$ の時間で計算可能である。
• デッドラインを考慮した精緻化： 標準的な容量境界がギャップによる予算膨張を捉えきれないタイトなデッドラインに対して、デッドラインを考慮した境界 $L_{dl}(k)$ を導入している（定理4）。この境界は、特定のデッドライン制約に対して正確なSBFに対して二分探索を行うことでブラックアウトギャップを正確に価格付けし、短デッドラインのタスクに対して境界を大幅にタイトにしている。
• 選択ワークフロー： 提案されるワークフローは、探索の初期化のために一次近似サロゲート（$Q_{lin}$）を使用し、次に認定済み下界を適用して候補集合を枝刈りする。これは、インカンベント（現時点での最良候補）の予算が、残りの候補の $\epsilon$-近最適条件を満たすまで反復的に候補のサイズを調整する。

3. 主な貢献

1. 目的関数の幾何学的特性： 論文では、400通りのタスクセット・オーバーヘッド条件下で最小予算のランドスケープを測定している。その結果、ランドスケープは「最適解の識別においてはギザギザしているが、目的関数の値においては平坦である」ことが判明した。最適解 $k^*$ はパラメータによって急激に変化するが、$\epsilon$-近最適集合はしばしば広く（例：$\delta=100\mu s$ において5%の許容誤差に対し、64個中の中央値は25個）、正確な特定は必ずしも重要ではない。
2. 近最適集合の統治： 近最適集合の幅は、主に相対的なウィンドウあたりのオーバーヘッド $\eta_\delta = \delta/Q^*$ によって支配される。高い相対オーバーヘッド、低い利用率、およびタイトなデッドラインは、「狭い集合」のレジームを生み出し、その場合は正確な選択が重要となる。それ以外の場合、集合は広く、正確な特定は重要性が低い。
3. 認定済み選択ワークフロー： 全探索を行わずに、インカンベントが $\epsilon$-近最適であることを認定するワークフローを提示している。これは、証明可能な妥当性を持つ下界と、少数の候補に対する正確なサイジングに依拠している。
4. 性能向上： 提案されたワークフローは、暗黙的から中程度のデッドラインにおいて、完全探索と比較してフルでの正確な予算サイジングの回数を91〜98%削減し、タイトなデッドラインにおいては（デッドラインを考慮した境界を用いることで）97.4%削減する。これは、タイトなデッドラインのシナリオにおいて、実時間（wall-clock time）で25.8倍の高速化を実現している。

4. 結果

• ランドスケープの安定性： 目的関数の値と近最適集合は、パラメータの小さな摂動（例：$\delta$ または WCET の $\pm 1\%$ の変化）に対して局所的に安定している。一方で、正確な最適解の識別は、離散的に切り替わり得る「近退化」したターゲットである。
• 幅の法則： 近最適集合の幅は、近似的に $\epsilon Q^*/\delta$ に比例してスケールする。経験的分析によれば、指数は流体モデルの $-1$ではなく、離散的な整数効果により、サブリニアな（約$-0.7$から$-0.8$）値を示す。
• 堅牢性： 幾何学的特性とワークフローの性能は、異なる周期構造（対数一様、ハーモニック、セミハーモニック）およびデッドライン・ファミリー（暗黙的、中程度、タイト）にわたって保持される。
• 外部検証： ワークフローは、宇宙輸送機の飛行制御システムから公開されているパラメータセット、および先行研究の制約付きデッドライン・パーティションに対してテストされ、期待される挙動を再現し、本手法の実用性を実証した。

5. 意義と主張

本論文は、ARINC-653のウィンドウ数選択において、「正確な最適解の識別」は、多くの場合、「予算の悔恨（regret）」よりも厳格であり、意思決定に関連性の高いターゲットであると論じている。

• 最適化の再定義： 著者は、問題を「正確なベストな $k$ を見つけること」から、「供給粒度がベストの $\epsilon$ 以内であることを認定すること」へと再定義することを提案している。これにより、出力は単一の点から、認定された集合への所属へと移行する。
• 実用的な意味合い： 低い相対オーバーヘッドと暗黙的/中程度のデッドラインを持つレジームでは、完全探索は不要である。提案されたワークフローは、安全性保証（選定された構成の正確な検証）と、予算保証（宣言された集合内でのベストの $\epsilon$ 以内）を、計算コストのわずかな部分で提供する。
• 限界： 論文では、「狭い集合」のレジーム（高オーバーヘッド、低利用率、タイトなデッドライン）においては、正確な選択が依然として重要であることを指摘している。これらの場合でも、ワークフローは機能するが、集合を絞り込むために、より多くの正確なサイジングを実行する。主張の範囲はシングルコア、シングルパーティションの解析に限定されており、システムレベルのパッキングやマルチコア間の相互作用は、パーティションごとのプレミアムが蓄積し、さらなる研究が必要な領域として特定されている。

本研究は、既存のスケジューラビリティ解析を置き換えることを目的としているのではなく、そのような解析に供給される供給粒度のパラメータ（$k$）の選択を最適化し、ブルートフォース探索に代わる、認定された効率的な代替手段を提供するものである。