(57)【要約】  プロセッサは、レジスタ更新命令を検出すると、レジスタ更新命令のアドレスを更新されるレジスタの識別情報に対応付けてレジスタ・プロデューサ・テーブルに登録する。プロセッサは、レジスタによって間接的に指定されるアドレスにアクセスする命令を検出すると、アドレスを指定したレジスタの識別情報によって、レジスタ・プロデューサ・テーブルに登録されたレジスタ更新命令のアドレスを特定する。プロセッサは、特定されたアドレスのレジスタ更新命令をアドレス生成命令とみなす。プロセッサは、アドレス生成命令によって更新されたレジスタの値が示すアドレスのデータをキャッシュメモリにプリフェッチする。
2008155812.tif 000002
【特許請求の範囲】
【請求項１】
記憶装置の情報を予めキャッシュに格納するプリフェッチ機能を有するプロセッサであって、
記憶装置に記憶されたプログラムを読み出して命令を実行する場合に、当該命令がレジスタの値を更新する命令であると判定すると、前記レジスタの識別情報と前記命令とを対応付けてレジスタ・プロデューサ・テーブルに記憶する記憶制御手段と、
前記記憶装置に記憶されたプログラムを読み出して命令を実行する場合に、当該命令がレジスタによって間接的に指定されるアドレスにアクセスする命令であると判定すると、前記アドレスを間接的に指定するレジスタの識別情報と前記レジスタ・プロデューサ・テーブルとを基にして前記レジスタを更新した命令をアドレス生成命令として特定する命令特定手段と、
前記アドレス生成命令によって更新されたレジスタの値をプリフェッチするプリフェッチ手段と、
を備えたことを特徴とするプロセッサ。
【請求項２】
前記命令特定手段は、前記プログラムに含まれる命令のうち、前記アドレス生成命令に対応する命令を、本来の命令と同様の処理を行った後に演算結果をメモリアドレスとみなしプリフェッチを実行する命令に書き換え、前記プリフェッチ手段は、前記書き換えられた命令に基づいてプリフェッチすることを特徴とする請求項１に記載のプロセッサ。
【請求項３】
前記命令特定手段は、前記キャッシュに格納された命令のうち、前記アドレス生成命令に対応する命令に、当該命令がアドレス生成命令である旨の付加情報を付加し、前記プリフェッチ手段は、前記付加情報が付加された命令によって更新されたレジスタの値をプリフェッチすることを特徴とする請求項１に記載のプロセッサ。
【請求項４】
前記命令特定手段は、前記アドレス生成命令として特定した命令をアドレス生成テーブルに登録し、前記プリフェッチ手段は、前記アドレス生成テーブルに登録された命令を実行する場合に、当該命令によって更新されたレジスタの値をプリフェッチすることを特徴とする請求項１に記載のプロセッサ。
【請求項５】
コンピュータに、
記憶装置に記憶されたプログラムを読み出して命令を実行する場合に、当該命令がレジスタの値を更新する命令であると判定すると、前記レジスタの識別情報と前記命令とを対応付けてレジスタ・プロデューサ・テーブルに記憶する記憶制御手順と、
前記記憶装置に記憶されたプログラムを読み出して命令を実行する場合に、当該命令がレジスタによって間接的に指定されるアドレスにアクセスする命令であると判定すると、前記アドレスを間接的に指定するレジスタの識別情報と前記レジスタ・プロデューサ・テーブルとを基にして前記レジスタを更新した命令をアドレス生成命令として特定する命令特定手順と、
前記アドレス生成命令によって更新されたレジスタの値をプリフェッチするプリフェッチ手順と、
を実行させるためのプリフェッチ支援プログラム。
【請求項６】
前記命令特定手順は、前記プログラムに含まれる命令のうち、前記アドレス生成命令に対応する命令を、本来の命令と同様の処理を行った後に演算結果をメモリアドレスとみなしプリフェッチを実行する命令に書き換え、前記プリフェッチ手順は、前記書き換えられた命令に基づいてプリフェッチすることを特徴とする請求項５に記載のプリフェッチ支援プログラム。
【請求項７】
前記コンピュータは、プリフェッチした情報を格納するキャッシュを備え、
前記命令特定手順は、前記キャッシュに格納された命令のうち、前記アドレス生成命令に対応する命令に、当該命令がアドレス生成命令である旨の付加情報を付加し、前記プリフェッチ手順は、前記付加情報が付加された命令によって更新されたレジスタの値をプリフェッチすることを特徴とする請求項５に記載のプリフェッチ支援プログラム。
【請求項８】
前記命令特定手順は、前記アドレス生成命令として特定した命令をアドレス生成テーブルに登録し、前記プリフェッチ手順は、前記アドレス生成テーブルに登録された命令を実行する場合に、当該命令によって更新されたレジスタの値をプリフェッチすることを特徴とする請求項５に記載のプリフェッチ支援プログラム。
【請求項９】
コンピュータに、
記憶装置に記憶されたプログラムを読み出して命令を実行する場合に、当該命令がレジスタの値を更新する命令であると判定すると、前記レジスタの識別情報と前記命令とを対応付けてレジスタ・プロデューサ・テーブルに記憶する記憶制御手順と、
前記記憶装置に記憶されたプログラムを読み出して命令を実行する場合に、当該命令がレジスタによって間接的に指定されるアドレスにアクセスする命令であると判定すると、前記アドレスを間接的に指定するレジスタの識別情報と前記レジスタ・プロデューサ・テーブルとを基にして前記レジスタを更新した命令をアドレス生成命令として特定する命令特定手順と、
前記アドレス生成命令によって更新されたレジスタの値をプリフェッチするプリフェッチ手順と、
を実行させるためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【請求項１０】
前記命令特定手順は、前記プログラムに含まれる命令のうち、前記アドレス生成命令に対応する命令を、本来の命令と同様の処理を行った後に演算結果をメモリアドレスとみなしプリフェッチを実行する命令に書き換え、前記プリフェッチ手順は、前記書き換えられた命令に基づいてプリフェッチすることを特徴とする請求項９に記載の記憶媒体。
【請求項１１】
前記コンピュータは、プリフェッチした情報を格納するキャッシュを備え、
前記命令特定手順は、前記キャッシュに格納された命令のうち、前記アドレス生成命令に対応する命令に、当該命令がアドレス生成命令である旨の付加情報を付加し、前記プリフェッチ手順は、前記付加情報が付加された命令によって更新されたレジスタの値をプリフェッチすることを特徴とする請求項９に記載の記憶媒体。
【請求項１２】
前記命令特定手順は、前記アドレス生成命令として特定した命令をアドレス生成テーブルに登録し、前記プリフェッチ手順は、前記アドレス生成テーブルに登録された命令を実行する場合に、当該命令によって更新されたレジスタの値をプリフェッチすることを特徴とする請求項９に記載の記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記憶装置の情報を予めキャッシュに格納するプリフェッチ機能を有するプロセッサ等に関するものである。
【背景技術】
【０００２】
昨今の計算機システムでは、メモリと演算器の速度差を隠蔽するために、キャッシュ機構を導入している。キャッシュとは、頻繁に利用するデータを一時的に格納するための、小容量かつ高速なメモリを示す。このキャッシュを効果的に利用することが、システム全体の性能を引き上げるために大きく寄与する。【０００３】
キャッシュを有効利用するためのアプローチには大きく２つある。１つは、一度キャッシュに載せたデータのうち、再利用する可能性の高いデータをなるべくキャッシュの外に追い出さないようにするアプローチである。もう１つは、近い将来利用する可能性の高いデータを、事前に遅いメモリから速いキャッシュへ転送するアプローチである。後者のアプローチの代表的な手法がプリフェッチと呼ばれる手法である（例えば、特許文献１、特許文献２参照）。【０００４】
キャッシュ機構を有する計算機システムは、小さいが高速なメモリをプロセッサの近い場所に、大きいが低速なメモリをプロセッサの遠い場所に配置し、頻繁に利用されるデータほどプロセッサに近いメモリにコピーしておく。これにより理想的には全てのメモリが近い高速なメモリに載っている状態にできる。今日の計算機システムにおいては、様々な工夫によりこの理想状態に近いアクセス時間を実現している。このような階層的なメモリの仕組みをキャッシュと呼ぶ。キャッシュ機構を有する計算機システムについては、非特許文献１参照。【０００５】
また、スーパースカラ・プロセッサにおけるアウト・オブ・オーダー技術をはじめとするマイクロアーキテクチャの詳細は非特許文献２に記述されている。アウト・オブ・オーダー技術とは、キャッシュミスなど、コンパイル時に予測できない要因に対して、プロセッサ内で実行しながら動的に対処し、命令を最適な実行順序に再構成する技術である。【０００６】
次に、プリフェッチについて述べる。プリフェッチは、キャッシュアクセスを最適化するための技術の１つである。通常、load命令などメモリからデータを読み出す命令を実行する際、そのデータがキャッシュ上に存在しなければ、メインメモリまでデータを読みに行く。これは、キャッシュ上に存在するデータをアクセスする場合に比べて、非常に時間のかかる処理である。【０００７】
ところが、事前に読み出すメモリアドレスが判明している場合には、必要なデータをメインメモリからキャッシュまで事前に読み出すことが可能である。通常の処理と平行してメモリからキャッシュへのデータ転送を行う事で、その後該当データを読み出そうとした際に、キャッシュから高速に読み出すことができる。このように、他の処理と平行して、事前にメインメモリからキャッシュまでデータを読み出す処理のことをプリフェッチと呼ぶ。【０００８】
通常のメモリアクセスでは、データが取得できるまでメモリアクセス命令の実行は完了しない。一方、プリフェッチ処理は、他の命令実行と平行して行われ、データ取得が終わらなくともプロセッサは次の命令処理を継続する。このため、前もってプリフェッチを行っておくことで、必要なときにデータをキャッシュ上に転送しておくことが可能となる。【０００９】
実際にデータが必要になるまでに、キャッシュへのデータ読み出しが完了していれば、データはキャッシュから高速に読み出される。完了していない場合には、転送が終わるまで待った後にデータが読み込まれる。この場合、プリフェッチが間に合った場合に比べ効果は小さいが、メモリ読み出し処理が命令に先立って開始されているため、プリフェッチ命令を利用しなかった場合に比べ、メモリ読み出しの応答は高速化される。【００１０】
ここで、プリフェッチについてさらに詳しく説明する。通常、プリフェッチといったとき、大きく分けて２種類のプリフェッチが存在する。ソフトウェア・プリフェッチとハードウェア・プリフェッチである。両者の性能的な比較については非特許文献３を参照。【００１１】
ソフトウェア・プリフェッチは、非特許文献４、５に記載されているように、コンパイラあるいはプログラマが明示的にプリフェッチ命令を挿入する事で実施される。プログラムの静的な特性に基づき、キャッシュミスの発生しそうな箇所に対し、実際のメモリアクセス命令に対して十分先行した箇所に挿入される。【００１２】
ハードウェア・プリフェッチは、非特許文献６、７に記載されているように、プロセッサが暗黙的に行うプリフェッチである。アプリケーションの動的な振る舞いから、予測に基づき実施される。連続したストリームメモリアクセスや、一定区間あけながら規則的な連続アクセスを行うストライドメモリアクセスを検出し、それらのアクセスに対して先読みを行うようプリフェッチを実施する。【００１３】
【特許文献１】特開平７−５６８０９号公報
【特許文献２】特開平１１−１４３７７４号公報
【非特許文献１】John  L.  Hennessy,  and  David  A.  Patterson.  “Computer  Architecture  -  A  Quantitative  Approach  3rd  Edition,”  MORGAN  KAUFMANN  PUBLISHERS,  ISBN  1-55860-724-2.
【非特許文献２】Mike  Johnson.  “Superscalar  Microprocessor  Design,”  Prentice-Hallm  Inc,  ISBN  0138756341.
【非特許文献３】Tien-Fu  Chen,  and  Jean-Loup  Baer.  “A  performance  study  of  software  and  hardware  data  prefetching  schemes,”  Proc.  1994  the  21st  Annual  International  Symposium  on  Computer  Architecture.
【非特許文献４】David  Callahan,  Ken  Kennedy,  and  Allan  Porterfield.  “Software  prefetching,“  ACM  SIGARCH  Computer  Architecture  News  Volume  19,  Issue  2  (April  1991).
【非特許文献５】Todd  C.  Mowry,  Monica  S.  Lam,  and  Anoop  Gupta.  “Design  and  evaluation  of  a  compiler  algorithm  for  prefetching,”  ACM  SIGPLAN  Notices  Volume  27,  Issue  9  (September  1992)
【非特許文献６】Steven  P.  Vanderwiel,  and  David  J.  Lilja.  “Data  Prefetch  mechanisms,“  ACM  Computing  Surveys  Volume  32,  Issue  2  (June  2000).
【非特許文献７】Wei-Fen  Lin,  Steven  K.  Reinhardt,  and  Doug  Burger.  “Designing  a  Modern  Memory  Hierarchy  with  Hardware  Prefetching,”  IEEE  Transactions  on  Computers  Volume  50,  Issue  11  (November  2001).
【発明の開示】
【発明が解決しようとする課題】
【００１４】
しかしながら、上述した従来のハードウェア・プリフェッチ技術では、メモリに対するストリームアクセス、あるいはストライドアクセスに関してのみ、過去のアクセス傾向から予測してプリフェッチを実施する手法であるため、学術計算などメモリアクセスパターンが規則的なアプリケーションでは効果が期待できるが、一般的なアプリケーション（特に、メモリアクセスパターンが不規則なアプリケーション）ではハードウェア・プリフェッチの予測精度が低く、ハードウェア・プリフェッチの効果が低いという問題があった。【００１５】
すなわち、一般的なアプリケーションで見受けられる不規則なメモリアクセスを見抜き、効果的なハードウェア・プリフェッチを行うことが極めて重要な課題となっている。【００１６】
本発明は、上記に鑑みてなされたものであって、一般的なアプリケーションで見受けられる不規則なメモリアクセスを見抜き、効果的なハードウェア・プリフェッチを実行可能なプロセッサおよびプリフェッチ支援プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
上述した課題を解決し、目的を達成するために、本発明は、メモリの情報を予めキャッシュに格納するプリフェッチ機能を有するプロセッサであって、メモリに記憶されたプログラムを読み出して命令を実行する場合に、当該命令がレジスタの値を更新する命令であると判定すると、前記レジスタの識別情報と前記命令とを対応付けてレジスタ・プロデューサ・テーブルに記憶する記憶制御手段と、前記メモリに記憶されたプログラムを読み出して命令を実行する場合に、当該命令がレジスタによって間接的に指定されるアドレスにアクセスする命令であると判定すると、前記アドレスを間接的に指定するレジスタの識別情報と前記レジスタ・プロデューサ・テーブルとを基にして前記レジスタを更新した命令をアドレス生成命令として特定する命令特定手段と、前記アドレス生成命令によって更新されたレジスタの値をプリフェッチするプリフェッチ手段と、を備えたことを特徴とする。【００１８】
また、本発明は、上記発明において、前記命令特定手段は、前記プログラムに含まれる命令のうち、前記アドレス生成命令に対応する命令を、本来の命令と同様の処理を行った後に演算結果をメモリアドレスとみなしプリフェッチを実行する命令に書き換え、前記プリフェッチ手段は、前記書き換えられた命令に基づいてプリフェッチすることを特徴とする。【００１９】
また、本発明は、上記発明において、前記命令特定手段は、前記キャッシュに格納された命令のうち、前記アドレス生成命令に対応する命令に、当該命令がアドレス生成命令である旨の付加情報を付加し、前記プリフェッチ手段は、前記付加情報が付加された命令によって更新されたレジスタの値をプリフェッチすることを特徴とする。【００２０】
また、本発明は、上記発明において、前記命令特定手段は、前記アドレス生成命令として特定した命令をアドレス生成テーブルに登録し、前記プリフェッチ手段は、前記アドレス生成テーブルに登録された命令を実行する場合に、当該命令によって更新されたレジスタの値をプリフェッチすることを特徴とする。
【発明の効果】
【００２１】
本発明によれば、メモリに記憶されたプログラムを読み出して命令を実行する場合に、当該命令がレジスタの値を更新する命令であると判定すると、レジスタの識別情報と命令とを対応付けてレジスタ・プロデューサ・テーブルに記憶し、メモリに記憶されたプログラムを読み出して命令を実行する場合に、当該命令がレジスタによって間接的に指定されるアドレスにアクセスする命令であると判定すると、アドレスを間接的に指定するレジスタの識別情報とレジスタ・プロデューサ・テーブルとを基にしてレジスタを更新した命令をアドレス生成命令として特定し、アドレス生成命令によって更新されたレジスタの値をプリフェッチするので、一般的なアプリケーションで見受けられる不規則なメモリアクセスを見抜き、効果的なハードウェア・プリフェッチを行うことができる。【００２２】
また、本発明によれば、プログラムに含まれる命令のうち、アドレス生成命令に対応する命令を、本来の命令と同様の処理を行った後に演算結果をメモリアドレスとみなしプリフェッチを実行する命令に書き換え、書き換えられた命令に基づいてプリフェッチするので、高速なメモリアクセスを実現することができる。【００２３】
また、本発明によれば、キャッシュに格納された命令のうち、アドレス生成命令に対応する命令に、命令がアドレス生成命令である旨の付加情報を付加し、付加情報が付加された命令によって更新されたレジスタの値をプリフェッチするので、高速なメモリアクセスを実現することができる。【００２４】
また、本発明によれば、アドレス生成命令として特定した命令をアドレス生成テーブルに登録し、アドレス生成テーブルに登録された命令を実行する場合に、当該命令によって更新されたレジスタの値をプリフェッチするので、高速なメモリアクセスを実現することができる。
【図面の簡単な説明】
【００２５】
【図１】図１は、本実施例１にかかるプロセッサがアドレス生成命令を特定する仕組みを説明するための図である。
【図２】図２は、レジスタ・プロデューサ・テーブルのデータ構造の一例を示す図である。
【図３】図３は、レジスタ・プロデューサ・テーブルの更新処理を説明するための図である。
【図４】図４は、アドレス生成命令を特定する処理を説明するための図である。
【図５】図５は、命令の書き換え処理を説明するための図である。
【図６】図６は、本実施例１にかかるプロセッサの構成を示す機能ブロック図である。
【図７】図７は、本実施例１にかかるプロセッサの処理手順を示すフローチャートである。
【図８】図８は、レジスタ・プロデューサ・テーブル更新処理を示すフローチャートである。
【図９】図９は、キャッシュ情報のデータ構造の一例を示す図である。
【図１０】図１０は、プロセッサがキャッシュ情報のアドレス生成フラグを更新する処理を説明するための図である。
【図１１】図１１は、本実施例２にかかるプロセッサの構成を示す機能ブロック図である。
【図１２】図１２は、本実施例２にかかるプロセッサの処理手順を示すフローチャート（１）である。
【図１３】図１３は、本実施例２にかかるプロセッサの処理手順を示すフローチャート（２）である。
【図１４】図１４は、アドレス生成命令テーブルのデータ構造の一例を示す図である。
【図１５】図１５は、プロセッサがアドレス生成テーブルを参照する方法を説明するための図である。
【図１６】図１６は、本実施例３にかかるプロセッサの構成を示す機能ブロック図である。
【図１７】図１７は、本実施例３にかかるプロセッサの処理手順を示すフローチャート（１）である。
【図１８】図１８は、本実施例３にかかるプロセッサの処理手順を示すフローチャート（２）である。
【符号の説明】
【００２６】
１００，４００，５００    プロセッサ
１１０，４１０，５１０    Ｉ／Ｏ制御部
１１０ａ，４１０ａ，５１０ａ  プリフェッチ制御部
１２０，４２０，５２０    レジスタ部
１３０，４３０，５３０    制御部
１４０，４４０，５４０    演算部
１５０，４５０，５５０    レジスタ・プロデューサ・テーブル記憶部
１６０，４６０，５７０    データ依存解析部
２００    キャッシュ
３００    メインメモリ
５６０    アドレス生成命令テーブル記憶部
【発明を実施するための最良の形態】
【００２７】
以下に、本発明にかかるプロセッサおよびプリフェッチ支援プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例１】
【００２８】
まず、本実施例１にかかるプロセッサの概要および特徴について説明する。本実施例１にかかるプロセッサは、メインメモリのデータを予めキャッシュに格納するハードウェア・プリフェッチ（以下、プリフェッチと略記する）機能を有するプロセッサであり、メインメモリ（あるいはキャッシュ）に記憶されたプログラムを読み出して命令を実行する場合に、当該命令がレジスタの値を更新する命令（以下、レジスタ更新命令）であると判定すると、かかるレジスタの識別情報とレジスタ更新命令とを対応付けてレジスタ・プロデューサ・テーブルに記憶する。【００２９】
また、プロセッサは、メインメモリ（あるいはキャッシュ）に記憶されたプログラムを実行する場合に、当該命令がレジスタによって間接的に指定されるアドレスにアクセスする命令であると判定すると、アドレスを間接的に指定するレジスタの識別情報とレジスタ・プロデューサ・テーブルとを基にしてレジスタ（アドレスを間接的に指定するレジスタ）を更新した命令をレジスタ更新命令の中からを特定し、特定した命令（アドレス生成命令）によって更新されたレジスタの値をプリフェッチする。【００３０】
このように、本実施例１にかかるプロセッサは、レジスタ・プロデューサ・テーブルを用いてアドレス生成命令を特定し、次回アドレス生成命令を実行する際、アドレス生成命令によって更新されたレジスタの値をプリフェッチするので、一般的なアプリケーションで見受けられる不規則なメモリアクセスを見抜き、効果的なハードウェア・プリフェッチを行うことができる。【００３１】
続いて、本実施例１にかかるプロセッサがアドレス生成命令を特定する仕組みについて説明する。図１は、本実施例１にかかるプロセッサがアドレス生成命令を特定する仕組みを説明するための図である。図１では、メインメモリに展開されたサンプルプログラムを示しており、同図に示される番号0x00004020〜0x000040a0はメモリアドレス（プログラムカウンタの値）を表している。サンプルプログラムは、0x00004020から下に向かって順に実行させる。【００３２】
ここで、図１に示したサンプルプログラムに含まれる各種の命令について説明する。「move」は、レジスタ間でデータをコピーする命令である。図１に示される「move  r1=r2」という表現は、レジスタ２番の値をレジスタ１番に代入するという意味である。【００３３】
「add」は、加算命令である。「add  r2＝r2+r3」という表現は、レジスタ２番の値とレジスタ３番の値とを加算した結果をレジスタ２番に格納するという意味である。「load」は、メモリアクセスを行う命令（メモリアクセス命令）である。「[r1]」という表現は、レジスタ１番の値をアドレスとするメモリの値を意味する。【００３４】
したがって、図１に示される「load  r4=[r1]」は、レジスタ１番の値をアドレスとみなし、そのアドレスのメモリから読み出した値をレジスタ４番に格納するという意味である。以上を踏まえてサンプルプログラムについて説明する。【００３５】
プロセッサは、プログラムに含まれる命令を実行する際、レジスタを更新する命令（レジスタ更新命令）であれば、レジスタ・プロデューサ・テーブルの対応する領域（エントリ）にレジスタ更新命令のアドレスを書き込む。図２は、レジスタ・プロデューサ・テーブルのデータ構造の一例を示す図である。【００３６】
レジスタ・プロデューサ・テーブルは、プロセッサに含まれるレジスタの数だけのエントリを持ち、それぞれのエントリにはレジスタを最後に更新したレジスタ更新命令のアドレスを格納する。図２に示す例では、レジスタ１番のレジスタ更新命令のアドレスは、「0x00004020」となっている。レジスタ・プロデューサ・テーブルには、各々のレジスタを最後に更新したレジスタ更新命令のアドレスが書き込まれている状態となる。【００３７】
レジスタ・プロデューサ・テーブルの更新処理は、全ての命令において常に実施される。図３は、レジスタ・プロデューサ・テーブルの更新処理を説明するための図である。同図に示すように、メモリアドレス（プログラムカウンタ）「0x00004028」の「move」命令は、レジスタ３番を更新しているので、レジスタ更新命令となる。したがって、レジスタ・プロデューサ・テーブルのレジスタ３番に対応するエントリに、かかる「move」命令のアドレス「0x00004028」が登録される。【００３８】
ここで、上記したレジスタ・プロデューサ・テーブルの更新処理を、図１に示したサンプルプログラムを用いて説明すると、サンプルプログラムの１段目では、レジスタ１番が更新されているため、１段目の命令「move」はレジスタ更新命令となる。したがって、レジスタ・プロデューサ・テーブルのレジスタ１番に対応するエントリに、かかる「move」命令のアドレス「0x00004020」が登録される。【００３９】
同様に、サンプルプログラムの２，３段目の命令「add」、「move」もそれぞれ、レジスタ２番，３番を更新する命令であるため、レジスタ更新命令となり、各命令のアドレスがレジスタの番号に対応するエントリに登録される。【００４０】
次に、アドレス生成命令を特定する処理について説明する。図４は、アドレス生成命令を特定する処理を説明するための図である。プロセッサがアドレス生成命令を特定する場合には、まず、プログラムに含まれる命令からメモリアクセス命令を検出する。【００４１】
図４に示す例では、メモリアドレス「0x000040a0」の「load」命令が、レジスタ１番に格納されているアドレスの値をレジスタ４番に代入しているため（レジスタによって間接的に指定されるアドレスにアクセスするため）、かかる「load」命令は、メモリアクセス命令となる。【００４２】
プロセッサは、メモリアクセス命令を検出した後に、検出したメモリアクセス命令によって参照されるレジスタの番号（図４に示す例では、レジスタ１番）と、レジスタ・プロデューサ・テーブルとを比較して、かかるレジスタ番号のレジスタを最後に更新したレジスタ更新命令を特定し、特定したレジスタ更新命令をアドレス生成命令として特定する。【００４３】
ここで、図１に示したサンプルプログラムを用いて、アドレス生成命令を特定する処理について説明する。図１のサンプルプログラムにおいて、メモリアクセス命令に該当する命令は、「load」命令である。【００４４】
そして、プロセッサは、メモリアクセス命令を検出した後に、検出したメモリアクセス命令によって参照されるレジスタの番号を特定する。図１のサンプルプログラムでは、メモリアクセス命令「load」によって参照されるレジスタ番号はレジスタ１番となる。【００４５】
プロセッサは、メモリアクセス命令によって参照されるレジスタ番号を特定した後に、特定したレジスタ番号とレジスタ・プロデューサ・テーブル（図２参照）とを比較して、かかるレジスタ番号のレジスタを最後に更新したレジスタ更新命令を特定し、特定したレジスタ更新命令をアドレス生成命令として特定する。図１に示すサンプルプログラムでは、１段目（メモリアドレス「0x00004020」）の「move」命令がアドレス生成命令となる。【００４６】
次に、本実施例１にかかるプロセッサが実施する命令書き換え処理について説明する。上述したアドレス生成命令を特定する方法では、「load」命令を実施して初めて、「move」命令がアドレス生成命令であると判定できた。しかし、プリフェッチを「move」命令の直後に実行するためには、かかる「move」命令がアドレス生成命令であると事前に判別できていなければならない。【００４７】
本実施例１にかかるプロセッサは、アドレス生成命令を特定した場合に、本来の処理に加え、演算後にプリフェッチを行う特殊な命令に書き換える。図５は、命令の書き換え処理を説明するための図である。【００４８】
図５に示すように、例えば、上記の説明のように、メモリアクセス命令を特定した後、レジスタ更新命令のアドレス「0x00004020」がアドレス生成命令のアドレスと判定した場合には、メモリアドレス「0x00004020」にアクセスし、かかるアドレスに登録される命令を書き換える。【００４９】
図５に示す例では、「move」命令を、「pmove」命令に書き換えている。プロセッサが「pmove」命令を読み出した場合には、本来の「move」命令に相当する処理を実行すると共に、更新したレジスタの値（図５では、レジスタ１番の値）をキャッシュにプリフェッチする。【００５０】
このように、本実施例２にかかるプロセッサは、アドレス生成命令を特定し、特定したアドレス生成命令を書き換えているので、次回、アドレス生成命令を読み出した後に、アドレス生成命令に更新されたレジスタの値をプリフェッチすることができ、後のメモリアクセス命令でプリフェッチした値を利用することができるので、プロセッサの処理効率を向上させることができる。【００５１】
次に、上述したプロセッサの構成の一例について説明する。図６は、本実施例１にかかるプロセッサの構成を示す機能ブロック図である。同図に示すように、プロセッサ１００は、Ｉ／Ｏ制御部１１０と、レジスタ部１２０と、制御部１３０と、演算部１４０と、レジスタ・プロデューサ・テーブル記憶部１５０と、データ依存解析部１６０とを備えて構成される。【００５２】
そして、プロセッサ１００は、キャッシュ２００に接続され、キャッシュ２００は、メインメモリ３００に接続されている。キャッシュ２００、メインメモリ３００は、プロセッサ１００によって利用される命令やデータなどを記憶する記憶装置である。図６では、１段のキャッシュ２００が描かれているが、このキャッシュ２００については何段であっても構わない。【００５３】
Ｉ／Ｏ制御部１１０は、プロセッサ１００とキャッシュ２００との間で実行されるデータの入出力を制御する手段である。また、Ｉ／Ｏ制御部１１０は、プリフェッチ制御部１１０ａを備える。プリフェッチ制御部１１０ａは、データ依存解析部１６０からプリフェッチ対象となるメモリアドレスを取得した場合に、該当アドレスに登録されたデータをプリフェッチする手段である。【００５４】
制御部１３０は、キャッシュ２００あるいはメインメモリ３００から命令を読み出して命令を解釈し、命令に応じた各種の処理を実行する制御手段である。レジスタ部１２０は、複数のレジスタ（汎用レジスタ、プログラムカウンタ等）から構成され、制御部１３０等で使用する命令、データを記憶する記憶手段である。【００５５】
演算部１４０は、制御部１３０からの制御命令を取得して各種演算処理を実行し、演算結果をレジスタ部１２０あるいは制御部１３０に出力する手段である。レジスタ・プロデューサ・テーブル記憶部１５０は、図２において説明したレジスタ・プロデューサ・テーブルを記憶する記憶手段である。【００５６】
データ依存解析部１６０は、アドレス生成命令を特定し、特定したアドレス生成命令に対応するメインメモリ３００上の命令を書き換える手段である。具体的に、データ依存解析部１６０の処理について説明すると、データ依存解析部１６０は、メインメモリ３００あるいはキャッシュ２００に記憶されたプログラムを読み出して、レジスタ更新命令を特定し、特定したレジスタ更新命令のアドレスをレジスタ・プロデューサ・テーブルに登録する。【００５７】
また、データ依存解析部１６０は、プログラムの依存関係を解析し、上記した手法によってアドレス生成命令を特定し（図４参照）、メインメモリ３００上のアドレス生成命令を特殊な命令に書き換える（図５参照）。そして、データ依存解析部１６０は、プログラムが実行される過程において、アドレス生成命令となる命令を検出した場合には、アドレス生成命令によって更新されるレジスタの値をプリフェッチすべく、プリフェッチ制御部１１０ａに制御命令を出力する（プリフェッチ対象となるデータのアドレスをプリフェッチ制御部１１０ａに出力する）。【００５８】
次に、本実施例１にかかるプロセッサ１００の処理手順について説明する。図７は、本実施例１にかかるプロセッサの処理手順を示すフローチャートである。同図に示すように、プロセッサ１００は、命令を読み出し（ステップＳ１０１）、読み出した命令がload／store命令（あるいはメモリアクセス命令）か否かを判定する（ステップＳ１０２）。【００５９】
load／store命令（あるいはメモリアクセス命令）である場合には（ステップＳ１０３，Ｙｅｓ）、命令で指定された読み出し元のメモリアドレスを指定するレジスタ番号を特定し（ステップＳ１０４）、レジスタ番号に対応するレジスタ・プロデューサ・テーブル内のエントリを調べる（ステップＳ１０５）。【００６０】
そして、プロセッサ１００は、エントリに書かれたレジスタ更新命令のアドレスをアドレス生成命令のアドレスとして検出し（ステップＳ１０６）、検出した命令を「本来の命令と同様の処理を行った後に演算結果をメモリアドレスとみなしプリフェッチを行う命令」に書き換え（ステップＳ１０７）、ステップＳ１０８に移行する。【００６１】
一方、load／store命令（あるいはメモリアクセス命令）でない場合には（ステップＳ１０３，Ｎｏ）、レジスタ変更を伴う命令か否かを判定し（ステップＳ１０８）、レジスタ変更を伴う場合には（ステップＳ１０９，Ｙｅｓ）、レジスタ・プロデューサ・テーブル更新処理を実行し（ステップＳ１１０）、ステップＳ１１１に移行する。【００６２】
一方、レジスタ値変更を伴う命令でない場合には（ステップＳ１０９，Ｎｏ）、命令を実施し（ステップＳ１１１）、次の命令を読み出し（ステップＳ１１２）、ステップＳ１０２に移行する。【００６３】
次に、図７のステップＳ１１０に示したレジスタ・プロデューサ・テーブル更新処理について説明する。図８は、レジスタ・プロデューサ・テーブル更新処理を示すフローチャートである。【００６４】
図８に示すように、プロセッサ１００は、命令（レジスタ更新命令）で指定された書き込みレジスタ番号を特定し（ステップＳ２０１）、プログラムカウンタから命令のアドレスを読み出す（ステップＳ２０２）。【００６５】
そして、プロセッサ１００は、レジスタ番号に対応するレジスタ・プロデューサ・テーブル内のエントリに命令のアドレスを書き込み（ステップＳ２０３）、レジスタ・プロデューサ・テーブル更新処理を終了する。【００６６】
上述してきたように、本実施例１にかかるプロセッサ１００は、メインメモリ３００からプログラムを読み出してレジスタ更新命令を検出し、レジスタ・プロデューサ・テーブル記憶部１５０にレジスタ更新命令のアドレスを登録する。また、プロセッサ１００は、プログラムを読み出してメモリアクセス命令を検出し、検出したメモリアクセス命令が利用するレジスタの番号とレジスタ・プロデューサ・テーブルとを比較してアドレス生成命令を特定し、アドレス生成命令に対応する命令を書き換えるので、一般的なアプリケーションで見受けられる不規則なメモリアクセスを見抜き、効果的なハードウェア・プリフェッチを行うことができる。
【実施例２】
【００６７】
次に、本実施例２にかかるプロセッサの概要および特徴について説明する。本実施例２にかかるプロセッサは、上記した実施例１と同様の手法を用いて、アドレス生成命令を特定する。そして、本実施例２にかかるプロセッサは、特定したアドレス生成命令を記録するために、キャッシュ上に付加情報を保持させる。【００６８】
キャッシュ情報の保持の仕方は様々なものが考えられるが、ここでは説明を簡単にするため、ダイレクトマップ方式のキャッシュを前提とする。なお、セットアソシアティブ方式などでも、キャッシュ情報を検索する部分を、それぞれの方式に読み替えることで、同様に実現できる。【００６９】
ここで、キャッシュに記憶されるキャッシュ情報について説明する。図９は、キャッシュ情報のデータ構造の一例を示す図である。同図に示すように、このキャッシュ情報は、タグと、状態と、アドレス生成フラグと、命令ワードとから構成される。【００７０】
このうち、タグは、該当ラインが要求された命令に対応するものか判別するためのアドレス情報を記憶するものである。また、状態は、該当ラインの状態を示す情報であり、CLEAN、DIRTY、INVALIDなどが格納される。【００７１】
アドレス生成フラグは、対応する命令ワードがアドレス生成命令か否かを示す情報を格納しており、命令ワードは、各種の処理を実行するための命令を格納している。図９に示した例では、各命令ワードと各アドレス生成フラグが対応付けられているものとする。アドレス生成フラグが「TRUE」となる命令ワードが、アドレス生成命令となる。【００７２】
次に、本実施例２にかかるプロセッサがキャッシュ情報のアドレス生成フラグを更新する処理について説明する。図１０は、プロセッサがキャッシュ情報のアドレス生成フラグを更新する処理を説明するための図である。図１０に示す例では、アドレス生成命令のアドレスを、１５bit、８bit、９bitに区切り、それぞれを、タグ、インデックス、ライン内インデックスとしているが、これに限定されるものではなく、キャッシュ方式の違いや、ラインサイズの違いなどによって区切り方が変化する。【００７３】
プロセッサは、アドレス生成命令のインデックスを参照し、インデックスに対応するキャッシュラインにアクセスする。そして、キャッシュラインに記憶されたキャッシュ情報のタグの値とアドレス生成命令のタグとを比較して一致するか否かを判定し、一致している場合には、該当アドレスを含むラインがキャッシュ上に存在すると判定する。【００７４】
その後、プロセッサは、アドレス生成命令アドレスのライン内インデックスに格納された値を基にして、該当ラインのアドレス生成フラグを「FALSE」から「TRUE」に変換する。例えば、図１０に示すアドレス生成命令のアドレスによって、キャッシュ情報のアドレス生成フラグ（キャッシュ情報の上から４段目、左から２列目のアドレス生成フラグ）を「TRUE」に変換した場合には、命令ワードの左から２列目の命令ワードがアドレス生成命令に対応することとなる。【００７５】
次に、上述したプロセッサの構成の一例について説明する。図１１は、本実施例２にかかるプロセッサの構成を示す機能ブロック図である。同図に示すように、このプロセッサ４００は、Ｉ／Ｏ制御部４１０と、レジスタ部４２０と、制御部４３０と、演算部４４０と、レジスタ・プロデューサ・テーブル記憶部４５０と、データ依存解析部４６０とを備えて構成される。【００７６】
このうち、Ｉ／Ｏ制御部４１０、レジスタ部４２０、制御部４３０、演算部４４０、レジスタ・プロデューサ・テーブル記憶部４５０に関する説明は、図６に示したＩ／Ｏ制御部１１０、レジスタ部１２０、制御部１３０、演算部１４０、レジスタ・プロデューサ・テーブル記憶部１５０に関する説明と同様であるため説明を省略する。【００７７】
データ依存解析部４６０は、アドレス生成命令を特定し、特定したアドレス生成命令のアドレスを基にしてキャッシュ２００に記憶されたキャッシュ情報のアドレス生成フラグを変換する手段である。具体的に、データ依存解析部４６０は、メインメモリ３００あるいはキャッシュ２００に記憶されたプログラムを読み出して、レジスタ更新命令を特定し、特定したレジスタ更新命令のアドレスをレジスタ・プロデューサ・テーブルに登録する。【００７８】
また、データ依存解析部４６０は、プログラムの依存関係を解析し、実施例１で示した手法によってアドレス生成命令を特定し（図４参照）、キャッシュ２００のキャッシュ情報のアドレス生成フラグを更新する（図１０参照）。データ依存解析部４６０は、キャッシュ２００に記憶されたキャッシュ情報が読み出され、命令が実行される場合に、アドレス生成フラグと命令ワードとを比較する。【００７９】
そして、アドレス生成命令が「TRUE」となる命令である場合には、該当命令がアドレス生成命令であると判定し、アドレス生成命令によって更新されるレジスタの値をプリフェッチすべく、プリフェッチ制御部４１０ａに制御命令を出力する（プリフェッチ対象となるデータのアドレスをプリフェッチ制御部４１０ａに出力する）。【００８０】
次に、本実施例２にかかるプロセッサ４００の処理手順について説明する。図１２、図１３は、本実施例２にかかるプロセッサ４００の処理手順を示すフローチャートである。同図に示すように、プロセッサ４００は、命令を読み出し（ステップＳ３０１）、読み出した命令がload／store命令（あるいはメモリアクセス命令）か否かを判定する（ステップＳ３０２）。【００８１】
load／store命令（あるいはメモリアクセス命令）である場合には（ステップＳ３０３，Ｙｅｓ）、アドレスとして使用されるレジスタ番号を命令から特定し（ステップＳ３０４）、レジスタ・プロデューサ・テーブルを参照し、最終更新を行った命令（アドレス生成命令）のアドレスを調べる（ステップＳ３０５）。【００８２】
そして、プロセッサ４００は、アドレス生成命令のアドレスからメモリ読み出しを行い、アドレス生成命令を特定し（ステップＳ３０６）、アドレス生成命令のアドレスを、桁で分割し、上位１５bitをタグ、下位９bitをライン内インデックス、残った８bitをインデックスとする（ステップＳ３０７）。【００８３】
プロセッサ４００は、キャッシュ情報をアドレス生成命令のインデックスにより参照し（ステップＳ３０８）、参照したキャッシュ情報中のタグの値と、アドレス生成命令のタグ値とを比較し（ステップＳ３０９）、タグが一致していない場合には（ステップＳ３１０，Ｎｏ）、ステップＳ３１４に移行する。【００８４】
一方、タグが一致している場合には（ステップＳ３１０，Ｙｅｓ）、参照したキャッシュ情報内のアドレス生成フラグを更新対象と判定し（ステップＳ３１１）、更新するフラグをライン内インデックスで示す値とし（ステップＳ３１２）、ライン内インデックスが示すアドレス生成フラグをTUREに更新し（ステップＳ３１３）、ステップＳ３１４に移行する。【００８５】
ところで、load／store命令（あるいはメモリアクセス命令）でない場合には（ステップＳ３０３，Ｎｏ）、レジスタ変更を伴う命令か否かを判定し（ステップＳ３１４）、レジスタ変更を伴う場合には（ステップＳ３１５，Ｙｅｓ）、レジスタ・プロデューサ・テーブル更新処理を実行し（ステップＳ３１６）、ステップＳ３１７に移行する。【００８６】
一方、レジスタ変更を伴う命令でない場合には（ステップＳ３１５，Ｎｏ）、命令を実施し（ステップＳ３１７）、実施した命令がアドレス生成命令か否かを判定し（ステップＳ３１８）、アドレス生成命令である場合には（ステップＳ３１９，Ｙｅｓ）、プリフェッチを実施し（ステップＳ３２０）、ステップＳ３２１に移行する。【００８７】
一方、アドレス生成命令でない場合には（ステップＳ３１９，Ｎｏ）、次の命令を読み出し（ステップＳ３２１）、ステップＳ３０２に移行する。なお、図１３のステップＳ３１６に示したレジスタ・プロデューサ・テーブル更新処理は、図８において説明した処理に対応するため、説明を省略する。【００８８】
上述してきたように、本実施例２にかかるプロセッサ４００は、メインメモリ３００からプログラムを読み出してレジスタ更新命令を検出し、レジスタ・プロデューサ・テーブル記憶部４５０にレジスタ更新命令のアドレスを登録する。また、プロセッサ４００は、プログラムを読み出してメモリアクセス命令を検出し、検出したメモリアクセス命令が利用するレジスタの番号とレジスタ・プロデューサ・テーブルとを比較してアドレス生成命令を特定し、キャッシュ２００のアドレス生成フラグを変換するので、命令実行時にかかるアドレス生成フラグを利用することにより、一般的なアプリケーションで見受けられる不規則なメモリアクセスを見抜き、効果的なハードウェア・プリフェッチを行うことができる。
【実施例３】
【００８９】
次に、本実施例３にかかるプロセッサの概要および特徴について説明する。本実施例３にかかるプロセッサは、上記した実施例１と同様の手法を用いて、アドレス生成命令を特定する。そして、本実施例３にかかるプロセッサは、特定したアドレス生成命令のアドレスをアドレス生成命令テーブルに登録する。【００９０】
図１４は、アドレス生成命令テーブルのデータ構造の一例を示す図である。同図に示すように、このアドレス生成命令テーブルは、アドレス生成命令のアドレスを格納している。アドレス生成命令テーブルの構成方法については、キャッシュ同様にダイレクト方式、セットアソシアティブ方式、フルアソシアディブ方式などが考えられるが、本実施例３では、ダイレクト方式を例にしている。【００９１】
次に、本実施例３にかかるプロセッサがアドレス生成テーブルを参照する方法について説明する。図１５は、プロセッサがアドレス生成テーブルを参照する方法を説明するための図である。同図に示すように、プロセッサは、アドレス生成命令の一部をインデックスとして解釈し、そのインデックスでアドレス生成命令テーブルを参照する。アドレス生成命令のアドレスを登録する場合には、かかるインデックスで示されたアドレス生成命令テーブルのエントリを登録するアドレスで上書きすればよい。【００９２】
また、アドレス生成命令か否かを判定する場合には、調査対象の命令のアドレスを特定し、そのアドレスから得られたインデックスを用いてアドレス生成テーブルを参照する。書かれたアドレスが調査対象の命令のアドレスと一致するならば、該当命令はアドレス生成命令であると判定できる。【００９３】
次に、上述したプロセッサの構成の一例について説明する。図１６は、本実施例３にかかるプロセッサの構成を示す機能ブロック図である。同図に示すように、このプロセッサ５００は、Ｉ／Ｏ制御部５１０と、レジスタ部５２０と、制御部５３０と、演算部５４０と、レジスタ・プロデューサ・テーブル記憶部５５０と、アドレス生成命令テーブル記憶部５６０と、データ依存解析部５７０とを備えて構成される。【００９４】
このうち、Ｉ／Ｏ制御部５１０、レジスタ部５２０、制御部５３０、演算部５４０、レジスタ・プロデューサ・テーブル記憶部５５０に関する説明は、図６に示したＩ／Ｏ制御部１１０、レジスタ部１２０、制御部１３０、演算部１４０、レジスタ・プロデューサ・テーブル記憶部１５０に関する説明と同様であるため説明を省略する。【００９５】
アドレス生成命令テーブル記憶部５６０は、図１４に示したアドレス生成命令テーブルを記憶する記憶手段である。【００９６】
データ依存解析部５７０は、アドレス生成命令を特定し、特定したアドレス生成命令のアドレスをアドレス生成命令テーブルに記憶する手段である。具体的に、データ依存解析部５７０は、メインメモリ３００あるいはキャッシュ２００に記憶されたプログラムを読み出して、レジスタ更新命令を特定し、特定したレジスタ更新命令のアドレスをレジスタ・プロデューサ・テーブルに登録する。【００９７】
また、データ依存解析部５７０は、プログラムの依存関係を解析し、実施例１で示した手法によってアドレス生成命令を特定し（図４参照）、アドレス生成命令テーブル記憶部５６０に記憶されたアドレス生成命令テーブルにアドレス生成命令のアドレスを登録する（図１４参照）。データ依存解析部５７０は、プログラムを読み出して命令を実行する場合に、命令のアドレスとアドレス生成命令テーブルとを比較する。【００９８】
そして、命令のアドレスに含まれるインデックスがアドレス生成命令テーブルに存在する場合には、該当命令がアドレス生成命令であると判定し、アドレス生成命令によって更新されるレジスタの値をプリフェッチすべく、プリフェッチ制御部５１０ａに制御命令を出力する（プリフェッチ対象となるデータのアドレスをプリフェッチ制御部５１０ａに出力する）。【００９９】
次に、本実施例３にかかるプロセッサ５００の処理手順について説明する。図１７、図１８は、本実施例３にかかるプロセッサ５００の処理手順を示すフローチャートである。同図に示すように、プロセッサ５００は、命令を読み出し（ステップＳ４０１）、読み出した命令がload／store命令（あるいはメモリアクセス生命）か否かを判定する（ステップＳ４０２）。【０１００】
load／store命令（あるいはメモリアクセス命令）である場合には（ステップＳ４０３，Ｙｅｓ）、アドレスとして使用されるレジスタ番号を命令から特定し（ステップＳ４０４）、レジスタ・プロデューサ・テーブルを参照し、最終更新を行った命令のアドレスを調べる（ステップＳ４０５）。【０１０１】
そして、プロセッサ５００は、アドレス生成命令のアドレスからメモリ読み出しを行い、アドレス生成命令を特定し（ステップＳ４０６）、アドレス生成命令のアドレスを桁で分割し、bit８からbit２０までの１３bitで構成した値を「インデックス」として用いる（ステップＳ４０７）。【０１０２】
プロセッサ５００は、アドレス生成命令テーブルに対して参照するエントリをインデックスにより決定し（ステップＳ４０８）、決定したエントリに、アドレス生成命令のアドレスを書き込み（ステップＳ４０９）、ステップＳ４１０に移行する。【０１０３】
ところで、load／store命令（あるいはメモリアクセス命令）でない場合には（ステップＳ４０３，Ｎｏ）、レジスタ変更を伴う命令か否かを判定し（ステップＳ４１０）、レジスタ変更を伴う場合には（ステップＳ４１１，Ｙｅｓ）、レジスタ・プロデューサ・テーブル更新処理を実行し（ステップＳ４１２）、ステップＳ４１３に移行する。【０１０４】
一方、レジスタ変更を伴う命令でない場合には（ステップＳ４１１，Ｎｏ）、命令を実施し（ステップＳ４１３）、調査対象の命令のアドレスを桁で分割し、bit８からbit２０までの１３bitで構成した値をインデックスとして用いる（ステップＳ４１４）。【０１０５】
続いて、プロセッサ５００は、アドレス生成命令テーブルに対して参照するエントリをインデックスにより決定し（ステップＳ４１５）、決定したエントリの値が、調査対象のアドレスと一致するか否かを判定する（ステップＳ４１６）。【０１０６】
アドレスが一致した場合には（ステップＳ４１７，Ｙｅｓ）、プリフェッチを実施し（ステップＳ４１８）、ステップＳ４１９に移行する。一方、アドレスが一致しない場合には（ステップＳ４１７，Ｎｏ）、次の命令を読み出し（ステップＳ４１９）、ステップＳ４０２に移行する。なお、図１８のステップＳ４１２に示したレジスタ・プロデューサ・テーブル更新処理は、図８において説明した処理に対応するため、説明を省略する。【０１０７】
上述してきたように、本実施例３にかかるプロセッサ５００は、メインメモリ３００からプログラムを読み出してレジスタ更新命令を検出し、レジスタ・プロデューサ・テーブル記憶部５５０にレジスタ更新命令のアドレスを登録する。また、プロセッサ５００は、プログラムを読み出してメモリアクセス命令を検出し、検出したメモリアクセス命令が利用するレジスタの番号とレジスタ・プロデューサ・テーブルとを比較してアドレス生成命令を特定し、アドレス生成命令のアドレスをアドレス生成命令テーブルに登録するので、命令実行時にかかるアドレス生成命令テーブルを利用することにより、一般的なアプリケーションで見受けられる不規則なメモリアクセスを見抜き、効果的なハードウェア・プリフェッチを行うことができる。
【実施例４】
【０１０８】
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例１〜３以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下では実施例４として本発明に含まれる他の実施例を説明する。【０１０９】
（１）アドレス生成命令に着目したコンパイラによる最適化
コンパイラがソースプログラムをコンパイルする場合に、命令間の依存関係を解析して、アドレス生成命令を検出し、高速なメモリアクセスを実現したアプリケーションプログラムを生成することができる。アドレス生成命令を検出する手法は、実施例１〜３に示した手法と同様の手法を用いることができる。【０１１０】
アドレス生成命令を検出した場合には、コンパイラは、アドレス生成命令の入力データを計算する命令を優先的にアプリケーションプログラムに配置する、あるいは、アドレス生成命令の直後に、アドレス生成命令によって更新されたデータをプリフェッチする命令を挿入するなどの最適化を行うことで、効率的なプリフェッチを行うことができるアプリケーションを生成することができる。【０１１１】
かかるコンパイラにより生成されたアプリケーションプログラムは、メモリアクセスが発生する際、そのメモリアドレスが確定した時点でデータの先読みを開始する。また、メモリアドレス確定のために必要な処理は、なるべく優先して処理されるように命令を並び替えているため、この先読み処理の可能な限り速い時期にスタートできる。これにより、コンパイラにより生成されたアプリケーションプログラムは、最適なタイミングでデータを先読みし、高速なデータ読み出しを実現することができる。【０１１２】
（２）仮想マシン上での実現
前提として、キャッシュ機構を持つプロセッサ上に実装された仮想マシンを考える。この仮想マシンは、実施例１〜３に示した手法と同様の手法を用いてアドレス生成命令を検出する。かかる仮想マシンは、仮想マシン上で動作するバイナリからアドレス生成命令の検出を行い、実機上のメモリシステムに対して、仮想マシン上のメモリアクセスに対応するデータのプリフェッチを実施する。【０１１３】
仮想マシンは、仮想マシン上で実行中のプログラムについて、データフローの解析を行い、実施例１〜３のシステムと同様、自動的なプリフェッチを実現している。そのため、仮想マシン上で動作するプログラムも、メモリアクセスが最適化され、高速に動作することが可能となる。なお、仮想マシンのプログラムは、例えば、メインメモリに記憶され、プロセッサに読み出されて実行されるものとする。【０１１４】
（３）Just  In  Timeコンパイル環境上での実現
前提として、キャッシュ機構をもつプロセッサ上に実装された仮想マシンを考える。この仮想マシンはJust  In  Timeコンパイル機能を有する。また、上記した仮想マシンと同様に実施例１〜３と同様の手法を用いてアドレス生成命令を検出する。【０１１５】
そして、仮想マシンは、Just  In  Timeコンパイル時において、アドレス生成命令の直後に演算結果のアドレスに対してプリフェッチを行う命令を付加する。変換後のプリフェッチ命令が有効に機能しない場合は、改めて変換した命令列の中から、プリフェッチ命令を取り除けばよい。これにより、仮想マシンは高速なメモリアクセスや命令実行を実現することができる。【０１１６】
（４）システムの構成等
本実施例において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。この他、上記文章中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。【０１１７】
また、図示したプロセッサ１００，４００，５００の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況に応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行われる各処理機能は、その全部または任意の一部が、ＣＰＵおよび該当ＣＰＵにて解析実行されるプログラム（例えば、仮想マシン）にて実現され得る。【０１１８】
なお、本実施例で説明した各種の処理手順は、予め用意されたプログラムをコンピュータで実行することによって実現することができる。このプログラムは、インターネットなどのネットワークを介して配布することができる。また、このプログラムは、ハードディスク、フレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記憶媒体に記録され、コンピュータによって記憶媒体から読み出されることによって実行することもできる。
【産業上の利用可能性】
【０１１９】
以上のように、本発明にかかるプロセッサおよびプリフェッチ支援プログラムは、プリフェッチを実施するプロセッサに対して有用であり、特に、一般的なアプリケーションで見受けられる不規則なメモリアクセスを見抜き、効果的なハードウェア・プリフェッチを行う場合に適している。
【図１】
2008155812.tif 000003
【図２】
2008155812.tif 000004
【図３】
2008155812.tif 000005
【図４】
2008155812.tif 000006
【図５】
2008155812.tif 000007
【図６】
2008155812.tif 000008
【図７】
2008155812.tif 000009
【図８】
2008155812.tif 000010
【図９】
2008155812.tif 000011
【図１０】
2008155812.tif 000012
【図１１】
2008155812.tif 000013
【図１２】
2008155812.tif 000014
【図１３】
2008155812.tif 000015
【図１４】
2008155812.tif 000016
【図１５】
2008155812.tif 000017
【図１６】
2008155812.tif 000018
【図１７】
2008155812.tif 000019
【図１８】
2008155812.tif 000020
【手続補正書】
【提出日】平成21年10月14日(2009.10.14)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
記憶装置の情報を予めキャッシュに格納するプリフェッチ機能を有するプロセッサであって、
記憶装置に記憶されたプログラムを読み出して命令を実行する場合に、当該命令がレジスタの値を更新する命令であると判定すると、前記レジスタの識別情報と前記命令とを対応付けてレジスタ・プロデューサ・テーブルに記憶する記憶制御手段と、
前記記憶装置に記憶されたプログラムを読み出して命令を実行する場合に、当該命令がレジスタによって間接的に指定されるアドレスにアクセスする命令であると判定すると、前記アドレスを間接的に指定するレジスタの識別情報と前記レジスタ・プロデューサ・テーブルとを基にして前記レジスタを更新した命令をアドレス生成命令として特定する命令特定手段と、
前記アドレス生成命令によって更新されたレジスタの値をプリフェッチするプリフェッチ手段と、
を備えたことを特徴とするプロセッサ。
【請求項２】
前記命令特定手段は、前記プログラムに含まれる命令のうち、前記アドレス生成命令に対応する命令を、本来の命令と同様の処理を行った後に演算結果をメモリアドレスとみなしプリフェッチを実行する命令に書き換え、前記プリフェッチ手段は、前記書き換えられた命令に基づいてプリフェッチすることを特徴とする請求項１に記載のプロセッサ。
【請求項３】
前記命令特定手段は、前記キャッシュに格納された命令のうち、前記アドレス生成命令に対応する命令に、当該命令がアドレス生成命令である旨の付加情報を付加し、前記プリフェッチ手段は、前記付加情報が付加された命令によって更新されたレジスタの値をプリフェッチすることを特徴とする請求項１に記載のプロセッサ。
【請求項４】
前記命令特定手段は、前記アドレス生成命令として特定した命令をアドレス生成テーブルに登録し、前記プリフェッチ手段は、前記アドレス生成テーブルに登録された命令を実行する場合に、当該命令によって更新されたレジスタの値をプリフェッチすることを特徴とする請求項１に記載のプロセッサ。
【請求項５】
コンピュータに、
記憶装置に記憶されたプログラムを読み出して命令を実行する場合に、当該命令がレジスタの値を更新する命令であると判定すると、前記レジスタの識別情報と前記命令とを対応付けてレジスタ・プロデューサ・テーブルに記憶する記憶制御手順と、
前記記憶装置に記憶されたプログラムを読み出して命令を実行する場合に、当該命令がレジスタによって間接的に指定されるアドレスにアクセスする命令であると判定すると、前記アドレスを間接的に指定するレジスタの識別情報と前記レジスタ・プロデューサ・テーブルとを基にして前記レジスタを更新した命令をアドレス生成命令として特定する命令特定手順と、
前記アドレス生成命令によって更新されたレジスタの値をプリフェッチするプリフェッチ手順と、
を実行させるためのプリフェッチ支援プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記憶装置の情報を予めキャッシュに格納するプリフェッチ機能を有するプロセッサ等に関するものである。
【背景技術】
【０００２】
昨今の計算機システムでは、メモリと演算器の速度差を隠蔽するために、キャッシュ機構を導入している。キャッシュとは、頻繁に利用するデータを一時的に格納するための、小容量かつ高速なメモリを示す。このキャッシュを効果的に利用することが、システム全体の性能を引き上げるために大きく寄与する。
【０００３】
キャッシュを有効利用するためのアプローチには大きく２つある。１つは、一度キャッシュに載せたデータのうち、再利用する可能性の高いデータをなるべくキャッシュの外に追い出さないようにするアプローチである。もう１つは、近い将来利用する可能性の高いデータを、事前に遅いメモリから速いキャッシュへ転送するアプローチである。後者のアプローチの代表的な手法がプリフェッチと呼ばれる手法である（例えば、特許文献１、特許文献２参照）。
【０００４】
キャッシュ機構を有する計算機システムは、小さいが高速なメモリをプロセッサの近い場所に、大きいが低速なメモリをプロセッサの遠い場所に配置し、頻繁に利用されるデータほどプロセッサに近いメモリにコピーしておく。これにより理想的には全てのメモリが近い高速なメモリに載っている状態にできる。今日の計算機システムにおいては、様々な工夫によりこの理想状態に近いアクセス時間を実現している。このような階層的なメモリの仕組みをキャッシュと呼ぶ。キャッシュ機構を有する計算機システムについては、非特許文献１参照。
【０００５】
また、スーパースカラ・プロセッサにおけるアウト・オブ・オーダー技術をはじめとするマイクロアーキテクチャの詳細は非特許文献２に記述されている。アウト・オブ・オーダー技術とは、キャッシュミスなど、コンパイル時に予測できない要因に対して、プロセッサ内で実行しながら動的に対処し、命令を最適な実行順序に再構成する技術である。
【０００６】
次に、プリフェッチについて述べる。プリフェッチは、キャッシュアクセスを最適化するための技術の１つである。通常、load命令などメモリからデータを読み出す命令を実行する際、そのデータがキャッシュ上に存在しなければ、メインメモリまでデータを読みに行く。これは、キャッシュ上に存在するデータをアクセスする場合に比べて、非常に時間のかかる処理である。
【０００７】
ところが、事前に読み出すメモリアドレスが判明している場合には、必要なデータをメインメモリからキャッシュまで事前に読み出すことが可能である。通常の処理と平行してメモリからキャッシュへのデータ転送を行う事で、その後該当データを読み出そうとした際に、キャッシュから高速に読み出すことができる。このように、他の処理と平行して、事前にメインメモリからキャッシュまでデータを読み出す処理のことをプリフェッチと呼ぶ。
【０００８】
通常のメモリアクセスでは、データが取得できるまでメモリアクセス命令の実行は完了しない。一方、プリフェッチ処理は、他の命令実行と平行して行われ、データ取得が終わらなくともプロセッサは次の命令処理を継続する。このため、前もってプリフェッチを行っておくことで、必要なときにデータをキャッシュ上に転送しておくことが可能となる。
【０００９】
実際にデータが必要になるまでに、キャッシュへのデータ読み出しが完了していれば、データはキャッシュから高速に読み出される。完了していない場合には、転送が終わるまで待った後にデータが読み込まれる。この場合、プリフェッチが間に合った場合に比べ効果は小さいが、メモリ読み出し処理が命令に先立って開始されているため、プリフェッチ命令を利用しなかった場合に比べ、メモリ読み出しの応答は高速化される。
【００１０】
ここで、プリフェッチについてさらに詳しく説明する。通常、プリフェッチといったとき、大きく分けて２種類のプリフェッチが存在する。ソフトウェア・プリフェッチとハードウェア・プリフェッチである。両者の性能的な比較については非特許文献３を参照。
【００１１】
ソフトウェア・プリフェッチは、非特許文献４、５に記載されているように、コンパイラあるいはプログラマが明示的にプリフェッチ命令を挿入する事で実施される。プログラムの静的な特性に基づき、キャッシュミスの発生しそうな箇所に対し、実際のメモリアクセス命令に対して十分先行した箇所に挿入される。
【００１２】
ハードウェア・プリフェッチは、非特許文献６、７に記載されているように、プロセッサが暗黙的に行うプリフェッチである。アプリケーションの動的な振る舞いから、予測に基づき実施される。連続したストリームメモリアクセスや、一定区間あけながら規則的な連続アクセスを行うストライドメモリアクセスを検出し、それらのアクセスに対して先読みを行うようプリフェッチを実施する。
【００１３】
【特許文献１】特開平７−５６８０９号公報
【特許文献２】特開平１１−１４３７７４号公報
【非特許文献１】John  L.  Hennessy,  and  David  A.  Patterson.  “Computer  Architecture  -  A  Quantitative  Approach  3rd  Edition,”  MORGAN  KAUFMANN  PUBLISHERS,  ISBN  1-55860-724-2.
【非特許文献２】Mike  Johnson.  “Superscalar  Microprocessor  Design,”  Prentice-Hallm  Inc,  ISBN  0138756341.
【非特許文献３】Tien-Fu  Chen,  and  Jean-Loup  Baer.  “A  performance  study  of  software  and  hardware  data  prefetching  schemes,”  Proc.  1994  the  21st  Annual  International  Symposium  on  Computer  Architecture.
【非特許文献４】David  Callahan,  Ken  Kennedy,  and  Allan  Porterfield.  “Software  prefetching,“  ACM  SIGARCH  Computer  Architecture  News  Volume  19,  Issue  2  (April  1991).
【非特許文献５】Todd  C.  Mowry,  Monica  S.  Lam,  and  Anoop  Gupta.  “Design  and  evaluation  of  a  compiler  algorithm  for  prefetching,”  ACM  SIGPLAN  Notices  Volume  27,  Issue  9  (September  1992)
【非特許文献６】Steven  P.  Vanderwiel,  and  David  J.  Lilja.  “Data  Prefetch  mechanisms,“  ACM  Computing  Surveys  Volume  32,  Issue  2  (June  2000).
【非特許文献７】Wei-Fen  Lin,  Steven  K.  Reinhardt,  and  Doug  Burger.  “Designing  a  Modern  Memory  Hierarchy  with  Hardware  Prefetching,”  IEEE  Transactions  on  Computers  Volume  50,  Issue  11  (November  2001).
【発明の開示】
【発明が解決しようとする課題】
【００１４】
しかしながら、上述した従来のハードウェア・プリフェッチ技術では、メモリに対するストリームアクセス、あるいはストライドアクセスに関してのみ、過去のアクセス傾向から予測してプリフェッチを実施する手法であるため、学術計算などメモリアクセスパターンが規則的なアプリケーションでは効果が期待できるが、一般的なアプリケーション（特に、メモリアクセスパターンが不規則なアプリケーション）ではハードウェア・プリフェッチの予測精度が低く、ハードウェア・プリフェッチの効果が低いという問題があった。
【００１５】
すなわち、一般的なアプリケーションで見受けられる不規則なメモリアクセスを見抜き、効果的なハードウェア・プリフェッチを行うことが極めて重要な課題となっている。
【００１６】
本発明は、上記に鑑みてなされたものであって、一般的なアプリケーションで見受けられる不規則なメモリアクセスを見抜き、効果的なハードウェア・プリフェッチを実行可能なプロセッサおよびプリフェッチ支援プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
上述した課題を解決し、目的を達成するために、本発明は、メモリの情報を予めキャッシュに格納するプリフェッチ機能を有するプロセッサであって、メモリに記憶されたプログラムを読み出して命令を実行する場合に、当該命令がレジスタの値を更新する命令であると判定すると、前記レジスタの識別情報と前記命令とを対応付けてレジスタ・プロデューサ・テーブルに記憶する記憶制御手段と、前記メモリに記憶されたプログラムを読み出して命令を実行する場合に、当該命令がレジスタによって間接的に指定されるアドレスにアクセスする命令であると判定すると、前記アドレスを間接的に指定するレジスタの識別情報と前記レジスタ・プロデューサ・テーブルとを基にして前記レジスタを更新した命令をアドレス生成命令として特定する命令特定手段と、前記アドレス生成命令によって更新されたレジスタの値をプリフェッチするプリフェッチ手段と、を備えたことを特徴とする。
【００１８】
また、本発明は、上記発明において、前記命令特定手段は、前記プログラムに含まれる命令のうち、前記アドレス生成命令に対応する命令を、本来の命令と同様の処理を行った後に演算結果をメモリアドレスとみなしプリフェッチを実行する命令に書き換え、前記プリフェッチ手段は、前記書き換えられた命令に基づいてプリフェッチすることを特徴とする。
【００１９】
また、本発明は、上記発明において、前記命令特定手段は、前記キャッシュに格納された命令のうち、前記アドレス生成命令に対応する命令に、当該命令がアドレス生成命令である旨の付加情報を付加し、前記プリフェッチ手段は、前記付加情報が付加された命令によって更新されたレジスタの値をプリフェッチすることを特徴とする。
【００２０】
また、本発明は、上記発明において、前記命令特定手段は、前記アドレス生成命令として特定した命令をアドレス生成テーブルに登録し、前記プリフェッチ手段は、前記アドレス生成テーブルに登録された命令を実行する場合に、当該命令によって更新されたレジスタの値をプリフェッチすることを特徴とする。
【発明の効果】
【００２１】
本発明によれば、メモリに記憶されたプログラムを読み出して命令を実行する場合に、当該命令がレジスタの値を更新する命令であると判定すると、レジスタの識別情報と命令とを対応付けてレジスタ・プロデューサ・テーブルに記憶し、メモリに記憶されたプログラムを読み出して命令を実行する場合に、当該命令がレジスタによって間接的に指定されるアドレスにアクセスする命令であると判定すると、アドレスを間接的に指定するレジスタの識別情報とレジスタ・プロデューサ・テーブルとを基にしてレジスタを更新した命令をアドレス生成命令として特定し、アドレス生成命令によって更新されたレジスタの値をプリフェッチするので、一般的なアプリケーションで見受けられる不規則なメモリアクセスを見抜き、効果的なハードウェア・プリフェッチを行うことができる。
【００２２】
また、本発明によれば、プログラムに含まれる命令のうち、アドレス生成命令に対応する命令を、本来の命令と同様の処理を行った後に演算結果をメモリアドレスとみなしプリフェッチを実行する命令に書き換え、書き換えられた命令に基づいてプリフェッチするので、高速なメモリアクセスを実現することができる。
【００２３】
また、本発明によれば、キャッシュに格納された命令のうち、アドレス生成命令に対応する命令に、命令がアドレス生成命令である旨の付加情報を付加し、付加情報が付加された命令によって更新されたレジスタの値をプリフェッチするので、高速なメモリアクセスを実現することができる。
【００２４】
また、本発明によれば、アドレス生成命令として特定した命令をアドレス生成テーブルに登録し、アドレス生成テーブルに登録された命令を実行する場合に、当該命令によって更新されたレジスタの値をプリフェッチするので、高速なメモリアクセスを実現することができる。
【発明を実施するための最良の形態】
【００２５】
以下に、本発明にかかるプロセッサおよびプリフェッチ支援プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例１】
【００２６】
まず、本実施例１にかかるプロセッサの概要および特徴について説明する。本実施例１にかかるプロセッサは、メインメモリのデータを予めキャッシュに格納するハードウェア・プリフェッチ（以下、プリフェッチと略記する）機能を有するプロセッサであり、メインメモリ（あるいはキャッシュ）に記憶されたプログラムを読み出して命令を実行する場合に、当該命令がレジスタの値を更新する命令（以下、レジスタ更新命令）であると判定すると、かかるレジスタの識別情報とレジスタ更新命令とを対応付けてレジスタ・プロデューサ・テーブルに記憶する。
【００２７】
また、プロセッサは、メインメモリ（あるいはキャッシュ）に記憶されたプログラムを実行する場合に、当該命令がレジスタによって間接的に指定されるアドレスにアクセスする命令であると判定すると、アドレスを間接的に指定するレジスタの識別情報とレジスタ・プロデューサ・テーブルとを基にしてレジスタ（アドレスを間接的に指定するレジスタ）を更新した命令をレジスタ更新命令の中からを特定し、特定した命令（アドレス生成命令）によって更新されたレジスタの値をプリフェッチする。
【００２８】
このように、本実施例１にかかるプロセッサは、レジスタ・プロデューサ・テーブルを用いてアドレス生成命令を特定し、次回アドレス生成命令を実行する際、アドレス生成命令によって更新されたレジスタの値をプリフェッチするので、一般的なアプリケーションで見受けられる不規則なメモリアクセスを見抜き、効果的なハードウェア・プリフェッチを行うことができる。
【００２９】
続いて、本実施例１にかかるプロセッサがアドレス生成命令を特定する仕組みについて説明する。図１は、本実施例１にかかるプロセッサがアドレス生成命令を特定する仕組みを説明するための図である。図１では、メインメモリに展開されたサンプルプログラムを示しており、同図に示される番号0x00004020〜0x000040a0はメモリアドレス（プログラムカウンタの値）を表している。サンプルプログラムは、0x00004020から下に向かって順に実行させる。
【００３０】
ここで、図１に示したサンプルプログラムに含まれる各種の命令について説明する。「move」は、レジスタ間でデータをコピーする命令である。図１に示される「move  r1=r2」という表現は、レジスタ２番の値をレジスタ１番に代入するという意味である。
【００３１】
「add」は、加算命令である。「add  r2＝r2+r3」という表現は、レジスタ２番の値とレジスタ３番の値とを加算した結果をレジスタ２番に格納するという意味である。「load」は、メモリアクセスを行う命令（メモリアクセス命令）である。「[r1]」という表現は、レジスタ１番の値をアドレスとするメモリの値を意味する。
【００３２】
したがって、図１に示される「load  r4=[r1]」は、レジスタ１番の値をアドレスとみなし、そのアドレスのメモリから読み出した値をレジスタ４番に格納するという意味である。以上を踏まえてサンプルプログラムについて説明する。
【００３３】
プロセッサは、プログラムに含まれる命令を実行する際、レジスタを更新する命令（レジスタ更新命令）であれば、レジスタ・プロデューサ・テーブルの対応する領域（エントリ）にレジスタ更新命令のアドレスを書き込む。図２は、レジスタ・プロデューサ・テーブルのデータ構造の一例を示す図である。
【００３４】
レジスタ・プロデューサ・テーブルは、プロセッサに含まれるレジスタの数だけのエントリを持ち、それぞれのエントリにはレジスタを最後に更新したレジスタ更新命令のアドレスを格納する。図２に示す例では、レジスタ１番のレジスタ更新命令のアドレスは、「0x00004020」となっている。レジスタ・プロデューサ・テーブルには、各々のレジスタを最後に更新したレジスタ更新命令のアドレスが書き込まれている状態となる。
【００３５】
レジスタ・プロデューサ・テーブルの更新処理は、全ての命令において常に実施される。図３は、レジスタ・プロデューサ・テーブルの更新処理を説明するための図である。同図に示すように、メモリアドレス（プログラムカウンタ）「0x00004028」の「move」命令は、レジスタ３番を更新しているので、レジスタ更新命令となる。したがって、レジスタ・プロデューサ・テーブルのレジスタ３番に対応するエントリに、かかる「move」命令のアドレス「0x00004028」が登録される。
【００３６】
ここで、上記したレジスタ・プロデューサ・テーブルの更新処理を、図１に示したサンプルプログラムを用いて説明すると、サンプルプログラムの１段目では、レジスタ１番が更新されているため、１段目の命令「move」はレジスタ更新命令となる。したがって、レジスタ・プロデューサ・テーブルのレジスタ１番に対応するエントリに、かかる「move」命令のアドレス「0x00004020」が登録される。
【００３７】
同様に、サンプルプログラムの２，３段目の命令「add」、「move」もそれぞれ、レジスタ２番，３番を更新する命令であるため、レジスタ更新命令となり、各命令のアドレスがレジスタの番号に対応するエントリに登録される。
【００３８】
次に、アドレス生成命令を特定する処理について説明する。図４は、アドレス生成命令を特定する処理を説明するための図である。プロセッサがアドレス生成命令を特定する場合には、まず、プログラムに含まれる命令からメモリアクセス命令を検出する。
【００３９】
図４に示す例では、メモリアドレス「0x000040a0」の「load」命令が、レジスタ１番に格納されているアドレスの値をレジスタ４番に代入しているため（レジスタによって間接的に指定されるアドレスにアクセスするため）、かかる「load」命令は、メモリアクセス命令となる。
【００４０】
プロセッサは、メモリアクセス命令を検出した後に、検出したメモリアクセス命令によって参照されるレジスタの番号（図４に示す例では、レジスタ１番）と、レジスタ・プロデューサ・テーブルとを比較して、かかるレジスタ番号のレジスタを最後に更新したレジスタ更新命令を特定し、特定したレジスタ更新命令をアドレス生成命令として特定する。
【００４１】
ここで、図１に示したサンプルプログラムを用いて、アドレス生成命令を特定する処理について説明する。図１のサンプルプログラムにおいて、メモリアクセス命令に該当する命令は、「load」命令である。
【００４２】
そして、プロセッサは、メモリアクセス命令を検出した後に、検出したメモリアクセス命令によって参照されるレジスタの番号を特定する。図１のサンプルプログラムでは、メモリアクセス命令「load」によって参照されるレジスタ番号はレジスタ１番となる。
【００４３】
プロセッサは、メモリアクセス命令によって参照されるレジスタ番号を特定した後に、特定したレジスタ番号とレジスタ・プロデューサ・テーブル（図２参照）とを比較して、かかるレジスタ番号のレジスタを最後に更新したレジスタ更新命令を特定し、特定したレジスタ更新命令をアドレス生成命令として特定する。図１に示すサンプルプログラムでは、１段目（メモリアドレス「0x00004020」）の「move」命令がアドレス生成命令となる。
【００４４】
次に、本実施例１にかかるプロセッサが実施する命令書き換え処理について説明する。上述したアドレス生成命令を特定する方法では、「load」命令を実施して初めて、「move」命令がアドレス生成命令であると判定できた。しかし、プリフェッチを「move」命令の直後に実行するためには、かかる「move」命令がアドレス生成命令であると事前に判別できていなければならない。
【００４５】
本実施例１にかかるプロセッサは、アドレス生成命令を特定した場合に、本来の処理に加え、演算後にプリフェッチを行う特殊な命令に書き換える。図５は、命令の書き換え処理を説明するための図である。
【００４６】
図５に示すように、例えば、上記の説明のように、メモリアクセス命令を特定した後、レジスタ更新命令のアドレス「0x00004020」がアドレス生成命令のアドレスと判定した場合には、メモリアドレス「0x00004020」にアクセスし、かかるアドレスに登録される命令を書き換える。
【００４７】
図５に示す例では、「move」命令を、「pmove」命令に書き換えている。プロセッサが「pmove」命令を読み出した場合には、本来の「move」命令に相当する処理を実行すると共に、更新したレジスタの値（図５では、レジスタ１番の値）をキャッシュにプリフェッチする。
【００４８】
このように、本実施例２にかかるプロセッサは、アドレス生成命令を特定し、特定したアドレス生成命令を書き換えているので、次回、アドレス生成命令を読み出した後に、アドレス生成命令に更新されたレジスタの値をプリフェッチすることができ、後のメモリアクセス命令でプリフェッチした値を利用することができるので、プロセッサの処理効率を向上させることができる。
【００４９】
次に、上述したプロセッサの構成の一例について説明する。図６は、本実施例１にかかるプロセッサの構成を示す機能ブロック図である。同図に示すように、プロセッサ１００は、Ｉ／Ｏ制御部１１０と、レジスタ部１２０と、制御部１３０と、演算部１４０と、レジスタ・プロデューサ・テーブル記憶部１５０と、データ依存解析部１６０とを備えて構成される。
【００５０】
そして、プロセッサ１００は、キャッシュ２００に接続され、キャッシュ２００は、メインメモリ３００に接続されている。キャッシュ２００、メインメモリ３００は、プロセッサ１００によって利用される命令やデータなどを記憶する記憶装置である。図６では、１段のキャッシュ２００が描かれているが、このキャッシュ２００については何段であっても構わない。
【００５１】
Ｉ／Ｏ制御部１１０は、プロセッサ１００とキャッシュ２００との間で実行されるデータの入出力を制御する手段である。また、Ｉ／Ｏ制御部１１０は、プリフェッチ制御部１１０ａを備える。プリフェッチ制御部１１０ａは、データ依存解析部１６０からプリフェッチ対象となるメモリアドレスを取得した場合に、該当アドレスに登録されたデータをプリフェッチする手段である。
【００５２】
制御部１３０は、キャッシュ２００あるいはメインメモリ３００から命令を読み出して命令を解釈し、命令に応じた各種の処理を実行する制御手段である。レジスタ部１２０は、複数のレジスタ（汎用レジスタ、プログラムカウンタ等）から構成され、制御部１３０等で使用する命令、データを記憶する記憶手段である。
【００５３】
演算部１４０は、制御部１３０からの制御命令を取得して各種演算処理を実行し、演算結果をレジスタ部１２０あるいは制御部１３０に出力する手段である。レジスタ・プロデューサ・テーブル記憶部１５０は、図２において説明したレジスタ・プロデューサ・テーブルを記憶する記憶手段である。
【００５４】
データ依存解析部１６０は、アドレス生成命令を特定し、特定したアドレス生成命令に対応するメインメモリ３００上の命令を書き換える手段である。具体的に、データ依存解析部１６０の処理について説明すると、データ依存解析部１６０は、メインメモリ３００あるいはキャッシュ２００に記憶されたプログラムを読み出して、レジスタ更新命令を特定し、特定したレジスタ更新命令のアドレスをレジスタ・プロデューサ・テーブルに登録する。
【００５５】
また、データ依存解析部１６０は、プログラムの依存関係を解析し、上記した手法によってアドレス生成命令を特定し（図４参照）、メインメモリ３００上のアドレス生成命令を特殊な命令に書き換える（図５参照）。そして、データ依存解析部１６０は、プログラムが実行される過程において、アドレス生成命令となる命令を検出した場合には、アドレス生成命令によって更新されるレジスタの値をプリフェッチすべく、プリフェッチ制御部１１０ａに制御命令を出力する（プリフェッチ対象となるデータのアドレスをプリフェッチ制御部１１０ａに出力する）。
【００５６】
次に、本実施例１にかかるプロセッサ１００の処理手順について説明する。図７は、本実施例１にかかるプロセッサの処理手順を示すフローチャートである。同図に示すように、プロセッサ１００は、命令を読み出し（ステップＳ１０１）、読み出した命令がload／store命令（あるいはメモリアクセス命令）か否かを判定する（ステップＳ１０２）。
【００５７】
load／store命令（あるいはメモリアクセス命令）である場合には（ステップＳ１０３，Ｙｅｓ）、命令で指定された読み出し元のメモリアドレスを指定するレジスタ番号を特定し（ステップＳ１０４）、レジスタ番号に対応するレジスタ・プロデューサ・テーブル内のエントリを調べる（ステップＳ１０５）。
【００５８】
そして、プロセッサ１００は、エントリに書かれたレジスタ更新命令のアドレスをアドレス生成命令のアドレスとして検出し（ステップＳ１０６）、検出した命令を「本来の命令と同様の処理を行った後に演算結果をメモリアドレスとみなしプリフェッチを行う命令」に書き換え（ステップＳ１０７）、ステップＳ１０８に移行する。
【００５９】
一方、load／store命令（あるいはメモリアクセス命令）でない場合には（ステップＳ１０３，Ｎｏ）、レジスタ変更を伴う命令か否かを判定し（ステップＳ１０８）、レジスタ変更を伴う場合には（ステップＳ１０９，Ｙｅｓ）、レジスタ・プロデューサ・テーブル更新処理を実行し（ステップＳ１１０）、ステップＳ１１１に移行する。
【００６０】
一方、レジスタ値変更を伴う命令でない場合には（ステップＳ１０９，Ｎｏ）、命令を実施し（ステップＳ１１１）、次の命令を読み出し（ステップＳ１１２）、ステップＳ１０２に移行する。
【００６１】
次に、図７のステップＳ１１０に示したレジスタ・プロデューサ・テーブル更新処理について説明する。図８は、レジスタ・プロデューサ・テーブル更新処理を示すフローチャートである。
【００６２】
図８に示すように、プロセッサ１００は、命令（レジスタ更新命令）で指定された書き込みレジスタ番号を特定し（ステップＳ２０１）、プログラムカウンタから命令のアドレスを読み出す（ステップＳ２０２）。
【００６３】
そして、プロセッサ１００は、レジスタ番号に対応するレジスタ・プロデューサ・テーブル内のエントリに命令のアドレスを書き込み（ステップＳ２０３）、レジスタ・プロデューサ・テーブル更新処理を終了する。
【００６４】
上述してきたように、本実施例１にかかるプロセッサ１００は、メインメモリ３００からプログラムを読み出してレジスタ更新命令を検出し、レジスタ・プロデューサ・テーブル記憶部１５０にレジスタ更新命令のアドレスを登録する。また、プロセッサ１００は、プログラムを読み出してメモリアクセス命令を検出し、検出したメモリアクセス命令が利用するレジスタの番号とレジスタ・プロデューサ・テーブルとを比較してアドレス生成命令を特定し、アドレス生成命令に対応する命令を書き換えるので、一般的なアプリケーションで見受けられる不規則なメモリアクセスを見抜き、効果的なハードウェア・プリフェッチを行うことができる。
【実施例２】
【００６５】
次に、本実施例２にかかるプロセッサの概要および特徴について説明する。本実施例２にかかるプロセッサは、上記した実施例１と同様の手法を用いて、アドレス生成命令を特定する。そして、本実施例２にかかるプロセッサは、特定したアドレス生成命令を記録するために、キャッシュ上に付加情報を保持させる。
【００６６】
キャッシュ情報の保持の仕方は様々なものが考えられるが、ここでは説明を簡単にするため、ダイレクトマップ方式のキャッシュを前提とする。なお、セットアソシアティブ方式などでも、キャッシュ情報を検索する部分を、それぞれの方式に読み替えることで、同様に実現できる。
【００６７】
ここで、キャッシュに記憶されるキャッシュ情報について説明する。図９は、キャッシュ情報のデータ構造の一例を示す図である。同図に示すように、このキャッシュ情報は、タグと、状態と、アドレス生成フラグと、命令ワードとから構成される。
【００６８】
このうち、タグは、該当ラインが要求された命令に対応するものか判別するためのアドレス情報を記憶するものである。また、状態は、該当ラインの状態を示す情報であり、CLEAN、DIRTY、INVALIDなどが格納される。
【００６９】
アドレス生成フラグは、対応する命令ワードがアドレス生成命令か否かを示す情報を格納しており、命令ワードは、各種の処理を実行するための命令を格納している。図９に示した例では、各命令ワードと各アドレス生成フラグが対応付けられているものとする。アドレス生成フラグが「TRUE」となる命令ワードが、アドレス生成命令となる。
【００７０】
次に、本実施例２にかかるプロセッサがキャッシュ情報のアドレス生成フラグを更新する処理について説明する。図１０は、プロセッサがキャッシュ情報のアドレス生成フラグを更新する処理を説明するための図である。図１０に示す例では、アドレス生成命令のアドレスを、１５bit、８bit、９bitに区切り、それぞれを、タグ、インデックス、ライン内インデックスとしているが、これに限定されるものではなく、キャッシュ方式の違いや、ラインサイズの違いなどによって区切り方が変化する。
【００７１】
プロセッサは、アドレス生成命令のインデックスを参照し、インデックスに対応するキャッシュラインにアクセスする。そして、キャッシュラインに記憶されたキャッシュ情報のタグの値とアドレス生成命令のタグとを比較して一致するか否かを判定し、一致している場合には、該当アドレスを含むラインがキャッシュ上に存在すると判定する。
【００７２】
その後、プロセッサは、アドレス生成命令アドレスのライン内インデックスに格納された値を基にして、該当ラインのアドレス生成フラグを「FALSE」から「TRUE」に変換する。例えば、図１０に示すアドレス生成命令のアドレスによって、キャッシュ情報のアドレス生成フラグ（キャッシュ情報の上から４段目、左から２列目のアドレス生成フラグ）を「TRUE」に変換した場合には、命令ワードの左から２列目の命令ワードがアドレス生成命令に対応することとなる。
【００７３】
次に、上述したプロセッサの構成の一例について説明する。図１１は、本実施例２にかかるプロセッサの構成を示す機能ブロック図である。同図に示すように、このプロセッサ４００は、Ｉ／Ｏ制御部４１０と、レジスタ部４２０と、制御部４３０と、演算部４４０と、レジスタ・プロデューサ・テーブル記憶部４５０と、データ依存解析部４６０とを備えて構成される。
【００７４】
このうち、Ｉ／Ｏ制御部４１０、レジスタ部４２０、制御部４３０、演算部４４０、レジスタ・プロデューサ・テーブル記憶部４５０に関する説明は、図６に示したＩ／Ｏ制御部１１０、レジスタ部１２０、制御部１３０、演算部１４０、レジスタ・プロデューサ・テーブル記憶部１５０に関する説明と同様であるため説明を省略する。
【００７５】
データ依存解析部４６０は、アドレス生成命令を特定し、特定したアドレス生成命令のアドレスを基にしてキャッシュ２００に記憶されたキャッシュ情報のアドレス生成フラグを変換する手段である。具体的に、データ依存解析部４６０は、メインメモリ３００あるいはキャッシュ２００に記憶されたプログラムを読み出して、レジスタ更新命令を特定し、特定したレジスタ更新命令のアドレスをレジスタ・プロデューサ・テーブルに登録する。
【００７６】
また、データ依存解析部４６０は、プログラムの依存関係を解析し、実施例１で示した手法によってアドレス生成命令を特定し（図４参照）、キャッシュ２００のキャッシュ情報のアドレス生成フラグを更新する（図１０参照）。データ依存解析部４６０は、キャッシュ２００に記憶されたキャッシュ情報が読み出され、命令が実行される場合に、アドレス生成フラグと命令ワードとを比較する。
【００７７】
そして、アドレス生成命令が「TRUE」となる命令である場合には、該当命令がアドレス生成命令であると判定し、アドレス生成命令によって更新されるレジスタの値をプリフェッチすべく、プリフェッチ制御部４１０ａに制御命令を出力する（プリフェッチ対象となるデータのアドレスをプリフェッチ制御部４１０ａに出力する）。
【００７８】
次に、本実施例２にかかるプロセッサ４００の処理手順について説明する。図１２、図１３は、本実施例２にかかるプロセッサ４００の処理手順を示すフローチャートである。同図に示すように、プロセッサ４００は、命令を読み出し（ステップＳ３０１）、読み出した命令がload／store命令（あるいはメモリアクセス命令）か否かを判定する（ステップＳ３０２）。
【００７９】
load／store命令（あるいはメモリアクセス命令）である場合には（ステップＳ３０３，Ｙｅｓ）、アドレスとして使用されるレジスタ番号を命令から特定し（ステップＳ３０４）、レジスタ・プロデューサ・テーブルを参照し、最終更新を行った命令（アドレス生成命令）のアドレスを調べる（ステップＳ３０５）。
【００８０】
そして、プロセッサ４００は、アドレス生成命令のアドレスからメモリ読み出しを行い、アドレス生成命令を特定し（ステップＳ３０６）、アドレス生成命令のアドレスを、桁で分割し、上位１５bitをタグ、下位９bitをライン内インデックス、残った８bitをインデックスとする（ステップＳ３０７）。
【００８１】
プロセッサ４００は、キャッシュ情報をアドレス生成命令のインデックスにより参照し（ステップＳ３０８）、参照したキャッシュ情報中のタグの値と、アドレス生成命令のタグ値とを比較し（ステップＳ３０９）、タグが一致していない場合には（ステップＳ３１０，Ｎｏ）、ステップＳ３１４に移行する。
【００８２】
一方、タグが一致している場合には（ステップＳ３１０，Ｙｅｓ）、参照したキャッシュ情報内のアドレス生成フラグを更新対象と判定し（ステップＳ３１１）、更新するフラグをライン内インデックスで示す値とし（ステップＳ３１２）、ライン内インデックスが示すアドレス生成フラグをTUREに更新し（ステップＳ３１３）、ステップＳ３１４に移行する。
【００８３】
ところで、load／store命令（あるいはメモリアクセス命令）でない場合には（ステップＳ３０３，Ｎｏ）、レジスタ変更を伴う命令か否かを判定し（ステップＳ３１４）、レジスタ変更を伴う場合には（ステップＳ３１５，Ｙｅｓ）、レジスタ・プロデューサ・テーブル更新処理を実行し（ステップＳ３１６）、ステップＳ３１７に移行する。
【００８４】
一方、レジスタ変更を伴う命令でない場合には（ステップＳ３１５，Ｎｏ）、命令を実施し（ステップＳ３１７）、実施した命令がアドレス生成命令か否かを判定し（ステップＳ３１８）、アドレス生成命令である場合には（ステップＳ３１９，Ｙｅｓ）、プリフェッチを実施し（ステップＳ３２０）、ステップＳ３２１に移行する。
【００８５】
一方、アドレス生成命令でない場合には（ステップＳ３１９，Ｎｏ）、次の命令を読み出し（ステップＳ３２１）、ステップＳ３０２に移行する。なお、図１３のステップＳ３１６に示したレジスタ・プロデューサ・テーブル更新処理は、図８において説明した処理に対応するため、説明を省略する。
【００８６】
上述してきたように、本実施例２にかかるプロセッサ４００は、メインメモリ３００からプログラムを読み出してレジスタ更新命令を検出し、レジスタ・プロデューサ・テーブル記憶部４５０にレジスタ更新命令のアドレスを登録する。また、プロセッサ４００は、プログラムを読み出してメモリアクセス命令を検出し、検出したメモリアクセス命令が利用するレジスタの番号とレジスタ・プロデューサ・テーブルとを比較してアドレス生成命令を特定し、キャッシュ２００のアドレス生成フラグを変換するので、命令実行時にかかるアドレス生成フラグを利用することにより、一般的なアプリケーションで見受けられる不規則なメモリアクセスを見抜き、効果的なハードウェア・プリフェッチを行うことができる。
【実施例３】
【００８７】
次に、本実施例３にかかるプロセッサの概要および特徴について説明する。本実施例３にかかるプロセッサは、上記した実施例１と同様の手法を用いて、アドレス生成命令を特定する。そして、本実施例３にかかるプロセッサは、特定したアドレス生成命令のアドレスをアドレス生成命令テーブルに登録する。
【００８８】
図１４は、アドレス生成命令テーブルのデータ構造の一例を示す図である。同図に示すように、このアドレス生成命令テーブルは、アドレス生成命令のアドレスを格納している。アドレス生成命令テーブルの構成方法については、キャッシュ同様にダイレクト方式、セットアソシアティブ方式、フルアソシアディブ方式などが考えられるが、本実施例３では、ダイレクト方式を例にしている。
【００８９】
次に、本実施例３にかかるプロセッサがアドレス生成テーブルを参照する方法について説明する。図１５は、プロセッサがアドレス生成テーブルを参照する方法を説明するための図である。同図に示すように、プロセッサは、アドレス生成命令の一部をインデックスとして解釈し、そのインデックスでアドレス生成命令テーブルを参照する。アドレス生成命令のアドレスを登録する場合には、かかるインデックスで示されたアドレス生成命令テーブルのエントリを登録するアドレスで上書きすればよい。
【００９０】
また、アドレス生成命令か否かを判定する場合には、調査対象の命令のアドレスを特定し、そのアドレスから得られたインデックスを用いてアドレス生成テーブルを参照する。書かれたアドレスが調査対象の命令のアドレスと一致するならば、該当命令はアドレス生成命令であると判定できる。
【００９１】
次に、上述したプロセッサの構成の一例について説明する。図１６は、本実施例３にかかるプロセッサの構成を示す機能ブロック図である。同図に示すように、このプロセッサ５００は、Ｉ／Ｏ制御部５１０と、レジスタ部５２０と、制御部５３０と、演算部５４０と、レジスタ・プロデューサ・テーブル記憶部５５０と、アドレス生成命令テーブル記憶部５６０と、データ依存解析部５７０とを備えて構成される。
【００９２】
このうち、Ｉ／Ｏ制御部５１０、レジスタ部５２０、制御部５３０、演算部５４０、レジスタ・プロデューサ・テーブル記憶部５５０に関する説明は、図６に示したＩ／Ｏ制御部１１０、レジスタ部１２０、制御部１３０、演算部１４０、レジスタ・プロデューサ・テーブル記憶部１５０に関する説明と同様であるため説明を省略する。
【００９３】
アドレス生成命令テーブル記憶部５６０は、図１４に示したアドレス生成命令テーブルを記憶する記憶手段である。
【００９４】
データ依存解析部５７０は、アドレス生成命令を特定し、特定したアドレス生成命令のアドレスをアドレス生成命令テーブルに記憶する手段である。具体的に、データ依存解析部５７０は、メインメモリ３００あるいはキャッシュ２００に記憶されたプログラムを読み出して、レジスタ更新命令を特定し、特定したレジスタ更新命令のアドレスをレジスタ・プロデューサ・テーブルに登録する。
【００９５】
また、データ依存解析部５７０は、プログラムの依存関係を解析し、実施例１で示した手法によってアドレス生成命令を特定し（図４参照）、アドレス生成命令テーブル記憶部５６０に記憶されたアドレス生成命令テーブルにアドレス生成命令のアドレスを登録する（図１４参照）。データ依存解析部５７０は、プログラムを読み出して命令を実行する場合に、命令のアドレスとアドレス生成命令テーブルとを比較する。
【００９６】
そして、命令のアドレスに含まれるインデックスがアドレス生成命令テーブルに存在する場合には、該当命令がアドレス生成命令であると判定し、アドレス生成命令によって更新されるレジスタの値をプリフェッチすべく、プリフェッチ制御部５１０ａに制御命令を出力する（プリフェッチ対象となるデータのアドレスをプリフェッチ制御部５１０ａに出力する）。
【００９７】
次に、本実施例３にかかるプロセッサ５００の処理手順について説明する。図１７、図１８は、本実施例３にかかるプロセッサ５００の処理手順を示すフローチャートである。同図に示すように、プロセッサ５００は、命令を読み出し（ステップＳ４０１）、読み出した命令がload／store命令（あるいはメモリアクセス生命）か否かを判定する（ステップＳ４０２）。
【００９８】
load／store命令（あるいはメモリアクセス命令）である場合には（ステップＳ４０３，Ｙｅｓ）、アドレスとして使用されるレジスタ番号を命令から特定し（ステップＳ４０４）、レジスタ・プロデューサ・テーブルを参照し、最終更新を行った命令のアドレスを調べる（ステップＳ４０５）。
【００９９】
そして、プロセッサ５００は、アドレス生成命令のアドレスからメモリ読み出しを行い、アドレス生成命令を特定し（ステップＳ４０６）、アドレス生成命令のアドレスを桁で分割し、bit８からbit２０までの１３bitで構成した値を「インデックス」として用いる（ステップＳ４０７）。
【０１００】
プロセッサ５００は、アドレス生成命令テーブルに対して参照するエントリをインデックスにより決定し（ステップＳ４０８）、決定したエントリに、アドレス生成命令のアドレスを書き込み（ステップＳ４０９）、ステップＳ４１０に移行する。
【０１０１】
ところで、load／store命令（あるいはメモリアクセス命令）でない場合には（ステップＳ４０３，Ｎｏ）、レジスタ変更を伴う命令か否かを判定し（ステップＳ４１０）、レジスタ変更を伴う場合には（ステップＳ４１１，Ｙｅｓ）、レジスタ・プロデューサ・テーブル更新処理を実行し（ステップＳ４１２）、ステップＳ４１３に移行する。
【０１０２】
一方、レジスタ変更を伴う命令でない場合には（ステップＳ４１１，Ｎｏ）、命令を実施し（ステップＳ４１３）、調査対象の命令のアドレスを桁で分割し、bit８からbit２０までの１３bitで構成した値をインデックスとして用いる（ステップＳ４１４）。
【０１０３】
続いて、プロセッサ５００は、アドレス生成命令テーブルに対して参照するエントリをインデックスにより決定し（ステップＳ４１５）、決定したエントリの値が、調査対象のアドレスと一致するか否かを判定する（ステップＳ４１６）。
【０１０４】
アドレスが一致した場合には（ステップＳ４１７，Ｙｅｓ）、プリフェッチを実施し（ステップＳ４１８）、ステップＳ４１９に移行する。一方、アドレスが一致しない場合には（ステップＳ４１７，Ｎｏ）、次の命令を読み出し（ステップＳ４１９）、ステップＳ４０２に移行する。なお、図１８のステップＳ４１２に示したレジスタ・プロデューサ・テーブル更新処理は、図８において説明した処理に対応するため、説明を省略する。
【０１０５】
上述してきたように、本実施例３にかかるプロセッサ５００は、メインメモリ３００からプログラムを読み出してレジスタ更新命令を検出し、レジスタ・プロデューサ・テーブル記憶部５５０にレジスタ更新命令のアドレスを登録する。また、プロセッサ５００は、プログラムを読み出してメモリアクセス命令を検出し、検出したメモリアクセス命令が利用するレジスタの番号とレジスタ・プロデューサ・テーブルとを比較してアドレス生成命令を特定し、アドレス生成命令のアドレスをアドレス生成命令テーブルに登録するので、命令実行時にかかるアドレス生成命令テーブルを利用することにより、一般的なアプリケーションで見受けられる不規則なメモリアクセスを見抜き、効果的なハードウェア・プリフェッチを行うことができる。
【実施例４】
【０１０６】
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例１〜３以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下では実施例４として本発明に含まれる他の実施例を説明する。
【０１０７】
（１）アドレス生成命令に着目したコンパイラによる最適化
コンパイラがソースプログラムをコンパイルする場合に、命令間の依存関係を解析して、アドレス生成命令を検出し、高速なメモリアクセスを実現したアプリケーションプログラムを生成することができる。アドレス生成命令を検出する手法は、実施例１〜３に示した手法と同様の手法を用いることができる。
【０１０８】
アドレス生成命令を検出した場合には、コンパイラは、アドレス生成命令の入力データを計算する命令を優先的にアプリケーションプログラムに配置する、あるいは、アドレス生成命令の直後に、アドレス生成命令によって更新されたデータをプリフェッチする命令を挿入するなどの最適化を行うことで、効率的なプリフェッチを行うことができるアプリケーションを生成することができる。
【０１０９】
かかるコンパイラにより生成されたアプリケーションプログラムは、メモリアクセスが発生する際、そのメモリアドレスが確定した時点でデータの先読みを開始する。また、メモリアドレス確定のために必要な処理は、なるべく優先して処理されるように命令を並び替えているため、この先読み処理の可能な限り速い時期にスタートできる。これにより、コンパイラにより生成されたアプリケーションプログラムは、最適なタイミングでデータを先読みし、高速なデータ読み出しを実現することができる。
【０１１０】
（２）仮想マシン上での実現
前提として、キャッシュ機構を持つプロセッサ上に実装された仮想マシンを考える。この仮想マシンは、実施例１〜３に示した手法と同様の手法を用いてアドレス生成命令を検出する。かかる仮想マシンは、仮想マシン上で動作するバイナリからアドレス生成命令の検出を行い、実機上のメモリシステムに対して、仮想マシン上のメモリアクセスに対応するデータのプリフェッチを実施する。
【０１１１】
仮想マシンは、仮想マシン上で実行中のプログラムについて、データフローの解析を行い、実施例１〜３のシステムと同様、自動的なプリフェッチを実現している。そのため、仮想マシン上で動作するプログラムも、メモリアクセスが最適化され、高速に動作することが可能となる。なお、仮想マシンのプログラムは、例えば、メインメモリに記憶され、プロセッサに読み出されて実行されるものとする。
【０１１２】
（３）Just  In  Timeコンパイル環境上での実現
前提として、キャッシュ機構をもつプロセッサ上に実装された仮想マシンを考える。この仮想マシンはJust  In  Timeコンパイル機能を有する。また、上記した仮想マシンと同様に実施例１〜３と同様の手法を用いてアドレス生成命令を検出する。
【０１１３】
そして、仮想マシンは、Just  In  Timeコンパイル時において、アドレス生成命令の直後に演算結果のアドレスに対してプリフェッチを行う命令を付加する。変換後のプリフェッチ命令が有効に機能しない場合は、改めて変換した命令列の中から、プリフェッチ命令を取り除けばよい。これにより、仮想マシンは高速なメモリアクセスや命令実行を実現することができる。
【０１１４】
（４）システムの構成等
本実施例において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。この他、上記文章中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【０１１５】
また、図示したプロセッサ１００，４００，５００の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況に応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行われる各処理機能は、その全部または任意の一部が、ＣＰＵおよび該当ＣＰＵにて解析実行されるプログラム（例えば、仮想マシン）にて実現され得る。
【０１１６】
なお、本実施例で説明した各種の処理手順は、予め用意されたプログラムをコンピュータで実行することによって実現することができる。このプログラムは、インターネットなどのネットワークを介して配布することができる。また、このプログラムは、ハードディスク、フレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記憶媒体に記録され、コンピュータによって記憶媒体から読み出されることによって実行することもできる。
【産業上の利用可能性】
【０１１７】
以上のように、本発明にかかるプロセッサおよびプリフェッチ支援プログラムは、プリフェッチを実施するプロセッサに対して有用であり、特に、一般的なアプリケーションで見受けられる不規則なメモリアクセスを見抜き、効果的なハードウェア・プリフェッチを行う場合に適している。
【図面の簡単な説明】
【０１１８】
【図１】図１は、本実施例１にかかるプロセッサがアドレス生成命令を特定する仕組みを説明するための図である。
【図２】図２は、レジスタ・プロデューサ・テーブルのデータ構造の一例を示す図である。
【図３】図３は、レジスタ・プロデューサ・テーブルの更新処理を説明するための図である。
【図４】図４は、アドレス生成命令を特定する処理を説明するための図である。
【図５】図５は、命令の書き換え処理を説明するための図である。
【図６】図６は、本実施例１にかかるプロセッサの構成を示す機能ブロック図である。
【図７】図７は、本実施例１にかかるプロセッサの処理手順を示すフローチャートである。
【図８】図８は、レジスタ・プロデューサ・テーブル更新処理を示すフローチャートである。
【図９】図９は、キャッシュ情報のデータ構造の一例を示す図である。
【図１０】図１０は、プロセッサがキャッシュ情報のアドレス生成フラグを更新する処理を説明するための図である。
【図１１】図１１は、本実施例２にかかるプロセッサの構成を示す機能ブロック図である。
【図１２】図１２は、本実施例２にかかるプロセッサの処理手順を示すフローチャート（１）である。
【図１３】図１３は、本実施例２にかかるプロセッサの処理手順を示すフローチャート（２）である。
【図１４】図１４は、アドレス生成命令テーブルのデータ構造の一例を示す図である。
【図１５】図１５は、プロセッサがアドレス生成テーブルを参照する方法を説明するための図である。
【図１６】図１６は、本実施例３にかかるプロセッサの構成を示す機能ブロック図である。
【図１７】図１７は、本実施例３にかかるプロセッサの処理手順を示すフローチャート（１）である。
【図１８】図１８は、本実施例３にかかるプロセッサの処理手順を示すフローチャート（２）である。
【符号の説明】
【０１１９】
１００，４００，５００    プロセッサ
１１０，４１０，５１０    Ｉ／Ｏ制御部
１１０ａ，４１０ａ，５１０ａ  プリフェッチ制御部
１２０，４２０，５２０    レジスタ部
１３０，４３０，５３０    制御部
１４０，４４０，５４０    演算部
１５０，４５０，５５０    レジスタ・プロデューサ・テーブル記憶部
１６０，４６０，５７０    データ依存解析部
２００    キャッシュ
３００    メインメモリ
５６０    アドレス生成命令テーブル記憶部
【国際調査報告】
2008155812.tif 000021
2008155812.tif 000022