マルチコアプロセッサ
【課題】逐次処理用プログラムでも、ループ部分の繰り返し処理を並列に実行するマルチコアプロセッサの実現。
【解決手段】メインプロセッサ10を含む複数個のプロセッサエレメントPE20-1,20-N-1を含み、逐次処理プログラムを実行するマルチコアプロセッサであって、メインプロセッサは、ループ部分を検出するループ部分検出部11を含み、マルチコアプロセッサは、ループ部分を検出した時に、複数個のPEがループ部分を命令バッファにコピーし、ループカウンタの初期値を各PEごとにずらして格納し、更新量をPEの個数に応じて設定する展開制御部12と、を含み、いずれか１個のPEが終了通知を出力した際に，終了通知を出力したPEより前のループカウンタ値の処理を行っているすべてのPEの現在の処理の終了を待ち，終了通知を出力したPEより後ろのループカウンタ値の処理を行っているPEの処理を終了させた後，逐次処理のプログラムの処理を続行する。
【解決手段】メインプロセッサ10を含む複数個のプロセッサエレメントPE20-1,20-N-1を含み、逐次処理プログラムを実行するマルチコアプロセッサであって、メインプロセッサは、ループ部分を検出するループ部分検出部11を含み、マルチコアプロセッサは、ループ部分を検出した時に、複数個のPEがループ部分を命令バッファにコピーし、ループカウンタの初期値を各PEごとにずらして格納し、更新量をPEの個数に応じて設定する展開制御部12と、を含み、いずれか１個のPEが終了通知を出力した際に，終了通知を出力したPEより前のループカウンタ値の処理を行っているすべてのPEの現在の処理の終了を待ち，終了通知を出力したPEより後ろのループカウンタ値の処理を行っているPEの処理を終了させた後，逐次処理のプログラムの処理を続行する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチコアプロセッサに関する。
【背景技術】
【０００２】
処理の高速化を図るため、従来から複数のプロセッサを使用して処理を並列に実行する並列処理方法、および並列処理を実行するための複数のプロセッサを含む並列処理システムが各種提案されている。また、近年の半導体技術の集積度の向上により、複数個のプロセッサエレメントを含むマルチコアプロセッサが実現されている。
【０００３】
メディア処理，画像処理等においては，多数のデータに対して依存関係の無い処理を行うことが多い。具体的には、図１に示すような隣接する３×３の画素データを使用する画像のフィルタ処理の場合、各画素の演算処理は、他の画素の処理結果に対して依存関係が無いため、並列計算や計算順序の入れ替えは自由である。
【０００４】
図２は、上記のような処理を、通常のプロセッサ向けに記述した逐次処理用プログラムの例を示す。この演算は、各画素およびその隣接画素の画素データを変数とする演算で、画素位置を変化させながら同じ演算を繰り返すループ部分が含まれる。
【０００５】
このような複数のデータに１種類の処理を適用する場合に、繰り返し処理（イタレーション）方向に処理を並列に実行する並列処理方法として、ＳＩＭＤ(Single Instruction stream Multiple Data stream)法が知られている。ＳＩＭＤ法では内部に複数のプロセッサエレメントを含み、複数個のプロセッサエレメントが並列に１種類の処理を実行することにより、繰り返し処理（イタレーション）を並列に実行する。より具体的には１命令で多数のデータに対するロード・ストア・演算処理を記述することができ、命令を実行する装置は内部のパイプラインなどのリソースの許す限り、複数のデータを同時に処理する、または複数のデータをオーバーラップして処理することにより、並列処理を行う。
【０００６】
図３は、加算演算を繰り返すループ部分の処理をＳＩＭＤ法で実行する場合のプログラム例を示す。
【０００７】
ＳＩＭＤ法で処理を実行する場合、すなわちマルチコアプロセッサを動作させる場合には、図３に示すように、プログラムにおいて新たに定義されたＳＩＭＤ命令を使用しなければ、並列処理が行われないため高速化できない。そのため、プログラムを作成する容易性（プログラマビリティ）に関する問題がある。
【０００８】
また各入力データを各処理でどのようなパターンで参照するかについては、ＳＩＭＤ法の命令セットの形式に依存しており、処理したい演算パターンに合致する命令が無い場合、データを並び替える等の別の対策が必要になる。そのため、同様にプログラマビリティの問題が生じる。
【０００９】
図４および図５は、ＳＩＭＤ法で処理を行う場合の処理方法を説明する図である。
【００１０】
図４の（Ａ）は、図３の加算演算を実行する場合を示し、横軸が実行時間を、縦軸が回路規模（各演算ユニットのパイプライン段数）を示し、太線が１繰り返し処理における１データの処理の流れを示す。第１のＶＬＤは、ｉ番地のデータを各プロセッサエレメントの第１レジスタにロードする処理を示す。第２のＶＬＤは、ｊ番地のデータを各プロセッサエレメントの第２レジスタにロードする処理を示す。ＶＡＤＤは、第１レジスタのデータと第２レジスタのデータを加算して第３レジスタに格納する処理を示す。ＶＳＴは、第３レジスタのデータ（処理結果）をメモリのｏ番地に書き込む（格納する）処理を示す。
【００１１】
それぞれの処理はパイプライン的に処理される。パイプラインであるため前の段の処理が終わったデータに対して次の段の処理を適用することができる。
【００１２】
図４の（Ｂ）は図４の（Ａ）の各命令を実行するパイプラインの本数を４倍に増やしたものである。パイプラインの本数を増加すれば、所定時間内に処理できるデータ数は飛躍的に向上する。
図５は図４の（Ｂ）をデータ数方向を縦軸にとって示したものである。ＳＩＭＤ方式での実効的な並列度はパイプライン本数×パイプライン段数である。
【００１３】
また、複数のデータに１種類の処理を適用する場合に、繰り返し処理をオーバーラップして実行する並列処理方法として、アレイ方式が知られている．
【００１４】
図６は、加算演算、インクリメント（所定値増加）処理および比較処理からなる一連の処理を繰り返す処理をパイプライン方式で実行する場合のプログラム例を示す。
【００１５】
アレイ方式で実行する場合、すなわちアレイプロセッサを動作させる場合には、図５に示すように、逐次処理と同じ命令を用いることができるため、ＳＩＭＤ法の場合のような専用の命令を使わずに高速化を図ることができる。また、入力データの参照は逐次処理と同等に記述できるため、ＳＩＭＤ法より演算の自由度が高い。しかし、アレイ方式では、ループを構成する命令数以上の並列度を得ることができない。すなわち、プログラムを書き換えてループを構成する命令を増やさなければ、並列度を高くできないというスケーラビリティの問題がある。
【００１６】
図７は、パイプライン方式のプロセッサを使用する処理方法を説明する図である。
【００１７】
図７の（Ａ）は、図５の加算、インクリメントおよび比較の処理を実行する場合を示し、横軸が実行時間を、縦軸が回路規模（パイプライン段数）を示し、太線が繰り返し処理における１データの処理の流れを示す。１番目のＬＤは、ｉ番地のデータをプロセッサの第５レジスタにロードする処理を示す。２番目のＬＤは、ｊ番地のデータをプロセッサの第６レジスタにロードする処理を示す。ＡＤＤは、第５レジスタのデータと第６レジスタのデータを加算して第７レジスタに格納する処理を示す。ＳＴは、第７レジスタのデータ（処理結果）をメモリのｏ番地に書き込む（格納する）処理を示す。ＩＮＣは、ｋ番地のデータを１増加する処理を示す。ＣＭＰは、１増加したｋ番地のデータを所定値と比較する処理を示す。
【００１８】
図７の（Ａ）に示すように、１個のデータに対する一連の処理が終了する前に、次のデータに対する処理が開始される。
【００１９】
図７の（Ｂ）は図７（Ａ）を縦軸をデータ数（ループのイタレーション回数）として示したものである。並列度はデータの待ち合わせのためのＮＯＰを含めたループを構成する命令数によって定まる。
【００２０】
このように、アレイ方式のプロセッサは、十分な並列度を得るのが難しいという問題があった。また、ＳＩＭＤ法を実行するマルチプロセッサは、プログラムにおいてＳＩＭＤ命令、すなわちマルチプロセッサ命令を使用しなければ、高速化できないという問題があった。
【００２１】
そのため、広く使用される逐次処理用プログラムで動作可能でかつループ部分の繰り返し処理を並列化して高速化が図れるマルチコアプロセッサが要望されている。
【先行技術文献】
【特許文献】
【００２２】
【特許文献１】特開２０００−３５３２３７号公報
【特許文献２】特開２００３−０９１４２２号公報
【特許文献３】特開２００６−３３０８１３号公報
【発明の概要】
【発明が解決しようとする課題】
【００２３】
実施形態は、逐次処理用プログラムを実行する場合でも、ループ部分の繰り返し処理を並列に実行するマルチコアプロセッサを記載する。
【課題を解決するための手段】
【００２４】
実施形態の第１の態様は、メインプロセッサを含む複数個のプロセッサエレメントを含み、逐次処理プログラムを実行するマルチコアプロセッサであって、メインプロセッサは、逐次処理プログラムに含まれる並列化可能なループ部分を検出するループ部分検出部を含み、マルチコアプロセッサは、ループ部分検出部がループ部分を検出した時に、複数個のプロセッサエレメントがループ部分を命令バッファにコピーするように制御すると共に、複数個のプロセッサエレメントのループカウンタの初期値を各プロセッサエレメントごとにずらして格納し、さらに複数個のプロセッサエレメントのループカウンタの更新量を複数個のプロセッサエレメントの個数に応じて設定する展開制御部と、を含み、メインプロセッサは、逐次処理プログラムに含まれるループ部分の処理を、複数個のプロセッサエレメントに実行させ、複数個のプロセッサエレメントは、ループ外処理への変更が発生したら終了通知を出力し、メインプロセッサは、前記複数個のプロセッサエレメントのうちのいずれか１個が前記終了通知を出力した際に、終了通知を出力したプロセッサエレメントより前のループカウンタ値に対して処理を行っているすべてのプロセッサエレメントの現在処理中のループ部分の終了を待ち、終了通知を出力したプロセッサエレメントより後ろのループカウンタ値に対して処理を行っているプロセッサエレメントのループ部分の処理を終了させた後、逐次処理のプログラムの処理を続行する。
【発明の効果】
【００２５】
実施形態によれば、逐次処理用プログラムでも、ループ部分の繰り返し処理を並列に実行するマルチコアプロセッサが実現される。
【図面の簡単な説明】
【００２６】
【図１】図１は、メディア処理，画像処理等における多数のデータに対して依存関係の無い処理を説明する図である。
【図２】図２は、通常のプロセッサ向けに記述した逐次処理用プログラムの例を示す。
【図３】図３は、加算演算を繰り返すループ部分の処理をＳＩＭＤ法で実行する場合のプログラム例を示す。
【図４】図４は、ＳＩＭＤ法で処理を行う場合の処理方法を説明する図である。
【図５】図５は、ＳＩＭＤ法で処理を行う場合の処理方法を説明する図である。
【図６】図６は、加算演算、インクリメント（所定値増加）処理および比較処理からなる一連の処理を繰り返す処理をアレイ方式で実行する場合のプログラム例を示す。
【図７】図７は、アレイ方式のプロセッサを使用する処理方法を説明する図である。
【図８】図８は、第１実施形態のマルチコアプロセッサの構成を示す図である。
【図９】図９は、プロセッサエレメント（ＰＥ）の１個の構成を示す図である。
【図１０】図１０は、展開制御部の動作を説明する図である。
【図１１】図１１は、第１実施形態における命令および内部状態のコピー例を示す図である。
【図１２】図１２は、終了制御部の動作を説明する図である。
【図１３】図１３は、第１実施形態のマルチコアプロセッサが、ループ部分の繰り返し処理を並列に行う動作を説明する図である。
【図１４】図１４は、第２実施形態のマルチコアプロセッサの構成を示す図である。
【図１５】図１５は、ストリームバッファの構成を示す図である。
【図１６】図１６は、ストリームバッファの動作を示すフローチャートである。
【図１７】図１７は、ストアバッファの構成を示す図である。
【図１８】図１８は、ストアバッファの動作を示すフローチャートである。
【図１９】図１９は、第２実施形態のマルチコアプロセッサが、ループ部分の繰り返し処理を並列に行う動作を説明する図である。
【図２０】図２０は、第３実施形態のマルチコアプロセッサの構成を示す図である。
【発明を実施するための形態】
【００２７】
図８は、第１実施形態のマルチコアプロセッサの構成を示す図である。
【００２８】
図８に示すように、第１実施形態のマルチコアプロセッサは、メインプロセッサ１０と、Ｎ個のプロセッサエレメント（ＰＥ）２０−０〜２０−Ｎ−１と、展開制御部１２と、終了制御部１３と、主記憶３０と、バス３１と、を含む。
【００２９】
メインプロセッサ１０は、逐次処理プログラムＡを実行するための従来例と同様の構成を含むが、図示は省略している。メインプロセッサ１０は、逐次処理プログラムＡ中のループ部分を検出するループ部分検出部１１と、レジスタファイル１４と、を、含む。ループ部分検出部１１は、ハードウェアまたはソフトウェアで形成することができる。また、レジスタファイル１４は、逐次処理プログラムＡを実行するためのレジスタで、従来例と同様の構成を含む。
【００３０】
展開制御部１２および終了制御部１３も、ハードウェアまたはソフトウェアで形成することができる。なお、ハードウェアまたはソフトウェアの中間的な形式でファームウェアと呼ばれる形で、これらを形成することも可能である。
【００３１】
図８において破線で示すように、展開制御部１２および終了制御部１３の少なくとも一方がメインプロセッサ１０’に含まれるようにしてもよい。
【００３２】
プロセッサエレメント（ＰＥ）２０−０〜２０−Ｎ−１は、同じ構成を含み、メインプロセッサ１０と同じ構成を含むようにしてもよい。
【００３３】
図９は、プロセッサエレメント（ＰＥ）２０−０〜２０−Ｎ−１の１個のＰＥ２０の構成を示す図である。
【００３４】
図９に示すように、ＰＥ２０は、命令を解釈実行する命令解釈部２２と、複数の演算器２３と、レジスタファイル２４と、ロードストアユニット２６と、を含むこれまでの構成に加えて、命令バッファ２１と、終了条件判定部２５と、を含む。複数の演算器２３は、命令をパイプライン方式で処理する。
【００３５】
命令バッファ２１は、展開制御部１２を介してメインプロセッサ１０から供給されるループ長分の命令を格納する。
【００３６】
レジスタファイル２４は、展開制御部１２を介してメインプロセッサ１０から供給されるレジスタ初期値を格納し、繰り返し処理終了時には、最終値を出力する。
【００３７】
終了条件判定部２５は、命令バッファ２１に未格納の命令実行を検出することにより，ループ終了を判定する。
【００３８】
図１０は、展開制御部１２の動作を説明する図である。
【００３９】
メインプロセッサ１０が逐次処理プログラムＢを行っている時に、ループ部分検出部１１が並列処理可能なループ部分を検出すると、ループ部分を構成する命令Ｃ１を、各プロセッサエレメント（ＰＥ）の命令バッファ２１に、メインプロセッサ１０の内部状態を各ＰＥにコピーする。
【００４０】
ここで、ループ部分の処理をＮ個のＰＥで並列に実行する場合、各ＰＥで実行する処理をＮずつずらす必要がある。そのため、命令をコピーする時に、ループ部分を構成する命令のうち、ループカウンタ等を更新する命令について、図１０に示すように、１回あたりの更新量を、命令をコピーするＰＥ数に従って変更する。
【００４１】
具体的には、ループ部分の各繰り返し命令で、ループカウンタｋをｋ＝ｋ＋２という形の更新命令である時、Ｎ個のＰＥを使用する場合、この更新命令はｋ＝ｋ＋２Ｎに変更される。
【００４２】
また、メインプロセッサ１０の内部状態をレジスタファイル２４にコピーする時に、上ループカウンタ等の初期値を各ＰＥにずらしながら格納する。
【００４３】
具体的には、ループカウンタｋ＝０が初期値であり、各繰り返し処理においてｋ＝ｋ＋２という形の更新命令がある場合、ＰＥ２０−０にはｋ＝０、ＰＥ２０−１にはｋ＝２、ＰＥ２０−２にはｋ＝４の順にループカウンタｋの初期値を分配する。
【００４４】
より具体的には、ループカウンタはプロセッサのレジスタであり、内部状態のコピーとは、メインプロセッサ１０の全レジスタ値を各ＰＥに分配することである。
【００４５】
図１１は、第１実施形態における命令および内部状態のコピー例を示す図である。ループカウンタの初期値および更新量が、上記のようにコピーされる。
【００４６】
上記のように、各ＰＥにループ部分の命令およびメインプロセッサ１０の内部状態をコピーするループ展開制御完了後に、各プロセッサエレメントを動作させることにより、ループ部分の処理が複数のＰＥで並列に実行される。これにより、ループ部分の繰り返し処理は、ＰＥ数の並列度で実行される。
【００４７】
図１２は、終了制御部１３の動作を説明する図である。
【００４８】
複数のＰＥは、終了条件判定部２５がループ外処理への変更が発生したら終了通知を出力する。ループ部分Ｄの繰り返し処理（イタレーション）の並列実行中に、いずれかのＰＥ２０−Ｐの終了条件判定部２５が、命令バッファ２１に未格納の命令実行を検出すると、言い換えれば、次の実行命令がループ範囲外であることを検出すると、ループ部分の処理終了と判定して、終了制御を開始する。ここでは、上記のループの外側への分岐を行ったループの繰り返し処理を最終繰り返し処理と定義する。
【００４９】
最終繰り返し処理よりループカウンタ値が先行を示している繰り返し処理は、そのループの最後まで実行を完了する必要がある。また、最終繰り返し処理よりループカウンタ値が後の繰り返し処理は、逐次処理では実行してはならない処理であるため、即時に停止させる。最終繰り返し処理を実行していたＰＥ２０−Ｐのレジスタファイル２４に保持されている内部状態を、メインプロセッサ１０に反映させる。そして、メインプロセッサ１０は、すべてのＰＥが終了通知を出力した後、実行したループ部分に続く逐次処理を再開する。
【００５０】
上記の処理は、ループ部分の繰り返し処理がすべて終了した場合の動作である。第１実施形態のマルチコアプロセッサは、ループ部分の繰り返し処理を並列実行中に、割り込み等の外部からの中断要求を受け付けられるようになっている。中断が要求された場合、メインプロセッサ１０が、中断要求があったことを終了制御部１３に通知する。通知を受けた終了制御部１３は、各ＰＥに割り当てられた現在実行中の繰り返し処理が完了するまで待つ。このとき繰り返し処理を完了したプロセッサエレメントが新たな繰り返し処理を開始しないように抑止する。繰り返し処理を完了したＰＥのうち、ループカウンタ値が最も先に進んでいるＰＥの内部状態をレジスタファイル２４から読み出し、ループ処理位置レジスタ１４に格納する。
【００５１】
上記の動作完了後、メインプロセッサ１０が割り込みハンドラ等に制御を移すなどして、外部から要求された処理を行う。上記のループの中断制御はループの終了制御と同じ仕組みで実現することができる。
【００５２】
中断したループの再開は、ループ処理位置レジスタ１４に格納された中断時点でのループカウンタ値を初期値として、再度ループの展開制御を行うことで実現できる。
ここで、メインプロセッサ１０は、内部状態を示すレジスタファイル１４に書き込みを行うとオンとなるフラグを含む。複数のＰＥ２０−０〜２０−Ｎ−１も、内部状態を示すレジスタファイル２４に書き込みを行うとオンとなるフラグを含む。これらのフラグは、展開制御部１２が複数のＰＥに設定動作を行うとすべてオフとなり、例えばプログラムカウンタを更新するなどして内部状態を変化させるとオンとなる。終了制御部１３は、終了制御動作時に、最終の繰り返し処理を実行したＰＥから順に繰り返し処理を分配した方向とは逆方向にＰＥのフラグを調べてメインプロセッサのフラグと比較する。メインプロセッサ１０のフラグがオフであるのに、対応するＰＥのレジスタがオンである場合には、メインプロセッサ１０のフラグをオンすることにより、先頭のステップ位置をメインプロセッサ１０のレジスタファイル１４に設定する。
【００５３】
図１３は、第１実施形態のマルチコアプロセッサが、図１０に示したループ部分の繰り返し処理（イタレーション）を並列に行う動作を説明する図である。ここでは、ＰＥが４個の例を示している。
【００５４】
図１３の（Ａ）に示すように、４個のＰＥが、ロード、ロード、加算、ストア（格納）、インクリメント、比較およびループ継続判定の一連の繰り返し処理（イタレーション）を、並列に実行する。ＰＥ数を増加すると、単位時間に実行可能な繰り返し処理数が増加する。
【００５５】
図１３の（Ｂ）は、処理時間と、繰り返し処理数（イタレーション数）、すなわち処理データ数の関係を示す図である。ＰＥ数を増加すると、すなわち並列度を高くすると、その分処理データ数が増加する。具体的には、ＰＥ数がＮ個であれば、同一のループを逐次実行した場合と比較してＮ倍高速化できる。
【００５６】
図１４は、第２実施形態のマルチコアプロセッサの構成を示す図である。第２実施形態のマルチコアプロセッサは、第１実施形態のマルチコアプロセッサと類似の構成を含み、プリフェッチ４１と、ストリームバッファ４２と、ストアバッファ４３と、を更に含むことが異なる。したがって、メインプロセッサ１０は、ループ部分検出部１１およびレジスタファイル１４を含むが図示は省略している。また、展開制御部１２および終了制御部１３は、メインプロセッサ１０に含ませることも可能である。以下、第１実施例と異なる部分についてのみ説明する。
【００５７】
図１５は、ストリームバッファ４２の構成を示す図である。
【００５８】
主記憶３０からプロセッサエレメント（ＰＥ）方向への主記憶アクセス、すなわちＰＥ２０−０〜２０−Ｎ−１が主記憶３０のデータを読み取る時のアクセスの効率化を実現するために、リードオンリのストリームバッファ４２を設ける。ストリームバッファ４２は、各ＰＥ間の共有メモリ形式のキャッシュメモリであり、各ＰＥは共有のキャッシュメモリにアクセスするという方法をとる。
【００５９】
図１５に示すように、ストリームバッファ４２は、調停回路５１と、書き込み制御回路５２と、内部キャッシュメモリ５３と、を含む。図１５では、２個のプロセッサエレメント（ＰＥ）２０−０および２０−１が調停回路５１に接続されているように示しているが、実際にはすべてのプロセッサエレメント（ＰＥ）２０−０〜２０−Ｎ−１が接続されている。プリフェッチ４１は、メインプロセッサ１０からのプリフェッチ指令４０に応じて、処理対象のループ部分が使用するデータを主記憶３０からストリームバッファ４２に書き込む処理を行う。共有形式のキャッシュメモリについては広く知られているので、詳しい説明は省略する。
【００６０】
図１５に示したストリームバッファ４２を使用して、対象とするループ処理が扱うデータを、アクセスする順番にストリームバッファ４２に格納することにより、主記憶３０へのアクセスと演算処理を同時に行くことが可能である。
【００６１】
図１６は、ストリームバッファ４２の動作を示すフローチャートであり、左側のＳ１１からＳ１８は各ＰＥの動作を、右側のＳ２１からＳ２６はストリームバッファ４２における動作を示す。
【００６２】
ループ部分の展開および並列実行に先立って、メインプロセッサ１０は、対象とするループ処理が扱うデータのアクセスパターンを、プリフェッチ４１に指示する。これに応じて、プリフェッチ４１は、主記憶３０から指定されたデータをストリームバッファ４２に転送する。
【００６３】
ステップＳ１１で、各ＰＥ２０は、ループ部分の繰り返し処理を実行する。
【００６４】
ステップＳ１２で、処理を実行するのにデータをＰＥ内にロードする必要があるか否かを判定し、なければステップＳ１６に進み、あればステップＳ１３に進む。
【００６５】
ステップ１３では、ストリームバッファ４２に、データの格納アドレスを通信することにより必要なデータをロードするように要求（リクエスト）する。
【００６６】
ステップＳ１４では、データのロード（送信）が完了したかを判定し、完了すればステップＳ１６に進み、完了していなければステップＳ１５に進み、データのロード完了まで待機し、完了したらステップＳ１６に進む。したがって、キャッシュミスが発生した場合には、ＰＥ２０は、処理を停止して待機した状態になり、キャッシュミスが解消された時に動作を再開する。
【００６７】
ステップＳ１６では、終了条件判定部２５が、終了条件を満たすかを判定し、満たしていなければステップＳ１８に進み、満たしていればステップＳ１７に進む。
【００６８】
ステップＳ１７では、終了通知を終了制御部１３に出力して処理を終了する。
【００６９】
ステップＳ１８では、終了制御部１３から終了通知が出されているかを判定し、終了通知が出されていれば処理を終了し、出されていなければステップＳ１１に戻る。
【００７０】
したがって、キャッシュミスが発生しない状態では、各ＰＥはループ部分の繰り返し処理を続ける。
【００７１】
ステップＳ１３でロードするように要求されたデータがストリームバッファ４２に存在する場合には、短時間のうちにデータが送信されるが、要求されたデータがストリームバッファ４２に存在しない場合には、キャッシュミスが発生する。キャッシュミスの場合には、データを受信するまでの時間が長くなる。したがって、キャッシュミスが発生した場合には、ＰＥ２０は、ステップＳ１５で待機する時間が長くなり、処理を停止してキャッシュミスが解消された時に動作を再開することになる。
【００７２】
ストリームバッファ４２に必要なデータが存在しない場合はキャッシュミスの状態であり、プリフェッチ４１は、必要なデータを主記憶３０からにストリームバッファ４２に転送する。この動作をプリフェッチ処理と称する。また、ストリームバッファ４２は、各ＰＥからのロード要求に応じて、ストリームバッファ４２内のデータを各ＰＥに送信するこれをロード処理と称する。もし、各ＰＥからロード要求されたデータがストリームバッファ４２に存在しない場合はキャッシュミスの状態であり、プリフェッチ処理を実行する必要がある。
【００７３】
ステップＳ２１で、ストリームバッファ４２は、要求がプリフェッチ処理かロード処理かを判定し、プリフェッチ処理の場合にはステップＳ２２に進み、ロード処理の場合にはステップＳ２３に進む。
【００７４】
ステップＳ２２では、プリフェッチ４１が主記憶３０のデータをストリームバッファ４２の内部キャッシュメモリ５３に転送する。
【００７５】
ステップＳ２３では、ロード処理で要求されたデータがストリームバッファ４２の内部キャッシュメモリ５３にあるか否かを判定し、あればステップＳ２５に進み、無ければステップＳ２４に進む。
【００７６】
ステップＳ２４では、キャッシュミスの状態なので、プリフェッチ４１が主記憶３０のデータをストリームバッファ４２の内部キャッシュメモリ５３に転送するように要求し、データが供給されるまで待機し、データが供給されたら、ステップＳ２５に進む。
【００７７】
ステップＳ２５では、ストリームバッファ４２の内部キャッシュメモリ５３からロード要求されたデータを読み出す。
【００７８】
ステップＳ２６では、ストリームバッファ４２の内部キャッシュメモリ５３から読み出したデータを要求したＰＥに送信し、ステップＳ２１に戻る。
【００７９】
以上説明したように、プリフェッチしたデータは、各ＰＥ間で共有のストリームバッファ４２に格納するため、各ＰＥ間で共有されるデータについても１回の主記憶アクセスで取得可能であり、主記憶アクセスが効率化される。
【００８０】
図１７は、ストアバッファ４３の構成を示す図である。
【００８１】
第２実施形態では、プロセッサエレメント（ＰＥ）から主記憶３０方向への主記憶アクセスの効率化を実現するために、各ＰＥ２０−０〜２０−Ｎ−１は書込動作（ストア）発生時に直接主記憶３０に書き込むのではなく、ストアバッファ４３を介してデータを書き込む方法をとる。
【００８２】
図１７に示すように、ストリームバッファ４２は、調停回路６１と、書き込み制御回路６２と、書き込み分配回路６３と、複数個のエントリ６４−０〜６４−Ｎ−１と、書き込み合成回路６５と、を含む。図１７では、２個のプロセッサエレメント（ＰＥ）２０−０および２０−１が調停回路６１に接続されているように示しているが、実際にはすべてのプロセッサエレメント（ＰＥ）２０−０〜２０−Ｎ−１が接続されている。
【００８３】
書き込み制御回路６２は、各ＰＥから出力される書き込みアドレスに基づいて、書き込み分配回路６３がＮ個のエントリ６４−０〜６４−Ｎ−１のいずれかを選択し、ＰＥから出力されたアドレスとデータの組を、選択したエントリ内に格納するように制御する。
【００８４】
書き込み制御回路６２は、１エントリが満たされたタイミングで、１エントリ単位で主記憶３０への書き込みアクセスを行い、書き込みアクセスを行ったエントリを解放する。
【００８５】
１エントリ内に格納されるデータが、主記憶３０上で連続したアドレスとなるように、アドレスに基づいたエントリ選択を行うことにより、エントリの内容を主記憶３０に書き込む際に、バースト転送等の効率的なアクセスが可能となる。
【００８６】
また、ループの終了時には、最終繰り返し処理を実行したＰＥからの指示に基づき，ストアバッファ４３内のストアデータ格納済みエントリ内のデータをすべて主記憶に書き込むというフラッシュ動作を行ことにより、ＰＥがストアした全データが主記憶３０に書き込まれることを保証する。
【００８７】
図１８は、ストアバッファ４３の動作を示すフローチャートであり、左側のＳ３１からＳ３８は各ＰＥの動作を、右側のＳ４１からＳ４７およびＳ５１からＳ５３はストアバッファ４３における動作を示す。
【００８８】
ステップＳ３１で、各ＰＥ２０は、ループ部分の繰り返し処理を実行する。
【００８９】
ステップＳ３２で、実行した処理の結果、ストアする（書き込む）データが発生したか否かを判定し、発生しなければステップＳ３６に進み、発生していればステップＳ３３に進む。
【００９０】
ステップ３３では、ストアバッファ４３の所望のエントリが満杯（フル）であるか否かを判定し、フルであればステップＳ３４に進み、空きがあればステップＳ３５に進む。
【００９１】
ステップＳ３４では、ストアバッファ４３の所望のエントリが空くまで待機し、ストアバッファ４３から空いたことが通信されたらステップＳ３５に進む。
【００９２】
ステップＳ３５では、ストアバッファ４３に対して、データのストア処理を要求（リクエスト）し、データおよびアドレスをストアバッファ４３に送信する。
【００９３】
ステップＳ３６では、終了条件判定部２５が、終了条件を満たすかを判定し、満たしていなければステップＳ３８に進み、満たしていればステップＳ３７に進む。
【００９４】
ステップＳ３７では、終了通知を終了制御部１３に出力すると共に、ストアバッファ４３にフラッシュ処理を要求して処理を終了する。
【００９５】
ステップＳ３８では、終了制御部１３から終了通知が出されているかを判定し、終了通知が出されていれば処理を終了し、出されていなければステップＳ３１に戻る。
【００９６】
次に、ストアバッファ４３における動作を説明する。
【００９７】
ステップＳ４１で、ストリームバッファ４２は、要求がストア処理かフラッシュ処理かを判定し、ストア処理の場合にはステップＳ４２に進み、フラッシュ処理の場合にはステップＳ５１に進む。
【００９８】
ステップＳ４２では、所望のエントリが確保されているかを判定し、確保されていなければステップＳ４３に進み、確保されていればステップＳ４４に進む。
【００９９】
ステップＳ４３では、エントリを確保する。
【０１００】
ステップＳ４４では、確保済みのエントリに、ＰＥから送信されたデータおよびアドレスを格納する。
【０１０１】
ステップＳ４５では、格納先のエントリが満杯であるか否かを判定し、満杯であればステップＳ４６に進み、満杯でなければステップＳ４１に戻る。
【０１０２】
ステップＳ４６では、満杯のエントリのアドレスで主記憶３０にアクセスして、データを書き込む。
【０１０３】
ステップＳ４７では、出力（読み出し）が行われた上記のエントリが解放され、エントリの解放をＰＥに通知し、ステップＳ４１に戻る。
【０１０４】
一方、ステップＳ４１で、フラッシュ処理と判定された時には、ステップＳ５１で、格納隅のエントリがあるか否かを判定し、あればステップＳ５２に進み、無ければ終了する。
【０１０５】
ステップＳ５２では、未格納のエントリのアドレスで主記憶３０にアクセスして、データを書き込む。
【０１０６】
ステップＳ５３では、出力（読み出し）が行われた上記のエントリが解放され、ステップＳ５１に戻る。以下、未格納のエントリのすべてのデータが主記憶３０に書き込まれるまでこの処理を繰り返す。
【０１０７】
以上説明したように、第２実施形態では、ループカウンタ値をずらしたものを並列実行しているため、ループ自体が元々メモリアクセスの局所性を有しており、並列実行している各ＰＥがメモリ中の近い領域にアクセスする。このため、各ＰＥが主記憶から読んだ値が周辺のプロセッサエレメントでも再利用できるため、主記憶アクセスが効率化される。
【０１０８】
さらに、ループの各繰り返し処理が、同一のデータを主記憶から読み出す特性を持ったループ処理の場合、プログラム中に記述したプリフェッチ指令または予測機構に基づいて、プリフェッチが各繰り返し処理に必要なデータを主記憶から、複数のＰＥ間に共有のストリームバッファに読み出しておくことにより、さらに読み出しアクセスの効率化を図ることができる。
【０１０９】
また、ループの各繰り返し処理から主記憶への書き込みアドレスに局所性がある場合、ＰＥ間で共有のストアバッファに、書き込みアドレスとデータを格納し、ほかのＰＥの書き込みデータとまとめることにより、書き込みアクセスの効率化を図ることができる。
【０１１０】
図１９は、第２実施形態のマルチコアプロセッサが、図１１に示したループ部分の繰り返し処理を並列に行う動作を説明する図である。ここでは、ＰＥが４個の例を示している。
【０１１１】
図１９に示すように、ロード、演算およびストアを含む一連の繰り返し処理を、複数のデータについて行う場合を考える。１回の繰り返し処理の命令実行時間をＴ、データ数をＰとすると、逐次処理では１つの繰り返し処理をＰ回繰り返すので、処理時間はＴ×Ｐになる。
【０１１２】
これに対して、ＰＥを４個使用して繰り返し処理を並列に行う場合を考える。ただし、繰り返し処理を並列に行うには、並列に行う４つの処理に必要な４組のデータも並列に供給可能で、処理結果の４組のデータも並列に出力可能であることが必要である。もし、データの供給および出力が、同じ速度で並列に行えないと、４倍の速度で処理することはできない。
【０１１３】
第２実施形態では、上記のように、ストリームバッファ４２およびストアバッファ４３を使用して、ＰＥへのデータ供給およびＰＥからのデータ出力を並列に行えるようにしている。
【０１１４】
図１９に示すように、入力データが画像データの場合、４個のＰＥは、１画素ずつずれた隣接画素群のデータを処理に使用する。このような隣接画素群のデータは、スキャンなどにより、主記憶に連続してアクセスして読み出すことが可能である。そこで、プリフェッチ処理で、このような隣接画素群のデータを連続して読み出して、ストリームバッファ４２に格納する。この場合、１画素ずつずらすので、図１９に示すように、タイムラグが発生する。４個のＰＥ用のデータが揃ったら、４個のＰＥは同時に並列で４つの画素についてそれぞれ処理を行う。４個のＰＥが処理を行っている間に、次の４つずれた画素の隣接画素群のデータを供給して準備しておく。
【０１１５】
一方、４個のＰＥで処理した結果である出力データは、並列にストアバッファに出力され、次のデータが出力されるまでに主記憶に書き込まれる。この場合も、１画素ずつずれてデータが書き込まれるので、画像をスキャンするように書き込むことになる。
【０１１６】
いずれにしろ、以上のようにして、ループ部分の処理を、ＰＥの個数、すなわち４倍に近い高速で行えるようになる。
【０１１７】
図２０は、第３実施形態のマルチコアプロセッサの構成を示す図である。第３実施形態のマルチコアプロセッサは、対称な構成の複数のプロセッサエレメント（ＰＥ）２０−０〜２０−Ｎ−１を含み、いずれかのＰＥがメインプロセッサとして動作することが、第２実施形態のマルチコアプロセッサと異なり、他の部分は同じである。
【０１１８】
各ＰＥは、展開制御部１２、終了制御部１３、命令バッファ２１および終了条件検出回路２５を含み、いずれもメインプロセッサとして動作可能である。
【０１１９】
いずれかのＰＥがメインプロセッサとして動作し、並列処理可能なループを検出した時に、メインプロセッサとして動作するＰＥの展開制御部１２が動作し、汎用のバス３１を介して他のＰＥに命令および内部状態を分配する。各ＰＥは、それぞれ繰り返し処理の１つの処理を並列に実行し、いずれかのＰＥがループの終了条件を検出した際に、メインプロセッサの終了制御への終了通知を行う。終了通知を受けたメインプロセッサの終了制御は、最終繰り返し処理より後の処理返し処理を実行しているＰＥを停止させ、また最終繰り返し処理を実行していたＰＥより内部状態のデータを得て、自分のＰＥの内部状態に反映させた後、逐次実行に復帰する。
【０１２０】
以上第１から第３実施形態を説明したが、各実施形態で説明した事項は、他の実施形態に適用することが可能であり、説明した以外にも各種の変形例が可能である。
【０１２１】
例えば、第３実施形態では、Ｎ個のＰＥが設けられている場合、Ｎ個のＰＥをすべてループ部分の繰り返し処理に使用したが、一部のＰＥを使用し、残りのＰＥは他の処理に使用することも可能である。メインプロセッサを含む複数のＰＥが、独立したスレッドを実行している時に、あるＰＥが並列実行可能なループ部分を検出し、他のＰＥにループ部分の繰り返し処理を分担して並列に実行するように要求する。展開要求を受けたＰＥが、展開要求元のスレッドより高い優先度のスレッドを実行している場合には、展開要求を拒否し、独立してスレッド実行を続行し、より低い優先度のスレッドを実行している場合のみ展開要求を受け付ける。そして、展開要求を出したＰＥおよび展開要求を受け付けたＰＥにのみループ部分を展開して、各繰り返し処理（イタレーション）の並列実行を行う。
【０１２２】
以上説明したように、実施形態によれば、ＳＩＭＤ法を実行するマルチプロセッサ（マルチコアプロセッサ）と比較して、ループを構成する命令は逐次実行の命令のままでよく、入力データの参照、入力データ間の演算の自由度が高いためプログラマビリティが高い。
【０１２３】
また、パイプライン方式のプロセッサでは最大の並列度がループの長さに依存していたのに対して、実施形態のマルチコアプロセッサではプロセッサエレメント（ＰＥ）数を増加させることで、並列度を向上させることができ、スケーラビリティを高くすることが可能である。
【０１２４】
以上、実施形態を説明したが、ここに記載したすべての例や条件は、発明および技術に適用する発明の概念の理解を助ける目的で記載されたものであり、特に記載された例や条件は発明の範囲を制限することを意図するものではなく、明細書のそのような例の構成は発明の利点および欠点を示すものではない。発明の実施形態を詳細に記載したが、各種の変更、置き換え、変形が発明の精神および範囲を逸脱することなく行えることが理解されるべきである。
【０１２５】
以下、実施形態に関し、更に以下の付記を開示する。
（付記１）
メインプロセッサを含む複数個のプロセッサエレメントを備え、逐次処理プログラムを実行するマルチコアプロセッサであって、
前記メインプロセッサは、前記逐次処理プログラムに含まれる並列化可能なループ部分を検出するループ部分検出部を備え、
前記マルチコアプロセッサは、前記ループ部分検出部が前記ループ部分を検出した時に、前記複数個のプロセッサエレメントが前記ループ部分を命令バッファにコピーするように制御すると共に、前記複数個のプロセッサエレメントのループカウンタの初期値を各プロセッサエレメントごとにずらして格納し、さらに前記複数個のプロセッサエレメントのループカウンタの更新量を前記複数個のプロセッサエレメントの個数に応じて設定する展開制御部と、を備え、
前記メインプロセッサは、前記逐次処理プログラムに含まれる前記ループ部分の処理を、前記複数個のプロセッサエレメントに実行させ、
前記複数個のプロセッサエレメントは、ループ外処理への変更が発生したら終了通知を出力し、
前記メインプロセッサは、前記複数個のプロセッサエレメントのうちのいずれか１個が前記終了通知を出力した際に、終了通知を出力したプロセッサエレメントより前のループカウンタ値に対して処理を行っているすべてのプロセッサエレメントの現在処理中のループ部分の終了を待ち、終了通知を出力したプロセッサエレメントより後ろのループカウンタ値に対して処理を行っているプロセッサエレメントのループ部分の処理を終了させ、前記逐次処理プログラムの処理を続行することを特徴とするマルチコアプロセッサ。
（付記２）
前記メインプロセッサが、実行中の前記ループ部分の処理の中断を指示すると、前記ループ部分の処理を実行中の前記複数個のプロセッサエレメントは、実行中の前記ループ部分の１ステップを完了すると前記終了通知を出力すると共に処理を停止し、
前記マルチコアプロセッサは、すべての前記複数個のプロセッサエレメントからの前記終了通知を受信した後、前記複数個のプロセッサエレメントの内部状態の情報を取得して、前記ループ部分の処理のうち完了している先頭のステップ位置を検出する終了制御部を備え、
前記メインプロセッサは、前記終了制御部の検出した前記先頭のステップ位置を記憶する内部状態を示すレジスタを備え、中断した前記ループ部分の処理を再開する時には、前記ループ処理位置レジスタに記憶された前記先頭のステップ位置の次から前記ループ部分の処理を実行するように、前記展開制御部に情報を提供する付記１に記載のマルチコアプロセッサ。
（付記３）
前記メインプロセッサおよび前記複数個のプロセッサエレメントは、内部状態を示すレジスタに書き込みを行うとオンとなるフラグを含み、
前記フラグは、前記展開制御部が前記複数個のプロセッサエレメントに設定動作を行うとすべてオフとなり、
前記終了制御部は、終了制御動作時に、最終の繰り返し処理を実行したプロセッサエレメントから順に繰り返し処理を分配した方向とは逆方向に、前記メインプロセッサの前記フラグがオフである前記レジスタのフラグを調べ、オンであるレジスタに対応する前記メインプロセッサのレジスタのフラグをオンすることにより、前記先頭のステップ位置を前記メインプロセッサの前記レジスタに設定する付記２に記載のマルチコアプロセッサ。
（付記４）
前記複数個のプロセッサエレメントが処理に使用するデータを格納する共有メモリ形式のストリームバッファと、
前記ループ部分の処理で使用するデータから順に主記憶からのプリフェッチを行い、プリフェッチしたデータを、前記ループ部分の処理順を保持しながら前記ストリームバッファに格納するプリフェッチと、を備える付記２または３に記載のマルチコアプロセッサ。
（付記５）
前記プリフェッチは、前記複数個のプロセッサエレメントにおける前記ループ部分の処理の実行に合わせて、各プロセッサエレメントと同期しながら、各プロセッサエレメントが使用するデータを前記主記憶からプリフェッチして前記ストリームバッファに格納する付記４に記載のマルチコアプロセッサ。
（付記６）
前記複数個のプロセッサエレメントが処理した処理済みデータを格納する共有メモリ形式のストアバッファを備え、
前記ストアバッファは、格納された前記処理済みデータを、主記憶に書き込むのに適した量に達したら前記主記憶に書き込む付記２から５のいずれかに記載のマルチコアプロセッサ。
（付記７）
前記ストアバッファは、前記複数個のプロセッサエレメントが前記処理済みデータを書き込む各書き込み領域に対応して設けられたフラグを備え、各プロセッサエレメントからの書き込み時点では前記フラグをオフに、前記主記憶に書き込むのに適した量に達した時に前記フラグをオンに変化させ、
前記フラグがオンの前記書き込み領域のデータを前記主記憶に格納し、
前記終了制御部が、すべての前記複数個のプロセッサエレメントからの前記終了通知を受信した時に、前記フラグがオフの前記書き込み領域のデータを消去する付記６に記載のマルチコアプロセッサ。
（付記８）
前記展開制御部および前記終了制御部の少なくとも１つは、前記メインプロセッサに設けられる付記２から７のいずれかに記載のマルチコアプロセッサ。
（付記９）
前記メインプロセッサおよび前記複数個のプロセッサエレメントは、同等の複数個のベースプロセッサであり、前記複数個のベースプロセッサのうちの任意の１個が前記メインプロセッサとして動作する付記２から８のいずれかに記載のマルチコアプロセッサ。
（付記１０）
前記複数個のプロセッサエレメントは、独立したスレッドを並列に実行可能であり、
前記複数個のプロセッサエレメントから選択された２個以上のプロセッサエレメントが、１つの前記ループ部分の処理を実行する付記２から９のいずれかに記載のマルチコアプロセッサ。
【符号の説明】
【０１２６】
１０、１０’ メインプロセッサ
１１ ループ部分検出部
１２ 展開制御部
１３ 終了制御部
１４ レジスタファイル
２０−０〜２０−Ｎ−１ プロセッサエレメント（ＰＥ）
３０ 主記憶
３１ バス
【技術分野】
【０００１】
本発明は、マルチコアプロセッサに関する。
【背景技術】
【０００２】
処理の高速化を図るため、従来から複数のプロセッサを使用して処理を並列に実行する並列処理方法、および並列処理を実行するための複数のプロセッサを含む並列処理システムが各種提案されている。また、近年の半導体技術の集積度の向上により、複数個のプロセッサエレメントを含むマルチコアプロセッサが実現されている。
【０００３】
メディア処理，画像処理等においては，多数のデータに対して依存関係の無い処理を行うことが多い。具体的には、図１に示すような隣接する３×３の画素データを使用する画像のフィルタ処理の場合、各画素の演算処理は、他の画素の処理結果に対して依存関係が無いため、並列計算や計算順序の入れ替えは自由である。
【０００４】
図２は、上記のような処理を、通常のプロセッサ向けに記述した逐次処理用プログラムの例を示す。この演算は、各画素およびその隣接画素の画素データを変数とする演算で、画素位置を変化させながら同じ演算を繰り返すループ部分が含まれる。
【０００５】
このような複数のデータに１種類の処理を適用する場合に、繰り返し処理（イタレーション）方向に処理を並列に実行する並列処理方法として、ＳＩＭＤ(Single Instruction stream Multiple Data stream)法が知られている。ＳＩＭＤ法では内部に複数のプロセッサエレメントを含み、複数個のプロセッサエレメントが並列に１種類の処理を実行することにより、繰り返し処理（イタレーション）を並列に実行する。より具体的には１命令で多数のデータに対するロード・ストア・演算処理を記述することができ、命令を実行する装置は内部のパイプラインなどのリソースの許す限り、複数のデータを同時に処理する、または複数のデータをオーバーラップして処理することにより、並列処理を行う。
【０００６】
図３は、加算演算を繰り返すループ部分の処理をＳＩＭＤ法で実行する場合のプログラム例を示す。
【０００７】
ＳＩＭＤ法で処理を実行する場合、すなわちマルチコアプロセッサを動作させる場合には、図３に示すように、プログラムにおいて新たに定義されたＳＩＭＤ命令を使用しなければ、並列処理が行われないため高速化できない。そのため、プログラムを作成する容易性（プログラマビリティ）に関する問題がある。
【０００８】
また各入力データを各処理でどのようなパターンで参照するかについては、ＳＩＭＤ法の命令セットの形式に依存しており、処理したい演算パターンに合致する命令が無い場合、データを並び替える等の別の対策が必要になる。そのため、同様にプログラマビリティの問題が生じる。
【０００９】
図４および図５は、ＳＩＭＤ法で処理を行う場合の処理方法を説明する図である。
【００１０】
図４の（Ａ）は、図３の加算演算を実行する場合を示し、横軸が実行時間を、縦軸が回路規模（各演算ユニットのパイプライン段数）を示し、太線が１繰り返し処理における１データの処理の流れを示す。第１のＶＬＤは、ｉ番地のデータを各プロセッサエレメントの第１レジスタにロードする処理を示す。第２のＶＬＤは、ｊ番地のデータを各プロセッサエレメントの第２レジスタにロードする処理を示す。ＶＡＤＤは、第１レジスタのデータと第２レジスタのデータを加算して第３レジスタに格納する処理を示す。ＶＳＴは、第３レジスタのデータ（処理結果）をメモリのｏ番地に書き込む（格納する）処理を示す。
【００１１】
それぞれの処理はパイプライン的に処理される。パイプラインであるため前の段の処理が終わったデータに対して次の段の処理を適用することができる。
【００１２】
図４の（Ｂ）は図４の（Ａ）の各命令を実行するパイプラインの本数を４倍に増やしたものである。パイプラインの本数を増加すれば、所定時間内に処理できるデータ数は飛躍的に向上する。
図５は図４の（Ｂ）をデータ数方向を縦軸にとって示したものである。ＳＩＭＤ方式での実効的な並列度はパイプライン本数×パイプライン段数である。
【００１３】
また、複数のデータに１種類の処理を適用する場合に、繰り返し処理をオーバーラップして実行する並列処理方法として、アレイ方式が知られている．
【００１４】
図６は、加算演算、インクリメント（所定値増加）処理および比較処理からなる一連の処理を繰り返す処理をパイプライン方式で実行する場合のプログラム例を示す。
【００１５】
アレイ方式で実行する場合、すなわちアレイプロセッサを動作させる場合には、図５に示すように、逐次処理と同じ命令を用いることができるため、ＳＩＭＤ法の場合のような専用の命令を使わずに高速化を図ることができる。また、入力データの参照は逐次処理と同等に記述できるため、ＳＩＭＤ法より演算の自由度が高い。しかし、アレイ方式では、ループを構成する命令数以上の並列度を得ることができない。すなわち、プログラムを書き換えてループを構成する命令を増やさなければ、並列度を高くできないというスケーラビリティの問題がある。
【００１６】
図７は、パイプライン方式のプロセッサを使用する処理方法を説明する図である。
【００１７】
図７の（Ａ）は、図５の加算、インクリメントおよび比較の処理を実行する場合を示し、横軸が実行時間を、縦軸が回路規模（パイプライン段数）を示し、太線が繰り返し処理における１データの処理の流れを示す。１番目のＬＤは、ｉ番地のデータをプロセッサの第５レジスタにロードする処理を示す。２番目のＬＤは、ｊ番地のデータをプロセッサの第６レジスタにロードする処理を示す。ＡＤＤは、第５レジスタのデータと第６レジスタのデータを加算して第７レジスタに格納する処理を示す。ＳＴは、第７レジスタのデータ（処理結果）をメモリのｏ番地に書き込む（格納する）処理を示す。ＩＮＣは、ｋ番地のデータを１増加する処理を示す。ＣＭＰは、１増加したｋ番地のデータを所定値と比較する処理を示す。
【００１８】
図７の（Ａ）に示すように、１個のデータに対する一連の処理が終了する前に、次のデータに対する処理が開始される。
【００１９】
図７の（Ｂ）は図７（Ａ）を縦軸をデータ数（ループのイタレーション回数）として示したものである。並列度はデータの待ち合わせのためのＮＯＰを含めたループを構成する命令数によって定まる。
【００２０】
このように、アレイ方式のプロセッサは、十分な並列度を得るのが難しいという問題があった。また、ＳＩＭＤ法を実行するマルチプロセッサは、プログラムにおいてＳＩＭＤ命令、すなわちマルチプロセッサ命令を使用しなければ、高速化できないという問題があった。
【００２１】
そのため、広く使用される逐次処理用プログラムで動作可能でかつループ部分の繰り返し処理を並列化して高速化が図れるマルチコアプロセッサが要望されている。
【先行技術文献】
【特許文献】
【００２２】
【特許文献１】特開２０００−３５３２３７号公報
【特許文献２】特開２００３−０９１４２２号公報
【特許文献３】特開２００６−３３０８１３号公報
【発明の概要】
【発明が解決しようとする課題】
【００２３】
実施形態は、逐次処理用プログラムを実行する場合でも、ループ部分の繰り返し処理を並列に実行するマルチコアプロセッサを記載する。
【課題を解決するための手段】
【００２４】
実施形態の第１の態様は、メインプロセッサを含む複数個のプロセッサエレメントを含み、逐次処理プログラムを実行するマルチコアプロセッサであって、メインプロセッサは、逐次処理プログラムに含まれる並列化可能なループ部分を検出するループ部分検出部を含み、マルチコアプロセッサは、ループ部分検出部がループ部分を検出した時に、複数個のプロセッサエレメントがループ部分を命令バッファにコピーするように制御すると共に、複数個のプロセッサエレメントのループカウンタの初期値を各プロセッサエレメントごとにずらして格納し、さらに複数個のプロセッサエレメントのループカウンタの更新量を複数個のプロセッサエレメントの個数に応じて設定する展開制御部と、を含み、メインプロセッサは、逐次処理プログラムに含まれるループ部分の処理を、複数個のプロセッサエレメントに実行させ、複数個のプロセッサエレメントは、ループ外処理への変更が発生したら終了通知を出力し、メインプロセッサは、前記複数個のプロセッサエレメントのうちのいずれか１個が前記終了通知を出力した際に、終了通知を出力したプロセッサエレメントより前のループカウンタ値に対して処理を行っているすべてのプロセッサエレメントの現在処理中のループ部分の終了を待ち、終了通知を出力したプロセッサエレメントより後ろのループカウンタ値に対して処理を行っているプロセッサエレメントのループ部分の処理を終了させた後、逐次処理のプログラムの処理を続行する。
【発明の効果】
【００２５】
実施形態によれば、逐次処理用プログラムでも、ループ部分の繰り返し処理を並列に実行するマルチコアプロセッサが実現される。
【図面の簡単な説明】
【００２６】
【図１】図１は、メディア処理，画像処理等における多数のデータに対して依存関係の無い処理を説明する図である。
【図２】図２は、通常のプロセッサ向けに記述した逐次処理用プログラムの例を示す。
【図３】図３は、加算演算を繰り返すループ部分の処理をＳＩＭＤ法で実行する場合のプログラム例を示す。
【図４】図４は、ＳＩＭＤ法で処理を行う場合の処理方法を説明する図である。
【図５】図５は、ＳＩＭＤ法で処理を行う場合の処理方法を説明する図である。
【図６】図６は、加算演算、インクリメント（所定値増加）処理および比較処理からなる一連の処理を繰り返す処理をアレイ方式で実行する場合のプログラム例を示す。
【図７】図７は、アレイ方式のプロセッサを使用する処理方法を説明する図である。
【図８】図８は、第１実施形態のマルチコアプロセッサの構成を示す図である。
【図９】図９は、プロセッサエレメント（ＰＥ）の１個の構成を示す図である。
【図１０】図１０は、展開制御部の動作を説明する図である。
【図１１】図１１は、第１実施形態における命令および内部状態のコピー例を示す図である。
【図１２】図１２は、終了制御部の動作を説明する図である。
【図１３】図１３は、第１実施形態のマルチコアプロセッサが、ループ部分の繰り返し処理を並列に行う動作を説明する図である。
【図１４】図１４は、第２実施形態のマルチコアプロセッサの構成を示す図である。
【図１５】図１５は、ストリームバッファの構成を示す図である。
【図１６】図１６は、ストリームバッファの動作を示すフローチャートである。
【図１７】図１７は、ストアバッファの構成を示す図である。
【図１８】図１８は、ストアバッファの動作を示すフローチャートである。
【図１９】図１９は、第２実施形態のマルチコアプロセッサが、ループ部分の繰り返し処理を並列に行う動作を説明する図である。
【図２０】図２０は、第３実施形態のマルチコアプロセッサの構成を示す図である。
【発明を実施するための形態】
【００２７】
図８は、第１実施形態のマルチコアプロセッサの構成を示す図である。
【００２８】
図８に示すように、第１実施形態のマルチコアプロセッサは、メインプロセッサ１０と、Ｎ個のプロセッサエレメント（ＰＥ）２０−０〜２０−Ｎ−１と、展開制御部１２と、終了制御部１３と、主記憶３０と、バス３１と、を含む。
【００２９】
メインプロセッサ１０は、逐次処理プログラムＡを実行するための従来例と同様の構成を含むが、図示は省略している。メインプロセッサ１０は、逐次処理プログラムＡ中のループ部分を検出するループ部分検出部１１と、レジスタファイル１４と、を、含む。ループ部分検出部１１は、ハードウェアまたはソフトウェアで形成することができる。また、レジスタファイル１４は、逐次処理プログラムＡを実行するためのレジスタで、従来例と同様の構成を含む。
【００３０】
展開制御部１２および終了制御部１３も、ハードウェアまたはソフトウェアで形成することができる。なお、ハードウェアまたはソフトウェアの中間的な形式でファームウェアと呼ばれる形で、これらを形成することも可能である。
【００３１】
図８において破線で示すように、展開制御部１２および終了制御部１３の少なくとも一方がメインプロセッサ１０’に含まれるようにしてもよい。
【００３２】
プロセッサエレメント（ＰＥ）２０−０〜２０−Ｎ−１は、同じ構成を含み、メインプロセッサ１０と同じ構成を含むようにしてもよい。
【００３３】
図９は、プロセッサエレメント（ＰＥ）２０−０〜２０−Ｎ−１の１個のＰＥ２０の構成を示す図である。
【００３４】
図９に示すように、ＰＥ２０は、命令を解釈実行する命令解釈部２２と、複数の演算器２３と、レジスタファイル２４と、ロードストアユニット２６と、を含むこれまでの構成に加えて、命令バッファ２１と、終了条件判定部２５と、を含む。複数の演算器２３は、命令をパイプライン方式で処理する。
【００３５】
命令バッファ２１は、展開制御部１２を介してメインプロセッサ１０から供給されるループ長分の命令を格納する。
【００３６】
レジスタファイル２４は、展開制御部１２を介してメインプロセッサ１０から供給されるレジスタ初期値を格納し、繰り返し処理終了時には、最終値を出力する。
【００３７】
終了条件判定部２５は、命令バッファ２１に未格納の命令実行を検出することにより，ループ終了を判定する。
【００３８】
図１０は、展開制御部１２の動作を説明する図である。
【００３９】
メインプロセッサ１０が逐次処理プログラムＢを行っている時に、ループ部分検出部１１が並列処理可能なループ部分を検出すると、ループ部分を構成する命令Ｃ１を、各プロセッサエレメント（ＰＥ）の命令バッファ２１に、メインプロセッサ１０の内部状態を各ＰＥにコピーする。
【００４０】
ここで、ループ部分の処理をＮ個のＰＥで並列に実行する場合、各ＰＥで実行する処理をＮずつずらす必要がある。そのため、命令をコピーする時に、ループ部分を構成する命令のうち、ループカウンタ等を更新する命令について、図１０に示すように、１回あたりの更新量を、命令をコピーするＰＥ数に従って変更する。
【００４１】
具体的には、ループ部分の各繰り返し命令で、ループカウンタｋをｋ＝ｋ＋２という形の更新命令である時、Ｎ個のＰＥを使用する場合、この更新命令はｋ＝ｋ＋２Ｎに変更される。
【００４２】
また、メインプロセッサ１０の内部状態をレジスタファイル２４にコピーする時に、上ループカウンタ等の初期値を各ＰＥにずらしながら格納する。
【００４３】
具体的には、ループカウンタｋ＝０が初期値であり、各繰り返し処理においてｋ＝ｋ＋２という形の更新命令がある場合、ＰＥ２０−０にはｋ＝０、ＰＥ２０−１にはｋ＝２、ＰＥ２０−２にはｋ＝４の順にループカウンタｋの初期値を分配する。
【００４４】
より具体的には、ループカウンタはプロセッサのレジスタであり、内部状態のコピーとは、メインプロセッサ１０の全レジスタ値を各ＰＥに分配することである。
【００４５】
図１１は、第１実施形態における命令および内部状態のコピー例を示す図である。ループカウンタの初期値および更新量が、上記のようにコピーされる。
【００４６】
上記のように、各ＰＥにループ部分の命令およびメインプロセッサ１０の内部状態をコピーするループ展開制御完了後に、各プロセッサエレメントを動作させることにより、ループ部分の処理が複数のＰＥで並列に実行される。これにより、ループ部分の繰り返し処理は、ＰＥ数の並列度で実行される。
【００４７】
図１２は、終了制御部１３の動作を説明する図である。
【００４８】
複数のＰＥは、終了条件判定部２５がループ外処理への変更が発生したら終了通知を出力する。ループ部分Ｄの繰り返し処理（イタレーション）の並列実行中に、いずれかのＰＥ２０−Ｐの終了条件判定部２５が、命令バッファ２１に未格納の命令実行を検出すると、言い換えれば、次の実行命令がループ範囲外であることを検出すると、ループ部分の処理終了と判定して、終了制御を開始する。ここでは、上記のループの外側への分岐を行ったループの繰り返し処理を最終繰り返し処理と定義する。
【００４９】
最終繰り返し処理よりループカウンタ値が先行を示している繰り返し処理は、そのループの最後まで実行を完了する必要がある。また、最終繰り返し処理よりループカウンタ値が後の繰り返し処理は、逐次処理では実行してはならない処理であるため、即時に停止させる。最終繰り返し処理を実行していたＰＥ２０−Ｐのレジスタファイル２４に保持されている内部状態を、メインプロセッサ１０に反映させる。そして、メインプロセッサ１０は、すべてのＰＥが終了通知を出力した後、実行したループ部分に続く逐次処理を再開する。
【００５０】
上記の処理は、ループ部分の繰り返し処理がすべて終了した場合の動作である。第１実施形態のマルチコアプロセッサは、ループ部分の繰り返し処理を並列実行中に、割り込み等の外部からの中断要求を受け付けられるようになっている。中断が要求された場合、メインプロセッサ１０が、中断要求があったことを終了制御部１３に通知する。通知を受けた終了制御部１３は、各ＰＥに割り当てられた現在実行中の繰り返し処理が完了するまで待つ。このとき繰り返し処理を完了したプロセッサエレメントが新たな繰り返し処理を開始しないように抑止する。繰り返し処理を完了したＰＥのうち、ループカウンタ値が最も先に進んでいるＰＥの内部状態をレジスタファイル２４から読み出し、ループ処理位置レジスタ１４に格納する。
【００５１】
上記の動作完了後、メインプロセッサ１０が割り込みハンドラ等に制御を移すなどして、外部から要求された処理を行う。上記のループの中断制御はループの終了制御と同じ仕組みで実現することができる。
【００５２】
中断したループの再開は、ループ処理位置レジスタ１４に格納された中断時点でのループカウンタ値を初期値として、再度ループの展開制御を行うことで実現できる。
ここで、メインプロセッサ１０は、内部状態を示すレジスタファイル１４に書き込みを行うとオンとなるフラグを含む。複数のＰＥ２０−０〜２０−Ｎ−１も、内部状態を示すレジスタファイル２４に書き込みを行うとオンとなるフラグを含む。これらのフラグは、展開制御部１２が複数のＰＥに設定動作を行うとすべてオフとなり、例えばプログラムカウンタを更新するなどして内部状態を変化させるとオンとなる。終了制御部１３は、終了制御動作時に、最終の繰り返し処理を実行したＰＥから順に繰り返し処理を分配した方向とは逆方向にＰＥのフラグを調べてメインプロセッサのフラグと比較する。メインプロセッサ１０のフラグがオフであるのに、対応するＰＥのレジスタがオンである場合には、メインプロセッサ１０のフラグをオンすることにより、先頭のステップ位置をメインプロセッサ１０のレジスタファイル１４に設定する。
【００５３】
図１３は、第１実施形態のマルチコアプロセッサが、図１０に示したループ部分の繰り返し処理（イタレーション）を並列に行う動作を説明する図である。ここでは、ＰＥが４個の例を示している。
【００５４】
図１３の（Ａ）に示すように、４個のＰＥが、ロード、ロード、加算、ストア（格納）、インクリメント、比較およびループ継続判定の一連の繰り返し処理（イタレーション）を、並列に実行する。ＰＥ数を増加すると、単位時間に実行可能な繰り返し処理数が増加する。
【００５５】
図１３の（Ｂ）は、処理時間と、繰り返し処理数（イタレーション数）、すなわち処理データ数の関係を示す図である。ＰＥ数を増加すると、すなわち並列度を高くすると、その分処理データ数が増加する。具体的には、ＰＥ数がＮ個であれば、同一のループを逐次実行した場合と比較してＮ倍高速化できる。
【００５６】
図１４は、第２実施形態のマルチコアプロセッサの構成を示す図である。第２実施形態のマルチコアプロセッサは、第１実施形態のマルチコアプロセッサと類似の構成を含み、プリフェッチ４１と、ストリームバッファ４２と、ストアバッファ４３と、を更に含むことが異なる。したがって、メインプロセッサ１０は、ループ部分検出部１１およびレジスタファイル１４を含むが図示は省略している。また、展開制御部１２および終了制御部１３は、メインプロセッサ１０に含ませることも可能である。以下、第１実施例と異なる部分についてのみ説明する。
【００５７】
図１５は、ストリームバッファ４２の構成を示す図である。
【００５８】
主記憶３０からプロセッサエレメント（ＰＥ）方向への主記憶アクセス、すなわちＰＥ２０−０〜２０−Ｎ−１が主記憶３０のデータを読み取る時のアクセスの効率化を実現するために、リードオンリのストリームバッファ４２を設ける。ストリームバッファ４２は、各ＰＥ間の共有メモリ形式のキャッシュメモリであり、各ＰＥは共有のキャッシュメモリにアクセスするという方法をとる。
【００５９】
図１５に示すように、ストリームバッファ４２は、調停回路５１と、書き込み制御回路５２と、内部キャッシュメモリ５３と、を含む。図１５では、２個のプロセッサエレメント（ＰＥ）２０−０および２０−１が調停回路５１に接続されているように示しているが、実際にはすべてのプロセッサエレメント（ＰＥ）２０−０〜２０−Ｎ−１が接続されている。プリフェッチ４１は、メインプロセッサ１０からのプリフェッチ指令４０に応じて、処理対象のループ部分が使用するデータを主記憶３０からストリームバッファ４２に書き込む処理を行う。共有形式のキャッシュメモリについては広く知られているので、詳しい説明は省略する。
【００６０】
図１５に示したストリームバッファ４２を使用して、対象とするループ処理が扱うデータを、アクセスする順番にストリームバッファ４２に格納することにより、主記憶３０へのアクセスと演算処理を同時に行くことが可能である。
【００６１】
図１６は、ストリームバッファ４２の動作を示すフローチャートであり、左側のＳ１１からＳ１８は各ＰＥの動作を、右側のＳ２１からＳ２６はストリームバッファ４２における動作を示す。
【００６２】
ループ部分の展開および並列実行に先立って、メインプロセッサ１０は、対象とするループ処理が扱うデータのアクセスパターンを、プリフェッチ４１に指示する。これに応じて、プリフェッチ４１は、主記憶３０から指定されたデータをストリームバッファ４２に転送する。
【００６３】
ステップＳ１１で、各ＰＥ２０は、ループ部分の繰り返し処理を実行する。
【００６４】
ステップＳ１２で、処理を実行するのにデータをＰＥ内にロードする必要があるか否かを判定し、なければステップＳ１６に進み、あればステップＳ１３に進む。
【００６５】
ステップ１３では、ストリームバッファ４２に、データの格納アドレスを通信することにより必要なデータをロードするように要求（リクエスト）する。
【００６６】
ステップＳ１４では、データのロード（送信）が完了したかを判定し、完了すればステップＳ１６に進み、完了していなければステップＳ１５に進み、データのロード完了まで待機し、完了したらステップＳ１６に進む。したがって、キャッシュミスが発生した場合には、ＰＥ２０は、処理を停止して待機した状態になり、キャッシュミスが解消された時に動作を再開する。
【００６７】
ステップＳ１６では、終了条件判定部２５が、終了条件を満たすかを判定し、満たしていなければステップＳ１８に進み、満たしていればステップＳ１７に進む。
【００６８】
ステップＳ１７では、終了通知を終了制御部１３に出力して処理を終了する。
【００６９】
ステップＳ１８では、終了制御部１３から終了通知が出されているかを判定し、終了通知が出されていれば処理を終了し、出されていなければステップＳ１１に戻る。
【００７０】
したがって、キャッシュミスが発生しない状態では、各ＰＥはループ部分の繰り返し処理を続ける。
【００７１】
ステップＳ１３でロードするように要求されたデータがストリームバッファ４２に存在する場合には、短時間のうちにデータが送信されるが、要求されたデータがストリームバッファ４２に存在しない場合には、キャッシュミスが発生する。キャッシュミスの場合には、データを受信するまでの時間が長くなる。したがって、キャッシュミスが発生した場合には、ＰＥ２０は、ステップＳ１５で待機する時間が長くなり、処理を停止してキャッシュミスが解消された時に動作を再開することになる。
【００７２】
ストリームバッファ４２に必要なデータが存在しない場合はキャッシュミスの状態であり、プリフェッチ４１は、必要なデータを主記憶３０からにストリームバッファ４２に転送する。この動作をプリフェッチ処理と称する。また、ストリームバッファ４２は、各ＰＥからのロード要求に応じて、ストリームバッファ４２内のデータを各ＰＥに送信するこれをロード処理と称する。もし、各ＰＥからロード要求されたデータがストリームバッファ４２に存在しない場合はキャッシュミスの状態であり、プリフェッチ処理を実行する必要がある。
【００７３】
ステップＳ２１で、ストリームバッファ４２は、要求がプリフェッチ処理かロード処理かを判定し、プリフェッチ処理の場合にはステップＳ２２に進み、ロード処理の場合にはステップＳ２３に進む。
【００７４】
ステップＳ２２では、プリフェッチ４１が主記憶３０のデータをストリームバッファ４２の内部キャッシュメモリ５３に転送する。
【００７５】
ステップＳ２３では、ロード処理で要求されたデータがストリームバッファ４２の内部キャッシュメモリ５３にあるか否かを判定し、あればステップＳ２５に進み、無ければステップＳ２４に進む。
【００７６】
ステップＳ２４では、キャッシュミスの状態なので、プリフェッチ４１が主記憶３０のデータをストリームバッファ４２の内部キャッシュメモリ５３に転送するように要求し、データが供給されるまで待機し、データが供給されたら、ステップＳ２５に進む。
【００７７】
ステップＳ２５では、ストリームバッファ４２の内部キャッシュメモリ５３からロード要求されたデータを読み出す。
【００７８】
ステップＳ２６では、ストリームバッファ４２の内部キャッシュメモリ５３から読み出したデータを要求したＰＥに送信し、ステップＳ２１に戻る。
【００７９】
以上説明したように、プリフェッチしたデータは、各ＰＥ間で共有のストリームバッファ４２に格納するため、各ＰＥ間で共有されるデータについても１回の主記憶アクセスで取得可能であり、主記憶アクセスが効率化される。
【００８０】
図１７は、ストアバッファ４３の構成を示す図である。
【００８１】
第２実施形態では、プロセッサエレメント（ＰＥ）から主記憶３０方向への主記憶アクセスの効率化を実現するために、各ＰＥ２０−０〜２０−Ｎ−１は書込動作（ストア）発生時に直接主記憶３０に書き込むのではなく、ストアバッファ４３を介してデータを書き込む方法をとる。
【００８２】
図１７に示すように、ストリームバッファ４２は、調停回路６１と、書き込み制御回路６２と、書き込み分配回路６３と、複数個のエントリ６４−０〜６４−Ｎ−１と、書き込み合成回路６５と、を含む。図１７では、２個のプロセッサエレメント（ＰＥ）２０−０および２０−１が調停回路６１に接続されているように示しているが、実際にはすべてのプロセッサエレメント（ＰＥ）２０−０〜２０−Ｎ−１が接続されている。
【００８３】
書き込み制御回路６２は、各ＰＥから出力される書き込みアドレスに基づいて、書き込み分配回路６３がＮ個のエントリ６４−０〜６４−Ｎ−１のいずれかを選択し、ＰＥから出力されたアドレスとデータの組を、選択したエントリ内に格納するように制御する。
【００８４】
書き込み制御回路６２は、１エントリが満たされたタイミングで、１エントリ単位で主記憶３０への書き込みアクセスを行い、書き込みアクセスを行ったエントリを解放する。
【００８５】
１エントリ内に格納されるデータが、主記憶３０上で連続したアドレスとなるように、アドレスに基づいたエントリ選択を行うことにより、エントリの内容を主記憶３０に書き込む際に、バースト転送等の効率的なアクセスが可能となる。
【００８６】
また、ループの終了時には、最終繰り返し処理を実行したＰＥからの指示に基づき，ストアバッファ４３内のストアデータ格納済みエントリ内のデータをすべて主記憶に書き込むというフラッシュ動作を行ことにより、ＰＥがストアした全データが主記憶３０に書き込まれることを保証する。
【００８７】
図１８は、ストアバッファ４３の動作を示すフローチャートであり、左側のＳ３１からＳ３８は各ＰＥの動作を、右側のＳ４１からＳ４７およびＳ５１からＳ５３はストアバッファ４３における動作を示す。
【００８８】
ステップＳ３１で、各ＰＥ２０は、ループ部分の繰り返し処理を実行する。
【００８９】
ステップＳ３２で、実行した処理の結果、ストアする（書き込む）データが発生したか否かを判定し、発生しなければステップＳ３６に進み、発生していればステップＳ３３に進む。
【００９０】
ステップ３３では、ストアバッファ４３の所望のエントリが満杯（フル）であるか否かを判定し、フルであればステップＳ３４に進み、空きがあればステップＳ３５に進む。
【００９１】
ステップＳ３４では、ストアバッファ４３の所望のエントリが空くまで待機し、ストアバッファ４３から空いたことが通信されたらステップＳ３５に進む。
【００９２】
ステップＳ３５では、ストアバッファ４３に対して、データのストア処理を要求（リクエスト）し、データおよびアドレスをストアバッファ４３に送信する。
【００９３】
ステップＳ３６では、終了条件判定部２５が、終了条件を満たすかを判定し、満たしていなければステップＳ３８に進み、満たしていればステップＳ３７に進む。
【００９４】
ステップＳ３７では、終了通知を終了制御部１３に出力すると共に、ストアバッファ４３にフラッシュ処理を要求して処理を終了する。
【００９５】
ステップＳ３８では、終了制御部１３から終了通知が出されているかを判定し、終了通知が出されていれば処理を終了し、出されていなければステップＳ３１に戻る。
【００９６】
次に、ストアバッファ４３における動作を説明する。
【００９７】
ステップＳ４１で、ストリームバッファ４２は、要求がストア処理かフラッシュ処理かを判定し、ストア処理の場合にはステップＳ４２に進み、フラッシュ処理の場合にはステップＳ５１に進む。
【００９８】
ステップＳ４２では、所望のエントリが確保されているかを判定し、確保されていなければステップＳ４３に進み、確保されていればステップＳ４４に進む。
【００９９】
ステップＳ４３では、エントリを確保する。
【０１００】
ステップＳ４４では、確保済みのエントリに、ＰＥから送信されたデータおよびアドレスを格納する。
【０１０１】
ステップＳ４５では、格納先のエントリが満杯であるか否かを判定し、満杯であればステップＳ４６に進み、満杯でなければステップＳ４１に戻る。
【０１０２】
ステップＳ４６では、満杯のエントリのアドレスで主記憶３０にアクセスして、データを書き込む。
【０１０３】
ステップＳ４７では、出力（読み出し）が行われた上記のエントリが解放され、エントリの解放をＰＥに通知し、ステップＳ４１に戻る。
【０１０４】
一方、ステップＳ４１で、フラッシュ処理と判定された時には、ステップＳ５１で、格納隅のエントリがあるか否かを判定し、あればステップＳ５２に進み、無ければ終了する。
【０１０５】
ステップＳ５２では、未格納のエントリのアドレスで主記憶３０にアクセスして、データを書き込む。
【０１０６】
ステップＳ５３では、出力（読み出し）が行われた上記のエントリが解放され、ステップＳ５１に戻る。以下、未格納のエントリのすべてのデータが主記憶３０に書き込まれるまでこの処理を繰り返す。
【０１０７】
以上説明したように、第２実施形態では、ループカウンタ値をずらしたものを並列実行しているため、ループ自体が元々メモリアクセスの局所性を有しており、並列実行している各ＰＥがメモリ中の近い領域にアクセスする。このため、各ＰＥが主記憶から読んだ値が周辺のプロセッサエレメントでも再利用できるため、主記憶アクセスが効率化される。
【０１０８】
さらに、ループの各繰り返し処理が、同一のデータを主記憶から読み出す特性を持ったループ処理の場合、プログラム中に記述したプリフェッチ指令または予測機構に基づいて、プリフェッチが各繰り返し処理に必要なデータを主記憶から、複数のＰＥ間に共有のストリームバッファに読み出しておくことにより、さらに読み出しアクセスの効率化を図ることができる。
【０１０９】
また、ループの各繰り返し処理から主記憶への書き込みアドレスに局所性がある場合、ＰＥ間で共有のストアバッファに、書き込みアドレスとデータを格納し、ほかのＰＥの書き込みデータとまとめることにより、書き込みアクセスの効率化を図ることができる。
【０１１０】
図１９は、第２実施形態のマルチコアプロセッサが、図１１に示したループ部分の繰り返し処理を並列に行う動作を説明する図である。ここでは、ＰＥが４個の例を示している。
【０１１１】
図１９に示すように、ロード、演算およびストアを含む一連の繰り返し処理を、複数のデータについて行う場合を考える。１回の繰り返し処理の命令実行時間をＴ、データ数をＰとすると、逐次処理では１つの繰り返し処理をＰ回繰り返すので、処理時間はＴ×Ｐになる。
【０１１２】
これに対して、ＰＥを４個使用して繰り返し処理を並列に行う場合を考える。ただし、繰り返し処理を並列に行うには、並列に行う４つの処理に必要な４組のデータも並列に供給可能で、処理結果の４組のデータも並列に出力可能であることが必要である。もし、データの供給および出力が、同じ速度で並列に行えないと、４倍の速度で処理することはできない。
【０１１３】
第２実施形態では、上記のように、ストリームバッファ４２およびストアバッファ４３を使用して、ＰＥへのデータ供給およびＰＥからのデータ出力を並列に行えるようにしている。
【０１１４】
図１９に示すように、入力データが画像データの場合、４個のＰＥは、１画素ずつずれた隣接画素群のデータを処理に使用する。このような隣接画素群のデータは、スキャンなどにより、主記憶に連続してアクセスして読み出すことが可能である。そこで、プリフェッチ処理で、このような隣接画素群のデータを連続して読み出して、ストリームバッファ４２に格納する。この場合、１画素ずつずらすので、図１９に示すように、タイムラグが発生する。４個のＰＥ用のデータが揃ったら、４個のＰＥは同時に並列で４つの画素についてそれぞれ処理を行う。４個のＰＥが処理を行っている間に、次の４つずれた画素の隣接画素群のデータを供給して準備しておく。
【０１１５】
一方、４個のＰＥで処理した結果である出力データは、並列にストアバッファに出力され、次のデータが出力されるまでに主記憶に書き込まれる。この場合も、１画素ずつずれてデータが書き込まれるので、画像をスキャンするように書き込むことになる。
【０１１６】
いずれにしろ、以上のようにして、ループ部分の処理を、ＰＥの個数、すなわち４倍に近い高速で行えるようになる。
【０１１７】
図２０は、第３実施形態のマルチコアプロセッサの構成を示す図である。第３実施形態のマルチコアプロセッサは、対称な構成の複数のプロセッサエレメント（ＰＥ）２０−０〜２０−Ｎ−１を含み、いずれかのＰＥがメインプロセッサとして動作することが、第２実施形態のマルチコアプロセッサと異なり、他の部分は同じである。
【０１１８】
各ＰＥは、展開制御部１２、終了制御部１３、命令バッファ２１および終了条件検出回路２５を含み、いずれもメインプロセッサとして動作可能である。
【０１１９】
いずれかのＰＥがメインプロセッサとして動作し、並列処理可能なループを検出した時に、メインプロセッサとして動作するＰＥの展開制御部１２が動作し、汎用のバス３１を介して他のＰＥに命令および内部状態を分配する。各ＰＥは、それぞれ繰り返し処理の１つの処理を並列に実行し、いずれかのＰＥがループの終了条件を検出した際に、メインプロセッサの終了制御への終了通知を行う。終了通知を受けたメインプロセッサの終了制御は、最終繰り返し処理より後の処理返し処理を実行しているＰＥを停止させ、また最終繰り返し処理を実行していたＰＥより内部状態のデータを得て、自分のＰＥの内部状態に反映させた後、逐次実行に復帰する。
【０１２０】
以上第１から第３実施形態を説明したが、各実施形態で説明した事項は、他の実施形態に適用することが可能であり、説明した以外にも各種の変形例が可能である。
【０１２１】
例えば、第３実施形態では、Ｎ個のＰＥが設けられている場合、Ｎ個のＰＥをすべてループ部分の繰り返し処理に使用したが、一部のＰＥを使用し、残りのＰＥは他の処理に使用することも可能である。メインプロセッサを含む複数のＰＥが、独立したスレッドを実行している時に、あるＰＥが並列実行可能なループ部分を検出し、他のＰＥにループ部分の繰り返し処理を分担して並列に実行するように要求する。展開要求を受けたＰＥが、展開要求元のスレッドより高い優先度のスレッドを実行している場合には、展開要求を拒否し、独立してスレッド実行を続行し、より低い優先度のスレッドを実行している場合のみ展開要求を受け付ける。そして、展開要求を出したＰＥおよび展開要求を受け付けたＰＥにのみループ部分を展開して、各繰り返し処理（イタレーション）の並列実行を行う。
【０１２２】
以上説明したように、実施形態によれば、ＳＩＭＤ法を実行するマルチプロセッサ（マルチコアプロセッサ）と比較して、ループを構成する命令は逐次実行の命令のままでよく、入力データの参照、入力データ間の演算の自由度が高いためプログラマビリティが高い。
【０１２３】
また、パイプライン方式のプロセッサでは最大の並列度がループの長さに依存していたのに対して、実施形態のマルチコアプロセッサではプロセッサエレメント（ＰＥ）数を増加させることで、並列度を向上させることができ、スケーラビリティを高くすることが可能である。
【０１２４】
以上、実施形態を説明したが、ここに記載したすべての例や条件は、発明および技術に適用する発明の概念の理解を助ける目的で記載されたものであり、特に記載された例や条件は発明の範囲を制限することを意図するものではなく、明細書のそのような例の構成は発明の利点および欠点を示すものではない。発明の実施形態を詳細に記載したが、各種の変更、置き換え、変形が発明の精神および範囲を逸脱することなく行えることが理解されるべきである。
【０１２５】
以下、実施形態に関し、更に以下の付記を開示する。
（付記１）
メインプロセッサを含む複数個のプロセッサエレメントを備え、逐次処理プログラムを実行するマルチコアプロセッサであって、
前記メインプロセッサは、前記逐次処理プログラムに含まれる並列化可能なループ部分を検出するループ部分検出部を備え、
前記マルチコアプロセッサは、前記ループ部分検出部が前記ループ部分を検出した時に、前記複数個のプロセッサエレメントが前記ループ部分を命令バッファにコピーするように制御すると共に、前記複数個のプロセッサエレメントのループカウンタの初期値を各プロセッサエレメントごとにずらして格納し、さらに前記複数個のプロセッサエレメントのループカウンタの更新量を前記複数個のプロセッサエレメントの個数に応じて設定する展開制御部と、を備え、
前記メインプロセッサは、前記逐次処理プログラムに含まれる前記ループ部分の処理を、前記複数個のプロセッサエレメントに実行させ、
前記複数個のプロセッサエレメントは、ループ外処理への変更が発生したら終了通知を出力し、
前記メインプロセッサは、前記複数個のプロセッサエレメントのうちのいずれか１個が前記終了通知を出力した際に、終了通知を出力したプロセッサエレメントより前のループカウンタ値に対して処理を行っているすべてのプロセッサエレメントの現在処理中のループ部分の終了を待ち、終了通知を出力したプロセッサエレメントより後ろのループカウンタ値に対して処理を行っているプロセッサエレメントのループ部分の処理を終了させ、前記逐次処理プログラムの処理を続行することを特徴とするマルチコアプロセッサ。
（付記２）
前記メインプロセッサが、実行中の前記ループ部分の処理の中断を指示すると、前記ループ部分の処理を実行中の前記複数個のプロセッサエレメントは、実行中の前記ループ部分の１ステップを完了すると前記終了通知を出力すると共に処理を停止し、
前記マルチコアプロセッサは、すべての前記複数個のプロセッサエレメントからの前記終了通知を受信した後、前記複数個のプロセッサエレメントの内部状態の情報を取得して、前記ループ部分の処理のうち完了している先頭のステップ位置を検出する終了制御部を備え、
前記メインプロセッサは、前記終了制御部の検出した前記先頭のステップ位置を記憶する内部状態を示すレジスタを備え、中断した前記ループ部分の処理を再開する時には、前記ループ処理位置レジスタに記憶された前記先頭のステップ位置の次から前記ループ部分の処理を実行するように、前記展開制御部に情報を提供する付記１に記載のマルチコアプロセッサ。
（付記３）
前記メインプロセッサおよび前記複数個のプロセッサエレメントは、内部状態を示すレジスタに書き込みを行うとオンとなるフラグを含み、
前記フラグは、前記展開制御部が前記複数個のプロセッサエレメントに設定動作を行うとすべてオフとなり、
前記終了制御部は、終了制御動作時に、最終の繰り返し処理を実行したプロセッサエレメントから順に繰り返し処理を分配した方向とは逆方向に、前記メインプロセッサの前記フラグがオフである前記レジスタのフラグを調べ、オンであるレジスタに対応する前記メインプロセッサのレジスタのフラグをオンすることにより、前記先頭のステップ位置を前記メインプロセッサの前記レジスタに設定する付記２に記載のマルチコアプロセッサ。
（付記４）
前記複数個のプロセッサエレメントが処理に使用するデータを格納する共有メモリ形式のストリームバッファと、
前記ループ部分の処理で使用するデータから順に主記憶からのプリフェッチを行い、プリフェッチしたデータを、前記ループ部分の処理順を保持しながら前記ストリームバッファに格納するプリフェッチと、を備える付記２または３に記載のマルチコアプロセッサ。
（付記５）
前記プリフェッチは、前記複数個のプロセッサエレメントにおける前記ループ部分の処理の実行に合わせて、各プロセッサエレメントと同期しながら、各プロセッサエレメントが使用するデータを前記主記憶からプリフェッチして前記ストリームバッファに格納する付記４に記載のマルチコアプロセッサ。
（付記６）
前記複数個のプロセッサエレメントが処理した処理済みデータを格納する共有メモリ形式のストアバッファを備え、
前記ストアバッファは、格納された前記処理済みデータを、主記憶に書き込むのに適した量に達したら前記主記憶に書き込む付記２から５のいずれかに記載のマルチコアプロセッサ。
（付記７）
前記ストアバッファは、前記複数個のプロセッサエレメントが前記処理済みデータを書き込む各書き込み領域に対応して設けられたフラグを備え、各プロセッサエレメントからの書き込み時点では前記フラグをオフに、前記主記憶に書き込むのに適した量に達した時に前記フラグをオンに変化させ、
前記フラグがオンの前記書き込み領域のデータを前記主記憶に格納し、
前記終了制御部が、すべての前記複数個のプロセッサエレメントからの前記終了通知を受信した時に、前記フラグがオフの前記書き込み領域のデータを消去する付記６に記載のマルチコアプロセッサ。
（付記８）
前記展開制御部および前記終了制御部の少なくとも１つは、前記メインプロセッサに設けられる付記２から７のいずれかに記載のマルチコアプロセッサ。
（付記９）
前記メインプロセッサおよび前記複数個のプロセッサエレメントは、同等の複数個のベースプロセッサであり、前記複数個のベースプロセッサのうちの任意の１個が前記メインプロセッサとして動作する付記２から８のいずれかに記載のマルチコアプロセッサ。
（付記１０）
前記複数個のプロセッサエレメントは、独立したスレッドを並列に実行可能であり、
前記複数個のプロセッサエレメントから選択された２個以上のプロセッサエレメントが、１つの前記ループ部分の処理を実行する付記２から９のいずれかに記載のマルチコアプロセッサ。
【符号の説明】
【０１２６】
１０、１０’ メインプロセッサ
１１ ループ部分検出部
１２ 展開制御部
１３ 終了制御部
１４ レジスタファイル
２０−０〜２０−Ｎ−１ プロセッサエレメント（ＰＥ）
３０ 主記憶
３１ バス
【特許請求の範囲】
【請求項１】
メインプロセッサを含む複数個のプロセッサエレメントを備え、逐次処理プログラムを実行するマルチコアプロセッサであって、
前記メインプロセッサは、前記逐次処理プログラムに含まれる並列化可能なループ部分を検出するループ部分検出部を備え、
前記マルチコアプロセッサは、前記ループ部分検出部が前記ループ部分を検出した時に、前記複数個のプロセッサエレメントが前記ループ部分を命令バッファにコピーするように制御すると共に、前記複数個のプロセッサエレメントのループカウンタの初期値を各プロセッサエレメントごとにずらして格納し、さらに前記複数個のプロセッサエレメントのループカウンタの更新量を前記複数個のプロセッサエレメントの個数に応じて設定する展開制御部と、を備え、
前記メインプロセッサは、前記逐次処理プログラムに含まれる前記ループ部分の処理を、前記複数個のプロセッサエレメントに実行させ、
前記複数個のプロセッサエレメントは、ループ外処理への変更が発生したら終了通知を出力し、
前記メインプロセッサは、前記複数個のプロセッサエレメントのうちのいずれか１個が前記終了通知を出力した際に、終了通知を出力したプロセッサエレメントより前のループカウンタ値に対して処理を行っているすべてのプロセッサエレメントの現在処理中のループ部分の終了を待ち、終了通知を出力したプロセッサエレメントより後ろのループカウンタ値に対して処理を行っているプロセッサエレメントのループ部分の処理を終了させ、前記逐次処理プログラムの処理を続行することを特徴とするマルチコアプロセッサ。
【請求項２】
前記メインプロセッサが、実行中の前記ループ部分の処理の中断を指示すると、前記ループ部分の処理を実行中の前記複数個のプロセッサエレメントは、実行中の前記ループ部分の１ステップを完了すると前記終了通知を出力すると共に処理を停止し、
前記マルチコアプロセッサは、すべての前記複数個のプロセッサエレメントからの前記終了通知を受信した後、前記複数個のプロセッサエレメントの内部状態の情報を取得して、前記ループ部分の処理のうち完了している先頭のステップ位置を検出する終了制御部を備え、
前記メインプロセッサは、前記終了制御部の検出した前記先頭のステップ位置を記憶する内部状態を示すレジスタを備え、中断した前記ループ部分の処理を再開する時には、前記ループ処理位置レジスタに記憶された前記先頭のステップ位置の次から前記ループ部分の処理を実行するように、前記展開制御部に情報を提供する請求項１に記載のマルチコアプロセッサ。
【請求項３】
前記複数個のプロセッサエレメントが処理に使用するデータを格納する共有メモリ形式のストリームバッファと、
前記ループ部分の処理で使用するデータから順に主記憶からのプリフェッチを行い、プリフェッチしたデータを、前記ループ部分の処理順を保持しながら前記ストリームバッファに格納するプリフェッチと、を備える請求項２に記載のマルチコアプロセッサ。
【請求項４】
前記複数個のプロセッサエレメントが処理した処理済みデータを格納する共有メモリ形式のストアバッファを備え、
前記ストアバッファは、格納された前記処理済みデータを、主記憶に書き込むのに適した量に達したら前記主記憶に書き込む請求項２または３に記載のマルチコアプロセッサ。
【請求項５】
前記展開制御部および前記終了制御部の少なくとも１つは、前記メインプロセッサに設けられる請求項２から４のいずれか１項に記載のマルチコアプロセッサ。
【請求項１】
メインプロセッサを含む複数個のプロセッサエレメントを備え、逐次処理プログラムを実行するマルチコアプロセッサであって、
前記メインプロセッサは、前記逐次処理プログラムに含まれる並列化可能なループ部分を検出するループ部分検出部を備え、
前記マルチコアプロセッサは、前記ループ部分検出部が前記ループ部分を検出した時に、前記複数個のプロセッサエレメントが前記ループ部分を命令バッファにコピーするように制御すると共に、前記複数個のプロセッサエレメントのループカウンタの初期値を各プロセッサエレメントごとにずらして格納し、さらに前記複数個のプロセッサエレメントのループカウンタの更新量を前記複数個のプロセッサエレメントの個数に応じて設定する展開制御部と、を備え、
前記メインプロセッサは、前記逐次処理プログラムに含まれる前記ループ部分の処理を、前記複数個のプロセッサエレメントに実行させ、
前記複数個のプロセッサエレメントは、ループ外処理への変更が発生したら終了通知を出力し、
前記メインプロセッサは、前記複数個のプロセッサエレメントのうちのいずれか１個が前記終了通知を出力した際に、終了通知を出力したプロセッサエレメントより前のループカウンタ値に対して処理を行っているすべてのプロセッサエレメントの現在処理中のループ部分の終了を待ち、終了通知を出力したプロセッサエレメントより後ろのループカウンタ値に対して処理を行っているプロセッサエレメントのループ部分の処理を終了させ、前記逐次処理プログラムの処理を続行することを特徴とするマルチコアプロセッサ。
【請求項２】
前記メインプロセッサが、実行中の前記ループ部分の処理の中断を指示すると、前記ループ部分の処理を実行中の前記複数個のプロセッサエレメントは、実行中の前記ループ部分の１ステップを完了すると前記終了通知を出力すると共に処理を停止し、
前記マルチコアプロセッサは、すべての前記複数個のプロセッサエレメントからの前記終了通知を受信した後、前記複数個のプロセッサエレメントの内部状態の情報を取得して、前記ループ部分の処理のうち完了している先頭のステップ位置を検出する終了制御部を備え、
前記メインプロセッサは、前記終了制御部の検出した前記先頭のステップ位置を記憶する内部状態を示すレジスタを備え、中断した前記ループ部分の処理を再開する時には、前記ループ処理位置レジスタに記憶された前記先頭のステップ位置の次から前記ループ部分の処理を実行するように、前記展開制御部に情報を提供する請求項１に記載のマルチコアプロセッサ。
【請求項３】
前記複数個のプロセッサエレメントが処理に使用するデータを格納する共有メモリ形式のストリームバッファと、
前記ループ部分の処理で使用するデータから順に主記憶からのプリフェッチを行い、プリフェッチしたデータを、前記ループ部分の処理順を保持しながら前記ストリームバッファに格納するプリフェッチと、を備える請求項２に記載のマルチコアプロセッサ。
【請求項４】
前記複数個のプロセッサエレメントが処理した処理済みデータを格納する共有メモリ形式のストアバッファを備え、
前記ストアバッファは、格納された前記処理済みデータを、主記憶に書き込むのに適した量に達したら前記主記憶に書き込む請求項２または３に記載のマルチコアプロセッサ。
【請求項５】
前記展開制御部および前記終了制御部の少なくとも１つは、前記メインプロセッサに設けられる請求項２から４のいずれか１項に記載のマルチコアプロセッサ。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【公開番号】特開２０１１−２０４２０８（Ｐ２０１１−２０４２０８Ａ）
【公開日】平成２３年１０月１３日（２０１１．１０．１３）
【国際特許分類】
【出願番号】特願２０１０−７３６７６（Ｐ２０１０−７３６７６）
【出願日】平成２２年３月２６日（２０１０．３．２６）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２３年１０月１３日（２０１１．１０．１３）
【国際特許分類】
【出願日】平成２２年３月２６日（２０１０．３．２６）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]