(57)【要約】データ処理装置は相互に異なるアクセス待ち時間を持つ記憶位置を含むメインメモリを有する。メインメモリからの情報はキャッシュメモリ内にキャッシュされる。キャッシュの置換えが必要とされる場合におけるキャッシュ置換え位置の選択は、そのための置換え可能なキャッシュ位置が使用中であるメインメモリ位置のアクセス待ち時間における差異に依存する。置換え可能なキャッシュメモリ位置にキャッシュされたメインメモリ位置のアクセス待ち時間が他の置換え可能なキャッシュメモリ位置にキャッシュされた他のメインメモリ位置のアクセス待ち時間よりも比較的小さい場合には、メインメモリ位置に関するキャッシュされたデータは、その待ち時間が小さいので、他のメインメモリ位置に関するデータよりも優先的に置換えられる。
2004503010.tif 000002
【特許請求の範囲】
【請求項１】
相互に異なるアクセス待ち時間を持つ記憶位置を含むメインメモリを有するプロセッサにおいてキャッシュメモリを管理する方法であって、置換え可能なキャッシュ位置が用いられるために前記メインメモリ位置の前記アクセス待ち時間における差異にキャッシュ置換え位置の選択が依存し、
前記置換え可能なキャッシュメモリ位置にキャッシュされたメインメモリ位置のアクセス待ち時間が他の置換え可能キャッシュメモリ位置にキャッシュされた他のメインメモリ位置のアクセス待ち時間より比較的小さいかどうかに従ってプリファランスが置換え可能なキャッシュメモリ位置の置換えに与えられる方法。
【請求項２】
少なくとも１つのキャッシュミスに関して、事前選定されていないキャッシュメモリ位置にキャッシュされたメインメモリ位置よりも小さいアクセス待ち時間を持つメインメモリ位置をキャッシュする置換え可能なキャッシュメモリ位置を事前選定するステップを前記選択が含み、前記置換え可能なキャッシュメモリ位置のアクセス待ち時間の表示に依存して前記事前選定ステップが実行され、置換えのためのキャッシュメモリ位置が前記事前選定済みキャッシュメモリ位置から選定される請求項１に記載の方法。
【請求項３】
アクセス待ち時間に依存しない前記キャッシュ置換え位置の選択とアクセス待ち時間に依存する前記キャッシュ置換え位置の前記選択をインタリーブするステップを含む請求項２に記載の方法。
【請求項４】
前記置換え可能なキャッシュメモリ位置のそれぞれの１つにキャッシュされる前記メインメモリ位置のアクセス待ち時間に依存する前記置換え可能なキャッシュメモリ位置のそれぞれの１つにプリファランス値を割り当てるステップと、いずれの前記置換え可能なキャッシュメモリ位置が最も好ましいプリファランス値を持つかの決定により前記キャッシュ置換え位置を選択するステップとを有する請求項１に記載の方法。
【請求項５】
前記置換え可能なキャッシュメモリ位置が最高頻度でアクセスされることなく、前記置換え可能なキャッシュメモリ位置を使用する前記メインメモリ位置の前記アクセス待ち時間が更に長くなるにつれて重み付けが強化されるサイクル数に前記プリファランス値が依存する請求項４に記載の方法。
【請求項６】
データ処理装置であって、
プロセッサと、
相互に異なるアクセス待ち時間を持つ位置をアドレスするアドレススペースを持つメインメモリと、
前記メインメモリと前記プロセッサとの間のキャッシュメモリと、
前記キャッシュメモリ内の置換え可能なキャッシュメモリ位置の中からキャッシュ置換え位置を選択するように配置構成されたキャッシュ管理ユニットとを有し、前記置換え可能なキャッシュメモリ位置にキャッシュされたメインメモリ位置のアクセス待ち時間が他の置換え可能なキャッシュメモリ位置にキャッシュされた他のメインメモリ位置のアクセス待ち時間よりも比較的小さいかどうかに従って、置換え可能なキャッシュメモリ位置の置き換えに与えられた前記キャッシュ内にキャッシュされた前記メインメモリ位置の前記相対アクセス待ち時間に依存する前記キャッシュ置換え位置を前記キャッシュ管理ユニットが選択する
装置。
【請求項７】
前記キャッシュ管理ユニットが、少なくとも１つのキャッシュミスに関して、事前選定されないキャッシュメモリ位置にキャッシュされたメインメモリ位置よりも小さいアクセス待ち時間を有するメインメモリ位置をキャッシュする置換え可能なキャッシュメモリ位置を事前選択するように配置構成され、前記キャッシュ管理ユニットが置換え可能な前記キャッシュメモリ位置の表示に依存して前記事前選定を実行し、前記キャッシュ管理ユニットが事前選定された前記キャッシュメモリ位置の中から置換えのためのキャッシュメモリ位置を選択する請求項６に記載のデータ処理装置。
【請求項８】
前記キャッシュ管理ユニットが、アクセス待ち時間から独立した前記キャッシュ置換え位置の選択とアクセス待ち時間に依存する前記キャッシュ置換え位置の前記選択とをインタリーブするように配置構成される請求項７に記載のデータ処理装置。
【請求項９】
前記キャッシュ管理ユニットが、置換え可能なキャッシュメモリ位置のそれぞれの１つにキャッシュされた前記メインメモリの前記アクセス待ち時間に依存する前記置換え可能なキャッシュメモリ位置のそれぞれ１つにプリファランス値を割り当て、かつ、いずれの前記置換え可能なキャッシュメモリ位置が最も好ましいプリファランス値を有するかの決定により前記キャッシュ置換え位置を選択するように配置構成される請求項６に記載のデータ処理装置。
【請求項１０】
置換え可能なキャッシュメモリ位置が最高頻度においてアクセスされることなく、前記置換え可能なキャッシュメモリ位置を使用する前記メインメモリ位置の前記アクセス待ち時間が更に長くなるにつれて重み付けが強化されるサイクル数に依存する前記プリファランス値を計算するように前記キャッシュ管理ユニットが配置構成される請求項６に記載のデータ処理装置。
【請求項１１】
１つの第１と第２集積回路を有し、前記第１集積回路が前記プロセッサと前記キャッシュメモリと前記メインメモリの第１部分とを含み、前記第１部分が比較的速いアクセス待ち時間を持つメインメモリ位置を含み、前記第２集積回路が比較的遅いアクセス待ち時間を持つ前記メインメモリの第２部分を含む請求項６に記載のデータ処理装置。
【請求項１２】
請求項１１に記載の装置における第１集積回路として使用するために配置構成された集積回路。
【発明の詳細な説明】
【０００１】
本発明はキャッシュメモリを有するデータ処理装置、この種装置で使用する集積回路、及び、この種装置を操作する方法に関する。
【０００２】
キャッシュメモリは例えば米国特許第５，７３７，７５２号に記載済みの技術においてよく知られている。これらのキャッシュメモリはプロセッサの作動速度とメインメモリの作動速度との間の間隙を橋絡するために役立つ。作動速度はキャッシュメモリの方がメインメモリよりも高い。プロセッサがメインメモリからのデータを使用する（または、使用することが予期される）ときには、当該データのコピーがキャッシュメモリ内に記憶される。従って、プロセッサが当該データを必要とするときには、当該データはメインメモリからフェッチ可能であるよりも更に迅速にキャッシュメモリからフェッチ可能である。
【０００３】
通常、キャッシュメモリはマイクロプロセッサと大型オフチップＤＲＡＭメモリとの間で用いられている。キャッシュは、当該マイクロプロセッサと同じチップに組み込まれたＳＲＡＭであることが好ましい。現行技術は、速度がＤＲＡＭよりも数オーダ大きいプロセッサ及びＳＲＡＭの製造を可能にする。キャッシュメモリはオンチップメインメモリ用、即ち、プロセッサとメインメモリとキャッシュが全て同一集積回路内に集積されている集積回路用にも使用されている。この場合、例えば、オンチップメインメモリは速度を最大限化するよりもケイ素部位（エリア）を減少させるように最適化されるので、メインメモリも低速である。この場合にも、キャッシュはプロセッサの作動速度との間に結果的に生じる間隙を橋絡する速い方のメモリである。キャッシュメモリは処理装置にも使用可能であり、この場合には、メインメモリの第１部分はプロセッサ及びキャッシュメモリと共にオンチップであり（チップ内に所在し）、メインメモリの第２部分（これは、依然として第１の部分と同じメモリスペース内に所在する）はオフチップである（チップ外に所在する）。この場合、キャッシュメモリは作動速度間における差間隙、即ち、プロセッサとメインメモリの第１部分との間の間隙およびプロセッサとメインメモリの第２部分との間の間隙を橋絡するために用いられる。ここに、通常、後者間隙の方が前者間隙よりも大きい。
【０００４】
一般的に、キャッシュメモリはメインメモリよりも遥かに小さい。メインメモリ位置からのデータがキャッシュメモリ内に記憶されるべきであり、自由なキャッシュメモリ位置が利用可能でないときには、他のメインメモリ位置用としてキャッシュ内に所在するデータは重ね書きされなければならないはずである。キャッシュ管理ユニットは、いずれのキャッシュ位置が用いられるかを選択する。選択はキャッシュ置換え戦略に依存する。１つのよく知られた戦略は、プロセッサによる使用頻度が最低であったキャッシュ位置を選定する最低使用頻度（ＬＲＵ）戦略である。米国特許第５，７３７，７５２号は、この置換えメカニズム又は他のユーザ選択可能な置換えメカニズムを使用するキャッシュについて記述している。この特許は、ユーザ選択可能な置換えメカニズムの一例としてランダム選択に言及している。
【０００５】
他の多くの目的に中で、本発明の一目的は処理装置および改良されたキャッシュ置換え戦略を用いて処理装置を操作する方法を提供することにある。
【０００６】
本発明に従った方法は請求項１に記載されている。本発明によれば、キャッシュ置換え戦略は、それに関するデータがキャッシュ内に所在するメインメモリ位置の待ち時間に依存して実施される。新規データを記憶するための空間をキャッシュ内に作ることが必要なときには、メモリ管理ユニットは、それに関するデータがキャッシュ内に所在する他のメインメモリ位置よりも更に短いアクセス待ち時間を持つメインメモリ位置に関するデータによって占有されている位置を選定することが好ましい。従って、メインメモリのアクセス待ち時間における差異は、置換えられたデータがメインメモリから再びフェッチされることが必要であれば、失われる時間は少なくてすむことが期待されるという点で利用される。一例として、メインメモリ位置の一部はオンチップＤＲＡＭ内に所在し、かつメインメモリ位置の一部はオフチップＤＲＡＭ内に所在するので、異なる記憶位置のアクセス待ち時間は異なることがあり得る。
【０００７】
図１は集積回路１０および外部メモリ１２を有する処理回路を示す。集積回路は、プロセッサ処理装置１００、キャッシュ管理単位体ユニット１０２、キャッシュメモリ１０４、ローカルメモリ１０６、及び、バス１０８、１０９を含む。バスはアドレスバス１０９およびデータバス１０８を含む。キャッシュ管理ユニット１０２はキャッシュメモリ１０４に結合される。プロセッサ１００はキャッシュメモリ１０４を介してバス１０８、１０９に接続される。ローカルメモリ１０４はバス１０８、１０９に接続される。バスは集積回路１０の外部インタフェース１１０に接続される。バス１０８、１０９は集積回路１０内の部分および集積回路外の部分を有する。外部メモリ１２は集積回路外のバス１０８、１０９の部分へ接続される。
【０００８】
ローカルメモリ１０６および外部メモリ１２は、プロセッサ１００、例えばメモリアドレスの第１レンジに関するメモリセルを提供するローカルメモリ１０６、及び、アドレスの第２レンジに関するメモリセルを提供する外部メモリ１２にとって可視である概念メインメモリの同一アドレススペースの部分である。
【０００９】
作動に際して、プロセッサ１００はプログラムを実行する。プログラム実行の経過に際して、プロセッサ１０は、例えば命令をロードし、及び／又は、メインメモリ１２、１０６からのデータをロードするためにロード命令を実行するようにメインメモリ１２、１０６をアドレスする。プロセッサ１００がミインメモリ１２、１０６をアドレスするとき、プロセッサ１００は当該アドレスをキャッシュ管理ユニット１０２にパスする。キャッシュ管理ユニット１０２はアドレスに関するデータがキャッシュメモリ１０４において利用可能であるかどうかをテストし、可能であれば、当該データをプロセッサ１００に返す。アドレスに関するデータがキャッシュメモリ１０４において利用可能でないならば、キャッシュ管理ユニット１０２は当該アドレスをバス１０８、１０９にパスし、メインメモリ１２、１０６をアドレスする。当該アドレスがローカルメモリ１０６または外部メモリ１２をアドレスするかどうかによって、外部メモリ１２およびローカルメモリ１０６の適切な１つは当該アドレスに関するデータをバス１０８、１０９への戻す。キャッシュ管理ユニット１０２は当該データを受け取り、それをプロセッサ１０に返す。
【００１０】
ローカルメモリ１０６または外部メモリ１２からデータが戻される以前に必要とされる時間はアクセス待ち時間（レイテンシ）と呼ばれる。アクセス待ち時間は当該メモリの速度、及び、当該メモリへアクセスリクエストを伝送し、かつ結果を戻すために必要な時間の関数である。一般的に、集積回路とその外部との間でのアドレス及びデータ交換必要時間は集積回路内における同様の交換必要時間より大きいので、外部メモリ１２のアクセス待ち時間はローカルメモリ１０６のアクセス待ち時間より大きいはずである。図１の回路はアクセス待ち時間差の１つの原因を示すが、勿論、例えば集積回路の両内部または両外部において速度が異なる同じでないタイプのメモリの使用などのような他の原因もあり得る。
【００１１】
また、キャッシュ管理ユニット１０２はデータのコピーを当該データがそれから読み取られたメインメモリアドレスを識別する情報と共にキャッシュメモリ１０４に書き込む。その結果、同じメインメモリ位置（ロケーション）へのその次のアクセスは、メインメモリへのアクセスが必要とされる時間よりも短い時間でキャッシュメモリ１０４からサポートされることが可能である。
【００１２】
キャッシュ管理ユニット１０２は、データを書き込もうとするキャッシュメモリ１０４内の記憶位置を選択しなければならない。本発明はキャッシュ管理ユニット１０２がこの機能を実施する方法に関係する。キャッシュメモリ１０４は、例えば完全な連想メモリ又はセットアソシエィティブメモリとして組織される。これは、データのコピーが幾つかの代替位置の１つに書き込み可能であることを意味する。キャッシュ管理ユニット１０２は、これらの代替位置において当該データを記憶するためのキャッシュメモリ１０４内における記憶位置を選択しなければならない。この選択に用いられる規則はキャッシュ置換え戦略と呼ばれる。キャッシュ管理ユニット１０２によって用いられるキャッシュ置換え戦略はプログラムの実行速度に影響する。通常、新規なメインメモリアドレスに関するデータを記憶するために選定されたキャッシュメモリ位置は他のメインメモリアドレスに関するデータを既に含んでいるはずである。これは、新しい新規メインメモリアドレスに関するデータを記憶するためのキャッシュメモリ位置が選定される場合には、他の当該メインメモリアドレスに関するデータが犠牲にされることを意味する。他の当該メインメモリアドレスのデータへのその次のアクセスはキャッシュミスに帰着し、メインメモリがアクセスされなければならないはずである。
【００１３】
周知のキャッシュ置換え戦略は「最低使用頻度」（ＬＲＵ）戦略である。ＬＲＵ戦略を用いるキャッシュ管理ユニット１０２は、新規記憶位置に関するデータを記憶するために使用できるキャッシュメモリ１０４内の記憶位置から、最低アクセス頻度であったキャッシュメモリ１０４内の当該記憶位置を選定する。
【００１４】
本発明に従ったデータ処理装置で用いられるキャッシュ置換え戦略では、新規メインメモリ位置に関するデータを記憶しようとするキャッシュメモリ１０４内の記憶位置を選択するために、それに関するデータが一次判定基準としてキャッシュメモリ内に記憶されているデータメインメモリ位置の待ち時間が用いられる。新規メインメモリ位置に関するデータがキャッシュメモリ１０４における幾つかの代替記憶位置に記憶可能であり、これら全ての代替位置がメインメモリ位置に関するデータを記憶する場合には、その待ち時間が他のあらゆる代替位置の待ち時間より大きくないメインメモリ位置に関するデータを記憶する位置が優先性を以て選定される。従って、置き換えられたデータが再び必要とされるので、当該位置におけるデータの置換えの結果としてその次のキャッシュミスを生じる場合には、メインメモリからのフェッチングに要する時間は、比較的大きいアクセス待ち時間を持つ位置に関して同じことが起きた場合よりも所要時間は小さいはずである。
【００１５】
キャッシュメモリ１０４内の代替記憶位置に記憶されるデータに関する複数のメインメモリ位置が同じ待ち時間を持ち、しかも、更に小さい待ち時間を持つメインメモリ位置に関するデータを記憶する代替位置が無い場合には、前者の代替位置の中から選択するために、例えばＬＲＵなどの他の戦略が使用可能である。
【００１６】
キャッシュ管理ユニット１０２は次のように作動する。置換え用のキャッシュメモリ位置が選定される必要があるときには、置換え優先順位の少なくとも一部分が選択対象とされる全ての代替位置の間で決定される。（位置（ロケーション）という用語は、キャッシュ置換え単位が個々にアドレス可能な記憶位置であるか、或いは、記憶位置のブロック（塊）であるかを表すために用いられる）。キャッシュメモリ１０４が完全な連想キャッシュメモリである場合には、代替位置は全てキャッシュ位置である。キャッシュメモリがセットアソシエィティブである場合には、代替位置はメインメモリロ位置によってアドレスされたセット（集合）から選択される位置である。少なくとも幾らかの置換えオペレーションに関して、キャッシュ管理ユニットは、代替位置に記憶されるデータに関するメインメモリ位置のアクセス待ち時間から置換え優先順位を決定する。一実施形態において、キャッシュ管理ユニット１０２は、優先順位を決定する際に使用するために、各キャッシュ位置に関するアクセス待ち時間を表すデータを記憶する。他の一実施形態において、キャッシュ管理ユニット１０２はキャッシュメモリ１０４内の代替位置に記憶されたデータのアドレスタグからアクセス待ち時間を決定する。例えば、或る待ち時間はメインメモリ１０６のローカル部分によってサポートされるアドレスレンジ内におけるメモリアドレスに関する待ち時間であるものと仮定し、別の待ち時間はメインメモリ１２の外部部分によってサポートされるアドレスレンジ内におけるメモリアドレスに関する待ち時間であるものと仮定しても差し支えない。
【００１７】
一実施形態において、キャッシュ管理ユニット１０２は、他のあらゆる代替位置に関するアクセス待ち時間より大きくないアクセス待ち時間を持つメインメモリアドレスに関するデータを記憶する代替位置を事前選択する。これは、キャッシュ管理ユニット１０２によって実行されたマイクロプログラムによるか、或いは、メモリ待ち時間またはそれらの表現体を比較するための並列演算ハードウェアによって実現可能である。続いて、キャッシュ管理ユニットは事前選定された位置の中から最終位置を選択する。ここに、最終位置は事前選定された他のあらゆる位置よりも更に頻繁にはアクセスされていない位置である。後者の選択は通常のＬＲＵ技法を用いて実施可能である。最終位置は新規メインメモリ位置に関するデータを記憶するために用いられる。
【００１８】
図２は、セット・アソシエィティブキャッシングスキーム（計画）用キャッシュメモリ２０及びキャッシュ管理ユニット２２の一実施形態の例を示す。キャッシュメモリ２０は、異なるセット集合からのデータに関してデータメモリ２００ａ−ｄを含む（以降、「データ」という用語はデータ及び命令の両方に関して総称的に用いられる）。更に、キャッシュメモリは種々異なる集合によって構成されるデータのタグに関するタグメモリ２０２ａから２０２ｄを含む。キャッシュメモリ２０はメモリアドレスに関する入力「Ａ」を有する。メモリアドレスの一部分はデータメモリ２０ａから２０ｄ及びタグメモリ２０２ａから２０２ｄのアドレス入力に供給される（説明図を簡素化するために、アドレスのこの部分はメモリ２００ａから２００ｄ、２０２ａから２０２ｄ、２２２、２２４の間の直列接続部として示される）。この直列接続は、単に、好ましい実施形態における並列メモリに等価であるメモリ２００ａ−ｄ、２０２ａ−ｄ、２２２、２２４、及び、その次のメモリ２００ａ−ｄ、２０２ａ−ｄ、２２２、２２４まで通過するアドレスの使用に関する接続を表すに過ぎない。また、キャッシュメモリ２０はタグコンパレータ２０４及びデータセレクタ２０６を含む。タグメモリ２０２の出力は、タグ用に使用されるメモリアドレスの一部分を受け取るためにアドレス入力Ａに結合された入力を有するタグコンパレータ２０４に結合される。タグコンパレータ２０４は、データメモリ２００ａ−ｄの出力に結合された入力を有するデータセレクタ２０６の制御入力に結合された出力を有する。
【００１９】
キャッシュ管理ユニット２２は制御ユニット２２０、待ち時間識別子メモリ２２２、使用順序メモリ２２４、使用順序更新ユニット２２６、及び、置換え選択ユニット２２８を含む。待ち時間識別子メモリ２２２、及び、使用順序メモリ２２４はアドレス入力Ａによってアドレスされる。使用順序ユニット２２４は、タグコンパレータ２０４の出力も受け取る使用順序更新ユニット２２６に結合された出力を有する。使用更新ユニット２２６は使用順序メモリ２２４の入力に結合された出力を有する。置換え選択ユニット２２８は使用順序メモリ２２４及び待ち時間識別子メモリ２２２両方の出力に結合された入力を有する。制御ユニット２２０は全てのメモリ２００ａ−ｄ、２０２ａ−ｄ、２２２、２２４の入力に結合される。
【００２０】
作動に際して、キャッシュメモリ２０はデータメモリ２００ａ−ｄの任意の１つにおける所与の記憶位置に関するデータを記憶できる。データメモリ２００ａ−ｄはアドレススペース全体を記憶するために必要とされるよりも遥かに小さく、アドレス入力からのメモリアドレスの第１部分のみを受け取る。タグメモリ２０２ａ−ｄは、該当する場合に、所与のメモリアドレスに関するデータがどのデータメモリ２００ａ−ｄに記憶されるかの決定に役立つ。この目的のために、各タグメモリ２０２ａ−ｄはデータメモリ２００ａ−ｄの中の対応する１つに記憶されているデータのメモリアドレスの第２部分（第１部分以外）を記憶する。タグメモリ２０２ａ−ｄはアドレスの第１部分によってアドレスされ、対応するデータメモリ２００ａ−ｄに記憶されているデータに関するアドレスの第２部分を出力する。タグコンパレータ２０４はこの出力された第２部分をアドレス入力Ａにおいて受け取られたメモリアドレスの第２部分と比較する。タグメモリ２０２ａ−ｄの任意の１つからのアドレスの第２部分がアドレス入力Ａからの第２部分にマッチする場合には、タグコンパレータ２０４は対応するデータメモリ２００ａ−ｄからのデータをキャッシュメモリ２０の出力へパスするようにセレクタ２０６に合図する。
【００２１】
使用順序メモリ２２４はメモリアドレスの第１部分によってアドレスされるデータメモリ２００ａ−ｄ内における位置が最後にアクセスされた順序を表す情報を記憶する。この情報は、現在アクセスされているデータメモリ２００ａ−ｄを識別するためにタグコンパレータ２０４からの情報も受け取る更新ユニット２２６へ出力される。更新ユニット２２６は更新された順序を表す情報を前記の情報から決定し、更新情報を使用順序メモリ２２４に書き戻す。原則として、この情報は順列を表すが、その代りに、データメモリラベルの順序付けされたリストを使用することも可能である。
【００２２】
アドレス入力Ａにおいて受け取ったメモリアドレスに関するデータはどのデータメモリ２００ａ−ｄにも記憶されていないことをタグコンパレータ２０４を合図すると、置換え選択ユニット２２８は選定されたデータメモリ２００ａ−ｄが含まれるメモリアドレスに関するデータを記憶するためのデータメモリ２００ａ−ｄの１つを選定する。本発明によれば、この選択はデータメモリ２００ａ−ｄに記憶されているデータに関するメインメモリ位置の待ち時間に依存する。待ち時間識別子メモリ２２２は、データメモリ２００ａ−ｄ　アドレス入力から受け取ったメモリアドレスの第１部分によってアドレスされたデータメモリ２００ａ−ｄ内の位置に記憶されているデータに関するこれらメインメモリ位置の待ち時間を識別する識別子を記憶する。識別子は、例えば各データメモリ２００ａ−ｄに関する１つのビットを含み、このビットは対応するメインメモリ位置に関する長いか又は短い待ち時間を表示する。識別子は、比較的短い待ち時間を持つメインメモリ位置が利用可能であれば、比較的長い待ち時間を持つメインメモリ位置は選定されないように識別子を使用する置換え選択ユニット２２８に供給される。更に、同じ待ち時間を持つメインメモリ位置の中から選択するために置換え選択ユニット２２８は使用順序メモリ２２４から受け取った使用順序を用いることもできる。
【００２３】
メインメモリ位置に関するデータがメインメモリからフェッチされたときには、制御ユニット２２０は、選択ユニットによって選択されたデータメモリ２００ａ−ｄ内のデータを選定されたデータメモリ２００ａ−ｄ内のアドレスに配置する。この場合、前記アドレスはメインメモリアドレスの第１部分である。制御ユニット２２０は、選定されたデータメモリ２００ａ−ｄに対応するタグメモリ２０２ａ−ｄの１つ内におけるタグとしてメインメモリアドレスの第２部分を配置する。このメモリに記憶されているタグのアドレスもメインメモリアドレスの第１部分によって決定される。制御ユニット２２０は待ち時間表示メモリ２２２内に新規記憶されるデータに関するメインメモリ位置の待ち時間を表示する。更に、使用順序メモリ２２４は、選定されたデータメモリ２００ａ−ｄがメインメモリアドレスの第１部分の現行値用に使用されるべき最後のデータメモリであることを反映するように更新される。
【００２４】
アクセス待ち時間依存置換え戦略の多数の変形が可能である。これらの戦略は、比較的短いアクセス待ち時間を持つメインメモリ位置に関する置換え優先順位が絶対的ではないが、比較的長い待ち時間を持つメインメモリ位置に関するデータを記憶するキャッシュメモリ位置の例外的な選択を可能にする特質を持つことが好ましい。これは、比較的長いアクセス待ち時間を持つメインメモリ位置に関するデータが究極的に使用されることは非常に好ましくないので、このデータがキャッシュメモリ内に恒久的に留まることを防止するために役立つ。
【００２５】
これは、例えばキャッシュ管理ユニット１０２において、メインメモリ位置に関するデータがキャッシュ内に保持される期間がこれらのメインメモリ位置のアクセス待ち時間に従って重み付けされるＬＲＵ戦略を実施することによって実現可能である。この場合の重みは例えばアクセス待ち時間に逆比例することもあり得る。従って、２つのメインメモリ位置のアクセス待ち時間が２つのメインメモリ位置の係数だけ異なる場合には、大きい方の待ち時間を持つメインメモリ位置に関するデータは、小さい方の待ち時間を持つ位置に関するデータの長さの少なくとも２倍の長さに亙って当該データがキャッシュメモリ１０４内に所在する場合に限り、代替されるはずである。
【００２６】
他の一例において、アクセス待ち時間から独立したＬＲＵ戦略は周期的に、又は、事前決定されるか、或いは、無作為に選定された置換え回数の後毎に使用可能である。
【図面の簡単な説明】
本発明のこれら及び他の有利な態様については次に示す図面を用いて更に詳細に記述される。
【図１】
処理回路図である。
【図２】
キャッシュメモリ及びキャッシュ管理ユニットの実施形態例を示す図である。
【記号の説明】
１０　集積回路
１２　外部メモリ
１００　プロセッサ
１０２　キャッシュ管理ユニット
１０４　キャッシュメモリ
１０６　ローカルメモリ
１０８　データバス
１０９　アドレスバス
１１０　外部インタフェース
２０　　キャッシュメモリ
２０２　データメモリ
２０４　タグコンパレータ
２０６　データセレクタ
２２２　待ち時間識別子メモリ
２２４　使用順序メモリ
２２６　使用順序更新ユニット
２２８　置換え選択ユニット
【国際公開パンフレット】
2004503010.tif 000003
2004503010.tif 000004
2004503010.tif 000005
2004503010.tif 000006
2004503010.tif 000007
2004503010.tif 000008
2004503010.tif 000009
2004503010.tif 000010
2004503010.tif 000011
2004503010.tif 000012
2004503010.tif 000013
2004503010.tif 000014
2004503010.tif 000015
2004503010.tif 000016
【国際調査報告】
2004503010.tif 000017
2004503010.tif 000018
2004503010.tif 000019