(57)【要約】【課題】Ｎ個のウェイを持つセットアソシアティブ方式の記憶装置において、登録・置換が行われるエントリを有するウェイの選択を、ＬＲＵ法よりもはるかに低コストで、かつ、ＬＲＵに近い性能を出しつつ行う。【解決手段】セットアソシアティブ方式の記憶装置であって、少なくともリプレースフラグと所定データとを含む複数のエントリを有するＮ個（Ｎは２以上の整数）のウェイと、前記Ｎ個のウェイそれぞれから、同一アドレスによって指定されるエントリに含まれるリプレースフラグを取得する取得部と、前記取得部によって取得されたリプレースフラグに基づいて、置換対象のウェイを選択する選択部とを備える。【選択図】　　　図１
2004038298.tif 000002
【特許請求の範囲】
【請求項１】
少なくともリプレースフラグと所定データとを含む複数のエントリを有するＮ個（Ｎは２以上の整数）のウェイと、
前記Ｎ個のウェイそれぞれから、同一アドレスによって指定されるエントリに含まれるリプレースフラグを取得する取得部と、
前記取得部によって取得されたリプレースフラグに基づいて、置換対象のウェイを選択する選択部とを備える、セットアソシアティブ方式の記憶装置。
【請求項２】
前記同一アドレスによって指定されるエントリのうち前記選択部によって選択されたウェイが有するエントリに含まれる所定データを更新する所定データ更新部を備える、請求項１に記載のセットアソシアティブ方式の記憶装置。
【請求項３】
前記所定データ更新部によって最新に更新された所定データを含むエントリを有するウェイができるだけ遅く選択されるように、前記同一アドレスによって指定されるエントリのうち前記選択部によって選択されたウェイが有するエントリに含まれるリプレースフラグを更新するリプレースフラグ更新部をさらに備える、請求項２に記載のセットアソシアティブ方式の記憶装置。
【請求項４】
前記リプレースフラグ更新部は、１ビットのリプレースフラグに基づいて前記更新を行う、請求項３に記載のセットアソシアティブ方式の記憶装置。
【請求項５】
前記同一アドレスによって指定されるエントリの全てが有効か否かを判定する判定部をさらに備え、
前記選択部は、前記判定部によって少なくとも一つのエントリが無効であると判定された場合に、リプレースフラグとは無関係に、その無効なエントリを有するウェイを選択する、請求項１に記載のセットアソシアティブ方式の記憶装置。
【請求項６】
前記各エントリはさらに、バリッドフラグを含み、
前記取得部は、前記Ｎ個のウェイそれぞれから、前記同一アドレスによって指定されるエントリに含まれるバリッドフラグを取得し、
前記判定部は、前記取得部によって取得されたバリッドフラグに基づいて、エントリの全てが有効か否かを判定する、請求項５に記載のセットアソシアティブ方式の記憶装置。
【請求項７】
前記同一アドレスに基づいて分岐予測を行う分岐予測部をさらに備え、
前記選択部は、前記分岐予測部が分岐すると予測しなかった場合に、置換対象のウェイを選択する、請求項１に記載のセットアソシアティブ方式の記憶装置。
【請求項８】
少なくともリプレースフラグと所定データとを含む複数のエントリを有するＮ個（Ｎは２以上の整数）のウェイと、
前記Ｎ個のウェイそれぞれから、同一アドレスによって指定されるエントリに含まれるリプレースフラグを取得する取得部と、
前記取得部によって取得されたリプレースフラグに基づいて、置換対象のウェイを選択する選択部とを備える、セットアソシアティブ方式のキャッシュメモリ装置。
【請求項９】
前記同一アドレスによって指定されるエントリのうち前記選択部によって選択されたウェイが有するエントリに含まれる所定データを更新する所定データ更新部を備える、請求項８に記載のセットアソシアティブ方式のキャッシュメモリ装置。
【請求項１０】
前記所定データ更新部によって最新に更新された所定データを含むエントリを有するウェイができるだけ遅く選択されるように、前記同一アドレスによって指定されるエントリのうち前記選択部によって選択されたウェイが有するエントリに含まれるリプレースフラグを更新するリプレースフラグ更新部をさらに備える、請求項９に記載のセットアソシアティブ方式のキャッシュメモリ装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、Ｎ個のウェイを有するセットアソシアティブ方式の記憶装置において置換対象のウェイを選択する技術に関する。
【０００２】
【従来の技術】
Ｎ個のウェイを持つセットアソシアティブ方式の記憶装置において、新規に情報を登録する際に、記憶装置が既に全て使用されていて、登録可能な場所がない場合、記憶された情報の中から、記憶装置より削除する情報を選択し、新たな登録情報との入れ替えを行う必要がある。その選択方法としては、最近使われていない情報を優先的に削除するＬＲＵ（Ｌｅａｓｔ　Ｒｅｃｅｎｔｌｙ　Ｕｓｅｄ）法である。
【０００３】
しかしながら、ＬＲＵ法を行うには多大なコストを必要とする。ＬＲＵを実行するために最低限必要なビット数は、Ｎウェイの装置で、ｎＣ２である。例えば４つのウェイを持つ装置であれば、最低限６ビットのフラグが必要となり、それがパイプライン段数分、装置内をめぐることになる。コストが６倍で効いてくるため、パイプラインの段数が増えれば増えるほど、多大なるコストがかかることになる。ＬＲＵの他には、置換を示すフラグをウェイ毎に設定する方法があるが、これまでに提案されてきたものは２ウェイ用のものであり、これは３ウェイ以上には適用できないため、あらたな技術を開発する必要がある。
【０００４】
【発明が解決しようとする課題】
本発明の課題は、Ｎ個のウェイを持つセットアソシアティブ方式の記憶装置において、登録・置換が行われるエントリを有するウェイの選択を、ＬＲＵ法よりもはるかに低コストで、かつ、ＬＲＵに近い性能を出しつつ行うことにある。
【０００５】
【課題を解決するための手段】
本発明は、上記課題を解決するためになされたものであり、セットアソシアティブ方式の記憶装置であって、少なくともリプレースフラグと所定データとを含む複数のエントリを有するＮ個（Ｎは２以上の整数）のウェイと、前記Ｎ個のウェイそれぞれから、同一アドレスによって指定されるエントリに含まれるリプレースフラグを取得する取得部と、前記取得部によって取得されたリプレースフラグに基づいて、置換対象のウェイを選択する選択部とを備える構成とした。
【０００６】
本発明によれば、各エントリに保持される比較的少ビット（通常１ビット）のリプレースフラグに基づいて置換対象のウェイ（エントリ）を選択することが可能となる。したがって、Ｎ個のウェイを持つセットアソシアティブ方式の記憶装置において、登録・置換が行われるエントリを有するウェイの選択を、ＬＲＵ法よりもはるかに低コストで、かつ、ＬＲＵに近い性能を出しつつ行うことが可能になる。
【０００７】
上記セットアソシアティブ方式の記憶装置においては、例えば、前記同一アドレスによって指定されるエントリのうち前記選択部によって選択されたウェイが有するエントリに含まれる所定データを更新する所定データ更新部を備える。
【０００８】
このようにすれば、選択部によって選択されたウェイが有するエントリに含まれる所定データ（例えば分岐アドレス）を更新することが可能となる。
【０００９】
上記セットアソシアティブ方式の記憶装置においては、例えば、前記所定データ更新部によって最新に更新された所定データを含むエントリを有するウェイができるだけ遅く選択されるように、前記同一アドレスによって指定されるエントリのうち前記選択部によって選択されたウェイが有するエントリに含まれるリプレースフラグを更新するリプレースフラグ更新部をさらに備える。
【００１０】
このようにすれば、ＬＲＵ法と同様のウェイを置換対象ウェイとして選択することが可能となる。
【００１１】
上記セットアソシアティブ方式の記憶装置においては、例えば、前記リプレースフラグ更新部は、１ビットのリプレースフラグに基づいて前記更新を行う。
【００１２】
上記セットアソシアティブ方式の記憶装置においては、例えば、前記同一アドレスによって指定されるエントリの全てが有効か否かを判定する判定部をさらに備え、前記選択部は、前記判定部によって少なくとも一つのエントリが無効であると判定された場合に、リプレースフラグとは無関係に、その無効なエントリを有するウェイを選択する。
【００１３】
このようにすれば、同一アドレスによって指定されるエントリのうちに無効なエントリが存在する場合であっても、ＬＲＵ法と同様のウェイを置換対象ウェイとして選択することが可能となる。
【００１４】
上記セットアソシアティブ方式の記憶装置においては、例えば、前記各エントリはさらに、バリッドフラグを含み、前記取得部は、前記Ｎ個のウェイそれぞれから、前記同一アドレスによって指定されるエントリに含まれるバリッドフラグを取得し、前記判定部は、前記取得部によって取得されたバリッドフラグに基づいて、エントリの全てが有効か否かを判定する。
【００１５】
このようにすれば、同一アドレスによって指定されるエントリのうちに無効なエントリが存在する場合であっても、各エントリに保持される比較的少ビット（通常１ビット）のバリッドフラグに基づいて、ＬＲＵ法と同様のウェイを置換対象ウェイとして選択することが可能となる。
【００１６】
上記セットアソシアティブ方式の記憶装置においては、例えば、前記同一アドレスに基づいて分岐予測を行う分岐予測部をさらに備え、前記選択部は、前記分岐予測部が分岐すると予測しなかった場合に、置換対象のウェイを選択する。
【００１７】
このようにすれば、分岐予測部によって正しく分岐予測できなかった場合に、各エントリに保持される比較的少ビット（通常１ビット）のリプレースフラグに基づいて置換対象のウェイ（エントリ）を選択することが可能となる。
【００１８】
本発明は、セットアソシアティブ方式のキャッシュメモリ装置として次のように特定することができる。
【００１９】
少なくともリプレースフラグと所定データとを含む複数のエントリを有するＮ個（Ｎは２以上の整数）のウェイと、前記Ｎ個のウェイそれぞれから、同一アドレスによって指定されるエントリに含まれるリプレースフラグを取得する取得部と、前記取得部によって取得されたリプレースフラグに基づいて、置換対象のウェイを選択する選択部とを備える、セットアソシアティブ方式のキャッシュメモリ装置。
【００２０】
上記セットアソシアティブ方式の記憶装置（又はキャッシュメモリ装置）において、新規に登録を要求されるデータが生じ、かつ新規に登録可能な場所が存在しなかった場合、出来る限り古いデータと置換して、新規にデータを登録する必要がある。
【００２１】
これを実現するため、それぞれのウェイ毎に置換フラグをもち、全ウェイの置換フラグをひとまとめにして、置換を行うウェイを指し示すステートマシンの様に取り扱う。即ち、記憶装置の参照が行われる度、取り決めに従い置換フラグの値を変更し、全ウェイの置換フラグの値を合わせて、次に置換の対象となるウェイを決定する。
【００２２】
置換フラグ変更の取り決めは、あるエントリについて、置換を含め、新規に登録されたウェイがその後、次の置換対象となる機会が出来るだけ遅くなるように設定される。また、無効なウェイが存在した場合は、置換フラグの値に関係なく、無効なウェイに新規登録が行われるように処理される。この方式では、実際の置換フラグの変更は、置換対象となるウェイのフラグのみの変更で済み、選択されたウェイを示す信号と、該ウェイの変更後のフラグの値だけを送出する。
【００２３】
読み出したエントリの内に、無効なウェイが存在した場合にも、置換フラグを取り決めに従い変更して送出する。この場合も、送出されるのは、無効なウェイを示す信号と該ウェイの変更後のフラグの値だけである。記憶装置の外部装置の要請により、記憶装置から送られたウェイに対するエントリの更新、または新規登録が行われる。置換フラグもこの時新たに登録される。
【００２４】
このように、回路内をめぐる信号は、該ウェイの置換フラグ１ビットおよび、ウェイを示す信号数ビットのみである。これがＬＲＵであれば、全ウェイの中から任意の二つのウェイを選ぶ選び方の数ぶんだけのビット数が必要となり、それは例えば４ウェイのセットアソシアティブであれば、６ビットである。ウェイを示す信号は、置換フラグの方式に関係なく必要であるため、ＬＲＵでは本方式に比べ、４ウェイの場合６倍のコストが掛かることになる。パイプラインにより、段数が刻まれれば刻まれるほど、コストの差は明らかとなる。
【００２５】
【発明の実施の形態】
以下、本発明の実施形態であるＮウェイ・セット・アソシアティブ方式の記憶装置について図面を参照しながら説明する。Ｎは、２ｎの整数（例えば、２、４、８、１６、３２・・・等）、又は、その他の整数（２以上の整数）である。本実施形態においてはＮ＝４の４ウェイ・セット・アソシアティブ方式の記憶装置について説明する。
【００２６】
図１及び図２は、本発明の実施形態である４ウェイ・セット・アソシアティブ方式の記憶装置の概略構成を説明するための図である。
【００２７】
図１及び図２に示すように、記憶装置１００は、主に、４つのウェイＷ０からＷ３を持つ分岐履歴記憶装置、アドレス生成ユニット１０１、キャッシュメモリ１０２、デコーダ１０３、分岐履歴検索結果判定ユニット１０４、等価性判定部１０５、ヒットウェイ選択部１０６、置換対象ウェイ選択部１０７、及び、更新制御装置１０８等を備える。これらはバス等を介して接続されている。
【００２８】
図３は、各ウェイ（分岐履歴記憶装置）の構成を説明するための図である。ウェイＷ０からＷ３は、ＳＲＡＭ等の比較的高速にアクセス可能な記憶装置である。図３に示すように、ウェイＷ０からＷ３は、複数のエントリを有する。エントリは、タグ部ＴＧとデータ部ＤＴを含む。タグ部ＴＧは、命令アドレス（の一部）ＴＧ１、バリッドフラグＶ、リプレースフラグＲ、及び、その他のフラグＴＧ２からなる。データ部ＤＴは、所定データとしての分岐先アドレスＤＴ１からなる。
【００２９】
エントリは、アドレス生成ユニット１０１から出力される命令アドレスＡの一部（例えば＜１５：５＞）によって指定される。本実施形態では４ウェイなので４つのエントリが指定される。さらに、その４つのエントリのうち、命令アドレスＡの一部（例えば＜３１：１６＞）によって指定される一のエントリが決定される。この一のエントリを決定するために、命令アドレスＴＧ１には命令アドレスの一部（例えば＜３１：１６＞）が格納されている。例えば、登録時に、命令アドレスＡの一部＜１５：５＞を使ってエントリを決定し、残りの部分がタグ部（命令アドレスＴＧ１を含む）にデータとして格納されるようになっている。なお、命令アドレス＜３１：１６＞との記載は、命令アドレスＴＧ１が命令アドレス（例えば３２ビット）の一部３１ビット目から１６ビット目であることを意味する。
【００３０】
バリッドフラグＶは、エントリの有効又は無効を示すフラグである。例えば、バリッドフラグＶが”１”であればそのバリッドフラグＶを含むエントリが有効であること、バリッドフラグＶが”０”であればそのバリッドフラグＶを含むエントリが無効であることを示す。バリッドフラグＶは、置換対象のウェイを選択するためにも用いられる。
【００３１】
リプレースフラグＲは、置換対象のウェイを選択するために用いられるフラグである。分岐先アドレス（ブランチヒストリともいう）ＤＴ１には、キャッシュメモリ１０２（又は主記憶装置）からフェッチされた分岐命令の分岐先アドレスが格納される。
【００３２】
アドレス生成ユニット１０１は、命令アドレスＡ等を生成し出力するためのものである。アドレス生成ユニット１０１はプログラムカウンタ等を含む。キャッシュメモリ１０２は、ＳＲＡＭ等の比較的高速にアクセス可能な記憶装置である。デコーダ１０３は、キャッシュメモリ１０２（又は主記憶装置）からフェッチされた分岐命令等をデコードするためのものである。
【００３３】
分岐履歴検索結果判定ユニット１０４は、分岐予測装置から得られた分岐先アドレスがメモリ領域（キャッシュメモリ１０２又は主記憶装置）からフェッチされた分岐命令の分岐先アドレスと等しいか、つまり、予測が正しかったかどうかを判定するためのものである。等価性判定部１０５は、アドレス生成ユニット１０１から出力される命令アドレスＡ（の一部）とタグ部ＴＧの命令アドレスＴＧ１とを比較し、一致する命令アドレスＴＧ１が存在すればヒット信号（ヒットを示すビット）を出力する。ヒットウェイ選択部１０６は、各ウェイからのヒット信号に基づいてヒットしたウェイを指定するヒットウェイ選択信号を出力する。
【００３４】
置換対象ウェイ選択部１０７は、主に置換対象のウェイを選択するためのものである。図４に置換対象ウェイ選択部１０７の概略構成を示す。置換対象ウェイ選択部１０７は、各ウェイＷ０からＷ３それぞれから、同一アドレスＡによって指定されるエントリに含まれるリプレースフラグＲ（ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ０，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ１，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ２，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ３）及びバリッドフラグＶ（ｗａｙ０＿ｖａｌｉｄ，ｗａｙ１＿ｖａｌｉｄ，ｗａｙ２＿ｖａｌｉｄ，ｗａｙ３＿ｖａｌｉｄ）を取得する。置換対象ウェイ選択部１０７は最終的に、置換対象のウェイを指定する置換対象ウェイ選択信号（ｒｅｐｌａｃｅ＿ｗａｙ＜１：０＞）及びその選択信号によって指定されるウェイに書き込むリプレースフラグ（ｎｅｗ＿ｒｅｐｌａｃｅ＿ｆｌａｇ）を出力する。
【００３５】
置換対象ウェイ選択部１０７は、ウェイＷ０からＷ３それぞれから取得されたリプレースフラグＲに基づいて、置換対象のウェイを選択する。図５は、それらリプレースフラグＲによって選択される置換対象のウェイを説明するための図である。同図は、ウェイＷ０からＷ３それぞれから左側のリプレースフラグＲ（例えば（ｗａｙ０，ｗａｙ１，ｗａｙ２，ｗａｙ３）＝（０，０，０，０））が取得された場合には、置換対象のウェイとして右側の○が位置するウェイ（例えばウェイ０）が選択されることを示す。
【００３６】
置換対象ウェイ選択部１０７は、ウェイＷ０からＷ３それぞれから取得されたバリッドフラグＶ全てが有効であれば、リプレースフラグＲに基づいて選択されたウェイ（図５の関係で定まるウェイ）を指定する置換対象ウェイ選択信号（ｒｅｐｌａｃｅ＿ｗａｙ＜１：０＞）を出力する。
【００３７】
また、置換対象ウェイ選択部１０７は、ウェイＷ０からＷ３それぞれから取得されたバリッドフラグＶに基づいて、置換対象のウェイを選択する。即ち、置換対象ウェイ選択部１０７は、各ウェイから取得されたバリッドフラグＶのうち少なとも一つが無効であれば、バリッドフラグＶに基づいて選択されたウェイ（その無効なエントリを有するウェイ）を指定する置換対象ウェイ選択信号（ｒｅｐｌａｃｅ＿ｗａｙ＜１：０＞）を出力する。
【００３８】
また、置換対象ウェイ選択部１０７は、置換対象ウェイ選択信号（ｒｅｐｌａｃｅ＿ｗａｙ＜１：０＞）によって指定されるウェイに書き込むリプレースフラグＲ（ｎｅｗ＿ｒｅｐｌａｃｅ＿ｆｌａｇ）を出力する。即ち、置換対象ウェイ選択部１０７は、ウェイＷ０からＷ３それぞれから取得されるバリッドフラグＶ全てが有効であれば、置換対象ウェイ選択信号（ｒｅｐｌａｃｅ＿ｗａｙ＜１：０＞）によって指定されるウェイから取得されたリプレースフラグＲを反転したリプレースフラグ（ｎｅｗ＿ｒｅｐｌａｃｅ＿ｆｌａｇ）を出力する。一方、置換対象ウェイ選択部１０７は、ウェイＷ０からＷ３それぞれから取得されたバリッドフラグＶのうち少なくとも一つが無効であれば、図６の表に従ってリプレースフラグ（ｎｅｗ＿ｒｅｐｌａｃｅ＿ｆｌａｇ）を出力する。
【００３９】
同図は、ウェイＷ０からＷ３それぞれから左側のリプレースフラグＲ（例えば（ｗａｙ０，ｗａｙ１，ｗａｙ２，ｗａｙ３）＝（０，０，０，０））が取得され、かつ、置換対象ウェイ選択信号（ｒｅｐｌａｃｅ＿ｗａｙ＜１：０＞）によって無効なエントリを有するウェイ（例えばウェイ０）が指定された場合には、右側の”反転”が位置するウェイであるので、その選択信号によって指定されるウェイ０から取得されたリプレースフラグＲを反転したリプレースフラグ（ｎｅｗ＿ｒｅｐｌａｃｅ＿ｆｌａｇ）を出力することを示す。それ以外の場合には、リプレースフラグＲを反転することなく、そのままリプレースフラグ（ｎｅｗ＿ｒｅｐｌａｃｅ＿ｆｌａｇ）として出力する。
【００４０】
上記置換対象ウェイ選択部１０７は、図７から図１２に一例として示す論理回路によって実現される。この論理回路は説明の便宜上各図に分けて記載したが、実際はこれらが結合した一つの回路である。結合関係は各図に記載した入出力の信号名により示される。
【００４１】
更新制御装置１０８は、主に、同一アドレスによって指定される４つのエントリのうち置換対象ウェイ選択信号（ｒｅｐｌａｃｅ＿ｗａｙ＜１：０＞）によって指定されるウェイが有するエントリのリプレースフラグＲを更新するためのものである。
【００４２】
次に、上記構成の記憶装置１００の動作について図面を参照しながら説明する。図１３及び図１６は、記憶装置１００の動作を説明するためのフローチャートである。図１５は、更新制御装置１０８の制御対象を説明するための図である。
【００４３】
まず、動作の概要について説明する。アドレス生成ユニット１０１から出力された命令アドレスＡは、本来のキャッシュメモリ１０２へのアクセスと同時に、分岐履歴記憶装置（各ウェイＷ０からＷ３）にリードアクセスし、この命令アドレスＡが分岐命令がフェッチされてきた場合の分岐先アドレスの予測を得る。予測された分岐先アドレスは、アドレス生成ユニットに送出され、新たなキャッシュアクセスに用いられる。同時に、分岐履歴検索結果判定ユニット１０４で、その整合性が判定される。
【００４４】
この結果、分岐命令であると予測した命令が分岐でなかったまたは分岐ではあったが分岐履歴記憶装置に記憶されていた分岐先アドレスが正しくなかったと判断された場合または装置がヒットせず分岐先アドレスが得られずかつ分岐命令があった場合に、該命令アドレスとそれに対応する分岐先アドレスを次回の検索のため新たに登録する（ライト実行）。（先行していたキャッシュアクセスはキャンセルされる。）この時、どのウェイに登録するかを本実施形態のリプレースフラグによって決定する。
【００４５】
次に、動作の詳細について説明する。リードアクセスのために、アドレス生成ユニット１０１から命令アドレスＡが全ウェイに送られてきたとする（Ｓ１００）。等価性判定部１０５は、ヒット判定を行う（Ｓ１０１）。具体的には、等価性判定部１０５は、その同一アドレスＡ（の一部）によって指定される全てのエントリ（ウェイ）からタグ部ＴＧの命令アドレスＴＧ１を読み出す。そして、等価性判定部１０５は、その読み出したデータと命令アドレスＡ（の一部）とを比較し、両者が一致すればヒット信号（ヒットを示すビット）を出力する。
【００４６】
ヒットした場合には（Ｓ１０１：Ｙｅｓ）、そのヒットしたウェイから予測結果としての分岐先アドレスＤＴ及びリプレースフラグＲが読み出され、そのヒットウェイを指定するヒットウェイ選択信号と共に分岐履歴検索結果判定ユニット１０４に送られる（Ｓ１０２）。同時に、その読み出された予測結果としての分岐先アドレスＤＴはアドレス生成ユニット１０１にも送られる。
【００４７】
これにより、その予測結果としての分岐先アドレスＤＴによって指定されるキャッシュメモリ１０２（又は主記憶装置）の領域から分岐命令がフェッチ及びデコードされ、そのフェッチされた分岐命令の実際の分岐先アドレスが分岐履歴検索結果判定ユニット１０４に送られる。分岐履歴検索結果判定ユニット１０４は、そのフェッチされた分岐命令の実際の分岐先アドレスと、ヒットしたウェイから送られる予測結果としての分岐先アドレスＤＴとを比較し、両者が一致すれば予測が正しかったものとして、その後の処理を継続する。
【００４８】
一方、両者が一致しなければ予測が正しくなかったものとして、ヒットウェイ選択信号によって指定されるウェイが有するエントリのバリッドフラグを、場合によっては無効にする。これとともに、ヒットしたウェイから送られるリプレースフラグＲを反転して登録する。また、付属のタグの更新等が行われる（Ｓ１０３）。なお、いずれかのウェイがヒットすれば（Ｓ１０１：Ｙｅｓ）、これらのデータは有効であるとして、リプレースフラグＲは更新されない。
【００４９】
一方、ヒットしなかった場合には（Ｓ１０１：Ｎｏ）、置換対象ウェイ選択部１０７によって置換対象のウェイが選択される。以下、この処理について説明する。なお、Ｓ１０６からＳ１０９は説明の便宜上時系列的に表現しているが、置換対象ウェイ選択部１０７は論理回路によって構成されるため、これらのステップはほぼ同時に進行する。以下、ほぼ同時というときは、このことを意味する。
【００５０】
ヒットしなかった場合には（Ｓ１０１：Ｎｏ）、置換対象ウェイ選択部１０７は、ウェイＷ０からＷ３それぞれから、同一アドレスＡ（の一部）によって指定される４つのエントリに含まれるリプレースフラグＲ（ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ０，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ１，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ２，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ３）及びバリッドフラグＶ（ｗａｙ０＿ｖａｌｉｄ，ｗａｙ１＿ｖａｌｉｄ，ｗａｙ２＿ｖａｌｉｄ，ｗａｙ３＿ｖａｌｉｄ）を取得する（Ｓ１０５）。
【００５１】
置換対象ウェイ選択部１０７は、ウェイＷ０からＷ３それぞれから取得されたバリッドフラグＶに基づいて、それら全てのバリッドフラグＶが有効か否かを判定する（Ｓ１０６）。この判定は、置換対象ウェイ選択部１０７を構成する論理回路のうち、図１２に示すアンド演算回路Ｃ１が行う。アンド演算回路Ｃ１にはバリッドフラグＶ（ｗａｙ０＿ｖａｌｉｄ，ｗａｙ１＿ｖａｌｉｄ，ｗａｙ２＿ｖａｌｉｄ，ｗａｙ３＿ｖａｌｉｄ）が入力され、それら全てのバリッドフラグＶが有効である場合には”１”、少なくとも一つのバリッドフラグＶが無効である場合には”０”が出力される。
【００５２】
ここでは、全てのバリッドフラグＶが有効である場合について説明する。置換対象ウェイ選択部１０７は、ほぼ同時に、リプレースフラグＲに基づいて、置換対象ウェイを選択する（Ｓ１０７）。この選択は、置換対象ウェイ選択部１０７を構成する論理回路のうち、図７、図８、及び、図９に示す部分が行う。
【００５３】
図７に示す論理回路部分にはリプレースフラグＲ（ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ０，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ１，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ２，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ３）が入力され、図８及び図９に示す論理回路部分を介して、図９に示す論理回路部分から置換対象ウェイを指定する置換対象ウェイ選択信号（ｒｅｐｌａｃｅ＿ｗａｙ０，ｒｅｐｌａｃｅ＿ｗａｙ１，ｒｅｐｌａｃｅ＿ｗａｙ２，ｒｅｐｌａｃｅ＿ｗａｙ３）が出力される。
【００５４】
ここでは、図７に示す論理回路部分にリプレースフラグＲ（ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ０，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ１，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ２，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ３）＝（１，１，０，０）が入力されたとする。この場合、図９に示す論理回路部分から置換対象ウェイを指定する置換対象ウェイ選択信号（ｒｅｐｌａｃｅ＿ｗａｙ０，ｒｅｐｌａｃｅ＿ｗａｙ１，ｒｅｐｌａｃｅ＿ｗａｙ２，ｒｅｐｌａｃｅ＿ｗａｙ３）＝（０，０，１，０）が出力される。これはビットオン位置のウェイ２（図５の関係で定まるウェイ）が選択されたことを示す。
【００５５】
ここでは、全てのバリッドフラグＶが有効であるため（Ｓ１０６：Ｎｏ）、図１２に示すアンド演算回路Ｃ１の出力が”１”となる。このため、セレクタＳＥ０からＳＥ３によって置換対象ウェイ選択信号（ｒｅｐｌａｃｅ＿ｗａｙ０，ｒｅｐｌａｃｅ＿ｗａｙ１，ｒｅｐｌａｃｅ＿ｗａｙ２，ｒｅｐｌａｃｅ＿ｗａｙ３）が選択される。その選択された４ビットの置換対象ウェイ選択信号は２つのＯＲ演算回路Ｃ２によって２ビットの置換対象ウェイ選択信号（ｒｅｐｌａｃｅ＿ｗａｙ＜０＞，ｒｅｐｌａｃｅ＿ｗａｙ＜１＞）に変換され、更新制御装置１０８へ送られる。
【００５６】
置換対象ウェイ選択部１０７は、ほぼ同時に、置換対象ウェイ選択信号によって指定されるウェイ２から取得されたリプレースフラグＲ＝”０”を反転したリプレースフラグ（ｎｅｗ＿ｒｅｐｌａｃｅ＿ｆｌａｇ）＝”１”を出力する。このリプレースフラグ（ｎｅｗ＿ｒｅｐｌａｃｅ＿ｆｌａｇ）は、更新制御装置１０８へ送られる。分岐履歴検索結果判定ユニット１０４（更新制御装置１０８）は、置換対象ウェイ選択信号によって指定されるウェイ２の命令アドレス（の一部）及びその実際の分岐先アドレス（所定データ）を更新する（Ｓ１０８）。
【００５７】
この場合、更新制御装置１０８が所定データ更新部として機能する。これとともに、更新制御装置１０８は、その最新に更新された分岐先アドレスを含むエントリを有するウェイができるだけ遅く選択されるように、同一アドレスＡによって指定されるエントリに含まれるリプレースフラグＲの更新指示を出力する。これにより、置換対象ウェイ選択信号によって指定されるウェイ２にリプレースフラグ（ｎｅｗ＿ｒｅｐｌａｃｅ＿ｆｌａｇ）＝”１”が書き込まれる。この場合、更新制御装置１０８がリプレースフラグ更新部として機能する。更新後のリプレースフラグＲは次回、置換対象ウェイを選択するときに用いられる。
【００５８】
これにより、次回、ヒットしなかった場合には（Ｓ１０１：Ｎｏ）、置換対象ウェイ選択部１０７に、更新後のリプレースフラグＲ（ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ０，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ１，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ２，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ３）＝（１，１，１，０）が入力される。この場合、図９に示す論理回路部分から置換対象ウェイを指定する置換対象ウェイ選択信号（ｒｅｐｌａｃｅ＿ｗａｙ０，ｒｅｐｌａｃｅ＿ｗａｙ１，ｒｅｐｌａｃｅ＿ｗａｙ２，ｒｅｐｌａｃｅ＿ｗａｙ３）＝（０，０，０，１）が出力される。これは次回、ヒットしなかった場合には（Ｓ１０１：Ｎｏ）、置換対象ウェイとしてビットオン位置のウェイ３（図５の関係で定まるウェイ）が選択されることを示す。
【００５９】
このように、図５に示した表に従ってリプレースフラグＲを更新することによって、最新に更新されたウェイができるだけ遅く置換対象として選択されるようになる。
【００６０】
次に、少なくとも一つのバリッドフラグＶが無効である場合について説明する。置換対象ウェイ選択部１０７は、ほぼ同時に、リプレースフラグＲとは関係なく、バリッドフラグＶに基づいて、置換対象ウェイ（無効なエントリを有するウェイ）を選択する。この選択は、置換対象ウェイ１０７を構成する論理回路のうち、図１０に示す部分が行う。なお、無効なエントリが複数存在する場合には、任意の取り決めに従って、優先順位が決定される（例えば、最若番のウェイが選択される）。
【００６１】
図１０に示す論理回路部分にはバリッドフラグＶ（ｗａｙ０＿ｖａｌｉｄ，ｗａｙ１＿ｖａｌｉｄ，ｗａｙ２＿ｖａｌｉｄ，ｗａｙ３＿ｖａｌｉｄ）が入力され、置換対象ウェイ（無効なエントリを有するウェイ）を指定する置換対象ウェイ選択信号（ｃｒｅａｔｅ＿ｗａｙ０，ｃｒｅａｔｅ＿ｗａｙ１，ｃｒｅａｔｅ＿ｗａｙ２，ｃｒｅａｔｅ＿ｗａｙ３）が出力される。ここでは、図１０に示す論理回路部分にリプレースフラグＲ（ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ０，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ１，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ２，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ３）＝（１，１，０，０）及びバリッドフラグＶ（ｗａｙ０＿ｖａｌｉｄ，ｗａｙ１＿ｖａｌｉｄ，ｗａｙ２＿ｖａｌｉｄ，ｗａｙ３＿ｖａｌｉｄ）＝（１，０，１，１）が入力されたとする。
【００６２】
この場合、図１０に示す論理回路部分から置換対象ウェイを指定する置換対象ウェイ選択信号（ｃｒｅａｔｅ＿ｗａｙ０，ｃｒｅａｔｅ＿ｗａｙ１，ｃｒｅａｔｅ＿ｗａｙ２，ｃｒｅａｔｅ＿ｗａｙ３）＝（０，１，０，０）が出力される。これはビットオン位置のウェイ１が無効なエントリを有するウェイであり、そのウェイ１が選択されたことを示す。
【００６３】
ここでは、少なくとも一つのバリッドフラグＶが無効であるため（Ｓ１０６：Ｙｅｓ）、図１２に示すアンド演算回路Ｃ１の出力が”０”となる。このため、セレクタＳＥ０からＳＥ３によって置換対象ウェイ選択信号（ｃｒｅａｔｅ＿ｗａｙ０，ｃｒｅａｔｅ＿ｗａｙ１，ｃｒｅａｔｅ＿ｗａｙ２，ｃｒｅａｔｅ＿ｗａｙ３）が選択される。その選択された４ビットの置換対象ウェイ選択信号は、２つのＯＲ演算回路Ｃ２によって２ビットの置換対象ウェイ選択信号（ｒｅｐｌａｃｅ＿ｗａｙ＜０＞，ｒｅｐｌａｃｅ＿ｗａｙ＜１＞）に変換され、更新制御装置１０８へ送られる。
【００６４】
置換対象ウェイ選択部１０７は、ほぼ同時に、図６に示したルールに従って、置換対象ウェイ選択信号によって指定されるウェイ１から取得されたリプレースフラグＲ＝”１”を反転させないリプレースフラグ（ｎｅｗ＿ｒｅｐｌａｃｅ＿ｆｌａｇ）＝”１”を出力する。このリプレースフラグ（ｎｅｗ＿ｒｅｐｌａｃｅ＿ｆｌａｇ）は、更新制御装置１０８へ送られる。分岐履歴検索結果判定ユニット１０４（更新制御装置１０８）は、置換対象ウェイ選択信号によって指定されるウェイ１に命令アドレス（の一部）及びその実際の分岐先アドレス（所定データ）を更新する（Ｓ１０８）。
【００６５】
この場合、更新制御装置１０８が所定データ更新部として機能する。これとともに、更新制御装置１０８は、その最新に更新された分岐先アドレスを含むエントリを有するウェイができるだけ遅く選択されるように、同一アドレスによって指定されるエントリに含まれるリプレースフラグＲの更新指示を出力する。これにより、置換対象ウェイ選択信号によって指定されるウェイ１にリプレースフラグ（ｎｅｗ＿ｒｅｐｌａｃｅ＿ｆｌａｇ）＝”１”が書き込まれる。この場合、更新制御装置１０８がリプレースフラグ更新部として機能する。更新後のリプレースフラグＲは次回、置換対象ウェイを選択するときに用いられる。
【００６６】
これにより、次回、ヒットしなかった場合には（Ｓ１０１：Ｎｏ）、置換対象ウェイ選択部１０７に、更新後のリプレースフラグＲ（ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ０，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ１，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ２，ｒｅｐｌａｃｅ＿ｆｌａｇ＿ｗａｙ３）＝（１，１，０，０）が入力される。この場合、図９に示す論理回路部分から置換対象ウェイを指定する置換対象ウェイ選択信号（ｒｅｐｌａｃｅ＿ｗａｙ０，ｒｅｐｌａｃｅ＿ｗａｙ１，ｒｅｐｌａｃｅ＿ｗａｙ２，ｒｅｐｌａｃｅ＿ｗａｙ３）＝（０，０，１，０）が出力される。これは次回、ヒットしなかった場合には（Ｓ１０１：Ｎｏ）、置換対象ウェイとしてビットオン位置のウェイ２（図５の関係で定まるウェイ）が選択されることを示す。
【００６７】
この後は、図５のルールに従って、置換対象となる機会が順番に巡ってくることになる。つまり、最新に更新されたウェイ１ができるだけ遅く置換対象として選択されるようになる。ただし、組合わせによっては、最も遅い場合よりも一つだけ早く置換の機会が来る場合もあるが、全ての組合わせで、「最も遅く置換の機会が来る」か、あるいは、「最も遅い場合よりも一つだけ早く置換の機会が来る」となり、完全なＬＲＵではないが、それに近い状態で動作する。
本実施形態の記憶装置１００によれば、各ウェイに１ビットのリプレースフラグを用意し、取り決めに従ってリプレースフラグＲ、およびバリッド信号Ｖからエントリの置換の制御を行い、またリプレースフラグＲを更新することで、ＬＲＵに近い動作での記憶装置のエントリの入れ替えが実現される。このために必要な情報は、ウェイにつき１ビットのフラグのみである。また、その情報を外部に出すときは、さらに１ビットに圧縮される。これは、従来のＬＲＵのような方法と比べて、格段に低コストとなることを意味する。
【００６８】
次に、上記実施形態の変形例について説明する。
【００６９】
上記実施形態においては、ヒットしなかった場合に（Ｓ１０１：Ｎｏ）、リプレースフラグＲを更新するように説明した（Ｓ１０８、Ｓ１０９）が、本発明はこれに限定されない。例えば、ヒットした場合に、リプレースフラグＲを更新するようにしてもよい。図１４は、ヒットした場合に、リプレースフラグＲを更新する例を示している。同図は、図１３に示したフローチャートのＳ１０２及びＳ１０３をＳ２０２及びＳ２０３に置き換えたものである。その他のステップについては、既に説明したものと同じであるので、説明を省略する。
【００７０】
ヒットした場合には（Ｓ１０１：Ｙｅｓ）、全ウェイから読み出したリプレースフラグＲと図６に示した表に従って、リプレースフラグＲを決定し、そのヒットウェイを指定するヒットウェイ選択信号と共に分岐履歴検索結果判定ユニット１０４に送られる（Ｓ１０２）。これにより、その選択信号によって指定されるウェイに、その決定されたリプレースフラグＲが書き込まれる（Ｓ２０３）。また、付属のタグの更新等が行われる（Ｓ１０３）。
【００７１】
これにより、図６に示した表に従ってリプレースフラグＲを更新することによって、最新にヒットしたウェイができるだけ遅く置換対象として選択されるようになる。
【００７２】
また、上記実施形態においては、いずれのウェイにもヒットしない場合（Ｓ１０１）に、置換対象ウェイ選択部１０７による置換対象ウェイ選択処理（Ｓ１０６からＳ１０９）が行われるように説明したが、本発明はこれに限定されない。例えば、置換対象ウェイ選択部１０７は、分岐履歴検索結果判定ユニット１０４によって正しく分岐予測できなかったと判定された場合に、置換対象ウェイ選択部１０７による置換対象ウェイ選択処理（Ｓ１０６からＳ１０９）を行うようにしてもよい。
【００７３】
また、上記実施形態においては、分岐履歴検索結果判定ユニット１０４を有する記憶装置１００について説明したが、本発明はこれに限定されない。例えば、記憶装置１００は、分岐履歴検索結果判定ユニット１０４を有さないキャッシュメモリ装置（例えば、主記憶装置とプロセッサとの間に配置されるキャッシュメモリ装置）であってもよい。
【００７４】
また、上記実施形態においては、Ｎ＝４の４ウェイ・セット・アソシアティブ方式の記憶装置について説明したが、本発明はこれに限定されない。例えば、Ｎは、２、４、８、１６、３２・・・等の２のｎ乗ウェイにも拡張することが可能である。また、それ以外の整数ウェイであってもこれに近い形で実現可能である。
【００７５】
［その他］　本発明は、以下のように特定することができる。
（付記１）　少なくともリプレースフラグと所定データとを含む複数のエントリを有するＮ個（Ｎは２以上の整数）のウェイと、前記Ｎ個のウェイそれぞれから、同一アドレスによって指定されるエントリに含まれるリプレースフラグを取得する取得部と、前記取得部によって取得されたリプレースフラグに基づいて、置換対象のウェイを選択する選択部とを備える、セットアソシアティブ方式の記憶装置。（１）
（付記２）　前記同一アドレスによって指定されるエントリのうち前記選択部によって選択されたウェイが有するエントリに含まれる所定データを更新する所定データ更新部を備える、付記１に記載のセットアソシアティブ方式の記憶装置。（２）
（付記３）　前記所定データ更新部によって最新に更新された所定データを含むエントリを有するウェイができるだけ遅く選択されるように、前記同一アドレスによって指定されるエントリのうち前記選択部によって選択されたウェイが有するエントリに含まれるリプレースフラグを更新するリプレースフラグ更新部をさらに備える、付記２に記載のセットアソシアティブ方式の記憶装置。（３）
（付記４）　前記リプレースフラグ更新部は、１ビットのリプレースフラグに基づいて前記更新を行う、付記３に記載のセットアソシアティブ方式の記憶装置。（４）
（付記５）　前記同一アドレスによって指定されるエントリの全てが有効か否かを判定する判定部をさらに備え、前記選択部は、前記判定部によって少なくとも一つのエントリが無効であると判定された場合に、リプレースフラグとは無関係に、その無効なエントリを有するウェイを選択する、付記１に記載のセットアソシアティブ方式の記憶装置。（５）
（付記６）　前記各エントリはさらに、バリッドフラグを含み、前記取得部は、前記Ｎ個のウェイそれぞれから、前記同一アドレスによって指定されるエントリに含まれるバリッドフラグを取得し、前記判定部は、前記取得部によって取得されたバリッドフラグに基づいて、エントリの全てが有効か否かを判定する、付記５に記載のセットアソシアティブ方式の記憶装置。（６）
（付記７）　前記同一アドレスに基づいて分岐予測を行う分岐予測部をさらに備え、前記選択部は、前記分岐予測部が分岐すると予測しなかった場合に、置換対象のウェイを選択する、付記１に記載のセットアソシアティブ方式の記憶装置。（７）
（付記８）　少なくともリプレースフラグと所定データとを含む複数のエントリを有するＮ個（Ｎは２以上の整数）のウェイと、前記Ｎ個のウェイそれぞれから、同一アドレスによって指定されるエントリに含まれるリプレースフラグを取得する取得部と、前記取得部によって取得されたリプレースフラグに基づいて、置換対象のウェイを選択する選択部とを備える、セットアソシアティブ方式のキャッシュメモリ装置。（８）
（付記９）　前記同一アドレスによって指定されるエントリのうち前記選択部によって選択されたウェイが有するエントリに含まれる所定データを更新する所定データ更新部を備える、付記８に記載のセットアソシアティブ方式のキャッシュメモリ装置。（９）
（付記１０）　前記所定データ更新部によって最新に更新された所定データを含むエントリを有するウェイができるだけ遅く選択されるように、前記同一アドレスによって指定されるエントリのうち前記選択部によって選択されたウェイが有するエントリに含まれるリプレースフラグを更新するリプレースフラグ更新部をさらに備える、付記９に記載のセットアソシアティブ方式のキャッシュメモリ装置。（１０）
（付記１１）　前記リプレースフラグ更新部は、１ビットのリプレースフラグに基づいて前記更新を行う、付記１０に記載のセットアソシアティブ方式のキャッシュメモリ装置。
（付記１２）　前記同一アドレスによって指定されるエントリの全てが有効か否かを判定する判定部をさらに備え、前記選択部は、前記判定部によって少なくとも一つのエントリが無効であると判定された場合に、リプレースフラグとは無関係に、その無効なエントリを有するウェイを選択する、付記８に記載のセットアソシアティブ方式のキャッシュメモリ装置。
（付記１３）　前記各エントリはさらに、バリッドフラグを含み、前記取得部は、前記Ｎ個のウェイそれぞれから、前記同一アドレスによって指定されるエントリに含まれるバリッドフラグを取得し、前記判定部は、前記取得部によって取得されたバリッドフラグに基づいて、エントリの全てが有効か否かを判定する、付記１２に記載のセットアソシアティブ方式のキャッシュメモリ装置。
（付記１４）　少なくともリプレースフラグと所定データとを含む複数のエントリを有するＮ個（Ｎは２以上の整数）のウェイを有するセットアソシアティブ方式の記憶装置において置換対象ウェイを選択する方法であって、前記Ｎ個のウェイそれぞれから、同一アドレスによって指定されるエントリに含まれるリプレースフラグを取得するステップと、前記取得部によって取得されたリプレースフラグに基づいて、置換対象のウェイを選択するステップとを備える。
【００７６】
本発明は、その精神または主要な特徴から逸脱することなく、他の様々な形で実施することができる。このため、上記の実施形態は、あらゆる点で単なる例示にすぎず、限定的に解釈されるものではない。
【００７７】
【発明の効果】
以上説明したように、本発明によれば、Ｎ個のウェイを持つセットアソシアティブ方式の記憶装置において、登録・置換が行われるエントリを有するウェイの選択を、ＬＲＵ法よりもはるかに低コストで、かつ、ＬＲＵに近い性能を出しつつ行うことが可能になる。
【図面の簡単な説明】
【図１】本発明の実施形態である４ウェイ・セット・アソシアティブ方式の記憶装置の概略構成を説明するための図である。
【図２】本発明の実施形態である４ウェイ・セット・アソシアティブ方式の記憶装置の概略構成を説明するための図である。
【図３】本発明の実施形態である４ウェイ・セット・アソシアティブ方式の記憶装置が有するウェイ（分岐履歴記憶装置）の構成を説明するための図である。
【図４】本発明の実施形態である４ウェイ・セット・アソシアティブ方式の記憶装置が有する置換対象ウェイ選択部の概略構成を説明するための図である。
【図５】本発明の実施形態である４ウェイ・セット・アソシアティブ方式の記憶装置において、全てのバリッドフラグが有効の場合に選択される置換対象のウェイを説明するための図である。
【図６】本発明の実施形態である４ウェイ・セット・アソシアティブ方式の記憶装置において、少なくとも一つのバリッドフラグが無効の場合に反転されるリプレースフラグを説明するための図である。
【図７】本発明の実施形態である４ウェイ・セット・アソシアティブ方式の記憶装置が有する置換対象ウェイ選択部を実現する論理回路を説明するための図である。
【図８】本発明の実施形態である４ウェイ・セット・アソシアティブ方式の記憶装置が有する置換対象ウェイ選択部を実現する論理回路を説明するための図である。
【図９】本発明の実施形態である４ウェイ・セット・アソシアティブ方式の記憶装置が有する置換対象ウェイ選択部を実現する論理回路を説明するための図である。
【図１０】本発明の実施形態である４ウェイ・セット・アソシアティブ方式の記憶装置が有する置換対象ウェイ選択部を実現する論理回路を説明するための図である。
【図１１】本発明の実施形態である４ウェイ・セット・アソシアティブ方式の記憶装置が有する置換対象ウェイ選択部を実現する論理回路を説明するための図である。
【図１２】本発明の実施形態である４ウェイ・セット・アソシアティブ方式の記憶装置が有する置換対象ウェイ選択部を実現する論理回路を説明するための図である。
【図１３】本発明の実施形態である４ウェイ・セット・アソシアティブ方式の記憶装置の動作を説明するためのフローチャートである。
【図１４】本発明の実施形態の変形例である４ウェイ・セット・アソシアティブ方式の記憶装置の動作を説明するためのフローチャートである。
【図１５】本発明の実施形態である４ウェイ・セット・アソシアティブ方式の記憶装置の制御対象を説明するための図である。
【図１６】本発明の実施形態である４ウェイ・セット・アソシアティブ方式の記憶装置の動作を説明するためのフローチャートである。
【符号の説明】
１００　　　記憶装置
１０１　　　アドレス生成ユニット
１０２　　　キャッシュメモリ
１０３　　　デコーダ
１０４　　　分岐履歴検索結果判定ユニット
１０５　　　等価性判定部
１０６　　　ヒットウェイ選択部
１０７　　　置換対象ウェイ選択部
１０８　　　更新制御装置
Ｒ　　　　　リプレースフラグ
Ｖ　　　　　バリッドフラグ
【図１】
2004038298.tif 000003
【図２】
2004038298.tif 000004
【図３】
2004038298.tif 000005
【図４】
2004038298.tif 000006
【図５】
2004038298.tif 000007
【図６】
2004038298.tif 000008
【図７】
2004038298.tif 000009
【図８】
2004038298.tif 000010
【図９】
2004038298.tif 000011
【図１０】
2004038298.tif 000012
【図１１】
2004038298.tif 000013
【図１２】
2004038298.tif 000014
【図１３】
2004038298.tif 000015
【図１４】
2004038298.tif 000016
【図１５】
2004038298.tif 000017
【図１６】
2004038298.tif 000018