論文要約：Scheduling Cause-Effect Chains without Timing Anomalies in End-to-End Latency

1. 背景と問題定義

リアルタイムシステム（特に自動運転などの制御システム）では、個々のタスクの実行時間だけでなく、データがシステム全体を伝播する「エンド・ツー・エンド（E2E）の遅延」が厳格なタイミング制約を満たす必要があります。この振る舞いを分析するために「因果チェーン（Cause-Effect Chains）」が広く用いられています。

しかし、これらのシステムには**タイミング・アノマリー（Timing Anomalies, TAs）**という現象が存在します。

• 現象: 特定のタスクの実行時間が短縮（ベストケースに近い実行）されたにもかかわらず、システム全体の反応時間（最大反応時間：MRT）が逆に長くなる非直感的な現象。
• 原因: 実行時間のばらつきにより、ジョブ間のデータ伝播パス（依存関係）が再構成され、予期せぬ長いパスが生成されるため。
• 既存手法の限界:
  1. 全 WCET 実行強制（Günzel et al. [10] など）: 解析を単純化し TA を排除するために、オンライン実行時にすべてのタスクを最悪実行時間（WCET）で実行させる。これにより平均遅延が著しく増大し、システム性能が低下する。
  2. 安全な解析手法（Günzel et al. [11] など）: スケジューリングを変更せずに安全な上限を導出するが、TA が残存しているため、得られる遅延の上限値が非常に大きくなり、過剰な設計マージンが必要となる。

本研究は、平均遅延の損失を無視できるほど小さく抑えつつ、E2E 遅延におけるタイミング・アノマリーを完全に排除する新しい手法を提案するものです。

2. 提案手法：決定論的データフロー（DDF）

著者らは、E2E 遅延における TA の発生原因を 2 つ特定し、これらを解決する「決定論的データフロー（Deterministic Data Flow, DDF）」を提案しました。

2.1 TA の発生源の特定

1. ジョブレベルの依存関係構造の変化: 全 WCET 実行で構築された「即時フォワード・チェーン（Immediate Forward Chain）」が、実際の非 WCET 実行時に発生する可能性のあるすべてのチェーンを網羅していないこと。
2. ジョブの読み書き時刻の境界の不確実性: 特定のチェーンが存在しても、全 WCET 実行で得られる読み書き時刻が、他の実行パターンにおける最悪の時刻を必ずしも上回らないこと。

2.2 解決策：DDF の実装

DDF は、ジョブ間の通信関係をオフラインで固定し、オンライン実行時にその関係を維持する枠組みです。これにより、実行時間のばらつきがデータ伝播パスの構造変化を引き起こすことを防ぎます。

• オフラインフェーズ:
  • 元のスケジューリング（FP）下で全 WCET 実行をシミュレーションし、ジョブレベルの通信関係（どのジョブがどのジョブのデータを参照するか）を抽出して DDF を構築します。
  • この DDF を維持するために、タスク属性（リリース時刻や優先度）を修正します。
• オンラインフェーズ:
  • RAW (Read-After-Write) の保証: 修正されたタスク属性（リリース時刻の遅延や優先度の調整）により、消費者ジョブが必ずプロデューサージョブの書き込み完了後に読み取りを開始するように強制します。これにより、依存関係の順序が保たれます。
  • RFI (Read-From-Intended) の保証: 複数のバッファを持つ通信機構（Multi-buffer communication）を導入します。これにより、消費者ジョブは意図したプロデューサー（DDF で定義された特定のジョブ）からのデータのみを読み取り、他のジョブからのデータ混入を防ぎます。

2.3 理論的保証

• TA 排除の証明: DDF 下では、即時フォワード・チェーンの構造が実行パターンに関わらず不変であり、かつジョブの読み書き時刻の境界が全 WCET 実行によって安全に上から抑えられることを数学的に証明しました。
• 結果: したがって、オフラインでの全 WCET 実行による解析結果が、オンラインでのあらゆる実行パターンに対する厳密な最悪ケース遅延（MRT）となります。

3. 主要な貢献

1. 重要な洞察: E2E 遅延における TA の発生源を「ジョブ依存関係の構造変化」と「読み書き時刻の境界」の 2 点に特定しました。
2. 初の TA 排除治療: 因果チェーンの E2E 遅延において、平均遅延の損失を無視できるレベルで抑えつつ TA を排除する初の手法を提案しました。
3. 一般的なモデリング: レジスタ通信だけでなく、マルチバッファ通信にも対応するより一般的な「即時フォワード・チェーン」の定義を提示しました。
4. 厳密な証明: 提案手法が E2E 遅延において TA 自由であることを形式化して証明しました。
5. 実験的評価: 既存の最先端手法（SOTA）と比較して、最大遅延、平均遅延、ジッターのすべてにおいて優位性を示しました。

4. 実験結果

自動車ベンチマークに基づいて生成された合成タスクセットを用いて評価を行いました。

• 最大反応時間 (MRT): 既存の安全解析手法（M23）と比較して、9%〜12% 平均で減少（最大 61% 改善）。これは、データ伝播パスの構造変化を防ぐことで、周期的な遅延の蓄積を排除したためです。
• 平均反応時間 (ART): 全 WCET 実行を強制する手法（M21）と比較して、平均遅延は大幅に改善（M21 は MRT と同等の遅延になるため）。提案手法は M23 と比較しても、平均遅延の増加はわずか**2%〜5%**に留まりました。
• ジッター（変動）: 依存関係の構造が固定されるため、遅延のばらつきが大幅に減少し、ジッターが 53%〜68% 削減されました。
• メモリオーバーヘッド: マルチバッファ機構によるメモリ使用量の増加はわずかで、実用的な範囲内でした。
• スケジューラビリティ: 元のスケジューリングで実行可能だったタスクセットは、提案手法を適用しても依然として実行可能であることが確認されました。

5. 意義と結論

本研究は、リアルタイムシステムにおける「タイミング・アノマリー」という長年の課題に対し、**「平均性能を犠牲にせず、かつ解析を厳密かつ安全に行う」**というトレードオフを打破する画期的な解決策を提供しました。

• 実用性: 自動運転や産業制御など、厳密な E2E 遅延保証が求められるシステムにおいて、過剰な設計マージンを削減し、システム性能を最大化する基盤技術となります。
• 学術的価値: 因果チェーンの遅延解析において、実行時間のばらつきがもたらす複雑な影響を、決定論的なデータフローの固定によって制御可能であることを示しました。

この手法は、既存の固定優先度プリエンプティブ（FP）スケジューリングと互換性があり、オフライン解析とオンライン実行の両面で実装可能であるため、実際の組み込みシステムへの導入が期待されます。