(57)【要約】区分されたキャッシュのウェイ予測スキームは、メモリ内のデータ項目にアクセスするのに間接アドレス指定を用いる命令の内容に基づく。間接アドレス命令の内容が、メモリのアドレス計算を行うことなく直接用いられ、この直接用いられる情報に基づく予測スキームは、特にパイプラインアーキテクチャに適している。間接アドレス指定命令は、メモリアクセスの抽象化をより高いレベルで行うこともでき、データ項目の絶対アドレスに比べてデータ項目間の関係をよりよく示すと思われる。好適な実施形態では、間接アドレス指定命令に収容されるベースレジスタは、Ｎウェイアソシアティブキャッシュのウェイ予測テーブルに索引を与える。同じベースレジスタを用いて間接アドレス指定されるデータ項目は関係があると思われ、よって間接アドレス命令のベースレジスタに基づいてＮウェイアソシアティブキャッシュの特定のウェイを予測することは、キャッシュヒットにつながり、キャッシュ内のすべてのウェイにアクセスすることに伴うエネルギー消費を低減すると思われる。
2004519776.tif 000002
【特許請求の範囲】
【請求項１】
それぞれに複数の格納データ列（１２５）が格納される複数のセクション（Ｗａｙ−ａ，ｂ，．．．ｎ）を含むキャッシュメモリ（１２０）を備えるキャッシュシステム（２００）であって、
アドレス指定されたデータ項目が前記複数のセクションのうち予測されたセクション（ｐ）にある前記複数の格納データ列（１２５）の対応するデータ列に置かれているかどうかを判定し、
前記予測されたセクション（ｐ）は、前記アドレス指定されたデータ項目のアドレス（１１０）を与える間接アドレス指定命令（１６０）のサブセット（１６２，１６４）に基づいている、
ように構成されていることを特徴とする、キャッシュシステム（２００）。
【請求項２】
前記キャッシュメモリ（１２０）はＮウェイアソシアティブキャッシュに相当し、前記Ｎウェイアソシアティブキャッシュの各ウェイは、前記複数のセクションの一つを形成し、前記予測されたセクション（ｐ）は予測されたウェイであり、
各ウェイは、前記複数の格納データ列（１２５）に対応する複数の格納タグ（１２１）をさらに備え、
前記複数の格納データ列（１２５）と前記複数の格納タグ（１２１）のそれぞれは、前記アドレス指定されたデータ項目の前記アドレス（１１０）のインデックスフィールド（１１２）を介して、一義的にアドレス可能であり、
前記Ｎウェイアソシアティブキャッシュは、前記アドレス（１１０）のタグフィールド（１１１）と、前記予測されたウェイ内の、前記アドレス（１１０）の前記インデックスフィールドに相当する、前記複数の格納タグ（１２１）の一つとを比較して、前記アドレス指定されたデータ項目が前記予測されたウェイに置かれているかどうかを判定することを特徴とする、請求項１に記載のキャッシュシステム。
【請求項３】
前記Ｎウェイアソシアティブキャッシュは、前記アドレス指定されたデータ項目が前記予測されたウェイの対応するデータ列（１２５）に置かれていない場合、前記アドレス（１１０）の前記タグフィールド（１１１）と、前記複数のセクションの他のウェイにある、格納タグ（１２１）とを比較し、前記アドレス指定されたデータ項目が前記他のウェイの対応するデータ列（１２５）に置かれているかどうかを判定するように構成されていることを特徴とする、請求項２に記載のキャッシュシステム（２００）。
【請求項４】
前記Ｎウェイアソシアティブキャッシュは、前記アドレス指定されたデータ項目が、前記予測されたウェイまたは他のウェイの対応するデータ列に置かれていない場合、前記アドレス指定されたデータ項目をメモリから、前記複数のセクションの中の選択ウェイにロードすることを特徴とする、請求項３に記載のキャッシュシステム（２００）。
【請求項５】
前記間接アドレス指定命令（１６０）のサブセット（１６２，１６４）は、前記アドレス指定されたデータ項目の前記アドレス（１１０）のベースとなるベースアドレスを含む、ベースレジスタ（１６２）の識別子を含むことを特徴とする、請求項１に記載のキャッシュシステム（２００）。
【請求項６】
前記サブセット（１６２，１６４）は、前記アドレス指定されたデータ項目の前記アドレス（１１０）のさらなるベースとなる、前記間接アドレス指定命令（１６０）のオフセットフィールド（１６４）をさらに備えることを特徴とする、請求項５に記載のキャッシュシステム（２００）。
【請求項７】
前記予測されたセクション（ｐ）は、最小使用頻度判定に基づいていることを特徴とする、請求項１に記載のキャッシュシステム（２００）。
【請求項８】
メモリ内で参照されるデータ項目を間接参照（１６２，１６４）する少なくとも一つの間接アドレス指定命令を含むプログラム命令を受け取るように構成される命令レジスタ（１６０）と、
前記命令レジスタに含まれるビットのサブセット（１６２，１６４）に基づいて、参照されたデータ項目を含むと思われる予測されたセクション（ｐ）を、キャッシュ（２００）内の複数のセクション（Ｗａｙ−ａ，ｂ，．．．ｎ）から特定するよう構成される、予測装置（２５０）と、
を備えることを特徴とする、プロセッサ。
【請求項９】
前記命令レジスタ（１６０）に収容される前記ビットのサブセット（１６２，１６４）は、前記メモリ内の前記参照されたデータ項目のアドレス（１１０）を判定するのに用いられるベースアドレスを含む、ベースレジスタの識別子を含んでいることを特徴とする、請求項８に記載のプロセッサ。
【請求項１０】
前記命令レジスタ（１６０）に収容される、前記ビットのサブセット（１６２，１６４）は、前記メモリ内の前記参照されたデータ項目のアドレス（１１０）を判定するのにやはり用いられる、オフセットフィールド（１６４）の少なくとも一部分をさらに含んでいることを特徴とする、請求項９に記載のプロセッサ。
【請求項１１】
前記キャッシュ（２００）の前記複数のセクションは、Ｎウェイアソシアティブキャッシュの複数のウェイに相当し、
前記予測されたウェイ（ｐ）は、前記複数のウェイの中の予測されたウェイに相当することを特徴とする、請求項８に記載のプロセッサ。
【請求項１２】
参照されたデータ項目を含むと思われるキャッシュ（２００）内のセクションの予測方法であって、
参照されたデータ項目を間接的にアドレス指定する間接アドレス指定命令（１６０）から複数のビット（１６２，１６４）を抽出する工程と、
前記間接アドレス指定命令（１６０）からの前記複数のビット（１６２，１６４）に基づいて、前記キャッシュ（２００）の前記セクションを判定（２５０）する工程と、
を有することを特徴とする、予測方法。
【請求項１３】
前記複数のビット（１６２，１６４）は、前記参照されたデータ項目のアドレス（１１０）を判定するのに用いられるベースレジスタ（１６２）の識別子を含むことを特徴とする、請求項１２に記載の予測方法。
【請求項１４】
前記複数のビット（１６２，１６４）は、前記参照されたデータ項目の前記アドレスを判定するのにさらに用いられる、オフセットフィールド（１６４）の少なくとも一部をさらに含むことを特徴とする、請求項１３に記載の予測方法。
【発明の詳細な説明】
【０００１】
発明の背景
１．発明の技術分野
本発明はコンピュータシステムの分野に関し、特にアドレス指定されたデータ項目を含むと思われるキャッシュ内の特定のウェイの予測装置として、命令ベースレジスタを用いる、予測型Ｎウェイアソシアティブキャッシュに関する。
【０００２】
２．関連技術の記載
一般的にキャッシュシステムは、比較的低速のメモリ装置へのアクセスに関連しておこる有効遅延を低減するために用いられる。そのような低速のメモリ内にある、特定のデータ項目へのアクセスをプロセッサが要求する場合、キャッシュシステムは要求されたデータ項目をより高速のメモリにロードする。その後、同じデータ項目に対するアクセスは高速のメモリ経由で行われ、これにより低速のメモリに関連する遅延を回避する。一般的に、データ項目の要求があった場合は、要求されたデータ項目を含むデータ項目の「列」が低速のメモリから高速のメモリへとロードされ、高速メモリは、ロードされた列の全てのデータ項目を順次提供することができるようになる。
【０００３】
キャッシュメモリアクセスシステムの有効性は、将来的になされるデータアクセスは、過去になされたデータアクセスに関連するという可能性に基づいている。一般的に、要求されたデータ項目が、キャッシュにおいて過去に要求されたデータ項目と同じ列に含まれている可能性は、実質的にゼロ以上であり、よって、高速のキャッシュメモリからの要求を満たす可能性はこれに対応して実質的にゼロより大きい。
【０００４】
高速メモリのコストは低速メモリのコストより高く、よって一般的に、利用可能なキャッシュメモリの量は限られる。高速メモリに新しいデータの列をロードする必要がある時、どのデータ項目を高速メモリから削除するのかを決定するために、キャッシュ管理スキームが用いられる。高速メモリ内のデータ項目を維持するために一般的に用いられる優先順位スキームには、「最小使用頻度」（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ＝ＬＲＵ）条件があり、これは最近の使用頻度が最も低い（つまり、「古めの」）メモリアクセスの列を新しい列に置き換えることにより、最近使われ、アクセスされているデータ項目を保持するものである。他の条件、例えば「最大使用頻度」を、通常はＬＲＵ優先順位スキームと併用して、使うことも可能である。
【０００５】
要求された項目のアドレスのサブセットに基づいてデータ項目の列を格納するために、一般的にアソシアティブキャッシュが用いられる。図１は、アソシアティブキャッシュ１００に対する従来のアドレス指定スキームを示す。一般的にはプロセッサから出力されるアドレス１１０（以下でさらに記載する）は、タグフィールド１１１、インデックスフィールド１１２、およびワードフィールド１１３に論理的に区分けされる。インデックスフィールド１１２は、キャッシュ１２０内の関連するキャッシュ列のセットに索引を与える。このセットのそれぞれのキャッシュ列を「ウェイ」と呼び、キャッシュ１００はＮウェイアソシアティブキャッシュに相当する。ワードフィールド１１３のサイズｊは、データ列のサイズ２ｊに対応する。よって、もしデータ列あたり１６ワードあれば、ワードフィールド１１３のサイズは４ビットである。データ列あたり６４ワードあれば、ワードフィールド１１３は６ビット幅である。この、ワードフィールド１１３とデータ列のサイズとの間の、２の累乗の関係を用いて、タグフィールドとインデックスフィールドはメモリ中のデータ列を一義的に特定する。
【０００６】
低速メモリ（図示せず）からキャッシュ１２０にアドレス指定されたデータがロードされると、そのデータ項目を含むデータ列が選択ウェイに置かれ、インデックスフィールドは選択ウェイの中でデータ列を置く場所を定める。ウェイの選択は、上述したＬＲＵ優先順位スキームのような、一般的に用いることのできる種々のアルゴリズムの一つを用いて行われる。アドレス指定されたデータ項目がキャッシュ１２０内の特定の列領域ＤＬｉｎｅ−ａ、ＤＬｉｎｅ−ｂ等に格納されるとき、図１にＴａｇ−ａ、Ｔａｇ−ｂ等のフィールドで表されるように、タグフィールド１１１もまた格納される。格納されたタグフィールドは、データ列のインデックスフィールドに対応する、ウェイ内でのデータ列の場所との組み合わせにより、一義的にキャッシュ１２０内に格納されているデータ列を特定する。
【０００７】
アドレス指定されたデータ項目がキャッシュ１２０にロードされる前に、キャッシュ１２０はそのデータ項目がすでに自己の中に置かれているかどうかをチェックし、低速メモリからデータ項目をロードする可能性を回避する。アドレス指定されたデータは、過去にアクセスされたことによって、あるいはそのデータ項目と同じデータ列（ＤＬｉｎｅ−ａ、ＤＬｉｎｅ−ｂ等）にあるデータ項目が過去にアクセスされたことによって、キャッシュ内に置かれている可能性がある。インデックスフィールド１１２は、このアドレスに関連するキャッシュ内のＮ列のセットを特定する。関連するセット内に格納されている１２５ａ、１２５ｂ等の各列に対応する、１２１ａ、１２１ｂ等の格納タグはそれぞれ、コンパレータ１３０ａ、１３０ｂ等を介して、アドレス指定されたデータ項目のタグフィールド１１１と比較される。比較が行われている間、インデックスフィールド１１２に対応する格納データ列１２５ａ、１２５ｂ等は、高速バッファ１４０にロードされ、データ項目が現在キャッシュにロードされている場合に利用できるようになる。
【０００８】
アドレス指定されたデータ項目が現在キャッシュ内にロードされている場合、対応するコンパレータ１３０ａ、１３０ｂ等は、キャッシュヒット信号をアサートにし、これによりデータ列を含む特定のウェイＨｉｔ−ａ、Ｈｉｔ−ｂなどを割り出す。ヒットがアサートされると、適当なワードが対応するバッファ１４０から取り出される。適当なワード１４１ａ、１４１ｂ等をバッファ１４０に収容されているデータ列から選択するために、ワードフィールド１１３が用いられる。取り出されたワードはアドレス１１０を与えたプロセッサに渡される。従来例のキャッシュシステム１００においては、タグフィールド１１１と格納タグフィールド１２０ａ、１２０ｂ等とを比較し、キャッシュヒットがあったとき、続いて適当なワード１４１ａ、１４１ｂ等を選択するのに必要な時間は、低速メモリに関する遅延時間より実質的に少ない。このように、データ項目がキャッシュ１２０内にあるとき、そのデータ項目にアクセスする実効アクセス時間は、実質的に低減されている。
【０００９】
キャッシュヒットがなかった場合、主としてデータ列を使用頻度が最小の（ＬＲＵ）ウェイや、上述した他の優先順位スキームにロードすることにより、アドレス指定されたデータ項目をメモリからキャッシュ１２０の選択ウェイＷａｙ−ａ、Ｗａｙ−ｂ等にロードする上述の作業が行われる。
【００１０】
ワードを有効にプロセッサからメモリに格納するのに必要な時間も、キャッシュ１２０を経由することにより同様に短縮される。キャッシュ１２０内にアドレス指定されたデータ項目が存在することが、上述の比較プロセスを用いて判断される。データ項目が現在キャッシュ内にある場合、プロセッサからのデータ項目の新しい値がバッファ１４０の選択ワードに取って代わり、バッファ１４０はアドレス指定されたデータ項目を含むデータ列１２５ａ、１２５ｂ等にロードされる。「修正された」フィールド１２９は、キャッシュされた列の内容に変更があったことを表すために用いられる。データ列が新しいデータ列に上書きされる前に、修正されたフィールド１２９はチェックされ、もしデータ列が修正されていた場合、修正されたデータ列は、メモリ内に列を格納する場所を特定するのに格納タグフィールド１２１ａ、１２１ｂ等を用いて、メモリに格納されなおされる。
【００１１】
Ｎウェイアソシアティブキャッシュは実効メモリアクセススピードを増すための有効な手段であるが、アドレス指定されたデータ項目のタグと格納されている全てのタグとを比較する同時ウェイ比較スキームは、１ウェイアソシアティブキャッシュのＮ倍もの割合でエネルギーを消費する。Ｎウェイアソシアティブキャッシュが、集積回路やプリント基板の他の部分より熱くなるのは珍しいことではない。
【００１２】
従来のＮウェイアソシアティブキャッシュの電力消費を低減するために、予測テクニックを利用して、与えられたアドレスに対応する可能性のあるウェイを選択することがある。従来例のウェイ予測スキームでは、アドレス指定されたデータ項目に対し、可能性のあるウェイがまずチェックされ、このウェイがアドレス指定されたデータ項目を含んでいなかった場合に限り、残りのウェイがチェックされる。Ｋｏｊｉ  Ｉｎｏｕｅ他による、「推測的ウェイ選択による高性能及び低電力キャッシュアーキテクチャ」（ＩＥＩＣＥ  Ｔｒａｎｓ．  Ｅｌｅｃｔｒｏｎ、第Ｅ８３−Ｃ巻、第２号、２０００年２月、１８６−１９４ページ）（引用により、本明細書中に含まれているものとする）には、ウェイ予測スキームと、ウェイ予測スキームによるエネルギー消費と非予測スキームによるエネルギー消費の比較が示されている。予測成功率が高ければ、エネルギーの節約はかなりのものとなる。ウェイ予測が成功する度に、Ｎ倍分のエネルギー削減が達成できるからである。
【００１３】
図１に、アドレス指定されたデータ項目に関連する特定のウェイを予測するために用いられるウェイ予測テーブル１５０の例を示す。データアドレス１１０のサブセットが、ウェイ予測テーブル１５０に索引をつけるために用いられる。アドレス１１０のサブセットを特定するため、およびウェイ予測テーブル１５０の内容を得るために用いられるアルゴリズムを特定するために、様々なスキームを用いることができる。簡単に表された実施形態では、テーブル１５０に索引をつけるために用いられるサブセットとして、インデックスフィールド１１２を用い、テーブル１５０の内容は、各索引に対し、最小使用頻度（ＬＲＵ）ウェイ、Ｗａｙ−ａ、Ｗａｙ−ｂ等に対応する。あるいは、インデックスフィールド１１２のサブセット、またはタグフィールド１１１およびインデックスフィールド１１２の両方から得られたサブセットを用いてウェイ予測テーブル１５０の索引を得てもよい。ウェイ予測テーブルに索引をつけるためのアドレス１１０のサブセットと、ウェイの数Ｎの選択により、必要なウェイ予測テーブルのサイズが決定される。８ウェイアソシアティブキャッシュでは、ウェイ予測テーブルの各ウェイを一義的に特定するために３ビットが必要とされ、テーブル１５０における３ビットエントリの数は、テーブル１５０に索引をつけるためのアドレスのサブセットの一義的な組み合わせの数によって決定される。例えば、テーブル１５０に索引をつけるのに１０ビットが使われるとすると、テーブル１５０では１，０２４（２１０）の３ビットエントリができなければならない。
【００１４】
アドレス１１０が要求されると、予測されたウェイのみを、選択的にアクセスするために、ウェイ予測テーブル１５０から予測されたウェイのみが使用される。便宜上、予測されたウェイを表すために、今後添え字ｐを用いることにする。選択されたウェイｐのインデックスフィールド１１２に対応する格納タグ１２１ｐは、選択されたウェイのコンパレータ１３０ｐに提供され、対応するデータ列１２５ｐが選択されたウェイｐのバッファ１４０ｐに提供される。予測されたウェイがデータ列を含んでいた場合、Ｈｉｔ−ｐ信号がアサートされ、アドレス指定されたワードがバッファ１４０ｐから、要求を出しているプロセッサに提供される。予測されたウェイｐがアドレス指定されたデータ項目を含んでいなかった場合は、アドレス指定されたデータ項目を探してＮウェイアソシアティブキャッシュをチェックする、上述のテクニックを用いて、予測されなかった各ウェイがチェックされ、アドレス指定されたデータ項目の存在を探す。
【００１５】
もしいずれのウェイもアドレス指定されたデータ項目を含んでいなければ、指定されたデータ項目を含んだデータ列がメモリからキャッシュ１２０の、通常は使用頻度が最小のウェイの索引位置にロードされる。ウェイ予測テーブル１５０は使用頻度が最大のウェイを格納するように構成されていると仮定して、データ列を格納するために使用されたウェイの識別（ｉｄｅｎｔｉｆｉｃａｔｉｏｎ）（識別子）がウェイ予測テーブル１５０に格納される。このようにして、現在アドレス指定されているデータ項目と同じデータ列にあるデータ項目が引き続き要求されると、ウェイが正しく予測され、電力消費を節約することができる。
【００１６】
この節電スキームの他の種類のものもまた用いられる。例えば、タグ１２１ａ、１２１ｂ、等のすべてが対応するコンパレータ１３０ａ、１３０ｂ、等にロードされるが、予測されたウェイｐのデータ列１２５ｐのみがバッファ１４０ｐにロードされてもよい。これにより、予測されたウェイが指定されたデータ項目を含んでいなかった場合に、予測されなかったウェイの全てのデータ列１２５ａ、１２５ｂ、等をバッファ１４０ａ、１４０ｂ等にロードするのを回避し、またすべてのタグフィールド１２１ａ、１２１ｂ等を再チェックするのに要する時間を省けるため、節電をすることができる。もし他のタグコンパレータ１３０の一つがヒット信号をアサートにすると、対応するウェイのデータ列が対応するバッファ１４０にロードされ、適当なワードがプロセッサに提供される。他のタグコンパレータ１３０がいずれもヒット信号をアサートにしなければ、上述の通り、アドレス指定されたデータ列がメモリからキャッシュ１２０にロードされる。
【００１７】
図１の従来のウェイ予測スキームでは、命令の間接アドレスに対応するメモリアドレスを判定した後でウェイ予測を行っている。パイプラインアーキテクチャでは、メモリアドレスの判定はしばしばクリティカルパス上で行われ、ウェイ予測のために遅延が生じると、全体的なプロセッサ性能に直接的な影響を与えることになりうる。
【００１８】
発明の概要
本発明の目的は、プロセッサのクリティカルパスの外でのウェイ予測を可能にする方法およびシステムを提供することである。さらに、本発明の目的は、Ｎウェイアソシアティブキャッシュのウェイ予測の成功率を潜在的に向上させる方法およびシステムを提供することである。また、本発明の目的は、従来のアドレスベースのウェイ予測スキームより効率のよい、ウェイ予測スキームを提供することである。
【００１９】
これらおよび他の目的は、メモリ内のデータ項目にアクセスするのに間接アドレス指定を用いる命令の内容に基づいたＮウェイアソシアティブキャッシュのウェイ予測スキームを提供することによって達成される。パイプライン処理のために間接アドレス命令の内容はいつでも参照でき、本発明のウェイ予測スキームはメモリアドレスの計算を必要としない。間接アドレス指定命令の内容により、メモリアクセスの抽象化をより高いレベルで行うことができ、よってデータ項目の絶対アドレスよりも、データ項目間の関係をよりよく示すものと思われる。好適な実施形態では、間接アドレス命令に含まれるベースレジスタがウェイ予測テーブルの索引を与える。同じベースレジスタを用いて間接アドレス指定されるデータ項目は関係があるものと思われ、よって間接アドレス指定命令のベースレジスタに基づいてＮウェイアソシアティブメモリの特定のウェイを予測することは、キャッシュヒットにつながり、キャッシュ内の全てのウェイへのアクセスに伴うエネルギー消費を削減することができるものと思われる。
【００２０】
添付の図面を参照しながら本発明をさらに詳細に、例をあげながら説明する。
【００２１】
図全体に渡り、同じ参照番号は同様のあるいは対応する特徴又は機能を表す。添え字のある項目は、一般的な特徴又は機能の特定の例を表している。明細書中で添え字なしで参照された項目は、図示された項目のうち、同じ参照番号をもつ一つまたはすべてのものを表す。
【００２２】
発明の詳細な説明
図１は、間接アドレス指定命令１６０を介してメモリ内のデータ項目を間接アドレス指定する一般的な方法を示す。プロセッサに与えられる命令１６０は、「ロード」「格納」など、実行される動作を特定するオペレーションコードフィールド１６１を含む。ベースレジスタフィールド１６２およびオフセットフィールド１６４は、後で詳細に述べるようにメモリ内のアドレスを間接参照するために用いられる。レジスタフィールド１６３は（「ロード」命令において）データ項目を受け取ったり、（「格納」命令において）提供したりするプロセッサの内部レジスタを特定する。
【００２３】
アドレス指定スペースが大きいと、明示アドレスまたは直接アドレスを収容するのに必要な命令のサイズも大きくなる。６４Ｋワードという比較的小さなアドレススペースをアドレス指定するために、たとえばアドレスを含む命令に１６ビットを割り当てなくてはならない。アドレススペースがより大きくなると、アドレスを収容するためにより大きな命令幅が必要となる。各データ転送命令において、明示アドレスを提供する代わりに、アドレスがレジスタ１７０に格納され、命令１６０は単にこのレジスタの識別子１６２を含む。命令１６０においてレジスタ１７０を参照することは、レジスタ１７０に含まれるアドレスを間接的に参照することである。一般的には８、１６、３２、または６４レジスタが提供され、それぞれ命令１６０のアドレスの識別子１６２を格納するのに３、４、５、または６ビットを必要とするのみである。それぞれのレジスタ１７０のサイズは、メモリのアドレススペースに対応するアドレスを収容するのに十分なサイズである。新しいアドレスをそのたび毎にレジスタ１７０にリロードする必要性を回避するために、間接アドレス指定命令１６０にはオフセットフィールド１６４が与えられている。ベースレジスタ１７０への参照１６２と命令１６０におけるオフセット１６４とに対応する絶対アドレス１１０は、加算器１８０を介してベースレジスタ１７０とオフセット１６４の内容を加算することによって決定される。特定のプロセッサによっては、オフセットは符号付きの、あるいは符号無しの整数であり、符号付き整数の構成にすると、ベースレジスタ１７０の内容から順方向および逆方向のオフセットが可能となる。
【００２４】
本発明は、間接アドレス指定命令は、プログラムにおけるデータの関係をより高いレベルで抽象化できるという考えを前提条件にしている。例えば、一般的にコンパイラはあるサブルーチン内の全ての一時変数を近接するメモリ領域に置く。これらの一時変数はそれぞれ一つのベースアドレスのオフセット範囲にあると仮定すると、コンパイラは一時変数のそれぞれを参照するために特別なベースレジスタを特定することになる。一時変数が参照されるたび、命令１６０には同じベースレジスタが現れる。同様に、サブルーチンへパスされる特別な引数や、これらの引数へのポインタは、メモリ内の近接した、またはほぼ近接した領域に一時的に置かれることが多く、共通のベースレジスタから参照されることになる。共通のベースレジスタがメモリ内で空間的に関連したデータ項目を参照するのに用いられる他の例としては、アレイの項目の参照、文字列内の文字の参照、などがある。他の見方をすると、同じベースレジスタを含む間接アドレス指定命令は、互いに空間的に関連した項目を参照しがちであり、よって、同じベースレジスタを含む間接アドレス指定命令の発生に基づいてデータの関係を予想することは、成功し、高いキャッシュヒットを得られるものと思われる。
【００２５】
本発明は、Ｎウェイアソシアティブキャッシュに用いるのに特に適しているが、参照されるデータ項目を含むと思われるキャッシュのセクションを予想するのにアドレスのフィールドを従来通りに用いる他のキャッシュスキームに適用することもできる。予測に用いられる従来のアドレスフィールドを増したり、参照されるベースレジスタの識別子と置き換えることにより、より高いキャッシュヒット率が期待できる。ベースレジスタの使用とデータ項目間の空間的関係の存在との間には、間接的な関係があるからである。本発明が区分されたキャッシュを用いる他のキャッシュスキームに適用できることは当業者にとっては明らかであろうが、便宜上本明細書では、本発明はＮウェイアソシアティブキャッシュの例として表すことにする。
【００２６】
図２は、本発明による、ウェイ予測を行うＮウェイアソシアティブキャッシュ２００の例を示すブロック図である。図２には、参照されるデータ項目に対応するキャッシュ１２０のウェイを予測する基準として、プロセッサに与えられる間接アドレス指定命令１６０の内容を用いるウェイ予測テーブルが示されている。図の例では、ベースレジスタ１６２は、予測されたウェイを得るためのウェイ予測テーブル２５０に索引を与える。同じベースレジスタ１６２を含む命令はレジスタ１７０の内容のオフセット１６４の範囲内にある関連するデータ項目を参照することが多いため、もし参照されるデータ項目が実際にキャッシュ１２０内にある場合、予測されたウェイはおそらくそのデータ項目を含むウェイである。
【００２７】
予測されたウェイが参照されたデータ項目を含んでいる可能性は、各キャッシュ列に含まれるデータ項目の数による。各列のデータ項目が多いほど、その列内に参照されたデータ項目がある可能性が高くなる。同様に、予測されたウェイが参照されたデータ項目を含む可能性は、関連するキャッシュ列を同じウェイに格納するキャッシュ割り当てスキームを用いることにより、増大する。つまり、例えば新しいキャッシュ列をロードするのにどのウェイを用いるかを決定する、上述のＬＲＵ優先順位スキームは、新しいキャッシュ列を、同じベースレジスタ１６２を有し、過去にロードされたキャッシュ列と同じウェイにロードされるように修正されてもよい。ここで開示されているような、間接アドレスベース予測スキームの効果を向上させる、これらおよび他のスキームは、当業者には明らかであろう。
【００２８】
メモリアドレスの計算を必要とせず、予測成功率を潜在的に向上させる予測スキームの提供に加えて、本発明のウェイ予測テーブル２５０によるリソースの消費は、従来のウェイ予測テーブル１５０より、はるかに少ないと期待できる。上述したとおり、通常レジスタ１７０の数は６４までに制限されており、一般的には３２である。本発明によるウェイ予測テーブル２５０の総メモリ要求量は、レジスタ１７０の数をキャッシュ１２０の各ウェイを一義的に特定するのに必要なビット数をかけたものに等しい。一般的に、レジスタ１７０の数はアドレス１１０のインデックスフィールド１１２に与えられる索引の数よりかなり小さい。故に、ウェイ予測テーブルのサイズを削減することができるのである。
【００２９】
好適な実施形態では、命令を実行するときにデータアクセスを開始してもかまわないにもかかわらず、命令１６０は実際に実行される前にデータアクセスを開始するように処理されている。ベースレジスタ１６２の内容はウェイ予測テーブル２５０で予測されたウェイに索引を付けるために使われる。この予測されたウェイは、キャッシュ１２０の予測されたウェイｐをイネーブルにし、コンパレータ１３０ｐ経由で予測されたウェイ内にアドレス指定されたデータ項目が含まれているかどうかをチェックできるようにする。このチェック作業と平行して、もし予測されたウェイｐがアドレス指定されたデータ項目を含んでいると、データ列１２５ｐが直ちに使用可能なようにバッファ１４０ｐにロードされる。予測されたウェイがアドレス指定されたデータ項目を含んでいると、ワードフィールド１１３がバッファ１４０ｐのデータ列からアドレス指定されたデータ項目を選択し、命令１６０が実行されるときにプロセッサにそれを渡す。予測されたウェイｐがアドレス指定されたデータ項目を含んでいなかった場合は、図１に関連して上に詳述したように、他のウェイがチェックされる。
【００３０】
上述のことは、単に本発明の原理を述べただけにすぎない。当業者であれば、本明細書では明白に記載はしていなくても、本発明の範囲内で本発明の原理を具体化した様々な構成例を考案することは可能である。例えば、予測のレベルをさらに正確なものにするために、ベースレジスタ１６２とオフセット１６４のサブセットの組み合わせを用いることができる。例えば、もしオフセットが符号付きの整数であればベースレジスタ１６２とオフセット１６４の最上位ビットの組み合わせにより、レジスタ１７０に含まれるベースアドレスより小さい項目を参照するウェイ予測と、ベースアドレスより大きい項目を参照するウェイ予測を行うことができる。オフセット１６４の他のビットをさらに用いることにより、予測の精度をさらに上げることができる。極端な例では、ウェイ予測テーブルは、オフセット１６４のデータ列サイズのセグメントについてそれぞれ予測するように構成してもよい。この構成では、従来のアドレスベースのタグ予測と同じ程度、あるいはそれ以上のビット格納が必要となるかも知れないが、ウェイ予測テーブルを構成するのにベースレジスタを用いることにより、従来のアドレスベースのウェイ予測スキームよりかなり高いキャッシュヒット率を得ることが期待できる。上述の、および他のシステム構成や最適化構成は本明細書の開示内容を参照すれば当業者には明らかであり、添付の請求項の範囲に含まれるものである。
【図面の簡単な説明】
【図１】
従来の、ウェイ予測を行うＮウェイアソシアティブキャッシュの例を示すブロック図。
【図２】
本発明によるウェイ予測を行うＮウェイアソシアティブキャッシュの例を示すブロック図。
【図１】
2004519776.tif 000003
【図２】
2004519776.tif 000004
【国際公開パンフレット】
2004519776.tif 000005
2004519776.tif 000006
2004519776.tif 000007
2004519776.tif 000008
2004519776.tif 000009
2004519776.tif 000010
2004519776.tif 000011
2004519776.tif 000012
2004519776.tif 000013
2004519776.tif 000014
2004519776.tif 000015
2004519776.tif 000016
2004519776.tif 000017
2004519776.tif 000018
2004519776.tif 000019
2004519776.tif 000020
【国際公開パンフレット（コレクトバージョン）】
2004519776.tif 000021
【国際調査報告】
2004519776.tif 000022
2004519776.tif 000023
2004519776.tif 000024