プロセッサ及びプリフェッチ制御方法
【課題】本来の処理命令の実行に対する影響を抑えつつ、複数のキャッシュブロックを転送する。
【解決手段】本プロセッサは、実行ユニットとキャッシュとキャッシュブロックを主記憶からキャッシュに転送する主記憶制御部とキャッシュブロックの転送指示を主記憶制御部に出力するマルチブロックプリフェッチ制御部とを有する。そして、実行ユニットは、プログラム内の所定の処理の前に挿入された第1prefetch開始命令を実行し、プリフェッチ対象領域情報を含む第2prefetch開始命令をマルチブロックプリフェッチ制御部に出力する。また、マルチブロックプリフェッチ制御部は、第2prefetch開始命令を受信した場合、当該命令に含まれるプリフェッチ対象領域情報とキャッシュブロックの大きさとに基づき、転送すべき複数のキャッシュブロックを特定し、複数のキャッシュブロックを所定の処理の実行時間内で転送するようにスケジューリングし、転送指示を出力する。
【解決手段】本プロセッサは、実行ユニットとキャッシュとキャッシュブロックを主記憶からキャッシュに転送する主記憶制御部とキャッシュブロックの転送指示を主記憶制御部に出力するマルチブロックプリフェッチ制御部とを有する。そして、実行ユニットは、プログラム内の所定の処理の前に挿入された第1prefetch開始命令を実行し、プリフェッチ対象領域情報を含む第2prefetch開始命令をマルチブロックプリフェッチ制御部に出力する。また、マルチブロックプリフェッチ制御部は、第2prefetch開始命令を受信した場合、当該命令に含まれるプリフェッチ対象領域情報とキャッシュブロックの大きさとに基づき、転送すべき複数のキャッシュブロックを特定し、複数のキャッシュブロックを所定の処理の実行時間内で転送するようにスケジューリングし、転送指示を出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プロセッサにおけるプリフェッチ制御技術に関する。
【背景技術】
【０００２】
近年、プロセッサ（例えばＣＰＵ：Central Processing Unit）の処理速度が向上しつつある。一方で、主記憶装置（メインメモリとも呼ぶ）の性能がプロセッサに追いついておらず、例えば、処理に必要なデータがプロセッサ内部のキャッシュメモリに存在しない場合には、プロセッサは、そのデータが主記憶装置から転送されるのを待たなくてはならない。従って、プロセッサの処理速度が向上しても、システム全体としては処理速度がそれほど向上しないという問題がある。
【０００３】
この問題を解決するための技術として、主記憶装置からキャッシュメモリにデータを事前に読み出しておく、プリフェッチと呼ばれる技術が存在する。プリフェッチには、プロセッサが、必要になると思われるデータを自動的に予測し、主記憶装置から読み出すハードウェアプリフェッチと、プログラム内に挿入されたプリフェッチ命令に従って、指定されたデータを主記憶装置から読み出すソフトウェアプリフェッチとがある。
【０００４】
例えば、図１に示すようなプログラムに対し、従来技術によりプリフェッチを実装する場合の例を説明する。
【０００５】
図１において、行１０１は、double型の二次元配列Ａを定義しており、二次元配列Ａの１次元目の配列の要素数はＩＭＡＸ、２次元目の配列の要素数はＬＥＮとなっている。なお、二次元配列Ａの各要素は、Ａ[ｉ][ｋ]で表される（ｉ及びｋは、配列のインデックスを表す変数であり、０≦ｉ＜ＩＭＡＸ、０≦ｋ＜ＬＥＮである）。また、図１において、ループ１０２は、ｉを０からＩＭＡＸ−１まで変化させるループとなっている。さらに、ループ１０３は、ループ１０２内のループであり、ｋを０からＪＭＡＸ−１まで変化させるループとなっている。そして、ループ１０３内には、主要処理１０４が含まれる。なお、主要処理１０４は、二次元配列Ａを参照する処理となっている。
【０００６】
図２に、図１に示したプログラムを実行した際の処理を時系列に並べた例を示す。図２では、ｉ＝０の場合に、主要処理１０４でＡ[０][０]からＡ[０][ＬＥＮ−１]までのデータ（図２では、これらのデータをまとめてＡ[０][＊]と示す）を参照することを表す。また、ｉ＝１の場合に、主要処理１０４でＡ[１][０]からＡ[１][ＬＥＮ−１]までのデータ（図２では、これらのデータをまとめてＡ[１][＊]と示す）を参照し、ｉ＝２の場合に、主要処理１０４でＡ[２][０]からＡ[２][ＬＥＮ−１]までのデータ（図２では、これらのデータをまとめてＡ[２][＊]と示す）を参照することを表す。例えば、プリフェッチがなされていないと、ｉ＝０の処理からｉ＝１の処理に移行する際に、ｉ＝１の処理で参照するＡ[１][＊]（すなわち、Ａ[１][０]〜Ａ[１][ＬＥＮ−１]）のデータを主記憶装置からキャッシュメモリに転送しなければならず、プロセッサが待たされることになる。一方で、ｉ＝０の処理の際に、ｉ＝１の処理で参照するであろうＡ[１][＊]（すなわち、Ａ[１][０]〜Ａ[１][ＬＥＮ−１]）のデータをプリフェッチしておけば、プロセッサが待たされることなく、次の処理に移行できる。すなわち、ｉの処理の際に、Ａ[ｉ＋１][＊]（すなわち、Ａ[ｉ＋１][０]〜Ａ[ｉ＋１][ＬＥＮ−１]）のデータをプリフェッチすればよい。
【０００７】
上記ようなプリフェッチをソフトウェアプリフェッチで実装する場合の例を図３に示す。図３の例では、図１に示したプログラムのループ１０３内にプリフェッチ命令３０１が挿入されている。プリフェッチ命令３０１は、引数で指定されたアドレスを含むキャッシュブロックをプリフェッチさせる命令である。なお、キャッシュブロックとは、予め所定のサイズに区画された領域であり、キャッシュブロック単位で主記憶からキャッシュメモリに転送される。このように、プログラム内にプリフェッチ命令３０１を挿入することで、プリフェッチさせることが可能となる。
【０００８】
しかし、図３のように、ループ１０３内にプリフェッチ命令３０１を挿入すると、プリフェッチ命令３０１がループ１０３のループ回数だけ（すなわち、ＪＭＡＸ回）実行されることになる。プリフェッチ命令もプロセッサの実行ユニットを使用するため、プリフェッチ命令の実行回数が多くなると、本来の処理命令の実行を妨げてしまう。また、キャッシュメモリは小容量のため、プリフェッチするデータ量が多すぎると、本来の処理命令で使用するはずのデータがキャッシュメモリから追い出されてしまう可能性もある。例えば、条件によってプリフェッチ命令１０３を実行させるか否かを判断させることは可能であるが、ループ１０３内に条件分岐命令を挿入しなければならず、かえって本来の処理命令の実行の妨げとなる。
【０００９】
また、１回のプリフェッチ命令３０１の実行につき、１キャッシュブロックを転送するため、逆に、ループ１０３のループ回数があまりにも少ないと（例えば、ループ回数が、転送すべきキャッシュブロックの数より小さい場合）、転送すべきキャッシュブロックを全て転送することができず、結果として、プロセッサが待たされることになる。
【００１０】
一方、ハードウェアプリフェッチは、上で述べたように、プロセッサが、必要になると思われるデータを予測し、そのデータを読み出すものであり、一定の範囲のデータをまとめて読み出すようにはなっていない。
【００１１】
また、プリフェッチに関する技術として、例えば、特開平０８−３１４８０２号公報記載の技術がある。具体的には、複数のライン（上記のキャッシュブロックに相当）のデータをキャッシュメモリに転送させる際、各ラインのデータがキャッシュメモリ内にあるか判断し、既にキャッシュメモリにデータが存在する場合には、不要なプリフェッチ要求を出さないようにするものである。しかし、キャッシュメモリにデータが存在しない場合には、複数のプリフェッチ要求を連続して出すことになるため、上記のような問題が生じる場合がある。
【００１２】
さらに、例えば、特開平０６−３２４９４２号公報には、システム全体の高速化を図る並列計算機システムが開示されている。具体的には、共有バスに共有メモリと複数のＣＰＵとを結合させた並列計算機システムにおいて、共有バスと共有メモリの間に共有メモリ上のデータの一部を格納して高速化を図るキャッシュメモリを備え、各ＣＰＵから共有メモリに対してアクセスが予想されるデータを予めキャッシュメモリに格納しておくことを特徴とする並列計算機システムが開示されている。しかし、複数のキャッシュブロックを転送するような場合については考慮されていない。
【００１３】
また、例えば、特開平０７−１２９４６４号公報には、主記憶装置とキャッシュメモリ間における情報の転送を制御する情報処理装置が開示されている。具体的には、実行すべき命令及び処理すべきデータに関する情報を格納する主記憶手段と、主記憶手段に格納された命令に従って、主記憶手段に格納されたデータを処理する命令処理手段と、主記憶手段に格納された情報の一部を格納するキャッシュメモリと、アプリケーションプログラムに応じたキャッシュメモリ制御情報を格納する制御情報記憶手段と、制御情報記憶手段に格納されたキャッシュメモリ制御情報に従って主記憶手段とキャッシュメモリ間における情報の転送を制御するメモリ制御手段とを備えている情報処理装置が開示されている。しかし、複数のキャッシュブロックを転送するような場合については考慮されていない。
【００１４】
さらに、例えば、特開２００４−３４８１７５号公報には、データのプリフェッチ命令に、そのデータの利用時刻に関する情報を付加し、前記利用時刻に関する情報をもとに前記プリフェッチ命令の発行タイミングをスケジュールすることを特徴とするプリフェッチ命令制御方法が開示されている。しかし、複数のキャッシュブロックを転送するような場合については考慮されていない。
【００１５】
また、例えば、特開２００３−２２３３５９号公報には、予めメインメモリからキャッシュメモリへデータを転送するように指示するプリフェッチ命令を動的に命令列中に挿入して実行する演算処理装置が開示されている。具体的には、キャッシュミスを起こす命令のうちプリフェッチ処理の対象とすべき命令を選択するプリフェッチ対象選択手段と、プリフェッチ対象選択手段によってプリフェッチ処理の対象とされた命令の実行時におけるメモリアクセスアドレスを予測するアドレス予測手段と、プリフェッチ対象選択手段によってプリフェッチ処理の対象とされた命令に対応するプリフェッチ命令の命令列中への挿入位置を決定するプリフェッチ命令挿入位置決定手段と、アドレス予測手段によって予測されたメモリアクセスアドレスをオペランドに有するプリフェッチ命令を、プリフェッチ命令挿入位置決定手段によって決定された挿入位置に、挿入するプリフェッチ命令挿入手段とを具備する演算処理装置が開示されている。しかし、複数のキャッシュブロックを転送するような場合については考慮されていない。
【特許文献１】特開平０８−３１４８０２号公報
【特許文献２】特開平０６−３２４９４２号公報
【特許文献３】特開平０７−１２９４６４号公報
【特許文献４】特開２００４−３４８１７５号公報
【特許文献５】特開２００３−２２３３５９号公報
【発明の開示】
【発明が解決しようとする課題】
【００１６】
上で述べたように、従来技術によれば、プリフェッチすべきデータが複数のキャッシュブロックに渡る場合でもプリフェッチすることが可能である。しかし、本来の処理命令の実行を妨げてしまい、システム全体の処理速度をかえって低下させる可能性がある。
【００１７】
従って、本発明の目的は、本来の処理命令の実行に対する影響を抑えつつ、複数のキャッシュブロックを主記憶装置からキャッシュメモリに転送するための技術を提供することである。
【課題を解決するための手段】
【００１８】
本発明に係るプロセッサは、プログラムを実行する実行ユニットと、キャッシュメモリと、所定の大きさのキャッシュブロックを主記憶からキャッシュメモリに転送する主記憶制御部と、キャッシュブロックの転送指示を主記憶制御部に出力するマルチブロックプリフェッチ制御部とを有する。そして、実行ユニットは、プログラム内の所定の処理の前に挿入された第１プリフェッチ開始命令を実行し、当該第１プリフェッチ開始命令に係るプリフェッチ対象領域の情報を含む第２プリフェッチ開始命令をマルチブロックプリフェッチ制御部に出力する。また、マルチブロックプリフェッチ制御部は、実行ユニットから第２プリフェッチ開始命令を受信した場合に、第２プリフェッチ開始命令に含まれるプリフェッチ対象領域の情報とキャッシュブロックの所定の大きさとに基づいて、転送すべき複数のキャッシュブロックを特定し、複数のキャッシュブロックを主記憶からキャッシュメモリに所定の処理の実行時間内で転送するようにスケジューリングし、転送指示を出力する。
【００１９】
例えば所定の間隔で転送指示を主記憶制御部に出力するようにすれば、本来の処理命令の実行に対する影響を抑えつつ、複数のキャッシュブロックを主記憶装置からキャッシュメモリに転送させることができる。また、従来、開発者は、プリフェッチ命令の数や挿入場所（例えば、何ステップ前に挿入するか等）を試行錯誤して探していたが、所定の処理（例えば、ループ処理）の前に第１プリフェッチ開始命令を挿入すれば良いので、従来の煩雑な作業が不要になる。
【００２０】
また、マルチブロックプリフェッチ制御部は、主記憶制御部における主記憶アクセス用リソースの使用状況を監視し、主記憶アクセス用リソースが空いている場合に、転送指示を出力するようにしてもよい。
【００２１】
さらに、実行ユニットは、プログラム内の所定の処理の後に挿入された第１プリフェッチ終了命令を実行し、第２プリフェッチ終了命令をマルチブロックプリフェッチ制御部に出力するようにしてもよい。また、マルチブロックプリフェッチ制御部は、実行ユニットから第２プリフェッチ終了命令を受信した場合に、第２プリフェッチ開始命令を受信してから第２プリフェッチ終了命令を受信するまでの時間と当該時間に対応する第１プリフェッチ開始命令を特定するための所定の情報とを実行履歴テーブルに格納するようにしてもよい。そして、マルチブロックプリフェッチ制御部は、実行履歴テーブルに格納された情報を基に所定の処理の実行時間を推定するようにしてもよい。例えば、前回の実行時間や過去数回の実行時間の平均時間を今回の実行時間とみなすことで、今回の実行時間を適切に推定することができる。
【００２２】
また、マルチブロックプリフェッチ制御部は、推定された、所定の処理の実行時間を基に複数のキャッシュブロックの転送間隔を算出し、当該転送間隔を基に転送指示の出力時間を特定するようにしてもよい。そして、マルチブロックプリフェッチ制御部は、出力時間に達した場合又は主記憶制御部における主記憶アクセス用のリソースが空いている場合に、転送指示を出力するようにしてもよい。このようにすれば、本来の処理命令の実行に対する影響を、より抑えることができる。
【００２３】
また、所定の処理が、第１プリフェッチ開始命令と第１プリフェッチ終了命令との間の処理を所定回数繰り返すループ処理である場合もある。
【発明の効果】
【００２４】
本発明によれば、本来の処理命令の実行に対する影響を抑えつつ、複数のキャッシュブロックを主記憶装置からキャッシュメモリに転送することができる。
【発明を実施するための最良の形態】
【００２５】
図４に本発明の一実施の形態に係るプロセッサ１の機能ブロック図を示す。本実施の形態に係るプロセッサ１は、キャッシュメモリ１３と、データやプログラム等をキャッシュメモリ１３から読み出し、命令を実行する実行ユニット１１と、実行ユニット１１からの指示に従って、複数のキャッシュブロックをキャッシュメモリ１３に転送するようにスケジューリングするマルチブロックプリフェッチ制御部１５と、実行ユニット１１の参照すべきデータがキャッシュメモリ１３に存在しない場合、又はマルチブロックプリフェッチ制御部１５からの転送指示を受信した場合に、主記憶３からキャッシュメモリ１３にデータを転送する主記憶制御部１７とを有する。なお、プロセッサ１と主記憶３とは、バスで接続されている。
【００２６】
さらに、マルチブロックプリフェッチ制御部１５は、プリフェッチ予定表１５１と実行履歴テーブル１５２とを含み、これらを用いて処理を行う。なお、プリフェッチ予定表１５１と実行履歴テーブル１５２については後で説明する。
【００２７】
図５に、図１に示したプログラムに対し、本発明を適用してプリフェッチを実装する場合のプログラムの一例を示す。図５の例では、従来のプリフェッチ命令３０１（図３）の代わりに、プリフェッチ開始命令（mb.prefetch.start命令）５０１がループ１０３の直前に挿入され、プリフェッチ終了命令（mb.prefetch.end命令）５０２がループ１０３の直後に挿入されている。プリフェッチ開始命令５０１では、プリフェッチ対象領域を指定するようになっている。なお、本実施の形態では、先頭アドレス及び末尾アドレスによって、プリフェッチ対象領域を指定するようになっている。図５の例では、Ａ[ｉ＋１][０]のアドレスを先頭アドレス、Ａ[ｉ＋２][０]のアドレスを末尾アドレスとして指定するようになっている。従って、例えば、ｉ＝１の場合は、Ａ[２][０]のアドレスを先頭アドレス、Ａ[３][０]のアドレスを末尾アドレスとしてプリフェッチ開始命令５０１が実行される。
【００２８】
図６乃至図１１を用いて、プロセッサ１がプリフェッチ開始命令５０１を実行した際の処理を説明する。まず、プロセッサ１の実行ユニット１１は、プリフェッチ開始命令５０１を実行し、プリフェッチ開始命令５０１で指定された先頭アドレスと末尾アドレスとを含むマルチブロックプリフェッチ開始命令をマルチブロックプリフェッチ制御部１５に出力する。また、実行ユニット１１は、プリフェッチ開始命令５０１の命令アドレスをマルチブロックプリフェッチ制御部１５に出力するようにする。マルチブロックプリフェッチ制御部１５は、先頭アドレスと末尾アドレスとを含むマルチブロックプリフェッチ開始命令を実行ユニット１１から受信し（図６：ステップＳ１）、内部に一旦格納する。このとき、プリフェッチ開始命令５０１の命令アドレス及びマルチブロックプリフェッチ開始命令の受信時刻も合わせて格納する。そして、マルチブロックプリフェッチ制御部１５は、先頭アドレスと末尾アドレスとをキャッシュブロックの境界にアライメントする（ステップＳ３）。この処理については、図７を用いて説明する。
【００２９】
図７は、キャッシュブロックのサイズが６４Ｂ（バイト）の際に、先頭アドレスとして0xa0000060、末尾アドレスとして0xa0000160が指定された場合の例を示す。上でも述べたが、主記憶３からキャッシュメモリ１３へのデータの転送は、キャッシュブロック単位で行われるため、先頭アドレス（0xa0000060）及び末尾アドレス（0xa0000160）をキャッシュブロックの境界と合わせる必要がある。キャッシュブロックのサイズが６４Ｂの場合であれば、例えば、以下の（１）及び（２）式によって、調整後の先頭アドレス及び末尾アドレスを算出することができる。なお、演算子「＆」は、ビットごとの論理積を求める演算子である。
（調整後先頭アドレス）＝ 0xffffffc0 ＆（先頭アドレス） （１）
（調整後末尾アドレス）＝ 0xffffffc0 ＆（末尾アドレス＋0x0000003f） （２）
図７の例では、（１）式により、調整後先頭アドレス（0xa0000040）が算出され、（２）式により、調整後末尾アドレス（0xa0000180）が算出される。
【００３０】
図６の説明に戻って、マルチブロックプリフェッチ制御部１５は、調整後先頭アドレスと調整後末尾アドレスとに基づきプリフェッチ対象ブロック数を算出する（ステップＳ５）。図７の例であれば、プリフェッチ対象ブロック数は５となる。そして、マルチブロックプリフェッチ制御部１５は、プリフェッチ開始命令５０１の命令アドレスをキーとして実行履歴テーブル１５２を検索し、経過時間を取得する（ステップＳ７）。
【００３１】
図８に、実行履歴テーブル１５２に格納されるデータの一例を示す。図８の例では、命令アドレスと経過時間とが格納されるようになっている。命令アドレスには、プリフェッチ開始命令５０１の命令アドレスが格納される。また、経過時間には、マルチブロックプリフェッチ開始命令を受信してから、後で述べるマルチブロックプリフェッチ終了命令を受信するまでの時間が格納される。従って、同一の命令アドレスのプリフェッチ開始命令５０１が過去に実行されている場合には、その際の実行時間を取得することができる。本実施の形態では、プリフェッチをいつまでに完了すべきかを同一処理の過去の実行時間から推定し、推定された時間内に、プリフェッチ対象ブロック数分のキャッシュブロックを転送するようにスケジューリングする。なお、同一の命令アドレスのプリフェッチ開始命令５０１が過去に実行されていない場合には（すなわち、実行履歴テーブル１５２に該当する経過時間が格納されていない場合には）、デフォルトの時間を使用する。
【００３２】
マルチブロックプリフェッチ制御部１５は、取得した経過時間とプリフェッチ対象ブロック数とに基づいてプリフェッチ間隔を算出する（ステップＳ９）。例えば、経過時間が５００、プリフェッチ対象ブロック数が５の場合には、プリフェッチ間隔は１００となる。そして、マルチブロックプリフェッチ制御部１５は、調整後先頭アドレスとプリフェッチ間隔とプリフェッチ対象ブロック数とを基にプリフェッチ予定表１５１を生成する（ステップＳ１１）。例えば、図９に示すようなプリフェッチ予定表が生成される。
【００３３】
図９の例では、プリフェッチアドレスとカウンタとプリフェッチ間隔と残ブロック数とが格納されるようになっている。プリフェッチアドレスには、初期値として調整後先頭アドレスが設定される。残ブロック数には、初期値としてプリフェッチ対象ブロック数が設定される。また、本実施の形態では、カウンタには、初期値として０を設定する。
【００３４】
そして、処理は端子Ａを介して図１０の処理に移行する。マルチブロックプリフェッチ制御部１５は、プリフェッチ予定表１５１の残ブロック数が０より大きいか判断する（図１０：ステップＳ１３）。もし、残ブロック数が０の場合（ステップＳ１３：Ｎｏルート）、処理を終了する。
【００３５】
一方、残ブロック数が０より大きい場合（ステップＳ１３：Ｙｅｓルート）、マルチブロックプリフェッチ制御部１５は、カウンタが０になったか判断する（ステップＳ１５）。なお、図示していないが、カウンタは、マルチブロックプリフェッチ制御部１５のタイマ等によって定期的にデクリメントされるものとする。カウンタがまだ０になっていない場合（ステップＳ１５：Ｎｏルート）、マルチブロックプリフェッチ制御部１５は、主記憶制御部１７における、主記憶にアクセスするためのリソースが空いているか判断する（ステップＳ１７）。もし、主記憶にアクセスするためのリソースが空いていない場合（ステップＳ１７：Ｎｏルート）、ステップＳ１３の処理に戻る。
【００３６】
一方、カウンタが０の場合（ステップＳ１５：Ｙｅｓルート）、又は主記憶にアクセスするためのリソースが空いている場合（ステップＳ１７：Ｙｅｓルート）、マルチブロックプリフェッチ制御部１５は、プリフェッチアドレスを含むプリフェッチ指示を主記憶制御部１７に出力する（ステップＳ１９）。
【００３７】
そして、マルチブロックプリフェッチ制御部１５は、プリフェッチ予定表１５１を更新する（ステップＳ２１）。例えば、図９に示したプリフェッチ予定表は、図１１に示すようなプリフェッチ予定表に更新される。図１１において、プリフェッチアドレスは、更新前のプリフェッチアドレス（0xa0000040）にキャッシュブロックのサイズ（６４Ｂ）分だけ加算され、次のキャッシュブロックを示すアドレス（0xa0000080）となっている。また、カウンタはプリフェッチ間隔の値でリセットされ、残ブロック数は１デクリメントされている。
【００３８】
以上のような処理を実施することにより、本来の処理命令に対する影響を抑えるように、複数のキャッシュブロックの転送をスケジューリングすることができる。
【００３９】
次に、図１２を用いて、プロセッサ１がプリフェッチ終了命令５０２を実行した際の処理を説明する。まず、プロセッサ１の実行ユニット１１は、プリフェッチ終了命令５０２を実行し、マルチブロックプリフェッチ終了命令をマルチブロックプリフェッチ制御部１５に出力する。マルチブロックプリフェッチ制御部１５は、マルチブロックプリフェッチ終了命令を実行ユニット１１から受信し（図１２：ステップＳ２３）、内部に一旦格納する。このとき、マルチブロックプリフェッチ終了命令の受信時刻も合わせて格納する。そして、マルチブロックプリフェッチ制御部１５は、プリフェッチ予定表１５１を削除する（ステップＳ２５）。なお、未転送のキャッシュブロックがある場合（すなわち、残ブロック数が１以上の場合）、プリフェッチをその時点で中止する。
【００４０】
そして、マルチブロックプリフェッチ制御部１５は、実行履歴を実行履歴テーブル１５２に格納する（ステップＳ２７）。具体的には、マルチブロックプリフェッチ制御部１５は、マルチブロックプリフェッチ開始命令の受信時刻とマルチブロックプリフェッチ終了命令の受信時刻との差を経過時間として実行履歴テーブル１５２に格納する。同時に、命令アドレスとしてプリフェッチ開始命令５０１の命令アドレスを格納する。
【００４１】
以上のような処理を実施することにより、複数のキャッシュブロックの転送をスケジューリングする際に必要となる実行時間を適切に推定することができるようになる。
【００４２】
以上本発明の実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、図４に示したプロセッサ１の機能ブロック図は一例であって、上で述べた機能を実現できれば図４の機能ブロック構成に限定されるわけではない。さらに、処理フローにおいても、処理結果が変らなければ処理の順番を入れ替えることも可能である。さらに、並列に実行させるようにしても良い。
【００４３】
また、プリフェッチ開始命令５０１では、先頭アドレスと末尾アドレスとを指定するようになっているが、先頭アドレスとプリフェッチ対象領域のサイズとを指定するようにしてもよい。この場合、ステップＳ３の処理の前に、先頭アドレスとプリフェッチ対象領域のサイズから末尾アドレスを算出すればよい。
【００４４】
また、例えば、プリフェッチ開始命令５０１の前に条件分岐命令を挿入し、条件によってプリフェッチ開始命令５０１を実行させるようなプログラムにしてもよい。例えば、プリフェッチ対象領域が大きすぎると、本来の処理命令で使用するはずのデータを追い出してしまい、処理速度をかえって低下させる可能性があるため、プリフェッチ対象領域が所定の大きさを超えるような場合にはプリフェッチ開始命令５０１を実行させないような条件分岐命令を挿入すればよい。なお、従来のプリフェッチ命令３０１（図３）はループ１０３内に挿入されるため、条件分岐命令もループ１０３内に挿入しなければならなかったが、本発明においては、プリフェッチ開始命令５０１がループ１０３外に挿入されるため、条件分岐命令もループ１０３外に挿入できる。すなわち、条件分岐命令を挿入したとしても、本来の処理命令の実行に対する影響は、従来に比べて少ない。
【００４５】
また、上で説明したテーブルの構成は一例であって、必ずしも上記のような構成でなければならないわけではない。例えば、実行履歴テーブル１５２において、前回の実行時間を取得できる構成であれば、命令アドレス以外の情報と対応付けて経過時間を格納することも可能である。また、実行ユニット１１が、プリフェッチ開始命令５０１を実行してからプリフェッチ終了命令５０２を実行するまでの時間を実行履歴テーブル１５２に格納するように構成することも可能である。
【００４６】
（付記１）
プログラムを実行する実行ユニットと、
キャッシュメモリと、
所定の大きさのキャッシュブロックを主記憶から前記キャッシュメモリに転送する主記憶制御部と、
前記キャッシュブロックの転送指示を前記主記憶制御部に出力するマルチブロックプリフェッチ制御部と、
を有し、
前記実行ユニットは、
前記プログラム内の所定の処理の前に挿入された第１プリフェッチ開始命令を実行し、当該第１プリフェッチ開始命令に係るプリフェッチ対象領域の情報を含む第２プリフェッチ開始命令を前記マルチブロックプリフェッチ制御部に出力し、
前記マルチブロックプリフェッチ制御部は、
前記実行ユニットから前記第２プリフェッチ開始命令を受信した場合に、前記第２プリフェッチ開始命令に含まれる前記プリフェッチ対象領域の情報と前記キャッシュブロックの前記所定の大きさとに基づいて、転送すべき複数のキャッシュブロックを特定し、
前記複数のキャッシュブロックを前記主記憶から前記キャッシュメモリに前記所定の処理の実行時間内で転送するようにスケジューリングし、前記転送指示を出力する
プロセッサ。
【００４７】
（付記２）
前記マルチブロックプリフェッチ制御部は、
前記主記憶制御部における主記憶アクセス用リソースの使用状況を監視し、前記主記憶アクセス用リソースが空いている場合に、前記転送指示を出力する
付記１記載のプロセッサ。
【００４８】
（付記３）
前記実行ユニットは、
前記プログラム内の所定の処理の後に挿入された第１プリフェッチ終了命令を実行し、第２プリフェッチ終了命令を前記マルチブロックプリフェッチ制御部に出力し、
前記マルチブロックプリフェッチ制御部は、
前記実行ユニットから前記第２プリフェッチ終了命令を受信した場合に、前記第２プリフェッチ開始命令を受信してから前記第２プリフェッチ終了命令を受信するまでの時間と当該時間に対応する前記第１プリフェッチ開始命令を特定するための所定の情報とを実行履歴テーブルに格納する
付記１記載のプロセッサ。
【００４９】
（付記４）
前記マルチブロックプリフェッチ制御部は、
前記実行履歴テーブルに格納された情報を基に前記所定の処理の実行時間を推定する
付記３記載のプロセッサ。
【００５０】
（付記５）
前記マルチブロックプリフェッチ制御部は、
推定された、前記所定の処理の実行時間を基に前記複数のキャッシュブロックの転送間隔を算出し、当該転送間隔を基に前記転送指示の出力時間を特定する
付記４記載のプロセッサ。
【００５１】
（付記６）
前記マルチブロックプリフェッチ制御部は、
前記複数のキャッシュブロックの転送間隔を算出し、当該転送間隔を基に前記転送指示の出力時間を特定する
付記１記載のプロセッサ。
【００５２】
（付記７）
前記マルチブロックプリフェッチ制御部は、
前記出力時間に達した場合又は前記主記憶制御部における主記憶アクセス用のリソースが空いている場合に、前記転送指示を出力する
付記５又は６記載のプロセッサ。
【００５３】
（付記８）
前記マルチブロックプリフェッチ制御部は、
前記転送指示を出力した後、前記複数のキャッシュブロックのうち未転送のキャッシュブロックがある場合には、前記転送間隔を基に次に出力すべき前記転送指示の出力時間を特定する
付記７記載のプロセッサ。
【００５４】
（付記９）
前記プリフェッチ対象領域の情報が、当該プリフェッチ対象領域の先頭アドレスと当該プリフェッチ対象領域の終了アドレス又はサイズとを含む
付記１記載のプロセッサ。
【００５５】
（付記１０）
前記所定の処理が、前記第１プリフェッチ開始命令と前記第１プリフェッチ終了命令との間の処理を所定回数繰り返すループ処理である
付記３記載のプロセッサ。
【００５６】
（付記１１）
プログラム内の所定の処理の前に挿入された第１プリフェッチ開始命令の実行時に実行ユニットから出力され、当該第１プリフェッチ開始命令に係るプリフェッチ対象領域の情報を含む第２プリフェッチ開始命令を受信した場合に、前記第２プリフェッチ開始命令に含まれる前記プリフェッチ対象領域の情報とキャッシュブロックのサイズとに基づいて、主記憶からキャッシュメモリに転送すべき複数のキャッシュブロックを特定するステップと、
前記複数のキャッシュブロックを前記主記憶から前記キャッシュメモリに前記所定の処理の実行時間内で転送するようにスケジューリングし、転送指示を主記憶制御部に出力するステップと、
を含む、プリフェッチ制御方法。
【図面の簡単な説明】
【００５７】
【図１】プリフェッチを必要とするプログラムの一例を示す図である。
【図２】図１に示したプログラムの処理とプリフェッチとの関係を時系列で表した図である。
【図３】従来技術によりプリフェッチを実装する場合のプログラムの一例を示す図である。
【図４】本発明の実施の形態におけるプロセッサの機能ブロック図を示す図である。
【図５】本発明を適用してプリフェッチを実装する場合のプログラムの一例を示す図である。
【図６】プリフェッチ開始命令を実行した際の処理フロー（第１の部分）を示す図である。
【図７】アドレスのアライメントを説明するための図である。
【図８】実行履歴テーブルに格納されるデータの一例を示す図である。
【図９】プリフェッチ予定表に格納されるデータの一例を示す図である。
【図１０】プリフェッチ開始命令を実行した際の処理フロー（第２の部分）を示す図である。
【図１１】更新後のプリフェッチ予定表に格納されるデータの一例を示す図である。
【図１２】プリフェッチ終了命令を実行した際の処理フローを示す図である。
【符号の説明】
【００５８】
１ プロセッサ ３ 主記憶
１１ 実行ユニット １３ キャッシュメモリ
１５ マルチブロックプリフェッチ制御部 １７ 主記憶制御部
１５１ プリフェッチ予定表 １５２ 実行履歴テーブル
【技術分野】
【０００１】
本発明は、プロセッサにおけるプリフェッチ制御技術に関する。
【背景技術】
【０００２】
近年、プロセッサ（例えばＣＰＵ：Central Processing Unit）の処理速度が向上しつつある。一方で、主記憶装置（メインメモリとも呼ぶ）の性能がプロセッサに追いついておらず、例えば、処理に必要なデータがプロセッサ内部のキャッシュメモリに存在しない場合には、プロセッサは、そのデータが主記憶装置から転送されるのを待たなくてはならない。従って、プロセッサの処理速度が向上しても、システム全体としては処理速度がそれほど向上しないという問題がある。
【０００３】
この問題を解決するための技術として、主記憶装置からキャッシュメモリにデータを事前に読み出しておく、プリフェッチと呼ばれる技術が存在する。プリフェッチには、プロセッサが、必要になると思われるデータを自動的に予測し、主記憶装置から読み出すハードウェアプリフェッチと、プログラム内に挿入されたプリフェッチ命令に従って、指定されたデータを主記憶装置から読み出すソフトウェアプリフェッチとがある。
【０００４】
例えば、図１に示すようなプログラムに対し、従来技術によりプリフェッチを実装する場合の例を説明する。
【０００５】
図１において、行１０１は、double型の二次元配列Ａを定義しており、二次元配列Ａの１次元目の配列の要素数はＩＭＡＸ、２次元目の配列の要素数はＬＥＮとなっている。なお、二次元配列Ａの各要素は、Ａ[ｉ][ｋ]で表される（ｉ及びｋは、配列のインデックスを表す変数であり、０≦ｉ＜ＩＭＡＸ、０≦ｋ＜ＬＥＮである）。また、図１において、ループ１０２は、ｉを０からＩＭＡＸ−１まで変化させるループとなっている。さらに、ループ１０３は、ループ１０２内のループであり、ｋを０からＪＭＡＸ−１まで変化させるループとなっている。そして、ループ１０３内には、主要処理１０４が含まれる。なお、主要処理１０４は、二次元配列Ａを参照する処理となっている。
【０００６】
図２に、図１に示したプログラムを実行した際の処理を時系列に並べた例を示す。図２では、ｉ＝０の場合に、主要処理１０４でＡ[０][０]からＡ[０][ＬＥＮ−１]までのデータ（図２では、これらのデータをまとめてＡ[０][＊]と示す）を参照することを表す。また、ｉ＝１の場合に、主要処理１０４でＡ[１][０]からＡ[１][ＬＥＮ−１]までのデータ（図２では、これらのデータをまとめてＡ[１][＊]と示す）を参照し、ｉ＝２の場合に、主要処理１０４でＡ[２][０]からＡ[２][ＬＥＮ−１]までのデータ（図２では、これらのデータをまとめてＡ[２][＊]と示す）を参照することを表す。例えば、プリフェッチがなされていないと、ｉ＝０の処理からｉ＝１の処理に移行する際に、ｉ＝１の処理で参照するＡ[１][＊]（すなわち、Ａ[１][０]〜Ａ[１][ＬＥＮ−１]）のデータを主記憶装置からキャッシュメモリに転送しなければならず、プロセッサが待たされることになる。一方で、ｉ＝０の処理の際に、ｉ＝１の処理で参照するであろうＡ[１][＊]（すなわち、Ａ[１][０]〜Ａ[１][ＬＥＮ−１]）のデータをプリフェッチしておけば、プロセッサが待たされることなく、次の処理に移行できる。すなわち、ｉの処理の際に、Ａ[ｉ＋１][＊]（すなわち、Ａ[ｉ＋１][０]〜Ａ[ｉ＋１][ＬＥＮ−１]）のデータをプリフェッチすればよい。
【０００７】
上記ようなプリフェッチをソフトウェアプリフェッチで実装する場合の例を図３に示す。図３の例では、図１に示したプログラムのループ１０３内にプリフェッチ命令３０１が挿入されている。プリフェッチ命令３０１は、引数で指定されたアドレスを含むキャッシュブロックをプリフェッチさせる命令である。なお、キャッシュブロックとは、予め所定のサイズに区画された領域であり、キャッシュブロック単位で主記憶からキャッシュメモリに転送される。このように、プログラム内にプリフェッチ命令３０１を挿入することで、プリフェッチさせることが可能となる。
【０００８】
しかし、図３のように、ループ１０３内にプリフェッチ命令３０１を挿入すると、プリフェッチ命令３０１がループ１０３のループ回数だけ（すなわち、ＪＭＡＸ回）実行されることになる。プリフェッチ命令もプロセッサの実行ユニットを使用するため、プリフェッチ命令の実行回数が多くなると、本来の処理命令の実行を妨げてしまう。また、キャッシュメモリは小容量のため、プリフェッチするデータ量が多すぎると、本来の処理命令で使用するはずのデータがキャッシュメモリから追い出されてしまう可能性もある。例えば、条件によってプリフェッチ命令１０３を実行させるか否かを判断させることは可能であるが、ループ１０３内に条件分岐命令を挿入しなければならず、かえって本来の処理命令の実行の妨げとなる。
【０００９】
また、１回のプリフェッチ命令３０１の実行につき、１キャッシュブロックを転送するため、逆に、ループ１０３のループ回数があまりにも少ないと（例えば、ループ回数が、転送すべきキャッシュブロックの数より小さい場合）、転送すべきキャッシュブロックを全て転送することができず、結果として、プロセッサが待たされることになる。
【００１０】
一方、ハードウェアプリフェッチは、上で述べたように、プロセッサが、必要になると思われるデータを予測し、そのデータを読み出すものであり、一定の範囲のデータをまとめて読み出すようにはなっていない。
【００１１】
また、プリフェッチに関する技術として、例えば、特開平０８−３１４８０２号公報記載の技術がある。具体的には、複数のライン（上記のキャッシュブロックに相当）のデータをキャッシュメモリに転送させる際、各ラインのデータがキャッシュメモリ内にあるか判断し、既にキャッシュメモリにデータが存在する場合には、不要なプリフェッチ要求を出さないようにするものである。しかし、キャッシュメモリにデータが存在しない場合には、複数のプリフェッチ要求を連続して出すことになるため、上記のような問題が生じる場合がある。
【００１２】
さらに、例えば、特開平０６−３２４９４２号公報には、システム全体の高速化を図る並列計算機システムが開示されている。具体的には、共有バスに共有メモリと複数のＣＰＵとを結合させた並列計算機システムにおいて、共有バスと共有メモリの間に共有メモリ上のデータの一部を格納して高速化を図るキャッシュメモリを備え、各ＣＰＵから共有メモリに対してアクセスが予想されるデータを予めキャッシュメモリに格納しておくことを特徴とする並列計算機システムが開示されている。しかし、複数のキャッシュブロックを転送するような場合については考慮されていない。
【００１３】
また、例えば、特開平０７−１２９４６４号公報には、主記憶装置とキャッシュメモリ間における情報の転送を制御する情報処理装置が開示されている。具体的には、実行すべき命令及び処理すべきデータに関する情報を格納する主記憶手段と、主記憶手段に格納された命令に従って、主記憶手段に格納されたデータを処理する命令処理手段と、主記憶手段に格納された情報の一部を格納するキャッシュメモリと、アプリケーションプログラムに応じたキャッシュメモリ制御情報を格納する制御情報記憶手段と、制御情報記憶手段に格納されたキャッシュメモリ制御情報に従って主記憶手段とキャッシュメモリ間における情報の転送を制御するメモリ制御手段とを備えている情報処理装置が開示されている。しかし、複数のキャッシュブロックを転送するような場合については考慮されていない。
【００１４】
さらに、例えば、特開２００４−３４８１７５号公報には、データのプリフェッチ命令に、そのデータの利用時刻に関する情報を付加し、前記利用時刻に関する情報をもとに前記プリフェッチ命令の発行タイミングをスケジュールすることを特徴とするプリフェッチ命令制御方法が開示されている。しかし、複数のキャッシュブロックを転送するような場合については考慮されていない。
【００１５】
また、例えば、特開２００３−２２３３５９号公報には、予めメインメモリからキャッシュメモリへデータを転送するように指示するプリフェッチ命令を動的に命令列中に挿入して実行する演算処理装置が開示されている。具体的には、キャッシュミスを起こす命令のうちプリフェッチ処理の対象とすべき命令を選択するプリフェッチ対象選択手段と、プリフェッチ対象選択手段によってプリフェッチ処理の対象とされた命令の実行時におけるメモリアクセスアドレスを予測するアドレス予測手段と、プリフェッチ対象選択手段によってプリフェッチ処理の対象とされた命令に対応するプリフェッチ命令の命令列中への挿入位置を決定するプリフェッチ命令挿入位置決定手段と、アドレス予測手段によって予測されたメモリアクセスアドレスをオペランドに有するプリフェッチ命令を、プリフェッチ命令挿入位置決定手段によって決定された挿入位置に、挿入するプリフェッチ命令挿入手段とを具備する演算処理装置が開示されている。しかし、複数のキャッシュブロックを転送するような場合については考慮されていない。
【特許文献１】特開平０８−３１４８０２号公報
【特許文献２】特開平０６−３２４９４２号公報
【特許文献３】特開平０７−１２９４６４号公報
【特許文献４】特開２００４−３４８１７５号公報
【特許文献５】特開２００３−２２３３５９号公報
【発明の開示】
【発明が解決しようとする課題】
【００１６】
上で述べたように、従来技術によれば、プリフェッチすべきデータが複数のキャッシュブロックに渡る場合でもプリフェッチすることが可能である。しかし、本来の処理命令の実行を妨げてしまい、システム全体の処理速度をかえって低下させる可能性がある。
【００１７】
従って、本発明の目的は、本来の処理命令の実行に対する影響を抑えつつ、複数のキャッシュブロックを主記憶装置からキャッシュメモリに転送するための技術を提供することである。
【課題を解決するための手段】
【００１８】
本発明に係るプロセッサは、プログラムを実行する実行ユニットと、キャッシュメモリと、所定の大きさのキャッシュブロックを主記憶からキャッシュメモリに転送する主記憶制御部と、キャッシュブロックの転送指示を主記憶制御部に出力するマルチブロックプリフェッチ制御部とを有する。そして、実行ユニットは、プログラム内の所定の処理の前に挿入された第１プリフェッチ開始命令を実行し、当該第１プリフェッチ開始命令に係るプリフェッチ対象領域の情報を含む第２プリフェッチ開始命令をマルチブロックプリフェッチ制御部に出力する。また、マルチブロックプリフェッチ制御部は、実行ユニットから第２プリフェッチ開始命令を受信した場合に、第２プリフェッチ開始命令に含まれるプリフェッチ対象領域の情報とキャッシュブロックの所定の大きさとに基づいて、転送すべき複数のキャッシュブロックを特定し、複数のキャッシュブロックを主記憶からキャッシュメモリに所定の処理の実行時間内で転送するようにスケジューリングし、転送指示を出力する。
【００１９】
例えば所定の間隔で転送指示を主記憶制御部に出力するようにすれば、本来の処理命令の実行に対する影響を抑えつつ、複数のキャッシュブロックを主記憶装置からキャッシュメモリに転送させることができる。また、従来、開発者は、プリフェッチ命令の数や挿入場所（例えば、何ステップ前に挿入するか等）を試行錯誤して探していたが、所定の処理（例えば、ループ処理）の前に第１プリフェッチ開始命令を挿入すれば良いので、従来の煩雑な作業が不要になる。
【００２０】
また、マルチブロックプリフェッチ制御部は、主記憶制御部における主記憶アクセス用リソースの使用状況を監視し、主記憶アクセス用リソースが空いている場合に、転送指示を出力するようにしてもよい。
【００２１】
さらに、実行ユニットは、プログラム内の所定の処理の後に挿入された第１プリフェッチ終了命令を実行し、第２プリフェッチ終了命令をマルチブロックプリフェッチ制御部に出力するようにしてもよい。また、マルチブロックプリフェッチ制御部は、実行ユニットから第２プリフェッチ終了命令を受信した場合に、第２プリフェッチ開始命令を受信してから第２プリフェッチ終了命令を受信するまでの時間と当該時間に対応する第１プリフェッチ開始命令を特定するための所定の情報とを実行履歴テーブルに格納するようにしてもよい。そして、マルチブロックプリフェッチ制御部は、実行履歴テーブルに格納された情報を基に所定の処理の実行時間を推定するようにしてもよい。例えば、前回の実行時間や過去数回の実行時間の平均時間を今回の実行時間とみなすことで、今回の実行時間を適切に推定することができる。
【００２２】
また、マルチブロックプリフェッチ制御部は、推定された、所定の処理の実行時間を基に複数のキャッシュブロックの転送間隔を算出し、当該転送間隔を基に転送指示の出力時間を特定するようにしてもよい。そして、マルチブロックプリフェッチ制御部は、出力時間に達した場合又は主記憶制御部における主記憶アクセス用のリソースが空いている場合に、転送指示を出力するようにしてもよい。このようにすれば、本来の処理命令の実行に対する影響を、より抑えることができる。
【００２３】
また、所定の処理が、第１プリフェッチ開始命令と第１プリフェッチ終了命令との間の処理を所定回数繰り返すループ処理である場合もある。
【発明の効果】
【００２４】
本発明によれば、本来の処理命令の実行に対する影響を抑えつつ、複数のキャッシュブロックを主記憶装置からキャッシュメモリに転送することができる。
【発明を実施するための最良の形態】
【００２５】
図４に本発明の一実施の形態に係るプロセッサ１の機能ブロック図を示す。本実施の形態に係るプロセッサ１は、キャッシュメモリ１３と、データやプログラム等をキャッシュメモリ１３から読み出し、命令を実行する実行ユニット１１と、実行ユニット１１からの指示に従って、複数のキャッシュブロックをキャッシュメモリ１３に転送するようにスケジューリングするマルチブロックプリフェッチ制御部１５と、実行ユニット１１の参照すべきデータがキャッシュメモリ１３に存在しない場合、又はマルチブロックプリフェッチ制御部１５からの転送指示を受信した場合に、主記憶３からキャッシュメモリ１３にデータを転送する主記憶制御部１７とを有する。なお、プロセッサ１と主記憶３とは、バスで接続されている。
【００２６】
さらに、マルチブロックプリフェッチ制御部１５は、プリフェッチ予定表１５１と実行履歴テーブル１５２とを含み、これらを用いて処理を行う。なお、プリフェッチ予定表１５１と実行履歴テーブル１５２については後で説明する。
【００２７】
図５に、図１に示したプログラムに対し、本発明を適用してプリフェッチを実装する場合のプログラムの一例を示す。図５の例では、従来のプリフェッチ命令３０１（図３）の代わりに、プリフェッチ開始命令（mb.prefetch.start命令）５０１がループ１０３の直前に挿入され、プリフェッチ終了命令（mb.prefetch.end命令）５０２がループ１０３の直後に挿入されている。プリフェッチ開始命令５０１では、プリフェッチ対象領域を指定するようになっている。なお、本実施の形態では、先頭アドレス及び末尾アドレスによって、プリフェッチ対象領域を指定するようになっている。図５の例では、Ａ[ｉ＋１][０]のアドレスを先頭アドレス、Ａ[ｉ＋２][０]のアドレスを末尾アドレスとして指定するようになっている。従って、例えば、ｉ＝１の場合は、Ａ[２][０]のアドレスを先頭アドレス、Ａ[３][０]のアドレスを末尾アドレスとしてプリフェッチ開始命令５０１が実行される。
【００２８】
図６乃至図１１を用いて、プロセッサ１がプリフェッチ開始命令５０１を実行した際の処理を説明する。まず、プロセッサ１の実行ユニット１１は、プリフェッチ開始命令５０１を実行し、プリフェッチ開始命令５０１で指定された先頭アドレスと末尾アドレスとを含むマルチブロックプリフェッチ開始命令をマルチブロックプリフェッチ制御部１５に出力する。また、実行ユニット１１は、プリフェッチ開始命令５０１の命令アドレスをマルチブロックプリフェッチ制御部１５に出力するようにする。マルチブロックプリフェッチ制御部１５は、先頭アドレスと末尾アドレスとを含むマルチブロックプリフェッチ開始命令を実行ユニット１１から受信し（図６：ステップＳ１）、内部に一旦格納する。このとき、プリフェッチ開始命令５０１の命令アドレス及びマルチブロックプリフェッチ開始命令の受信時刻も合わせて格納する。そして、マルチブロックプリフェッチ制御部１５は、先頭アドレスと末尾アドレスとをキャッシュブロックの境界にアライメントする（ステップＳ３）。この処理については、図７を用いて説明する。
【００２９】
図７は、キャッシュブロックのサイズが６４Ｂ（バイト）の際に、先頭アドレスとして0xa0000060、末尾アドレスとして0xa0000160が指定された場合の例を示す。上でも述べたが、主記憶３からキャッシュメモリ１３へのデータの転送は、キャッシュブロック単位で行われるため、先頭アドレス（0xa0000060）及び末尾アドレス（0xa0000160）をキャッシュブロックの境界と合わせる必要がある。キャッシュブロックのサイズが６４Ｂの場合であれば、例えば、以下の（１）及び（２）式によって、調整後の先頭アドレス及び末尾アドレスを算出することができる。なお、演算子「＆」は、ビットごとの論理積を求める演算子である。
（調整後先頭アドレス）＝ 0xffffffc0 ＆（先頭アドレス） （１）
（調整後末尾アドレス）＝ 0xffffffc0 ＆（末尾アドレス＋0x0000003f） （２）
図７の例では、（１）式により、調整後先頭アドレス（0xa0000040）が算出され、（２）式により、調整後末尾アドレス（0xa0000180）が算出される。
【００３０】
図６の説明に戻って、マルチブロックプリフェッチ制御部１５は、調整後先頭アドレスと調整後末尾アドレスとに基づきプリフェッチ対象ブロック数を算出する（ステップＳ５）。図７の例であれば、プリフェッチ対象ブロック数は５となる。そして、マルチブロックプリフェッチ制御部１５は、プリフェッチ開始命令５０１の命令アドレスをキーとして実行履歴テーブル１５２を検索し、経過時間を取得する（ステップＳ７）。
【００３１】
図８に、実行履歴テーブル１５２に格納されるデータの一例を示す。図８の例では、命令アドレスと経過時間とが格納されるようになっている。命令アドレスには、プリフェッチ開始命令５０１の命令アドレスが格納される。また、経過時間には、マルチブロックプリフェッチ開始命令を受信してから、後で述べるマルチブロックプリフェッチ終了命令を受信するまでの時間が格納される。従って、同一の命令アドレスのプリフェッチ開始命令５０１が過去に実行されている場合には、その際の実行時間を取得することができる。本実施の形態では、プリフェッチをいつまでに完了すべきかを同一処理の過去の実行時間から推定し、推定された時間内に、プリフェッチ対象ブロック数分のキャッシュブロックを転送するようにスケジューリングする。なお、同一の命令アドレスのプリフェッチ開始命令５０１が過去に実行されていない場合には（すなわち、実行履歴テーブル１５２に該当する経過時間が格納されていない場合には）、デフォルトの時間を使用する。
【００３２】
マルチブロックプリフェッチ制御部１５は、取得した経過時間とプリフェッチ対象ブロック数とに基づいてプリフェッチ間隔を算出する（ステップＳ９）。例えば、経過時間が５００、プリフェッチ対象ブロック数が５の場合には、プリフェッチ間隔は１００となる。そして、マルチブロックプリフェッチ制御部１５は、調整後先頭アドレスとプリフェッチ間隔とプリフェッチ対象ブロック数とを基にプリフェッチ予定表１５１を生成する（ステップＳ１１）。例えば、図９に示すようなプリフェッチ予定表が生成される。
【００３３】
図９の例では、プリフェッチアドレスとカウンタとプリフェッチ間隔と残ブロック数とが格納されるようになっている。プリフェッチアドレスには、初期値として調整後先頭アドレスが設定される。残ブロック数には、初期値としてプリフェッチ対象ブロック数が設定される。また、本実施の形態では、カウンタには、初期値として０を設定する。
【００３４】
そして、処理は端子Ａを介して図１０の処理に移行する。マルチブロックプリフェッチ制御部１５は、プリフェッチ予定表１５１の残ブロック数が０より大きいか判断する（図１０：ステップＳ１３）。もし、残ブロック数が０の場合（ステップＳ１３：Ｎｏルート）、処理を終了する。
【００３５】
一方、残ブロック数が０より大きい場合（ステップＳ１３：Ｙｅｓルート）、マルチブロックプリフェッチ制御部１５は、カウンタが０になったか判断する（ステップＳ１５）。なお、図示していないが、カウンタは、マルチブロックプリフェッチ制御部１５のタイマ等によって定期的にデクリメントされるものとする。カウンタがまだ０になっていない場合（ステップＳ１５：Ｎｏルート）、マルチブロックプリフェッチ制御部１５は、主記憶制御部１７における、主記憶にアクセスするためのリソースが空いているか判断する（ステップＳ１７）。もし、主記憶にアクセスするためのリソースが空いていない場合（ステップＳ１７：Ｎｏルート）、ステップＳ１３の処理に戻る。
【００３６】
一方、カウンタが０の場合（ステップＳ１５：Ｙｅｓルート）、又は主記憶にアクセスするためのリソースが空いている場合（ステップＳ１７：Ｙｅｓルート）、マルチブロックプリフェッチ制御部１５は、プリフェッチアドレスを含むプリフェッチ指示を主記憶制御部１７に出力する（ステップＳ１９）。
【００３７】
そして、マルチブロックプリフェッチ制御部１５は、プリフェッチ予定表１５１を更新する（ステップＳ２１）。例えば、図９に示したプリフェッチ予定表は、図１１に示すようなプリフェッチ予定表に更新される。図１１において、プリフェッチアドレスは、更新前のプリフェッチアドレス（0xa0000040）にキャッシュブロックのサイズ（６４Ｂ）分だけ加算され、次のキャッシュブロックを示すアドレス（0xa0000080）となっている。また、カウンタはプリフェッチ間隔の値でリセットされ、残ブロック数は１デクリメントされている。
【００３８】
以上のような処理を実施することにより、本来の処理命令に対する影響を抑えるように、複数のキャッシュブロックの転送をスケジューリングすることができる。
【００３９】
次に、図１２を用いて、プロセッサ１がプリフェッチ終了命令５０２を実行した際の処理を説明する。まず、プロセッサ１の実行ユニット１１は、プリフェッチ終了命令５０２を実行し、マルチブロックプリフェッチ終了命令をマルチブロックプリフェッチ制御部１５に出力する。マルチブロックプリフェッチ制御部１５は、マルチブロックプリフェッチ終了命令を実行ユニット１１から受信し（図１２：ステップＳ２３）、内部に一旦格納する。このとき、マルチブロックプリフェッチ終了命令の受信時刻も合わせて格納する。そして、マルチブロックプリフェッチ制御部１５は、プリフェッチ予定表１５１を削除する（ステップＳ２５）。なお、未転送のキャッシュブロックがある場合（すなわち、残ブロック数が１以上の場合）、プリフェッチをその時点で中止する。
【００４０】
そして、マルチブロックプリフェッチ制御部１５は、実行履歴を実行履歴テーブル１５２に格納する（ステップＳ２７）。具体的には、マルチブロックプリフェッチ制御部１５は、マルチブロックプリフェッチ開始命令の受信時刻とマルチブロックプリフェッチ終了命令の受信時刻との差を経過時間として実行履歴テーブル１５２に格納する。同時に、命令アドレスとしてプリフェッチ開始命令５０１の命令アドレスを格納する。
【００４１】
以上のような処理を実施することにより、複数のキャッシュブロックの転送をスケジューリングする際に必要となる実行時間を適切に推定することができるようになる。
【００４２】
以上本発明の実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、図４に示したプロセッサ１の機能ブロック図は一例であって、上で述べた機能を実現できれば図４の機能ブロック構成に限定されるわけではない。さらに、処理フローにおいても、処理結果が変らなければ処理の順番を入れ替えることも可能である。さらに、並列に実行させるようにしても良い。
【００４３】
また、プリフェッチ開始命令５０１では、先頭アドレスと末尾アドレスとを指定するようになっているが、先頭アドレスとプリフェッチ対象領域のサイズとを指定するようにしてもよい。この場合、ステップＳ３の処理の前に、先頭アドレスとプリフェッチ対象領域のサイズから末尾アドレスを算出すればよい。
【００４４】
また、例えば、プリフェッチ開始命令５０１の前に条件分岐命令を挿入し、条件によってプリフェッチ開始命令５０１を実行させるようなプログラムにしてもよい。例えば、プリフェッチ対象領域が大きすぎると、本来の処理命令で使用するはずのデータを追い出してしまい、処理速度をかえって低下させる可能性があるため、プリフェッチ対象領域が所定の大きさを超えるような場合にはプリフェッチ開始命令５０１を実行させないような条件分岐命令を挿入すればよい。なお、従来のプリフェッチ命令３０１（図３）はループ１０３内に挿入されるため、条件分岐命令もループ１０３内に挿入しなければならなかったが、本発明においては、プリフェッチ開始命令５０１がループ１０３外に挿入されるため、条件分岐命令もループ１０３外に挿入できる。すなわち、条件分岐命令を挿入したとしても、本来の処理命令の実行に対する影響は、従来に比べて少ない。
【００４５】
また、上で説明したテーブルの構成は一例であって、必ずしも上記のような構成でなければならないわけではない。例えば、実行履歴テーブル１５２において、前回の実行時間を取得できる構成であれば、命令アドレス以外の情報と対応付けて経過時間を格納することも可能である。また、実行ユニット１１が、プリフェッチ開始命令５０１を実行してからプリフェッチ終了命令５０２を実行するまでの時間を実行履歴テーブル１５２に格納するように構成することも可能である。
【００４６】
（付記１）
プログラムを実行する実行ユニットと、
キャッシュメモリと、
所定の大きさのキャッシュブロックを主記憶から前記キャッシュメモリに転送する主記憶制御部と、
前記キャッシュブロックの転送指示を前記主記憶制御部に出力するマルチブロックプリフェッチ制御部と、
を有し、
前記実行ユニットは、
前記プログラム内の所定の処理の前に挿入された第１プリフェッチ開始命令を実行し、当該第１プリフェッチ開始命令に係るプリフェッチ対象領域の情報を含む第２プリフェッチ開始命令を前記マルチブロックプリフェッチ制御部に出力し、
前記マルチブロックプリフェッチ制御部は、
前記実行ユニットから前記第２プリフェッチ開始命令を受信した場合に、前記第２プリフェッチ開始命令に含まれる前記プリフェッチ対象領域の情報と前記キャッシュブロックの前記所定の大きさとに基づいて、転送すべき複数のキャッシュブロックを特定し、
前記複数のキャッシュブロックを前記主記憶から前記キャッシュメモリに前記所定の処理の実行時間内で転送するようにスケジューリングし、前記転送指示を出力する
プロセッサ。
【００４７】
（付記２）
前記マルチブロックプリフェッチ制御部は、
前記主記憶制御部における主記憶アクセス用リソースの使用状況を監視し、前記主記憶アクセス用リソースが空いている場合に、前記転送指示を出力する
付記１記載のプロセッサ。
【００４８】
（付記３）
前記実行ユニットは、
前記プログラム内の所定の処理の後に挿入された第１プリフェッチ終了命令を実行し、第２プリフェッチ終了命令を前記マルチブロックプリフェッチ制御部に出力し、
前記マルチブロックプリフェッチ制御部は、
前記実行ユニットから前記第２プリフェッチ終了命令を受信した場合に、前記第２プリフェッチ開始命令を受信してから前記第２プリフェッチ終了命令を受信するまでの時間と当該時間に対応する前記第１プリフェッチ開始命令を特定するための所定の情報とを実行履歴テーブルに格納する
付記１記載のプロセッサ。
【００４９】
（付記４）
前記マルチブロックプリフェッチ制御部は、
前記実行履歴テーブルに格納された情報を基に前記所定の処理の実行時間を推定する
付記３記載のプロセッサ。
【００５０】
（付記５）
前記マルチブロックプリフェッチ制御部は、
推定された、前記所定の処理の実行時間を基に前記複数のキャッシュブロックの転送間隔を算出し、当該転送間隔を基に前記転送指示の出力時間を特定する
付記４記載のプロセッサ。
【００５１】
（付記６）
前記マルチブロックプリフェッチ制御部は、
前記複数のキャッシュブロックの転送間隔を算出し、当該転送間隔を基に前記転送指示の出力時間を特定する
付記１記載のプロセッサ。
【００５２】
（付記７）
前記マルチブロックプリフェッチ制御部は、
前記出力時間に達した場合又は前記主記憶制御部における主記憶アクセス用のリソースが空いている場合に、前記転送指示を出力する
付記５又は６記載のプロセッサ。
【００５３】
（付記８）
前記マルチブロックプリフェッチ制御部は、
前記転送指示を出力した後、前記複数のキャッシュブロックのうち未転送のキャッシュブロックがある場合には、前記転送間隔を基に次に出力すべき前記転送指示の出力時間を特定する
付記７記載のプロセッサ。
【００５４】
（付記９）
前記プリフェッチ対象領域の情報が、当該プリフェッチ対象領域の先頭アドレスと当該プリフェッチ対象領域の終了アドレス又はサイズとを含む
付記１記載のプロセッサ。
【００５５】
（付記１０）
前記所定の処理が、前記第１プリフェッチ開始命令と前記第１プリフェッチ終了命令との間の処理を所定回数繰り返すループ処理である
付記３記載のプロセッサ。
【００５６】
（付記１１）
プログラム内の所定の処理の前に挿入された第１プリフェッチ開始命令の実行時に実行ユニットから出力され、当該第１プリフェッチ開始命令に係るプリフェッチ対象領域の情報を含む第２プリフェッチ開始命令を受信した場合に、前記第２プリフェッチ開始命令に含まれる前記プリフェッチ対象領域の情報とキャッシュブロックのサイズとに基づいて、主記憶からキャッシュメモリに転送すべき複数のキャッシュブロックを特定するステップと、
前記複数のキャッシュブロックを前記主記憶から前記キャッシュメモリに前記所定の処理の実行時間内で転送するようにスケジューリングし、転送指示を主記憶制御部に出力するステップと、
を含む、プリフェッチ制御方法。
【図面の簡単な説明】
【００５７】
【図１】プリフェッチを必要とするプログラムの一例を示す図である。
【図２】図１に示したプログラムの処理とプリフェッチとの関係を時系列で表した図である。
【図３】従来技術によりプリフェッチを実装する場合のプログラムの一例を示す図である。
【図４】本発明の実施の形態におけるプロセッサの機能ブロック図を示す図である。
【図５】本発明を適用してプリフェッチを実装する場合のプログラムの一例を示す図である。
【図６】プリフェッチ開始命令を実行した際の処理フロー（第１の部分）を示す図である。
【図７】アドレスのアライメントを説明するための図である。
【図８】実行履歴テーブルに格納されるデータの一例を示す図である。
【図９】プリフェッチ予定表に格納されるデータの一例を示す図である。
【図１０】プリフェッチ開始命令を実行した際の処理フロー（第２の部分）を示す図である。
【図１１】更新後のプリフェッチ予定表に格納されるデータの一例を示す図である。
【図１２】プリフェッチ終了命令を実行した際の処理フローを示す図である。
【符号の説明】
【００５８】
１ プロセッサ ３ 主記憶
１１ 実行ユニット １３ キャッシュメモリ
１５ マルチブロックプリフェッチ制御部 １７ 主記憶制御部
１５１ プリフェッチ予定表 １５２ 実行履歴テーブル
【特許請求の範囲】
【請求項１】
プログラムを実行する実行ユニットと、
キャッシュメモリと、
所定の大きさのキャッシュブロックを主記憶から前記キャッシュメモリに転送する主記憶制御部と、
前記キャッシュブロックの転送指示を前記主記憶制御部に出力するマルチブロックプリフェッチ制御部と、
を有し、
前記実行ユニットは、
前記プログラム内の所定の処理の前に挿入された第１プリフェッチ開始命令を実行し、当該第１プリフェッチ開始命令に係るプリフェッチ対象領域の情報を含む第２プリフェッチ開始命令を前記マルチブロックプリフェッチ制御部に出力し、
前記マルチブロックプリフェッチ制御部は、
前記実行ユニットから前記第２プリフェッチ開始命令を受信した場合に、前記第２プリフェッチ開始命令に含まれる前記プリフェッチ対象領域の情報と前記キャッシュブロックの前記所定の大きさとに基づいて、転送すべき複数のキャッシュブロックを特定し、
前記複数のキャッシュブロックを前記主記憶から前記キャッシュメモリに前記所定の処理の実行時間内で転送するようにスケジューリングし、前記転送指示を出力する
プロセッサ。
【請求項２】
前記実行ユニットは、
前記プログラム内の所定の処理の後に挿入された第１プリフェッチ終了命令を実行し、第２プリフェッチ終了命令を前記マルチブロックプリフェッチ制御部に出力し、
前記マルチブロックプリフェッチ制御部は、
前記実行ユニットから前記第２プリフェッチ終了命令を受信した場合に、前記第２プリフェッチ開始命令を受信してから前記第２プリフェッチ終了命令を受信するまでの時間と当該時間に対応する前記第１プリフェッチ開始命令を特定するための所定の情報とを実行履歴テーブルに格納する
請求項１記載のプロセッサ。
【請求項３】
前記マルチブロックプリフェッチ制御部は、
前記実行履歴テーブルに格納された情報を基に前記所定の処理の実行時間を推定する
請求項２記載のプロセッサ。
【請求項４】
前記マルチブロックプリフェッチ制御部は、
前記複数のキャッシュブロックの転送間隔を算出し、当該転送間隔を基に前記転送指示の出力時間を特定する
請求項１記載のプロセッサ。
【請求項５】
前記マルチブロックプリフェッチ制御部は、
前記出力時間に達した場合又は前記主記憶制御部における主記憶アクセス用のリソースが空いている場合に、前記転送指示を出力する
請求項４記載のプロセッサ。
【請求項６】
プログラム内の所定の処理の前に挿入された第１プリフェッチ開始命令の実行時に実行ユニットから出力され、当該第１プリフェッチ開始命令に係るプリフェッチ対象領域の情報を含む第２プリフェッチ開始命令を受信した場合に、前記第２プリフェッチ開始命令に含まれる前記プリフェッチ対象領域の情報とキャッシュブロックのサイズとに基づいて、主記憶からキャッシュメモリに転送すべき複数のキャッシュブロックを特定するステップと、
前記複数のキャッシュブロックを前記主記憶から前記キャッシュメモリに前記所定の処理の実行時間内で転送するようにスケジューリングし、転送指示を主記憶制御部に出力するステップと、
を含む、プリフェッチ制御方法。
【請求項１】
プログラムを実行する実行ユニットと、
キャッシュメモリと、
所定の大きさのキャッシュブロックを主記憶から前記キャッシュメモリに転送する主記憶制御部と、
前記キャッシュブロックの転送指示を前記主記憶制御部に出力するマルチブロックプリフェッチ制御部と、
を有し、
前記実行ユニットは、
前記プログラム内の所定の処理の前に挿入された第１プリフェッチ開始命令を実行し、当該第１プリフェッチ開始命令に係るプリフェッチ対象領域の情報を含む第２プリフェッチ開始命令を前記マルチブロックプリフェッチ制御部に出力し、
前記マルチブロックプリフェッチ制御部は、
前記実行ユニットから前記第２プリフェッチ開始命令を受信した場合に、前記第２プリフェッチ開始命令に含まれる前記プリフェッチ対象領域の情報と前記キャッシュブロックの前記所定の大きさとに基づいて、転送すべき複数のキャッシュブロックを特定し、
前記複数のキャッシュブロックを前記主記憶から前記キャッシュメモリに前記所定の処理の実行時間内で転送するようにスケジューリングし、前記転送指示を出力する
プロセッサ。
【請求項２】
前記実行ユニットは、
前記プログラム内の所定の処理の後に挿入された第１プリフェッチ終了命令を実行し、第２プリフェッチ終了命令を前記マルチブロックプリフェッチ制御部に出力し、
前記マルチブロックプリフェッチ制御部は、
前記実行ユニットから前記第２プリフェッチ終了命令を受信した場合に、前記第２プリフェッチ開始命令を受信してから前記第２プリフェッチ終了命令を受信するまでの時間と当該時間に対応する前記第１プリフェッチ開始命令を特定するための所定の情報とを実行履歴テーブルに格納する
請求項１記載のプロセッサ。
【請求項３】
前記マルチブロックプリフェッチ制御部は、
前記実行履歴テーブルに格納された情報を基に前記所定の処理の実行時間を推定する
請求項２記載のプロセッサ。
【請求項４】
前記マルチブロックプリフェッチ制御部は、
前記複数のキャッシュブロックの転送間隔を算出し、当該転送間隔を基に前記転送指示の出力時間を特定する
請求項１記載のプロセッサ。
【請求項５】
前記マルチブロックプリフェッチ制御部は、
前記出力時間に達した場合又は前記主記憶制御部における主記憶アクセス用のリソースが空いている場合に、前記転送指示を出力する
請求項４記載のプロセッサ。
【請求項６】
プログラム内の所定の処理の前に挿入された第１プリフェッチ開始命令の実行時に実行ユニットから出力され、当該第１プリフェッチ開始命令に係るプリフェッチ対象領域の情報を含む第２プリフェッチ開始命令を受信した場合に、前記第２プリフェッチ開始命令に含まれる前記プリフェッチ対象領域の情報とキャッシュブロックのサイズとに基づいて、主記憶からキャッシュメモリに転送すべき複数のキャッシュブロックを特定するステップと、
前記複数のキャッシュブロックを前記主記憶から前記キャッシュメモリに前記所定の処理の実行時間内で転送するようにスケジューリングし、転送指示を主記憶制御部に出力するステップと、
を含む、プリフェッチ制御方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２００８−２６９４５０（Ｐ２００８−２６９４５０Ａ）
【公開日】平成２０年１１月６日（２００８．１１．６）
【国際特許分類】
【出願番号】特願２００７−１１３７９２（Ｐ２００７−１１３７９２）
【出願日】平成１９年４月２４日（２００７．４．２４）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２０年１１月６日（２００８．１１．６）
【国際特許分類】
【出願日】平成１９年４月２４日（２００７．４．２４）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]