(57)【特許請求の範囲】
【請求項１】
（ｉ）データを処理するための少なくとも１つのデータ・プロセッサと、
（ｉｉ）前記データ・プロセッサにより処理される複数の値を格納するためのセット連想キャッシュであって、各値はそれを格納するメモリ内のメモリ場所のアドレスにより識別され、前記セット連想キャッシュは複数のキャッシュ・ウェイへ分割されるセット連想キャッシュと、
（ｉｉｉ）複数の識別子を格納するための複数の記憶場所を含むデータ・ストアであって、各識別子は前記セット連想キャッシュからの対応する値が格納されるキャッシュ・ウェイを識別しかつ各々が関連する有効なインジケータを有し、前記複数の識別子は複数の値に対応し、前記複数の値は前記データ・ストアが前記メモリの領域内に格納された値に対する識別子を格納するように連続アドレス内に格納される値であるデータ・ストアと、
（ｉｖ）前記データ・ストア内の最も最近アクセスされた記憶場所を指すカレント・ポインタを格納するカレント・ポインタ・ストアと、
（ｖ）キャッシュ・アクセス要求に応答してすぐ前のキャッシュ・アクセス要求に対する前記キャッシュ・アクセス要求のアドレスのオフセットを決定するオフセット決定回路であって、前記カレント・ポインタを前記オフセット量だけ更新するようにしたオフセット決定回路と、
（ｖｉ）前記データ・ストアのサイズと前記オフセットから、前記更新されたカレント・ポインタが前記領域内のアドレスを指しているかどうかを決定し、そうであれば、前記データ・プロセッサは関連する有効なインジケータを有する場合に前記カレント・ポインタにより指示された前記格納された識別子から前記キャッシュ・ウェイを識別するようにしたデータ・ストア・ルックアップ回路と、
を含むデータ処理装置。
【請求項２】
請求項１に記載のデータ処理装置であって、さらに、
（ｉ）連続アドレスの前記領域内の予め定められた位置に対応する前記データ・ストア内のエントリを指している領域ロケータ・ポインタを格納する領域ロケータ・ポインタ・ストアを含み、
（ｉｉ）前記データ・ストア・ルックアップ回路は、前記領域ロケータ・ポインタに対する前記カレント・ポインタの値から、前記更新されたカレント・ポインタが前記領域内のアドレスを指しているかどうかを決定するようにされている、データ処理装置。
【請求項３】
請求項２に記載のデータ処理装置であって、前記領域ロケータ・ポインタは最低アドレスを有する値に対応する前記データ・ストア内の記憶場所を指すデータ処理装置。
【請求項４】
請求項２に記載のデータ処理装置であって、
前記データ・ストア・ルックアップ回路は前記更新されたカレント・ポインタおよび前記領域ロケータ・ポインタを比較し、前比較に応答して前記更新されたカレント・ポインタが前記領域の外側であるかどうかを決定する比較器を含むデータ処理装置。
【請求項５】
請求項２に記載のデータ処理装置であって、さらに、データ・ストア更新回路を含み、前記データ・ストア更新回路は前記更新されたカレント・ポインタが前記領域の外側であるという指示の前記データ・ストア・ルックアップ回路からの受信に応答して、前記領域が前記オフセット量だけ移動されるように前記領域ロケータ・ポインタを前記オフセット量だけ更新し、もはや前記領域内ではないアドレスに対応する前記記憶場所を無効とするデータ処理装置。
【請求項６】
請求項５に記載のデータ処理装置であって、前記データ・ストア更新回路は、さらに、前記更新されたカレント・ポインタが前記領域の外側であるという指示の前記データ・ストア・ルックアップ回路からの受信に応答して、タグＲＡＭルックアップを開始し前記キャッシュ・アクセス要求の前記値を格納するウェイを特定し、さらに、前記更新されたカレント・ポインタにより指示された前記データ・ストア内の前記エントリを前記ウェイを識別する識別子で更新するデータ処理装置。
【請求項７】
請求項２に記載のデータ処理装置であって、前記データ・ストアは環状バッファを含むデータ処理装置。
【請求項８】
請求項７に記載のデータ処理装置であって、前記ポインタは前記データ・ストア内のいかなる前記記憶場所も指すことができるようにいくつかのビットを有するカウンタを含むデータ処理装置。
【請求項９】
請求項１に記載のデータ処理装置であって、前記値は前記データ・プロセッサにより処理されるデータ・アイテムを含むデータ処理装置。
【請求項１０】
請求項１に記載のデータ処理装置であって、前記値は前記データ・プロセッサにより処理されるデータ・アイテムを含むデータ処理装置。
【請求項１１】
請求項１に記載のデータ処理装置であって、前記オフセット決定回路は前記キャッシュ・アクセス要求の仮想アドレスの予め定められたビットを前記すぐ前のキャッシュ・アクセス要求の仮想アドレスの前記予め定められたビットと比較する比較器を含むデータ処理装置。
【請求項１２】
請求項１に記載のデータ処理装置であって、前記セット連想キャッシュと関連するプリフェッチ・ユニットを含み、前記プリフェッチ・ユニットはフェッチされる後の命令が連続アドレス内にあることの検出に応答してシーケンシャル・インジケータを出力し、前記オフセット決定回路は前記シーケンシャル・インジケータに応答して前記カレント・ポインタを増分するデータ処理装置。
【請求項１３】
請求項１に記載のデータ処理装置であって、前記データ・ストアのアクセッシングおよび無効インジケータの検出に応答して、前記データ処理装置はタグＲＡＭルックアップを実施することにより前記記憶場所および前記有効ビットを更新するデータ処理装置。
【請求項１４】
請求項１に記載のデータ処理装置であって、前記データ・ストアはマイクロタグを含むデータ処理装置。
【請求項１５】
複数のキャッシュ・ウェイのいずれがセット連想キャッシュへのキャッシュ・アクセス要求を処理するかを決定する方法であって、
（ｉ）キャッシュ・アクセス要求に応答してすぐ前のキャッシュ・アクセス要求に対する前記キャッシュ・アクセス要求のアドレスのオフセットを決定するステップと、
（ｉｉ）データ・ストア内の最も最近アクセスされた記憶場所を指しているカレント・ポインタを前記オフセット量だけ更新するステップであって、前記データ・ストアは複数の識別子を格納するための複数の記憶場所を含み、各識別子は前記セット連想キャッシュからの対応する値が格納されるキャッシュ・ウェイを識別しかつ各々が関連する有効なインジケータを有し、前記複数の識別子は複数の値に対応し、前記複数の値は前記データ・ストアが前記メモリの領域内に格納された値に対する識別子を格納するように連続アドレス内に格納される値であるステップと、
（ｉｉｉ）前記データ・ストアのサイズと前記オフセット量から前記更新されたカレント・ポインタが前記領域内のアドレスを指しているか決定するステップと、
（ｉｖ）そうであれば、関連する有効なインジケータを有する場合に前記ポインタにより指示される前記格納された識別子から前記キャッシュ・ウェイを識別するステップと、
を含む方法。
【請求項１６】
請求項１５に記載の方法であって、前記更新されたカレント・ポインタが前記領域内のアドレスを指しているか決定する前記ステップは連続アドレスの前記領域内の予め定められた位置に対応する前記データ・ストア内のエントリを指す領域ロケータ・ポインタの相対位置を前記更新されたカレント・ポインタと比較するステップを含む方法。
【請求項１７】
請求項１６に記載の方法であって、前記方法は、さらに、前記更新されたカレント・ポインタが前記領域の外側であると決定する前記決定ステップに応答して前記領域が前記オフセット量だけ移動されるように前記領域ロケータ・ポインタを前記オフセット量だけ更新し、もはや前記領域内ではないアドレスに対応する前記記憶場所を無効とするステップを含む方法。
【請求項１８】
請求項１７に記載の方法であって、前記方法は、さらに、もはや前記領域内ではないアドレスに対応する前記記憶場所を無効とするステップに続いてタグＲＡＭルックアップを開始して前記キャッシュ・アクセス要求の前記値を格納するウェイを特定し、前記更新されたカレント・ポインタにより指示される前記データ・ストア内の前記エントリを前記ウェイを識別する識別子で更新するステップを含む方法。
【請求項１９】
請求項１５に記載の方法であって、すぐ前のキャッシュ・アクセス要求に対する前記キャッシュ・アクセス要求のアドレスのオフセットを決定する前記ステップは、前記キャッシュ・アクセス要求の仮想アドレスの予め定められたビットを前記すぐ前のキャッシュ・アクセス要求の仮想アドレスの予め定められたビットと比較するステップを含む方法。
【請求項２０】
請求項１５に記載の方法であって、すぐ前のキャッシュ・アクセス要求に対する前記キャッシュ・アクセス要求のアドレスのオフセットを決定する前記ステップは、プリフェッチ・ユニットにより出力されるシーケンシャル・インジケータを検出してフェッチされるシーケンシャル・インジケータは連続アドレス内にあることを指示するステップを含み、前記カレント・ポインタを更新する前記ステップは前記シーケンシャル・インジケータの検出に応答してそれを増分するステップを含む方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はマイクロタグを使用するキャッシュのアクセッシングに関する。
【背景技術】
【０００２】
キャッシュはデータ処理装置内でますます大量のデータを格納するのに使用される。大量のデータを格納するとキャッシュ内のデータへのアクセッシングは比較的大きいサイズのアドレスを必要とする極めて複雑な手順となることがある。したがって、このようなアドレスの操作は相当な量の電力および時間を必要とすることがある。内部の記憶場所へのアクセッシングに伴う電力および時間オーバヘッドを低減するために、キャッシュはいくつかの方法で編成されている。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
キャッシュを構成する１つの評判が良い方法はいわゆる「セット連想」キャッシュである。１６Ｋバイト・セット連想キャッシュが図１に示されている。図示されているキャッシュは各々がいくつかのキャッシュ・ライン２０を含む４ウェイ１１，１２，１３，１４を有する４ウェイ・セット連想キャッシュ１０である。特定のアドレス３５に関連づけられたデータ値（下記の例では、語）を４ウェイのいずれか特定のキャッシュ・ライン内に格納することができる（すなわち、一般的に参照番号２２で示すように、各セットは４キャッシュ・ラインを有する）。各ウェイが４Ｋバイト（１６Ｋバイト・キャッシュ／４ウェイ）を格納する。各キャッシュ・ラインが８つの３２ビット語を格納すれば各ウェイに３２バイト／キャッシュ・ライン（８語×４バイト／語）および１２８キャッシュ・ラインがある（（４Ｋバイト／ウェイ）／（３２バイト／キャッシュ・ライン））。したがって、本例では、セットの総数は１２８に等しい、すなわち、図のＭは１２７である。
【０００４】
この種のキャッシュ内に格納されたデータをアドレス指定するために、アドレスがどのセットまたはラインを参照しているかを示すＳＥＴすなわちインデクス部（Ｉｎｄｅｘ）３７、および４ウェイのどの中にそれがあるかを示すタグ部（ＴＡＧ）３６を含むアドレス３５が使用される。このようなアドレスはキャッシュ・ラインおよびキャッシュ・ウェイを識別する。ラインはセットおよび４ＴＡＧＲＡＭ２５内に格納されたＴＡＧとウェイを示す４キャッシュ１０の対応するセット内のＴＡＧとの比較および一致により識別される。実際上、２つ以上のデータ語をキャッシュ・ウェイ内のキャッシュ・ライン内に格納することができ、アドレスはさらに情報を含むことができる。
【０００５】
このように編成されたキャッシュ内に格納されたデータにアクセスする時は、プログラミング・モデルにより作り出された仮想アドレスを物理的アドレスに変換する必要がある。プログラムは仮想アドレスを容易に作り出すため、これにより手順は遅くなることがあるが、データは物理的アドレスに変換されるまでアクセスすることができない。
【０００６】
仮想アドレスを物理的アドレスに変換する既知の方法はトランスレーション・ルックアサイド・バッファすなわちＴＬＢを使用することである。図２は仮想アドレスが物理的アドレスに変換される間の既知のデータ・アクセス方法を示し、物理的アドレスは次にデータをアクセスするのに使用される。物理的アドレス３５はタグ部３６およびインデクス部３７を含む。インデクス部はアドレスがキャッシュ・ウェイ内のどのセットを参照するかを示すのに使用される。こうして、アドレス３５のインデクス部を使用して複数のキャッシュ・タグ・ディレクトリ４０内の対応するラインが選出される。次に、アドレス３５はタグ部３６が比較器６０内でキャッシュの４ウェイに対応する４つのキャッシュ・タグ・ディレクトリの各々に格納された４つのタグと比較される。比較により一致が得られると、それはデータ・アイテムを格納するキャッシュ・ウェイを示し、次に、マルチプレクサ７０を使用してこのデータ・アイテムをキャッシュ５０からアクセスすることができる。
【０００７】
これは仮想アドレスにより識別されたデータをアクセスすることができる１つの方法である。この手順の初期ステップはテーブル・ルックアサイド・バッファを使用する仮想アドレスの物理的アドレスへの変換である。これは高速ステップではないため、これを手順の最初のステップにするとクリティカル・パスは著しく遅くなる。これに代わるものが図３に示されている。このシステムは仮想インデクス／物理的タグ・キャッシュ・システムと呼ばれる。この例では、データ・アクセスはどのセット（またはライン）にタグが格納されるかを選出する仮想インデクスを使用して実施される。こうして、仮想アドレスが利用可能となるとすぐに、ＴＬＢ３０を使用する仮想アドレスの物理的アドレスへの変換と並列にこのステップを実施することができる。ＴＬＢ３０により物理的タグが作り出されると、それはインデクスによりキャッシュ・タグ・ディレクトリから選出された４つのタグと比較される。一致すると、それはキャッシュ５０からデータへアクセスするのに使用される。
【０００８】
これは図２に示すデータ・アクセスよりも高速である。しかしながら、タグは比較的長いデータ・ピースとなることがあり、たとえば、３２Ｋ４ウェイ・セット連想キャッシュ構造（６４バイト・キャッシュ・ライン・サイズからなる）を有するメモリ・システムは１９ビットのタグを有することがある（３２ビット・アドレスのプロセッサに対して）。こうして、比較段階は遅くなることがある。
【０００９】
さらに、このプロセスは多数のＲＡＭすなわち多数のキャッシュ・タグ・ディレクトリのアクセッシングを必要とし、また、手順中にキャッシュ・データ・アレイ（ＲＡＭ）がアクセスされるため消費電力が高い。
【００１０】
いつも多数のＲＡＭにアクセスしなければならない問題に取り組む１つの既知の方法はマイクロタグを使用することである。マイクロタグは最近のキャッシュ・アクセスのキャッシュ・ウェイに関する情報を格納するのに使用される。これらは命令キャッシュ・アクセスにおいて特に有用である。それは、命令がしばしばループ内で処理されると、同じ命令を多数回連続的にアクセスできるためである。キャッシュ・アクセスが行われていると、どのキャッシュ・ウェイ内にアクセスされた場所があるかが判り、したがって、最近のキャッシュ・アクセス上の情報をマイクロタグの形で格納すると多数のＲＡＭをイネーブルする必要がある回数を減らすことができる。しかしながら、キャッシュ・アクセス要求を前のアクセスと関連付けられるようにするには、キャッシュ・ラインの実質的に全アドレスをキャッシュ・ウェイの情報と共に格納する必要がある。アドレスはしばしば３２ビット長であるが、キャッシュ・ウェイの情報は識別されるウェイの数に応じて一般的には２，３ビットにすぎない。こうして、このソリューションは、特にいくつかの最近のキャッシュ・アクセスに対するキャッシュ・アクセス情報が格納される場合、格納に費用がかかる。
【課題を解決するための手段】
【００１１】
本発明の第１の側面はデータ処理装置を提供し、前記データ処理装置はデータを処理するための少なくとも１つのデータ・プロセッサと、前記データ・プロセッサにより処理される複数の値を格納するためのセット連想キャッシュであって、各値は前記値を格納するメモリ内の記憶場所のアドレスにより識別され、前記セット連想キャッシュは複数のキャッシュ・ウェイへ分割されるセット連想キャッシュと、複数の識別子を格納するための複数の記憶場所を含むデータ・ストアであって、各識別子が前記セット連想キャッシュからの対応する値が格納されるキャッシュ・ウェイを識別しかつ各々が関連する有効なインジケータを有し、前記複数の識別子は複数の値に対応し、前記複数の値は前記データ・ストアが前記メモリの領域内に格納された値に対する識別子を格納するように連続アドレスに格納された値であるデータ・ストアと、前記データ・ストア内の最も最近アクセスされた記憶場所を指すカレント・ポインタを格納するカレント・ポインタ・ストアと、キャッシュ・アクセス要求に応答してすぐ前のキャッシュ・アクセス要求に対する前記キャッシュ・アクセス要求のアドレスのオフセットを決定するオフセット決定回路であって、前記カレント・ポインタを前記オフセット量だけ更新するようにされているオフセット決定回路と、前記データ・ストアのサイズと前記オフセットから前記更新されたカレント・ポインタが前記領域内のアドレスを指しているかどうかを決定し、そうであれば前記データ・プロセッサは関連する有効なインジケータを有する場合に前記カレント・ポインタにより指示される前記格納された識別子から前記キャッシュ・ウェイを識別するようにされているデータ・ストア・ルックアップ回路と、を含んでいる。
【００１２】
本発明は、一般的に区別する２，３のキャッシュ・ウェイしかないため、特定の値が格納されるキャッシュ・ウェイを識別するのに必要な情報は小さいが、キャッシュ・ラインを識別するのに必要な情報は大きいため、どのエントリが特定のキャッシュ・ラインに関連するかを識別できるようにするためにキャッシュ・ウェイ情報を格納する各エントリに対して大量のロジックが必要であるという事実を認識する。また、本発明は、最も最近アクセスされたアドレスは再度アクセスされる可能性が高いため、この情報を格納する大概のデータ・ストアは典型的に最も最近アクセスされたアドレスに関連する情報を格納するが、多くの状況においてアクセスは特定期間中にメモリの特定領域に対して実施されることを認識する。こうして、キャッシュ・ウェイ情報を格納するデータ・ストアが最も最近アクセスされたキャッシュ・アドレスではなく最近アクセスされたキャッシュ・アドレスがあるメモリの特定領域に関連する値を格納するようにされると、キャッシュ・ライン・アドレスを使用して各場所を識別する必要なしにアクセスを実施することができる。特に、連続アドレスに関連する値をデータ・ストアに格納することにより、必要なエントリを前のアクセスに対するオフセットから簡単に決定することができる。次に、カレント・ポインタをそのオフセット量だけ移動させることができ、カレント・ポインタはデータ・ストアによりカバーされるアドレス領域から外へ出ない限り新しいエントリを指す。これは新しいエントリ場所を決定するのに２，３ビットしか必要としない利点を有し、そのためより多くのエントリ場所を提供することができ、同じロジック量に対してより大きいメモリ領域がデータ・ストアによりカバーされる。これにより、システムの効率が向上しマイクロタグ内にエントリが無い場合に必要なタグＲＡＭ（ＴＡＧ  ＲＡＭ）ルックアップ数が減少する。
【００１３】
本装置はいくつかの方法でカレント・ポインタが領域の外側となるように更新されるかどうかを決定することができるが、いくつかの実施例では、前記データ処理装置はさらに連続アドレスの前記領域内の予め定められた位置に対応する前記データ・ストア内のエントリを指す領域ロケータ・ポインタを格納する領域ロケータ・ポインタ・ストアを含んでおり、前記データ・ストア・ルックアップ回路は前記更新されたカレント・ポインタが前記領域内のアドレスを指しているかどうかを前記領域ロケータ・ポインタに関連する前記カレント・ポインタの値から決定するようにされている。
【００１４】
特定位置に対応するデータ・ストア内の特定のエントリを指す領域ロケータ・ポインタを使用して、本装置は単純に領域ロケーション・ポインタと比較するだけでカレント・ポインタがカバーされたアドレス領域内側の場所を指しているかどうかを決定することができる。
【００１５】
領域ロケーション・ポインタはデータ・ストア内の任意の記憶場所を指すことができるが、いくつかの実施例では、それは最低アドレスを有する値を指す。このような実施例では、それはボトム・ポインタと呼ばれカレント・ポインタが領域内か否かを知る簡単な方法である。データ・ストアがｎアドレス場所をカバーする場合、カレント・ポインタがボトム・ポインタ＋ｎ以上の値となると、それは領域外である。
【００１６】
いくつかの実施例では、前記データ・ストア・ルックアップ回路は前記更新されたカレント・ポインタおよび前記領域ロケータ・ポインタを比較し、前記比較に応答して前記更新されたカレント・ポインタが前記領域の外側かどうかを決定する。
【００１７】
更新されたカレント・ポインタが領域の外側へ移動しているかを決定する簡単な方法はそれを領域ロケータ・ポインタと比較することである。
【００１８】
いくつかの実施例では、前記データ処理装置はさらにデータ・ストア更新回路を含み、前記データ・ストア更新回路は前記更新されたカレント・ポインタが前記領域の外側であるという表示の前記データ・ストア・ルックアップ回路からの受信に応答して前記領域ロケータ・ポインタを前記オフセット量だけ更新し、前記領域が前記オフセット量だけ移動されてもはや前記領域内ではないアドレスに対応する前記記憶場所を無効にする。
【００１９】
データ・ストアによりカバーされた領域の外側にカレント・ポインタが移動していると装置が決定すれば、データ・ストアによりカバーされた領域が移動するように領域ロケータ・ポインタが移動される。これは現在アクセスされている領域をカバーすることを保証する。領域を移動させる時は、現在更新されている領域内ではないデータ・ストア内の任意の場所は関連情報を含まないため無効とする必要がある。
【００２０】
いくつかの実施例では、前記データ・ストア更新回路はさらに前記更新されたカレント・ポインタが前記領域の外側であるという表示の前記データ・ストア・ルックアップ回路からの受信に応答してタグＲＡＭルックアップを開始し前記キャッシュ・アクセス要求の前記値を格納するウェイを見つけ、また前記更新されたカレント・ポインタにより指示される前記データ・ストア内の前記エントリを前記ウェイを識別する識別子で更新する。
【００２１】
カレント・ポインタが前記領域の外側であるという表示の受信に続いて、タグＲＡＭルックアップはキャッシュ・アクセスの値を格納するウェイを見つける必要がある。このキャッシュ・ウェイが見つかっておれば、それを使用して必要なデータにアクセスすることができ、またデータ・ストア内のカレント・ポインタにより指示される位置内にそれを格納することができる。このように、データ・ストアは現在アクセスされている領域内のアドレスに関連する情報により更新される。
【００２２】
いくつかの実施例では、前記データ・ストアは環状バッファを含んでいる。
【００２３】
環状バッファをデータ・ストアとして使用することはデータ・ストア内の場所を指すポインタと共に使用する時に特に適切である。このように、カレント・ポインタおよび領域ロケータ・ポインタはデータ・ストア内の各場所を指すのに十分な数ビットを含むだけでよい。オフセット量が正値か負値かに依存してそれらをオフセット量だけ増分または減分することはそれらを環状バッファ周りに移動させて新しい場所を指すようにできることを意味する。カレント・ポインタが遠くへ移動しすぎると、付加ビットを使用してそれが環状バッファ周りを完全に回っていることを表示することができ、この情報はその値を領域ロケータ・ポインタと比較して現在カバーされているアドレス領域の外側か否かを決定するのに使用される。
【００２４】
いくつかの実施例では、前記値は前記データ・プロセッサにより処理されるデータ・アイテムを含み、他の実施例では、前記値は前記データ・プロセッサにより処理される命令を含む。
【００２５】
本発明の実施例はキャッシュ・アクセス要求が特定領域内の場所である状況に応用できる。こうして、しばしばシーケンシャルであるかまたは小さなループ内の命令アクセスは特に本発明の実施例から利益を得る。さらに、メモリ内の連続場所または近接場所にアクセスするあるデータ・アクセスも本発明の実施例に応用できる。
【００２６】
いくつかの実施例では、前記オフセット決定回路は前記キャッシュ・アクセス要求の仮想アドレスの予め定められたビットを前記すぐ前のキャッシュ・アクセス要求の仮想アドレスの前記予め定められたビットと比較する比較器を含んでいる。
【００２７】
オフセット決定回路はいくつかの方法でオフセットを決定することができるが、アクセス要求の仮想アドレスの予め定められたビットを比較してもこの情報しか提供できない。データ・ストアはサイズが制限されているためアドレスの２，３ビットしか比較する必要がなく、カレント・ポインタが必要なのはデータ・ストア内の相対位置だけである。カバーされた領域の外側を移動する時に実際のデータを見つけるのに使用するために完全な仮想アドレスは重要であるが、データ・ストアのアクセッシングに関する限り２，３ビットを考慮するだけでよい。
【００２８】
いくつかの実施例では、前記データ処理装置はフェッチされる後の命令が連続するアドレス内にあることの検出に応答してシーケンシャル・インジケータを出力するプリフェッチ・ユニットを含み、前記オフセット決定回路は前記シーケンシャル・インジケータに応答して前記カレント・ポインタを増分する。
【００２９】
命令のフェッチング等の多くの状況において、次のキャッシュ・アクセス要求は後のアドレスに対するものである。この情報はプリフェッチ・ユニットにより知られており、カレント・ポインタは作られる仮想アドレスのビットの比較よりもこれの検出に応答して単純に増分できるようにこの情報が出力されることが有利である。
【００３０】
いくつかの実施例では、前記データ・ストアのアクセッシングおよび無効インジケータの検出に応答して、前記データ処理装置はタグＲＡＭルックアップを実施することにより前記記憶場所および前記有効ビットを更新する。
【００３１】
データ・ストアがこの特定キャッシュ・アクセス要求のキャッシュ・ウェイに関する情報を格納しない場合には、データ・ストア・エントリに関連する無効インジケータが検出され、それに応答してタグ・ルックアップを実施しキャッシュ・ウェイを決定しこの値でデータ・ストアを更新することができる。
【００３２】
本発明のさらなる側面はセット連想キャッシュへのキャッシュ・アクセス要求がアクセスするのは複数のキャッシュ・ウェイのいずれであるかを決定する方法を提供し、キャッシュ・アクセス要求に応答してすぐ前のキャッシュ・アクセス要求に対する前記キャッシュ・アクセス要求のアドレスのオフセットを決定するステップと、データ・ストア内の最も最近アクセスされた記憶場所を指すカレント・ポインタを前記オフセット量だけ更新するステップであって、前記データ・ストアは複数の識別子を格納する複数の記憶場所を含み、各識別子が前記セット連想キャッシュからの対応する値が格納されるキャッシュ・ウェイを識別しかつ各々が関連する有効インジケータを有し、前記複数の識別子は複数の値に対応し、前記複数の値は前記データ・ストアが前記メモリの領域内に格納された値に対する識別子を格納するように連続アドレスに格納される値であるステップと、前記データ・ストアのサイズと前記オフセット量から前記更新されたカレント・ポインタが前記領域内のアドレスを指しているかどうかを決定するステップと、そうであれば関連する有効なインジケータを有する場合に前記カレント・ポインタにより指示される前記格納された識別子から前記キャッシュ・ウェイを識別するステップと、を含んでいる。
【００３３】
本発明の前記および他の目的、特徴および利点は添付図と共に例示する実施例の下記の詳細な説明を読めば明らかである。
【図面の簡単な説明】
【００３４】
【図１】従来技術に従った４ウェイ・セット連想キャッシュを例示する略図である。
【図２】従来技術に従った物理的インデクス／物理的タグ・キャッシュ・システムにおけるデータ・アクセスを例示する略図である。
【図３】従来技術に従った仮想インデクス／物理的タグ・キャッシュ・システムを示す図である。
【図４】本発明の実施例に従ったマイクロタグ・ストアおよびそれがカバーするメモリの対応する部分を示す図である。
【図５】本発明の実施例に従ったデータ処理装置を示す図である。
【図６】本発明の実施例に従ったオフセット決定回路およびルックアップ回路を示す図である。
【図７】本発明の実施例に従ったマイクロタグを示す略図である。
【図８】本発明の実施例に従ったオフセット決定回路、データ・ストア・ルックアップ回路および更新回路を示す略図である。
【図９】本発明の実施例に従った方法のステップを例示するフロー図である。
【発明を実施するための形態】
【００３５】
図４はメモリ１１０の領域に対するキャッシュ・ウェイを示す値を格納するマイクロタグ１００を示す。マイクロタグ１００はメモリ１１０内のｎ連続アドレスに対するキャッシュ・ウェイを示すｎ値を格納するｎエントリを有し、マイクロタグ１００内の２つのエントリを指す２つの関連するポインタを含んでいる。一方のポインタはマイクロタグ１００によりカバーされる最低アドレスを指すボトム・ポインタであり、他方は処理されるカレント・キャッシュ・アクセス要求に対応する場所を指すカレント・ポインタである。命令キャッシュの場合、これはプログラム・カウンタと同じアドレスを指す。
【００３６】
図５は本発明の実施例に従ったデータ処理装置１２０を示す。データ処理装置１２０はプリフェッチ・ユニット１３２、命令キュー１３３、デコード部１３４および実行部１３５を有するプロセッサ１３０を含んでいる。プリフェッチ・ユニット１３２がそこから命令をフェッチする命令キャッシュ１４０および命令キャッシュが通信するメモリ１１０（図示せず）がある。
【００３７】
キャッシュ・アクセス要求がプリフェッチ・ユニット１３２から出力され、このキャッシュ・アクセス要求がシーケンシャル・アクセス要求であれば、本発明の実施例において、シーケンシャル・インジケータＳＩもプリフェッチ・ユニット１３２により出力される。そうでなければ、それは単純に出力されるアクセス要求である。ＳＩが出力されなければオフセット決定回路内の比較器はそれらの仮想アドレスのある関連ビットを比較して前のアクセス要求に対するこのアクセス要求のオフセットを決定し、それから次にオフセット・ストア１８２内に格納するオフセット（ｏｆｆｓｅｔ）を決定する。他の実施例では、プリフェッチ・ユニットから出力されるＳＩに対する規定は無いかも知れず、このような実施例では、オフセット決定回路がシーケンシャル・アクセス要求を含む全てのキャッシュ・アクセス要求に対するオフセットを決定する。次に、このオフセットはカレント・ポインタを更新するのに使用される。シーケンシャル・インジケータＳＩが出力されると、カレント・ポインタは単純に増分される。次に、ルックアップ回路１９０はデータ・ストアのサイズおよびボトム・ポインタの位置から更新されたカレント・ポインタはマイクロタグ１００により現在カバーされている領域内であるかどうかを決定する。そうであると決定すると、ルックアップ回路は更新されたカレント・ポインタにより指示されたマイクロタグ１００からの値にアクセスし、それが有効とマークされるとキャッシュ・ルックアップ内で活性化されるウェイを選択する。次に、マルチプレクサ１９７がＡのキャッシュの選択されたウェイから格納された値を出力し、これはプリフェッチ・ユニットにより検索されてキューに送られる。
【００３８】
それが有効とマークされると、更新回路１９５はタグＲＡＭ（ｔａｇ  ＲＡＭ）１９８内でタグ・ルックアップを開始して従来の方法でタグからどのウェイにアクセス要求が格納されるかを決定し、適切なウェイがタグ・ルックアップから活性化される。次に、マルチプレクサ１９７がＡのキャッシュの選択されたウェイから格納された値を出力し、これはプリフェッチ・ユニットにより検索されてキューに送られる。次に、このアドレスに対応するマイクロタグ記憶場所が更新回路を使用してこの値で更新され有効とマークされる。
【００３９】
カレント・ポインタはマイクロタグ１００によりカバーされる領域の外側であるとルックアップ回路１９０が決定する場合、更新回路１９５はボトム・ポインタをオフセット量だけ増分することによりカバーされた領域がカレント・ポインタを含むようにマイクロタグ１００を更新する。決定されるオフセットはポインタをいずれの方向にも移動できるように符号の付いた値であることに注目しなければならない。次にどのようにマイクロタグ１００が更新されボトム・ポインタが移動されるかの詳細については後の図面について説明する。
【００４０】
キャッシュ１４０もメモリ１００に接続され、キャッシュ・アクセス要求に応答してキャッシュ内にミスがあれば、キャッシュ内のラインは適切なアドレスへのメモリ・アクセスにより更新することができる。
【００４１】
図６はオフセット決定回路１８０を詳細に示す。この回路内でキャッシュ・アクセス要求および場合によりシーケンシャル・インジケータが受信される。シーケンシャル・インジケータが受信されなければ、ここでは５から７ビットである、カレント・アクセス要求の仮想アドレスの適切なビットが前のアクセス要求と比較され、この比較からオフセット値が作り出されてカレント・ポインタはこの量だけ更新される。シーケンシャル・インジケータが受信されれば、オフセットは単純に増分され比較は行われない。次に、更新されたカレント・ポインタの値は更新回路１９０によりボトム・ポインタおよびデータ・ストアのサイズと比較されて、それが領域内であるか決定される。マイクロタグによりカバーされる領域内でなければ、更新回路１９０はボトム・ポインタをオフセットだけ移動させ、現在移動した領域の外側である記憶場所アドレスを無効とする。ボトム・ポインタはカレント・ポインタが関心ある領域内となるように単純に更新するだけでよいことに注目しなければならない。これはオフセットによりそれを更新することにより働く。あるいは、カレント・ポインタと同じ値となるようにまたは異なる方法で更新することができる。
【００４２】
図７はこのような更新および無効化がどのように行われるかをより詳細に示す。図７ａにはマイクロタグ１００がエントリを格納するための場所０，１，２，３，４，５，６，７を有する環状バッファとして示されている。現在、ボトム・ポインタはエントリ・ナンバー２を指している。領域によりカバーされたシーケンシャル・アドレスが環状バッファの記憶場所に対応するものとして示されるようにメモリ１１０の対応する部分が示される。新しいキャッシュ・アクセス要求（ｎ）が受信され、それは前の（ｎ−１）値に比べて５のオフセット（ｏｆｆｓｅｔ）を有する。カレント・ポインタＣｐｎ−１を５だけ更新することは、それが環状バッファ内のボトム・ポインタＢＰｎ−１を通過してメモリ１１０内のカバーされた領域から出て行くことを伴う。図７ｂは新しい要求に対して更新されたマイクロタグ１００を示す。ＣＰｎはマイクロタグ１００である環状バッファ内のエントリ３のポイントで終わる。データ・ストア・ルックアップ回路はオフセット値、ボトム・ポインタの位置およびマイクロタグのサイズからカレント・ポインタが現在領域の外側であると決定し、次に、更新回路はボトム・ポインタが現在マイクロタグ１００である環状バッファ内の記憶場所７を指すようにボトム・ポインタをオフセット量だけ更新する。次に、更新回路はもはや有効値を格納しない環状データ・ストア内のこれらの位置を無効とする。これらは前にカバーされていた領域の現在外側の位置であり、前のボトム・ポインタ（ＢＰｎ−１）＋ｎと前のカレント・ポインタ（ＣＰｎ−１）との間にある位置である。次に、更新回路はタグ・ルックアップを実施して現在要求されている値が格納されるウェイを決定する。結果は要求されたウェイを活性化するのに使用され、現在ポインタＣＰｎにより指示されるマイクロタグ１００内の場所を更新するのにも使用される。図から分かるように、記憶場所２，３，４，５および６はもはやマイクロタグ１００によりカバーされる領域内に値を格納しないため無効とされる。記憶場所３は無効化に続いてタグＲＡＭルックアップの結果で更新されるが、次に有効（ｖａｌｉｄ）としてマークされる。記憶場所１，０および７は有効のままであり、このように無効とされることはない。どの場所が領域の外側であるかを計算するのに使用されるアルゴリズムは、全ての場所が領域の外側となるような長い距離を領域が移動してもあるいはいくつかの場所しか領域の外側とならないような短い距離を移動しても同じであることに注目しなければならない。
【００４３】
図８はオフセット決定回路１８０および更新回路１９５を詳細に示す。それは有効なマイクロタグ・エントリが見つからない時にルックアップが実施されるＴＡＧＲＡＭ１９８も示している。図から分かるように、キャッシュ・アクセス要求が受信されそれからオフセット（ｏｆｆｓｅｔ）が決定される。次に、このオフセットはデータ・ストア・サイズおよびボトム・ポインタ場所の知識と共にカレント・ポインタがマイクロタグ内であるか否かを決定するのに使用される。そうであれば、それは更新されそれが有効に格納されればウェイがマイクロタグから読みだされる。有効に格納されなければ、ウェイ選出はタグＲＡＭルックアップから決定されマイクロタグ１００が更新される。カレント・ポインタが領域の外側を移動していると、ボトム・ポインタが更新されマイクロタグはそれが次にカバーする領域に対応するように更新される。
【００４４】
図９は本発明の実施例に従った方法のステップを例示するフロー図である。第１のステップにおいて、キャッシュ・アクセス要求が受信される。前のキャッシュ・アクセス要求からのオフセットが決定され、受信されたキャッシュ・アクセス要求およびカレント・ポインタがオフセットにより更新される。次に、カレント・ポインタはマイクロタグによりカバーされたアドレス領域内であるか否か決定される。そうであれば、カレント・ポインタにより指示されたマイクロタグ・エントリが読み出され、それが有効であればその値により指示されるキャッシュ・ウェイが選択されてキャッシュ・ライン内の値が読みだされる。有効でなければ、ＴＡＧＲＡＭルックアップが実施されてキャッシュ・ウェイを決定し、次に、このキャッシュ・ウェイが選択されてマイクロタグ・エントリが更新される。
【００４５】
カレント・ポインタがアドレス範囲内ではないと決定されと、ボトム・ポインタがオフセットにより更新される。これに続いて、前のボトム・ポインタ（ＢＰｎ−１）＋ｎと前のカレント・ポインタ（ＣＰｎ−１）間のマイクロタグ内の全エントリが無効とされる。次に、ＴＡＧＲＡＭルックアップが実施されてどのキャッシュ・ウェイにアクセスするか決定される。次に、このキャッシュ・ウェイが選択され対応するマイクロタグ・エントリがこの値で更新され有効としてマークされる。
【００４６】
添付図を参照して本発明の実施例を詳細に説明してきたが、本発明はこれらの厳密な実施例に限定されるものではなく、当業者ならば添付特許請求の範囲に明記された本発明の範囲を逸脱することなくさまざまな変更および修正を行うことができる。
【符号の説明】
【００４７】
１０  ４ウェイ・セット連想キャッシュ
１１，１２，１３，１４  ウェイ
２０，２２  キャッシュ・ライン
２５，１９８  ＴＡＧＲＡＭ
３０  ＴＬＢ
３５  アドレス
３６  ＴＡＧ部
３７  インデクス部
４０  キャッシュ・タグ・ディレクトリ
５０  キャッシュ
６０  比較器
７０，１９７  マルチプレクサ
１００  マイクロタグ
１１０  メモリ
１２０  データ処理装置
１３０  プロセッサ
１３２  プリフェッチ・ユニット
１３３  命令キュー
１３４  デコード部
１３５  実行部
１４０  命令キャッシュ
１８０  オフセット決定回路
１８２  オフセット・ストア
１９０  ルックアップ回路
１９５  更新回路
【図１】
0005394780.tif 000002
【図２】
0005394780.tif 000003
【図３】
0005394780.tif 000004
【図４】
0005394780.tif 000005
【図５】
0005394780.tif 000006
【図６】
0005394780.tif 000007
【図７】
0005394780.tif 000008
【図８】
0005394780.tif 000009
【図９】
0005394780.tif 000010