(57)【特許請求の範囲】
【請求項１】
単一のプログラムを複数のスレッドに分割し複数のプロセッサで並列に実行する並列プロセッサシステムにおけるフォーク後に親スレッドで更新されたレジスタを子スレッドに継承する方法において、フォーク後、親スレッドの汎用レジスタ書き込み毎に更新後のレジスタ値を親スレッド側のプロセッサから子スレッド側のプロセッサへ送信し、子スレッド側のプロセッサでは子スレッドを投機的に実行し、正依存の違反を検出すると再実行を行うことを特徴とするプロセッサ間レジスタ継承方法。
【請求項２】
各プロセッサの汎用レジスタに１対１に対応し、スレッド開始時点で第１の状態を保持し、対応する汎用レジスタに対するスレッド開始後の最初のアクセスがリードの場合に第２の状態を保持し、対応する汎用レジスタに対するスレッド開始後の最初のアクセスがライトの場合に第３の状態を保持する状態レジスタを備え、レジスタ値が親スレッド側のプロセッサから送信された汎用レジスタに対応する状態レジスタが第２の状態を保持しているとき、正依存の違反が発生したと検出する請求項１記載のプロセッサ間レジスタ継承方法。
【請求項３】
子スレッドへの転送停止、転送再開を制御する特殊命令によって操作されるマスクビットを汎用レジスタに１対１に対応して備え、フォーク後、親スレッドの汎用レジスタ書き込み毎に、書き込みの行われた汎用レジスタに対応するマスクビットが転送許可状態である場合に限って、更新後のレジスタ値を親スレッド側のプロセッサから子スレッド側のプロセッサへ送信する請求項１または２記載のプロセッサ間レジスタ継承方法。
【請求項４】
フォーク時点のスタックポインタの値を保存するスタックポインタ保存手段と、現在のスタックポインタの値と前記スタックポインタ保存手段に保存されたスタックポインタの値との一致を検出する検出手段とを備え、フォーク後、親スレッドの汎用レジスタ書き込み毎に、書き込みの行われた汎用レジスタが関数の返り値レジスタである場合、及び書き込みの行われた汎用レジスタが関数の返り値レジスタ以外のレジスタであって前記検出手段で一致が検出されている場合に限って、更新後のレジスタ値を親スレッド側のプロセッサから子スレッド側のプロセッサへ送信する請求項１または２記載のプロセッサ間レジスタ継承方法。
【請求項５】
各汎用レジスタに１対１に対応するストアアドレスレジスタを備え、ストア命令実行時に汎用レジスタ毎にストアアドレスを前記ストアアドレスレジスタに記憶し、汎用レジスタの内容切り替えを検出した際に当該汎用レジスタの子スレッドへの転送を禁止状態にすると共にストアアドレスレジスタへの書き込みを停止し、ロード時のアドレスをストアアドレスレジスタに記憶されたストアアドレスと比較することによって汎用レジスタの内容が元に戻ったことを検出して、当該汎用レジスタの子スレッドへの転送禁止状態を解除する請求項１または２記載のプロセッサ間レジスタ継承方法。
【請求項６】
更新後の汎用レジスタの値が更新前と異なる場合に限って、更新後のレジスタ値を親スレッド側のプロセッサから子スレッド側のプロセッサへ送信する請求項１乃至５の何れか１項に記載のプロセッサ間レジスタ継承方法。
【請求項７】
単一のプログラムを複数のスレッドに分割し複数のプロセッサで並列に実行する並列プロセッサシステムにおけるフォーク後に親スレッドで更新されたレジスタを子スレッドに継承する装置において、フォーク後、親スレッドの汎用レジスタ書き込み毎に更新後のレジスタ値を親スレッド側のプロセッサから子スレッド側のプロセッサへ送信する手段と、子スレッド側のプロセッサでは子スレッドを投機的に実行し、正依存の違反を検出すると再実行を行う手段とを備えることを特徴とするプロセッサ間レジスタ継承装置。
【請求項８】
各プロセッサは、汎用レジスタに１対１に対応し、スレッド開始時点で第１の状態を保持し、対応する汎用レジスタに対するスレッド開始後の最初のアクセスがリードの場合に第２の状態を保持し、対応する汎用レジスタに対するスレッド開始後の最初のアクセスがライトの場合に第３の状態を保持する状態レジスタと、レジスタ値が親スレッド側のプロセッサから送信された汎用レジスタに対応する状態レジスタが第２の状態を保持しているとき、正依存の違反が発生したと検出する検出手段とを備える請求項７記載のプロセッサ間レジスタ継承装置。
【請求項９】
各プロセッサは、子スレッドへの転送停止、転送再開を制御する特殊命令によって操作されるマスクビットを汎用レジスタに１対１に対応して備え、フォーク後、親スレッドの汎用レジスタ書き込み毎に、書き込みの行われた汎用レジスタに対応するマスクビットが転送許可状態である場合に限って、更新後のレジスタ値を親スレッド側のプロセッサから子スレッド側のプロセッサへ送信する手段を備える請求項７または８記載のプロセッサ間レジスタ継承装置。
【請求項１０】
各プロセッサは、フォーク時点のスタックポインタの値を保存するスタックポインタ保存手段と、現在のスタックポインタの値と前記スタックポインタ保存手段に保存されたスタックポインタの値との一致を検出する検出手段と、フォーク後、親スレッドの汎用レジスタ書き込み毎に、書き込みの行われた汎用レジスタが関数の返り値レジスタである場合、及び書き込みの行われた汎用レジスタが関数の返り値レジスタ以外のレジスタであって前記検出手段で一致が検出されている場合に限って、更新後のレジスタ値を親スレッド側のプロセッサから子スレッド側のプロセッサへ送信する手段とを備える請求項７または８記載のプロセッサ間レジスタ継承装置。
【請求項１１】
各プロセッサは、各汎用レジスタに１対１に対応するストアアドレスレジスタと、ストア命令実行時に汎用レジスタ毎にストアアドレスを前記ストアアドレスレジスタに記憶する手段と、汎用レジスタの内容切り替えを検出した際に当該汎用レジスタの子スレッドへの転送を禁止状態にすると共にストアアドレスレジスタへの書き込みを停止する手段と、ロード時のアドレスをストアアドレスレジスタに記憶されたストアアドレスと比較することによって汎用レジスタの内容が元に戻ったことを検出して、当該汎用レジスタの子スレッドへの転送禁止状態を解除する手段とを備える請求項７または８記載のプロセッサ間レジスタ継承装置。
【請求項１２】
更新後の汎用レジスタの値が更新前と異なるか否かを検出する手段と、更新後の汎用レジスタの値が更新前と異なる場合に限って、更新後のレジスタ値を親スレッド側のプロセッサから子スレッド側のプロセッサへ送信する手段とを備える請求項７乃至１１の何れか１項に記載のプロセッサ間レジスタ継承装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は単一のプログラムを複数のスレッドに分割して複数のプロセッサにより並列に実行する並列プロセッサシステムに関し、特にフォーク後に親スレッドで更新されたレジスタを子スレッドに継承する方法と装置に関する。
【０００２】
【従来の技術】
単一のプログラムを並列プロセッサシステムで並列に処理する手法として、プログラムをスレッドと呼ぶ命令流に分割して複数のプロセッサで並列に実行するマルチスレッド実行方法があり、この方法を記載した文献として、特開平１０−２７１０８号公報（以下、文献１と称す）、「Ｏｎ−Ｃｈｉｐ  Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒ指向  制御並列アーキテクチャＭＵＳＣＡＴの提案」（並列処理シンポジュウムＪＳＰＰ９７論文集、情報処理学会、ｐｐ．２２９−２３６、Ｍａｙ  １９９７）（以下、文献２と称す）、特開平１０−７８８８０号公報（以下、文献３と称す）、「非数値計算プログラムのスレッド間命令レベル並列を利用するプロセッサ・アーキテクチャＳＫＹ」（並列処理シンポジウムＪＳＰＰ９８論文集、情報処理学会、ｐｐ．８７−９４、平成１０年６月）（以下、文献４と称す）、「Ｍｕｌｔｉｓｃａｌａｒ  Ｐｒｏｃｅｓｓｏｒ」（Ｇ．Ｓ．Ｓｏｈｉ，Ｓ．Ｅ．Ｂｒｅａｃｈ  ａｎｄ  Ｔ．Ｎ．Ｖｉｊａｙｋｕｍａｒ，  Ｔｈｅ２２ｎｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ａｒｃｈｉｔｅｃｔｕｒｅ，ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  ＳｏｃｉｅｔｙＰｒｅｓｓ，１９９５，ページ４１４−４２５）（以下、文献５と称す）等がある。以下、これらの文献に記載された従来の技術について説明する。
【０００３】
一般にマルチスレッド実行方法において、他のプロセッサ上に新たなスレッドを生成することを、スレッドをフォーク（ｆｏｒｋ）すると言い、フォーク動作を行った側のスレッドを親スレッド、生成された新しいスレッドを子スレッド、スレッドをフォークする箇所をフォーク点、子スレッドの先頭箇所をフォーク先アドレスまたは子スレッドの開始点と呼ぶ。文献１〜４では、スレッドのフォークを指示するためにフォーク点にフォーク命令が挿入される。フォーク命令にはフォーク先アドレスが指定され、フォーク命令の実行によりそのフォーク先アドレスから始まる子スレッドが他プロセッサ上に生成され、子スレッドの実行が開始される。また、スレッドの処理を終了させるターム（ｔｅｒｍ）命令と呼ばれる命令が用意されており、各プロセッサはターム命令を実行することによりスレッドの処理を終了する。
【０００４】
図１２にマルチスレッド実行方法の処理の概要を示す。同図（ａ）は３つのスレッドＡ、Ｂ、Ｃに分割された単一のプログラムを示す。このプログラムを単一のプロセッサで処理する場合、同図（ｂ）に示すように１つのプロセッサＰＥがスレッドＡ、Ｂ、Ｃを順番に処理していく。これに対して文献１〜５のマルチスレッド実行方法では、同図（ｃ）に示すように、１つのプロセッサＰＥ１にスレッドＡを実行させ、プロセッサＰＥ１でスレッドＡを実行している最中に、スレッドＡに埋め込まれたフォーク命令によってスレッドＢを他のプロセッサＰＥ２に生成し、プロセッサＰＥ２においてスレッドＢを実行させる。また、プロセッサＰＥ２はスレッドＢに埋め込まれたフォーク命令によってスレッドＣをプロセッサＰＥ３に生成する。プロセッサＰＥ１、ＰＥ２はそれぞれスレッドＢ、Ｃの開始点の直前に埋め込まれたターム命令によってスレッドの処理を終了し、プロセッサＰＥ３はスレッドＣの最後の命令を実行すると、その次の命令（一般にはシステムコール命令）を実行する。このように複数のプロセッサでスレッドを同時に並行して実行することにより、逐次処理に比べて性能の向上が図られる。
【０００５】
従来の他のマルチスレッド実行方法として、図１２（ｄ）に示すように、スレッドＡを実行しているプロセッサＰＥ１からフォークを複数回行うことにより、プロセッサＰＥ２にスレッドＢを、またプロセッサＰＥ３にスレッドＣをそれぞれ生成するマルチスレッド実行方法も存在する。この図１２（ｄ）のモデルに対して、同図（ｃ）に示したようにスレッドはその生存中に高々１回に限って有効な子スレッドを生成することができるという制約を課したマルチスレッド実行方法をフォーク１回モデルと呼ぶ。フォーク１回モデルでは、スレッド管理の大幅な簡略化が可能となり、現実的なハードウェア規模でスレッド管理部のハードウェア化が実現できる。また、個々のプロセッサは子スレッドを生成する他プロセッサが１プロセッサに限定されるため、隣接するプロセッサを単方向にリング状に接続した並列プロセッサシステムでマルチスレッド実行が可能となる。本発明はこのようなフォーク１回モデルを前提とする。
【０００６】
子スレッドをフォークした場合、親スレッドから子スレッドへのレジスタ継承が必要になる。このレジスタ継承に関しては、一般に２通りの方式がある。１つは、文献１〜３の並列プロセッサシステムで採用されているように、親スレッドのフォーク時点のレジスタファイルの内容だけを継承対象とし、フォーク後に更新されたレジスタは継承しない方式であり、これを以下、フォーク時レジスタ転送方式と呼ぶ。もう１つは、文献４、５の並列プロセッサシステムで採用されているように、フォーク後に更新されたレジスタも継承対象とする方式である。これを以下、フォーク後レジスタ転送方式と呼ぶ。
【０００７】
例えば図１３（ａ）に示すように、レジスタｒ２０の値を＋１する命令１、関数ｆｕｎｃを呼出す命令２、レジスタｒ２０の値を＋１する命令３、関数ｆｕｎｃを呼出す命令４、レジスタｒ２０の値を＋１した値をレジスタｒ１３に置く命令５が、その順に記述された逐次実行プログラムにおいて、命令５以降の命令流を子スレッドとして実行する場合、フォーク時レジスタ転送方式では、同図（ｂ）に示すように子スレッドが参照するレジスタｒ２０の値が確定する時点にフォーク命令を挿入する。
【０００８】
他方、フォーク後レジスタ転送方式では、レジスタｒ２０の確定値をフォーク後に子スレッドへ転送するため、レジスタｒ２０の値が確定するのを待たずに子スレッドを先行してフォークすることができる。従って、例えば図１３（ｃ）に示すように命令１の直前にフォーク命令を挿入することができる。但し、このままでは子スレッド側で正依存（ＲＡＷ；Ｒｅａｄ  Ａｆｔｅｒ  Ｗｒｉｔｅ）違反が生じるため、文献４及び５ではコンパイラによる静的な依存解析によって子スレッドで必要なレジスタ及びそのレジスタ値が確定する時点を検出し、転送すべきレジスタが定義ないし決定した直後にレジスタ転送命令を挿入するか（文献４）、命令コード中にレジスタ転送ビットを設け（文献５）、共に受信側では、確定したレジスタ値が受信されるまで命令の実行を待ち合わせている。
【０００９】
マルチスレッド実行方法では、実行の確定した先行スレッドを並列に実行することを基本とするが、実際のプログラムでは実行の確定するスレッドが充分に得られない場合も多い。また、動的に決定される依存やコンパイラ解析能力の限界等により並列化率が低く抑えられ所望の性能が得られない可能性が生じる。このため文献１等では、制御投機を導入し、ハードウェア的にスレッドの投機実行をサポートしている。制御投機では、実行する可能性の高いスレッドを実行確定前に投機的に実行する。投機状態のスレッドは、実行の取り消しがハードウェア上可能である範囲内で仮実行を行う。子スレッドが仮実行を行っている状態を仮実行状態と言い、子スレッドが仮実行状態にあるとき親スレッドはスレッド仮生成状態にあると言う。仮実行状態の子スレッドでは共有メモリへの書き込みは抑制され、別途設けた仮実行用バッファ（ｔｅｍｐｏｒａｒｙ  ｂｕｆｆｅｒ）に対して書き込みが行われる。投機が正しいことが確定すると、親スレッドから子スレッドに対して投機成功通知が出され、子スレッドは仮実行用バッファの内容を共有メモリに反映し、仮実行用バッファを用いない通常の状態となる。また親スレッドはスレッド仮生成状態からスレッド生成状態となる。他方、投機が失敗したことが確定すると、親スレッドでスレッド破棄命令（ａｂｏｒｔ）が実行され、子スレッド以下の実行がキャンセルされる。また、親スレッドはスレッド仮生成状態からスレッド未生成状態となり、再び子スレッドの生成が可能になる。つまり、フォーク１回モデルではスレッド生成は高々１回に限定されるが、制御投機を行い、投機が失敗した場合には再びフォークが可能となる。この場合においても、生成できる有効な子スレッドは高々１つである。
【００１０】
その他、文献２に記載のＭＵＳＣＡＴでは、スレッド間の同期命令など、スレッドの並列動作を柔軟に制御するための専用命令が数多く用意されている。
【００１１】
【発明が解決しようとする課題】
前述したようにフォーク後レジスタ転送方式では、子スレッドで必要なレジスタの値が確定するのを待たずに先行して子スレッドをフォークすることができ、その分、フォーク時レジスタ転送方式に比べて命令実行の並列度が向上する。しかし、フォーク後に親スレッドで更新されたレジスタを子スレッドに継承するため、ＲＡＷ違反が子スレッド側で生じないように制御する必要がある。この制御を、文献４及び５に記載された前述した方法で実現すると、不必要な同期が発生し、性能が低下する場合がある。その理由はＲＡＷ違反をコンパイラ時点の依存解析によって静的に解消しようとしており、且つ、子スレッドに継承すべきレジスタについて親スレッドと子スレッド間で必ず同期をとるようにしているためである。以下、具体例を挙げてこの問題点を説明する。
【００１２】
今、図１４（ａ）に示すように、レジスタｒ１０の更新命令を含むブロックａ、分岐命令ｂ、レジスタｒ１０の更新命令を含むブロックｃ、レジスタｒ１０の参照命令を含むブロックｄを有する逐次処理プログラムを想定し、ブロックａの直前でブロックｄを子スレッドとしてフォークすることを考える。この場合、ブロックｄでレジスタｒ１０が参照されているため、親スレッドから子スレッドへレジスタｒ１０の値を継承する必要がある。フォーク点以降、レジスタｒ１０はブロックａとブロックｃで更新されているが、ブロックｃは分岐命令ｂの分岐成立時にのみ実行されるため、分岐成立時にはブロックｃで更新されたレジスタｒ１０の値を、また分岐不成立時にはブロックａで更新されたレジスタｒ１０の値を、子スレッドへ継承する必要がある。文献５等による従来方法では、このような場合、図１４（ｂ）に示すように分岐成立、不成立が確定した箇所にレジスタｒ１０の確定値を子スレッドへ転送する命令を挿入しなければならない。このため、実際のプログラム実行に際しては分岐命令ｂの分岐成功、不成功にかかわらず子スレッドのレジスタｒ１０を参照する命令が長期間待たされることになる。分岐成立のときはブロックｃで更新されたレジスタｒ１０の値を参照するため、当該待ち合わせは致し方ないが、分岐不成立の場合はブロックａで更新されたレジスタｒ１０の値がそのまま使えるため、当該待ち合わせは不必要な同期待ちと言える。
【００１３】
本発明の目的は、フォーク後に親スレッドで更新されたレジスタを子スレッドに継承する新規な方法と装置を提供することにある。
【００１４】
本発明の別の目的は、フォーク後レジスタ転送方式を採用する並列プロセッサシステムにおいて、ＲＡＷ違反をコンパイル時点でなくプログラム実行時に動的に解消し得るようにすることにある。
【００１５】
本発明の他の目的は、フォーク後レジスタ転送方式を採用する並列プロセッサシステムにおいて、ＲＡＷ違反を解消するために不必要な待ち合わせが発生しないようにして性能の向上を図ることにある。
【００１６】
【課題を解決するための手段】
第１の発明は、単一のプログラムを複数のスレッドに分割し複数のプロセッサで並列に実行する並列プロセッサシステムにおいてフォーク後に親スレッドで更新されたレジスタを子スレッドに継承する方法において、フォーク後、親スレッドの汎用レジスタ書き込み毎に更新後のレジスタ値を親スレッド側のプロセッサから子スレッド側のプロセッサへ送信し、子スレッド側のプロセッサでは子スレッドを投機的に実行し、正依存の違反を検出すると再実行を行う。正依存の違反の検出は、具体的には、各プロセッサの汎用レジスタに１対１に対応し、スレッド開始時点で第１の状態を保持し、対応する汎用レジスタに対するスレッド開始後の最初のアクセスがリードの場合に第２の状態を保持し、対応する汎用レジスタに対するスレッド開始後の最初のアクセスがライトの場合に第３の状態を保持する状態レジスタを備え、レジスタ値が親スレッド側のプロセッサから送信された汎用レジスタに対応する状態レジスタが第２の状態を保持しているとき、正依存の違反が発生したと検出する。
【００１７】
第２の発明は、第１の発明において、子スレッドへの転送停止、転送再開を制御する特殊命令によって操作されるマスクビットを汎用レジスタに１対１に対応して備え、フォーク後、親スレッドの汎用レジスタ書き込み毎に、書き込みの行われた汎用レジスタに対応するマスクビットが転送許可状態である場合に限って、更新後のレジスタ値を親スレッド側のプロセッサから子スレッド側のプロセッサへ送信する。
【００１８】
第３の発明は、第１の発明において、フォーク時点のスタックポインタの値を保存するスタックポインタ保存手段と、現在のスタックポインタの値と前記スタックポインタ保存手段に保存されたスタックポインタの値との一致を検出する検出手段とを備え、フォーク後、親スレッドの汎用レジスタ書き込み毎に、書き込みの行われた汎用レジスタが関数の返り値レジスタである場合、及び書き込みの行われた汎用レジスタが関数の返り値レジスタ以外のレジスタであって前記検出手段で一致が検出されている場合に限って、更新後のレジスタ値を親スレッド側のプロセッサから子スレッド側のプロセッサへ送信する。
【００１９】
第４の発明は、第１の発明において、各汎用レジスタに１対１に対応するストアアドレスレジスタを備え、ストア命令実行時に汎用レジスタ毎にストアアドレスを前記ストアアドレスレジスタに記憶し、汎用レジスタの内容切り替えを検出した際に当該汎用レジスタの子スレッドへの転送を禁止状態にすると共にストアアドレスレジスタへの書き込みを停止し、ロード時のアドレスをストアアドレスレジスタに記憶されたストアアドレスと比較することによって汎用レジスタの内容が元に戻ったことを検出して、当該汎用レジスタの子スレッドへの転送禁止状態を解除する。
【００２０】
第５の発明は、第１乃至第４の発明において、更新後の汎用レジスタの値が更新前と異なる場合に限って、更新後のレジスタ値を親スレッド側のプロセッサから子スレッド側のプロセッサへ送信する。
【００２１】
【作用】
第１の発明にあっては、フォーク後、親スレッドの汎用レジスタ書き込み毎に更新後のレジスタ値を親スレッド側のプロセッサから子スレッド側のプロセッサへ送信し、子スレッド側のプロセッサでは子スレッドを投機的に実行し、ＲＡＷ違反を検出すると再実行を行うことにより、ＲＡＷ違反をコンパイル時点でなくプログラム実行時に動的に解消し、且つＲＡＷ違反を解消するために不必要な待ち合わせが発生しないようにする。
【００２２】
第１の発明の作用を従来の技術の説明で用いた図１４（ａ）の逐次処理プログラムを例に以下説明する。ブロックａの直前でブロックｄを子スレッドとしてフォークする場合、第１の発明では、子スレッド側のプロセッサはブロックｄから子スレッドを投機的に実行する。他方、親スレッド側のプロセッサは、フォーク後、ブロックａでレジスタｒ１０が更新されると、その値を子スレッド側に転送し、また分岐命令ｂの分岐が成立してブロックｃを実行した場合、ブロックｃで更新されたレジスタｒ１０の値を再び子スレッド側に転送する。投機的に実行を開始した子スレッドがＲＡＷ違反によって再実行するか否かは、親スレッドにおける分岐命令ｂの分岐の成否および親スレッドにおけるレジスタｒ１０の更新、転送のタイミングと子スレッドにおけるレジスタｒ１０の参照のタイミングによって決まる。図１に幾つかの実行シーケンス例を示す。
【００２３】
図１（ａ）は、分岐命令ｂの分岐が不成立で、且つ子スレッド側のプロセッサ＃１がブロックｄのレジスタｒ１０の参照命令を、親スレッド側のプロセッサ＃０からブロックａで更新されたレジスタｒ１０の値を受信した後に実行した場合のシーケンスを示す。この場合、ＲＡＷ違反は発生せず、子スレッドの再実行はない。図１（ｂ）は、分岐命令ｂの分岐が不成立である点は図１（ａ）と同じであるが、親スレッド側のプロセッサ＃０からブロックａで更新されたレジスタｒ１０の値を受信する前に、子スレッド側のプロセッサ＃１がブロックｄのレジスタｒ１０の参照命令を実行した点が相違しており、この場合、ＲＡＷ違反が発生し、子スレッドの再実行が行われる。他方、図１（ｃ）は、分岐命令ｂの分岐が成立した場合の実行シーケンス例を示し、親スレッドのブロックｃで更新されたレジスタｒ１０の値を受信した時点でＲＡＷが検出され、子スレッドが再実行されている。
【００２４】
これらの実行シーケンスを図１４（ｂ）に示した従来方法と比較すると、図１４（ｂ）ではブロックｃの直後にレジスタｒ１０を子スレッドに転送する命令が挿入されているため、この転送のタイミングは図１（ｃ）におけるブロックｃで更新されたレジスタｒ１０の転送タイミングとほぼ近い。従来方法は、このタイミングでブロックｄのレジスタｒ１０の参照命令の実行が初めて開始される。従って、本発明によれば、分岐命令ｂの分岐が成立する状況下においても従来方法にほぼ近い性能を確保しながら、分岐不成立時には図１（ａ）及び（ｂ）に示す如く従来方法に比べて子スレッドの処理を格段に早めることができる。
【００２５】
また第１の発明では、フォーク後、親スレッドでレジスタが更新されると、必ずそのレジスタの値を子スレッド側のプロセッサに転送するため、従来方法におけるようなレジスタ転送命令などの付加情報を並列化プログラム中に挿入する必要がなく、またコンパイラによる静的な依存解析が必ずしも必要でないという利点も有する。
【００２６】
他方、レジスタの更新時に常に転送を行うと却って性能が低下する場合もある。例えば、汎用レジスタはその個数に限りがあるため、使える汎用レジスタが無くなったときに使用中の汎用レジスタの値をメモリに退避して当該汎用レジスタを別の目的で使用し、その使用を終えるとメモリに退避してあるレジスタ値を当該汎用レジスタに復帰する操作が行われる。この操作は汎用レジスタの内容切り替えと呼ばれているが、この内容切り替えが親スレッドで実行されると第１の発明では転送の必要のないレジスタ値も転送されてしまい、子スレッド側でＲＡＷ違反による無駄な再実行が起こってしまう。また、レジスタが前回と同じ値に更新された場合、子スレッドへの転送は本来不要であるが、第１の発明ではレジスタ転送が実行され、子スレッド側でＲＡＷ違反による無駄な再実行が起こってしまう。第２乃至第４の発明では、汎用レジスタの内容切り替えに伴う無用なレジスタ転送を回避し、第５の発明では、レジスタが前回と同じ値に更新された場合の無用なレジスタ転送を回避する。
【００２７】
【発明の実施の形態】
次に本発明の実施の形態の例について図面を参照して詳細に説明する。
【００２８】
【第１の実施の形態】
図２を参照すると、本発明を適用した並列プロセッサシステムの一例は、４スレッド並列実行型プロセッサであり、４個のプロセッサ１−ｉ（ｉ＝０〜３）が信号線２−ｉによってスレッド管理部３に接続されると共に、信号線４−ｉによって共有のメモリ５に接続されている。また、隣接するプロセッサ同士が通信バス６−０〜６−３によって単方向にリング状に接続されている。この例では、４スレッド並列実行型プロセッサを取り上げたが、８スレッドや１６スレッドの並列実行型プロセッサ等、一般にｎ（≧２）スレッド並列実行型プロセッサに対して本発明は適用可能である。
【００２９】
各プロセッサ１−ｉは、プログラムカウンタ（以下、ＰＣと称す）及びレジスタファイルを独立に有し、ＰＣに従って、メモリ５中のスレッドの命令を同時にフェッチ、解釈、実行する機能を有している。また、各プロセッサ１−ｉは、スレッド実行の取り消し（キャンセル）が可能なように仮実行用バッファ（ｔｅｍｐｏｒａｒｙ  ｂｕｆｆｅｒ）を有している。各プロセッサ１−ｉは、スレッド管理部３から信号線２−ｉを通じてターゲットＰＣ値を伴うスレッド開始要求７ｃが送信された時点で、仮実行用バッファを使ってスレッドの実行を仮実行状態で開始する。この時点でスレッド管理部３において当該プロセッサ１−ｉはビジー状態として管理される。スレッドの実行を終了するプロセッサ１−ｉは、スレッド管理部３に対して信号線２−ｉを通じてスレッド終了通知７ｄを送信する。このスレッド終了通知７ｄは、通知元のプロセッサ１−ｉが最古親スレッドを実行していることを条件にスレッド管理部３で受理され、当該プロセッサ１−ｉはフリー状態として管理され、プロセッサ１−ｉにスレッド終了許可７ｅが返却される。プロセッサ１−ｉはスレッド終了許可７ｅを受信した時点で仮実行状態を解き、仮実行用バッファの内容を共有のメモリ５に反映させ、スレッドの実行を終える。
【００３０】
各プロセッサ１−ｉは、実行中の親スレッドに存在するフォーク命令によって隣接する一方のプロセッサ１−ｊ（ｉ≠ｊ）（プロセッサ１−０はプロセッサ１−１、プロセッサ１−１はプロセッサ１−２、プロセッサ１−２はプロセッサ１−３、プロセッサ１−３はプロセッサ１−０）に子スレッドをフォークすることができる。各プロセッサ１−ｉは、子スレッドのフォークを行う際、信号線２−ｉを通じてスレッド管理部３に対し、子スレッドのフォーク先アドレス（開始ＰＣ値）を伴うフォーク要求７ａを送信する。スレッド管理部３は、フォーク要求７ａを受信すると、隣接プロセッサの状態に基づいて、隣接する他プロセッサ１−ｊに対するフォークが可能か否かを判定し、可能ならば当該プロセッサ１−ｊに対してフォーク先アドレスを伴うスレッド開始要求７ｃを送信する一方、フォーク要求元のプロセッサ１−ｉに対しては、フォーク応答７ｂを返却する。フォーク応答７ｂを受信したプロセッサ１−ｉは、通信バス６−ｉを通じてフォーク先プロセッサ１−ｊに親スレッドのレジスタの値を転送するレジスタ継承を行い、スレッド開始要求７ｃを受信したプロセッサ１−ｊは、フォーク先アドレスから子スレッドの実行を投機的に開始する。
【００３１】
図３に各々のプロセッサ１−ｉの要部ブロック図を示す。図３において、制御ユニット１１は、ＰＣや、ＰＣに従ってメモリ５からスレッドの命令をフェッチする命令フェッチユニットや、フェッチされた命令をデコードし、実行する実行ユニットを含んでいる。レジスタファイル１３は汎用レジスタ１２−０〜１２−ｍの集合であり、ユニット１１からレジスタリードバス１４及びレジスタリード信号１６によってリードでき、レジスタライトバス１５及びレジスタライト信号１７によってライトできる。レジスタリードバス１４は読み出し値を転送するバス、レジスタライトバス１５は書き込み値を転送するバスであり、レジスタリード信号１６は読み出し対象とする汎用レジスタのレジスタ番号を、レジスタライト信号１７は書き込み対象とする汎用レジスタのレジスタ番号をそれぞれ示す。つまり、ユニット１１は、汎用レジスタ１２−ｋ（ｋ＝０〜ｍ）のアクセス時、リードのときは汎用レジスタ１２−ｋのレジスタ番号をレジスタリード信号１６として出力し、ライトのときは汎用レジスタ１２−ｋのレジスタ番号をレジスタライト信号１７として出力する。仮実行用バッファ１８は、バス１９を通じてユニット１１に接続されており、ユニット１１はこの仮実行用バッファ１８を使ってスレッドの仮実行（投機実行）を行う。
【００３２】
ステータスレジスタ２０−ｋは、汎用レジスタ１２−ｋに１対１に対応しており、レジスタリード信号１６及びレジスタライト信号１７が入力されている。各ステータスレジスタ２０−ｋの初期状態はクリーン状態であり、レジスタリード信号１６のレジスタ番号が自レジスタに対応する汎用レジスタ１２−ｋを示す場合、現在の状態がクリーン状態であればリード状態に遷移し、それ以外は現状態を維持し、レジスタライト信号１７のレジスタ番号が自レジスタに対応する汎用レジスタ１２−ｋを示す場合、現在の状態がクリーン状態であればローカルストア状態に遷移し、それ以外は現状態を維持する。各ステータスレジスタ２０−ｋの状態遷移を図４に示す。各ステータスレジスタ２０−ｋは、当該プロセッサにおけるスレッド開始時にクリーン状態にあり、スレッド実行開始後、対応する汎用レジスタ１２−ｋに対するユニット１１からの最初のアクセスが読み出しの場合はリード状態に遷移し、最初のアクセスが書き込みの場合は変数定義から始まったことを表すローカルストア状態に遷移する。共に、その後にリード、ライトが行われても、リード状態、ローカルストア状態を維持する。
【００３３】
通信バス２１は、フォーク先プロセッサに対してレジスタ継承を行うためのバスであり、ユニット１１がレジスタライトバス１５に出力する書き込み値２２とレジスタライト信号１７に出力するレジスタ番号２３とを転送する。通信バス２４は、フォーク元プロセッサからレジスタ継承を受けるためのバスであり、レジスタへの書き込み値２５とレジスタ番号２６とを転送する。汎用レジスタ１２−０〜１２−ｍのうち、レジスタ番号２６と同じレジスタ番号の汎用レジスタが書き込み値２５で書き換えられる。通信バス２４は、フォーク元プロセッサにおいては通信バス２１に相当する。通信バス２１、２４は図２の通信バス６−０〜６−３に対応する。
【００３４】
ＲＡＷ検出回路２７は、ステータスレジスタ２０−０〜２０−ｍの状態と、フォーク元プロセッサから通信バス２４に出されたレジスタ番号２６とから、ＲＡＷ違反を検出する検出回路である。ステータスレジスタ２０−０〜２０−ｍのうち、レジスタ番号２６が示すステータスレジスタの状態がリード状態であれば、ＲＡＷ違反が発生したと検出する。ＲＡＷ検出回路２７は、ＲＡＷ違反を検出すると、キャンセル信号２８を仮実行用バッファ１８に出力し、仮実行用バッファ１８の内容を全てキャンセルする。キャンセル信号２８はユニット１１にも通知されており、ユニット１１は実行中のスレッドをキャンセルし、その開始点よりリスタートする。このリスタート時、ステータスレジスタ２０−ｋは全てクリーン状態に戻される。なお、従来の制御投機等と同様に、キャンセルされたスレッドが子スレッドをフォークしていた場合、子スレッド以下のスレッドもキャンセルされる。
【００３５】
次に、フォーク後に親スレッドで更新されたレジスタを子スレッドに継承する動作を親スレッド側のプロセッサと子スレッド側のプロセッサに分けて、図３を参照して説明する。
【００３６】
（１）親スレッド側のプロセッサ
ユニット１１は、子スレッドをフォークすると、そのフォーク後、レジスタライトバス１５を介して何れかの汎用レジスタ１２−ｋを更新する際に、そのレジスタ番号２３をレジスタライト信号１７として出力する。通信バス２１は、レジスタライトバス１５に出力された書き込み値２２とレジスタライト信号１７に出力されたレジスタ番号２３を、子スレッドをフォークしたプロセッサに向けて送信する。
【００３７】
（２）子スレッド側のプロセッサ
ユニット１１は、信号線２−ｉを通じてスレッド管理部３からスレッド開始要求７ｃを受信すると、全てのステータスレジスタ２０−ｋをクリーン状態に初期化し、仮実行用バッファ１８を使って、スレッド開始要求７ｃで指定されたスレッドの開始点から汎用レジスタに関して投機的にスレッドを実行する。実行の過程で何れかの汎用レジスタ１２−ｋに対するアクセスが必要になると、リードの場合はレジスタリードバス１４を通じてアクセスし、リードした汎用レジスタの番号をレジスタリード信号１６に出力する。また、ライトの場合はレジスタライトバス１５を通じてアクセスし、ライトした汎用レジスタの番号をレジスタライト信号１７に出力する。
【００３８】
各ステータスレジスタ２０−ｋは、対応する汎用レジスタ１２−ｋに対する最初のアクセスがリードの場合はリード状態に遷移し、最初のアクセスがライトの場合はローカルストア状態に遷移する。また、通信バス２４経由で親スレッド側のプロセッサから書き込み値２５とレジスタ番号２６が送信されてくると、汎用レジスタ１２−０〜１２−ｍのうち、レジスタ番号２６に対応する汎用レジスタが書き込み値２５で書き換えられる。若し、今回更新された汎用レジスタ１２−ｋに対応するステータスレジスタ２０−ｋがリード状態であれば、ＲＡＷ検出回路２７はＲＡＷ違反を検出し、キャンセル信号２８を出力する。これにより、仮実行用バッファ１８がクリアされ、ユニット１１は実行中のスレッドをキャンセルし、スレッドの開始点から当該スレッドを再び投機的に実行する。このとき全てのステータスレジスタ２０−ｋはクリーン状態に初期化される。
【００３９】
ユニット１１は、スレッドをその最後の命令まで投機的に実行すると、スレッド管理部３に対して信号線２−ｉを通じてスレッド終了通知７ｄを送信し、スレッド終了許可７ｅをスレッド管理部３から受信した時点で、仮実行用バッファ１８の内容を共有のメモリ５に反映させ、スレッドの実行を終える。
【００４０】
【第２の実施の形態】
本実施の形態は、子スレッドへのレジスタ転送の停止、再開を制御する特殊命令を用意し、フォーク後の親スレッドの汎用レジスタ書き込み時、転送許可状態にある汎用レジスタだけを子スレッド側のプロセッサへ送信するようにした点で第１の実施の形態と相違する。以下、第１の実施の形態との相違点を中心に本実施の形態を説明する。
【００４１】
図５を参照すると、本実施の形態における並列プロセッサシステムの各々のプロセッサ１−ｉは、図３に示した構成に加えて、汎用レジスタ１２−ｋに１対１に対応するマスクビット３１−ｋと、レジスタライト信号１７が示すレジスタ番号２３の汎用レジスタ１２−ｋに対応するマスクビット３１−ｋが転送許可状態にある場合に限って、今回書き込みの行われた汎用レジスタのレジスタ番号２３を通信バス２１に出力するゲート回路３２とを備えている。マスクビット３１−ｋは、スレッドの開始時点で転送許可状態（例えば“１”）にあり、ユニット１１で実行される特殊命令により更新バス３３上に出力される制御信号によって転送禁止状態（例えば“０”）に更新され、または再び転送許可状態に戻される。
【００４２】
上記の特殊命令を、本実施の形態では、ｐｒｏｐａｇａｔｅ命令（略して、ｐｒｏｐ命令）と呼ぶ。ｐｒｏｐ命令は、転送停止用と転送再開用の２種類があり、並列化プログラム中に以下のような形式で挿入される。
ｐｒｏｐ  ！ｒ２０    …（ａ）
ｐｒｏｐ    ｒ２０    …（ｂ）
【００４３】
ｐｒｏｐ命令ａは、この命令以降、レジスタｒ２０の子スレッドへの転送を停止する命令である。ｐｒｏｐ命令ｂは、この命令以降、レジスタｒ２０の子スレッドへの転送を再開する命令である。
【００４４】
図６（ａ）に、ｐｒｏｐ命令を挿入する前の並列化プログラムの例を示す。このプログラムでは関数ｆｕｎｃ内でレジスタｒ２０に関して内容切り替えが行われている。この関数ｆｕｎｃ内のレジスタｒ２０の書き込みは真の依存ではないが、第１の実施の形態では内容切り替えに伴うレジスタｒ２０の更新時にレジスタｒ２０の値が子スレッド側に転送されるためＲＡＷ違反検出による再実行が起こってしまう。
【００４５】
図６（ｂ）に、ｐｒｏｐ命令を挿入した並列化プログラムの例を示す。関数ｆｕｎｃの呼び出し前後でｐｒｏｐ命令によりレジスタｒ２０の転送を停止、再開することによって、無駄な転送およびＲＡＷ違反検出による再実行を防止している。
【００４６】
次に、図６（ｂ）のプログラムを例に本実施の形態の動作を説明する。なお、子スレッド側のプロセッサの動作は第１の実施の形態と同じなので、親スレッド側のプロセッサの動作だけを説明する。
【００４７】
ユニット１１は、フォーク命令「ｆｏｒｋ  ｔｈ１」によって子スレッドをフォークする。次のレジスタｒ２０の更新を含む命令「ａｄｄ  ｒ２０，ｒ２０，１」をユニット１１が実行したとき、レジスタｒ２０に対応するマスクビット３１−ｋは転送許可状態の初期状態にあるため、更新後のレジスタｒ２０の値がレジスタ番号と共に通信バス２１経由で子スレッド側のプロセッサに送信される。次の命令はｐｒｏｐ命令ａであり、レジスタｒ２０に対応するマスクビット３１−ｋが転送禁止状態に設定される。従って、関数ｆｕｎｃが呼び出され、その中でレジスタｒ２０の更新を含む命令「ｍｏｖｅ  ｒ２０，ｒ０」、「ｌｗ  ｒ２０，２０（ｓｐ）」等がユニット１１で実行されても、レジスタｒ２０は転送されない。関数ｆｕｎｃの呼び出し命令の直後の命令はｐｒｏｐ命令ｂであり、レジスタｒ２０に対応するマスクビット３１−ｋが転送許可状態に戻される。従って、次にレジスタｒ２０の更新を含む命令「ａｄｄ  ｒ２０，ｒ２０，１」をユニット１１が実行すると、更新後のレジスタｒ２０の値が子スレッド側のプロセッサへ転送される。以下、図６（ｂ）のプログラムでは、次の関数ｆｕｎｃの呼び出し前にｐｒｏｐ命令ａによってレジスタｒ２０の転送が再び禁止されている。
【００４８】
【第３の実施の形態】
本実施の形態は、汎用レジスタの内容切り替えのほとんどが関数呼び出しに因るものである点に着目し、親スレッド側プロセッサはフォーク時にスタックポインタ（ＳＰ）の値を保存しておき、フォーク後に汎用レジスタの更新があった時、更新された汎用レジスタが関数の返り値レジスタである場合を除き、現在のスタックポインタの値と保存してあったスタックポインタの値が等しいときのみ更新後の汎用レジスタの値を子スレッド側プロセッサへ転送するようにした点で第１の実施の形態と相違する。以下、第１の実施の形態との相違点を中心に本実施の形態を説明する。
【００４９】
図７を参照すると、本実施の形態における並列プロセッサシステムの各々のプロセッサ１−ｉは、図３に示した構成に加えて、フォーク時点のスタックポインタ（ＳＰ）の値を保存するシャドウスタックポインタ４１と、現在のスタックポインタ（ＳＰ）の値とシャドウスタックポインタ４１の値の一致を検出する比較回路４２と、この比較回路４２が一致を検出したときに限ってレジスタライト信号１７が示すレジスタ番号２３を通信バス２１に出力するゲート回路４３と、書き込みの行われた汎用レジスタが関数の返り値レジスタである場合には、比較回路４２の一致、不一致にかかわらず当該返り値レジスタのレジスタ番号２３を通信バス２１に出力する返り値レジスタライト信号線４４とを備えている。
【００５０】
次に、本実施の形態の動作を説明する。なお、子スレッド側のプロセッサの動作は第１の実施の形態と同じなので、親スレッド側のプロセッサの動作だけを説明する。
【００５１】
ユニット１１は、子スレッドをフォークすると、シャドウスタックポインタ４１にフォーク信号４５を出力することにより、レジスタファイル１３中の汎用レジスタの１つであるスタックポインタ（ＳＰ）の値を信号線４６経由でシャドウスタックポインタ４１に保存する。その後、シャドウスタックポインタ４１に保存されたスタックポインタの値は、比較回路４２において、信号線４６経由で読み出されているスタックポインタ（ＳＰ）の値と比較され、一致、不一致の信号がゲート回路４３に出力される。
【００５２】
ユニット１１は、子スレッドのフォーク後、レジスタライトバス１５を介して何れかの汎用レジスタ１２−ｋを更新する毎に、そのレジスタ番号をレジスタライト信号１７として出力する。また、書き込みの行われた汎用レジスタが関数の返り値レジスタである場合には、返り値レジスタの番号を返り値レジスタライト信号線４４に出力する。関数の返り値レジスタは、コンピュータのアーキテクチャ、コンパイラなどにより事前に決まっている。若し、書き込みの行われた汎用レジスタが関数の返り値レジスタである場合、返り値レジスタライト信号線４４上のレジスタ番号２３とレジスタライトバス１５上の書き込み値２２とが通信バス２２によって子スレッド側プロセッサへ転送される。また、書き込みの行われた汎用レジスタが関数の返り値レジスタ以外の場合、比較回路４２において、現在のスタックポインタ（ＳＰ）とシャドウスタックポインタ４１に保存されているスタックポインタ値とが一致している場合に限って、レジスタライト信号１７のレジスタ番号２３がゲート回路４３を通過し、書き込み値２２と共に通信バス２２によって子スレッド側プロセッサへ転送される。
【００５３】
例えば図６（ａ）に示したプログラムの場合、フォーク命令「ｆｏｒｋ  ｔｈ１」によって子スレッドをフォークした時点のスタックポインタ（ＳＰ）の値が信号線４６経由でシャドウスタックポインタ４１に保存され、次のレジスタｒ２０の更新を含む命令「ａｄｄ  ｒ２０，ｒ２０，１」の時点では、現在のスタックポインタ（ＳＰ）の値がシャドウスタックポインタ４１に保存された値と一致するので、更新後のレジスタｒ２０の値がレジスタ番号と共に通信バス２１経由で子スレッド側のプロセッサに送信される。次の関数呼出し命令によって関数ｆｕｎｃが呼び出され、スタックポインタ（ＳＰ）が更新されると、シャドウスタックポインタ４１に保存された値と相違することになり、レジスタｒ２０の更新を含む命令「ｍｏｖｅ  ｒ２０，ｒ０」、「ｌｗ  ｒ２０，２０（ｓｐ）」等がユニット１１で実行されても、レジスタｒ２０は転送されない。その後、スタックポインタ（ＳＰ）が元の値に復帰し、関数ｆｕｎｃの処理が終了すると、スタックポインタ（ＳＰ）の値がシャドウスタックポインタ４１の値と等しくなるので、次にレジスタｒ２０の更新を含む命令「ａｄｄ  ｒ２０，ｒ２０，１」をユニット１１が実行すると、更新後のレジスタｒ２０の値が子スレッド側のプロセッサへ転送される。
【００５４】
【第４の実施の形態】
本実施の形態は、汎用レジスタの内容切り替えはメモリ（特にスタック領域）へのストア、ロードを伴う場合が多いこと、内容切り替えが起こったということは、「レジスタを参照することなしに当該レジスタにデータを書き込む命令」を検出することで付加情報無しで判断可能である点に着目し、各汎用レジスタに１対１に対応するストアアドレスレジスタを設け、ストア命令実行時に汎用レジスタ毎のストアアドレスを対応するストアアドレスレジスタに記憶しておき、汎用レジスタの内容切り替えを検出した際に当該汎用レジスタの子スレッドへの転送を禁止状態にすると共にストアアドレスレジスタへの書き込みを停止し、他方、ロード時のアドレスをストアアドレスレジスタに記憶されたストアアドレスと比較することによって汎用レジスタの内容が元に戻ったか否かを判断して、子スレッドへの転送禁止状態を解除するようにした点で第１の実施の形態と相違する。以下、第１の実施の形態との相違点を中心に本実施の形態を説明する。
【００５５】
図８を参照すると、本実施の形態における並列プロセッサシステムの各々のプロセッサ１−ｉは、図３に示した構成に加えて、汎用レジスタ１２−ｋに１対１に対応するストアアドレスレジスタ５１−ｋ及びマスクビット５２−ｋと、レジスタライト信号１７が示すレジスタ番号２３の汎用レジスタ１２−ｋに対応するマスクビット５２−ｋが転送許可状態（例えば“１”）にある場合に限って、今回更新されたレジスタ番号２３を通信バス２１に出力するゲート回路５３と、ユニット１１から信号線５４及びタイミング調整用のディレイ５９を通じて出力されるロードアドレスに一致するストアアドレスがストアアドレスレジスタ５１−ｋに記録されているか否かを検出する比較回路５５とを備えている。
【００５６】
各ストアアドレスレジスタ５１−ｋには、レジスタライト信号１７が示すレジスタ番号２３と信号線５６を通じてユニット１１から出力されるストアアドレスとが入力されており、レジスタ番号２３に対応するストアアドレスレジスタ５１−ｋに信号線５６上のストアアドレスが記録される。但し、対応するマスクビット５２−ｋが転送禁止状態（例えば“０”）に設定されている場合、新たなストアアドレスの記録は行われない。各ストアアドレスレジスタ５１−ｋに記録されたストアアドレスは、参照バス５８を介して比較回路５５から参照可能になっている。
【００５７】
各マスクビット５２−ｋは、ユニット１１から更新バス５７を通じて転送許可状態、転送禁止状態に設定でき、また比較回路５５の出力によって転送許可状態に設定することができる。各マスクビット５２−ｋの出力はゲート回路５３及び対応するストアアドレスレジスタ５１−ｋに出力される。
【００５８】
次に、本実施の形態の動作を説明する。なお、子スレッド側のプロセッサの動作は第１の実施の形態と同じなので、親スレッド側のプロセッサの動作だけを説明する。
【００５９】
ユニット１１は、子スレッドのフォーク時点で、更新バス５７を通じて全てのマスクビット５２−ｋを転送許可状態に初期設定する。その後、汎用レジスタ１２−ｋのリードを含むストア命令の実行時、レジスタリード信号１６に汎用レジスタ１２−ｋのレジスタ番号を出力すると共に信号線５６にそのストアアドレスを出力し、汎用レジスタ１２−ｋに対応するストアアドレスレジスタ５１−ｋにストアアドレスを記録する。また、汎用レジスタ１２−ｋについてその値を参照することなしにデータを書き込むムーブ命令などの命令の実行時、汎用レジスタ１２−ｋの内容切り替えが起こったものと判断し、更新バス５７を通じて汎用レジスタ１２−ｋに対応するマスクビット５２−ｋを転送禁止状態に設定する。従って、汎用レジスタ１２−ｋが更新されても、その値は子スレッドへは転送されなくなる。
【００６０】
その後、汎用レジスタ１２−ｋの内容を元の値に戻すためにユニット１１でロード命令が実行されると、ユニット１１からそのロードアドレスがディレイ５９で例えば１命令サイクルだけ遅延されて比較回路５５に出力される。比較回路５５は、出力されたロードアドレスに一致するストアアドレスがストアアドレスレジスタ５１−ｋに記録されているか否かを判断し、記録されていれば、マスクビット５２−ｋを転送禁止状態から転送許可状態に変更する。これにより、汎用レジスタ１２−ｋが更新されると、その更新値が子スレッドへ再び転送されるようになる。
【００６１】
例えば図６（ａ）に示したプログラムの場合、フォーク命令「ｆｏｒｋ  ｔｈ１」によって子スレッドをフォークした時点で全てのマスクビット５２−ｋが転送許可状態に設定される。従って、次のレジスタｒ２０の更新を含む命令「ａｄｄ  ｒ２０，ｒ２０，１」の時点では、更新後のレジスタｒ２０の値がレジスタ番号と共に通信バス２１経由で子スレッド側のプロセッサに送信される。次の関数呼出し命令によって関数ｆｕｎｃが呼び出され、ストア命令「ｓｗ  ｒ２０，２０（ｓｐ）」が実行されると、レジスタｒ２０に対応するストアアドレスレジスタ５１−ｋにストアアドレスが記録される。そして、ｍｏｖｅ命令「ｒ２０，ｒ０」の実行時、レジスタｒ２０の内容切り替えが起こったことがユニット１１で検出され、レジスタｒ２０に対応するマスクビット５２−ｋが転送禁止状態に変更される。このため、レジスタｒ２０の更新後の値は子スレッドへは転送されない。次のロード命令「ｌｗ  ｒ２０，２０（ｓｐ）」の場合も同様である。そして、このロード命令の実行時にユニット１１から信号線５４に出されるロードアドレスがレジスタｒ２０に対応するストアアドレスレジスタ５１−ｋに記録されているストアアドレスと一致することが比較回路５５で検出され、レジスタｒ２０に対応するマスクビット５２−ｋが転送許可状態に戻される。従って、関数ｆｕｎｃの処理が終了し、次にレジスタｒ２０の更新を含む命令「ａｄｄ  ｒ２０，ｒ２０，１」をユニット１１が実行すると、更新後のレジスタｒ２０の値が子スレッド側のプロセッサへ転送されることになる。
【００６２】
【第５の実施の形態】
第１乃至第４の実施の形態では、更新後の汎用レジスタの値が更新前と異なる値であるかどうかに関係なく、更新後のレジスタ値を親スレッド側のプロセッサから子スレッド側のプロセッサへ送信した。しかし、汎用レジスタへの書き込み値が直前の値と同じ場合は送信しなくて良い。本実施の形態では、汎用レジスタへの書き込み時に書き込み前の値と比較することによって無駄なレジスタ送信量を削減し、子スレッド側での無駄なＲＡＷ違反検出による再実行を防止する。以下、第１の実施の形態との相違点を中心に本実施の形態を説明する。
【００６３】
図９を参照すると、本実施の形態における並列プロセッサシステムの各々のプロセッサ１−ｉは、図３に示した構成に加えて、汎用レジスタ１２−０〜１２−ｍのうちユニット１１がレジスタライト信号１７に出力したレジスタ番号２３の汎用レジスタ１２−ｋの書き込み前の内容をレジスタリードバス６１を通じて参照し、この書き込み前のレジスタ値とレジスタライトバス１５に出力された書き込み値２２との一致を検出する比較回路６２と、比較回路６２の出力を反転するインバータ６３と、インバータ６３の出力とレジスタライト信号１７に出力されたレジスタ番号２３とを入力し、比較回路６２で書き込み前後のレジスタ値の一致が検出された場合に限って、レジスタ番号２３を通信バス２１に出力するゲート回路６４とを備えている。
【００６４】
次に、本実施の形態の動作を説明する。なお、子スレッド側のプロセッサの動作は第１の実施の形態と同じなので、親スレッド側のプロセッサの動作だけを説明する。
【００６５】
ユニット１１は、子スレッドをフォークすると、そのフォーク後、レジスタライトバス１５を介して何れかの汎用レジスタ１２−ｋを更新する際に、そのレジスタ番号２３をレジスタライト信号１７として出力する。比較回路６２は、レジスタライト信号１７のレジスタ番号２３に従って同じレジスタ番号を持つ汎用レジスタ１２−ｋの書き込み前のレジスタ値を読み出し、ユニット１１がレジスタライトバス１５に出力した書き込み値２２と比較し、一致した場合にはその出力を“０”にし、インバータ６３を通じてゲート回路６４を開く。一致しない場合、比較回路６２の出力は“１”のままであり、ゲート回路６４は閉じている。従って、汎用レジスタ１２−ｋの書き込み値２２が更新前の値と同じである場合に限って、通信バス２１は、書き込み値２２とレジスタ番号２３をフォーク先プロセッサに向けて送信する。
【００６６】
以上は、第１の実施の形態に対して適用したが、第２乃至第４の実施の形態においても同様に、更新前後のレジスタ値が一致する場合に限ってフォーク先プロセッサへレジスタ値を転送するように構成することができる。
【００６７】
以上の各実施の形態では、フォーク後に親スレッドで更新されないが子スレッド側で必要となるレジスタの継承方法に関しては特に言及しなかった。本発明では、これらのレジスタの継承に関しては、文献１乃至３に記載されるようにフォーク点の親レジスタのレジスタファイルの全内容を子スレッドへ一括に転送する方法を使用しても良いし、子スレッドで必要なレジスタがコンパイラの静的解析によって判明しているのであればフォーク点の親レジスタのレジスタファイルの内、少なくとも子スレッドで必要なレジスタの値を転送するようにしても良い。更に、フォーク点における親スレッドのレジスタファイルの内容をレジスタ単位で順次に転送しながら、一度転送したレジスタが親スレッドで更新されたら再転送を行うような方法など任意の方法を採用することもできる。本発明は、フォーク後に親スレッドで更新されないが子スレッド側で必要となるレジスタの継承方法については任意の方法を採用することができるが、以下、幾つかの実施の形態を挙げておく。
【００６８】
【第６の実施の形態】
図１０を参照すると、本実施の形態における並列プロセッサシステムの各々のプロセッサ１−ｉは、図３に示した構成に加えて、子スレッドをフォークした旨の通知を信号線７１を通じてユニット１１から受けることにより参照バス７２を介して汎用レジスタ１２−０〜１２−ｍの内容を順次に読み出し、その書き込み値及びレジスタ番号を通信バス２１に出力し、全ての汎用レジスタ１２−０〜１２−ｍの転送を終えると信号線７１を通じてユニット１１にその旨通知するシーケンサ７３を備えている。ユニット１１は、シーケンサ７３から転送終了が通知されると、フォーク命令の次の命令の実行を開始する。なお、コンパイラの静的解析によって子スレッドに継承すべきレジスタが判明している場合、その情報を信号線７１を通じてシーケンサ７３に伝えることにより、子スレッドに継承すべきレジスタの内容だけを転送することもできる。
【００６９】
本実施の形態では、シーケンサ７３は、フォーク後に親スレッドで更新されたレジスタを子スレッドに継承する通信バス２１を使ってレジスタ内容を転送したが、別の大容量の通信バスを用いて全ての汎用レジスタ１２−０〜１２−ｍの内容を一括転送する構成にしても良い。また、本実施の形態は第１の実施の形態に適用したものであるが、第２乃至第５の実施の形態においても同様に適用できる。
【００７０】
【第７の実施の形態】
図１１を参照すると、本実施の形態における並列プロセッサシステムの各々のプロセッサ１−ｉは、図３に示した構成に加えて、各汎用レジスタ１２−ｋに１対１に対応する転送状態ビット８１−ｋと、レジスタトランスファシーケンサ８２とを備えている。
【００７１】
全ての転送状態ビット８１−ｋは、子スレッドをフォークした旨の通知がユニット１１から信号線８３に出力された時点で未転送状態（例えば“１”）に初期設定され、レジスタトランスファシーケンサ８２によってフォーク先プロセッサに転送が行われた時点で転送済状態（例えば“０”）に設定される。しかし、転送後、ユニット１１が汎用レジスタ１２−ｋを更新すると、レジスタライト信号１７上のレジスタ番号に基づき、更新された汎用レジスタ１２−ｋに対応する転送状態ビット８１−ｋが再び未転送状態に設定される。
【００７２】
レジスタトランスファシーケンサ８２は、子スレッドをフォークした旨の通知を信号線８３を通じてユニット１１から受けると、参照バス８４を介して汎用レジスタ１２−０〜１２−ｍの内容を順次に読み出し、その書き込み値２２及びレジスタ番号２３を通信バス２１に出力し、出力した汎用レジスタ１２−ｋに対応する転送状態ビット８１−ｋを転送済状態に変更する。汎用レジスタ１２−０から汎用レジスタ１２−ｍまで一通りの転送を終えると、レジスタトランスファシーケンサ８２は、転送状態ビット８１−０〜８１−ｍのうちに未転送状態になっているものが存在するか否かを常時監視し、未転送状態になっている転送状態ビット８１−ｋを検出する毎に、参照バス８４を介して該当する汎用レジスタ１２−ｋの内容を読み出し、その書き込み値２２及びレジスタ番号２３を通信バス２１に出力し、出力した汎用レジスタ１２−ｋに対応する転送状態ビット８１−ｋを転送済状態に変更する。本実施の形態では、ユニット１１はフォーク後、直ちにフォーク命令以後の命令の実行を開始する。
【００７３】
以上、本発明を幾つかの実施の形態を挙げて説明したが、本発明は以上の実施の形態にのみ限定されず、その他各種の付加変更が可能である。例えば、前記各実施の形態では、複数のプロセッサに共通にスレッド管理部３を設ける集中スレッド管理型の並列プロセッサシステムに本発明を適用したが、文献１等に記載されるように各プロセッサ毎にスレッド管理部を設ける分散スレッド管理型の並列プロセッサシステムにも本発明は適用可能である。また、隣接するプロセッサ間同士を単方向にリング状に接続する通信バスを使ってレジスタ転送を行ったが、全てのプロセッサが共通の通信バスに接続された並列プロセッサシステムでは当該共通の通信バスを使ってレジスタ転送が行われる。
【００７４】
【発明の効果】
以上説明したように本発明によれば、フォーク後、親スレッドの汎用レジスタ書き込み毎に更新後のレジスタ値を親スレッド側のプロセッサから子スレッド側のプロセッサへ送信し、子スレッド側のプロセッサでは子スレッドを投機的に実行し、ＲＡＷ違反を検出すると再実行を行うことにより、ＲＡＷ違反をコンパイル時点でなくプログラム実行時に動的に解消でき、且つＲＡＷ違反解消のための不必要な待ち合わせを解消することができる。
【００７５】
また、第２乃至第４の発明によれば、汎用レジスタの内容切り替えに伴う無用なレジスタ転送を回避でき、第５の発明によれば、レジスタが前回と同じ値に更新された場合の無用なレジスタ転送を回避でき、共にレジスタ転送量を削減できると共に無駄なＲＡＷ違反検出による子スレッド側の再実行を防止することができる。
【図面の簡単な説明】
【図１】本発明の作用の説明図である。
【図２】本発明を適用した並列プロセッサシステムの一例を示すブロック図である。
【図３】本発明の第１の実施の形態におけるプロセッサの要部ブロック図である。
【図４】ステータスレジスタの状態遷移図である。
【図５】本発明の第２の実施の形態におけるプロセッサの要部ブロック図である。
【図６】ｐｒｏｐ命令を挿入する前と後の並列化プログラムの例を示す図である。
【図７】本発明の第３の実施の形態におけるプロセッサの要部ブロック図である。
【図８】本発明の第４の実施の形態におけるプロセッサの要部ブロック図である。
【図９】本発明の第５の実施の形態におけるプロセッサの要部ブロック図である。
【図１０】本発明の第６の実施の形態におけるプロセッサの要部ブロック図である。
【図１１】本発明の第７の実施の形態におけるプロセッサの要部ブロック図である。
【図１２】従来のマルチスレッド実行方法の処理の概要を示す図である。
【図１３】レジスタ継承に関する２通りの方式（フォーク時レジスタ転送方式、フォーク後レジスタ転送方式）の説明に用いるプログラム例を示す図である。
【図１４】従来の問題点の説明図である。
【符号の説明】
１−０〜１−３…プロセッサ
２−０〜２−３…信号線
３…スレッド管理部
４−０〜４−３…信号線
５…メモリ
６−０〜６−３…通信バス
【図１】
0003702815.tif 000002
【図２】
0003702815.tif 000003
【図３】
0003702815.tif 000004
【図４】
0003702815.tif 000005
【図５】
0003702815.tif 000006
【図６】
0003702815.tif 000007
【図７】
0003702815.tif 000008
【図８】
0003702815.tif 000009
【図９】
0003702815.tif 000010
【図１０】
0003702815.tif 000011
【図１１】
0003702815.tif 000012
【図１２】
0003702815.tif 000013
【図１３】
0003702815.tif 000014
【図１４】
0003702815.tif 000015