QoS-Efficient and Near-Optimal Imprecise Computation Task Deployment for Heterogeneous Multicore Systems

技術要約：ヘテロジニアス・マルチコア・システムにおけるQoS効率的かつ準最適（Near-Optimal）な不完全計算タスクのデプロイメント

問題提起
本論文は、ヘテロジニアス・マルチコア・プラットフォーム上での依存関係のある不完全計算（Imprecise Computation: IC）タスクのマッピングおよびスケジューリングに関する結合設計問題を扱っている。ICタスクは、必須サブタスク（ベースラインのQoSを保証）と、オプションのサブタスク（追加の実行時間を消費してQoSを向上させる）によって特徴付けられる。目的は、タスクのプロセッサへの割り当て、オプションのサイクル調整、およびタスクの開始時刻という3つの決定変数を同時に最適化することで、システムのQoSを最大化することである。

この最適化は、以下の4つの重要な制約条件を満たさなければならない：

1. リアルタイム制約： すべてのタスクはスケジューリング・ホライゾン $H$ 内に完了しなければならず、先行関係（precedence relations）が遵守されなければならない。
2. エネルギー供給： スケジューリング・ホライゾン全体における総エネルギー消費量（動的および静的）は、予算 $E_s$ を超えてはならない。
3. タスクの依存関係： 有向非巡回グラフ（DAG）としてモデル化されたタスクは、実行順序に従わなければならない。
4. 非重複（Non-overlapping）： 同じプロセッサに割り当てられたタスクは、同時に実行できてはならない。

本問題は混合整数非線形計画問題（MINLP）として定式化される。非線形性は、バイナリの割り当て変数と連続的なオプション実行変数との相互作用、および（オプションのサイクルが増えるにつれてQoSの利得が減少する）非線形な凹関数（concave QoS function）から生じる。著者らは、このMINLPを直接解くことはNP困難であり、大規模なシステムに対しては計算コストが高いと指摘している。

手法
MINLPの計算困難に対処するため、著者らは**TS-DD（Topological-sorting-assisted Dual Decomposition：トポロジカルソート支援型双対分解）**と呼ばれる分解ベースの解決フレームワークを提案している。このフレームワークは、元の問題を、クローズドループ・フィードバック機構を用いて反復的に解かれる2つのサブ問題へと分解する。

1. マスター問題 (Master Problem: MP):

   • 焦点： タスクのコアへの割り当て ($s_{ik}$) およびオプションの実行時間の調整 ($o_i$) を決定する。
   • 手法： バイナリの割り当て変数を連続変数に緩和する。非線形項を扱うために補助変数を用いて問題を凸形式に変換する。タスク割り当てとオプション実行のサブ問題に分離するために、ラグランジュ双対分解アプローチが採用される。
   • 解法： 双対問題は、ラグランジュ乗数を反復的に更新するために劣勾配法（subgradient method）を用いて解かれ、準最適なバイナリ割り当て決定を回収する。

2. スケジューリング問題 (Scheduling Problem: SP):

   • 焦点： MPによる割り当ておよび実行時間の決定に基づき、タスクの実行順序 ($u_{ij}$) および開始時刻 ($t^s_i$) を決定する。
   • 手法： トポロジカルソートに基づく依存関係を考慮したタスクソートアルゴリズムを使用する。これは、先行タスクの最終完了時刻と、割り当てられたプロセッサの最速利用可能時刻を計算することで、先行関係や非重複制約を違反することなく有効な開始時刻を決定する。

3. クローズドループ・フィードバック機構:

   • 機能： SPは実現可能性のチェックとして機能する。SPによって生成されたスケジュールがグローバルなデッドライン ($H$) を違反する場合、その残余時間がMPへとフィードバックされる。
   • メカニズム： フィードバックは、MPにおけるラグランジュ乗数（特にタイミングおよびオプション実行の境界に関連するもの）を更新する。これにより、次の反復においてオプション実行の「コスト」を増大させるか、あるいはより高速なプロセッサの選択を強制し、高QoSかつスケジューラブル（実行可能）な解へとMPを導く。

主な貢献

• 結合設計問題の定式化： ヘテロジニアス・マルチコアにおけるQoSを考慮したタスクデプロイメントを、非線形QoS関数を用いてオプション実行、エネルギー、およびリアルタイム制約のトレードオフを明示的にモデル化したMINLPとして定式化した。
• 分解ベースの解決策： 複雑なMINLPを、双対分解とトポロジカルソートを通じて、マスター問題（割り当て／サイクル調整）とスケジューリング問題（順序／タイミング）に分離する新しいフレームワークを開発した。
• 制約を考慮したフィードバック： スケジューリングの実行不能性（デッドライン違反）がマスター問題における割り当ておよびオプションサイクル決定に直接影響を与えるクローズドループ・メカニズムを導入し、解の品質とスケジューラビリティの両方を向上させた。
• 複雑度の低減： 提案手法は、計算複雑度を指数関数的（直接的なMINLPソルバーに典型的）なものから、タスク数に対してほぼ線形（$O(N_{max}N)$）へと低減させた。

実験結果
著者らは、実世界のアプリケーションDAG（LE, JPEG, FFT, MW）およびランダムに生成されたグラフを用いて、5コアのヘテロジニアス・プラットフォーム上で手法を評価した。

• 解の品質： 提案されたTS-DD法は、商用ソルバーであるGurobiが得た最適QoSの**95.25%**を達成した。これは、遺伝的アルゴリズム（GA, ~90.25%）および2ステップのヒューリスティック（HEU, ~75.00%）を上回った。
• 計算効率： TS-DDは、Gurobiが使用した計算時間のわずか**19.8%**しか必要としなかった。HEUはより高速であったが、著しく低いQoSしか得られなかった。
• スケーラビリティ： 計算時間はタスク数の増加に対してほぼ線形に成長し、理論的な複雑度分析が正しいことを裏付けた。
• フィードバック機構の影響： TS-DDと、フィードバックループを持たないバージョン（NoFB）を比較した実験では、フィードバック機構がQoS（特に依存強度の高い複雑なDAGにおいて）とタスクのスケジューラビリティ率（96.7% vs 8.0%）の両方を大幅に改善したことが示された。

意義と主張
本論文は、提案手法が解の品質と計算効率の間に優れたトレードオフを提供し、リアルタイム応答とエネルギー効率が極めて重要なリソース制約のあるヘテロジニアス・システムに適していると主張している。著者らは、提案手法が、既存のエネルギー重視またはQoS重視の手法よりも、ヘテロジニアス・プラットフォームの特性、タスクの依存関係、および非線形QoSモデルの結合をより包括的に扱える点を強調している。クローズドループ・フィードバックは、理論的な割り当て決定が、QoSを過度に犠牲にすることなく、現実世界の実行可能なスケジュールへと確実に変換されることを保証する鍵となる革新技術として位置づけられている。