JP2012108576A - マルチコアプロセッサ、処理実行方法、プログラム - Google Patents

Abstract

【課題】既存のプログラムの変更によるコスト増を抑制し、既存のプログラムをマルチコアで実行しても適切に負荷分散できるマルチコアプロセッサを提供すること。
【解決手段】複数のコア５１と、アプリケーション２２が記憶された記憶手段５７と、を有するマルチコアプロセッサ２００であって、アプリケーションを複数の処理に区分した際の処理間の依存関係を登録した処理依存関係情報１２と、各処理の進度状況が登録された進度状況登録テーブル１１と、進度状況が実行待ちの処理と処理依存関係情報において依存関係がある処理の実行完了が前記進度状況登録テーブルに登録されている場合、実行待ちの処理の前記進度状況を実行可能に更新する進度状況更新手段３１と、進度状況に実行可能と設定された処理を空きコアに割り当てる処理割り当て手段３２と、を有する。
【選択図】図２

Description

本発明は、複数のコアが搭載されたマルチコアプロセッサに関し、特に、コアに処理を割り当てることで負荷分散できるマルチコアプロセッサに関する。

車両には数多くの電子制御装置が搭載されており、各電子制御装置が各種のプログラムを実行して様々な車載装置を制御している。電子制御装置はＣＰＵを有しているが、電子制御装置においてもＣＰＵのマルチコア化を図ることで処理効率を向上させようという試みがある。

マルチコアのＣＰＵの処理効率の向上は、複数のタスクを各コアが並行に実行することを基本的な考え方にする。しかしながら、タスクには処理内容や重要度などに違いがあり全てのタスクを公平にコアに割り当てることはできないため、効率よくタスクをコアに割り当てる技術が考案されている（例えば、特許文献１参照。）。特許文献１には、複数個のプロセッサユニットにタスク割当を行なう際、プログラムの実行時間や実行タスク間の依存性を考慮するマルチプロセッサシステムが開示されている。

また、タスク単位でなくタスクが分割されたスレッド単位でコアに割り当てる技術も考案されている（例えば、特許文献２参照。）。特許文献２には、サブルーチンやスレッドにタグを付け、スレッドの実行特徴を連続して習得してスレッド性能データを生成し、スレッド特性データに基づきコアにスレッドを割り当てるマルチプロセッサシステムが提供されている。

特開２００９−０６９９２１号公報 特開２００９−１５１７７４号公報

ところで、車両ではすでに電子制御装置が多くのプログラムを実行しており、この既存のプログラムを変更することなく、マルチコアに適用することでコスト増を抑制することが検討されている。

図１は、従来のシングルコア用のプログラムを模式的に説明する図の一例である。このプログラムの特にメインタスクはシングルコア（図のＣＰＵ）用に開発されているため、最初から最後まで逐次実行される。また、ＣＰＵに割込みが生じると、ＣＰＵは例えば割込みタスクを実行する。

図１（ａ）のようなプログラムを、図１（ｂ）のようにマルチコアの各コアに割り当てることを考えると、例えばＯＳ（Operating System）が、タスクの起床毎にメインタスクと割込みタスクを各コアに割り当てることになる。したがって、図１（ａ）と図１（ｂ）を比較すれば、コア１の処理負荷は割込みタスクを実行する必要がない分だけ低減されたことになる。

しかしながら、一般に、メインタスクと割込みタスクではメインタスクの方が処理負荷が大きく、メインタスクと割込みタスクを分散しただけでは、マルチコアによる処理負荷の低減・処理の高効率化の恩恵を十分には受けられない。

そこで、特許文献２に開示されているように、タスクをスレッドなどのより小さい粒度に分割して、各コアに割り当てることが考えられる。しかし、シングルコア用のプログラム（この場合はメインタスク）を分割することは容易ではなく、特許文献２にもスレッドへの分割方法は開示されていない。コンパイルされたプログラムには、例えばC言語の関数やサブルーチンに対応するラベルが記述されているので、ラベル毎にスレッドに分割することが考えられる。しかし、ラベル毎にスレッド化した場合、１つのスレッドで処理が完結しているという保証がなく、スレッド単位の取り扱いが不具合を引き起こすおそれがある。また、スレッドをあまり小さい粒度にするとコアへの割り当てのオーバーヘッドが目立つようになるため、ラベル毎に一律にスレッド化することは適切でない。

また、処理単位の適切な粒度にスレッド化できたとしても、スレッド間の依存関係を考慮せずに、ＯＳ等が単にスレッドを空いたコアに割り当てるだけでは、プログラムが正常に動作する保証がない。

本発明は、上記課題に鑑み、既存のプログラムの変更によるコスト増を抑制し、既存のプログラムをマルチコアで実行しても適切に負荷分散できるマルチコアプロセッサを提供することを目的とする。

本発明は、複数のコアと、アプリケーションが記憶された記憶手段と、を有するマルチコアプロセッサであって、前記アプリケーションを複数の処理に区分した際の処理間の依存関係を登録した処理依存関係情報と、各処理の進度状況が登録された進度状況登録テーブルと、前記進度状況が実行待ちの処理と前記処理依存関係情報において依存関係がある処理の実行完了が前記進度状況登録テーブルに登録されている場合、実行待ちの処理の前記進度状況を実行可能に更新する進度状況更新手段と、前記進度状況に実行可能と設定された処理を空きコアに割り当てる処理割り当て手段と、を有することを特徴とする。

既存のプログラムの変更によるコスト増を抑制し、既存のプログラムをマルチコアで実行しても適切に負荷分散できるマルチコアプロセッサを提供することができる。

従来のシングルコア用のプログラムを模式的に説明する図の一例である。 マルチコアプロセッサの概略的な特徴部を示す図の一例である。 マルチコアプロセッサのハードウェア構成図の一例である。 マルチコアプロセッサの実装例を示す図である。 処理分割分散装置の機能ブロック図の一例である。 処理進度表の一例を示す図である。 処理モデルの一例を示す図である。 処理進度表更新部が処理進度表を更新する手順を示すフローチャート図の一例である。 処理割り当て部がコアに処理１〜５を割り当てる手順を示すフローチャート図の一例である。 Ｓ１４０，Ｓ１５０の処理のフローチャート図の一例である。 コア１，２が処理１〜５を実行するタイムチャート図の一例である。 コア１，２に対する処理１〜５と割込みタスクの割り当ての関係を示す図の一例である。 処理分割分散装置の機能ブロック図の一例である。 コア１，２が処理１〜５を実行するタイムチャート図の一例である。

以下、本発明を実施するための形態について図面を参照しながら説明する。
図２は、本実施形態のマルチコアプロセッサの概略的な特徴部を示す図の一例である。まず、マルチコアプロセッサには新たに処理分割分散装置１００が配置される。処理分割分散装置１００は処理進度表１１と処理モデル１２を有する。
・処理進度表１１には、プログラムのメインタスクから抽出された複数の処理のステータス（Wait、Ready、Processing、Done）が登録されている。
・処理モデル１２には、処理間の依存関係が登録されている。

制御部１３は、処理進度表１１のステータスを監視し、Waitの処理があれば処理モデル１２を参照して、Waitの処理が実行可能な状態になったか否かを判定する。制御部１３は、実行可能になった処理のステータスをReadyに更新することで、コア１又はコア２が該処理を実行することができる。

処理進度表１１には、既存のプログラムのメインタスクから適切な粒度の処理が抽出され、処理の先頭アドレス（後述の処理開始アドレス）と終了アドレス（後述の処理終了アドレス）が登録されている。制御部はこれらのアドレスを使用して処理を切り替えることで、既存のプログラムについてはほとんど変更することなく、マルチコアに負荷分散することが可能となる。このため、既存のプログラムを分割してマルチタスク用に再開発するのに比べて、小さい労力でマルチコア化に対応することができる。

〔構成〕
図３は、マルチコアプロセッサ２００のハードウェア構成図の一例を示す。マルチコアプロセッサ２００は、マルチレイヤーバス６１を介して接続されたＣＰＵ５０、ＤＭＡＣ５４、ＳＤＲＡＭ５５、Ｉ／Ｏブリッジ５６及びＲＯＭ５７を有する。

ＣＰＵ５０は２つの集積回路を有し、各集積回路が、コア５１、ＩＮＴ５２、及び、ＲＡＭを５３有する（これらを区別する場合、コア１，コア２のように番号を付す）。コア１，２は、それぞれ、ＩＦＵ（Instruction Fetch Unit）、ＤＥＣ（DECoder）、ＲＦ（Register Fetch）、ＲＥＧ（REGister）、ＬＳＵ（Load Store Unit）、ＳＨ（Shifter）、ＡＬＵ、ＭＵＬ及びＦＰＵ等の演算回路を有し、パイプライン制御により１クロックで１命令を実行することができる。

ＲＡＭ１はコア１に専用のメモリ（一次キャッシュ）であり、ＲＡＭ２はコア２に専用のメモリ（一次キャッシュ）である。ＩＮＴ１とＩＮＴ２は、コア間割り込みを制御すると共に、コア１からコア２又はコア２からコア１に、パラメータ等の送受信を制御する。また、ＩＮＴ１，ＩＮＴ２は、ＲＡＭ１、ＲＡＭ２、又は、ＳＤＲＡＭ５５を共有の通信用メモリにしてパラメータ等を送受信することもできる。ＩＮＴ１とＩＮＴ２を使用したコア間のパラメータ通信はハードウェア的な実装であり、この他、ＯＳが提供するコア間通信のＡＰＩを利用してもコア１とコア２は通信することができる。

ＤＭＡＣ５４は、コア１及びコア２から要求を受けてプログラム６０をＳＤＲＡＭ５５、ＲＡＭ１、ＲＡＭ２に読み込んだり、周辺機器からのメモリアクセス要求を調停すると共に、Ｉ／Ｏブリッジ５６からＳＤＲＡＭ５５へ、又は、ＳＤＲＡＭ５５からＩ／Ｏブリッジ５６へ、コア１、コア２を介することなくデータを転送する。ＳＤＲＡＭ５５は、コア１及びコア２がプログラム６０を実行している間、ＲＡＭ１又はＲＡＭ２にミスヒットするとプログラム６０又はデータを提供するためのメモリ（二次キャッシュ）である。ＳＤＲＡＭ５５の少なくとも一部はコア１とコア２により共有される。

ＲＯＭ５７にはプログラム６０及びタスク制御プログラム７０が記憶されている。プログラム６０は、少なくともメインタスクと割込みタスクが含まれている。タスク制御プログラム７０は、処理分割分散装置１００を制御するソフトウェアであるが、処理分割分散装置１００がハード的に実装される場合には不要となる場合がある。なお、ＲＯＭ５７には、ＯＳやデバイスドライバ（プラットフォーム）も記憶されている。

Ｉ／Ｏブリッジ５６は、マルチレイヤーバス６１とＩ／Ｏバス６２の間で相互に周波数や電圧値などを変換する。Ｉ／Ｏバス６２には種々のＩ／Ｏ５８が接続されている。Ｉ／Ｏ５８はプロセッサ１００と外部の機器を接続するインタフェースであり、例えば、ＣＡＮコントローラ、各種のアクチュエータ、センサ、スイッチ等が接続される。

ここで、マルチコアの態様として、それぞれのコアに決まったタスクを割り当てるＡＭＰ（Asymmetric Multi‐processing）、例えばＯＳがそれぞれのコアにタスクを動的に割り当てるＳＭＰ（Symmetric Multi‐processing）、又は、一部のコアにタスクを固定的に割り当て、残りのコアにタスクを動的に割り当てるＢＭＰ（Bound Multi‐processing）が知られている。本実施形態では、処理分割分散装置１００が複数のコアに処理を動的に割り当てるのでＳＭＰのマルチコアプロセッサ２００とすることが自然である。だが、いくつかのコア５１にだけ処理を割り当てると決めてそのコアの中だけで処理分割分散装置１００が処理を動的に割り当てることもできる。したがって、ＳＭＰ、ＡＭＰ又はＢＭＰのいずれかの実装態様でなければならないと言うことはない。

なお、ＳＭＰのマルチコアプロセッサ２００の場合、複数の処理の処理結果をコア間で共有できるように、不図示のスヌープコントローラ（ＳＮＣ）がＲＡＭ１とＲＡＭ２のデータの更新を監視して、更新データをＲＡＭ１とＲＡＭ２間で通信する。これによりＲＡＭ１とＲＡＭ２のキャッシュのコヒーレンシを維持することができる。また、コア間で１つの処理を再割り当てすることも容易になる。

図４は、マルチコアプロセッサ２００の実装例を示す図である。アプリケーション２２は、メインタスクや割込みタスクのプログラム６０、及び、別の既存のプログラムのメインタスク（区別するため他のタスクという）である。なお、別の既存のプログラムは、処理に分割されずに実行されるものとする。また、割込みタスクは２つ以上あってもよい。

ＰＦ／ＯＳ２１はプラットフォームとオペレーティングシステムを意味するが両者が独立して存在してもそうでなくてもよく、図示するＰＦ／ＯＳ２１の意義は処理分割分散装置１００と略一体になって、コア５１にアプリケーション２２の処理を割り当てる点にある。処理分割分散装置１００は複数の処理を各コア１〜Nに割り当てるが、この機能はＯＳのスケジューリングと同系統の機能となる。一方、メインタスクは複数の処理に分割されたので、ＯＳによるスケジューリングは困難になっている。

メインタスクを変更せずにＯＳによるスケジューリングを可能とするには、メインタスクが複数の処理に分割されていることをＯＳから遮蔽することが好ましい。このため、処理分割分散装置１００は、ＰＦ／ＯＳ２１がいずれかのコア５１にメインタスクを割り当てるというディスパッチ処理をコア５１の代わりに受け取り、各処理の実行を制御する。このように、処理分割分散装置１００はＰＦ／ＯＳ２１に含まれる形態で実装されることがある。なお、上記のように処理分割分散装置１００をハード的なＩＣで実装することもできるが、この場合はＯＳのメインタスクに対するディスパッチ処理をコア５１の代わりに、処理分割分散装置１００が取得して、各処理の実行の制御を開始する。

図５は、処理分割分散装置１００の機能ブロック図の一例を示す。処理分割分散装置１００をソフト的に実装する場合、図５の処理分割分散装置１００はいずれかのコア５１により実行される。また、図５では処理分割分散装置１００とＰＦ／ＯＳ２１を一体に図示した。

マルチタスクをサポートするＯＳでは、タスクの優先順位と状態に応じて、実行可能なタスクから順に実行キュー２３に登録する。タスクの状態には、例えば、実行可能、実行中、実行待ちの状態がある。ＯＳにとってタスクの優先順位は予め既知である。ＯＳは、実行キュー２３の中から最も優先順位の高いタスクをコア５１に割り当てる。

また、プリエンプション（実行中のタスクの中断と再開）が可能なＯＳの場合、ＯＳは実行キュー２３の中で最も優先順位の高いタスクと、各コア５１が実行中のタスクの優先順位を比較して、実行キュー２３で最も優先順位の高いタスクが、各コア５１が実行中のいずれかのタスクの優先順位よりも高くなると、そのコア５１に実行キュー２３で最も優先順位の高いタスクを割り当てる。

ここで、コア５１が実行しているタスクを切り替える必要が生じるのは、タスク自身がタスク切り替えを引き起こすサービスコールをＯＳに要求した場合や、割り込みが起こり割り込み処理を実行していたコア５１がサービスコールをＯＳに要求した場合などである。前者の場合は、自身を起床待ちにする場合や、優先度の高いタスクを呼び出す場合に生じる。

なお、メインタスクは既存のプログラムから変更がないので、メインタスクの各処理がサービスコールをＯＳに要求することはない。また、メインタスクの優先順位が最も高いのでメインタスクの各処理を実行しているコア５１の全てが、例えば割込みタスクに切り替えられることは生じない。

本実施形態では、メインタスクの優先順位が最も高いが、割込みが生じ割込みタスクが起床された場合は、割込みタスクの優先順位の方が高くなるものとする。

ところで、ＯＳから見てメインタスクとその他のタスクは優先順位の違いはあってもそれぞれは１つのタスクなので、発明の課題で説明したように、メインタスクに割り当てられるコア５１は１つである。しかし、マルチコアプロセッサ２００にメインタスク以外のタスクが同時に生起される数よりも２〜３個多いコアを用意しておけば、メインタスクに複数のコア５１が割り当てられているのとみなすことができる。すなわちＳＭＰでは、処理分割分散装置１００がメインタスクの複数の処理を空いているコア（メインタスク以外のタスクを実行していないコア）５１に割り当て並行に実行できる。

また、マルチコアプロセッサ２００の実装をＡＭＰとした場合、メインタスクに専用の複数のコア５１が割り当てられるので、この場合も処理分割分散装置１００がメインタスクの複数の処理を空いているコア５１に割り当て並行に実行できる。しかし、実行可能なコア５１の数を可変にできるという点（スケーラビリティ）ではＳＭＰの方がより好ましい。

サービスコールが発生したり、プリエンプションが発生すると、ＯＳはディスパッチ処理を開始する。本実施例では、ＯＳがメインタスクを呼び出すディスパッチ処理を、制御部１３が受け取る。

また、ＯＳがメインタスク以外のタスクを呼び出すディスパッチ処理を実行した場合は、従来と同様に、制御部１３を介することなくコア５１が実行するタスクの切り替えが行われる。制御部１３を介してタスクの切り替えが行われてもよい。

ＯＳは、タスクをコア５１に割り当てる際、まず、割り当て対象のコア５１が実行しているタスクのコンテキスト（タスクの実行に必要な、汎用レジスタ，プログラムカウンタ、スタックポインタなど）を保存し、該コア５１に割り当てるタスクのコンテキストを割り当て対象のコア５１に設定する。

一方、いずれかのコア５１にメインタスクが割り当てられた場合、メインタスクが実行中になる。実行中の間、制御部１３は、処理進度表１１の更新、各コア５１への処理の割り当てを繰り返す。

図６は処理進度表１１の一例を示す図である。処理進度表１１には、「エントリ」、「処理識別番号（１〜５）」、「処理開始アドレス」、「処理終了アドレス」、及び、「ステータス」が登録される。「エントリ」にフラグ「○」が設定された処理は、メインタスクにおいて処理の順番が最初の処理であることを示す。「エントリ」をなくし、処理割り当て部３２が処理進度表１１の最上位の処理からコア５１に割り当てるとしてもよいが、この場合、処理１と並行に実行可能な処理（図では処理２）があっても、しばらくは実行されない状態が発生してしまう。また、後述するように「エントリ」があることで、メインタスクの全ての処理１〜５が完了した後に、メインタスクを再開するための最初の処理が明らかになる。

「処理識別番号」は処理分割分散装置１００が処理を識別するための情報である。メインタスクから処理１〜５をどのように分割するかは後述する。

「処理開始アドレス」は処理１〜５の先頭アドレスであり、「処理終了アドレス」は処理１〜５の終了アドレスである。これらのアドレスは、ＲＯＭ５７に記憶された状態のプログラム６０のアドレスである。図では処理終了アドレスは処理開始アドレスの直前になっているが、分岐先で終了する場合などはこのようにならない場合もあるし、また、条件分岐した場合に対応するため複数の処理終了アドレスが登録される場合もある。

「ステータス」は、各処理の状態（Ready、Processing、Wait、Done）を表す。Readyは処理に必要なデータや事象が全て揃っていて、コア５１が割り当てられればいつでも実行可能な状態を、Processingはコア５１が実行している状態を、Waitは他の処理による演算結果、入出力終了などの事象の終了を待っている状態を、Doneは処理が完了した状態を、それぞれ意味する。なお、処理のステータスは、ＯＳが監視するタスクの状態とは別のものである。

図５の処理割り当て部３２は、処理進度表１１のステータスが“Ready”の処理を空いているコア５１に割り当てる。具体的には、処理進度表１１に登録された処理開始アドレスを、空いているコア５１のＰＣ(プログラムカウンタ)に設定する。割り当て対象の空いているコア５１がそれまで別の処理を実行していた場合、処理割り当て部３２はコンテキストを保存したり、複数の処理の処理結果を統合するなど、必要な処理を行う。

また、終了判定部３３は、処理進度表１１のステータスが“Processing”の処理を実行しているコア５１のＰＣを監視して、処理終了アドレスに到達したか否かを判定する。これは、メインタスクは既存のプログラムから変更がないため、各コア５１が処理の終了を判定することが困難なためである。このため、外部の終了判定部３３が終了を判定する。

処理進度表更新部３１は、処理進度表１１のステータスを操作する手段であり、特に、Waitの処理をReadyに更新する処理を行う。
図７は、処理モデル１２の一例を示す。処理モデル１２は並行に実行可能な処理、及び、処理間の依存関係を示す情報を含む。図７では、処理１〜３は並列に処理が可能であることを示し、処理４は処理１及び処理２に対し依存関係を有し、処理５は処理３及び処理４に依存関係を有することをそれぞれ示している。依存関係とは、例えば、処理４は処理１及び２のいずれも完了しないと実行できないことを言う。

なお、図６の処理進度表１１のステータスは、メインタスクが２つのコア５１を使用している状態で、処理１と処理２が並行に実行され、その後、処理１が先に終了されたことで、処理３がReadyになった状態を示す。

処理進度表１１の処理１〜５は、この処理モデル１２を開発者が抽出する際に区分した一連の（ひとまとまりの）処理となる。処理の抽出について説明する。シングルタスクのプログラムはコードの上から順番に実行される。関数型のプログラムではmain関数から定義された関数j（j：１〜ｍ）やマクロi（i：１〜ｎ）が順番に呼び出されるようにして実行される。開発者は、関数jやマクロiで依存関係のある箇所を特定する。依存関係には、次のようにデータ依存と処理依存がある。
・データ依存
後の関数jやマクロiがそれよりも前の関数jやマクロiが使用する変数を使用する場合である。例えば、後の関数がそれよりも前の関数から「引数」を受け渡される場合や、後の関数と前の関数が共通のグローバル関数を使うような場合である。より具体的な例では、前の関数がクランク角を求める処理であり、後の関数がクランク角を用いて燃料噴射タイミングなどを決定する処理の場合、２つの処理にデータ依存関係があると言える。また、例えば、前の関数が圧縮されたデータを伸張する処理であり、後の関数がデータを表示したり出力する処理の場合、２つの処理にデータ依存関係があると言える。
・処理依存
後の関数jやマクロiの実行に、それよりも前の関数jやマクロiが実行した状況が必要となる場合である。例えば、後の関数がアクチュエータを元の状態に戻す処理であり、前提として前の関数がアクチュエータをある状態にする処理である場合、２つの処理に処理依存関係があると言える。また例えば、後の関数が入出力装置にデータを出力する処理であり、前の関数が入出力装置を初期化する処理である場合、２つの処理に処理依存関係があると言える。

開発者は、このような依存関係を抽出し、メインタスクが使用可能なコア数を考慮して、適当な数の処理に区分する。例えば、メインタスクが使用可能なコア数が少ない（例えば２つしかない）のに、それよりもかなり多い数（例えば、５０〜１００）に処理を区分すると並列に実行可能な処理は増えるが、処理の切り替えのオーバーヘッドが処理効率を下げてしまう。一方、メインタスクが使用可能なコア数が十分にある（例えば１０個ある）のに、区分後の処理の数が少ないと（例えば、１０以下）、並列に実行可能な処理が少なくなり、マルチコアの有効性を活かせない。このため、開発者はある程度最適化しながら処理を適切な数に区分する。

〔動作手順〕
図８は、処理進度表更新部３１が処理進度表１１を更新する手順を示すフローチャート図の一例である。図８の手順は、マルチコアプロセッサ２００が起動すると繰り返し実行される。なお、以下では、コア数は２つ（処理分散分割装置１００を入れると３つ）であるとして説明する。

起動直後の処理進度表更新部３１は処理進度表１１を初期化する。例えば、ＲＡＭ５３に処理進度表１１を生成し初期状態を設定する。「エントリ」「処理識別番号」「処理開始アドレス」「処理終了アドレス」については固定なので、処理進度表更新部３１は既知のこれらの情報をＲＡＭ５３に書き込む。

また、起動直後の各処理のステータスは、「エントリ」にフラグが設定された処理１，２が“Ready”でなければならないので（そうしないとどの処理も開始されない）、処理進度表更新部３１は処理１，２のステータスをReadyに更新する。その他の処理３〜５のステータスは全てWaitに更新する。なお、処理モデル１２により依存関係のないことが分かる処理３のステータスをReadyとしておいてもよい。

処理進度表更新部３１は、処理進度表１１のステータスがWaitの処理があるか否かを判定する（Ｓ１０）。判定のタイミングは、例えば、クロックサイクル毎でもよいし、終了判定部３３が、コア５１が実行している処理が完了したと判定したタイミングでもよい。

ステータスがWaitの処理３，４、５がある場合（Ｓ１０のＹｅｓ）、処理進度表更新部３１はステータスがWaitの処理３，４、５について１つずつ処理モデル１２に基づき依存関係のある処理が全てDoneか否かを判定する（Ｓ２０）。

処理モデル１２によれば、処理３に対し依存関係のある処理はなく、処理４に対し依存関係のある処理は処理１，２なので、処理進度表更新部３１は処理１，２がDoneとなったか否かを判定し、処理５に対し依存関係のある処理は処理３，４なので、処理進度表更新部３１は処理３，４がDoneとなったか否かを判定する。ステータスがWaitの処理に関し依存関係のある処理が全てDoneになると、処理進度表更新部３１はWaitであったステータスをReadyに更新する（Ｓ３０）。

ステップＳ１０に戻り、ステータスがWaitの処理がなくなると（Ｓ１０のＮｏ）、処理のステータスはReady、Done、又は、Processingということになるが、全てDoneになった場合に「エントリ」の処理１、２から再開する必要がある。

このため、処理進度表更新部３１は処理進度表１１の全てのステータスがDoneになったか否かを判定する（Ｓ４０）。全てのステータスがDoneになっていない場合（Ｓ４０のＮｏ）、手順はＳ１０に戻る。

全てのステータスがDoneになった場合（Ｓ４０のＹｅｓ）、処理進度表更新部３１は「エントリ」にフラグが設定された処理１、２にReadyを設定する（Ｓ５０）。メインタスクをシングルコアのプロセッサで実行する場合と同様に、本実施形態のマルチコアプロセッサ２００はメインタスクを繰り返し実行することができる。

なお、ステップＳ４０で全てのステータスがDoneになるまで待つのでなく、ステータスがＤｏｎｅとProcessingだけになったら、「エントリ」にフラグが設定された処理１、２にReadyを設定することもできる。こうすることで、例えば、コア１が処理５を実行中（Processing）、処理１、２のステータスがReadyになるので、いずれか１つ以上のコア２が空き次第、そのコア２が処理１又は処理２を実行できるようになる。したがって、処理の並列度をさらに向上させることができる。

図９は、処理割り当て部３２がコア５１に処理１〜５を割り当てる手順を示すフローチャート図の一例である。図９の手順は、マルチコアプロセッサ２００が起動すると繰り返し実行される。

まず、処理割り当て部３２は、「エントリ」にフラグが設定された処理１、２のステータスがReadyか否かを判定する（Ｓ１１０）。こうすることで、マルチコアプロセッサ２００はメインタスクで最初に行うべき処理から実行を開始できる。処理１、２のステータスがReadyでない場合（Ｓ１１０のＮｏ）、処理進度表１１の初期化が完了していないとして待機する。

処理１、２のステータスがReadyである場合（Ｓ１１０のＹｅｓ）、処理割り当て部３２は処理進度表１１の処理１，２の処理開始アドレスを読み出す（Ｓ１４０）。そして、処理割り当て部３２は、空いているコア１，２で処理１，２を実行する（Ｓ１５０）。すなわち、処理１の処理開始アドレスをコア１のＰＣに、処理２の処理開始アドレスをコア２のＰＣに、それぞれ設定する。

図１０は、Ｓ１４０，Ｓ１５０の処理のフローチャート図の一例を示す。処理割り当て部３２は、空いているコア１，２に割り当てた処理１，２の識別情報を処理進度表更新部３１に通知するので、処理進度表更新部３１は処理１，２のステータスをProcessingに更新する（Ｓ２１０）。

その後、コア１，２は処理１，２を実行する（Ｓ２２０）。コア１，２が処理１，２を実行している間、終了判定部３３はコア１，２のＰＣをＩＮＴ経由で監視したり、命令バッファを読み出すことで、コア１，２が処理終了アドレスまで処理を実行したことを検出する。終了判定部３３は、コア１，２が処理終了アドレスまで処理を実行したことを検出すると、ＰＣや命令バッファに処理を終了する命令（例えば、NOP、ＥＮＤ等）を設定するなどして、処理１，２を強制的に終了させる。

そして、終了判定部３３は処理１，２の識別情報と終了を処理進度表更新部３１に通知する。これにより、処理進度表更新部３１は処理１，２のステータスをＤｏｎｅに更新する（Ｓ２３０）。

図１１はコア１，２が処理１〜５を実行するタイムチャート図の一例である。初期状態の処理１，２のステータスはReadyであり、ステップＳ２１０の手順により処理１，２のステータスはProcessingになる。また、この後、処理１，２が実行中に処理３のステータスはReadyとなる。その後、コア１が処理１の処理終了アドレスまで実行すると、処理１のステータスはＤｏｎｅとなり、コア２が処理２の処理終了アドレスまで実行すると、処理２のステータスはＤｏｎｅとなる。

図９に戻り、処理割り当て部３２は、定期的に又は処理進度表１１が更新される毎に、ステータスがReadyの処理があるか否かを判定する（Ｓ１３０）。処理１，２の実行中は処理３のステータスがReadyであるので、処理割り当て部３２は空きコアがあるか否かを判定する（Ｓ１３０）。空きコアの有無は、例えば、ＯＳに問い合わせたり、フラグを参照することで判断できる。

例えば、処理１，２の実行中は空きコアがないので手順はステップＳ１２０に戻る。そして、コア１が処理１の実行を完了すると、コア１が空きコアとなるので（Ｓ１３０のＹｅｓ）、処理割り当て部３２はコア１に処理３を割り当て、コア１が処理３を実行する（Ｓ１４０、Ｓ１５０）。

これにより、処理進度表更新部３１は処理３のステータスをProcessingに更新する（Ｓ２１０）。ここで、処理割り当て部３２は、「エントリ」にフラグが設定された処理以外の処理を割り当てる際、コンテキスト管理を実行する。

まず、処理割り当て部３２は、それまでコア１が実行していた処理１のコンテキストを保存する。次に、処理割り当て部３２は、処理モデル１２を参照して、割り当て対象の処理がデータ依存の関係を有する処理を探す。処理３の場合は、データ依存の関係にある処理はないので、処理割り当て部３２は何もしない。

これに対し、例えば処理４が処理１と処理２に対しデータ依存の関係がある場合、処理割り当て部３２は、保存してある処理１と処理２のコンテキストを読み出し、予め定められた処理を施して、コンテキストを復帰する。予め定められた処理は、処理１，２に対する処理４のデータ依存関係、処理３，４に対する処理５のデータ依存関係によって様々であるが、例えば、処理１、２のコンテキストのうち処理４が使用するデータが格納されたレジスタのみ取り出す処理、状態を示すフラグを取り出す処理等である。なお、処理４が処理１、２に対しデータ依存関係があっても、処理１，２のコンテキストを互いに演算するような処理は処理４内で行われる。

その後、コア１は処理３を実行するので（Ｓ２２０）、終了判定部３３はコア１が処理終了アドレスまで処理を実行したことを検出する。終了判定部３３は処理３の識別情報と終了を処理進度表更新部３１に通知するので、処理進度表更新部３１は処理３のステータスをＤｏｎｅに更新する（Ｓ２３０）。

図１１に示すように、コア１が処理３の処理終了アドレスまで実行すると、処理３のステータスはＤｏｎｅとなる。処理４，処理５についても同様に割り当てられ実行される。

すなわち、処理４のステータスは、処理２がDoneになるとReadyになり、コア２が処理４の実行を完了するとDoneになる。すると、処理５のステータスがReadyになるので、コア１が処理５の実行を開始することができる。そして、コア１が処理５の実行を完了すると、処理１，２のステータスがReadyになる。上記のように、処理５のステータスがProcessingになった時点で処理１，２のステータスをReadyとすれば、空いているコア２が処理１を実行することができ、並列度が向上する。

〔メインタスクと他のタスクとの競合について〕
コア５１の数に対し、ＯＳが割り当てるタスクの数がある程度多いと、メインタスクを実行していたコア５１が処理１〜５を途中で中断し、別のタスクを実行する必要も生じる。しかしこの場合でも、本実施形態のマルチコアプロセッサ２００は有効である。

図１２（ａ）は、コア１，２に対する処理１〜５と割込みタスクの割り当ての関係を示す図の一例である。処理分割分散装置１００は、ＯＳからの割り当てに関係なく、複数のコア１，２に処理を分散できるので、２つしかないコア１，２に処理１，２を割り当てることができる。コア１が処理１をコア２が処理２を実行している状態で、ＯＳが割込みタスクを起床した場合、コア１又はコア２（図ではコア２に）に割込みタスクをディスパッチする。これによりコア２は割込みタスクを実行するが、コア１は処理１の実行後、処理２には依存関係のない処理３を実行できる。

そして、コア２が割込みタスクを終了したら、ＯＳが処理２のコンテキストをコア２に復帰させるのでコア２は処理２を完了させることができる。なお、コア１が処理３を実行完了した後、処理２の実行が完了しないとコア１は処理４を実行できないが、換言すれば、処理３の後はコア１が空きコアになり、メインタスク以外のタスクをコア１が実行できるようになる。したがって、メインタスクと他のタスクとのリソースを共有しても、不都合は生じない。

なお、図１２（ａ）ではコア２が処理２の完了後、コア１が処理４を実行しているが、２つのコア１，２が空いている場合にどちらのコアが処理２を実行するか（ＯＳがどちらのコアに割り当てるか）は設計できる。

図１２（ｂ）は、コア１，２に対する処理１〜５と割込みタスクの割り当ての関係を示す図の別の一例である。コア２が割込みタスクを実行するところまでは図１２（ａ）と同じであるが、図１２（ｂ）ではコア２が実行する割込みタスクの実行時間が長い。しかしながら、このような場合も、処理分割分散装置１００が処理２をコア１に再割り当てすることで、処理を進行させることができる。

具体的には、処理分割分散装置１００がＯＳの割込みタスクの割り当てを監視し、ＯＳが退避したコンテキストを取得することで、処理２をコア１に再割り当てすることができる。再割り当てが可能であれば、以降は、処理分割分散装置１００が処理進度表１１に基づきReadyになった処理から順番にコア１に割り当てるので、シングルコアがメインタスクを実行する場合と同様に処理１〜５を完了させることができる。

〔処理分割分散装置を専用のコアに割り当てない場合〕
これまでは、固定のコアが処理分割分散装置１００の機能を提供するとしたが、タスクを実行するコアが処理分割分散装置１００の機能を提供することもできる。
図１３は、処理分割分散装置１００の機能ブロック図の一例を示す。図１３において図５と同一部について説明を省略する。図１３では機能ブロックの種類は図５と同じであるが、終了判定部３３の機能が異なっている。

まず、マルチコアプロセッサ２００の起動時に処理進度表更新部３１が処理進度表１１を初期化し、処理割り当て部３２が処理１，２を空きコアに割り当てるのは、上述したとおりである。そして、終了判定部３３は、コア自身が処理１〜５の終了を検出できるように、処理の直前に有効フラグと処理終了アドレスをコア１、２に設定する。コア１，２は、有効フラグがオンであることを条件に、ＰＣが処理終了アドレスと一致すると、割込みを発生する。この割込みによって、コア１，２は処理分割分散装置１００として起動する。

すると、終了判定部３３は、終了した処理の識別番号を処理進度表更新部３１に通知するので、処理進度表更新部３１は処理進度表１１の終了した処理のステータスをDoneに更新する。次に、処理進度表更新部３１は図８の手順を実行するので、処理依存のなくなった処理があればステータスにReadyが更新されることになる。

処理割り当て部３２は図９，１０の手順を実行するので、ステータスにReadyが更新された処理があれば、空きコアに処理を割り当てることができる。なお、ステータスにReadyが更新された処理がない場合でも、後に別のコアが割込みを発生したいずれかのタイミングで、必ずステータスにReadyが更新される処理が生じる。

図１４は、コア１，２が処理１〜５を実行するタイムチャート図の一例である。図１４ではメッシュ部が、処理分割分散装置１００がコアを占有したことを示し、丸数字は処理識別番号を示す。処理１，２の実行前に、処理分割分散装置１００は処理進度表１１を初期化すると共に処理１、２のステータスをReadyからProcessingに更新する。

コア１が処理１の処理終了アドレスまで実行すると、割込みによりコア１が処理分割分散装置１００として起動するので、処理進度表更新部３１は処理１のステータスをDoneに、依存関係のない処理３のステータスをReadyに更新する。また、処理割り当て部３２が処理３をコア１に割り当てることで、処理進度表更新部３１が処理３のステータスをProcessingに更新する。

コア２が処理２の処理終了アドレスまで実行すると、割込みによりコア２が処理分割分散装置１００として起動するので、処理進度表更新部３１は処理２のステータスをDoneに、依存関係のない処理４のステータスをReadyに更新する。また、処理割り当て部３２が処理４をコア２に割り当てることで、処理進度表更新部３１が処理４のステータスをProcessingに更新する。

次に、コア１が処理３の処理終了アドレスまで実行すると、割込みによりコア１が処理分割分散装置１００として起動するので、処理進度表更新部３１は処理３のステータスをDoneに更新する。しかし、処理３が終了した時点では処理４が終了していないので、処理進度表更新部３１は処理５のステータスをReadyに更新できない。

このため、次に、コア２が処理４の処理終了アドレスまで実行すると、割込みによりコア２が処理分割分散装置１００として起動するので、処理進度表更新部３１は処理４のステータスをDoneに、依存関係のない処理５のステータスをReadyに更新する。また、処理割り当て部３２が処理５をコア２に割り当てることで、処理進度表更新部３１が処理５のステータスをProcessingに更新する。

なお、コア２が処理５の処理終了アドレスまで実行した場合、処理１，２のステータスがReadyからProcessingにそれぞれ更新される。

したがって、専用のコアに処理分割分散装置１００が割り当てられない場合も、処理１〜５から処理分割分散装置１００の切り替えへのオーバーヘッドが生じるものの、処理分割分散装置１００がメインタスクの処理を分散させることができる。

以上説明したように、本実施形態のマルチコアプロセッサ２００は、既存のプログラムから適切な粒度の処理と依存関係を抽出することで、既存のプログラムをそのままマルチコアに適用でき、１つのメインタスクをマルチコアに負荷分散することができる。

１１ 処理進度表
１２ 処理モデル
２１ ＰＦ／ＯＳ
２２ アプリケーション
３１ 処理進度表更新部
３２ 処理割り当て部
３３ 終了判定部
６０ プログラム
７０ タスク制御プログラム
１００ 処理分割分散装置
２００ マルチコアプロセッサ

Claims (14)

1. 複数のコアと、アプリケーションが記憶された記憶手段と、を有するマルチコアプロセッサであって、
   前記アプリケーションを複数の処理に区分した際の処理間の依存関係を登録した処理依存関係情報と、
   各処理の進度状況が登録された進度状況登録テーブルと、
   前記進度状況が実行待ちの処理と前記処理依存関係情報において依存関係がある処理の実行完了が前記進度状況登録テーブルに登録されている場合、実行待ちの処理の前記進度状況を実行可能に更新する進度状況更新手段と、
   前記進度状況に実行可能と設定された処理を空きコアに割り当てる処理割り当て手段と、を有するマルチコアプロセッサ。
2. 各処理の処理終了アドレスが登録された処理終了アドレス情報と、
   コアが前記処理終了アドレスの命令を実行した場合に、処理の終了を検出する終了判定手段と、を有し、
   前記進度状況更新手段は、前記終了判定手段が終了を検出した処理の前記進度状況を実行完了に更新する、請求項１記載のマルチコアプロセッサ。
3. 各処理の処理開始アドレスが登録された処理開始アドレス情報、を有し、
   前記処理割り当て手段は、処理開始アドレスを割り当て対象のコアのプログラムカウンタに設定することで、処理を空きコアに割り当てる、
   請求項１又は２記載のマルチコアプロセッサ。
4. 前記進度状況登録テーブルには、複数のコアで並行に実行可能であり、かつ、前記アプリケーションの起動直後に実行される処理にエントリ情報が登録されている、
   請求項１〜３いずれか１項記載のマルチコアプロセッサ。
5. 前記進度状況更新手段は、全ての処理の前記進度状況が実行完了に設定された場合、前記エントリ情報が登録された処理の前記進度状況を実行可能に更新する、
   請求項４記載のマルチコアプロセッサ。
6. 前記進度状況更新手段は、全ての処理の前記進度状況が実行完了に設定される前であって、前記進度状況が実行中又は実行完了の処理のみになった場合、
   前記エントリ情報が登録された処理の前記進度状況を実行可能に更新する、
   請求項４記載のマルチコアプロセッサ。
7. 前記依存関係は、後の処理が前の処理のデータを使用するデータ依存、又は、後の処理が前の処理の処理結果を前提とする処理依存、である、
   請求項１〜６いずれか１項記載のマルチコアプロセッサ。
8. 前記処理割り当て手段は、複数の処理を異なるコアに割り当て、各コアが時間的に並行にそれぞれ処理を実行する、
   請求項７記載のマルチコアプロセッサ。
9. 前記進度状況更新手段は、前記処理割り当て手段により処理が割り当てられたコアが該処理を実行している間に、該処理の前記進度状況を更新する、
   請求項８記載のマルチコアプロセッサ。
10. 前記進度状況更新手段は、１つの処理の実行完了毎に、該処理を実行していたコアに割り当てられることで実現され、該処理の前記進度状況を更新する、
    請求項８記載のマルチコアプロセッサ。
11. 前記進度状況は、コア毎に、実行待ち、実行可能、実行中、実行完了の順に遷移する、
    請求項１〜１０いずれか１項記載のマルチコアプロセッサ。
12. 前記記憶手段にはアプリケーションの他にプログラムが記憶されており、
    前記アプリケーションと前記プログラムの優先順位に応じて、前記アプリケーションと前記プログラムを動的に前記コアに割り当てるスケジュール手段を有する、
    請求項１〜１１いずれか１項記載のマルチコアプロセッサ。
13. 複数のコアと、アプリケーションが記憶された記憶手段と、
    前記アプリケーションを複数の処理に区分した際の処理間の依存関係を登録した処理依存関係情報と、
    各処理の進度状況が登録された進度状況登録テーブルと、を有するマルチコアプロセッサの処理実行方法であって、
    進度状況更新手段が、前記進度状況が実行待ちの処理と前記処理依存関係情報において依存関係がある処理の実行完了が前記進度状況登録テーブルに登録されている場合、実行待ちの処理の前記進度状況を実行可能に更新するステップと、
    処理割り当て手段が、前記進度状況に実行可能と設定された処理を空きコアに割り当てるステップと、を有する処理実行方法。
14. 複数のコアと、アプリケーションが記憶された記憶手段と、
    前記アプリケーションを複数の処理に区分した際の処理間の依存関係を登録した処理依存関係情報と、
    各処理の進度状況が登録された進度状況登録テーブルと、を有するマルチコアプロセッサに、
    前記進度状況が実行待ちの処理と前記処理依存関係情報において依存関係がある処理の実行完了が前記進度状況登録テーブルに登録されている場合、実行待ちの処理の前記進度状況を実行可能に更新する進度状況更新ステップと、
    前記進度状況に実行可能と設定された処理を空きコアに割り当てる処理割り当てステップと、を実行させるプログラム。

Images