(57)【要約】本発明により、マルチコアまたはマルチスレッドプロセッサからのメモリアクセスに対するキャッシュヒット率が向上する。キャッシュメモリは、キャッシュされたブロックを記憶するデータアレイと、キャッシュされたブロックのアドレスを記憶する第１のアドレスアレイと、キャッシュミスが発生した場合にデータアレイから追い出される第１のブロックのアドレスを記憶する第２のアドレスアレイと、キャッシュミスをした第２のブロックをメモリから読み出してデータアレイに書き込むまでの間に、第２のアドレスアレイに記憶されたアドレスがキャッシュヒットした場合には、データアレイに記憶された第１のブロックをキャッシュヒットしたブロックとしてプロセッサに送信する制御部と、を有する。
2010087310.tif 000002
【特許請求の範囲】
【請求項１】
キャッシュされたブロックを記憶するデータアレイと、
キャッシュされたブロックのアドレスを記憶する第１のアドレスアレイと、
キャッシュミスが発生した場合に前記データアレイから追い出される第１のブロックのアドレスを記憶する第２のアドレスアレイと、
キャッシュミスをした第２のブロックをメモリから読み出して前記データアレイに書き込むまでの間に、前記第２のアドレスアレイによって記憶されたアドレスがキャッシュヒットした場合には、前記データアレイに記憶された前記第１のブロックをキャッシュヒットしたブロックとしてプロセッサに送信する制御部と、を備えていることを特徴とするキャッシュメモリ。
【請求項２】
前記制御部は、前記第２のブロックを前記データアレイに書き込む際に、前記第２のアドレスアレイに記憶された前記第１のブロックのアドレスを無効化することを特徴とする、請求項１に記載のキャッシュメモリ。
【請求項３】
前記第２のアドレスアレイは、前記第１のブロックが記憶されているウェイの識別子を記憶することを特徴とする、請求項１又は２に記載のキャッシュメモリ。
【請求項４】
前記第２のアドレスアレイは、前記第１のブロックがキャッシュヒットして書き換えられたか否かを示すフラグを記憶することを特徴とする、請求項１乃至３のいずれか１項に記載のキャッシュメモリ。
【請求項５】
前記制御部は、前記第２のブロックをメモリから読み出して前記データアレイに書き込む前に、前記第２のアドレスアレイに記憶されたフラグを参照し、前記第１のブロックが書き換えられていた場合には、前記第１のブロックをメモリに書き戻すことを特徴とする、請求項４に記載のキャッシュメモリ。
【請求項６】
キャッシュミスが発生した場合にデータアレイから追い出されるブロックのアドレスを格納するアドレスアレイと、
キャッシュミスをしたブロックをメモリから読み出して前記データアレイに格納するまでの間に、前記アドレスアレイに格納されたアドレスがキャッシュヒットした場合には、前記データアレイに格納されたブロックをキャッシュヒットしたブロックとしてプロセッサに送信する制御部と、を備えていることを特徴とするキャッシュメモリ。
【請求項７】
請求項１乃至６のいずれか１項に記載のキャッシュメモリを備えていることを特徴とする電子計算機。
【請求項８】
マルチコア又はマルチスレッドプロセッサを備えていることを特徴とする、請求項７に記載の電子計算機。
【請求項９】
キャッシュされたブロックを記憶するデータアレイと、キャッシュされたブロックのアドレスを記憶する第１のアドレスアレイと、第２のアドレスアレイとを備えたキャッシュメモリの制御方法であって、
キャッシュミスが発生した場合に前記データアレイから追い出される第１のブロックのアドレスを前記第２のアドレスアレイに記憶する工程と、
キャッシュミスをした第２のブロックをメモリから読み出して前記データアレイに書き込むまでの間に、前記第２のアドレスアレイに記憶されたアドレスがキャッシュヒットした場合には、前記データアレイに記憶された前記第１のブロックをキャッシュヒットしたブロックとしてプロセッサに送信する工程と、を含むことを特徴とするキャッシュメモリの制御方法。
【請求項１０】
前記第２のブロックを前記データアレイに書き込む際に、前記第２のアドレスアレイに記憶された前記第１のブロックのアドレスを無効化する工程をさらに含むことを特徴とする、請求項９に記載のキャッシュメモリの制御方法。
【請求項１１】
前記第１のブロックが記憶されているウェイの識別子を、前記第２のアドレスアレイに記憶させる工程を含むことを特徴とする、請求項９又は１０に記載のキャッシュメモリの制御方法。
【請求項１２】
前記第１のブロックがキャッシュヒットして書き換えられたか否かを示すフラグを、前記第２のアドレスアレイに記憶させる工程を含むことを特徴とする、請求項９乃至１１のいずれか１項に記載のキャッシュメモリの制御方法。
【請求項１３】
前記第２のブロックをメモリから読み出して前記データアレイに書き込む前に、前記第２のアドレスアレイに記憶されたフラグを参照し、前記第１のブロックが書き換えられていた場合には、前記第１のブロックをメモリに書き戻す工程を含むことを特徴とする、請求項１２に記載のキャッシュメモリの制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願についての記載）
本発明は、日本国特許出願：特願２００９−０１６２２４号（２００９年１月２８日出願）の優先権主張に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。【０００２】
本発明は、キャッシュメモリおよびその制御方法に関し、特に、マルチコアまたはマルチスレッドプロセッサからアクセスされるキャッシュメモリおよびその制御方法に関する。
【背景技術】
【０００３】
キャッシュメモリは、１度アクセスされたデータは再度アクセスされるというアクセスの時間的な局所性、および、１度アクセスされたデータの近傍のデータはアクセスされる可能性が高いというアクセスの空間的な局所性に基づいて、コンピュータのメモリアクセス性能を向上させる。しかしながら、キャッシュメモリの容量は限られていることから、限られた容量を効率的に用いてキャッシュヒット率を向上させる必要がある。キャッシュされるブロックがキャッシュメモリのどこに格納されるかは、キャッシュメモリのマッピング方式に応じて異なる。【０００４】
フルアソシアティブ方式においては、各ブロックはキャッシュメモリの任意の場所に格納することができるため、キャッシュメモリを効率良く使用することができる。しかしながら、フルアソシアティブ方式では、キャッシュにブロックがあるか否かを検索するとき、キャッシュ内の全ブロックを検索の対象にしなければならず、検索に時間を要する。【０００５】
ダイレクトマップ方式は、キャッシュメモリ内の検索が最も簡単な方式である。ダイレクトマップ方式では、各ブロックが格納される場所はキャッシュメモリ内の予め決められた箇所に限られる。しかしながら、ダイレクトマップ方式では、各ブロックが格納される場所が固定されているため、同じ場所に格納される複数のブロックを同時にキャッシュメモリにキャッシュすることができない。【０００６】
Ｎウェイセットアソシアティブ方式は、これら２つの方式の中間に位置づけられる。Ｎウェイセットアソシアティブ方式では、あるブロックを格納するキャッシュメモリ内の場所がＮ個ある。すなわち、キャッシュメモリの同じ場所に格納されるＮ個のブロックを同時にキャッシュすることができる。また、キャッシュ内にブロックがキャッシュされているか否かを検索する場合には、Ｎ箇所を検索すればよい。【０００７】
特許文献１において、キャッシュミス時に他のブロックをキャッシュするために置き換えの対象とされ、キャッシュメモリから追い出されたブロックを格納するヴィティムキャッシュメモリが記載されている。特許文献１のヴィクティムキャッシュはフルアソシアティブ方式の小容量（数ブロック）のキャッシュで、キャッシュメモリから追い出されたブロックをキャッシュする。ヴィクティムキャッシュメモリ内のブロックがキャッシュヒットした場合は、追い出されたブロックとヒットしたブロックとを、キャッシュメモリとの間でスワップ（交換）する。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平４−２７０４３１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
なお、上記の特許文献の開示を、本書に引用をもって繰り込むものとする。【００１０】
特許文献１に記載されたヴィクティムキャッシュメモリは数ブロックの容量しかないため、ヴィクティムキャッシュメモリ内にブロックが留まっている時間は短いと考えられる。特許文献１に記載された技術は、一度キャッシュされ追い出されたデータが追い出された直後に再びアクセスされる可能性が高いことを利用してキャッシュメモリのヒット率を向上させる技術である。【００１１】
一方、ＣＰＵにおけるマルチコア技術およびマルチスレッド技術の進歩により、同時に複数のスレッドによるメモリアクセスがキャッシュメモリに対して生じ得る。これらのメモリアクセスは複数の独立したスレッドによるものであり、因果関係がなく、同時に複数のキャッシュミスが発生することになる。したがって、シングルコア、シングルスレッドの場合と比較して、同時に発生しているキャッシュミスが多くなり、キャッシュミスによるメモリアクセスも同時に複数発行される。【００１２】
特許文献１に記載されたヴィクティムキャッシュメモリ技術では、同時に複数のキャッシュミスが発生するようなマルチコア、マルチスレッドのＣＰＵからのメモリアクセスを効率よく処理することができない。なぜなら、ヴィクティムキャッシュメモリは小容量（数ブロック）のフルアソシアティブ方式のキャッシュメモリであり、同時に複数のキャッシュミスが発生すると、キャッシュミスしたブロックの容量がヴィクティムキャッシュメモリの容量を超えてしまうからである。また、複数のキャッシュミスに対応するために、ヴィクティムキャッシュメモリの容量を大きくした場合にはフルアソシアティブ方式を採用することが困難になるためである。【００１３】
そこで、マルチコアまたはマルチスレッドプロセッサからのメモリアクセスに対するキャッスヒット率を向上させることが課題となる。本発明の目的は、かかる課題を解決するためのキャッシュメモリおよびその制御方法を提供することにある。
【課題を解決するための手段】
【００１４】
本発明の第１の視点に係るキャッシュメモリは、
キャッシュされたブロックを記憶するデータアレイと、
キャッシュされたブロックのアドレスを記憶する第１のアドレスアレイと、
キャッシュミスが発生した場合にデータアレイから追い出される第１のブロックのアドレスを記憶する第２のアドレスアレイと、
キャッシュミスをした第２のブロックをメモリから読み出してデータアレイに書き込むまでの間に、第２のアドレスアレイに格納記憶されたアドレスがキャッシュヒットした場合には、データアレイに記憶された第１のブロックをキャッシュヒットしたブロックとしてプロセッサに送信する制御部と、を有する。【００１５】
本発明の第２の視点に係るキャッシュメモリは、
キャッシュミスが発生した場合にデータアレイから追い出されるブロックのアドレスを格納するアドレスアレイと、
キャッシュミスをしたブロックをメモリから読み出して前記データアレイに格納するまでの間に、前記アドレスアレイに格納されたアドレスがキャッシュヒットした場合には、前記データアレイに格納されたブロックをキャッシュヒットしたブロックとしてプロセッサに送信する制御部と、を有する。【００１６】
本発明の第３の視点に係るキャッシュメモリの制御方法は、
キャッシュされたブロックを記憶するデータアレイと、キャッシュされたブロックのアドレスを記憶する第１のアドレスアレイと、第２のアドレスアレイとを備えたキャッシュメモリの制御方法であって、
キャッシュミスが発生した場合にデータアレイから追い出される第１のブロックのアドレスを第２のアドレスアレイに記憶する工程と、
キャッシュミスをした第２のブロックをメモリから読み出してデータアレイに書き込むまでの間に、第２のアドレスアレイに記憶されたアドレスがキャッシュヒットした場合には、データアレイに記憶された第１のブロックをキャッシュヒットしたブロックとしてプロセッサに送信する工程と、を含む。
【発明の効果】
【００１７】
本発明に係るキャッシュメモリおよびその制御方法によると、マルチコアまたはマルチスレッドプロセッサからのメモリアクセスに対するキャッシュヒット率を向上させることができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の実施形態に係るキャッシュメモリの構成を示すブロック図である。
【図２】本発明の第１の実施例のキャッシュメモリの構成を示す図である。
【図３】本発明の第１および第２の実施例のキャッシュメモリの状態ビット列を示す図である。
【図４】本発明の第１の実施例のキャッシュメモリの動作を表すフローチャートである。
【図５】本発明の第１の実施例のキャッシュメモリのブロックの置き換えとブロックの読み出し動作を表すフローチャートである。
【図６】本発明の第２の実施例のキャッシュメモリの構成を示す図である。
【図７】本発明の第２の実施例のキャッシュメモリの動作を表すフローチャートである。
【図８】本発明の第２の実施例のキャッシュメモリのブロックの置き換えとブロックの読み出し動作を表すフローチャートである。
【図９】本発明の第２の実施例のキャッシュメモリの動作を説明するための図である。
【図１０】本発明の第２の実施例のキャッシュメモリの動作を説明するための図である。
【図１１】本発明の第２の実施例のキャッシュメモリの動作を説明するための図である。
【図１２】本発明の第２の実施例のキャッシュメモリの動作を説明するための図である。
【図１３】本発明の第２の実施例のキャッシュメモリの動作を説明するための図である。
【図１４】本発明の第２の実施例のキャッシュメモリの動作を説明するための図である。
【図１５】本発明の第２の実施例のキャッシュメモリの動作を説明するための図である。
【発明を実施するための形態】
【００１９】
本発明の実施形態に係るキャッシュメモリについて図面を参照して説明する。図１は、本実施形態のキャッシュメモリの構成を示すブロック図である。図１を参照すると、キャッシュメモリ１０は、アドレスアレイＡ１１、データアレイ１２、アドレスアレイＢ１３、および制御部１４を有する。また、キャッシュメモリ１０は、メモリ２０およびプロセッサ３０に接続されている。
【００２０】
第１のアドレスアレイＡ１１は、キャッシュしたブロックのアドレスを記憶する。データアレイ１２は、キャッシュしたブロックを記憶する。第２のアドレスアレイＢ１３は、キャッシュミスが発生した場合にキャッシュメモリ１０から追い出されるブロックである第１のブロックのアドレスを記憶する。
【００２１】
制御部１４は、キャッシュミスをしたブロックである第２のブロックをメモリ２０から読み出してデータアレイ１２に書き込むまでの間に、アドレスアレイＢ１３によって記憶されたアドレスがキャッシュヒットした場合には、データアレイ１２によって記憶された第１のブロックをキャッシュヒットしたブロックとしてプロセッサ３０に送信する。
【００２２】
本実施形態に係るキャッシュメモリによると、キャッシュミスによって追い出されるべきブロック（すなわち、第１のブロック）を、キャッシュミスしたブロック（すなわち、第２のブロック）をメモリ２０から読み出してキャッシュメモリ１０のデータアレイ１２に格納するまでの間、キャッシュヒットとしたものとして処理することができる。したがって、キャッシュミスによって追い出されるべきブロックに対する、後続のアクセスを一定時間キャッシュヒットさせて、キャッシュヒット率を向上させることができる。また、本実施形態に係るキャッシュメモリによると、同時に多数のキャッシュミスが発生し、追い出されるべきブロックが多数あっても一定時間キャッシュヒットさせることができる。なお、キャッシュミスしたブロックとは、キャッシュメモリ１０のデータアレイ１２に格納されていないブロックであって、メモリ２０から読み出してデータアレイ１２に格納すべきブロックをいう。
【００２３】
制御部１４は、メモリ２０から読み出した第２のブロックをデータアレイ１２に書き込む際に、アドレスアレイＢ１３によって記憶された、第１のブロックアドレスを無効化することが好ましい。データアレイ１２において、第１のブロックが第２のブロックによって置き換えられ、すでに、第１のブロックがキャッシュメモリ１０にないことを、制御部１４が認識することができるようにするためである。
【００２４】
さらに、アドレスアレイＢ１３は、第１のブロックが記憶されているデータアレイ１２のウェイの識別子を記憶することが好ましい。本実施形態に係るキャッシュメモリおよびその制御方法を、Ｎウェイセットアソシアティブ方式に拡張することができるからである。
【００２５】
また、アドレスアレイＢ１３は、第１のブロックがキャッシュヒットして書き換えられたか否かを示すフラグを記憶することが好ましい。このとき、制御部１４は、第２のブロックをメモリ２０から読み出してデータアレイ１２に書き込む前に、アドレスアレイＢ１３に記憶されたフラグを参照し、第１のブロックが書き換えられていた場合には、第１のブロックをメモリ２０に書き戻すことが好ましい。キャッシュコヒーレンシ（キャッシュの一貫性）を保つことができるからである。
【００２６】
さらに、電子計算機は、上記のキャッシュメモリ１０を備えることが好ましい。また、電子計算機は、マルチコア又はマルチスレッドのプロセッサを備えるものであってもよい。本実施形態に係るキャッシュメモリを設けることにより、マルチコアまたはマルチスレッドのプロセッサを備えた電子計算機において、メモリアクセスに対するキャッシュヒット率を向上させることができるからである。
【実施例１】
【００２７】
本発明の第１の実施例に係るキャッシュメモリついて図面を参照して詳細に説明する。【００２８】
図２を参照すると、本発明の第１の実施例のキャッシュメモリは、アドレスレジスタ１０１、アドレスアレイ１０２、追い出しブロック用アドレスアレイ１０３、データアレイ１０４、比較器Ａ１０５、比較器Ｂ１０６、及び制御部１２０を有する。【００２９】
アドレスアレイ１０２は、２のｎ乗のエントリを持つメモリである。１エントリは、ブロックアドレスの一部であるアドレスの上位ｍビット１０７とそのブロックの状態を表す状態ビット列１０８を含む。【００３０】
追い出しブロック用アドレスアレイ１０３は、２のｎ乗のエントリを有するメモリである。各エントリは、ブロックアドレスの一部であるアドレスの上位ｍビット１０９、およびそのブロックの状態を表す状態ビット列１１０を含む。【００３１】
データアレイ１０４は、２のｎ乗のエントリを有するメモリである。各エントリは、２のｋ乗バイトのブロック１１１を格納している。【００３２】
比較器Ａ１０５は、アドレスレジスタ１０１のｎビット１１２をオフセット１１３としてアクセスしたアドレスアレイ１０２のエントリの中の上位ｍビット１０７のアドレスと、アドレスレジスタの上位ｍビット１１４とを比較する。一致した場合には、すでにブロックのエントリがキャッシュメモリ上にあることになる。【００３３】
比較器Ｂ１０６は、アドレスレジスタ１０１のｎビット１１２をオフセット１１３としてアクセスした追い出しブロック用アドレスアレイ１０３のエントリの中の上位ｍビット１０９のアドレスと、アドレスレジスタの上位ｍビット１１４とを比較する。一致した場合には、すでにブロックのエントリがキャッシュメモリ上にあることになる。【００３４】
制御部１２０は、比較器Ａ１０５からの比較結果Ａ１１５、比較器Ｂ１０６からの比較結果Ｂ１１６と、ＣＰＵからの命令種別（ｌｏａｄ、ｓｔｏｒｅ）１１７、読み出したアドレスアレイの状態ビット列１０８と追い出しブロック用アドレスアレイの状態ビット列１１０に基づいてキャッシュメモリを制御する。【００３５】
以下の説明では、アドレスレジスタ１０１に格納されるアドレスは６４ビットとし、ｋ＝６、すなわちブロックのサイズを６４バイト、ｎ＝１０、すなわちアドレスアレイ１０２、追い出しブロック用アドレスアレイ１０３、データアレイ１０４のエントリ数を１０２４、ｍ＝４８とする。また、本実施例のキャッシュメモリは、一例として、ダイレクトマップ方式のキャッシュメモリであるものとする。【００３６】
次に、図２のキャッシュメモリの動作を説明する。キャッシュメモリへのアクセスがあった場合には、そのアドレスがアドレスレジスタ１０１に設定される。アドレスは論理アドレスであってもよいし、物理アドレスであってもよい。ここでは、一例として、アドレスは、何らかのアドレス変換の手段により、仮想アドレスから変換された物理アドレスであるものとする。【００３７】
ブロックのサイズは６４バイトであるから、アドレスレジスタ１０１の下位６（ｋ）ビット１１８はブロック内のアドレスとなる。その上の１０（ｎ）ビット１１２をオフセット１１３として使用して、アドレスアレイ１０２と追い出し用アドレスアレイ１０３の中のエントリを読み出す。【００３８】
比較器Ａ１０５は、読み出したエントリの中のアドレスの上位４８（ｍ）ビット１０７と、アドレスレジスタ１０１の上位４８（ｍ）ビット１１４とを比較し、比較器Ｂ１０６は、アドレスの上位４８（ｍ）ビット１０９とアドレスレジスタ１０１の上位４８（ｍ）ビット１１４とを比較し、そのブロックのエントリがすでにキャッシュメモリにあるか否かを判定する。【００３９】
比較結果Ａ１１５、比較結果Ｂ１１６は、命令種別（ｌｏａｄ、ｓｔｏｒｅ）１１７、アドレスアレイ１０２と追い出しブロック用アドレスアレイ１０３から読み出されたエントリ内の状態ビット列１０８、１１０とともに制御部１２０に入力され、キャッシュメモリの動作を決定する。制御部１２０における動作の決定および動作の詳細ついては、後に、動作の説明の箇所で説明する。【００４０】
図３は、図２の状態ビット列１０８、１１０について詳しく説明している。アドレスアレイ１０２の状態３ビット２０１は、３ビットで構成されており、そのうちわけは、アドレスアレイのエントリが有効か否かを示すフラグＶ２０２と、データアレイのブロックが書き換えられたが否かを示すフラグＤ２０３と、アドレスアレイのブロックをメモリから読み出し中であるか否か示すフラグＦ２０４である。【００４１】
アドレスアレイ１０２のエントリが有効である場合にはフラグＶ２０２は１であり、無効である場合にはフラグＶ２０２は０である。ブロックが書き換えられた場合にはフラグＤ２０３は１であり、書き換えられていない場合にはフラグＤ２０３は０である。アドレスアレイのブロックをメモリから読み出し中である場合にはフラグＦ２０４は１であり、読み出し中でない場合にはフラグＦ２０４は０である。【００４２】
追い出しブロック用アドレスアレイ１０３の状態２ビット２０５は、追い出しブロック用アドレスアレイのエントリが有効か否かを示すフラグＶ２０６と、データアレイのブロックが書き換えられたか否かを示すフラグＤ２０７の２ビットを含む。【００４３】
追い出しブロック用アドレスアレイ１０３のエントリが有効である場合にはフラグＶ２０６は１であり、無効である場合にはフラグＶ２０６は０である。ブロックが書き換えられた場合にはフラグＤ２０７は１であり、書き換えられていない場合にはフラグＤ２０７は０である。【００４４】
次に、図２の構成要素と、図３の状態他のビット列を参照しながら、本発明の第１の実施例の動作について詳細に説明する。【００４５】
図４は、図２の制御部１２０での動作の決定と動作について説明しているフローチャートである。【００４６】
図２のアドレスレジスタ１０１にアクセスされたアドレスが格納され、アドレスレジスタ１０１の１０（ｎ）ビット１１２によって、アドレスアレイ１０２と追い出しブロック用アドレスアレイ１０３、データアレイ１０４のエントリがアクセスされた状態になっている。【００４７】
この時点における、制御部１２０による動作の決定とその動作とについて説明する。【００４８】
制御部１２０は、ＣＰＵからの命令種別１１７によって行うべき処理を判定する（ステップＳ３０１）。【００４９】
まず、命令種別１１７がｓｔｏｒｅである場合（ステップＳ３０１のｓｔｏｒｅ）、制御部１２０は、キャッシュヒットしたか否かを判定する（ステップＳ３０３）。制御部１２０は、比較器Ａ１０５と比較器Ｂ１０６からの比較結果Ａ１１５および比較結果Ｂ１１６、アドレスアレイ１０２および追い出しブロック用アドレスアレイ１０３の状態ビット列１０８、１１０により、アクセスしたデータがキャッシュヒットしているか否かを判定する（ステップＳ３０３）。比較結果Ａ１１５が一致しており状態ビット列１０８のフラグＶ２０２が１である場合、または、比較結果Ｂ１１６が一致しており状態ビット列１１０のフラグＶ２０６が１である場合には、制御部１２０は、キャッシュヒットしたものと判定する（ステップＳ３０３のＹｅｓ）。【００５０】
一方、比較結果Ａ１１５が一致しない、または、状態ビット列１０８のフラグＶ２０２が０である場合において、比較結果Ｂ１１６が一致しない、または、状態ビット列１１０のフラグＶ２０６が０であるときには、制御部１２０は、アクセスしたデータがキャッシュミスしたものと判定する（ステップＳ３０３のＮｏ）。【００５１】
キャッシュヒットした場合には（ステップＳ３０３のＹｅｓ）、制御部１２０は、比較結果Ａ１１５が一致したか否か、および、比較結果Ｂ１１６が一致したか否か基づいて、キャッシュヒットしたのが通常のアドレスアレイ１０２および追い出しブロック用のアドレスアレイ１０３のいずれであるのかを判定する（ステップＳ３２９）。【００５２】
通常のアドレスアレイがヒットした場合には（ステップＳ３２９のＮｏ）、制御部１２０は、そのブロックが読み出し中であるか否かを、状態ビット列１０８のフラグＦ２０４に基づいて判定する（ステップＳ３２３）。フラグＦ２０４が１であり、ブロックの読み出し中である場合には（ステップＳ３２３のＹｅｓ）、読み出しが終了するまで待つ。フラグＦ２０４が０であり、ブロックの読み出し中でない場合には（ステップＳ３２３のＮｏ）、制御部１２０は、下位６（ｋ）ビットのデータに基づいて、そのブロックのデータ内のワードを特定し、そのワードに対して、書き込みデータを書き込み（ステップＳ３０６）、状態ビット列１０８のフラグＤ２０３を１にする（ステップＳ３０７）。【００５３】
追い出しブロック用アドレスアレイ１０３がヒットした場合には（ステップ３２９のＹｅｓ）、制御部１２０は、下位６（ｋ）ビットのデータに基づいて、そのブロックのデータ内のワードを特定し、そのワードに対して、書き込みデータを書き込み（ステップＳ３３２）、状態ビット列１１０のフラグＤ２０７を１にする（ステップＳ３３３）。【００５４】
キャッシュミスした場合には（ステップ３０３のＮｏ）、制御部１２０は、キャッシュブロックの置き換えが発生するか否かを判定する（ステップＳ３０８）。すでに、そのエントリを使用しているブロックがある（状態ビット列１０８のフラグＶ２０２が１である）場合には、制御部１２０は、置き換えが発生するものと判定する（ステップ３０８のＹｅｓ）。一方、そのエントリが空いている（状態ビット列１０８のフラグＶ２０２が０である）場合には、制御部１２０は、置き換えが発生しないものと判定する（ステップ３０８のＮｏ）。【００５５】
ブロックの置き換えが発生しない場合には（ステップＳ３０８のＮｏ）、アドレスアレイ１０２の上位ｍビットにアドレスレジスタ１０１の上位ｍビット１１４を格納し、状態ビット列１０８のフラグＶ２０２とフラグＦ２０４を１にしてメモリからブロックを読み出す。そして、読み出されたブロックが到着したら、データアレイ１０４のブロック１１１に書き込み、アドレスアレイ１０２の状態ビット列１０８のフラグＦ２０４を０にする（ステップＳ３１１）。そして、ブロック１１１にデータを書き込み（ステップＳ３０６）、アドレスアレイ１０２の状態ビット列１０８のフラグＤ２０３を１にする（ステップＳ３０７）。【００５６】
ブロックの置き換えが発生する場合（ステップＳ３０９）は、ブロックの置き換えとブロックの読み出し（ステップＳ３１２）を行う。ステップＳ３１２については後に図５を使って説明する。ステップＳ３１２の後、ブロックにデータを書き込み（ステップＳ３０６）、アドレスアレイ１０２の状態ビット列１０８のフラグＤ２０３を１にする（ステップＳ３０７）。【００５７】
次に、命令種別１１７がｌｏａｄの場合（ステップＳ３０１のｌｏａｄ）、制御部１２０は、キャッシュヒットしたか否かを判定する（ステップＳ３１４）。制御部１２０は、比較器Ａ１０５と比較器Ｂ１０６からの比較結果Ａ１１５と比較結果Ｂ１１６と、アドレスアレイ１０２と追い出しブロック用アドレスアレイ１０３の状態ビット列１０８、１１０により、アクセスしたデータがキャッシュヒットしているか否かを判定する（ステップＳ３１４）。【００５８】
比較結果Ａ１１５が一致し、状態ビット列１０８のフラグＶ２０２が１である場合、または、比較結果Ｂ１１６が一致し状態ビット列１１０のフラグＶ２０６が１である場合には、制御部１２０は、キャッシュヒットしたものと判定する（ステップＳ３１４のＹｅｓ）。【００５９】
一方、比較結果Ａ１１５が一致しない、または、状態ビット列１０８のフラグＶ２０２が０である場合において、比較結果Ｂ１１６が一致しない、または、状態ビット列１１０のフラグＶ２０６が０であるときには、制御部１２０は、アクセスしたデータがキャッシュミスしたものと判定する（ステップＳ３１４のＮｏ）。【００６０】
キャッシュヒットした場合には（ステップＳ３１４のＹｅｓ）、制御部１２０は、比較結果Ａ１１５および比較結果Ｂ１１６のいずれが一致したのかに基づいて、キャッシュヒットしたのが通常のアドレスアレイ１０２および追い出しブロック用のアドレスアレイ１０３のいずれであるのかを判定する（ステップＳ３３４）。【００６１】
通常のアドレスアレイがヒットした場合には（ステップＳ３３４のＮｏ）、制御部１２０は、そのブロックが読み出し中であるか否かを、状態ビット列１０８のフラグＦ２０４に基づいて判定する（ステップＳ３２６）。フラグＦ２０４が１であり、ブロックの読み出し中である場合には（ステップＳ３２６のＹｅｓ）、読み出しが終了するまで待つ。一方、フラグＦ２０４が０であり、ブロックの読み出し中でない場合には（ステップＳ３２７のＮｏ）、制御部１２０は、下位６（ｋ）ビットのデータに基づいて、そのブロックのデータ内のワードを特定し、ブロック１１１からそのワードを読み出す（ステップＳ３１７）。【００６２】
追い出しブロック用アドレスアレイ１０３がヒットした場合には（ステップＳ３３６のＹｅｓ）、制御部１２０は、下位６（ｋ）ビットのデータに基づいて、そのブロックのデータ内のワードを特定し、ブロック１１１からそのワードを読み出す（ステップＳ３１７）。【００６３】
キャッシュミスした場合には（ステップＳ３１４のＮｏ）は、制御部１２０は、キャッシュブロックの置き換えが発生するか否かを判定する（ステップＳ３１８）。すでに、そのエントリを使用しているブロックがある（状態ビット列１０８のフラグＶ２０２が１である）場合には、制御部１２０は、置き換えが発生するものと判定する（ステップＳ３１８のＹｅｓ）。一方、そのエントリが空いている（状態ビット列１０８のフラグＶ２０２が０である）場合には、制御部１２０は、置き換えが発生しないものと判定する（ステップＳ３１８のＮｏ）。【００６４】
ブロックの置き換えが発生しない場合には（ステップＳ３１８のＮｏ）、アドレスアレイ１０２の上位ｍビットにアドレスレジスタ１０１の上位ｍビット１１４を格納し、状態ビット列１０８のフラグＶ２０２とフラグＦ２０４を１にしてメモリからブロックを読み出す。そして、読み出されたブロックが到着したら、データアレイ１０４のブロック１１１に書き込み、アドレスアレイ１０２の状態ビット列１０８のフラグＦ２０４を０にする（ステップＳ３２１）。次に、ブロック１１１からデータを読み出す（ステップＳ３１７）。【００６５】
一方、ブロックの置き換えが発生する場合には（ステップ３１８のＹｅｓ）は、ブロックの置き換えとブロックの読み出しを行う（ステップＳ３２２）。ステップＳ３２２については図５を参照して後述する。ステップＳ３２２の後、ブロックからデータを読み出す（ステップＳ３１７）。【００６６】
次に、図５を参照して、図４におけるステップＳ３１２およびＳ３２２について説明する。【００６７】
まず、制御部１２０は、追い出しブロック用アドレスアレイ１０３のエントリが空であるか否かを判定する（ステップＳ４０１）。追い出しブロック用アドレスアレイ１０３の状態ビット列１１０のフラグＶ２０６が０である場合には空であり、１である場合には空ではないものと判定する（ステップＳ４０１）。【００６８】
空でない場合には（ステップＳ４０１のＮｏ）、すでにキャッシュミスが起こり、置き換えのためのメモリからのブロックの読み出しが実行中であるため、その完了を待つ（ステップＳ４０３）。読み出しが完了した後、ステップＳ４０１に戻る。【００６９】
空である場合には（ステップＳ４０１のＹｅｓ）、追い出されるアドレスアレイ１０２の上位ｍビット１０７を追い出しブロック用アドレスアレイ１０３の上位ｍビット１０９にコピーする。そして、状態ビット列１１０のフラグＶ２０６を１とし、フラグＤ２０７を０にする（ステップＳ４０４）。次に、制御部１２０は、状態ビット列１０８のフラグＤ２０３が１であるか０であるかに基づいて、追い出されるブロックが書き換えられていたか否かを判定する（ステップＳ４０５）。【００７０】
書き換えられていた場合に限り（ステップＳ４０５のＹｅｓ）、データアレイ１０４内のブロック１１１をアドレスアレイ１０２の上位ｍビット１０７で示されるアドレスに書き戻す（ステップＳ４０７）。【００７１】
次に、制御部１２０は、アドレスレジスタ１０１の上位ｍビット１１４をアドレスアレイ１０２の上位ｍビット１０７にコピーする。また、アドレスアレイ１０２の状態ビット列１０８のフラグＶ２０２およびフラグＦ２０４を１とし、フラグＤ２０３を０にする（ステップＳ４０９）。そして、メモリに対してキャッシュミスしたブロックの読み出しリクエストを発行する（ステップＳ４１０）。次にメモリからのブロックの到着を待つ（ステップＳ４１１）。【００７２】
ブロックが到着するまでの間、従来なら無効となっている追い出されるブロックが、追い出しブロック用アドレスアレイ上で有効となる。また、追い出されるブロックのデータはデータアレイ１０４のブロック１１１に残っている。【００７３】
次に、読み出したブロックがキャッシュメモリに到着する（ステップＳ４１２）。制御部１２０は、追い出しブロック用アドレスアレイ１０３の状態ビット列１１０のフラグＶ２０６を０とし、無効化する（ステップＳ４１３）。次に、追い出しブロック用アドレスアレイ１０３の状態ビット列１１０のフラグＤ２０７を調べ、書き換えられたか否かを調べる（ステップＳ４１４）。【００７４】
書き換えられている場合に限り（ステップＳ４１４のＹｅｓ）、データアレイ１０４内のブロックを追い出しブロック用アドレスアレイ１０３の上位ｍビット１０９のアドレスに書き戻す（ステップＳ４１６）。次に、メモリから読み出したブロックをデータアレイ１０４のブロック１１１に書き込む。そして、アドレスアレイ１０２の状態ビット列１０８のフラグＦ２０４を０にする（ステップＳ４１８）。
【実施例２】
【００７５】
本発明の第２の実施例について図面を参照して詳細に説明する。図６を参照すると、本発明の第２の実施例のキャッシュメモリは、アドレスレジスタ５０１、アドレスアレイ（ウェイ０）５０２、アドレスアレイ（ウェイ１）５０３、追い出しブロック用アドレスアレイ５０４、データアレイ（ウェイ０）５０５、データアレイ（ウェイ１）５０６、比較器Ａ５０７、比較器Ｂ５０８、比較器Ｃ５０９、制御部５１０を備える。【００７６】
アドレスアレイ５０２、５０３は、２のｎ乗のエントリを有するメモリである。１エントリは、ブロックアドレスの一部であるアドレスの上位ｍビット５１１、５１３と、そのブロックの状態を表す状態ビット列５１２、５１４を含む。【００７７】
追い出しブロック用アドレスアレイ５０４は、２のｎ乗のエントリを有するメモリである。１エントリは、ブロックアドレスの一部であるアドレスの上位ｍビット５１５とそのブロックの状態を表す状態ビット列５１６と、格納したブロックがいずれのウェイのデータアレイに存在するかを示すウェイ番号５１７を含む。【００７８】
データアレイ５０５、５０６は２のｎ乗のエントリをもつメモリである。１エントリは、２のｋ乗バイトのブロック５１８、５１９を格納している。【００７９】
比較器Ａ５０７は、アドレスレジスタ５０１のｎビット５２０をオフセット５２１としてアクセスしたアドレスアレイ５０２のエントリの中の上位ｍビット５１１のアドレスと、アドレスレジスタの上位ｍビット５２２とを比較する。【００８０】
比較器Ｂ５０８は、アドレスレジスタ１０１のｎビット５２０をオフセット５２１としてアクセスしたアドレスアレイ５０３のエントリの中の上位ｍビット５１３のアドレスと、アドレスレジスタの上位ｍビット５２２とを比較する。【００８１】
比較器Ｃ５０９は、アドレスレジスタ１０１のｎビット５２０をオフセット５２１としてアクセスした追い出しブロック用アドレスアレイ５０４のエントリの中の上位ｍビット５１５のアドレスと、アドレスレジスタの上位ｍビット５２２とを比較する。【００８２】
制御部５１０は、比較器Ａ５０７からの比較結果Ａ５２３、比較器Ｂ５０８からの比較結果Ｂ５２４、比較器Ｃ５０９からの比較結果Ｃ５２５と、ＣＰＵからの命令種別（ｌｏａｄ、ｓｔｏｒｅ）５２８、読み出したアドレスアレイ５０２、５０３の状態ビット列５１２、５１４と追い出しブロック用アドレスアレイ５０４の状態ビット列５１６とウェイ番号５１７に基づいてキャッシュメモリの制御を行う。【００８３】
図６には図示していないものの、置き換え対象のウェイを決定するため、使われていない時間が最も長い（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ、ＬＲＵ）ウェイを示す情報が各カラムに設けられる。かかる情報に基づいて、置き換えるべきウェイが選択される。【００８４】
以下の説明では、アドレスレジスタ５０１に格納されるアドレスは６４ビットとし、ｋ＝６、すなわちブロックのサイズを６４バイト、ｎ＝１０、すなわちアドレスアレイ５０２、５０３、追い出しブロック用アドレスアレイ５０４、データアレイ５０５、５０６のエントリ数を１０２４、ｍ＝４８とする。ここでは、一例として２ウェイセットアソシアティブ方式のキャッシュメモリを示しているが、ウェイ数は任意である。また、一例として、追い出しブロック用のアドレスアレイの個数を１個としているが、この個数も任意である。なお、セットアソシアティブ方式のウェイ数と追い出しブロック用アドレスアレイの個数は、アドレス比較器の個数等に影響する。【００８５】
次に、図６のキャッシュメモリの動作を説明する。キャッシュメモリへのアクセスがあった場合に、そのアドレスがアドレスレジスタ５０１に設定される。このアドレスは論理アドレスであっても物理アドレスであってもよい。ここでは、何らかのアドレス変換の手段により、仮想アドレスから変換された物理アドレスとして説明を行う。【００８６】
ブロックのサイズは６４バイトであるから、アドレスレジスタ５０１の下位６（ｋ）ビット５２９はブロック内のアドレスとなる。その上位の１０（ｎ）ビット５２０をオフセット５２１として、アドレスアレイ５０２、５０３と追い出し用アドレスアレイ５０４の中のエントリを読み出す。比較器Ａ５０７は、アドレスアレイ（ウェイ０）５０２から読み出したエントリの中のアドレスの上位４８（ｍ）ビット５１１と、アドレスレジスタ５０１の上位４８（ｍ）ビット５２２を比較する。比較器Ｂ５０８は、アドレスアレイ（ウェイ１）５０３から読み出したエントリのアドレスの上位４８（ｍ）ビット５１３とアドレスレジスタ５０１の上位４８（ｍ）ビット５２２とを比較する。比較器Ｃ５０９は、追い出しブロック用アドレスアレイ５０４から読み出したエントリのアドレスの上位４８（ｍ）ビット５１５とアドレスレジスタ５０１の上位４８（ｍ）ビット５２２とを比較する。制御部５１０は、これらの比較結果に基づいて、そのブロックのエントリがすでにキャッシュメモリにあるか否かを判定する。【００８７】
比較結果Ａ５２３、比較結果Ｂ５２４、比較結果Ｃ５２５は、命令種別（ｌｏａｄ、ｓｔｏｒｅ）５２８、アドレスアレイ５０２、５０３と追い出しブロック用アドレスアレイ５０４から読み出されたエントリ内の状態ビット列５１２５１４５１６、ウェイ番号５１７とともに制御部５１０に入力され、キャッシュメモリの動作を決定する。制御部５１０における動作の決定と動作の詳細ついては、後の動作の説明のところで説明する。【００８８】
第２の実施例のアドレスアレイ５０２、５０３の状態ビット列５１２、５１４は、第１の実施例の図３の状態ビット列２０１と同じである。また、第２の実施例の追い出しブロック用アドレスアレイ５０４の状態ビット列５１６は、第１の実施例の図３の状態ビット列２０５と同じである。【００８９】
次に、図６の構成要素と、図３の状態他のビット列を参照しながら、本発明の第２の実施例の動作について詳細に説明する。【００９０】
図７は、図６の制御部５１０での動作の決定と動作について説明するためのフローチャートである。【００９１】
図６のアドレスレジスタ５０１にアクセスされたアドレスが格納され、アドレスレジスタ５０１の１０（ｎ）ビット５２０によって、アドレスアレイ５０２、５０３と追い出しブロック用アドレスアレイ５０４、データアレイ５０５、５０６のエントリがアクセスされた状態になっている。この時点における制御部５１０の動作の決定とその動作について説明する。【００９２】
制御部５１０は、ＣＰＵからの命令種別５２８によって行うべき処理を判定する（ステップＳ６０１）。【００９３】
まず、命令種別５２８がｓｔｏｒｅである場合には（ステップＳ６０１のｓｔｏｒｅ）、制御部５１０は、キャッシュがヒットしたか否かを判定する（ステップＳ６０３）。制御部５１０は、比較器Ａ５０７、比較器Ｂ５０８、比較器Ｃ５０９からの比較結果Ａ５２３、比較結果Ｂ５２４、比較結果Ｃ５２５と、アドレスアレイ５０２、５０３と追い出しブロック用アドレスアレイ５０４の状態ビット列５１２、５１４、５１６により、アクセスしたデータがキャッシュヒットしているか否かを判定する（ステップＳ６０３）。【００９４】
比較結果Ａ５２３が一致し、状態ビット列５１２のフラグＶ２０２が１である場合、比較結果Ｂ５２４が一致し、状態ビット列５１４のフラグＶ２０２が１である場合、または、比較結果Ｃ５２５が一致し、状態ビット列５１６のフラグＶ２０６が１である場合には、制御部５１０は、キャッシュヒットしたものと判定する（ステップＳ６０３のＹｅｓ）。【００９５】
一方、比較結果Ａ５２３が一致しない、または、状態ビット列５１２のフラグＶ２０２が０である場合において、比較結果Ｃ５２４が一致しない、または、状態ビット列５１４のフラグＶ２０２が０であるときに、比較結果Ｃ５２５が一致しない、または、状態ビット列５１６のフラグＶ２０６が０である場合には、制御部５１０は、キャッシュミスしたものと判定する（ステップＳ６０３のＮｏ）。【００９６】
キャッシュヒットした場合には（ステップＳ６０３のＹｅｓ）は、制御部５１０は、比較結果Ａ５２３または比較結果Ｂ５２４が一致を示したのか、比較結果Ｃ５２５が一致を示したのかにより、キャッシュヒットしたのが通常のアドレスアレイ５０２、５０３であるのか、または、追い出しブロック用のアドレスアレイ５０４であるのかを判定する（ステップＳ６０６）。【００９７】
通常のアドレスアレイ５０２、５０３がヒットした場合には（ステップＳ６０６のＮｏ）、制御部５１０は、まず、ＬＲＵの更新を行う（ステップＳ６０８）。そして、そのブロックが読み出し中かどうかを、状態ビット列５１２または５１４のフラグＦ２０４に基づいて判定する（ステップＳ６０９）。【００９８】
もし、フラグＦ２０４が１であり、ブロックの読み出し中である場合には（ステップＳ６０９のＹｅｓ）、読み出しが終了するまで待つ。一方、フラグＦ２０４が０であり、ブロックの読み出し中でない場合には（ステップＳ６０９のＮｏ）、制御部５１０は、下位６（ｋ）ビットのデータに基づいて、そのブロックのデータ内のワードを特定し、そのワードに対して、書き込みデータを書き込み（ステップＳ６１２）、状態ビット列５１２または５１４のフラグＤ２０３を１にする（ステップＳ６１３）。【００９９】
追い出しブロック用アドレスアレイ５０４がヒットした場合には（ステップＳ６０６のＹｅｓ）、制御部５１０は、ウェイ番号５１７が示すウェイのデータアレイ（ウェイ０）５０５または５０６のブロック５１８または５１９の、下位６（ｋ）ビットのデータに基づいて特定されるワードに対して、書き込みデータを書き込み（ステップＳ６１５）、状態ビット列５１６のフラグＤ２０７を１にする（ステップＳ６１６）。【０１００】
キャッシュミスした場合には（ステップＳ６０３のＮｏ）、制御部５１０は、キャッシュブロックの置き換えが発生するか否かを判定する（ステップＳ６１７）。【０１０１】
すでに、キャッシュメモリのすべてのウェイを使用している（状態ビット列５１２と５１４のフラグＶ２０２が１）場合には、制御部５１０は、置き換えが発生するものと判定する（ステップＳ６１７のＹｅｓ）。一方、１つでも空いているウェイがある場合には（状態ビット列５１２または５１４のフラグＶ２０２が０）、制御部５１０は、置き換えが発生しないものと判定する（ステップＳ６１７のＮｏ）。【０１０２】
ブロックの置き換えが発生しない場合には（ステップＳ６１７のＮｏ）、空いているウェイのアドレスアレイ５０２または５０３の上位ｍビット５１１または５１３にアドレスレジスタ５０１の上位ｍビット５２２を格納し、状態ビット列５１２または５１４のフラグＶ２０２とフラグＦ２０４を１としてメモリからブロックを読み出す。そして、読み出されたブロックが到着したら、データアレイ５０５または５０６のブロック５１８または５１９に書き込み、アドレスアレイ５０２または５０３の状態ビット列５１２または５１４のフラグＦ２０４を０にする（ステップＳ６２０）。そして、ブロック５１８または５１９にデータを書き込み（ステップＳ６１２）、アドレスアレイ５０２または５０３の状態ビット列５１２または５１４のフラグＤ２０３を１にする（ステップＳ６１３）。【０１０３】
ブロックの置き換えが発生する場合には（ステップＳ６１７のＹｅｓ）、ブロックの置き換えとブロックの読み出し（ステップＳ６２１）を行う。ステップＳ６２１については図６を参照して後述する。ステップＳ６２１の後、読み出されたブロックにデータを書き込み（ステップＳ６１２）、アドレスアレイ５０２または５０３の状態ビット列５１２または５１４のフラグＤ２０３を１にする（ステップＳ６１３）。【０１０４】
次に、命令種別５２８がｌｏａｄの場合には（ステップＳ６０１のｌｏａｄ）、制御部５１０は、キャッシュヒットしたか否かを判定する（ステップＳ６２３）。制御部５１０は、比較器Ａ５０７、比較器Ｂ５０８、比較器Ｃ５０９からの比較結果Ａ５２３、比較結果Ｂ５２４、比較結果Ｃ５２５と、アドレスアレイ５０２、５０３と追い出しブロック用アドレスアレイ５０４の状態ビット列５１２、５１４、５１６により、アクセスしたデータがキャッシュヒットしているか否かを判定する（ステップＳ６２３）。【０１０５】
比較結果Ａ５２３が一致し、状態ビット列５１２のフラグＶ２０２が１である場合、比較結果Ｂ５２４が一致し、状態ビット列５１４のフラグＶ２０２が１である場合、または、比較結果Ｃ５２５が一致し、状態ビット列５１６のフラグＶ２０６が１である場合には、制御部５１０は、キャッシュヒットしたものと判定する（ステップＳ６２３のＹｅｓ）。【０１０６】
一方、比較結果Ａ５２３が一致しない、または、状態ビット列５１２のフラグＶ２０２が０である場合において、比較結果Ｃ５２４が一致しない、または、状態ビット列５１４のフラグＶ２０２が０であるときに、比較結果Ｃ５２５が一致しない、または、状態ビット列５１６のフラグＶ２０６が０である場合には、制御部５１０は、キャッシュミスしたものと判定する（ステップＳ６２３のＮｏ）。【０１０７】
キャッシュヒットした場合には（ステップＳ６２３のＹｅｓ）、制御部５１０は、比較結果Ａ５２３または比較結果Ｂ５２４が一致したのか、比較結果Ｃ５２５が一致したのかにより、キャッシュヒットしたのが通常のアドレスアレイ５０２、５０３なのか、追い出しブロック用のアドレスアレイ５０４なのかを判定する（ステップＳ６２６）。【０１０８】
通常のアドレスアレイ５０２、５０３がヒットした場合には（ステップＳ６２６のＮｏ）、制御部５１０は、まず、ＬＲＵの更新を行う（ステップＳ６２８）。そして、そのブロックが読み出し中か否かを、状態ビット列５１２または５１４のフラグＦ２０４に基づいて判定する（ステップＳ６２９）。もし、フラグＦ２０４が１であり、ブロックの読み出し中である場合には（ステップＳ６２９のＹｅｓ）、読み出しが終了するまで待つ。フラグＦ２０４が０であり、ブロックの読み出し中でない場合には（ステップＳ６２９のＮｏ）、制御部５１０は、下位６（ｋ）ビットのデータに基づいて、そのブロック５１８または５１９内のワードを特定し、そのワードを読み出す（ステップＳ６３２）。【０１０９】
追い出しブロック用アドレスアレイ５０４がヒットした場合には（ステップＳ６２６のＹｅｓ）、制御部５１０は、ウェイ番号５１７が示すウェイのデータアレイ５０５または５０６のブロック５１８または５１９の、下位６（ｋ）ビットのデータに基づいて特定されるワードを読み出す（ステップＳ６３４）。【０１１０】
キャッシュミスした場合には（ステップＳ６２３のＮｏ）、制御部５１０は、キャッシュブロックの置き換えが発生するか否かを判定する（ステップＳ６３５）。すでに、キャッシュメモリのすべてのウェイを使用している（状態ビット列５１２と５１４のフラグＶ２０２が１）場合には、制御部５１０は置き換えが発生するものと判定する（ステップＳ６３５のＹｅｓ）。１つでも空いているウェイがある場合には（状態ビット列５１２または５１４のフラグＶ２０２が０）、制御部５１０は、置き換えが発生しないものと判定する（ステップＳ６３５のＮｏ）。【０１１１】
ブロックの置き換えが発生しない場合には（ステップＳ６３５のＮｏ）、空いているウェイのアドレスアレイ５０２または５０３の上位ｍビット５１１または５１３にアドレスレジスタ５０１の上位ｍビット５２２を格納し、状態ビット列５１２または５１４のフラグＶ２０２とフラグＦ２０４を１としてメモリからブロックを読み出す。そして、読み出されたブロックが到着したら、データアレイ５０５または５０６のブロック５１８または５１９に書き込み、アドレスアレイ５０２または５０３の状態ビット列５１２または５１４のフラグＦ２０４を０にする（ステップＳ６３８）。そして、ブロック５１８または５１９からデータを読み出す（ステップＳ６３２）。【０１１２】
ブロックの置き換えが発生する場合には（ステップＳ６３５のＹｅｓ）、ブロックの置き換えとブロックの読み出しを行う（ステップＳ６３９）。ステップＳ６３９については図６を参照して後述する。ステップＳ６３９の後、読み出されたブロックからデータを読み出す（ステップＳ６３２）。【０１１３】
次に、図６を参照して、図７のステップＳ６２１およびＳ６３９について説明する。まず、制御部５１０は、ＬＲＵに従い、置き換え対象のウェイを選択する（ステップＳ７０１）。そして、ＬＲＵを更新する。【０１１４】
次に、追い出しブロック用アドレスアレイ５０４のエントリが空であるか否かを判定する（ステップＳ７０２）。追い出しブロック用アドレスアレイ５０４の状態ビット列５１６のＶ２０６が０である場合には空であり、１である場合には空ではない。【０１１５】
空でない場合には（ステップＳ７０２のＮｏ）、制御部５１０は、置き換えられるアドレスアレイ５０２または５０３の状態ビット列１０８または１１０のフラグＤ２０３が１か０かに基づいて、追い出されるブロックが書き換えられていたか否かを判定する（ステップＳ７０４）。【０１１６】
書き換えられていた場合に限り（ステップＳ７０４のＹｅｓ）は、データアレイ５０５または５０６内のブロック５１８または５１９をアドレスアレイ５０２または５０３の上位ｍビット５１１または５１３で示されるアドレスに書き戻す（ステップＳ７０６）。【０１１７】
次に、制御部５１０は、アドレスレジスタ５０１の上位ｍビット５２２をアドレスアレイ５０２または５０３の上位ｍビット５１１または５１３にコピーする。また、アドレスアレイ５０２または５０３の状態ビット列５１２または５１３のフラグＶ２０２とフラグＦ２０４を１に、フラグＤ２０３を０にする（ステップＳ７０８）。そして、メモリに対してキャッシュミスしたブロックの読み出しリクエストを発行し、メモリからのブロックをデータアレイ５０５または５０６のブロック５１８または５１９に書き込む（ステップＳ７０９）。【０１１８】
追い出しブロック用アドレスアレイ５０４が空である場合には（ステップＳ７０２のＹｅｓ）、追い出されるアドレスアレイ５０２または５０３の上位ｍビット５１１か５１３を追い出しブロック用アドレスアレイ５０４の上位ｍビット５１５にコピーする。そして、状態ビット列５１６のフラグＶ２０６を１に、フラグＤ２０７を０にする。そして、ウェイ番号５１７に追い出されるウェイ番号をセットする（ステップＳ７１１）。【０１１９】
次に、制御部５１０は、ウェイ番号５１７で示されたアドレスアレイ５０２または５０３の状態ビット列のフラグＤ２０３が１か０かに基づいて、追い出されるブロックが書き換えられていたか否かを判定する（ステップＳ７１２）。書き換えられていた場合に限り（ステップＳ７１２のＹｅｓ）、ウェイ番号５１７で示されたデータアレイ５０５または５０６内のブロック５１８または５１９を、置き換えられるアドレスアレイ５０２または５０３の上位ｍビット５１１または５１２で示されるアドレスに書き戻す（ステップＳ７１４）。【０１２０】
次に、制御部５１０は、アドレスレジスタ５０１の上位ｍビット５２２をウェイ番号５１７で示されたアドレスアレイ５０２または５０３の上位ｍビット５１１または５１３にコピーする。そして、状態ビット列５１２または５１４のフラグＶ２０２とフラグＦ２０４を１にフラグＤ２０３を０にする（ステップＳ７１６）。その後、制御部５１０は、メモリに対してキャッシュミスしたブロックの読み出しリクエストを発行する（ステップＳ７１７）。次に、メモリからのブロックの到着を待つ（ステップＳ７１８）。【０１２１】
ブロックが到着するまでの間、従来なら無効となっている追い出されるブロックが、追い出しブロック用アドレスアレイ上で有効となる。また、追い出されるブロックのデータはデータアレイ５０５または５０６のブロック５１８または５１９に残っている。【０１２２】
読み出したブロックがキャッシュメモリに到着する（ステップＳ７１９）。制御部５１０は、追い出しブロック用アドレスアレイ５０４の状態ビット列５１６のフラグＶ２０６を０とし、無効化する（ステップＳ７２０）。制御部５１０は、追い出しブロック用アドレスアレイ５０４の状態ビット列５１６のフラグＤ２０７を調べ、書き換えられたか否かを判定する（ステップＳ７２１）。【０１２３】
書き換えられている場合に限り（ステップＳ７２１のＹｅｓ）、ウェイ番号５１７で示されたデータアレイ５０５または５０６内のブロック５１８または５１９を追い出しブロック用アドレスアレイ５０４の上位ｍビット５１５のアドレスに書き戻す（ステップＳ７２３）。そして、メモリから読み出したブロックをウェイ番号５１７の示すデータアレイ５０５または５０６のブロック５１８または５１９に書き込む。そして、ウェイ番号が示すアドレスアレイ１０２の状態ビット列１０８のフラグＦ２０４を０にする（ステップＳ７２５）。【０１２４】
次に、図９〜図１５を参照して、第２の実施例のキャッシュメモリの動作を説明する。【０１２５】
図９は、２ウェイにブロックをキャッシュしている状態で、同じカラムにキャッシュされる他のブロックのデータをｌｏａｄした時点を図示している。まず、アドレスレジスタ８０１のｎビット８０２をインデックスとしてカラムが選択され、アドレスアレイ（ウェイ０）８０３、アドレスアレイ（ウェイ１）８０４、追い出しブロック用アドレスアレイ８０５からエントリが読み出され、アドレスレジスタの上位ｍビット８０６の０ｘ０００００１ｃｃ０００３と比較される。【０１２６】
アドレスアレイ（ウェイ０）８０３の上位ｍビット８０７には０ｘ０００００１ｃｃ０００１、アドレスアレイ（ウェイ１）８０４の上位ｍビット８０８には０ｘ０００００１ｃｃ０００２、追い出しブロック用アドレスアレイ８０５は無効なので、その結果、キャッシュミスしたことがわかる。また、アドレスアレイ（ウェイ０）８０３、アドレスアレイ（ウェイ１）８０４ともにエントリが有効なので、置き換えが発生する。そこで、ＬＲＵ８０９を参照して、ウェイ０を置き換えの対象とする。そして、ＬＲＵ８０９を更新して１にする。【０１２７】
図１０は、追い出しブロック用アドレスアレイのエントリを有効化する処理を説明するための図である。追い出しブロック用アドレスアレイ８０５のエントリが空いているので、置き換え対象となったウェイ０の上位ｍビット８０７を追い出しブロック用アドレスアレイの上位ｍビット８１０にコピーする。そして、状態ビット列８１１を１０とし、ウェイ番号８１２を０とする。これで、追い出しブロック用アドレスアレイのエントリが有効となる。【０１２８】
図１１は、置き換え対象のブロックが書き換えられていた場合のライトバック処理を説明している。アドレスアレイ（ウェイ０）８０３の状態ビット列８１３のフラグＤが１なので、ウェイ０のデータアレイ上のブロックを上位ｍビット８０７が示すアドレスにライトバックする。【０１２９】
図１２は、ミスしたブロックをアドレスアレイに登録して、ミスしたブロックをメモリから読み出す処理を説明するための図である。アドレスレジスタ８０１の上位ｍビット８０２をウェイ番号８１２で示されているウェイ０のアドレスアレイ８０３の上位ｍビット８０７にコピーする。そして、状態ビット列８１３のフラグＶＤＦを１０１に設定する。その後、ミスしたブロックをメモリから読み出すためのリクエストを発行する。【０１３０】
図１３は、ミスしたブロックを読み出し中のときに追い出しブロック用アドレスアレイのエントリで書き込みヒットした状態を示す。アドレスレジスタ８０１にあるアドレスへのｓｔｏｒｅ命令が実行され、ｎビット８０２をインデックスとしてアドレスアレイ８０３８０４８０５のエントリが読み出され、アドレスレジスタ８０１の上位ｍビット８０６の０ｘ０００００１ｃｃ０００１と追い出しブロック用アドレスアレイ８０５の上位ｍビット８１０が一致してキャッシュヒットする。そして、ウェイ番号８１２に示されたウェイ０のデータアレイのブロックに書き込みデータが書かれる。そして、書き換えられたことを記憶する追い出しブロック用アドレスアレイ８０５の状態ビット列のフラグＤが１になる。【０１３１】
図１４は、メモリから読み出したブロックがキャッシュメモリに到着したときの処理を示す。まず、追い出しブロック用アドレスアレイ８０５の状態ビット列８１１のフラグＶを０にして、このエントリを無効化する。そして、状態ビット列８１１のフラグＤにより、書き換えられたか否かを調べる。フラグＤが１になっているので、追い出しブロック用アドレスアレイで書き込みヒットして書き換えられたことになるので、ウェイ番号８１２で示されたウェイ０のデータアレイのブロックを上位ｍビット８１０で示されたアドレスにライトバックする。【０１３２】
図１５は、メモリから読み出したブロックをデータアレイに書き込む処理を示す。メモリから読み出したブロックをウェイ番号８１２が示すウェイ０のデータアレイに書き込み、ウェイ０のアドレスアレイ８０２の状態ビット列８１３のフラグＦを０にする。【０１３３】
本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。【０１３４】
なお、本発明は、以下に付記する形態の発明をも含むものである。【０１３５】
（形態１）
上記第１の視点に係るキャッシュメモリ。【０１３６】
（形態２）
前記制御部は、前記第２のブロックを前記データアレイに書き込む際に、前記第２のアドレスアレイに記憶された前記第１のブロックのアドレスを無効化することを特徴とする、形態１に記載のキャッシュメモリ。【０１３７】
（形態３）
前記第２のアドレスアレイは、前記第１のブロックが記憶されているウェイの識別子を記憶することを特徴とする、形態１又は２に記載のキャッシュメモリ。【０１３８】
（形態４）
前記第２のアドレスアレイは、前記第１のブロックがキャッシュヒットして書き換えられたか否かを示すフラグを記憶することを特徴とする、形態１乃至３のいずれか１項に記載のキャッシュメモリ。【０１３９】
（形態５）
前記制御部は、前記第２のブロックをメモリから読み出して前記データアレイに書き込む前に、前記第２のアドレスアレイに記憶されたフラグを参照し、前記第１のブロックが書き換えられていた場合には、前記第１のブロックをメモリに書き戻すことを特徴とする、形態４に記載のキャッシュメモリ。【０１４０】
（形態６）
上記第２の視点に係るキャッシュメモリ。【０１４１】
（形態７）
形態１乃至６のいずれか１項に記載のキャッシュメモリを備えていることを特徴とする電子計算機。【０１４２】
（形態８）
マルチコア又はマルチスレッドプロセッサを備えていることを特徴とする、形態７に記載の電子計算機。【０１４３】
（形態９）
上記第３の視点に係る、キャッシュメモリの制御方法。【０１４４】
（形態１０）
前記第２のブロックを前記データアレイに書き込む際に、前記第２のアドレスアレイに記憶された前記第１のブロックのアドレスを無効化する工程をさらに含むことを特徴とする、形態９に記載のキャッシュメモリの制御方法。【０１４５】
（形態１１）
前記第１のブロックが記憶されているウェイの識別子を、前記第２のアドレスアレイに記憶させる工程を含むことを特徴とする、形態９又は１０に記載のキャッシュメモリの制御方法。【０１４６】
（形態１２）
前記第１のブロックがキャッシュヒットして書き換えられたか否かを示すフラグを、前記第２のアドレスアレイに記憶させる工程を含むことを特徴とする、形態９乃至１１のいずれか１項に記載のキャッシュメモリの制御方法。【０１４７】
（形態１３）
前記第２のブロックをメモリから読み出して前記データアレイに書き込む前に、前記第２のアドレスアレイに記憶されたフラグを参照し、前記第１のブロックが書き換えられていた場合には、前記第１のブロックをメモリに書き戻す工程を含むことを特徴とする、形態１２に記載のキャッシュメモリの制御方法。
【符号の説明】
【０１４８】
１０  キャッシュメモリ
１１  アドレスアレイＡ
１２  データアレイ
１３  アドレスアレイＢ
１４、１２０、５１０  制御部
２０  メモリ
３０  プロセッサ
１０１、５０１、８０１  アドレスレジスタ
１０２  アドレスアレイ
１０３、５０４、８０５  追い出しブロック用アドレスアレイ
１０４  データアレイ
１０５、５０７  比較器Ａ
１０６、５０８  比較器Ｂ
１０７、１０９、１１４、５１１、５１３、５１５、８０６〜８０８、８１０  上位ｍビット
１０８、１１０、５１２、５１４、５１６、８１１、８１３  状態ビット列
１１１、５１８、５１９  ブロック
１１２、５２０、８０２  ｎビット
１１３  オフセット
１１５、５２３  比較結果Ａ
１１６、５２４  比較結果Ｂ
１１７、５２８  命令種別
１１８、５２９  下位ｋビット
１１９、５３０、５３１  データ
２０１  状態３ビット
２０２、２０６  フラグＶ
２０３、２０７  フラグＤ
２０４  フラグＦ
２０５  状態２ビット
５０２、８０３  アドレスアレイ（ウェイ０）
５０３、８０４  アドレスアレイ（ウェイ１）
５０５  データアレイ（ウェイ０）
５０６  データアレイ（ウェイ１）
５０９  比較器Ｃ
５１７、８１２  ウェイ番号
５２１  オフセット
５２２  上位ｍビット
５２５  比較結果Ｃ
８０９  ＬＲＵ
【図１】
2010087310.tif 000003
【図２】
2010087310.tif 000004
【図３】
2010087310.tif 000005
【図４】
2010087310.tif 000006
【図５】
2010087310.tif 000007
【図６】
2010087310.tif 000008
【図７】
2010087310.tif 000009
【図８】
2010087310.tif 000010
【図９】
2010087310.tif 000011
【図１０】
2010087310.tif 000012
【図１１】
2010087310.tif 000013
【図１２】
2010087310.tif 000014
【図１３】
2010087310.tif 000015
【図１４】
2010087310.tif 000016
【図１５】
2010087310.tif 000017
【国際調査報告】
2010087310.tif 000018
2010087310.tif 000019
2010087310.tif 000020