(57)【特許請求の範囲】
【請求項１】
主メモリからデータキャッシュセット及び命令キャッシュセットを含むキャッシュメモリへ、データ或いは命令のいずれかの情報をプリフェッチするための、コンピュータにより使用される方法であって、
前記主メモリ内の前記情報のアドレスを示すアドレスフィールドと、前記主メモリからどのような形式の情報を検索すべきかを特定する命令／データフィールドを含むプリフェッチ命令を含むプリフェッチコマンドを実行するステップと、
前記情報がデータであるか命令であるかを判別するステップと、
前記主メモリ内の前記情報にアクセスするステップと、
前記判別するステップにおいて、前記情報がデータであると判別された場合には、前記データの受信後に、前記データを前記データキャッシュセットに送信するステップと、
前記判別するステップにおいて、前記情報が命令であると判別された場合には、前記命令の受信後に、前記命令を前記命令キャッシュセットに送信するステップと
を有する方法。
【請求項２】
プログラムを実行可能なＣＰＵと、命令及びデータを含む格納された情報を維持する主メモリと、命令キャッシュセット及びデータキャッシュセットを含むデータ及びキャッシュメモリを含むプリフェッチコマンドシステムであって、
前記主メモリ内のどこに前記格納された情報が位置するかを前記ＣＰＵに示すアドレスフィールドと、
前記格納された情報が命令であるかデータであるかを前記ＣＰＵに示し、前記情報を前記命令キャッシュ内に格納するか前記データキャッシュ内に格納するかを示す命令／データフィールドと
からなるプログラムの実行により前記ＣＰＵに提供されるプリフェッチ命令を含むシステム。
【請求項３】
どれだけの情報を前記主メモリから検索して前記キャッシュメモリに格納するかを前記ＣＰＵに示すサイズフィールドをプリフェッチ命令中に更に含む請求項２に記載のシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、キャッシュメモリに関し、特に、主メモリからキャッシュメモリへデータと命令を取り出すプリフェッチ命令に関する。
【０００２】
【従来の技術】
コンピュータ産業は、前世代の構成要素よりも、より高速で動作する新しいコンピュータ構成要素を開発するために常に努力している。最新世代のマイクロプロセッサは、以前のものよりも更に高速で動作するので、高速のデータ及び命令検索に対する要求も増加する。
【０００３】
コンピュータアーキテクチャにおいては、マイクロプロセッサ（ＣＰＵ）は、主メモリから分離された構成要素であり、この二つはバスによって接続されている。ＣＰＵが動作すると、ＣＰＵは主メモリからのデータ及び命令の両方にアクセスして、その動作を実行しなければならない。主メモリからのデータ及び命令検索のアクセス時間は、典型的には、ＣＰＵの動作を著しく遅くする。なぜなら、ＣＰＵは、要求されたデータ或いは命令を受け取るのを単に待つことに多くの時間を費やすからである。この時間遅延はメモリ待ち時間と呼ばれる。
【０００４】
メモリ待ち時間には二つの構成要素がある。第１は、バス伝搬時間で、要求をメモリに伝搬してから、その要求した情報を搬送するまでに要する時間の関数である。第２のものは、主メモリアクセス時間それ自身である。ダイナミックＲＡＭの（ＤＲＡＭ）ＣＭＯＳ技術のアドレスデコード及び他のロジックは、主メモリからの情報にアクセスする際の固有の遅延の原因となる。
【０００５】
現時点においては、主メモリが６０ナノ秒のクロックを有する一方、ＣＰＵが１０ナノ秒以下のクロックであることがあり、この組み合わせの場合には、６：１のメモリ待ち時間比となる。近い将来、改良されたマイクロプロセッサは、３ナノ秒以下のクロックを有することが期待されるが、一方、主メモリは５０ナノ秒のクロックを有するように改良することしか期待されない。このように、メモリ待ち時間は、１５：１の比より大きくなることが予測される。
【０００６】
１９６０年代初期に、ＣＰＵの近くにメモリをおいて、メモリ待ち時間の影響を減らすための開発が行われた。今日、頻繁に用いられるデータ及び命令は、主メモリに格納されるのに加えて、ＣＰＵにより近い「キャッシュ」メモリに格納される。キャッシュは、主メモリが有するよりもずっと少ないラインに対する容量であり、スタテックＲＡＭ（ＳＲＡＭ）（ＤＲＡＭよりも高速で、電力を消費し、高価である）である。
【０００７】
従って、キャッシュの機能は、度々使用されるデータ或いは命令を、アクセスに長い時間がかかる主メモリから呼ぶ代わりに、ＣＰＵの近くに置くことにより、メモリ待ち時間の影響を減らすことである。
【０００８】
図１を参照すると、最も単純な形式のキャッシュであるシングル−セットキャッシュが示される。主メモリ１０は、キャッシュ１２とＣＰＵ１４の互いの距離よりも、キャッシュ１２とＣＰＵ１４の組み合わせからかなり遠く離れているように描かれている。キャッシュ１２は、メモリ待ち時間の影響を減らすが、その構造は、それ自身の問題を引き起こす。特に、「スラッシング」の問題は、「ミスペナルティ」として知られる速度低下を引き起こす。
【０００９】
スラッシングは、最小のキャッシュオフセット（ライン）構造の制限から生じる。そこでは、共通のシングル−セットキャッシュにおいて、単一のページ（例えば、１００〜１０００から１００オフセット単位で増加する番号が付けられたマルチプルラインを有する）と等価なものに対して割り当てられた空間がある。図１に戻ると、主メモリ１０は、それぞれが、１００オフセット単位で増加するの１００〜１０００のラインを含んでいる、第１のバーチャルページは、１００〜１０００というラインを占有し、第２のものは、１１００〜２０００等のラインを含むというように、五つの「バーチャルページ」に分かれている（実際には、主メモリは、より多くのバーチャルページを含むことになる）。
【００１０】
スラッシングを説明するために、図１は、ＣＰＵが、主メモリから検索されてキャッシュのオフセット４００に格納されるライン１４００を要求したことを示す。その後直ぐに、ＣＰＵは、主メモリから検索されてキャッシュのオフセット４００に同様にマッピングされるライン２４００を要求し、以前に格納されたライン１４００を上書きする。ここでは、キャッシュが要求されたラインを含まなかったので、ミスペナルティとなり、これを主メモリから検索することが要求された。その後直ぐに、ＣＰＵは、主メモリから検索されてキャッシュのオフセット４００にマッピングされるライン１４００を再び必要とし、これを要求するので、以前に格納されたライン２４００を上書きした。再び、ミスペナルティとなった。二つのライン、１４００及び２４００が、通常の状態でＣＰＵにより双方とも必要とされる場合には、スラッシングのピンポン効果が、ミスペナルティを繰り返して生じさせる。
【００１１】
スラッシングは、ＣＰＵの処理速度を著しく遅くする。なぜなら、主メモリから受け取るべき、頻繁に使用される情報（データ或いは命令）を待つために非常に多くの時間を費やすからである。このような場合においては、複合されたミスペナルティが、ＣＰＵの性能を支配する。逆に、度々使用される情報が、常にキャッシュに格納されている時には、その最大能力で動作することができる。従って、マイクロプロセッサの速度が改善されるに連れて、ミスペナルティの影響も増加する。
【００１２】
スラッシング問題を除去するための努力がなされた際に導入された多くの異なった形式のキャッシュ構造がある。例えば、一つの一般的な解決法は、シングル−セットキャッシュの代わりに「マルチ−セットキャッシュ」を用いることである。図２を参照すると、他の競合するラインに関しての二つ以上のオフセット位置を潜在的に提供することができる２−セットキャッシュが示される。セット１２及びセット１４の双方は、情報を格納する４００オフセットの位置を有する。このように、ライン１４００と２４００の双方は、キャッシュに同時に格納することができ、スラッシングを最も生じそうにないこれらのいずれかについての要求に変更する。マルチ−セットキャッシュの実際の利点は、プログラムの実行に依存している。しかしながら、シングル−セットキャッシュを改良したマルチ−セットでさえ、ＣＰＵ処理速度が増加するに従って、ミスペナルティについての性能コストは増加し続ける。
【００１３】
【発明が解決しようとする課題】
データ及び命令に関して別々のキャッシュがあるハーバードアーキテクチャにおいては、少なくともデータが命令とスラッシングを起こすまで、スラッシングは減少する。勿論、上記したように、ＳＲＡＭは高価であるので、特にハーバードアーキテクチャにおいては、マルチ−セットキャッシュの数に制限がある。
【００１４】
スラッシングを避ける別の方法は、それらが必要とされる前に、データ及び命令をキャッシュへ「プリフェッチ」することである。すなわち、ＣＰＵからの要求を待つのではなくて、それが実際に必要とされる前に、ＣＰＵが何を必要とするだろうかを予測することを試みる各種の機構が存在する。例えば、ＳＰＡＲＣ（Ｒ）バージョン９で構築したアーキテクチャは、データをデータキャッシュへプリフェッチすることになるデータプリフェッチ命令を実行する能力を有する。しかしながら、プリフェッチ命令は、不変の静的なサイズのプリフェッチを提供するが、他の能力は提供しない。
【００１５】
ハーバードアーキテクチャは、命令及びデータを格納するための異なったキャッシュを用意する一方、先行技術のプリフェッチは、データのプリフェッチを行うが、現時点では、命令とデータの双方を適切なキャッシュに書き込むための機構が存在しない。更に、プリフェッチのサイズ、或いは、情報が書き込まれるマルチ−セットキャッシュの特定のセットを制御するための機構は存在しない。近い将来に予期されるＣＰＵの速度への大幅な改良を考慮すると、スラッシングの可能性を更に減らすプリフェッチ制御を提供することは好都合である。
【００１６】
【課題を解決するための手段】
本発明は、特定されたキャッシュセットに対する可変サイズのデータ或いは命令をプリフェッチするための命令レベルの方法及びシステムである。バイナリフィールドを含むプリフェッチ命令は、プリフェッチすべき最適のキャッシュセット位置及び最適なデータ量に関する情報を備えたプリフェッチハードウェアを提供することにより、コンパイラ、ローダ、或いは、ランタイムソフトウェアが、キャッシュプリフェッチを制御することが可能となり、スラッシングを減らすことができる。別々の命令とデータキャッシュを備えたハーバードアーキテクチャのサポートは、命令とデータキャッシュの別々のソフトウェア制御によって提供される。すなわち、プリフェッチ命令は、プリフェッチがデータに対するものであるか、或いは、命令に対するものであるかを示す。キャッシュセット数は、どのセットに情報をプリロードすべきであるかを示すために識別される。サイズフィールドは、可変プリフェッチサイズを提供する。アドレスフィールドは、プリフェッチが始まるアドレスを示す。
【００１７】
【発明の実施の形態】
上述したように、ＣＰＵからの要求を待つのではなくて、それが実際に必要とされる前に、ＣＰＵがどのような情報を必要とするだろうかを予測することを試みる各種の機構が存在する。確実なプリフェッチ機構は、キャッシュによってミスされることになる次のラインを予測してプリフェッチを行なう。一般に、全てのミスは強制的なものである、すなわち、フェッチされたラインはキャッシュ内には以前には存在していなかったという仮定のもとに、フェッチされた最終ラインに続くラインがプリフェッチされてラインバッファに格納される。次のミスを予測するプリフェッチがあるキャッシュは、「常時フェッチ（ｆｅｔｃｈ  ａｌｗａｙｓ）」或いはクラス２キャッシュと呼ばれる。これに対して、ミスしたラインのみがフェッチされるキャッシュは、クラス１、要求によるフェッチ（ｆｅｔｃｈ  ｏｎ  ｄｅｍａｎｄ）、或いは、失敗したキャッシュでのフェッチ（ｆｅｔｃｈ  ｏｎ  ｆａｕｌｔ  ｃａｃｈｅ）と呼ばれる。本発明は、任意の形式のプリフェッチ機構と組み合わせて使用され、そして、キャッシュ構造を管理するための初期プリフェッチ命令に対する拡張として実行される。
【００１８】
コンピュータシステムにおいて、コンパイラは、所定のコンピュータでプログラムを実行するために必要とされる任意のオブジェクトプログラムを命令の中へ組み込む。すなわち、コンパイラは、特定の高レベル言語（ソースコード）の入力プログラムを特定の機械形式の機械語（オブジェクトコード）に変換するプログラムである。従って、上記のプリフェッチコマンドは、コンパイラによって生成され、結果として生じたオブジェクトコードの一部として実行される。
【００１９】
図３を参照すると、プログラマのプログラム２０（ソースコード）は、プリフェッチ命令２４を、オブジェクトコード（機械コード）２６に挿入するコンパイラ２２によって翻訳される。上述したように、本発明以前には、プリフェッチ命令は、不変で静的なサイズのプリフェッチを提供するが、キャッシュ管理のような他の能力は提供しない。すなわち、先行技術の命令は、単にプリフェッチをトリガーするだけである。一方、本発明によれば、コンパイルされた命令２８は、以下のバイナリフィールドを含む。
＜ＯＰＣＯＤＥ＞＜Ｉ／Ｄ  ＢＩＴ＞＜ＳＥＴ＃＞＜ＡＤＤＲ＞＜ＳＩＺＥ＞
【００２０】
＜ＯＰＣＯＤＥ＞は、プリフェッチコマンドをプリフェッチコマンドとして識別するフィールドである。＜Ｉ／Ｄ  ＢＩＴ＞フィールドは、プリフェッチがデータに関するものであるか、或いは、命令に関するものであるかを識別する。＜ＳＥＴ＃＞フィールドは、情報をどのセットにプリロードすべきかを示すために識別される。＜ＡＤＤＲ＞フィールドはプリフェッチが始まるアドレスを示す。＜ＳＩＺＥ＞フィールドは可変プリフェッチのサイズを提供する。勿論、上記のプリフェッチ命令或いはその任意の部分を、ローダ或いはランタイムソフトウェアにより同様に生成することができ、また、任意のフィールドを任意のアクセス可能な位置に格納することができる。
【００２１】
＜ＳＩＺＥ＞フィールドは、どれだけラインをフェッチするかを示すバイナリ数を提供する。ここで説明された機構は静的であるが、プログラムを実行してキャッシュミスをモニタし、これに従ってサイズフィールドを可変する最適化ソフトウェアツールは、本発明の範囲内である。ここで一般的に説明された＜ＳＩＺＥ＞フィールドは、プログラマがコンパイラタスクに従って再定義することができるように、コンパイラによって整調することができる。静的な実施形態における最適サイズに調整するために、プログラマはシミュレーション環境でソフトウェアを実行し、そして、システムの性能に依存して、すなわち、ミスペナルティが非常に高ければ、サイズフィールドの調整を行う。
【００２２】
図４を参照すると、ＣＰＵ１４及び主メモリ１０が、ハーバードアーキテクチャのマルチ−セット（ここでは２−セット）キャッシュであるキャッシュメモリ３０と共に示される。命令キャッシュセット＃１及び＃２は、データキャッシュセット＃１及び＃２として示される。コンパイラによって生成されたプリフェッチ命令は、例えば以下の値を含む。
＜プリフェッチ＞＜Ｉ＞＜１＞＜３００＞＜４＞
【００２３】
このような場合には、プリフェッチが実行され、ライン３００から始まる四つのラインサイズ、すなわち、ライン３００，４００，５００及び６００の命令を検索して命令キャッシュセット＃１に格納する。異なったプリフェッチにおいては、ライン１３００から始まるメモリブロックは、異なった特定の動作を実行するのに必要な二つのラインからなり、従って、命令キャッシュセット＃１におけるキャッシュミスを避けるために、ライン３００から始まるブロックと異なったセット、すなわち、命令キャッシュセット＃２に格納される。サイズフィールドとキャッシュセット位置の最適化のプロセスは、以下に議論される。
【００２４】
スラッシングの減少は、プリフェッチすべきデータの最適なキャッシュセット位置と最適な量に関する情報を備えたプリフェッチハードウェア（ＣＰＵ）を提供することにより強化される。コンピュータのアーキテクチャに依っては、コンパイラは、ＣＰＵの性能を最適化するために異なった方法を用いることもある。例えば、一つの実施形態においては、コンパイラは、例えば、プログラムの流れを考慮して、最も最近使用されたセットを割り当ててもよい。
【００２５】
代替案として、オペレーティングシステム、ローダ、或いは、ランタイムソフトウェアが、特定の方針に従って実行の期間中にバイナリ値を最後に提供するように、空フィールドが、コンパイルされたフェッチ命令においてコンパイラによって提供されてもよく、そして、そのような事は本発明の範囲内である。同様の配置は、ここに参考として組み込まれ、本願と同時に、出願番号第０  ／      号として１９９５年  月  日に出願された「プリフェッチ制御を組み込んだメモリ管理ユニット」と題された米国特許出願に記載されている。
【００２６】
図５を参照すると、プリフェッチ命令を実行するための順序を図示するフローチャートが示される。プログラムが要素４０で開始された後に、システムは、＜ＯＰＣＯＤＥ＞フィールド４２を、命令がプリフェッチ命令であるか、或いは、そうでないかを示しているものとして認識する。プリフェッチ命令４４が存在しない場合には、プログラムは異なった命令を再び始める。
【００２７】
システムが、命令が実際にプリフェッチ命令であることを判別したときには、第１の問い合わせは、＜Ｉ／Ｄ＞フィールド４６が、命令（ｉｎｓｔｒｕｃｔｉｏｎ）の「Ｉ」かデータ（ｄａｔａ）の「Ｄ」を示すかどうかである。ハーバードアーキテクチャを備えたシステムにおいては、＜Ｉ／Ｄ＞フィールドは、いずれのキャッシュに、すなわち、命令キャッシュとデータキャッシュのどちらに、検索された情報を格納するかを示すことになる。
【００２８】
＜Ｉ／Ｄ＞フィールドが、プリフェッチがデータをフェッチすることになることを示す場合には、データキャッシュ４８を選択する。その後に、＜ＳＥＴ＃＞５０によって特定されたデータキャッシュセットが選択される。次いで、システムは、要素５２の＜ＳＩＺＥ＞によって特定された長さの＜ＡＤＤＲ＞フィールドによって特定されたアドレスにおいて、データをプリフェッチする。最後に、データは、＜ＳＥＴ＃＞５４によって特定されたデータキャッシュセットへ書き込まれ、そして、５６で完了する。
【００２９】
代わりに、Ｉ／Ｄ決定ボックス４６が、命令がプリフェッチされるべきことを示す場合には、命令キャッシュは、要素５８において選択されることになる。その後に、＜ＳＥＴ＃＞６０によって特定される命令キャッシュセットが、選択される。次いで、システムは、要素６２の＜ＳＩＺＥ＞によって特定された長さの＜ＡＤＤＲ＞フィールドによって特定されたアドレスにおいて命令をプリフェッチする。最後に、命令は、＜ＳＥＴ＃＞６４によって特定された命令キャッシュセットへ書き込まれ、そして、５６で完了する。
【００３０】
図５の上記説明は、このプログラムが実行されるプラットホームが、プリフェッチを実行することの能力を有しており、マルチ−セットハーバードアーキテクチャであると仮定しているが、勿論この方法及びシステムは、クロスプラットホームである。例えば、システムがプリフェッチコマンドを実行することができない場合には、それは、＜ＯＰＣＯＤＥ＞フィールドを実行しない。同じく、システムがマルチプルセットを持っていない場合には、それは＜ＳＥＴ＃＞フィールドを単に無視することになる。＜Ｉ／Ｄ＞フィールドについても同様である。
更に、サイズフィールドに関して、コンパイラは、そのフィールドに、システムによって上書きされる或る値を与えることができる。ここで述べられた発明は、フィールド自身と、それを生成して使用するシステム及び方法にある。
【図面の簡単な説明】
【図１】  先行技術のシングル−セットキャッシュを示す。
【図２】  先行技術のマルチ−セットキャッシュを示す。
【図３】  高レベルプログラム、従属命令を挿入するコンパイラ、及び、従属命令を含む機械コードの関係を示す。
【図４】  本発明のプリフェッチ命令が実行されるハーバードアーキテクチャシステムを示す。
【図５】  本発明のプリフェッチ命令を実行するためのステップを示すフローチャートである。
【符号の説明】
１０  主メモリ
１２  キャッシュ
１４  ＣＰＵ
２０  プログラム
２２  コンパイラ
２４  プリフェッチ命令
２６  オブジェクトコード
２８  コンパイルされた命令
３０  キャッシュメモリ
【図１】
0003739491.tif 000002
【図２】
0003739491.tif 000003
【図３】
0003739491.tif 000004
【図４】
0003739491.tif 000005
【図５】
0003739491.tif 000006