(57)【特許請求の範囲】
【請求項１】
メモリ操作命令を非プログラム順序で、命令間の依存関係に関して投機的に実行するデータ依存投機実行制御装置において、
前記メモリ操作命令の処理アドレスを受けて、その処理アドレスを一意な番号に変換するアドレス変換手段と、
前記変換された番号に対応して、前記メモリ操作命令の投機的実行の成否履歴を記憶する成否履歴記憶手段と、
前記成否履歴を参照して、前記投機的実行の成否を予測する予測手段と、
前記予測の結果に従って前記メモリ操作命令を実行する実行手段とを備え、
前記アドレス変換手段は、複数の前記処理アドレスを受けて前記番号に変換する場合であっても、同一の前記番号に変換することができ、
前記成否履歴記憶手段は、前記変換された同一の番号に対応して、投機的実行の成否履歴を重複して記憶することができることを特徴とするデータ依存投機実行制御装置。
【請求項２】
前記実行手段は、前記予測手段が前記投機的実行の成功を予測した場合、前記メモリ操作命令を非プログラム順序で投機的に実行し、前記予測手段が前記投機的実行の失敗を予測した場合には、前記メモリ操作命令をプログラム順序で確定的に実行することを特徴とする請求項１記載のデータ依存投機実行制御装置。
【請求項３】
前記予測手段は、前記成否履歴記憶手段の内容を参照して、過去において投機的実行が失敗するよりも成功した確率が高ければ、その投機的実行の成功を予測し、過去において投機的実行が成功するよりも失敗した確率が高ければ、その投機的実行の失敗を予測することを特徴とする請求項２記載のデータ依存投機実行制御装置。
【請求項４】
前記アドレス変換手段は、入力されるアドレスの所定ビットをそのまま出力することで、任意のアドレスを前記所定ビットで規定される番号に変換することを特徴とする請求項２記載のデータ依存投機実行制御装置。
【請求項５】
前記アドレス変換手段は、入力されるアドレスの所定の複数ビットの排他的論理和演算を行い、その演算結果を出力することで、任意のアドレスを前記出力で規定される番号に変換することを特徴とする請求項２記載のデータ依存投機実行制御装置。
【請求項６】
複数のプロセッサから構成され、スレッド単位で並列処理を行うマルチプロセッサシステムにおいて、
前記スレッドを構成するメモリ操作命令の処理アドレスを一意な番号に変換するアドレス変換手段と、
前記変換された番号に対応して、前記メモリ操作命令の投機的実行の成否履歴を記憶する成否履歴記憶手段と、
前記成否履歴を参照して、前記投機的実行の成否を予測する予測手段と、
前記予測の結果に従って、前記メモリ操作命令を前記スレッド間の依存関係に関して投機的に実行する実行手段とを備え、
前記アドレス変換手段は、複数の前記処理アドレスを受けて前記番号に変換する場合であっても、同一の前記番号に変換することができ、
前記成否履歴記憶手段は、前記変換された同一の番号に対応して、投機的実行の成否履歴を重複して記憶することができることを特徴とするマルチプロセッサシステム。
【請求項７】
前記実行手段は、前記予測手段が前記投機的実行の成功を予測した場合、前記メモリ操作命令を非プログラム順序で投機的に実行し、前記予測手段が前記投機的実行の失敗を予測した場合には、前記メモリ操作命令をプログラム順序で確定的に実行することを特徴とする請求項６記載のマルチプロセッサシステム。
【請求項８】
前記予測手段は、前記成否履歴記憶手段の内容を参照して、過去において投機的実行が失敗するよりも成功した確率が高ければ、その投機的実行の成功を予測し、過去において投機的実行が成功するよりも失敗した確率が高ければ、その投機的実行の失敗を予測することを特徴とする請求項７記載のマルチプロセッサシステム。
【請求項９】
前記アドレス変換手段は、入力されるアドレスの所定ビットをそのまま出力することで、任意のアドレスを前記所定ビットで規定される番号に変換することを特徴とする請求項７記載のマルチプロセッサシステム。
【請求項１０】
前記アドレス変換手段は、入力されるアドレスの所定の複数ビットの排他的論理和演算を行い、その演算結果を出力することで、任意のアドレスを前記出力で規定される番号に変換することを特徴とする請求項７記載のマルチプロセッサシステム。
【請求項１１】
メモリ操作命令を非プログラム順序で、命令間の依存関係に関して投機的に実行するデータ依存投機実行制御方法において、
前記メモリ操作命令の処理アドレスを受けて、その処理アドレスを一意な番号に変換するステップと、
前記変換された番号に対応して、前記メモリ操作命令の投機的実行の成否履歴を記憶するステップと、
前記成否履歴を参照して、前記投機的実行の成否を予測するステップと、
前記予測の結果に従って前記メモリ操作命令を実行するステップとを備え、
前記変換ステップは、複数の前記処理アドレスを受けて前記番号に変換する場合であっても、同一の前記番号に変換することができ、
前記記憶ステップは、前記変換された同一の番号に対応して、投機的実行の成否履歴を重複して記憶することができることを特徴とするデータ依存投機実行制御方法。
【請求項１２】
前記実行ステップでは、前記予測ステップにおいて前記投機的実行の成功を予測した場合、前記メモリ操作命令を非プログラム順序で投機的に実行し、前記投機的実行の失敗を予測した場合には、前記メモリ操作命令をプログラム順序で確定的に実行することを特徴とする請求項１１記載のデータ依存投機実行制御方法。
【請求項１３】
前記予測ステップでは、前記記憶ステップで記憶した成否履歴を参照して、過去において投機的実行が失敗するよりも成功した確率が高ければ、その投機的実行の成功を予測し、過去において投機的実行が成功するよりも失敗した確率が高ければ、その投機的実行の失敗を予測することを特徴とする請求項１２記載のデータ依存投機実行制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、例えば、マイクロプロセッサなどのデータ処理装置におけるマイクロプロセッサの性能向上に関わるマルチプロセッサシステム、データ依存投機実行制御装置およびその方法に関するものである。
【０００２】
【従来の技術】
従来より、マイクロプロセッサの性能向上技術として、マイクロプロセッサが実行するプログラム中の命令の順序とは異なる順序で命令の実行する、非プログラム順序実行（アウトオブオーダ実行）技術が広く使われている。非プログラム順序実行では、プロセッサが、実行可能になった命令から実行するため、プログラム中の命令の順序で実行するプログラム順序実行（インオーダ実行）を行う場合に比べて、プロセッサの性能を向上させることが可能となる。
【０００３】
しかし、非プログラム順序実行は、無条件に行えるわけではない。非プログラム順序実行が可能な条件として、まず、実行する命令間のレジスタに関する正依存関係がないことがあげられる。例えば、プログラム順序で前にある命令が変更を行うレジスタを、プログラム順序でそれより後にある命令が参照する場合、前にある命令から後にある命令へレジスタに関する正依存関係があるという。
【０００４】
この場合、それら２つの命令をプログラム順序とは逆の順序で実行すると、プログラムの意味が変わってしまい、正しいプログラムの実行結果を得ることができない。すなわち、レジスタに関して正依存関係がある場合、非プログラム順序で実行することができない。
【０００５】
同様にして、プログラム順序で前にある命令が参照するレジスタを、プログラム順序でそれより後にある命令が変更を行う場合、前にある命令から後にある命令へレジスタに関する逆依存関係があるという。
【０００６】
また、プログラム順序で前にある命令が変更を行うレジスタを、プログラム順序でそれより後にある命令も変更を行う場合、前にある命令から後にある命令へレジスタに関する出力依存関係があるという。いずれの場合も、それら２つの命令をプログラム順序とは逆の順序で実行すると、プログラムの意味が変わってしまい、正しいプログラムの実行結果を得ることができない。
【０００７】
通常、各命令が変更あるいは参照の対象とするレジスタは、命令のデコード時に判明するため、依存関係のある命令に対しては、非プログラム順序で実行を行わないことで対応することが多い。また、逆依存関係、出力依存関係に対してはレジスタ・リネーミングなどの技術で、その依存を解消して、非プログラム順序実行を可能にすることも広く実施されている。
【０００８】
メモリに対して操作を行うメモリ操作命令に対しては、非プログラム順序実行に際して、レジスタに関する依存関係に加えて、メモリに関する依存関係に関しての考慮が必要となる。
【０００９】
通常、メモリ操作命令には、メモリからデータを読み出すロード命令と、メモリへデータを書き込むストア命令が含まれる。プログラム中に出現する、ある２つのロード命令またはストア命令が対象とするアドレスが互いに異なれば、メモリの異なる位置が読み出し、または書き込みの対象となる。そのため、これら２つのロード命令またはストア命令の間には、メモリに関して依存関係は存在しない。すなわち、それら２つの命令は、非プログラム順序で実行することが可能である。
【００１０】
一方、プログラム中に出現する、ある２つのロード命令またはストア命令が対象とするアドレスが同じ場合、メモリの同じ位置が読み出し、または書き込みの対象となる。そのため、それら２つのロード命令またはストア命令間には、メモリに関して依存関係が存在する。
【００１１】
例えば、プログラム順序で前にあるストア命令が書き込みを行うアドレスに対して、プログラム順序でそれより後にあるロード命令が読み出しを行う場合、前にあるストア命令から後にあるロード命令へ、メモリに関する正依存関係があるという。
【００１２】
この場合、それら２つのロード命令、ストア命令を、プログラム順序とは逆の順序で実行すると、プログラムの意味が変わってしまい、正しいプログラムの実行結果を得ることができない。すなわち、メモリに関して正依存関係がある場合、非プログラム順序で実行することができない。
【００１３】
同様にして、プログラム順序で前にあるロード命令が読み出しを行うアドレスに対して、プログラム順序でそれより後にあるストア命令が書き込みを行う場合、前にあるロード命令から後にあるストア命令へメモリに関する逆依存関係があるという。
【００１４】
また、プログラム順序で前にあるストア命令が書き込みを行うアドレスに対して、プログラム順序でそれより後にあるストア命令も書き込みを行う場合、前にあるストア命令から後にあるストア命令へメモリに関する出力依存関係があるという。いずれの場合も、それら２つのロード・ストア命令をプログラム順序とは逆の順序で実行すると、プログラムの意味が変わってしまい、正しいプログラムの実行結果を得ることができない。
【００１５】
メモリに関する逆依存関係、および出力依存関係に対しては、ストア命令が書き込みを行うデータを一時的なバッファ（通常、ストアバッファと呼ばれる）に一時的に格納するなどの対応で、逆依存関係あるいは出力依存関係を解消し、非プログラム順序実行を可能とする技術が、従来より知られている。
【００１６】
一方、正依存関係が存在する場合は、本質的に非プログラム順序で実行することができず、プログラム順序で実行することになる。しかしながら、ロード・ストア命令が対象とするアドレスは、実行時まで不明である場合が多い。すなわち、デコード時に依存関係が判明するレジスタの場合と違い、メモリの場合には、実行時まで依存関係が判明しない場合が多い。そのため、非プログラム順序で実行できないことによる性能への影響が大きい。
【００１７】
その具体例を、図１１を参照して説明する。図１１の（ａ）は、ロード・ストア命令からなるプログラム例のプログラム順序であり、そのプログラム順に、アドレスＡ１に対するロード命令ＬＤ１、アドレスＡ４’に対するストア命令ＳＴ１、アドレスＡ２に対するロード命令ＬＤ２、アドレスＡ３に対するロード命令ＬＤ３、アドレスＡ４に対するロード命令ＬＤ４を示している。
【００１８】
ここで、ＳＴ１の対象アドレスＡ４’とＬＤ４の対象アドレスＡ４が等しい  （Ａ４’＝Ａ４）とすると、ＳＴ１とＬＤ４は同じアドレスを対象としていて、かつ、ＬＤ４よりもＳＴ１の方がプログラム順序で前にあるため、ＳＴ１からＬＤ４へ正依存関係が存在する。
【００１９】
つまり、プログラムの意味上、ＳＴ１がアドレスＡ４’（＝Ａ４）に書き込みを行ったデータを、ＬＤ４がアドレスＡ４（＝Ａ４’）から読み出すことが期待されている。そのため、それらの実行も先にＳＴ１、その後にＬＤ４のプログラム順序で行われる必要がある。
【００２０】
図１１の（ｂ）は、図１１の（ａ）に示したプログラム順序の命令列についてのプログラム順序実行の例である。同図において、左からサイクル番号、そのサイクルの実行命令、実行命令の対象アドレスを示す。ここで、ＳＴ１の対象アドレスＡ４’は、５サイクル目まで判明しないと想定すると、１サイクル目にアドレスＡ１に対するロード命令ＬＤ１、５サイクル目にアドレスＡ４’対するストア命令ＳＴ１、６サイクル目にアドレスＡ２に対するロード命令ＬＤ２、７サイクル目にアドレスＡ３に対するロード命令ＬＤ３、８サイクル目にアドレスＡ４に対するロード命令ＬＤ４が実行されることになる。
【００２１】
仮に２サイクル目、または３サイクル目、または４サイクル目にアドレスＡ２、またはアドレスＡ３、またはアドレスＡ４が判明していたとしても、ＬＤ２、またはＬＤ３、またはＬＤ４を、２サイクル目、または３サイクル目、または４サイクル目にＳＴ１を追い越して実行する非プログラム順序実行することはできない。
【００２２】
なぜなら、上述のように、ＳＴ１の対象アドレスＡ４’は、５サイクル目まで判明しないため、５サイクル目まで、ＳＴ１からＬＤ１，ＬＤ２，ＬＤ３，ＬＤ４への正依存関係の有無も判明しないからである。
【００２３】
すなわち、図１１の（ｂ）に示したプログラム順序実行の例の場合、２サイクル目、３サイクル目、４サイクル目には、ロード・ストア命令を実行することができず、ＬＤ１，ＬＤ２，ＬＤ３，ＬＤ４，ＳＴ１の５命令の実行に８サイクルを要してしまう。
【００２４】
このように、ロード・ストア命令に関して非プログラム順序実行を行わない方法では、その実行性能が低下するという問題がある。そこで、この問題に対して、従来より知られているものに、正依存関係の有無が判明するよりも前に、正依存関係が存在しないと仮定して、投機的に非プログラム順序実行を行う方式がある。以下、この方式によるデータの正依存関係に対する投機的な命令実行を「データ依存投機実行」と表記する。
【００２５】
データ依存投機実行においては、実際に正依存関係が存在せず、投機実行が成功する場合と、実際に正依存関係が存在して、投機実行が失敗する場合とがあり、正依存関係の有無が判明した時点で、そのいずれであるかを判定する必要がある。実際に正依存関係が存在せず、投機実行が成功した場合、そのまま、後続の命令実行を継続することが可能であり、データ依存投機実行による非プログラム順序実行を行った分だけ、実行性能の向上が期待できる。
【００２６】
一方、実際に正依存関係が存在して、投機実行が失敗した場合、プログラムの意味が変わってしまうため、プログラムの正しい実行結果が保証できなくなる。そのため、データ依存投機実行による非プログラム順序実行を行った命令の結果を取り消して、プログラム順序で再実行するなどのデータ依存投機実行の失敗に対する回復処理が必要となる。
【００２７】
投機実行が失敗した場合、失敗した命令の取り消しや回復処理のために、プログラム順序実行するよりも性能が低下することが多い。しかし、投機実行に失敗する場合よりも、成功する場合の確率が十分に高ければ、プログラム全体としての実行性能の向上が期待できることになる。
【００２８】
なお、非プログラム順序実行については、マイク・ジョンソンによる文献、「スーパースカラ・プロセッサ」（日経ＢＰ出版センター、１９９４年）に詳細に記載されている。また、データ依存投機実行や投機実行の失敗による回復処理方法については、例えば、特開平５−２２４９２７号公報や特開平８−３１４７２１号公報に開示されている。
【００２９】
そこで、データ依存投機実行の具体例を説明する。図１１の（ｃ）は、図１１の（ａ）に示したプログラム順序の命令列に対して、データ依存投機実行を行い、かつ、投機実行に成功した場合の実行例である。図１１の（ｂ）に示したプログラム順序実行の場合と同様、ＳＴ１の対象アドレスＡ４’は、５サイクル目まで判明しないものとする。また、ＬＤ２の対象アドレスＡ２は、２サイクル目で、ＬＤ３の対象アドレスＡ３は、３サイクル目で、そして、ＬＤ４の対象アドレスＡ４は、６サイクル目で判明すると想定する。
【００３０】
まず、１サイクル目に、アドレスＡ１に対するロード命令ＬＤ１を実行する。次に、２サイクル目において、プログラム順序（図１１の（ａ）参照）では、ＳＴ１を実行するのであるが、対象アドレスＡ４’は、まだ不明であるために実行できない。このため、対象アドレスＡ２が判明しているＬＤ２を、ＳＴ１を追い越して非プログラム順序で実行する。
【００３１】
ここで、ＳＴ１の対象アドレスＡ４’は、まだ不明であるため、ＳＴ１からＬＤ２への正依存関係の有無もまた、不明である。すなわち、ＬＤ２は、ＳＴ１に対してデータ依存投機実行する。
【００３２】
同様にして、３サイクル目においても、ＳＴ１は、まだ実行できないため、対象アドレスＡ３が判明しているＬＤ３のデータ依存投機実行する。このとき、ＳＴ１からＬＤ３への正依存関係の有無もまた、不明である。
【００３３】
次に、４サイクル目では、ＳＴ１およびＬＤ４ともに、その対象アドレスは不明であるから、いずれの命令も実行できない。そして、５サイクル目において、ＳＴ１の対象アドレスＡ４’が判明するので、ＳＴ１を実行する。同時に、ＳＴ１から、データ依存投機実行を行ったＬＤ２，ＬＤ３に対する正依存関係の有無を判定する。
【００３４】
この場合、ＬＤ２の対象アドレスＡ２、およびＬＤ３の対象アドレスＡ３は、ＳＴ１の対象アドレスＡ４’と異なるため、ＬＤ２およびＬＤ３に対して正依存関係は存在しない。すなわち、ＬＤ２およびＬＤ３のデータ依存投機実行は、成功したと判断する。従って、後続の命令実行をそのまま継続することができ、次の６サイクル目に、ＬＤ４を実行する。このＬＤ４は、ＳＴ１から正依存関係があるが、プログラム順序で実行されているので問題は生じない。以上が、データ依存投機実行が成功した場合である。
【００３５】
このように、図１１の（ｂ）に示したプログラム順序で実行した場合、その実行に８サイクルを要したのに対して、データ依存投機実行による非プログラム順序実行が成功した場合、実行は、６サイクルで完了する。そのため、その分だけ、実行性能が向上している。
【００３６】
一方、図１１の（ｄ）は、図１１の（ａ）に示したプログラム順序の命令列に対して、データ依存投機実行を行い、かつ、投機実行に失敗した場合の実行例を示している。ここでも、図１１の（ｂ）で示したプログラム順序実行の場合と同様、ＳＴ１の対象アドレスＡ４’は、５サイクル目まで判明しないものとする。また、ＬＤ２の対象アドレスＡ２は、２サイクル目で、ＬＤ３の対象アドレスＡ３は、３サイクル目で、ＬＤ４の対象アドレスＡ４は、４サイクル目で判明すると想定する。
【００３７】
そこで、まず、１サイクル目に、アドレスＡ１に対するロード命令ＬＤ１を実行する。次に、図１１の（ｃ）で示したデータ依存投機実行が成功した場合と同様に、２サイクル目、および３サイクル目において、プログラム順序で次の命令であるＳＴ１は、対象アドレスＡ４’が、まだ不明であるために実行できない。そのため、対象アドレスが判明しているＬＤ２およびＬＤ３を、データ依存投機実行による非プログラム順序実行する。
【００３８】
次に、４サイクル目では、いまだＳＴ１の対象アドレスＡ４’は不明であるが、ＬＤ４の対象アドレスＡ４は判明しているため、ＬＤ４のデータ依存投機実行をする。５サイクル目において、ＳＴ１の対象アドレスＡ４’が判明するので、ＳＴ１を実行する。同時に、ＳＴ１から、データ依存投機実行を行ったＬＤ２，ＬＤ３，ＬＤ４に対する正依存関係の有無を判定する。
【００３９】
この場合、ＬＤ２の対象アドレスＡ２、およびＬＤ３の対象アドレスＡ３は、ＳＴ１の対象アドレスＡ４’と異なるため、ＬＤ２およびＬＤ３に対しては、正依存関係は存在しない。しかし、ＬＤ４の対象アドレスＡ４は、ＳＴ１の対象アドレスＡ４’に等しいため、ＳＴ１からＬＤ４に対して正依存関係が存在する。
【００４０】
すなわち、正依存関係が存在するにもかかわらず、非プログラム順序で実行してしまっているので、ＬＤ４のデータ依存投機実行は、失敗したと判断する。この場合、このまま後続の命令の実行を継続すると、プログラムの正しい実行結果が保証されないので、データ依存投機実行の、失敗の回復処理の実行が必要である。
【００４１】
例えば、図１１の（ｄ）に示す実行例では、５サイクル目においてデータ依存投機実行は失敗したと判断されると、まず、データ依存投機実行を行った２サイクル目から４サイクル目のＬＤ２，ＬＤ３，ＬＤ４、および、５サイクル目のＳＴ１の実行結果を取り消す。次に、実行結果を取り消したＳＴ１，ＬＤ２，ＬＤ３，ＬＤ４の再実行を、７サイクル目からプログラム順序で実行することで、データ依存投機実行の失敗の回復を行い、その後、後続命令の実行を再開する。
【００４２】
この場合、ＬＤ１，ＬＤ２，ＬＤ３，ＬＤ４，ＳＴ１の５命令の実行に、１０サイクルを要することになり、プログラム順序で実行を行った場合の８サイクルより、性能が低下することになる。しかし、データ依存投機実行に成功した場合は、６サイクルで実行できる。そのため、投機実行に失敗する場合よりも成功する場合の確率が十分に高ければ、プログラム全体としての実行性能の向上が期待できる。
【００４３】
このように、プロセッサがデータ依存投機実行をするには、ロード・ストア命令間のメモリに対する正依存関係の有無を判定する機能が必要となる。この機能を担う装置として、例えば、特開平８−３１４７２１号公報に開示されているアドレス比較器などのデータ依存関係検出装置がある。以下、データ依存関係検出装置を備えたプロセッサにおけるデータ依存投機実行について説明する。
【００４４】
図１２は、ロード・ストア命令間の正依存関係を検出するデータ依存関係検出装置を備えるプロセッサの構成を示すブロック図である。同図に示すプロセッサは、プロセッサ制御部１２０、命令実行部１２１、データ依存関係検出装置１３０を備える。これらの内、データ依存関係検出装置１３０は、ロード命令の対象アドレスを格納する複数のアドレスバッファ１３１、各々のアドレスバッファ１３１に接続された複数のアドレス比較器１３２、すべてのアドレス比較器１３２の出力を入力とする論理和回路１３３から構成される。
【００４５】
アドレス比較器１３２は、アドレスバッファ１３１に格納されたロード命令の対象アドレスと、実行中のストア命令の対象アドレスとの比較を行う。論理和回路１３３は、すべてのアドレス比較器１３２の、出力の論理和を演算し、それをデータ依存検出結果１６０として出力する。
【００４６】
本プロセッサが命令を実行する場合、プロセッサ制御部１２０は、実行する命令の種別を、実行命令１１５を通じて命令実行部１２１、およびデータ依存関係検出装置１３０に出力する。さらに、実行する命令がメモリ操作命令の場合、プロセッサ制御部１２０は、その操作の対象となるアドレスを、対象アドレス１１４を通じて命令実行部１２１、およびデータ依存関係検出装置１３０に出力する。さらに、メモリ操作命令をデータ依存投機実行する場合、プロセッサ制御部１２０は、その旨を、投機実行フラグ１１３を通じてデータ依存関係検出装置１３０に通知する。
【００４７】
データ依存関係検出装置１３０によるストア命令からロード命令へのメモリに関する正依存関係の検出は、以下に示す動作で実現される。まず、プロセッサがデータ依存関係に対して、投機的な命令実行を行わず、プログラム順序で確定的に命令実行する状態にある場合（以下、「確定実行状態」と表記する）、データ依存関係検出装置１３０は、何ら動作を行わない。
【００４８】
それに対して、プロセッサが、データ依存関係に対して投機的な命令実行を行う状態（以下では、「投機実行状態」と表記する）にある場合、データ依存関係検出装置１３０は、ストア命令からロード命令への正依存関係の検出処理を行う。プロセッサが、確定実行状態、または投機実行状態のどちらにあるかは、プロセッサ制御部１２０からデータ依存関係検出装置１３０に入力される投機実行フラグ１１３で判断する。ロード命令がデータ依存投機実行された場合、その対象アドレスを、これまでロード命令の対象アドレスが格納されていない、空いているアドレスバッファ１３１に格納していく。
【００４９】
次に、ストア命令が実行されると、その対象アドレスは、すべてのアドレス比較器１３２に入力され、その比較器で、アドレスバッファ１３１に格納されている、それ以前にデータ依存投機実行されたロード命令の対象アドレスと比較する。アドレス比較器１３２から出力された比較結果は、すべて論理和をとり、データ依存検出結果１１６として、プロセッサ制御部１２０へ出力される。
【００５０】
ストア命令の対象アドレスと、アドレスバッファ１３１に格納されているロード命令の対象アドレスのいずれとも一致しない場合、そのストア命令からアドレスバッファ１３１に対象アドレスを格納したロード命令へ、正依存関係が存在しないと判断することができる。そこで、その旨がデータ依存検出結果１１６としてプロセッサ制御部１２０へ出力される。この場合、データ依存投機実行が成功したとして、そのまま、後続の命令の実行を継続することができる。
【００５１】
一方、ストア命令の対象アドレスと、アドレスバッファ１３１に格納されているロード命令の対象アドレスのいずれかが一致した場合、そのストア命令からアドレスバッファ１３１に対象アドレスを格納したロード命令へ、正依存関係が存在すると判断することができるので、その旨がデータ依存検出結果１１６としてプロセッサ制御部１２０へ出力される。この場合、データ依存投機実行が失敗したとして、プロセッサ制御部１２０はデータ依存投機実行が失敗したことによる回復処理などを実行する。
【００５２】
また、ハードウエアによる投機実行の成功確率を向上させる技術として、従来より知られているものに、分岐投機実行に対する分岐予測技術がある。例えば、特開平１０−１７１６５３号公報に記載のものは、実行するプログラム毎に前回までの分岐の履歴情報からなる学習情報と、今回の分岐結果からなる正解情報とから重み情報を更新し、それを用いて、次回の分岐予測を行う方式および装置に関するものである。
【００５３】
また、特表平１１−５０４４５８号公報には、スーパースカラマイクロプロセッサにおける条件付き分岐命令の方向指示を、行使された実際の分岐動作の履歴を記録した履歴レジスタを用いて予測する装置などが開示されている。
【００５４】
【発明が解決しようとする課題】
しかしながら、上記従来のデータ依存投機実行方式は、データ依存投機実行が失敗する確率が高い場合、データ依存投機実行失敗の回復処理のために、プログラムの実行性能が低下するという問題がある。
【００５５】
また、投機実行の成否が、その投機実行の直後に判明する分岐投機実行と異なり、データ依存投機実行では、投機実行の成否が投機実行のはるか後に判明するため、特開平１０−１７１６５３号や特表平１１−５０４４５８号公報に開示された、上記従来の分岐予測装置を、データ依存投機実行の成否予測に適用することは困難である、という問題がある。
【００５６】
本発明は、上述の課題に鑑みなてされたものであり、その目的とするところは、データ依存投機実行において、データ依存投機実行が失敗する確率を低減し、同時に、プログラムの実行性能を向上できるマルチプロセッサシステム、データ依存投機実行制御装置およびその方法を提供することである。
【００５７】
【課題を解決するための手段】
上記の目的を達成するため、本発明は、データ依存投機実行の制御手段（以下、データ依存投機制御装置と表記する）を提供する。具体的には、本発明は、メモリ操作命令を非プログラム順序で、命令間の依存関係に関して投機的に実行するデータ依存投機実行制御装置において、上記メモリ操作命令の処理アドレスを受けて、その処理アドレスを一意な番号に変換するアドレス変換手段と、上記変換された番号に対応して、上記メモリ操作命令の投機的実行の成否履歴を記憶する成否履歴記憶手段と、上記成否履歴を参照して、上記投機的実行の成否を予測する予測手段と、上記予測の結果に従って上記メモリ操作命令を実行する実行手段とを備え、前記アドレス変換手段は、複数の前記処理アドレスを受けて前記番号に変換する場合であっても、同一の前記番号に変換することができ、前記成否履歴記憶手段は、前記変換された同一の番号に対応して、投機的実行の成否履歴を重複して記憶することができるデータ依存投機実行制御装置を提供する。
【００５８】
また、他の発明によれば、複数のプロセッサから構成され、スレッド単位で並列処理を行うマルチプロセッサシステムにおいて、上記スレッドを構成するメモリ操作命令の処理アドレスを一意な番号に変換するアドレス変換手段と、上記変換された番号に対応して、上記メモリ操作命令の投機的実行の成否履歴を記憶する成否履歴記憶手段と、上記成否履歴を参照して、上記投機的実行の成否を予測する予測手段と、上記予測の結果に従って、上記メモリ操作命令を上記スレッド間の依存関係に関して投機的に実行する実行手段とを備え、前記アドレス変換手段は、複数の前記処理アドレスを受けて前記番号に変換する場合であっても、同一の前記番号に変換することができ、前記成否履歴記憶手段は、前記変換された同一の番号に対応して、投機的実行の成否履歴を重複して記憶することができるマルチプロセッサシステムが提供される。
【００５９】
好ましくは、上記実行手段は、上記予測手段が上記投機的実行の成功を予測した場合、上記メモリ操作命令を非プログラム順序で投機的に実行し、上記予測手段が上記投機的実行の失敗を予測した場合には、上記メモリ操作命令をプログラム順序で確定的に実行する。
【００６０】
また、好適には、上記予測手段は、上記成否履歴記憶手段の内容を参照して、過去において投機的実行が失敗するよりも成功した確率が高ければ、その投機的実行の成功を予測し、過去において投機的実行が成功するよりも失敗した確率が高ければ、その投機的実行の失敗を予測する。
【００６１】
さらに、他の発明によれば、メモリ操作命令を非プログラム順序で、命令間の依存関係に関して投機的に実行するデータ依存投機実行制御方法において、上記メモリ操作命令の処理アドレスを受けて、その処理アドレスを一意な番号に変換するステップと、上記変換された番号に対応して、上記メモリ操作命令の投機的実行の成否履歴を記憶するステップと、上記成否履歴を参照して、上記投機的実行の成否を予測するステップと、上記予測の結果に従って上記メモリ操作命令を実行するステップとを備え、前記変換ステップは、複数の前記処理アドレスを受けて前記番号に変換する場合であっても、同一の前記番号に変換することができ、前記記憶ステップは、前記変換された同一の番号に対応して、投機的実行の成否履歴を重複して記憶することができるデータ依存投機実行制御方法が提供される。
【００６２】
【発明の実施の形態】
以下、添付図面を参照しながら、本発明の実施の形態を詳細に説明する。
［実施の形態１］
最初に、本発明の実施の形態１について、図面を参照して詳細に説明する。図１は、本発明の実施の形態１に係るデータ依存投機制御装置を含むプロセッサの構成を示すブロック図である。同図に示すプロセッサは、データ依存投機制御装置１０、プロセッサ制御部２０、命令実行部２１、データ依存関係検出装置３０により構成される。なお、本プロセッサの他の構成要素については、図示を省略してある。
【００６３】
本プロセッサが命令を実行する場合、プロセッサ制御部２０は、実行する命令の種別を、実行命令１５を通じて、命令実行部２１、データ依存投機制御装置１０、およびデータ依存関係検出装置３０に出力する。さらに、実行する命令がメモリ操作命令の場合、プロセッサ制御部２０は、その操作の対象となるアドレスを、対象アドレス１４を通じて、命令実行部２１、データ依存投機制御装置１０、およびデータ依存関係検出装置３０に出力する。
【００６４】
さらに、メモリ操作命令をデータ依存投機実行する場合、プロセッサ制御部２０は、その旨を、投機実行フラグ１３を通じて、データ依存投機制御装置１０、およびデータ依存関係検出装置３０に通知する。
【００６５】
データ依存投機制御装置１０は、ハッシュ関数回路１１、および投機実行成否履歴テーブル１２より構成される。また、データ依存投機制御装置１０は、プロセッサ制御部２０から、投機実行フラグ１３、対象アドレス１４、実行命令１５を入力する。さらに、データ依存投機制御装置１０は、プロセッサ制御部２０へ、データ投機実行成否予測結果１７を出力する。
【００６６】
ハッシュ関数回路１１は、ｍビットで表現されるメモリ操作命令の対象アドレスを、ｎビットで表現される投機実行成否履歴テーブル１２のエントリ番号に変換するハッシュ関数ｆを実現する論理回路である。通常、ｍよりもｎの方が小さい（ｍ＞ｎ）。ここで、ハッシュ関数ｆは、同一の入力に対しては、同一の値を持つことを特徴とする。
【００６７】
すなわち、Ｎ１＝ｆ（Ａ１）、かつＮ２＝ｆ（Ａ２）としたとき、Ａ１＝Ａ２であれば、Ｎ１＝Ｎ２が成立する関数である。従って、ハッシュ関数回路１１は、同一のロード・ストア命令の対象アドレスに対して、必ず同一の命令履歴テーブルのエントリ番号を出力することを保証する。
【００６８】
一方、Ａ１≠Ａ２であっても、一般には、Ｎ１≠Ｎ２は保証されない。すなわち、異なるロード・ストア命令の対象アドレスに対して、同一の命令履歴テーブルのエントリ番号が出力される場合が存在する。
【００６９】
投機実行成否履歴テーブル１２は、各々のエントリが、メモリやフリップフロップなどの記憶手段で実現された複数のエントリから構成される。各エントリには、過去に投機実行を行ったメモリ操作命令のアドレスに対する投機実行の成否結果の履歴を記憶する。投機実行成否履歴テーブル１２が備える、上記エントリの総数は、ハッシュ関数回路１１の出力がｎビット幅である場合、２のｎ乗に等しい数である。この投機実行成否履歴テーブル１２は、ハッシュ関数回路１１が出力するエントリ番号が指し示すエントリに対して、書き込み、および読み出し処理を行う。
【００７０】
図２は、図１に示すプロセッサによる命令実行の手順を示すフローチャートである。上記のプロセッサは、データ依存関係検出装置３０によるロード命令の投機実行の成否判定機能、データ依存投機制御装置１０による前記投機実行の成否予測および実行制御機能を有する。命令の実行は、図２のブロック６０で開始され、ブロック６９で終了する。
【００７１】
まず、ブロック６１において、プロセッサ制御部２０による命令のデコード、および発行が行われる。次に、ブロック６２において、発行された命令がロード命令の場合は、ブロック６３へ、ロード命令以外の場合は、ブロック７４へ分岐する。発行された命令は、プロセッサ制御部２０が出力する実行命令１５により与えられる。
【００７２】
また、ブロック６３において、前記発行されたロード命令が投機的な実行の場合は、ブロック６４へ、確定的な実行の場合は、ブロック７２へ分岐する。実行が投機的であるか、確定的であるかは、プロセッサ制御部２０の出力する投機実行フラグ１３により与えられる。そして、このロード命令が投機的な実行の場合、ブロック６４において、データ依存投機制御装置１０により、投機実行が成功するか失敗するかの予測を行う。
【００７３】
次に、ブロック６５において、前記予測が、投機実行が“成功”することを予測した場合は、ブロック６６へ、“失敗”することを予測した場合には、ブロック７０へ分岐する。投機実行が“成功”することを予測した場合、ブロック６６において、そのロード命令を投機的に実行する。そして、ブロック６７において、ロード命令を投機実行した旨を、データ依存関係検出装置３０に記憶する。続くブロック６８において、投機実行を行ったという事実により、データ依存投機制御装置１０に記憶されている投機実行成否結果を更新し、次のブロック６９において、ロード命令の投機的な実行が終了する。
【００７４】
一方、ブロック６４において、ロード命令の投機実行が“失敗”することを予測した場合、ブロック７０において、そのロード命令の投機的な実行を中止する。このロード命令は、後にプログラム順序で確定的に実行されることになる。次のブロック７１では、投機実行を行わなかったという事実により、データ依存投機制御装置１０に記憶されている投機実行成否結果を更新し、ブロック６９において、今回のロード命令の実行を、中止により終了する。
【００７５】
他方、ブロック６３において、発行されたロード命令が確定的な実行の場合、ブロック７２において、そのロード命令を確定的に実行する。続くブロック７３において、確定的に実行したという事実により、データ依存投機制御装置１０に記憶されている投機実行成否結果を更新し、ブロック６９において、ロード命令の実行が終了する。
【００７６】
ブロック７４では、発行された命令がストア命令の場合は、ブロック７５に分岐し、発行された命令がロード命令でも、ストア命令でもない場合には、ブロック８１に分岐する。すなわち、ストア命令が発行された場合は、ブロック７５において、データ依存関係検出装置３０により、それ以前に投機実行されたロード命令が、前記ストア命令に関して成功したか、失敗したかを判定する。そして、ブロック７６において、投機実行が成功した場合は、ブロック７７に分岐し、投機実行が失敗した場合には、ブロック７９に分岐する。
【００７７】
投機実行が成功した場合、ブロック７７において、ストア命令を（確定的に）実行する。次のブロック７８において、投機実行が成功したという事実により、データ依存投機制御装置１０に記憶されている投機実行成否結果を更新し、ブロック６９において、ストア命令の実行が終了する。しかし、ブロック７６において、ロード命令の投機実行が失敗した場合、ブロック７９において、投機実行が失敗したという事実により、データ依存投機制御装置１０に記憶されている投機実行成否結果を更新する。続くブロック８０において、投機実行失敗の回復処理を実行し、ブロック６９において、ストア命令の実行が終了する。
【００７８】
ブロック７４において、発行された命令がロード命令でも、ストア命令でもない場合には、ブロック８１で命令を実行し、ブロック６９において終了する。この場合、データ依存投機制御装置１０、およびデータ依存関係検出装置３０は、何ら動作を行わない。
【００７９】
次に、再び図１を参照して、データ依存投機制御装置１０の動作の詳細を説明する。まず、図２に示すフローチャート上のブロック６４において、投機実行成否履歴テーブル１２に記憶されている投機実行の成否結果の履歴を参照し、それに基づいて、ロード命令の投機実行が成功するか、失敗するかの予測を行う。より詳細には、プロセッサ制御部２０から対象アドレス１４により与えられるロード命令の対象アドレスを、ハッシュ関数回路１１により投機実行成否履歴テーブル１２のエントリ番号に変換し、投機実行成否履歴テーブル１２に入力する。
【００８０】
投機実行成否履歴テーブル１２は、入力されたエントリ番号に対応するエントリの内容を読み出し、それに基づいて、前記ロード命令の投機実行の成否を予測する。また、図２に示すフローチャートにおけるブロック６８，７１，７３，７８，７９においては、それぞれの実行フローに基づいて、投機実行成否履歴１２に記憶されている投機実行の成否予測結果の履歴を更新する。
【００８１】
より詳細には、プロセッサ制御部２０から対象アドレス１４により与えられるロード・ストア命令の対象アドレスを、ハッシュ関数回路１１により投機実行成否履歴テーブル１２のエントリ番号に変換し、投機実行成否履歴テーブル１２に入力する。そこで、投機実行成否履歴テーブル１２は、入力されたエントリ番号に対応するエントリの内容を読み出し、そのエントリ内容とそれぞれの実行フローに基づいて、前記エントリ内容を更新する。
【００８２】
図３は、投機実行成否履歴テーブル１２の各エントリ内容の状態遷移を示す状態遷移図である。各エントリは、それぞれ３ビットの記憶素子から構成され、８つの投機実行成否履歴状態、すなわち、符号９０で示される“強い成功０”、符号９１の“強い成功１”、符号９２の“弱い成功０”、符号９３の“弱い成功１”、符号９４の“弱い失敗０”、符号９５の“弱い失敗１”、符号９６の“強い失敗０”、そして、符号９７の“強い失敗１”のいずれかの状態を指定する。
【００８３】
“強い成功０”９０は、それまで投機実行が成功した確率がかなり高く、かつ、そのエントリに割り当てられる対象アドレスのロード命令が、未だ投機的に発行されていない状態を示す。また、“強い成功１”９１は、それまで投機実行が成功した確率がかなり高く、かつ、そのエントリに割り当てられる対象アドレスのロード命令が、既に投機的に発行されている状態を示す。
【００８４】
“弱い成功０”９２は、“強い成功０”９０ほどではないが、それまで、投機実行が失敗したよりも、成功した確率が高く、かつ、そのエントリに割り当てられる対象アドレスのロード命令が、未だ投機的に発行されていない状態を示す。“弱い成功１”９３は、“強い成功１”９１ほどではないが、それまで、投機実行が失敗したよりも、成功した確率が高く、かつ、そのエントリに割り当てられる対象アドレスのロード命令が、既に投機的に発行されている状態を示す。
【００８５】
“強い失敗０”９６は、それまで、投機実行が失敗した確率がかなり高く、かつ、そのエントリに割り当てられる対象アドレスのロード命令が、未だ投機的に発行されていない状態を示す。“強い失敗１”９７は、それまで、投機実行が失敗した確率がかなり高く、かつ、そのエントリに割り当てられる対象アドレスのロード命令が、既に投機的に発行されている状態を示す。
【００８６】
また、“弱い失敗０”９４は、“強い失敗０”９６ほどではないが、それまで、投機実行が成功したよりも、失敗した確率が高く、かつ、そのエントリに割り当てられる対象アドレスのロード命令が、未だ投機的に発行されていない状態を示す。“弱い失敗１”９５は、“強い失敗１”９７ほどではないが、それまで、投機実行が成功したよりも、失敗した確率が高く、かつ、そのエントリに割り当てられる対象アドレスのロード命令が、既に投機的に発行されている状態を示す。
【００８７】
上記の投機実行成否履歴テーブル１２の各エントリが保持する８つの状態は、３ビットの記憶素子で実現することができる。例えば、図３において、“強い成功０”９０は、“０００”、“強い成功１”９１は、“００１”、“弱い成功０”９２は、“０１０”、“弱い成功１”９３は、“０１１”、“弱い失敗０”９４は、“１００”、“弱い失敗１”９５は、“１０１”、“強い失敗０”９６は、”１１０”、そして、“強い失敗１”９７は、“１１１”で表現される。
【００８８】
図２のフローチャートに示す、ブロック６４における投機実行の成否予測は、参照したエントリが、上記８つの状態のいずれにあるかで決定がなされる。すなわち、エントリが、“強い成功０”、“強い成功１”、“弱い成功０”、“弱い成功１”のいずれかにある場合は、投機実行が成功する可能性が高いと予測し、ロード命令を投機的に実行する。
【００８９】
一方、エントリが、“強い失敗０”、“強い失敗１”、“弱い失敗０”、“弱い失敗１”のいずれかにある場合には、投機実行が失敗する可能性が高いと予測し、ロード命令の投機実行を中止して、後にプログラム順序で確定的に実行する。
【００９０】
また、上記８状態間の状態遷移は、図２に示したフローチャートのブロック６８，７１，７３，７８，７９において、以下のように行う。まず、初期状態において、すべてのエントリが任意の状態にある。今、仮に、あるエントリが“弱い成功０”９２にあるとする。このとき、そのエントリに対応するアドレスを対象とする投機的なロード命令を発行した場合、ブロック６８において、エントリの状態を“弱い成功１”９３へ遷移させる。
【００９１】
この場合、ブロック６４の投機実行の成否予測で、投機実行が成功すると予測されるため、実際にロード命令が投機実行されることになる（ブロック６６）。それ以外の実行フローの場合、すなわち、ブロック７１，７３，７８，７９では、エントリの状態は遷移しない。
【００９２】
次に、エントリが、“弱い成功１”９３にある場合は、そのエントリに対応するアドレスを対象とするストア命令を実行し、ロード命令の投機実行の失敗が検出されなければ、ロード命令の投機実行が成功したとして、ブロック７８において、エントリの状態を“強い成功０”９０へ遷移させる。
【００９３】
一方、ロード命令の投機実行の失敗が検出された場合、ロード命令の投機実行が失敗したとして、ブロック７９において、エントリの状態を、“弱い失敗０”９４へ遷移させる。上記以外の実行フローの場合、すなわち、ブロック６８，７１，７３では、エントリの状態は遷移しない。
【００９４】
エントリが、“強い成功０”９０にあるときには、そのエントリに対応するアドレスを対象とする投機的なロード命令を発行した場合、ブロック６８において、エントリの状態を、“強い成功１”９１へ遷移させる。この場合、ブロック６４の投機実行の成否予測で、投機実行が成功すると予測されるため、実際にロード命令が投機実行されることになる（ブロック６６）。なお、それ以外の実行フローの場合、すなわち、ブロック７１，７３，７８，７９では、エントリの状態は遷移しない。
【００９５】
エントリが、“強い成功１”９１にある場合には、そのエントリに対応するアドレスを対象とするストア命令を実行し、ロード命令の投機実行の失敗が検出されなかった場合は、ロード命令の投機実行が成功したとして、ブロック７８において、エントリの状態は、“強い成功０”９０へ遷移させる。
【００９６】
他方、ロード命令の投機実行の失敗が検出された場合は、ロード命令の投機実行が失敗したとして、ブロック７９において、エントリの状態を、“弱い成功０”９２へ遷移させる。それ以外の実行フローの場合、すなわち、ブロック６８，７１，７３では、エントリの状態は遷移しない。
【００９７】
エントリが、“弱い失敗０”９４にあるときは、そのエントリに対応するアドレスを対象とする投機的なロード命令を発行した場合、ブロック７１において、エントリの状態を、“弱い失敗１”９５へ遷移させる。この場合、ブロック６４の投機実行の成否予測で、投機実行が失敗すると予測されるため、実際にロード命令が投機実行されることはない。上記以外の実行フローの場合、すなわち、ブロック６８，７３，７８，７９では、エントリの状態は遷移しない。
【００９８】
エントリが、“弱い失敗１”９５にあるときは、そのエントリに対応するアドレスを対象とするストア命令を実行した場合、ロード命令の投機実行は、失敗する可能性が高いとして、ブロック７８、またはブロック７９において、エントリの状態を、“強い失敗０”９６へ遷移させる。この場合、ロード命令の投機実行は、失敗する可能性が高いと判断するのは、“弱い失敗０”９４から投機的なロードが発行されて、“弱い失敗１”９５に遷移し、かつ、同アドレスのストア命令が実行されたからである。
【００９９】
実際は、ブロック６４において、投機実行は失敗すると予測されるため、投機実行は中止され、確定的に実行されるが、仮にロード命令を投機実行していたならば、その投機実行は失敗することになる。
【０１００】
一方、エントリが、“弱い失敗１”９５にあるとき、そのエントリに対応するアドレスを対象とする確定的なロード命令が発行された場合、ロード命令の投機実行は、成功する可能性が高いとして、ブロック７１において、エントリの状態を、“弱い成功０”９２へ遷移させる。この場合、ロード命令の投機実行は、成功する可能性が高いと判断する理由は、“弱い失敗０”９４から投機的なロードが発行されて、“弱い失敗１”９５に遷移し、かつ、同アドレスのストア命令が実行されずに、確定的なロード命令が発行されたからである。
【０１０１】
この確定的なロード命令は、ブロック６４において、投機実行が失敗すると予測されて、確定的に実行されたロード命令と考えられ、かつ、その間に同アドレスのストア命令が発行されなかったことから、仮に、ロード命令を投機実行していたならば、その投機実行は成功していたことになる。なお、上記以外の実行フローの場合、すなわち、ブロック６８，７３では、エントリの状態は遷移しない。
【０１０２】
次に、エントリが、“強い失敗０”９６にあるときには、そのエントリに対応するアドレスを対象とする投機的なロード命令を発行した場合、ブロック７１において、エントリの状態を、“強い失敗１”９７へ遷移させる。この場合、ブロック６４の投機実行の成否予測で、投機実行が失敗すると予測されるため、実際にロード命令が投機実行されることはない。上記以外の実行フローの場合、すなわち、ブロック６８，７３，７８，７９では、エントリの状態は遷移しない。
【０１０３】
エントリが、“強い失敗１”９７にあるとき、そのエントリに対応するアドレスを対象とするストア命令を実行した場合、ロード命令の投機実行は、失敗する可能性が高いとして、ブロック７８、またはブロック７９において、エントリの状態は、“強い失敗０”９６へ遷移させる。この場合、ロード命令の投機実行は、失敗する可能性が高いと判断する理由は、“強い失敗０”９６から投機的なロードが発行されて、“強い失敗１”９７に遷移し、かつ、同アドレスのストア命令が実行されたからである。
【０１０４】
実際には、ブロック６４において、投機実行は失敗すると予測されるため、投機実行は中止され、確定的に実行されるが、仮に、ロード命令を投機実行していたならば、その投機実行は失敗することになる。
【０１０５】
一方、エントリが、“強い失敗１”９７にあるとき、そのエントリに対応するアドレスを対象とする、確定的なロード命令が発行された場合、ロード命令の投機実行は、成功する可能性が高いとして、ブロック７１において、エントリの状態を、“弱い失敗０”９４へ遷移させる。この場合、ロード命令の投機実行は、成功する可能性が高いと判断する理由は、“強い失敗０”９６から投機的なロードが発行されて、“強い失敗１”９７に遷移し、かつ、同アドレスのストア命令が実行されずに、確定的なロード命令が発行されたからである。
【０１０６】
この確定的なロード命令は、ブロック６４において、投機実行が失敗すると予測されて、確定的に実行されたロード命令と考えられ、かつ、その間に同アドレスのストア命令が発行されなかったことから、仮に、ロード命令を投機実行していたならば、その投機実行は成功していたことになる。上記以外の実行フローの場合、すなわち、ブロック６８，７９では、エントリの状態は遷移しない。
【０１０７】
以上、投機実行成否履歴テーブル１２の各エントリ内容の状態遷移を説明したが、上述のように、投機実行が成功する確率が高ければ、“強い失敗”、“弱い失敗”から“弱い成功”、“強い成功”へ、また、投機実行が失敗する確率が高ければ、“強い成功”、“弱い成功”から“弱い失敗”、“強い失敗”へと遷移して行く。
【０１０８】
ブロック６４における投機実行の成否予測では、“弱い成功”、“強い成功”にあれば成功すると予測して、ロード命令の投機実行するが、“強い失敗”、“弱い失敗”にあれば失敗すると予測して、ロード命令の投機実行を中止し、後に、プログラム順序で確定的に実行する。すなわち、本実施の形態に係るデータ依存投機制御装置１０では、失敗する確率の高い投機実行は確定的に実行されるため、投機実行が失敗する確率が低減し、プログラムの実行性能が向上する。
【０１０９】
通常、メモリ操作命令が操作対象とするアドレス空間よりも、投機実行成否履歴テーブル１２のエントリ数の方が、はるかに小さいため、ハッシュ関数回路１１は、異なるアドレスを対象とする複数のメモリ操作命令に対して、投機実行成否履歴テーブル１２の同一のエントリ番号を割り当てる。すなわち、異なるアドレスを対象とする複数のメモリ操作命令に対して、投機実行成否履歴テーブル１２の同一のエントリで、投機実行の成否予測を行う場合がある。このような異なるアドレスを対象とする複数のメモリ操作命令が、投機実行成否履歴テーブル１２の同一のエントリに割り当てられることを、“エイリアスが発生する”という。
【０１１０】
かかるエイリアスが発生した場合、投機実行の成否履歴の蓄積を適切に行えない場合があるので、投機実行の成否予測の精度、すなわち、予測が的中する確率が低下することがある。その場合でも、プログラムの実行結果の正しさは保証される。そのため、プログラムの意味上に問題は生じないが、予測精度の低下の分だけ、投機実行によるプログラムの実行性能の向上が削減される、という問題がある。
【０１１１】
このようなことから、エイリアスは、なるべく発生しない方が望ましい。エイリアスは、ハッシュ関数回路１１のハッシュ関数を適切に選択したり、あるいは、投機実行成否履歴テーブル１２のエントリを十分、多く実装することにより、低減することが可能である。
【０１１２】
一方、エイリアスの発生を許容する利点として、投機実行の成否予測を行えるロード命令の数が、投機実行成否履歴テーブル１２のエントリ数に制限されないことがある。このため、多くの場合、エイリアスの発生を許容せず、投機実行の成否予測が可能なロード命令数を制限するよりも、本実施の形態による投機実行の成否予測の方が、投機実行による性能向上の効果が大きい。
【０１１３】
次に、本実施の形態１に係るデータ依存投機制御装置の動作の具体例について説明する。なお、ここでは、投機実行成否履歴テーブル１２は、４つのエントリ、すなわち、エントリ０〜３から構成される。ハッシュ関数回路１１は、例えば、アドレスが８ビットで表現されるとすると、図５の（ａ）に示すように、入力されるアドレスの特定の２ビットを出力することで、実現できる。あるいは、図５の（ｂ）に示すように、特定の複数ビットの排他的論理和を演算した結果を出力するようにしてもよい。
【０１１４】
図４を参照して、データ依存投機制御装置１０の具体的な動作例を説明する。まず、図４の（ａ）は、プログラム例における命令プログラム順序を示す。このプログラム順序は、ストア命令ＳＴ１、ロード命令ＬＤ１、ロード・ストア命令以外の命令、ロード命令ＬＤ２の順序で発行される命令列が繰り返される、ループ構造を持つプログラムにおいて典型的なものである。図４の（ａ）には、ループ０〜２の連続する３つのループに含まれる命令列のみを示す。
【０１１５】
ここで、ＳＴ１の対象アドレスはＡ１、ＬＤ１の対象アドレスはＡ２、ＬＤ２の対象アドレスはＡ１’である。Ａ１とＡ１’が等しいとすると、プログラム順序で、ＳＴ１の方が前にあるため、ＳＴ１からＬＤ２には、正依存関係が存在する。すなわち、実行時において、ＬＤ２よりもＳＴ１が先に実行されて、ＳＴ１がアドレスＡ１に書き込みを行った結果を、ＬＤ２がアドレスＡ１’（＝Ａ１）から読み出しを行わなければ、プログラムの実行結果の正しさは保証されない。
【０１１６】
プロセッサがデータ依存投機実行状態にある場合、ストア命令からロード命令への正依存関係の有無が不明であっても、実行可能になった命令から実行される。図４の（ｂ）は、データ依存投機実行状態における、図４の（ａ）に示すプログラム順序の命令列のデータ依存投機実行による、非プログラム順序実行例である。同図において、左から順に、サイクル番号、そのサイクルの実行命令、その実行命令の対象アドレスを示す。ここで、ＳＴ１の対象アドレスＡ１は、４サイクル目まで判明しないと想定する。また、ＬＤ１の対象アドレスＡ２、およびＬＤ２の対象アドレスＡ１’は、１サイクル目で判明すると想定する。
【０１１７】
図４の（ｃ）は、図４の（ｂ）に示す命令実行順序に対する、投機実行成否履歴テーブル１２の動作を示している。同図において、左から順に、サイクル番号、そのサイクルに実行されたメモリ命令が参照する投機実行成否履歴テーブル１２のエントリ番号、そのサイクルの投機実行成否履歴テーブル１２の状態を示す。投機実行成否履歴テーブル１２の状態については、４つのエントリを、右から順に、エントリ０、エントリ１、エントリ２、エントリ３の内容を示している。
【０１１８】
例えば、ループ０の１サイクル目において、エントリ０の内容は、“１００”（弱い失敗０）、エントリ１の内容は“０００”（強い成功０）、エントリ２の内容は“０１０”（弱い成功０）、エントリ３の内容は“０００”（強い成功０）である。
【０１１９】
ループ０の１サイクル目では、ＳＴ１の発行順であるが、その対象アドレスＡ１が判明していないため、対象アドレスＡ２が判明している、次のＬＤ１を、非プログラム順序で投機実行することを試みる。まず、投機実行に先立ち、データ依存投機制御装置１０により、投機実行の成否予測を行う（図２のブロック６４）。より詳細には、まず、ＬＤ１のアドレスＡ２を、ハッシュ関数回路１１により、投機実行成否履歴テーブル１２のエントリ番号に変換する。ここで、エントリ番号０に変換されたとすると、次に、投機実行成否履歴テーブル１２より、エントリ０に格納されている成否予測履歴“１００”（弱い失敗０）が読み出される。
【０１２０】
従って、投機実行が失敗することが予測されるので、ＬＤ１の投機実行は中止され、後に、プログラム順序で確定的に実行される（図２のブロック７０）。また、投機実行成否履歴テーブル１２のエントリ０は、“１０１”（弱い失敗１）に遷移する（図２のブロック７１）。
【０１２１】
ループ０の２サイクル目では、いまだ、ＳＴ１は実行できないので、ＬＤ１の次のメモリ操作命令以外の命令を実行する。データ依存投機制御装置１０は、何ら動作を行わない。次に、ループ０の３サイクル目では、いまだ、ＳＴ１は実行できないので、対象アドレスＡ１’が判明しているＬＤ２を、非プログラム順序で投機実行することを試みる。
【０１２２】
まず、投機実行に先立ち、データ依存投機制御装置１０により、投機実行の成否予測を行う（図２のブロック６４）。より詳細には、ＬＤ２のアドレスＡ１’を、ハッシュ関数回路１１により、投機実行成否履歴テーブル１２のエントリ番号に変換する。ここで、エントリ番号２に変換されたとすると、次に、投機実行成否履歴テーブル１２より、エントリ２に格納されている成否予測履歴“０１０”（弱い成功０）が読み出される。
【０１２３】
従って、投機実行が成功することが予測されるので、ＬＤ２は投機的に実行される（図２のブロック６６）。投機実行成否履歴テーブル１２のエントリ２は、“０１１”（弱い成功１）へ遷移する（図２のブロック６８）。
【０１２４】
次に、ループ０の４サイクル目では、ＳＴ１の対象アドレスＡ１が判明するので、ＳＴ１を実行する。その際、データ依存関係検出装置３０により、それまで、データ依存関係に対して投機的に実行されたロード命令の成否を判定する（図２のブロック７５）。この場合、ＳＴ１からＬＤ２へ、正依存関係が存在しているにも関わらず、ＳＴ１よりもＬＤ２を先に実行してしまったため、ＬＤ２の投機実行は、失敗している。
【０１２５】
すなわち、ＬＤ２は、アドレスＡ１’（＝Ａ１）から、ＳＴ１が、アドレスＡ１に書き込みを行った値ではなく、ＳＴ１が書き込みを行う以前の値を読み出してしまうため、プログラムの正しい実行結果を得ることが保証されないことになる。データ依存投機制御装置３０は、このデータ依存投機実行の失敗を検出し、プロセッサ制御部２０へ通知する機能を担う。
【０１２６】
その通知により、プロセッサ制御部２０は、正しいプログラムの実行結果が得られるように、データ依存投機実行した命令の再実行など、データ依存投機実行の失敗による回復処理を行う。具体的には、１サイクル目から４サイクル目までに実行された、ＬＤ１、メモリ操作命令以外の命令、ＬＤ２、ＳＴ１の実行結果を取り消し、６サイクル目から、今度は、プログラム順序で確定的にそれら取り消した命令を再実行する。すなわち、６サイクル目にＳＴ１、７サイクル目にＬＤ１、８サイクル目にメモリ操作命令以外の命令、９サイクル目にＬＤ２を確定的に再実行する。
【０１２７】
一方、データ依存投機制御装置１０においては、４サイクル目に、ＳＴ１により投機実行の失敗が検出されたため、投機実行成否履歴テーブル１２のエントリ２を、“０１１”（弱い成功１）から“１００”（弱い失敗０）へ遷移させる（図２のブロック７９）。６サイクル目から９サイクル目の確定的に命令実行されるサイクルでは、データ依存投機制御装置１０は、何ら動作を行わず、投機実行成否履歴テーブル１２も、参照および更新されない。
【０１２８】
以上、ループ０における命令実行、およびデータ依存投機制御装置１０の動作について説明した。ＬＤ２の投機実行の成否予測は、成功を予測したのに対して、実際には、投機実行は失敗し、投機実行失敗による回復処理の実行が必要となった。このため、ループ０においては、ＳＴ１，ＬＤ１、メモリ操作命令以外の命令、ＬＤ２の４命令の実行に、９サイクルを要した。
【０１２９】
次に、ループ０に続く、ループ１での動作を説明する。ここでも、ループ０の実行時と同様に、ＳＴ１の対象アドレスＡ１は、４サイクル目まで判明しないと想定する。また、ＬＤ１の対象アドレスＡ２、およびＬＤ２の対象アドレスＡ１’は、１サイクル目で判明すると想定する。
【０１３０】
ループ１の１サイクル目では、ＳＴ１の発行順であるが、その対象アドレスＡ１が判明していないため、対象アドレスＡ２が判明している次のＬＤ１を、非プログラム順序で投機実行することを試みる。まず、投機実行に先立ち、データ依存投機制御装置１０により、投機実行の成否予測を行う（図２のブロック６４）。投機実行成否履歴テーブル１２のエントリ０からは、“１０１”（弱い失敗１）が読み出されるので、投機実行が失敗することが予測される。
【０１３１】
従って、ＬＤ１の投機実行は中止され、後に、プログラム順序で確定的に実行される（図２のブロック７０）。この場合、投機実行成否履歴テーブル１２のエントリ０の状態は遷移しない（図２のブロック７１）。
【０１３２】
ループ１の２サイクル目では、いまだ、ＳＴ１は実行できないので、ＬＤ１の次のメモリ操作命令以外の命令を実行する。データ依存投機制御装置１０は、何ら動作を行わない。次に、ループ１の３サイクル目では、いまだ、ＳＴ１は実行できないので、対象アドレスＡ１’が判明しているＬＤ２を、非プログラム順序で投機実行することを試みる。
【０１３３】
まず、投機実行に先立ち、データ依存投機制御装置１０により、投機実行の成否予測を行う（図２のブロック６４）。投機実行成否履歴テーブル１２のエントリ２からは、“１００”（弱い失敗０）が読み出されるので、投機実行は、失敗することが予測される。従って、ＬＤ２の投機実行は中止され、後に、プログラム順序で確定的に実行される（図２のブロック７０）。また、投機実行成否履歴テーブル１２のエントリ２は、“１０１”（弱い失敗１）に遷移する（図２のブロック７１）。
【０１３４】
ループ１の４サイクル目では、ＳＴ１の対象アドレスＡ１が判明するので、ＳＴ１を実行する。その際、データ依存関係検出装置３０により、それまでデータ依存関係に対して投機的に実行されたロード命令の成否を判定する（図２のブロック７５）。この場合、ＳＴ１からＬＤ２へ、正依存関係が存在しているが、ＬＤ２は、３サイクル目において、投機実行が失敗することが予測されたため、投機実行が中止されている。
【０１３５】
このため、ＳＴ１に関して、投機実行が失敗したロード命令は存在せず、ＳＴ１は、確定的に実行される（図２のブロック７７）。また、ストア命令が実行されたため、投機実行成否履歴テーブル１２のエントリ２は、“１０１”（弱い失敗１）から“１１０”（強い失敗０）へ遷移する（図２のブロック７８）。
【０１３６】
ループ１の５サイクル目では、１サイクル目に投機実行が中止されたＬＤ１が、ＳＴ１に対してプログラム順序で、かつ、確定的に実行される。また、投機実行成否履歴テーブル１２のエントリ０は、“１０１”（弱い失敗１）から“０１０”（弱い成功０）へ遷移する（図２のブロック７３）。次に、ループ１の６サイクル目では、３サイクル目に投機実行が中止されたＬＤ２が、ＳＴ１に対してプログラム順序で、かつ、確定的に実行される。投機実行成否履歴テーブル１２のエントリ２は、“１１０”（強い失敗０）のままである（図２のブロック７３）。
【０１３７】
以上が、ループ１における命令実行、およびデータ依存投機制御装置１０の動作説明である。ここでは、ループ０の場合と異なり、ＬＤ２の投機実行の成否予測は、正しく失敗を予測したため、ＬＤ２の投機実行失敗が回避された。このため、ループ０においては、ＳＴ１，ＬＤ１、メモリ操作命令以外の命令、ＬＤ２の４命令の実行は、６サイクルに改善された。
【０１３８】
次に、ループ１に続くループ２における動作を説明する。ループ０、ループ１の実行時と同様、ＳＴ１の対象アドレスＡ１は、４サイクル目まで判明せず、一方、ＬＤ１の対象アドレスＡ２、およびＬＤ２の対象アドレスＡ１’は、１サイクル目で判明すると想定する。
【０１３９】
ループ２の１サイクル目では、ＳＴ１の発行順であるが、その対象アドレスＡ１が判明していないため、対象アドレスＡ２が判明している、次のＬＤ１を、非プログラム順序で投機実行することを試みる。まず、投機実行に先立ち、データ依存投機制御装置１０により、投機実行の成否予測を行う（図２のブロック６４）。投機実行成否履歴テーブル１２のエントリ０からは、“０１０”（弱い成功０）が読み出されるので、投機実行が成功することが予測される。
【０１４０】
従って、ＬＤ１は、投機的に実行される（図２のブロック６６）。投機実行成否履歴テーブル１２のエントリ０は、“０１１”（弱い成功１）に遷移する（図２のブロック６８）。
【０１４１】
ループ２の２サイクル目では、いまだ、ＳＴ１は実行できないので、ＬＤ１の次のメモリ操作命令以外の命令を実行する。データ依存投機制御装置１０は、何ら動作を行わない。次に、ループ２の３サイクル目では、いまだ、ＳＴ１は実行できないので、対象アドレスＡ１’が判明しているＬＤ２を、非プログラム順序で投機実行することを試みる。
【０１４２】
まず、投機実行に先立ち、データ依存投機制御装置１０により、投機実行の成否予測を行う（図２のブロック６４）。投機実行成否履歴テーブル１２のエントリ２からは、“１１０”（強い失敗０）が読み出されるので、投機実行が失敗することが予測される。従って、ＬＤ２の投機実行は中止され、後に、プログラム順序で、確定的に実行される（図２のブロック７０）。また、投機実行成否履歴テーブル１２のエントリ２は、“１１１”（強い失敗１）に遷移する（図２のブロック７１）。
【０１４３】
ループ２の４サイクル目では、ＳＴ１の対象アドレスＡ１が判明するので、ＳＴ１を実行する。その際、データ依存関係検出装置３０により、それまで、データ依存関係に対して投機的に実行されたロード命令の成否を判定する（図２のブロック７５）。この場合、ＳＴ１からＬＤ２へ、正依存関係が存在しているが、ＬＤ２は、３サイクル目において、投機実行が失敗することが予測されたため、投機実行が中止されている。
【０１４４】
このため、ＳＴ１に関して、投機実行が失敗したロード命令は存在せず、ＳＴ１は、確定的に実行される（図２のブロック７７）。また、ストア命令が実行されたため、投機実行成否履歴テーブル１２のエントリ２は、“１１１”（強い失敗１）から“１１０”（強い失敗０）へ遷移する（図２のブロック７８）。
【０１４５】
次に、ループ２の５サイクル目では、３サイクル目に投機実行が中止されたＬＤ２が、ＳＴ１に対してプログラム順序で、かつ、確定的に実行される。投機実行成否履歴テーブル１２のエントリ２は、“１１０”（強い失敗０）のままである（図２のブロック７３）。
【０１４６】
以上、ループ２における命令実行、およびデータ依存投機制御装置１０の動作について説明した。ここでも、ループ１の場合と同様に、ＬＤ２の投機実行の成否予測は、正しく失敗を予測したため、ＬＤ２の投機実行失敗が回避された。さらに、ループ１の場合とは異なり、ＬＤ１の投機実行の成否予測は、正しく成功を予測したため、ＬＤ１は、投機的に実行し、かつ、成功した。
【０１４７】
このため、ループ２においては、ＳＴ１，ＬＤ１、メモリ操作命令以外の命令、ＬＤ２の４命令の実行は、５サイクルに改善された。また、この例の場合、５サイクルが最小の実行サイクル数である。
【０１４８】
以上説明したように、本実施の形態によれば、データ依存投機制御装置１０は、投機実行が失敗すると予測されるロード命令は、投機実行を行わず、プログラム順序で確定的に実行する。その結果、投機実行が失敗する確率が低減され、プログラムの実行性能を向上できる。
【０１４９】
すなわち、データ依存投機制御装置１０は、過去における投機実行の成否結果の履歴を参照して、投機実行の成否を予測し、成功すると予測した場合には、投機的に実行を行うが、失敗すると予測した場合、投機実行を中止し、後に、プログラム順序で確定的に実行する。よって、このデータ依存投機制御装置１０によれば、失敗する確率の高い投機実行は確定的に実行されるため、投機実行が失敗する確率が低減され、プログラムの実行性能を向上することができるという効果を得ることができる。上記の具体例では、ループ０からループ２へループを繰り返すのに伴って、４命令の実行サイクルが、９サイクルから５サイクルに改善された。
【０１５０】
さらに、本実施の形態１に係るデータ依存投機制御装置１０に特徴的なのは、投機実行の成否予測を行うに際して、ロード・ストア命令の対象アドレスに関して、エイリアスの存在を許容することで、対象アドレスそのものを、すべて記憶する必要をなくしたことである。これにより、投機実行の成否予測が可能なロード命令数に制限がなく、必要なハードウエア量も小さく、少ないハードウエア量でも、データ依存投機実行による実行性能の向上を享受することができる。
【０１５１】
また、投機実行の成否予測を行うに際して、ロード・ストア命令間の対象アドレスの比較を必要とせず、参照される投機実行成否履歴テーブル１２のエントリは、高々１つなので、投機実行の成否予測の処理時間が短いという特徴がある。このため、プロセッサの動作周波数を高速化することが容易になる。
【０１５２】
［実施の形態２］
以下、本発明の実施の形態２について、図面を参照して詳細に説明する。図６は、本発明の実施の形態２に係るデータ依存投機制御装置の構成を示すブロック図である。このデータ依存投機制御装置は、マルチプロセッサシステムにより実行されるスレッド並列処理のデータ依存投機実行において、データ依存投機実行の制御手段を提供する。
【０１５３】
ここで、スレッド並列処理とは、単一のプログラム、あるいは複数のプログラムを、スレッドと呼ぶ複数のプログラムの部分単位に分割し、それぞれのスレッドを、複数のプロセッサなどで並列に処理することで、プログラムの実行を高速化する、プログラム処理の高速化方法の一つである。
【０１５４】
スレッドは、プログラムの一部分単位であり、複数の命令からなる命令列なので、複数のスレッド間で、順序関係が定義される場合がある。例えば、同一のプログラムに属する２つのスレッドを、それぞれＴ０，Ｔ１としたとき、Ｔ０とＴ１の間には、そのプログラム中の位置関係により、明確に順序関係が存在する。仮に、プログラムにおいて、Ｔ０がＴ１よりも前に位置しているならば、プログラムの意味上、Ｔ０がＴ１よりも前に実行されることを期待されていることになる。
【０１５５】
逆に、プログラムにおいて、Ｔ１がＴ０よりも前に位置しているならば、プログラムの意味上、Ｔ１がＴ０よりも前に実行されることを期待されていることになる。しかし、Ｔ０、およびＴ１に含まれる命令間に依存関係が存在しない場合、Ｔ０とＴ１間の順序関係を無視した順序で実行しても、プログラムの意味は変わらない。そのため、正しいプログラムの実行結果を得ることができる。
【０１５６】
スレッド並列処理では、上述した性質を利用して、プログラムの正しい実行結果を保証しつつ、スレッド間の順序関係によらずに、スレッドの実行を並列に行うことで、プログラム実行を高速化する。命令単位の非プログラム順序実行と対比して、スレッド単位の非プログラム順序実行と位置づけられる。
【０１５７】
スレッド単位の非プログラム順序実行においても、正しいプログラムの実行結果を得るためには、スレッドが含む命令間の依存関係の解消や保証が必要である。しかしながら、命令単位の非プログラム順序実行と同様に、特にメモリに関する正依存関係に対しては、本質的にプログラム順序で実行する必要があり、かつ、確定的にプログラム順序実行すると、非プログラム順序実行の実行性能向上の効果が十分、得られないという問題がある。
【０１５８】
特に、スレッド単位の非プログラム順序実行では、複数の命令からなるスレッド単位で、非プログラム順序実行が妨げられるので、より問題は深刻である。そこで、この問題への対応としては、命令単位の非プログラム順序実行と同様に、データ依存投機実行が有効である。すわなち、スレッドが含む命令間の正依存関係の有無が判明するよりも以前に、正依存関係が存在しないと仮定して、投機的にスレッドの非プログラム順序実行を行う、スレッド単位のデータ依存投機実行である。
【０１５９】
スレッド単位のデータ依存投機実行を実現するためには、順序関係が存在するスレッド対に関して、順序が前のスレッドが含むストア命令から、順序が後のスレッドが含むロード命令への正依存関係を検出する機能を必要とする。本実施の形態２におけるデータ依存関係検出装置は、このスレッド間の正依存関係を検出する機能を有する。
【０１６０】
一方、スレッド単位のデータ依存投機実行においても、データ依存投機実行が失敗する確率が高い場合、データ依存投機実行失敗の回復処理のために、プログラムの実行性能が低下してしまう、という問題がある。
【０１６１】
そこで、本実施の形態２におけるデータ依存投機制御装置は、スレッド単位のデータ依存投機実行に際し、過去における命令についての、投機実行の予測結果の履歴を参照して、投機実行の成否を予測する。そして、成功すると予測した場合には、投機的に命令を実行するが、失敗すると予測した場合、投機実行を中止し、後に、プログラム順序で、確定的に命令実行する。
【０１６２】
すなわち、本実施の形態２におけるデータ依存投機制御装置によれば、マルチプロセッサシステムにおけるスレッド並列処理において、失敗する確率の高い命令の投機実行は、確定的に実行される。そのため、投機実行が失敗する確率が低減し、プログラムの実行性能を向上させることができる。
【０１６３】
そこで、図６を参照して、本実施の形態２におけるデータ依存投機制御装置の構成を説明する。図６に示すデータ依存投機制御装置は、４つのプロセッサ、すなわち、プロセッサ５０，５１，５２，５３、スレッド制御部５４、および、データ依存投機制御装置５５により構成されるマルチプロセッサ構成を有する。なお、プロセッサ５０〜５３の構成は、すべて同一であるため、図６では、プロセッサ５１，５２，５３の内部構成は、その図示を省略している。
【０１６４】
スレッド制御部５４は、プロセッサ５０〜５３各々が実行するスレッドの割り当てや、スレッド間の順序関係の通知、スレッドのデータ依存投機実行が失敗した場合の回復処理の指示など、スレッド並列処理、およびデータ依存投機実行の制御を行う。そして、プロセッサ５０〜５３は、データ依存関係検出装置５７、プロセッサ制御部５６、および、命令実行部２１を含む。
【０１６５】
本実施の形態２では、スレッド単位の投機実行は行うが、スレッド内のスレッドを構成する命令単位での投機実行を行わないものとする。そのため、データ依存関係検出装置５７は、スレッド間の正依存関係を検出する機能を備えるが、スレッド内のスレッドを構成する命令間の正依存関係を検出する機能は備えていない。また、データ依存投機制御装置５５は、４つのプロセッサ５０〜５３で共有され、各プロセッサのスレッド単位の投機実行の制御を行う。
【０１６６】
プログラムをプロセッサ５０〜５３によりスレッド並列処理するにあたり、スレッド制御部５４は、プロセッサ５０〜５３各々が実行すべきスレッドの割り当てを行う。また、プロセッサ５０〜５３それぞれに、そのスレッド実行は、データ依存投機実行か否かを示す投機実行フラグ４０や、他の３つのプロセッサが実行するスレッドとの順序関係を示すスレッド順序４１を出力する。加えて、スレッド制御部５４は、各プロセッサへ出力する投機実行フラグ４０を、データ依存投機制御装置５５にも出力する。
【０１６７】
各プロセッサが、スレッド制御部５４より割り当てられたスレッドを実行する場合、各プロセッサのプロセッサ制御部５６は、実行する命令の種別を、実行命令４５を通じて、命令実行部２１、データ依存関係検出装置５７、他の３つのプロセッサ、および、データ依存投機制御装置５５に出力する。
【０１６８】
さらに、実行する命令がメモリ操作命令の場合、プロセッサ制御部５６は、その対象アドレス４６を、命令実行部２１、データ依存関係検出装置５７、他の３つのプロセッサ、および、データ依存投機制御装置５５に出力する。従って、各プロセッサが備えるデータ依存関係検出装置５７は、それぞれのプロセッサが実行する命令種別、および、他の３つのプロセッサが実行する命令種別を実行命令４５から入力する。
【０１６９】
さらに、それら実行命令がメモリ操作命令の場合、その対象アドレスを、それぞれ対象アドレス４６から入力する。同時に、データ依存投機制御装置５５は、各４つのプロセッサ５０〜５３が実行する命令種別をそれぞれ、実行命令４５から入力する。それらの実行命令がメモリ操作命令の場合、その対象アドレスをそれぞれ対象アドレス４６から入力する。
【０１７０】
例えば、プロセッサ５０が、スレッド制御部５４より割り当てられたスレッドを実行する際、プロセッサ５０のプロセッサ制御部５６は、実行命令４５を通じて実行する命令の種別を、プロセッサ５０の命令実行部２１、およびデータ依存関係検出装置５７に加えて、他の３つのプロセッサ（プロセッサ５１、プロセッサ５２、プロセッサ５３）、および、データ依存投機制御装置５５に出力する。
【０１７１】
同時に、プロセッサ５０のデータ依存関係検出装置５７は、他の３つのプロセッサ（プロセッサ５１、プロセッサ５２、プロセッサ５３）が実行する命令種別を、実行命令４５を通じて、それぞれ入力する。さらに、実行する命令がメモリ操作命令の場合、プロセッサ５０のプロセッサ制御部５６は、その対象アドレスを、対象アドレス４６を通じて、プロセッサ５０の命令実行部２１、およびデータ依存関係検出装置５７に加えて、他の３つのプロセッサ、および、データ依存投機制御装置５５に出力する。
【０１７２】
同時に、他の３つのプロセッサが実行する命令が、メモリ操作命令の場合、プロセッサ５０のデータ依存関係検出装置５７は、その対象アドレスを、対象アドレス４６を通じて、それぞれ入力する。
【０１７３】
各プロセッサが備えるデータ依存関係検出装置５７は、各プロセッサが実行するスレッドの順序関係に基づいて、他の３つのプロセッサが実行するスレッドの中で、自プロセッサが実行するスレッドよりも順序が前のスレッドが含むストア命令から、自プロセッサが実行するスレッドが含むロード命令への、正依存関係を検出する機能を備える。
【０１７４】
図７は、図６のデータ依存関係検出装置５７の一構成を示すブロック図である。同図において、本データ依存関係検出装置５７が入力する実行命令４５のうち、自プロセッサのプロセッサ制御部５６から入力されるものを実行命令４５ａ、他の３つのプロセッサから入力されるものを実行命令４５ｂと表記している。同様に、データ依存関係検出装置５７が入力する対象アドレス４６のうち、自プロセッサのプロセッサ制御部５６から入力されるものを対象アドレス４６ａ、他の３つのプロセッサから入力されるものを対象アドレス４６ｂと表記している。
【０１７５】
データ依存関係検出装置５７は、自プロセッサが実行したロード命令の対象アドレスを格納する複数のアドレスバッファ３１、３つのアドレス一致検出回路３５、および、先行スレッド選択回路３４から構成される。アドレス一致検出回路３５は、さらに、各々のアドレスバッファ３１に接続された複数のアドレス比較器３２、すべてのアドレス比較器３２の出力をその入力とする論理和回路３３から構成される。このアドレス一致検出回路３５は、各アドレスバッファ３１に格納された、自プロセッサが実行したロード命令の対象アドレスと、他のプロセッサが実行中のストア命令の対象アドレスとの比較を行う。
【０１７６】
自プロセッサ以外の、他の３つのプロセッサが同時にアドレス比較を実行可能とするため、データ依存関係検出装置５７は、３つのアドレス一致検出回路３５を備える。先行スレッド選択回路３４は、３つのアドレス一致検出回路３５の出力、他の３つのプロセッサからの実行命令４５ｂ、スレッド制御部５４からの投機実行フラグ４０、スレッド順序４１を参照する。そして、他の３つのプロセッサが実行するスレッドの中で、自プロセッサが実行するスレッドよりも順序が前のスレッドが含むストア命令から、自プロセッサが実行するスレッドが含むロード命令への正依存関係の検出結果を選択し、それをデータ依存検出結果４９として、スレッド制御部５４へ出力する。
【０１７７】
データ依存関係検出装置５７による、他のプロセッサが実行する先行するスレッドが含むストア命令から、自プロセッサが実行するスレッドが含むロード命令へのメモリに関する正依存関係（以下、スレッド間の正依存関係と表記する）の検出は、以下に示す動作で実現される。
【０１７８】
まず、各プロセッサが、スレッド間のデータ依存関係に対して、プログラム順序で確定的に命令実行する場合、データ依存関係検出装置５７は、何ら動作を行わない。それに対して、各プロセッサが、スレッド間のデータ依存関係に対して、投機的な命令実行をする場合、データ依存関係検出装置５７は、スレッド間の正依存関係の検出処理を行う。各プロセッサが、スレッド実行に関して、確定実行状態、または投機実行状態のどちらにあるかは、スレッド制御部５４から各プロセッサのデータ依存関係検出装置５７に入力される投機実行フラグ４０で判断する。
【０１７９】
まず、投機実行状態において、自プロセッサがロード命令を実行した場合、その対象アドレスを、これまでロード命令の対象アドレスが格納されていない、空いているアドレスバッファ３１に格納していく。一方、他のプロセッサで、メモリ操作命令が実行されると、その対象アドレスは、プロセッサ毎に別のアドレス一致検出回路３５それぞれに入力される。
【０１８０】
各アドレス一致検出回路３５では、入力された前記対象アドレスが、すべてのアドレス比較器３２に入力され、アドレスバッファ３１に格納されている、自プロセッサで、それ以前に実行されたロード命令の対象アドレスと比較される。アドレス比較器３２から出力された比較結果は、すべて、論理和回路３３により論理和をとり、その結果を先行スレッド選択回路３４へ出力する。
【０１８１】
先行スレッド選択回路３４は、自プロセッサが投機実行状態にあり、かつ、自プロセッサが実行するスレッドよりも先行するスレッドを実行する他のプロセッサでストア命令が実行され、かつ、そのストア命令の対象アドレスを入力するアドレス一致検出回路３５で、アドレスの一致が検出された場合、データ依存が検出されたとして、データ依存検出結果４９を通じて、その旨をスレッド制御部５４へ出力する。この場合、スレッド投機実行が失敗したとして、スレッド制御部５４は、スレッド投機実行が失敗したことによる回復処理の制御を開始する。
【０１８２】
一方、先行スレッド選択回路３４は、自プロセッサが投機実行状態にあり、かつ、自プロセッサが実行するスレッドよりも先行するスレッドを実行する他のプロセッサでストア命令が実行され、かつ、そのストア命令の対象アドレスを入力するアドレス一致検出回路３５で、アドレスの一致が検出されなかった場合、データ依存が検出されなかったとして、データ依存検出結果４９を通じて、その旨をスレッド制御部５４へ出力する。この場合、スレッド投機実行が成功したとして、そのまま、スレッド実行を継続することができる。
【０１８３】
スレッド制御部５４は、プロセッサ５０〜５３のいずれかより、データ依存投機実行の失敗の通知を受け取ると、その失敗通知を出力したプロセッサ、および、その失敗通知を出力したプロセッサが実行していたスレッドよりも、プログラム順序で後に位置するスレッドを実行しているプロセッサに対して、データ依存投機実行の失敗による回復処理の実行要求を出力する。データ依存投機実行の失敗による回復処理の実行要求の出力対象となった各プロセッサでは、データ依存投機実行の失敗による回復処理の実行要求が、回復処理実行要求４７を通じて、プロセッサ制御部５６に通知される。
【０１８４】
データ依存投機実行の失敗を通知したプロセッサだけではなく、データ依存投機実行を失敗したスレッドよりプログラム順序が後のスレッドを実行しているプロセッサに対しても、データ依存投機実行の失敗による回復処理の実行を要求するのは、以下の理由による。
【０１８５】
すなわち、データ依存投機実行の失敗を通知したプロセッサは、正依存関係に違反して、ロード命令をデータ依存投機実行した可能性がある。そのため、データ依存投機実行の失敗を通知したプロセッサが実行していた、データ依存投機実行に失敗したスレッドの実行結果は、正しくない可能性がある。従って、データ依存投機実行に失敗したスレッドの実行結果を参照している可能性のある、それよりもプログラム順序で後に位置するスレッドの実行結果もまた、正しくない可能性がある。
【０１８６】
同様に、データ依存投機実行に失敗したスレッドの実行結果を参照している可能性のある上記スレッドの実行結果を参照している可能性のある、それよりも、さらにプログラム順序で後に位置するスレッドの実行結果もまた、正しくない可能性がある。
【０１８７】
すなわち、データ依存投機実行の失敗を通知したプロセッサが実行していたスレッドよりも、プログラム順序が後に位置するすべてのスレッドの実行結果は正しくない可能性がある。このため、データ依存投機実行の失敗を通知したプロセッサだけでなく、データ依存投機実行に失敗したスレッドよりプログラム順序が後のスレッドを実行しているプロセッサに対しても、データ依存投機実行の失敗による回復処理の実行を要求し、スレッドの実行結果の正しさを保証する。
【０１８８】
一方、投機実行の失敗による回復処理の実行要求の対象になったプロセッサでは、投機実行を行ったスレッドの再実行するなど、データ依存投機実行の失敗による回復処理を実行することで、スレッドの実行結果の正しさを保証する。
【０１８９】
上述したように、各プロセッサが備えるデータ依存関係検出装置５７は、自プロセッサが実行するスレッドよりプログラム順序で先行するスレッドに含まれるストア命令から、自プロセッサが実行するスレッドに含まれるロード命令への正依存関係を検出する機能を有する。この機能は、データ依存関係検出装置５７が、自プロセッサがロード命令をデータ依存投機実行する際に書き込みを行うポートを備えるとともに、他のプロセッサがストア命令を実行する際に読み出し、およびアドレス比較を行う複数のポートを備えることで実現される。そして、この機能により、スレッド並列処理において、スレッド単位のデータ依存投機実行の実現を可能とすることで、スレッド単位の並列実行による、プログラム実行のさらなる高速化が可能となる。
【０１９０】
データ依存投機制御装置５５は、スレッド単位のデータ依存投機実行において、ロード命令を投機的に実行するに際し、過去のスレッドの投機実行の成否結果の履歴を参照して、投機実行の成否を予測し、成功すると予測した場合には、投機的にスレッドを実行する。しかし、失敗すると予測した場合には、投機実行を中止し、後に、プログラム順序で確定的にスレッド実行するよう制御を行う機能を提供する。
【０１９１】
データ依存投機制御装置５５は、図６に示すように、４つのハッシュ関数回路５９、投機実行成否履歴テーブル５８から構成される。また、４つのプロセッサ５０〜５３からの入力として、これら４つのプロセッサ５０〜５３それぞれに対応する４つの実行命令４５、対象アドレス４６、および、データ依存検出結果４９を入力する。
【０１９２】
データ依存投機制御装置５５は、スレッド制御部５４からの入力として、４つのプロセッサ５０〜５３それぞれに対応する４つの投機実行フラグ４０を入力する。さらに、４つのプロセッサ５０〜５３への出力として、４つのプロセッサ５０〜５３それぞれに対応する４つのデータ投機実行成否予測結果４８を出力する。
【０１９３】
４つのハッシュ関数回路５９は、メモリ操作命令の対象アドレスを、投棄実行成否履歴テーブル５８のエントリ番号に変換する、ハッシュ関数ｆを実現する論理回路である。ここで、ハッシュ関数ｆは、同一の入力に対しては、同一の値を持つことを特徴とする。すなわち、Ｎ１＝ｆ（Ａ１）、かつ、Ｎ２＝ｆ（Ａ２）としたとき、Ａ１＝Ａ２であれば、Ｎ１＝Ｎ２が成立する関数である。
【０１９４】
４つのハッシュ関数回路５９は、それぞれプロセッサ５０〜５３に割り当てられ、それぞれ対応するプロセッサが実行するメモリ操作命令の対象アドレスを、投棄実行成否履歴テーブル５８のエントリ番号に変換する。投機実行成否履歴テーブル５８は、３ビットの情報を格納できるメモリやフリップフロップなどの記憶手段で実現された、複数のエントリから構成される。備えるエントリの総数は、そのハッシュ関数回路の出力がｎビット幅である場合、２のｎ乗に等しい数である。
【０１９５】
投機実行成否履歴テーブル５８は、ハッシュ関数回路５９が出力するエントリ番号が指し示すエントリに対して、書き込みおよび読み出し処理を行う、４つの読み出し・書き込みポートを備える。すなわち、４つの読み出し処理、あるいは書き込み処理を、独立、かつ同時に行うことができる。
【０１９６】
次に、スレッド並列処理におけるスレッドの投機実行に関して、各プロセッサ５０〜５３における、自プロセッサに発行された命令に対する動作、および他のプロセッサに発行された命令に対する動作を説明する。
【０１９７】
図８は、自プロセッサに発行された命令に対する自プロセッサ、およびデータ依存投機制御装置５５の動作手順を示すフローチャートである。なお、図中、ブロック１１５は、他プロセッサにおける処理を説明するために示してある。
【０１９８】
自プロセッサに発行された命令に対する動作は、図８のブロック１００で開始され、ブロック１０８で終了する。まず、ブロック１０１において、プロセッサ制御部５６より発行された命令がロード命令と判断された場合、ブロック１０２へ分岐し、ロード命令以外の場合には、ブロック１１３へ分岐する。発行命令は、プロセッサ制御部５６が出力する実行命令４５により与えられる。
【０１９９】
ブロック１０２において、自プロセッサがスレッドの投機実行状態にある場合は、ブロック１０３へ分岐し、確定実行状態にある場合は、ブロック１１１へ分岐する。投機的であるか、あるいは確定的であるかは、スレッド制御部５４が出力する投機実行フラグ４０により与えられる。そして、自プロセッサが投機実行状態にある場合、ブロック１０３において、データ依存投機制御装置５５により、投機実行が成功するか、失敗するかの予測を行う。
【０２００】
ここで、投機実行が“成功”することを予測した場合は、ブロック１０５へ進み、“失敗”することを予測した場合には、ブロック１０９へ分岐する。すなわち、投機実行が“成功”することを予測した場合、ブロック１０５において、そのロード命令を投機的に実行する。次のブロック１０６において、ロード命令を投機実行した旨を、自プロセッサのデータ依存関係検出装置５７に記憶する。
【０２０１】
ブロック１０７において、投機実行を行ったという事実により、データ依存投機制御装置５５に記憶されている投機実行成否結果を更新し、続くブロック１０８において、ロード命令の投機的な実行が終了する。
【０２０２】
一方、ブロック１０４において、ロード命令の投機実行が“失敗”することを予測した場合、ブロック１０９において、そのロード命令の投機的な実行を中止する。このロード命令、および、このロード命令よりも後続の命令は、後に、自プロセッサよりも先行するスレッドの実行がすべて完了した後、プログラム順序で確定的に実行される。
【０２０３】
ブロック１１０では、投機実行を行わなかったという事実により、データ依存投機制御装置５５に記憶されている投機実行成否結果を更新し、ブロック１０８において、今回のロード命令の実行を、中止により、とりあえず終了する。
【０２０４】
ブロック１０２において、自プロセッサが確定実行状態にあると判断された場合、ブロック１１１において、そのロード命令を確定的に実行する。次のブロック１１２において、確定的に実行を行ったという事実により、データ依存投機制御装置５５に記憶されている投機実行成否結果を更新し、ブロック１０８において、ロード命令の実行が終了する。
【０２０５】
ブロック１１３では、自プロセッサに発行された命令が、ストア命令である場合は、ブロック１１４に分岐し、発行された命令がロード命令でも、ストア命令でもない場合は、ブロック１１９に分岐する。すなわち、発行された命令がストア命令である場合、ブロック１１４において、そのストア命令を実行する。さらに、ブロック１１５において、自プロセッサが実行するスレッドよりも後続のスレッドを実行するプロセッサにおいて、各プロセッサのデータ依存関係検出装置５７により、そのストア命令に関する投機実行の成否判定が行われる。
【０２０６】
他プロセッサでの成否判定の結果により、ブロック１１６において、投機実行の失敗が検出されなかった場合は、ブロック１１７に分岐し、投機実行の失敗が検出された場合は、ブロック１１８に分岐する。他プロセッサにおける投機実行の成否判定の結果は、データ依存投機制御装置５５において、データ依存検出結果４９を通じて、参照することができる。
【０２０７】
他プロセッサで、投機実行の失敗が検出されなかった場合、ブロック１１７において、投機実行が成功したという事実により、データ依存投機制御装置５５に記憶されている投機実行成否結果を更新し、ブロック１０８において、本動作を終了する。しかし、他プロセッサで、投機実行の失敗が検出された場合には、ブロック１１８において、投機実行が失敗したという事実により、データ依存投機制御装置５５に記憶されている投機実行成否結果を更新し、ブロック１０８において、本動作を終了する。
【０２０８】
一方、ブロック１１３において、発行された命令がロード命令でも、ストア命令でもない場合は、ブロック１１９で命令を実行し、ブロック１０８において終了する。この場合、データ依存投機制御装置５５は、動作を行わない。
【０２０９】
再び、図６を参照して、データ依存投機制御装置５５の詳細な動作を説明する。まず、図８に示したフローチャート内のブロック１０３において、投機実行成否履歴テーブル５８に記憶されている投機実行の成否予測結果の履歴を参照し、それに基づいて、ロード命令の投機実行が成功するか、失敗するかの予測を行う。より詳細には、各プロセッサのプロセッサ制御部５６から、対象アドレス４６により与えられるロード命令の対象アドレスを、ハッシュ関数回路５９により、投機実行成否履歴テーブル５８のエントリ番号に変換し、それを投機実行成否履歴テーブル５８に入力する。投機実行成否履歴テーブル５８は、入力されたエントリ番号に対応するエントリの内容を読み出し、それに基づいて、上記ロード命令の投機実行の成否を予測する。
【０２１０】
図８のブロック１０７，１１０，１１２，１１７，１１８では、それぞれの実行フローに基づいて、投機実行成否履歴テーブル５８に記憶されている投機実行についての成否予測結果の履歴の更新を行う。より詳細には、各プロセッサのプロセッサ制御部５６から、対象アドレス４６により与えられるロード・ストア命令の対象アドレスを、ハッシュ関数回路５９により、投機実行成否履歴テーブル５８のエントリ番号に変換し、それを投機実行成否履歴テーブル５８に入力する。
【０２１１】
投機実行成否履歴テーブル５８は、入力されたエントリ番号に対応するエントリの内容を読み出し、そのエントリ内容とそれぞれの実行フローに基づいて、前記エントリ内容を更新する。なお、投機実行成否履歴テーブル５８の各エントリの状態遷移は、図３に示す、実施の形態１に係る投機実行成否履歴テーブル１２と同じである。
【０２１２】
本実施の形態の場合、同図中のロード命令は、自プロセッサが実行するロード命令、同図中のストア命令は、自プロセッサよりも先行するスレッドに含まれる、他プロセッサが実行するストア命令に対応する。
【０２１３】
投機実行成否履歴テーブル５８の各エントリは、図３に示すように、それぞれ３ビットの記憶素子から構成される。なお、これら３ビットで表される８つの投機実行成否履歴状態は、上記実施の形態１と同じであるため、ここでは、その説明を省略する。
【０２１４】
スレッド並列処理における投機的な命令実行において、図８に示すフローチャート上のブロック１０３における投機実行の成否予測は、参照したエントリが、上記の８状態のいずれにあるかで決定する。すなわち、エントリが“強い成功０”、“強い成功１”、”弱い成功０”、“弱い成功１”のいずれかにある場合は、投機実行が成功する可能性が高いと予測して、ロード命令を投機的に実行する。
【０２１５】
エントリが、“強い失敗０”、“強い失敗１”、“弱い失敗０”“弱い失敗０”のいずれかにある場合は、投機実行が失敗する可能性が高いと予測し、ロード命令の投機実行を中止し、後に、プログラム順序で、確定的に実行する。
【０２１６】
また、上記８状態間の状態遷移は、図８に示すブロック１０７，１１０，１１２，１１７，１１８において、以下のように行う。まず、初期状態では、すべてのエントリは、任意の状態にある。今、仮に、あるエントリが、“弱い成功０”９２にあるとする。このとき、そのエントリに対応するアドレスを対象とする投機的なロード命令を発行した場合、ブロック１０７において、エントリの状態を、“弱い成功１”９３へ遷移させる。
【０２１７】
この場合、ブロック１０３の投機実行の成否予測で、投機実行が成功すると予測されるため、実際にロード命令が投機実行されることになる（ブロック１０５）。なお、それ以外の実行フローの場合、すなわち、ブロック１１０，１１２，１１７，１１８では、エントリの状態は遷移しない。
【０２１８】
次に、エントリが、“弱い成功１”９３にある場合には、そのエントリに対応するアドレスを対象とするストア命令を、他プロセッサが実行し、自プロセッサのロード命令の、投機実行の失敗が検出されなかった場合は、ロード命令の投機実行が成功したとして、ブロック１１７において、エントリの状態を、“強い成功０”９０へ遷移させる。
【０２１９】
ロード命令の投機実行の失敗が検出された場合は、ロード命令の投機実行が失敗したとして、ブロック１１８において、エントリの状態を、“弱い失敗０”９４へ遷移させる。上記以外の実行フローの場合、すなわち、ブロック１０７，１１０，１１２では、エントリの状態は遷移しない。
【０２２０】
また、エントリが、“強い成功０”９０にあるときには、そのエントリに対応するアドレスを対象とする投機的なロード命令を発行した場合、ブロック１０７において、エントリの状態を、“強い成功１”９１へ遷移させる。この場合、ブロック１０３の投機実行の成否予測で、投機実行が成功すると予測されるため、実際に、ロード命令が投機実行されることになる（ブロック１０５）。それ以外の実行フローの場合、すなわち、ブロック１１０，１１２，１１７，１１８では、エントリの状態は遷移しない。
【０２２１】
次に、エントリが、“強い成功１”９１にある場合、そのエントリに対応するアドレスを対象とするストア命令を、他プロセッサが実行し、自プロセッサのロード命令の、投機実行の失敗が検出されなかった場合は、ロード命令の投機実行が成功したとして、ブロック１１７において、エントリの状態は、“強い成功０”９０に遷移する。
【０２２２】
ロード命令の投機実行の失敗が検出された場合は、ロード命令の投機実行が失敗したとして、ブロック１１８において、エントリの状態を、“弱い成功０”９２へ遷移させる。それ以外の実行フローの場合、すなわち、ブロック１０７，１１０，１１２では、エントリの状態は遷移しない。
【０２２３】
エントリが、“弱い失敗０”９４にあるときには、そのエントリに対応するアドレスを対象とする投機的なロード命令を発行した場合、ブロック１１０において、エントリの状態を、“弱い失敗１”９５へ遷移させる。この場合、ブロック１０３の投機実行の成否予測で、投機実行が失敗すると予測されるため、実際に、ロード命令が投機実行されることはない。なお、上記以外の実行フローの場合、すなわち、ブロック１０７，１１２，１１７，１１８では、エントリの状態は遷移しない。
【０２２４】
次に、エントリが、“弱い失敗１”９５にあるとき、そのエントリに対応するアドレスを対象とするストア命令を、他プロセッサが実行した場合、ロード命令の投機実行は、失敗する可能性が高いとして、ブロック１１７、またはブロック１１８において、エントリの状態を、“強い失敗１”９６へ遷移させる。この場合、ロード命令の投機実行は、失敗する可能性が高いと判断する理由は、“弱い失敗０”９４から投機的なロードが発行されて、“弱い失敗１”９５に遷移し、かつ、同アドレスのストア命令が実行されたからである。
【０２２５】
実際には、ブロック１０３において、投機実行は失敗すると予測されるため、投機実行は中止され、確定的に実行されるが、仮に、ロード命令を投機実行していたならば、その投機実行は失敗することになる。
【０２２６】
一方、エントリが、“弱い失敗１”９５にあるとき、そのエントリに対応するアドレスを対象とする確定的なロード命令が発行された場合、ロード命令の投機実行は、成功する可能性が高いとして、ブロック１１０において、エントリの状態を、“弱い成功０”９２へ遷移させる。この場合、ロード命令の投機実行は、成功する可能性が高いと判断する理由は、“弱い失敗０”９４から投機的なロードが発行されて、“弱い失敗１”９５に遷移し、かつ、同アドレスのストア命令が実行されずに、確定的なロード命令が発行されたからである。
【０２２７】
この確定的なロード命令は、ブロック１０３において、投機実行が失敗すると予測されて、確定的に実行されたロード命令と考えられ、かつ、その間に、同アドレスのストア命令が発行されなかったので、仮に、ロード命令を投機実行していたならば、その投機実行は、成功していたことになる。なお、上記以外の実行フローの場合、すなわち、ブロック１０７，１１２では、エントリの状態は遷移しない。
【０２２８】
エントリが、“強い失敗０”９６にあるときは、そのエントリに対応するアドレスを対象とする投機的なロード命令を発行した場合、ブロック１１０において、エントリの状態を、“強い失敗１”９７へ遷移させる。この場合、ブロック１０３の投機実行の成否予測で、投機実行が失敗すると予測されるため、実際に、ロード命令が投機実行されることはない。上記以外の実行フローの場合（ブロック１０７，１１２，１１７，１１８）では、エントリの状態は遷移しない。
【０２２９】
エントリが、“強い失敗１”９７にあるときに、そのエントリに対応するアドレスを対象とするストア命令を、他プロセッサが実行した場合、ロード命令の投機実行は、失敗する可能性が高いとして、ブロック１１７、またはブロック１１８において、エントリの状態は、“強い失敗０”９６に遷移する。
【０２３０】
上記の場合に、ロード命令の投機実行は、失敗する可能性が高いと判断する理由は、“強い失敗０”９６から投機的なロードが発行されて、“強い失敗１”９７に遷移し、かつ、同アドレスのストア命令が実行されたからである。実際には、ブロック１０３において、投機実行は、失敗すると予測されるため、投機実行は中止され、確定的に実行される。しかし、仮に、ロード命令を投機実行していたならば、その投機実行は、失敗することになる。
【０２３１】
エントリが、“強い失敗１”９７にあるとき、そのエントリに対応するアドレスを対象とする確定的なロード命令が発行された場合、ロード命令の投機実行は、成功する可能性が高いとして、ブロック１１０において、エントリの状態を、“弱い失敗０”９４へ遷移させる。この場合、ロード命令の投機実行は、成功する可能性が高いと判断する理由は、“強い失敗０”９６から投機的なロードが発行されて、“強い失敗１”９７に遷移し、かつ、同アドレスのストア命令が実行されずに、確定的なロード命令が発行されたからである。
【０２３２】
上記の確定的なロード命令は、ブロック１０３において、投機実行が失敗すると予測されて、確定的に実行されたロード命令と考えられ、かつ、その間に、同アドレスのストア命令が発行されなかったので、仮に、ロード命令を投機実行していたならば、その投機実行は、成功していたことになる。なお、上記以外の実行フローの場合、すなわち、ブロック１０７，１１２では、エントリの状態は遷移しない。
【０２３３】
以上、投機実行成否履歴テーブル５８の各エントリ内容の状態遷移を説明したが、ここでも、投機実行が成功する確率が高ければ、“強い失敗”、“弱い失敗”から“弱い成功”、“強い成功”へ、また、投機実行が失敗する確率が高ければ、“強い成功”、“弱い成功”から“弱い失敗”、“強い失敗”へと遷移して行く。
【０２３４】
ブロック１０３における投機実行の成否予測では、“弱い成功”、“強い成功”にあれば成功すると予測して、ロード命令の投機実行するが、“強い失敗”、“弱い失敗”にあれば失敗すると予測して、ロード命令の投機実行を中止し、後に、プログラム順序で確定的に実行する。すなわち、本実施の形態に係るデータ依存投機制御装置５５では、スレッド並列処理における、スレッド間の正依存関係に対する投機実行に関しても、失敗する確率の高い投機実行は、確定的に実行される。そのため、投機実行が失敗する確率が低減され、プログラムの実行性能が向上する。
【０２３５】
次に、本実施の形態２に係る、スレッド並列処理におけるデータ依存投機実行の具体例を説明する。図９は、プログラム例における、命令のプログラム順序を示す。このプログラム例は、ロード命令ＬＤ１，ＬＤ２，ＬＤ３，ＬＤ４，ＬＤ５，ストア命令ＳＴ１，ＳＴ２，ＳＴ３、および、ロード・ストア命令以外の命令を含む１６命令からなるプログラムの部分列が繰り返される、ループ構造を持つプログラムの典型的な例である。
【０２３６】
図９において、ループ０〜１という、連続する２つのループに含まれる命令列のみを示す。また、図中、空欄の四角は、ロード・ストア命令以外の命令を示す。ループ内のプログラム順序は、順に、ロード命令ＬＤ１、ロード・ストア命令以外の命令が２つ、ストア命令ＳＴ１、ロード・ストア命令以外の命令、ロード命令ＬＤ２、ストア命令ＳＴ２、ロード・ストア命令以外の命令が３つ、ロード命令ＬＤ３、ロード命令ＬＤ４、ロード命令ＬＤ５、ストア命令ＳＴ３、ロード・ストア命令以外の命令が２つの順序である。
【０２３７】
ここで、ＬＤ１の対象アドレスはＡ１、ＬＤ２の対象アドレスはＡ２、ＬＤ３の対象アドレスはＡ３、ＬＤ４の対象アドレスはＡ４、ＬＤ５の対象アドレスはＡ５、ＳＴ１の対象アドレスはＡ３、ＳＴ２の対象アドレスはＡ１、そして、ＳＴ３の対象アドレスはＡ３である。
【０２３８】
ここでは、図９に示すプロクラム順序のプログラム例を、図６に示す４つのプロセッサ（プロセッサ５０，５１，５２，５３）において、スレッド単位でデータ依存投機実行する。具体的には、図９に示す１６命令から構成されるループを、４命令から構成される４つのスレッドに分割し、それぞれを、４つのプロセッサで並列実行する。
【０２３９】
すなわち、プログラム順序で、順に、ロード命令ＬＤ１、ロード・ストア命令以外の命令が２つ、そして、ストア命令ＳＴ１という４命令列をスレッド０とし、ロード・ストア命令以外の命令、ロード命令ＬＤ２、ストア命令ＳＴ２、ロード・ストア命令以外の命令の４命令列をスレッド１とし、ロード・ストア命令以外の命令が２つ、ロード命令ＬＤ３、ロード命令ＬＤ４の４命令列をスレッド２とし、ロード命令ＬＤ５、ストア命令ＳＴ３、ロード・ストア命令以外の命令が２つという４命令列をスレッド３として、スレッド０をプロセッサ５２で、スレッド１をプロセッサ５１で、スレッド２をプロセッサ５０で、スレッド３をプロセッサ５３で並列に実行する。なお、各プロセッサが実行するスレッドの割り当ては、スレッド制御部５４によって行われる。
【０２４０】
上記の場合、スレッド０〜３を構成する命令間に、依存関係が存在しなければ、４つのプロセッサによるスレッド並列処理により、１６命令を４サイクルで実行することができる。しかし、ＬＤ３とＳＴ１の対象アドレスは、同じＡ３であり、プログラム順序でＳＴ１の方が前にあるため、ＳＴ１からＬＤ３には、データ依存関係が存在する。
【０２４１】
すなわち、実行時において、ＬＤ３よりもＳＴ１が前に実行されて、ＳＴ１がアドレスＡ３に書き込みを行った結果を、ＬＤ３がアドレスＡ３から読み出さなければ、プログラムの実行結果の正しさは保証されない。スレッド単位の並列処理においては、ＳＴ１を含むスレッド０からＬＤ３を含むスレッド２へ、正依存関係が存在することになる。
【０２４２】
しかしながら、通常、各プロセッサへスレッドを割り当てる時点では、ＳＴ１からＬＤ３への正依存関係、すなわち、スレッド０からスレッド２への存在は判明しない。このため、確定的にスレッドの並列実行をすると、正依存関係が無いことが判明していないスレッド間では、プログラム順序で、スレッドを逐次、実行することで、正依存関係を保証する必要がある。そのため、スレッドの並列処理によるプログラム実行の高速性を充分、得ることができない。
【０２４３】
スレッド単位のデータ依存投機実行では、スレッド間の正依存関係の存在の有無が判明していなくても、投機的にスレッドの並列実行をする。データ依存投機実行が成功する確率が充分、高ければ、スレッドの並列処理によるプログラム実行の高速化が達成される。
【０２４４】
図１０の（ａ）は、図９に示すプログラム順序の命令列、スレッド列のデータ依存投機実行によるスレッド並列実行の例であり、左から順に、サイクル番号、スレッド２を実行するプロセッサ５０のそのサイクルの実行命令、その実行命令の対象アドレス、スレッド１を実行するプロセッサ５１のそのサイクルの実行命令、その実行命令の対象アドレス、スレッド０を実行するプロセッサ５２のそのサイクルの実行命令、その実行命令の対象アドレス、スレッド３を実行するプロセッサ５３のそのサイクルの実行命令、その実行命令の対象アドレスである。
【０２４５】
すなわち、スレッド２を実行するプロセッサ５０では、１サイクル目、および２サイクル目にロード・ストア命令以外の命令、３サイクル目にＬＤ３、４サイクル目にＬＤ４が実行される。スレッド１を実行するプロセッサ５１では、１サイクル目にロード・ストア命令以外の命令、２サイクル目にＬＤ２、３サイクル目にＳＴ２、４サイクル目にロード・ストア命令以外の命令が実行される。
【０２４６】
スレッド０を実行するプロセッサ５２では、１サイクル目にＬＤ１、２サイクル目にロード・ストア命令以外の命令、３サイクル目にロード・ストア命令以外の命令、４サイクル目にＳＴ１が実行される。スレッド３を実行するプロセッサ５３では、１サイクル目にＬＤ５、２サイクル目にＳＴ３、３サイクル目、および４サイクル目にロード・ストア命令以外の命令が実行される。
【０２４７】
ここで、スレッド０は、プログラム順序で最も前に位置するスレッドであるため、スレッド１〜３に含まれるストア命令からスレッド０に含まれるロード命令への、正依存関係は存在しない。すなわち、プロセッサ５２は、確定的にスレッド０を実行することができる。
【０２４８】
一方、スレッド１〜３に関しては、正依存関係の有無が不明であるため、プロセッサ５０、プロセッサ５１、およびプロセッサ５３は、スレッド１〜３をデータ依存投機実行することになる。図１０の（ａ）に示す例では、仮に、データ依存投機実行が成功した場合、１６命令からなるプログラムが、４サイクルで実行されることになり、大幅なプログラム実行性能の向上が達成される。
【０２４９】
しかしながら、図１０の（ａ）における、ループ０に示す実行例の場合、正依存関係のあるＳＴ１，ＬＤ３について、ＬＤ３が、３サイクル目にプロセッサ５０で実行され、ＳＴ１が、４サイクル目にプロセッサ５２で実行される。そのため、正依存関係が保証されておらず、正しいプログラムの実行結果が得られない。
【０２５０】
換言すれば、プロセッサ５０におけるスレッド２のデータ依存投機実行は、失敗している。プロセッサ５０の備えるデータ依存関係検出装置５７は、プロセッサ５２が実行したＳＴ１から、プロセッサ５０が実行したＬＤ３への、正依存関係の存在を検出し、スレッド２のデータ依存投機実行が失敗したことを、スレッド制御部５４に通知する機能を担う。
【０２５１】
スレッド制御部５４は、プロセッサ５０より、データ依存投機実行が失敗した旨を通知されると、正しいプログラムの実行結果が得られるように、プロセッサ５０、およびデータ依存投機実行が失敗したスレッド２より、プログラム順序で後に位置するスレッド３を実行するプロセッサ５３に対して、スレッドの実行結果の取り消しやスレッドの再実行など、データ依存投機実行失敗による回復処理を要求する。
【０２５２】
図１０の（ｂ）は、データ依存投機制御装置５５の動作を示す図である。同図において、左から順に、サイクル番号、プロセッサ毎のそのサイクルにアクセスした投機実行成否履歴テーブル５８のエントリ番号、そのサイクルの投機実行成否履歴テーブル５８の状態をそれぞれ示す。プロセッサ毎のアクセスしたエントリ番号は、左から順に、プロセッサ５０、プロセッサ５１、プロセッサ５２、プロセッサ５３がアクセスしたエントリ番号を示している。
【０２５３】
投機実行成否履歴テーブル５８は、４つのエントリから構成されるとして、４つのエントリの状態を、右から順に、エントリ０、エントリ１、エントリ２、エントリ３の内容を示している。例えば、ループ０の１サイクル目においては、すべてのエントリの内容は、“０１０”（弱い成功０）である。
【０２５４】
ループ０の１サイクル目では、プロセッサ５０において、スレッド２に含まれるロード・ストア命令以外の命令、プロセッサ５１において、スレッド１に含まれるロード・ストア命令以外の命令、プロセッサ５２において、スレッド０に含まれるＬＤ１、プロセッサ５３において、スレッド３に含まれるＬＤ５が発行される。ここで、プロセッサ５３に発行されたＬＤ５は、プロセッサ５３で実行するスレッド３よりも先行するスレッド、すなわち、スレッド０、スレッド１、スレッド２が含むストア命令からの正依存関係の有無が不明である。従って、ＬＤ５は、正依存関係に関して、投機的に実行することを試みる。
【０２５５】
まず、投機実行に先立ち、プロセッサ５３は、データ依存投機制御装置５５により、投機実行の成否予測を行う（図８のブロック１０３）。より詳細には、まず、ＬＤ５のアドレスＡ５を、ハッシュ関数回路５９により投機実行成否履歴テーブル５８のエントリ番号に変換する。今、エントリ番号１に変換されたとすると、次に、投機実行成否履歴テーブル５８より、エントリ１に格納されている成否予測履歴“０１０”（弱い成功０）が読み出される。従って、投機実行が成功することが予測されるので、ＬＤ５は、投機的に実行される（図８のブロック１０５）。
【０２５６】
一方、プロセッサ５２で実行されるスレッド０は、最も先行するスレッドであるため、ＬＤ１は、プロセッサ５２において、確定的に実行される（図８のブロック１１１）。ここで、ＬＤ１の対象アドレスＡ１は、ハッシュ関数回路５９により、投機実行成否履歴テーブル５８のエントリ番号１に変換されるとすると、投機実行成否履歴テーブル５８のエントリ１は、プロセッサ５２、およびプロセッサ５３から同時にアクセスされる。
【０２５７】
しかし、データ依存投機制御装置５５は、プロセッサ毎に独立した４つのポートを備えているため、プロセッサ５２、およびプロセッサ５３からの処理を同時に実行することができる。この場合、プロセッサ５３が投機的にＬＤ５を実行したため、エントリ１の内容は、“０１１”（弱い成功１）に遷移する。
【０２５８】
次に、ループ０の２サイクル目では、プロセッサ５０において、スレッド２に含まれるロード・ストア命令以外の命令、プロセッサ５１において、スレッド１に含まれるＬＤ２、プロセッサ５２において、スレッド０に含まれるロード・ストア命令以外の命令、プロセッサ５３において、スレッド３に含まれるＳＴ３が実行される。
【０２５９】
ここで、プロセッサ５１に発行されたＬＤ２は、プロセッサ５１で実行するスレッド１よりも先行するスレッド０が含むストア命令に対して、投機的であるため、プロセッサ５１は、データ依存投機制御装置５５により、投機実行の成否予測を行う（図８のブロック１０３）。より詳細には、まず、ＬＤ２のアドレスＡ２を、ハッシュ関数回路５９により、投機実行成否履歴テーブル５８のエントリ番号に変換する。
【０２６０】
ここで、エントリ番号２に変換されたとすると、次に、投機実行成否履歴テーブル５８より、エントリ２に格納されている成否予測履歴“０１０”（弱い成功０）が読み出される。従って、投機実行が成功することが予測されるので、ＬＤ２は、投機的に実行される（図８のブロック１０５）。この場合、エントリ２の内容は、“０１１”（弱い成功１）に遷移する（図８のブロック１０７）。
【０２６１】
一方、プロセッサ５３で実行されるＳＴ３に関しては、プロセッサ５３以外の３つのプロセッサ５０〜５２が実行するスレッドは、いずれも、プロセッサ５３が実行するスレッド３に先行するので、ＳＴ３により、投機実行失敗は検出されず、投機実行成否履歴テーブル５８のエントリ３の内容は、“０１０”（弱い成功０）のまま、遷移しない（図８のブロック１１７）。
【０２６２】
ループ０の３サイクル目では、プロセッサ５０において、スレッド２に含まれるＬＤ３、プロセッサ５１において、スレッド１に含まれるＳＴ２、プロセッサ５２において、スレッド０に含まれるロード・ストア命令以外の命令、プロセッサ５３において、スレッド３に含まれるロード・ストア命令以外の命令が実行される。
【０２６３】
ここで、プロセッサ５０に発行されたＬＤ３は、プロセッサ５０で実行するスレッド２よりも先行する、スレッド０、およびスレッド１が含むストア命令に対して、投機的であるため、プロセッサ５０は、データ依存投機制御装置５５により、投機実行の成否予測を行う（図８のブロック１０３）。より詳細には、まず、ＬＤ３のアドレスＡ３を、ハッシュ関数回路５９により、投機実行成否履歴テーブル５８のエントリ番号に変換する。
【０２６４】
ここで、エントリ番号３に変換されたとすると、次に、投機実行成否履歴テーブル５８より、エントリ３に格納されている成否予測履歴“０１０”（弱い成功０）が読み出される。従って、投機実行が成功することが予測されるので、ＬＤ３は、投機的に実行される（図８のブロック１０５）。この場合、エントリ３の内容は、“０１１”（弱い成功１）に遷移する（図８のブロック１０７）。
【０２６５】
プロセッサ５１で実行されるＳＴ２に対しては、ＳＴ２が含まれるスレッド１よりも後続のスレッド２を実行するプロセッサ５０、およびスレッド３を実行するプロセッサ５３において、各々のプロセッサが備えるデータ依存関係検出装置５７により、投機実行の成否判定が行われる（図８のブロック１１５）。この場合、いずれのプロセッサにおいても、投機実行失敗が検出されないため、ＳＴ２に関しては、投機実行が成功したとして、投機実行成否履歴テーブル５８のエントリ１は、“０００”（強い成功０）へ遷移する（図８のブロック１１７）。
【０２６６】
次に、ループ０の４サイクル目では、プロセッサ５０において、スレッド２に含まれるＬＤ４、プロセッサ５１において、スレッド１に含まれるロード・ストア命令以外の命令、プロセッサ５２において、スレッド０に含まれるＳＴ１、プロセッサ５３において、スレッド３に含まれるロード・ストア命令以外の命令が実行される。ここで、プロセッサ５０に発行されたＬＤ４は、プロセッサ５０で実行するスレッド２よりも先行するスレッド０、およびスレッド１が含むストア命令に対して投機的であるため、プロセッサ５０は、データ依存投機制御装置５５により、投機実行の成否予測を行う（図８のブロック１０３）。
【０２６７】
より詳細には、まず、ＬＤ４のアドレスＡ４を、ハッシュ関数回路５９により投機実行成否履歴テーブル５８のエントリ番号に変換する。ここで、エントリ番号０に変換されたとすると、次に、投機実行成否履歴テーブル５８より、エントリ０に格納されている成否予測履歴“０１０”（弱い成功０）が読み出される。従って、投機実行が成功することが予測されるので、ＬＤ４は、投機的に実行される（図８のブロック１０５）。なお、この場合、エントリ０の内容は、“０１１”（弱い成功１）に遷移する（図８のブロック１０７）。
【０２６８】
他方、プロセッサ５２で実行されるＳＴ１に対しては、ＳＴ１が含まれるスレッド０よりも後続のスレッド１を実行するプロセッサ５１、スレッド２を実行するプロセッサ５０、およびスレッド３を実行するプロセッサ５３において、各々のプロセッサが備えるデータ依存関係検出装置５７により、投機実行の成否判定が行われる（図８のブロック１１５）。
【０２６９】
この場合、ＳＴ１と対象アドレスが同じＡ３であるＬＤ３が、プロセッサ５０において、ＳＴ１よりも先のサイクル３で投機的に実行されており、かつ、ＬＤ３は、ＳＴ１よりもプログラム順序で後にあるため、このＬＤ３の投機実行は、失敗していることが、プロセッサ５０の備えるデータ依存関係検出装置５７により検出され、それが、データ依存検出結果４９を通じて、スレッド制御部５４に通知される。この通知により、スレッド制御部５４は、正しいプログラムの実行結果が得られるように、プロセッサ５０、およびプロセッサ５０よりも後続のスレッドを実行していたプロセッサ５３に対して、データ依存投機実行の失敗による回復処理の実行を指示する。
【０２７０】
回復処理を実行するプロセッサ５０、およびプロセッサ５３では、１サイクル目から４サイクル目までに実行した命令の実行結果を取り消し、６サイクル目からスレッドを再度、実行する。
【０２７１】
一方、投機実行成否履歴テーブル５８においては、４サイクル目に、ＳＴ１に関して投機実行の失敗が検出されたことにより、エントリ３は、“１００”（弱い失敗０）に遷移する（図８のブロック１１８）。
【０２７２】
プロセッサ５０における、スレッド２の投機実行失敗による回復処理は、プロセッサ５０において、６サイクル目にロード・ストア命令以外の命令、７サイクル目にロード・ストア命令以外の命令、８サイクル目にＬＤ３、９サイクル目にＬＤ４が再実行される。この回復処理による、スレッド２の再実行においては、スレッド２が最も先行するスレッドであるため、確定的な実行が可能である。
【０２７３】
プロセッサ５３における、スレッド３の投機実行失敗による回復処理は、６サイクル目にＬＤ５、７サイクル目にＳＴ３、８サイクル目にロード・ストア命令以外の命令、９サイクル目にロード・ストア命令以外の命令が実行される。この回復処理によるスレッド３の再実行においては、スレッド２との依存関係が不明であるため、スレッド３は、再び投機的に実行する。
【０２７４】
スレッド３の回復処理における、投機実行に関する投機実行成否履歴テーブル５８の動作の詳細を、以下に説明する。まず、６サイクル目において、ＬＤ５に対して、プロセッサ５３は、データ依存投機制御装置５５により、投機実行の成否予測を行う（図８のブロック１０３）。投機実行成否履歴テーブル５８のエントリ１からは、“０００”（強い成功０）が読み出される。従って、投機実行が成功することが予測されるので、ＬＤ５は、投機的に実行される（図８のブロック１０５）。この場合、エントリ１の内容は、“００１”（強い成功１）に遷移する（図８のブロック１０７）。
【０２７５】
次に、７サイクル目において、ＳＴ３が実行される。投機実行成否履歴テーブル５８のエントリ３は、“１００”（弱い失敗０）のまま遷移しない。
【０２７６】
以上が、ループ０における命令実行、およびデータ依存投機制御装置５５の動作である。ここでは、スレッド２に含まれるＬＤ３の投機実行の成否予測は、成功を予測したのに対して、実際には、投機実行は失敗し、スレッド２、および、それより後続のスレッド３の投機実行失敗による回復処理の実行が必要となった。このため、ループ０においては、スレッド０〜３の１６命令を、プロセッサ５０〜５３で実行するのに、９サイクルを要した。
【０２７７】
次に、ループ０に続くループ１における動作を説明する。ループ１の１サイクル目では、プロセッサ５０において、スレッド２に含まれるロード・ストア命令以外の命令、プロセッサ５１において、スレッド１に含まれるロード・ストア命令以外の命令、プロセッサ５２において、スレッド０に含まれるＬＤ１、プロセッサ５３において、スレッド３に含まれるＬＤ５が発行される。ここで、プロセッサ５３に発行されたＬＤ５は、プロセッサ５３で実行するスレッド３よりも先行するスレッド、すなわち、スレッド０、スレッド１、スレッド２が含むストア命令からの正依存関係の有無が不明である。従って、ＬＤ５は、正依存関係に関して投機的に実行することを試みる。
【０２７８】
まず、投機実行に先立ち、プロセッサ５３は、データ依存投機制御装置５５により、投機実行の成否予測を行う（図８のブロック１０３）。投機実行成否履歴テーブル５８のエントリ１からは、“００１”（強い成功１）が読み出される。従って、投機実行が成功することが予測されるので、ＬＤ５は、投機的に実行される（図８のブロック１０５）。
【０２７９】
一方、プロセッサ５２で実行されるスレッド０は、最も先行するスレッドであるため、ＬＤ１は、プロセッサ５２において、確定的に実行される（図８のブロック１１１）。投機実行成否履歴テーブル５８のエントリ１は、“００１”（強い成功１）のまま遷移しない。
【０２８０】
次に、ループ１の２サイクル目では、プロセッサ５０において、スレッド２に含まれるロード・ストア命令以外の命令、プロセッサ５１において、スレッド１に含まれるＬＤ２、プロセッサ５２において、スレッド０に含まれるロード・ストア命令以外の命令、プロセッサ５３において、スレッド３に含まれるＳＴ３が実行される。
【０２８１】
ここで、プロセッサ５１に発行されたＬＤ２は、プロセッサ５１で実行するスレッド１よりも先行するスレッド０が含むストア命令に対して、投機的であるため、プロセッサ５１は、データ依存投機制御装置５５により、投機実行の成否予測を行う（図８のブロック１０３）。投機実行成否履歴テーブル５８のエントリ２からは、“０１１”（弱い成功１）が読み出される。
【０２８２】
従って、投機実行が成功することが予測されるので、ＬＤ２は、投機的に実行される（図８のブロック１０５）。この場合、エントリ２は、“０１１”（弱い成功１）のまま遷移しない（図８のブロック１０７）。
【０２８３】
一方、プロセッサ５３で実行されるＳＴ３に関しては、プロセッサ５３以外の３つのプロセッサ５０〜５２が実行するスレッドは、いずれも、プロセッサ５３が実行するスレッド３に先行するので、ＳＴ３による投機実行の失敗は、検出されなお。投機実行成否履歴テーブル５８より、エントリ３の内容は、“１００”（弱い失敗０）のまま遷移しない（図８のブロック１１７）。
【０２８４】
ループ１の３サイクル目では、プロセッサ５０において、スレッド２に含まれるＬＤ３、プロセッサ５１において、スレッド１に含まれるＳＴ２、プロセッサ５２において、スレッド０に含まれるロード・ストア命令以外の命令、プロセッサ５３において、スレッド３に含まれるロード・ストア命令以外の命令が実行される。ここで、プロセッサ５０に発行されたＬＤ３は、プロセッサ５０で実行するスレッド２よりも先行するスレッド０、およびスレッド１が含むストア命令に対して、投機的である。そのため、プロセッサ５０は、データ依存投機制御装置５５により、投機実行の成否予測を行う（図８のブロック１０３）。
【０２８５】
投機実行成否履歴テーブル５８のエントリ３からは、“１００”（弱い失敗０）が読み出されるので、投機実行が失敗することが予測される。従って、ＬＤ３の投機的な実行は中止され、後に、プログラム順序で、確定的に実行される（図８のブロック１０９）。この場合、エントリ３の内容は、“１０１”（弱い失敗１）に遷移する（図８のブロック１１０）。
【０２８６】
プロセッサ５１で実行されるＳＴ２に対しては、ＳＴ２が含まれるスレッド１よりも後続のスレッド２を実行するプロセッサ５０、およびスレッド３を実行するプロセッサ５３において、各々のプロセッサが備えるデータ依存関係検出装置５７により、投機実行の成否判定が行われる（図８のブロック１１５）。この場合、いずれのプロセッサにおいても、投機実行失敗が検出されないため、ＳＴ２に関しては、投機実行が成功したとして、投機実行成否履歴テーブル５８のエントリ１は、“０００”（強い成功０）へ遷移する（図８のブロック１１７）。
【０２８７】
ループ１の４サイクル目において、スレッド２を実行するプロセッサ５０では、スレッド２よりもプログラム順序で先行するスレッド０、およびスレッド１の実行がまだ完了していないため、３サイクル目に投機実行が中止されたＬＤ３を、それらスレッド０、およびスレッド１との依存関係に関して、確定的に実行することはできない。そのため、ＬＤ３の実行は待機となる。
【０２８８】
一方、プロセッサ５１では、スレッド１に含まれるロード・ストア命令以外の命令、プロセッサ５２では、スレッド０に含まれるＳＴ１、プロセッサ５３では、スレッド３に含まれるロード・ストア命令以外の命令が実行される。プロセッサ５２で実行されるＳＴ１に対しては、ＳＴ１が含まれるスレッド０よりも後続のスレッド１を実行するプロセッサ５１、スレッド２を実行するプロセッサ５０、およびスレッド３を実行するプロセッサ５３において、各々のプロセッサが備えるデータ依存関係検出装置５７により、投機実行の成否判定が行われる（図８のブロック１１５）。
【０２８９】
ループ０の場合と異なり、ループ１では、ＬＤ３の投機実行が中止されているため、ＳＴ１に関して、投機実行の失敗は検出されない。従って、スレッド０、スレッド１およびスレッド３の実行は、４サイクル目で完了する。また、ＳＴ１に関して、投機実行成否履歴テーブル５８のエントリ３は、“１１０”（強い失敗０）に遷移する（図８のブロック１１７）。
【０２９０】
ループ１の５サイクル目では、プロセッサ５０において、３サイクル目に投機実行が失敗することが予測されて、実行が延期されていたＬＤ３の確定的な実行が可能になる。そのため、ＬＤ３が確定的に実行される。ループ１の６サイクル目では、プロセッサ５０において、ＬＤ４が確定的に実行される。
【０２９１】
上述したように、本実施の形態２に係るデータ依存投機制御装置５５は、マルチプロセッサシステムによるスレッド並列処理において、投機実行が失敗すると予測されるロード命令は、投機実行を行わずにプログラム順序で確定的に実行する。その結果、投機実行が失敗する確率が低減され、プログラムの実行性能が向上する。
【０２９２】
すなわち、ループ１における命令実行、およびデータ依存投機制御装置の動作において、スレッド２に含まれるＬＤ３の投機実行の成否予測は、正しく失敗を予測したことで、ＬＤ３の投機実行の失敗が回避される。そのため、ループ０においては、スレッド０〜３の１６命令を、プロセッサ５０〜５３で実行するのに９サイクルを要したのに対して、ループ１では６サイクルに改善された。
【０２９３】
かかるデータ依存投機制御装置５５によれば、マルチプロセッサシステム上のスレッド並列処理において、スレッド単位のデータ依存投機実行するに際して、過去の命令の、投機実行の成否結果の履歴を参照して、投機実行の成否を予測し、成功すると予測した場合には、投機的に命令を実行するが、失敗すると予測した場合、その投機実行を中止し、後に、プログラム順序で、確定的にスレッド実行する。よって、このデータ依存投機制御装置５５によれば、マルチプロセッサシステムにおけるスレッド並列処理において、失敗する確率の高い命令の投機実行は確定的に実行されるため、投機実行が失敗する確率が低減され、プログラムの実行性能を大幅に向上させることができる。
【０２９４】
具体的には、１６命令からなるプログラム例に対して、４つのプロセッサでスレッド並列処理を行うと、データ依存投機実行が失敗するループ０の場合で９サイクル、投機実行の成否予測が成功するループ１では、６サイクルで実行が完了し、プログラムの実行性能は大幅に向上する。かかる例では、説明のため各スレッドを４命令構成としたが、通常、数十命令から数万命令で構成されるので、より多くのロード命令がデータ依存投機実行されることになる。そのため、本実施の形態に係るデータ依存投機制御装置５５は、実際の使用場面においては、その性能向上により大きな効果を奏すると考えられる。
【０２９５】
さらに、本実施の形態に係るデータ依存投機制御装置５５は、投機実行の成否予測を行うに際して、ロード・ストア命令の対象アドレスに関して、エイリアスの存在を許容することで、対象アドレスそのものをすべて記憶することが不要になる。これにより、投機実行の成否予測が可能なロード命令数に制限がなく、必要なハードウエア量も小さく、少ないハードウエア量でも、データ依存投機実行による実行性能の向上を享受することができる。
【０２９６】
また、投機実行の成否予測を行うに際して、ロード・ストア命令間の対象アドレスの比較を必要とせず、参照される投機実行成否履歴テーブル５８のエントリは、高々１つなので、投機実行の成否予測の処理時間が短い。このため、プロセッサの動作周波数を高速化することが容易である。
【０２９７】
さらに、本実施の形態に係るデータ依存投機制御装置５５は、スレッド制御部５４が出力するスレッド順序４０に基づいて、正依存検出する対象のスレッドを選択する機能を有する。そのため、スレッド間の順序に柔軟に対応して、スレッド間の正依存関係を適切に検出できる、という効果を奏する。
【０２９８】
【発明の効果】
以上説明したように、本発明に係るデータ依存投機制御装置によれば、データ依存投機実行時において、過去における投機実行の成否結果の履歴を参照して、投機実行の成否を予測し、成功すると予測した場合には投機的に実行するが、失敗すると予測した場合には、投機実行を中止し、後にプログラム順序で確定的に実行する。すなわち、プロセッサがメモリ操作命令の実行する際に、データ投機実行が成功するか失敗するかを予測し、成功が予測される場合には、メモリ操作命令を非プログラム順序でデータ依存に関して投機的に実行し、失敗が予測される場合には、メモリ操作命令をプログラム順序で確定的に実行する。そのため、本データ依存投機制御装置は、過去の投機実行の成否履歴を記憶した記憶手段を含み、データ依存投機実行の成否予測は、過去の投機実行の成否結果に基づいて実行される。
【０２９９】
かかる構成により、データ依存投機実行が失敗すると予測されるメモリ操作命令、つまり、失敗する確率の高い投機実行は、プログラム順序で確定的に実行されるため、データ依存投機実行が失敗する確率が低減するだけでなく、過去のデータ依存投機実行の予測結果をもとに、高精度な成否予測ができる。その結果、プログラムの実行性能が向上するという効果がある。換言すれば、本発明における上記の効果は、以下の理由による。
【０３００】
（１）データ依存投機実行が失敗した場合、その回復処理のために、プログラム順序で確定的に実行するよりも実行性能が低下する場合が多い。すなわち、データ依存投機実行を行って失敗するならば、データ依存投機実行を行わずに、プログラム順序で確定的に実行する方が、実行性能が高い。
【０３０１】
（２）一般に、プログラム中でデータ依存投機実行に失敗する場合の多いメモリ操作命令は、再び失敗する確率が高く、逆に、プログラム中でデータ依存投機実行に成功する場合の多いメモリ操作命令は、再び成功する確率が高いという性質がある。すなわち、本発明の成否予測は、過去のデータ依存投機実行の予測結果を基づくものである。
【０３０２】
また、他の発明に係る、複数のプロセッサから構成され、スレッド単位で並列処理を行うマルチプロセッサシステムでのスレッド並列処理においても、スレッド単位のデータ依存投機実行するに際して、過去における命令の投機実行の成否結果の履歴を参照して、投機実行の成否を予測し、成功すると予測した場合は、投機的に命令を実行するが、失敗すると予測した場合には、投機実行を中止し、後にプログラム順序で確定的にスレッド実行する。
【０３０３】
つまり、各プロセッサが、スレッド間の命令に関して非プログラム順序で、データ依存に関して投機的にメモリ操作命令の実行する際、データ投機実行が成功するか失敗するかを予測し、成功が予測される場合、メモリ操作命令を非プログラム順序でデータ依存投機的に実行し、失敗が予測される場合には、メモリ操作命令をプログラム順序で確定的に実行する。
【０３０４】
ここでも、データ依存投機実行の成否予測は、過去の投機実行の成否結果に基づいて実行され、このような構成とすることで、失敗する確率の高い命令の投機実行は、確定的に実行される。そのため、マルチプロセッサシステムによるスレッド並列処理においても、投機実行が失敗する確率が低減され、プログラムの実行性能を向上することができる。
【０３０５】
また、本発明に係るデータ依存投機制御装置によれば、投機成否予測に際して、ロード命令の対象アドレスは、例えば、ハッシュ関数回路により、投機実行成否履歴テーブル（成否履歴記憶手段）の特定のエントリに重複を許して割り当てるため、実行されたロード命令の対象アドレス自体をすべて記憶しておく必要がない。また、ストア命令の対象アドレスと比較するためのアドレス比較器も不要となる。よって、投機実行の成否予測に必要なハーウェア量が小さくなる。
【０３０６】
さらに、投機実行の成否予測をすることのできるロード命令の数が、データ依存投機制御装置のハーウェア量に制限されないため、少ないハーウェア量でも、データ依存投機実行による実行性能を向上できる。また、投機実行の成否予測に際し、ロード・ストア命令の対象アドレス間の比較が不要であり、投機実行成否履歴テーブル（成否履歴記憶手段）から読み出すエントリは、高々１つであるため、成否予測の処理時間が短くなり、プロセッサの動作周波数の高速化が容易になる。
【図面の簡単な説明】
【図１】本発明の実施の形態１に係るデータ依存投機制御装置を含むプロセッサの構成を示すブロック図である。
【図２】図１に示すプロセッサによる命令実行の手順を示すフローチャートである。
【図３】実施の形態１に係る投機実行成否履歴テーブルの各エントリ内容の状態遷移を示す状態遷移図である。
【図４】実施の形態１に係るデータ依存投機制御装置の具体的な動作例を説明するための図である。
【図５】実施の形態１に係るデータ依存投機制御装置が備えるハッシュ関数回路を示す図である。
【図６】本発明の実施の形態２に係るデータ依存投機制御装置の構成を示すブロック図である。
【図７】図６のデータ依存関係検出装置の一構成を示すブロック図である。
【図８】実施の形態２に係るデータ依存投機制御装置の動作手順を示すフローチャートである。
【図９】データ依存投機制御装置の具体的動作例を示す図である。
【図１０】データ依存投機制御装置の具体的動作例を示す図である。
【図１１】データ依存投機実行の動作を説明するための図である。
【図１２】ロード・ストア命令間の正依存関係を検出する、従来のデータ依存関係検出装置を備えるプロセッサの構成を示すブロック図である。
【符号の説明】
１０  データ依存投機制御装置
１１  ハッシュ関数回路
１２  投機実行成否履歴テーブル
１３  投機実行フラグ
１４  対象アドレス
１５  実行命令
２０  プロセッサ制御部
２１  命令実行部
３０  データ依存関係検出装置
３１  アドレスバッファ
３２  アドレス比較器
３３  論理和回路
３４  先行スレッド選択回路
３５  アドレス一致検出回路
４０  投機実行フラグ
５０，５１，５２，５３  プロセッサ
５４  スレッド制御部
５５  データ依存投機制御装置
５６  プロセッサ制御部
５７  データ依存関係検出装置
５８  投棄実行成否履歴テーブル
５９  ハッシュ関数回路
【図１】
0003729087.tif 000002
【図２】
0003729087.tif 000003
【図３】
0003729087.tif 000004
【図４】
0003729087.tif 000005
【図５】
0003729087.tif 000006
【図６】
0003729087.tif 000007
【図７】
0003729087.tif 000008
【図８】
0003729087.tif 000009
【図９】
0003729087.tif 000010
【図１０】
0003729087.tif 000011
【図１１】
0003729087.tif 000012
【図１２】
0003729087.tif 000013