研究紹介

スケジューリング

リアルタイムスケジューリング

自動運転システムをはじめとするリアルタイムシステムは、処理結果の正しさだけでなく、出力のタイミング保証もその要件となります。したがって、多数のタスクの実行を定められたデッドラインまでに完了することが求められます。ただし、利用可能な計算資源には限りがあり、組込みシステムにおいては特にその制約が厳しいものとなります。そのような状況では、各タスクへ適切に計算資源を割り当てることが非常に重要であり、これを制御するのがリアルタイムスケジューリングです。

 

DAGスケジューリング

自動運転システムは、センシング、自己位置推定、周辺の物体検知、経路計画等の多数のタスクから構成されています。そして、これらのタスクの間には複雑な依存関係（データの流れ）が存在します。ここで、タスクをノード、タスク間の依存関係を有向エッジとすることで、自動運転システムはDAG（Directed Acyclic Graph）として表現できます。これにより、自動運転システムのスケジューリングをDAGのリアルタイムスケジューリング問題に帰着できます。DAGスケジューリングにおいて、最適解は多項式時間で計算不可能であることが知られており、最適に近い性能を得られるアルゴリズムの考案が主な関心となっています。

 

確率的実行時間

DAGスケジューリングにおける資源割り当て手法を考える際に、実行時間の最悪値を用いる既存研究が数多く存在します。しかしながら、実際の実行時間は入力データのサイズやキャッシュの挙動、分岐やループ構造などによって変動し、最悪値が発生する頻度は非常に低いことが一般的です。しかし、最悪値に耐えうるハードウェアは非常に高価であり、実際の実行時間でDAGスケジューリングを行う手法を考えなければならないという問題があります。この問題に対処する方法の一つとして、変動する実行時間とその発生確率を確率質量関数で表す、確率的実行時間を用いる手法があります。DAGスケジューリングに確率的実行時間を適用する際には、実行時間分布を検討した手法を提案する必要があります。図の例では、二つのノードの実行時間とそれらの間の通信時間がそれぞれ確率的に定義されています。この例において、それぞれの確率的実行/通信時間が独立であれば、それらの和は畳み込みと呼ばれる操作によって求められ、ノード列全体の確率的実行時間を算出できます。

メニーコア

近年、メニーコアプロセッサの中でもクラスタ型メニーコアプロセッサを使用したDAGスケジューリングの手法が盛んに研究されています。クラスタ型メニーコアでは、プロセッサ内の計算コアがクラスタと呼ばれるグループに分割され、各クラスタにはそれぞれのクラスタ内で独占的に使用できるシェアメモリが与えられています。この構造により、非クラスタ型のものと比べメモリ競合が発生しづらいといったメリットがあり、自動運転システムのような厳しいリアルタイム制約を持つプラットフォームでの使用が期待されています。クラスタ型メニーコアプロセッサでは、クラスタ内だけでなくクラスタ間でもデータの共有を行うことが出来ますが、デメリットとして、クラスタ間の通信がクラスタ内での通信よりも時間がかかってしまうということが挙げられます。例えばDAGスケジューリングでは、あるノードが複数のクラスタから計算コアを確保した場合や、依存関係のある二つのノード間で使用する計算コアが属するクラスタが異なっていた場合に発生します。そのため安積研究室では、クラスタ間通信を減らすたのコア割り当てアルゴリズムが研究されています。また、DAGのノードが持つ特性（最悪実行時間、並列度など）を考慮してメニーコア内の大量にある計算コアを有効的に使用するための手法も研究されています。