研究紹介
スケジューリング
リアルタイムスケジューリング
自動運転システムをはじめとするリアルタイムシステムは、処理結果の正しさだけでなく、出力のタイミング保証もその要件となります。したがって、多数のタスクの実行を定められたデッドラインまでに完了することが求められます。ただし、利用可能な計算資源には限りがあり、組込みシステムにおいては特にその制約が厳しいものとなります。そのような状況では、各タスクへ適切に計算資源を割り当てることが非常に重要であり、これを制御するのがリアルタイムスケジューリングです。
DAGスケジューリング
自動運転システムは、センシング、自己位置推定、周辺の物体検知、経路計画等の多数のタスクから構成されています。そして、これらのタスクの間には複雑な依存関係（データの流れ）が存在します。ここで、タスクをノード、タスク間の依存関係を有向エッジとすることで、自動運転システムはDAG（Directed Acyclic Graph）として表現できます。これにより、自動運転システムのスケジューリングをDAGのリアルタイムスケジューリング問題に帰着できます。DAGスケジューリングにおいて、最適解は多項式時間で計算不可能であることが知られており、最適に近い性能を得られるアルゴリズムの考案が主な関心となっています。
確率的実行時間
DAGスケジューリングにおける資源割り当て手法を考える際に、実行時間の最悪値を用いる既存研究が数多く存在します。しかしながら、実際の実行時間は入力データのサイズやキャッシュの挙動、分岐やループ構造などによって変動し、最悪値が発生する頻度は非常に低いことが一般的です。しかし、最悪値に耐えうるハードウェアは非常に高価であり、実際の実行時間でDAGスケジューリングを行う手法を考えなければならないという問題があります。この問題に対処する方法の一つとして、変動する実行時間とその発生確率を確率質量関数で表す、確率的実行時間を用いる手法があります。DAGスケジューリングに確率的実行時間を適用する際には、実行時間分布を検討した手法を提案する必要があります。図の例では、二つのノードの実行時間とそれらの間の通信時間がそれぞれ確率的に定義されています。この例において、それぞれの確率的実行/通信時間が独立であれば、それらの和は畳み込みと呼ばれる操作によって求められ、ノード列全体の確率的実行時間を算出できます。
メニーコア
近年、メニーコアプロセッサの中でもクラスタ型メニーコアプロセッサを使用したDAGスケジューリングの手法が盛んに研究されています。クラスタ型メニーコアでは、プロセッサ内の計算コアがクラスタと呼ばれるグループに分割され、各クラスタにはそれぞれのクラスタ内で独占的に使用できるシェアメモリが与えられています。この構造により、非クラスタ型のものと比べメモリ競合が発生しづらいといったメリットがあり、自動運転システムのような厳しいリアルタイム制約を持つプラットフォームでの使用が期待されています。クラスタ型メニーコアプロセッサでは、クラスタ内だけでなくクラスタ間でもデータの共有を行うことが出来ますが、デメリットとして、クラスタ間の通信がクラスタ内での通信よりも時間がかかってしまうということが挙げられます。例えばDAGスケジューリングでは、あるノードが複数のクラスタから計算コアを確保した場合や、依存関係のある二つのノード間で使用する計算コアが属するクラスタが異なっていた場合に発生します。そのため安積研究室では、クラスタ間通信を減らすたのコア割り当てアルゴリズムが研究されています。また、DAGのノードが持つ特性（最悪実行時間、並列度など）を考慮してメニーコア内の大量にある計算コアを有効的に使用するための手法も研究されています。
研究テーマ：確率的実行時間を考慮したDAGタスクのパーティショニング手法
【課題：確率的解析における計算量の爆発】 確率的実行時間を用いた解析は、実行時間の組み合わせ（状態空間）が膨大になるため計算量が爆発しやすく、特に複雑な依存関係を持つ大規模なDAGタスクセットへの適用が困難である点が課題でした。既存の確率的解析手法は計算コストの高さから小規模なタスクセットに限定されがちであり、実用的な規模へのスケーラビリティが欠けていました。
【アプローチ：シングルノード化と調整済み平均利用率】 本研究では、マルチコア環境でのパーティショニングEDFを対象に、計算効率の高いスケジューリング手法を提案しました。 具体的には、DAGタスクをシングルノードタスクとして扱うことで、計算手法が確立されているシングルコア向けの高速な確率的解析手法（近似計算等）の適用を可能にしました。さらに、確率的実行時間を基に計算する「調整済み平均利用率」を新たな指標として導入し、これを基にタスク割り当てを行うことで、計算量の増加を低減つつ高効率なシステム設計を実現しました。
研究テーマ：最悪ケースを考慮した確率的応答時間解析の高速化手法
【課題：最悪ケースによる計算負荷の増大】 確率的応答時間解析において、従来の「全タスク同時放出」という仮定は、最悪の期限ミス確率（WCDFP）を過小評価するリスクがあることが判明しました 。しかし、このリスクを排除した改訂された最悪ケースに基づく解析は、考慮すべき計算パターンが複雑になるため、従来手法では計算時間が大幅に増大してしまう点が課題でした 。その結果、高い精度を維持しつつ実用的な時間内で解析を完了させるスケーラビリティが不足していました 。
【アプローチ：解析モデルの統合とハフマン法による演算最適化】 本研究では、改訂された最悪ケースをモンテカルロ法や円環畳み込み法へ適用可能にする統合手法を提案しました 。具体的には、解析対象ジョブの直前に高負荷を集中させるモデルを構築し、過小評価のない安全な解析を可能にしました 。さらに、計算コストの大部分を占める確率分布の合成に対し、ハフマン符号の原理を応用した「最小分布優先の合成順序」を導入しました 。これにより、計算過程でのデータ肥大化を抑制し、精度を損なうことなく従来の数十倍の高速化を実現しました。
確率的最悪実行時間推定
リアルタイムシステムにおけるタイミング保証には、各タスクの実行時間情報、とりわけ最悪実行時間（WCET: Worst-Case Execution Time）が不可欠です。従来の理論では、任意のプログラムに対して単一値のWCETを安全側に見積もることが一般的でした。しかし、近年の組込みプラットフォームは、マルチプロセッサや深いパイプライン、多段キャッシュなどによって高速化・複雑化しており、実行時間は入力データとハードウェア状態によって大きく変動します。こうした環境では、すべてのハードウェア状態を網羅した決定論的なWCETの算出は極めて困難であり、過度に保守的な見積もりになりがちです。その結果として、計算資源の利用効率が著しく低下するという問題が生じます。
この課題に対する現実的なアプローチとして、確率的最悪実行時間（pWCET: probabilistic WCET）が注目されています。pWCETは、実行時間を確率変数として捉え、「実行時間がある値 x を超過する確率は p 以下である」という形で確率的な保証を与えます。これは、相補累積分布関数上で、超過確率 p に対応する実行時間 x を上限として定義されます。下図のように、実行時間分布はプログラムの入力や実行環境によって変化します（pET）が、pWCETはそれらを確率的に包絡する上界として表現されます。ここから、許容する超過確率に応じて実行時間の上限を柔軟に選択できる点がpWCETの利点です。これにより、稀に発生する極端な実行時間変動を考慮しつつも、過度に保守的にならないタイミング保証が可能となります。
本研究室では、限られた数の実行時間計測データからpWCETを推定する手法を研究テーマの一つとしており、精度・信頼性の向上、および適用範囲の拡大を目的としています。
