キャッシュメモリ、キャッシュメモリシステム
【課題】よりキャッシュヒット率を向上させたキャッシュメモリを提供する。
【解決手段】キャッシュメモリ６は、４つのワード（Word0,Word1,Word2,Word3）を含むラインを有するデータ格納部１６と、各ラインを識別するタグを格納するタグ格納部１４を備える。タグ格納部は、ラインがリフィル中であるか否かを示すリフィルビット(R)と、ワード毎にワードにおけるデータがダーティであるか否かを示すダーティビット(D0,D1,D2,D3)と、ラインに格納されたデータの主記憶におけるアドレスを示すタグビット(Tag)を格納している。ヒット判定器２０は、リードアクセス対象のタグアドレス(AD[31:16]）とタグビット(Tag)に示されるアドレスとが一致し、リードアクセス対象に係るラインに対応するリフィルビット(R)がリフィル中を示し、かつ、当該ラインに含まれリードアクセス対象に係るワードに対応するダーティビットがダーティを示していれば、リードヒットと判定する。
【解決手段】キャッシュメモリ６は、４つのワード（Word0,Word1,Word2,Word3）を含むラインを有するデータ格納部１６と、各ラインを識別するタグを格納するタグ格納部１４を備える。タグ格納部は、ラインがリフィル中であるか否かを示すリフィルビット(R)と、ワード毎にワードにおけるデータがダーティであるか否かを示すダーティビット(D0,D1,D2,D3)と、ラインに格納されたデータの主記憶におけるアドレスを示すタグビット(Tag)を格納している。ヒット判定器２０は、リードアクセス対象のタグアドレス(AD[31:16]）とタグビット(Tag)に示されるアドレスとが一致し、リードアクセス対象に係るラインに対応するリフィルビット(R)がリフィル中を示し、かつ、当該ラインに含まれリードアクセス対象に係るワードに対応するダーティビットがダーティを示していれば、リードヒットと判定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ライトバック方式のキャッシュメモリに関する。
【背景技術】
【０００２】
ライトバック方式とは、キャッシュメモリへのデータ書き込み時に、基本的にキャッシュメモリに対してのみ書き込み、主記憶へは同時には書き込まずに、後で適宜書き戻す方式である。
ライトバック方式では、キャッシュメモリと主記憶とへの書き込みタイミングにズレが生じるので、両者が保持しているデータの整合性を管理するためのDirty/Cleanフラグが設けられている。Dirty（ダーティ）は、キャッシュメモリに保持されているデータが更新されるなどして、主記憶上のデータとの一致が保証できない場合を示し、Clean（クリーン）は、その逆を示す。Dirty/Cleanフラグにより、対象のデータがDirtyかCleanかを判断することができる。Dirtyなデータは、適当なタイミングで主記憶に書き戻し、その整合性をとる必要がある。
【０００３】
このようなDirty/Cleanフラグは、ライン（数ワードから構成される）単位で管理することが一般的である。もっとも、ライン単位であると、ラインに含まれる数ワードのうちの、どのワードがDirtyかまでは不明なので無用な書き戻しが行われることがある。
そこで、特許文献１では、ラインより細かい単位（例えば、ワード単位）でDirty/Cleanの別を管理することで、必要なデータのみの書き戻しを可能にし、不要なバス・トランザクションの低減が図れるとしている。なお、他に特許文献２〜４の技術が知られている。
【特許文献１】特開2003-108439号公報
【特許文献２】特開2006-91995号公報
【特許文献３】特開平8-16467号公報
【特許文献４】特開平8-221270号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
低速な主記憶へアクセスする代わりに、高速なキャッシュメモリ上の対応するデータにアクセスすることで、一般にキャッシュヒット率が向上する。キャッシュヒット率が向上することで、計算機システム全体の性能を向上することができる。
キャッシュメモリにおいては、キャッシュミス時などには、ラインのデータを入れ換えるリフィルという処理を行う。このリフィルの最中であっても、キャッシュヒット扱いしてアクセスを許可しても問題がない場合も潜在している。しかしながら、前記従来の技術では、リフィルの最中においては、リフィル中のラインへのアクセスはキャッシュミスと扱っており、主記憶へアクセスをする必要があるという課題を有している。
【０００５】
このような背景のもとで、本発明は、よりキャッシュヒット率を向上させたキャッシュメモリを提供することを目的としている。
【課題を解決するための手段】
【０００６】
本発明に係るキャッシュメモリは、それぞれ複数のワードを含む複数のラインと、前記ラインに格納されたデータの主記憶におけるアドレスを示すタグと、前記ライン毎にラインがリフィル中であるか否かを示すリフィルビットと、前記ワード毎にワードにおけるデータがダーティであるか否かを示すダーティビットとを格納するタグ格納部と、リードアクセス対象のタグアドレスと、前記タグに示されるアドレスとが一致し、リードアクセス対象に係るラインに対応するリフィルビットがリフィル中を示し、かつ、当該ラインに含まれリードアクセス対象に係るワードに対応するダーティビットがダーティを示していれば、リードヒットと判定するヒット判定手段とを備えることを特徴としている。
【０００７】
また、前記ヒット判定手段は、ライトアクセス対象に係るラインのアドレスと、前記タグに示されるアドレスが一致するラインであって、当該ラインに対応するリフィルビットがリフィル中であることを示す場合には、ライトヒットと判定するとしても構わない。
また、前記ヒット判定手段は、当該ワードに対応するダーティビットがダーティを示していなければ、リードミスヒットと判定するとしても構わない。
【０００８】
また、本発明に係るキャッシュメモリは、それぞれ複数のワードを含む複数のラインと、前記ラインに格納されたデータの主記憶におけるアドレスを示すタグと、前記ライン毎にラインがリフィル中であるか否かを示すリフィルビットと、前記ワード毎にワードにおけるデータがダーティであるか否かを示すダーティビットとを格納するタグ格納部と、ライトアクセス対象のタグアドレスと、前記タグに示されるアドレスとが一致し、当該ラインに対応するリフィルビットがリフィル中であることを示す場合には、ライトヒットと判定するヒット判定手段とを備えることを特徴とする。
【０００９】
さらに、前記ヒット判定手段によりライトヒットと判定された場合に、前記ライトアクセスに係るワードへの書き込みがあると、当該ワードに対応するダーティビットをアサートし、ラインのリフィルに際して、ダーティビットがダーティであることを示さないワードに対してはデータの上書きを許可し、前記アサートによりダーティであることを示すワードに対してはデータの上書きを禁止する制御手段を備えるとしても構わない。
【００１０】
また、本発明に係るキャッシュメモリシステムは、中央処理装置と、前記キャッシュメモリと、前記中央処理装置と前記キャッシュメモリと記憶階層において間の階層に位置し、前記中央処理装置が前記キャッシュメモリへとライトすべきデータを保持する第１ライトバッファと、前記キャッシュメモリとライトバック対象となるメモリと記憶階層において間の階層に位置し、前記キャッシュメモリから前記ライトバック対象となるメモリへとライトバックすべきデータを保持する第２ライトバッファと、前記キャッシュメモリと前記ライトバック対象となるメモリと記憶階層において間の階層に位置し、前記キャッシュメモリがリードすべきデータを保持するリードバッファとを備えることを特徴とする。
【発明の効果】
【００１１】
本発明に係るキャッシュメモリは、従来はリフィル中であるとリードミスヒットと判定していたのに対して、ラインがリフィル中という状況下においても、ヒット判定手段は、そのラインに含まれるワードに対応するダーティビットがダーティを示していれば、リードヒットと判定する。
この構成によれば、リードアクセス対象に係るラインがリフィル中という状況下においても、ヒット判定手段は、リードヒットと判定するので、キャッシュリードミスを減らし、キャッシュリードヒット率を向上できる。これにより、キャッシュリードミスに起因する計算機のオーバーヘッドを軽減することができる。
【００１２】
また、本発明に係るキャッシュメモリは、それぞれ複数のワードを含む複数のラインと、前記ラインに格納されたデータの主記憶におけるアドレスを示すタグと、前記ライン毎にラインがリフィル中であるか否かを示すリフィルビットと、前記ワード毎にワードにおけるデータがダーティであるか否かを示すダーティビットとを格納するタグ格納部と、ライトアクセス対象のタグアドレスと、前記タグに示されるアドレスとが一致し、当該ラインに対応するリフィルビットがリフィル中であることを示す場合には、ライトヒットと判定するヒット判定手段とを備えることを特徴とするとしている。
【００１３】
この構成によれば、ライトアクセス対象に係るラインがリフィル中という状況下においても、ヒット判定手段は、ライトヒットと判定するので、キャッシュライトヒット率を向上できる。
【発明を実施するための最良の形態】
【００１４】
以下、図面を用いて本発明の実施の形態について説明する。また、本実施の形態におけるライトバック方式のキャッシュメモリは、ダイレクトマップ方式を採用しており、キャッシュのライトミス時には、ライトアロケート方式（先に新しいラインをキャッシュメモリに書き込み、その後で書き込みヒット時の動作を行う方式である。）で処理を行うとして説明する。
【００１５】
図１は、キャッシュメモリシステム１の構成図である。
キャッシュメモリシステム１は、ＣＰＵ２、主記憶４、キャッシュメモリ６、ライトバッファ８，１０、リードバッファ１２を含んで構成している。
ＣＰＵ２は、各種演算処理を行う中央処理装置である。
主記憶４は、DRAMなどデータを一時記憶する揮発性メモリから構成される。
【００１６】
キャッシュメモリ６は、主記憶４に格納すべきデータを一時的に格納する。主記憶４よりアクセス速度が速く、記憶階層の構造上、上位のＣＰＵ２と下位の主記憶４との間に介在している。キャッシュメモリ６はライトバック方式であり、キャッシュミス発生時などを契機として保持しているデータを主記憶４へと書き戻す。
キャッシュメモリ６は、制御部６ａ、格納部６ｂ、ヒット判定部６ｃ、調停部６ｄを備える。
【００１７】
制御部（キャッシュメモリ制御部）６ａは、各機能ブロックを制御し、例えば格納部６ｂに格納されたデータの読み書きやタグの更新を行う。また、ヒット判定部６ｃのヒット判定結果に応じてＣＰＵ２にデータを出力する。
格納部６ｂは、データを格納するデータ格納部と、格納されたデータを識別する情報としてのタグを含むタグ格納部とから構成される。
【００１８】
ヒット判定部６ｃは、ＣＰＵ２からのアクセス対象となったデータが、格納部６ｂに格納されているかどうかのヒット判定を行う。詳しくは後述する。
調停部６ｄは、格納部６ｂ内のデータ格納部へのデータへのアクセスが競合する場合などに調停する。
図２は、キャッシュメモリ６の構成を示す図である。
【００１９】
図２上部のアドレス２２は、ＣＰＵ２がキャッシュメモリ６へとアクセスを試みる際に、ＣＰＵ２からリード／ライト要求とともに出力されるアドレスを示している。
アドレス（AD[31:0]）２２は、32ビットであり、上位16ビット(AD[31:16])をタグアドレスとして、ビット4からビット15の12ビット（AD[15:4]）をインデックスアドレスとして、ビット2からビット3の2ビット（AD[3:2]）をラインに含まれるワードを特定するワードアドレスとして利用する。なお、インデックスアドレスは12ビットであるので、4096(=2^12)本のラインを指定することができる。このインデックスアドレスによりアクセス対象のラインが一意に特定されることとなる。
【００２０】
キャッシュメモリ６は、タグ格納部１４、データ格納部１６、セレクタ１８、ヒット判定器２０を含む。
タグ格納部１４は、データ格納部１６における4096本のラインに対応して設けられており、ラインに格納されたデータなどの識別情報を格納している。
具体的には、タグ格納部１４は、ラインのデータが有効であるか否かを示すバリッドビット(V)、ラインがリフィル中であるか否かを示すリフィルビット(R)、ラインに格納されたデータの主記憶におけるアドレスを示すタグビット(Tag)を有する。
【００２１】
これに加えて、タグ格納部１４は、ラインに含まれる４つのワード（Word0,Word1,Word2,Word3）に対応してそれぞれ設けられた４つのダーティビット(D0,D1,D2,D3)を含んでいる。ダーティビットがダーティならば、対応するワードは、更新されたが主記憶には未だ書き戻されていない状態であることを意味しているので、適宜、主記憶に書き戻す必要がある。
【００２２】
データ格納部１６は、４つのワードを1ラインとした4096本のラインを保持している。データ格納部１６は、タグ格納部１４とは別個のメモリとしてＳＲＡＭなどにより構成される。なお、１ワードあたりのサイズは、ＣＰＵ２からのアクセスのビット幅に対応して32ビットであり、データ格納部１６の入出力ポートのビット幅も32ビット（１ワード分）である。
【００２３】
セレクタ１８は、アドレス２２の2ビット（AD[3:2]）に基づいて、4つのワードのうちの1つのワードを選択する。
ヒット判定器２０には、リードかライトを示す信号（Read or Write）、タグアドレス（AD[31:16]）、インデックスアドレス（AD[15:4]）により特定されたラインのバリッドビット(V)、リフィルビット(R)、4つのワード毎のダーティビット(D0,D1,D2,D3)、上記ラインに格納されたデータのアドレスを示すタグビット(Tag)、4つのワードのうちの１つを特定するワードアドレス（AD[3:2]）、の10個の入力に基づいてヒットかミスヒットかを判定する。
【００２４】
ヒット判定器２０の回路構成例を図３に示す。
ヒット判定器２０は、２入力１出力のAND回路２３，２４，２６，２８，３０、３入力１出力のOR回路３２、NOT回路３４，３６、４入力１出力のセレクタ３８、コンパレータ４０を備える。
セレクタ３８は、2ビット（AD[3:2]）の入力に基づいて、D0，D1，D2，D3の４つのうちの１つを選択して出力する。すなわち、ラインに含まれるアクセス対象のワードを特定する入力（AD[3:2]）に基づいて、そのワードに対応するダーティビットを出力することとなる。
【００２５】
コンパレータ４０は、タグビット（Tag）と、タグアドレス（AD[31:16]）とを比較し一致した場合にHIGH出力となる。
図４は、図３のヒット判定器２０が入力に応じて出力する判定結果を示す表５０である。
入力される値の組み合わせに応じて（ａ）から（ｈ）までの８つの場合がある。各場合について順に説明する。なお、リフィル中でない（ａ）、（ｂ）、（ｄ）、（ｅ）、（ｆ）、（ｈ）の場合のヒット判定は基本的には従来と同様である。リフィル中の（ｃ）、（ｇ）の場合が特徴的である。
【００２６】
（ａ）の場合・・・ライトアクセス対象のデータのアドレス２２に含まれるタグアドレス（AD[31:16]）とタグビット（Tag）とが一致し、リフィル中で無く(R=0)、バリッドビットが有効(V=1)な場合であり、ライトヒットとなる。そして、キャッシュメモリ６は、ワードアドレス（AD[3:2]）に示されるワードに書き込み、同時に書き込んだワードに対応するダーティビットをアサートする。
【００２７】
（ｂ）の場合・・・バリッドビットが無効（V=0）であるところだけが（ａ）と異なる場合であり、V=0でデータが無効であるので、ライトミスとなる。
ここで、ライトミスヒットしたデータは、一旦ライトバッファ８に保持し、リフィルの完了を待ってキャッシュメモリ６へと書き込むこととなる。特に本実施の形態では、ライトミスヒットしたデータはキャッシュメモリ６にライトしておく。ライト時には、ライトしたワード毎のダーティビットをダーティに更新し、タグビット(Tag)をライトミスヒットしたアクセスのアドレスに更新する。これに先立って、ライトアクセス対象のラインをリフィルするために、主記憶4へのバスにデータリード要求とアドレスとを出力する。なお、このとき、リードバッファ１２に空きが無い場合には、空くまでリード要求の出力を待つか、リードデータが主記憶４から返ってくるよりも以前にリードバッファ１２が空くことが確定できるまでリード要求の出力を待つ。
【００２８】
（ｃ）の場合・・・ライトアクセス対象のデータのタグビット（Tag）とタグアドレス（AD[31:16]）とが一致し、リフィル中(R=1)の場合であり、ライトヒットとなる。そして、キャッシュメモリ６は、ワードアドレス(AD[3:2])に示されるワードに書き込み、書き込んだワードに対応するダーティビットをアサートする。
（ｄ）の場合・・・リードアクセス対象のデータのタグビット（Tag）とタグアドレス（AD[31:16]）とが一致し、リフィル中で無く(R=0)、バリッドビットが有効(V=1)な場合であり、リードヒットとなる。ＣＰＵ２はワードアドレス（AD[3:2]）に示されるワードのデータを読み出すこととなる。
【００２９】
（ｅ）の場合・・・バリッドビットは無効（V=0）であるところだけが（ｄ）と異なる場合であり、V=0でデータが無効であるので、リードミスとなる。
（ｆ）の場合・・・リードアクセス対象のデータのタグビット（Tag）とタグアドレス（AD[31:16]）とが一致し、リフィル中(R=1)であり、ワードアドレス（AD[3:2]）に示されるワード（図４ではW0）に対応するダーティビット（図４ではD0）がダーティではない（クリーンである）場合である。この場合は、ミスヒットとなり、キャッシュメモリ６の制御部６ａは、リフィル中である旨をＣＰＵ２に通知する。ＣＰＵ２は通知がリフィル中で無くなるまで待機（リフィル完了まで待機）し、リフィル完了後にリードヒットとしてリードヒット時の動作（リフィル済のリードアクセス対象のデータを読み出す）をするか、このミスヒットしたリードアクセスが完了しなくとも進められる後続の処理に移ることとなる。
【００３０】
（ｇ）の場合・・・リードアクセス対象のデータのタグビット（Tag）とタグアドレス（AD[31:16]）とが一致し、リフィル中(R=1)であり、ワードアドレス（AD[3:2]）に示されるワード（図４ではW2）に対応するダーティビット（図４ではD2）がダーティな場合である。この場合は、リードヒットとなり、ＣＰＵ２は、ワードアドレス（AD[3:2]）に示されるワードのデータを読み出す。
【００３１】
（ｈ）の場合・・・タグビット（Tag）とタグアドレス（AD[31:16]）とが一致していない場合である。これは、アクセス対象のデータのアドレスとデータ格納部に実際に格納されているデータのアドレスとが異なることを意味するので、他の条件を判断するまでもなく、ライト・リードに関わらずミスヒットとなる。
以上説明したように、ヒット判定器２０は、（ｇ）の場合のように、リフィル中であったとしても、リードアクセス対象のワードに対応するダーティビットがダーティであればリードヒットとして判定するので、従来よりリードヒット率を向上させることができる。
【００３２】
また、ヒット判定器２０は、（ｃ）の場合のように、リフィル中であったとしても、ライトヒットとして判定するので、従来よりライトヒット率を向上させることができる。
次に、ＣＰＵ２、キャッシュメモリ６、主記憶４の処理の流れについて、ライトアクセス時とリードアクセス時を分けて順に説明する。
図５は、ライトアクセス時におけるＣＰＵ２、キャッシュメモリ６、主記憶４のシーケンス図である。なお、初期状態において、ライトアクセス要求の対象となるラインはリフィル中でない（R=0）として説明する。
【００３３】
ＣＰＵ２がライトアクセス要求するデータは、一旦ライトバッファ８で保持する。そして、ライトバッファ８は、キャッシュメモリへのライトアクセス要求とともに、データとこのデータのアドレス（AD[31:0]）２２とをキャッシュメモリ６へと送る（S0）。
ライトアクセス要求を受けたキャッシュメモリ６のヒット判定器２０は、前述のようにライトバッファ８から送られたデータのアドレス（AD[31:0]）２２のタグアドレス（AD[31:16]）とライトアクセス要求の対象となったデータのラインのタグビット（Tag）との比較や、ラインのリフィルビット（R）などに基づいて、ヒット判定を行う。
【００３４】
ライトヒットと判定すれば（S1:Yes）、ライトアクセス要求の対象となるラインのワードにデータを書き込み、必要に応じてそのワードに対応するダーティビットをアサートする（S11）。
ライトミスと判定すれば（S1:No）、キャッシュメモリ６は、ラインのリフィルビットをアサートし(S2:R=1)、ライトバック処理(S3-S8)に移行する。この時、ライトミスしたライトアクセス要求のタグアドレス(AD[31:16])で、タグビット(Tag)を更新する。
【００３５】
ライトバック処理(S3-S8)では、バリッドビットが無効であれば(S3:No,V=0)、ラインが無効であり書き戻すべきデータが無いので処理を終える。
バリッドビットが有効であれば(S3:Yes,V=1)、ライン中のワードにおいて、ワードに対応するダーティビットがダーティ(D=1)なワードだけをライトバッファ１０に書き戻す(S4,S5)。書き戻しを終えたワードに対応するダーティビットはクリーン(D=0)にネゲートする(S6)。
【００３６】
なお、ライトバッファ１０に書き戻されたデータは、バスが空いているときなど適当なタイミングで主記憶４へとさらにライトバックされることとなる。
ラインに含まれる4つのワードについてＳ４からＳ６までの処理を終えると(S7:Yes)、ラインのバリッドビットを無効化(S8:V=0)する。
ライトバック処理(S3-S8)を終えると、キャッシュメモリ６は、リフィル・タグ更新を行う(S9)。具体的には、リードバッファ１２が主記憶４から読み出し済みのライトアクセス対象のラインのデータを、キャッシュメモリ６のラインに上書きする。
【００３７】
このリフィルでは、D=0のワードのみ上書きし、書き戻しされていないワードの上書きを回避する。
キャッシュメモリ６は、リードバッファ１２からの読み込みを完了すると（S9）、ラインを有効化し(S10:V=1)、リフィルビットをネゲート(S10:R=0)して一連のリフィルを終了する。
【００３８】
なお、図５のフローでは、まず先にライトバック処理(S3-S8)を行い、その後でリフィルの処理を行う(S9)として説明したが、両処理はこれに限らず並行して行っても構わない。
図６は、リードアクセス時におけるＣＰＵ２、キャッシュメモリ６、主記憶４のシーケンス図である。なお、初期状態において、リードアクセス要求の対象となるラインはリフィル中でない（R=0）として説明する。
【００３９】
ＣＰＵ２がキャッシュメモリ６にリードアクセスを要求すると(S20)、要求を受けたキャッシュメモリ６はヒット判定器２０において前述のヒット判定を行う。
リードヒットと判定すれば（S21:Yes）、ＣＰＵ２は、リードアクセス要求の対象となるラインのワードからデータを読み出す。
リードミスヒットと判定すれば（S21:No）、S２からS１０までのリフィル処理に移行する。この処理は図５を用いて既に説明したものと同様であるので説明を省略する。
【００４０】
次に、キャッシュメモリ６のあるラインがリフィル中の場合に、このライン中のワードへのライト／リードアクセスがあったときの例について説明する。
図７は、あるラインのワード（W0,W1,W2,W3）のリフィルを時系列上で説明する図である。（ａ）を用いてライトアクセス時の処理について説明し、（ｂ）を用いてリードアクセス時の処理について説明する。
【００４１】
ライトアクセス時は、図７（ａ）に示すように、キャッシュメモリ６は、ｔ０→ｔ１→ｔ２→ｔ３→ｔ４の間に、それぞれW0→W1→W2→W3の順番でリフィルが完了するものとする。また、リフィル開始時にはリフィルビットをアサートし、リフィルすべき新しいラインのアドレスにラインのタグビット(Tag)を更新する。
本実施の形態においては、リフィル途中にも関わらずライトアクセス要求を受けてデータの上書きを許容するので、ラインのタグビット(Tag)が、現実に上書きしたデータのタグと不一致にならないように、図７（ａ）に示すように、リフィル開始時にタグを更新する。
【００４２】
まず、ｔ０からｔ２までの間にワードW2へのライトアクセス要求があった場合には、ヒット判定器２０は前述のようにライトヒットと判定し、ワードW2へのライトアクセスを受けて対応するダーティビット(D2)をアサートする。その後、ｔ２からｔ３の間は、ワードW2のダーティビット(D2)がアサートされているので、キャッシュメモリ６は、ワードW2への上書きを行わない。
【００４３】
なお、上書きを行わない方法としては、例えば、ライトアクセスは行うが、ワードへの書き込みをマスクする信号を利用することが考えられる。また、ワードへのライトアクセス自体を行わずに処理をスキップしてもよい。
次に、ｔ２からｔ３までの間にワードW2へのライトアクセス要求があった場合には、ライトヒットと判定し、ワードW2へのライトアクセスを受けて対応するダーティビット(D2)をアサートする。この場合、ライトアクセス要求時には、ワードW2は既にリフィル中であるので、キャッシュメモリ６はライト制御を調停して両者の競合を防ぐ。
【００４４】
そして、ｔ３からｔ４までの間にワードW2へのライトアクセス要求があった場合には、ライトヒットと判定し、ワードW2へのライトアクセスを受けて対応するダーティビット(D2)をアサートする。
リードアクセス時は、図７（ｂ）に示すように、図７（ａ）同様に、キャッシュメモリ６は、ｔ０→ｔ１→ｔ２→ｔ３→ｔ４の間に、それぞれW0→W1→W2→W3の順番でリフィルが完了するものとする。
【００４５】
まず、ｔ０からｔ４までの間にワードW2へのリードアクセス要求があった場合、ワードW2に対応するダーティビットが有効であるならば、ヒット判定器２０は前述のようにリードヒットと判定し、ワードW2へのリードアクセスを受け付ける。
これに対して、ｔ０からｔ４までの間にワードW2へのリードアクセス要求があった場合で、ワードW2に対応するダーティビットが無効ならば、ヒット判定器２０は前述のようにリードミスヒットと判定する。ＣＰＵ２は、リフィル完了まで待つこととなる。
【００４６】
＜補足＞
以上、本発明の実施の形態について説明したが、本発明は上記の内容に限定されず、本発明の目的とそれに関連または付随する目的を達成するための各種形態においても実施可能であり、例えば、以下であってもよい。
（１）実施の形態では、ダイレクトマップ方式のキャッシュメモリを例に挙げて説明したが、この方式に限らずフルアソシアティブ方式やセットアソシアティブ方式を採用したキャッシュメモリを用いても構わない。これらの方式の場合には、ライトミスヒット時のリフィル対象のラインがダイレクトマップ方式のように一意のラインに決まるのではなく、LRU（Least Recently Used）方式やラウンドロビン方式などのアルゴリズムなどに基づいて行われる点が異なってくる。
【００４７】
また、共有バスを介して複数のキャッシュメモリが下位層の単一のメモリを共有するような共有メモリ型のキャッシュメモリシステムにおいても、ライトバックキャッシュメモリを構成、制御する方法として本発明を適用することができる。
（２）実施の形態では、対応するダーティビットがダーティなワードのみをライトバックする例について説明したが、ダーティワードを含む数ワード、もしくはラインに含まれるワードすべてをライトバックするとしてもよい。また書き戻しの際には、周知の技術のように、ライトバッファ１０に積まれたデータが主記憶４に書き戻されるよりも以前に、書き戻されるアドレスのデータが主記憶４から読み出されることが無いようにシステム全体は制御することができる。
【００４８】
（３）実施の形態では、図１に示すように、キャッシュメモリ６の入出力につながるパスにライトバッファ８，１０とリードバッファ１２を配することで、中央処理装置からキャッシュメモリへのライトアクセス、キャッシュメモリから主記憶へのライトアクセス、主記憶からキャッシュメモリへのライトアクセスが緩衝され、より柔軟なキャッシュメモリ制御が可能となる。
【００４９】
（４）実施の形態では、特に詳細を述べなかったが、システム全体へのオーバーヘッドを軽減する別のアプローチとして、ライトバッファを配置して制御系に工夫を施すことも考えられる。具体的には、ライトミスへの対応として、上位層メモリとキャッシュメモリとの間に多機能なライトバッファを配置し、リフィル中のラインへのライトは、上記ライトバッファにあるデータに対して上書き更新し、リフィル中のラインのリードは、上記ライトバッファから読み出すという制御を行うというものである。しかし、この制御は非常に複雑なものとなる。
【００５０】
これに対して、実施の形態では、ヒット判定器２０のヒット判定という簡単な制御を通してシステム全体へのオーバーヘッドを軽減することが可能となる。
（５）階層メモリシステムとして、中央処理装置、キャッシュメモリ、主記憶の構成を例示したが、さらに深い階層構成のメモリシステムのキャッシュメモリとしてもよい。例えば、キャッシュメモリが、１次キャッシュメモリと２次キャッシュメモリとから構成される場合がある。この場合、本実施の形態を、１次キャッシュメモリに適用してもよいし、２次キャッシュメモリに適用してもよい。
【産業上の利用可能性】
【００５１】
本発明のキャッシュメモリは、一般的な半導体回路内部に存在するキャッシュメモリとして利用でき、キャッシュヒット率を向上できるので有用である。
【図面の簡単な説明】
【００５２】
【図１】キャッシュメモリシステム１の構成図
【図２】キャッシュメモリ６の構成を示す図
【図３】ヒット判定器２０の回路構成例
【図４】図３のヒット判定器２０が入力に応じて出力する判定結果を示す表５０の図
【図５】ライトアクセス時におけるＣＰＵ２、キャッシュメモリ６、主記憶４のシーケンス図
【図６】リードアクセス時におけるＣＰＵ２、キャッシュメモリ６、主記憶４のシーケンス図
【図７】あるラインのワード（W0,W1,W2,W3）のリフィルを時系列上で説明する図
【符号の説明】
【００５３】
１ キャッシュメモリシステム
２ ＣＰＵ
４ 主記憶
６ キャッシュメモリ
８ ライトバッファ
１０ ライトバッファ
１２ リードバッファ
１４ タグ格納部
２０ ヒット判定器
２２ アドレス
【技術分野】
【０００１】
本発明は、ライトバック方式のキャッシュメモリに関する。
【背景技術】
【０００２】
ライトバック方式とは、キャッシュメモリへのデータ書き込み時に、基本的にキャッシュメモリに対してのみ書き込み、主記憶へは同時には書き込まずに、後で適宜書き戻す方式である。
ライトバック方式では、キャッシュメモリと主記憶とへの書き込みタイミングにズレが生じるので、両者が保持しているデータの整合性を管理するためのDirty/Cleanフラグが設けられている。Dirty（ダーティ）は、キャッシュメモリに保持されているデータが更新されるなどして、主記憶上のデータとの一致が保証できない場合を示し、Clean（クリーン）は、その逆を示す。Dirty/Cleanフラグにより、対象のデータがDirtyかCleanかを判断することができる。Dirtyなデータは、適当なタイミングで主記憶に書き戻し、その整合性をとる必要がある。
【０００３】
このようなDirty/Cleanフラグは、ライン（数ワードから構成される）単位で管理することが一般的である。もっとも、ライン単位であると、ラインに含まれる数ワードのうちの、どのワードがDirtyかまでは不明なので無用な書き戻しが行われることがある。
そこで、特許文献１では、ラインより細かい単位（例えば、ワード単位）でDirty/Cleanの別を管理することで、必要なデータのみの書き戻しを可能にし、不要なバス・トランザクションの低減が図れるとしている。なお、他に特許文献２〜４の技術が知られている。
【特許文献１】特開2003-108439号公報
【特許文献２】特開2006-91995号公報
【特許文献３】特開平8-16467号公報
【特許文献４】特開平8-221270号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
低速な主記憶へアクセスする代わりに、高速なキャッシュメモリ上の対応するデータにアクセスすることで、一般にキャッシュヒット率が向上する。キャッシュヒット率が向上することで、計算機システム全体の性能を向上することができる。
キャッシュメモリにおいては、キャッシュミス時などには、ラインのデータを入れ換えるリフィルという処理を行う。このリフィルの最中であっても、キャッシュヒット扱いしてアクセスを許可しても問題がない場合も潜在している。しかしながら、前記従来の技術では、リフィルの最中においては、リフィル中のラインへのアクセスはキャッシュミスと扱っており、主記憶へアクセスをする必要があるという課題を有している。
【０００５】
このような背景のもとで、本発明は、よりキャッシュヒット率を向上させたキャッシュメモリを提供することを目的としている。
【課題を解決するための手段】
【０００６】
本発明に係るキャッシュメモリは、それぞれ複数のワードを含む複数のラインと、前記ラインに格納されたデータの主記憶におけるアドレスを示すタグと、前記ライン毎にラインがリフィル中であるか否かを示すリフィルビットと、前記ワード毎にワードにおけるデータがダーティであるか否かを示すダーティビットとを格納するタグ格納部と、リードアクセス対象のタグアドレスと、前記タグに示されるアドレスとが一致し、リードアクセス対象に係るラインに対応するリフィルビットがリフィル中を示し、かつ、当該ラインに含まれリードアクセス対象に係るワードに対応するダーティビットがダーティを示していれば、リードヒットと判定するヒット判定手段とを備えることを特徴としている。
【０００７】
また、前記ヒット判定手段は、ライトアクセス対象に係るラインのアドレスと、前記タグに示されるアドレスが一致するラインであって、当該ラインに対応するリフィルビットがリフィル中であることを示す場合には、ライトヒットと判定するとしても構わない。
また、前記ヒット判定手段は、当該ワードに対応するダーティビットがダーティを示していなければ、リードミスヒットと判定するとしても構わない。
【０００８】
また、本発明に係るキャッシュメモリは、それぞれ複数のワードを含む複数のラインと、前記ラインに格納されたデータの主記憶におけるアドレスを示すタグと、前記ライン毎にラインがリフィル中であるか否かを示すリフィルビットと、前記ワード毎にワードにおけるデータがダーティであるか否かを示すダーティビットとを格納するタグ格納部と、ライトアクセス対象のタグアドレスと、前記タグに示されるアドレスとが一致し、当該ラインに対応するリフィルビットがリフィル中であることを示す場合には、ライトヒットと判定するヒット判定手段とを備えることを特徴とする。
【０００９】
さらに、前記ヒット判定手段によりライトヒットと判定された場合に、前記ライトアクセスに係るワードへの書き込みがあると、当該ワードに対応するダーティビットをアサートし、ラインのリフィルに際して、ダーティビットがダーティであることを示さないワードに対してはデータの上書きを許可し、前記アサートによりダーティであることを示すワードに対してはデータの上書きを禁止する制御手段を備えるとしても構わない。
【００１０】
また、本発明に係るキャッシュメモリシステムは、中央処理装置と、前記キャッシュメモリと、前記中央処理装置と前記キャッシュメモリと記憶階層において間の階層に位置し、前記中央処理装置が前記キャッシュメモリへとライトすべきデータを保持する第１ライトバッファと、前記キャッシュメモリとライトバック対象となるメモリと記憶階層において間の階層に位置し、前記キャッシュメモリから前記ライトバック対象となるメモリへとライトバックすべきデータを保持する第２ライトバッファと、前記キャッシュメモリと前記ライトバック対象となるメモリと記憶階層において間の階層に位置し、前記キャッシュメモリがリードすべきデータを保持するリードバッファとを備えることを特徴とする。
【発明の効果】
【００１１】
本発明に係るキャッシュメモリは、従来はリフィル中であるとリードミスヒットと判定していたのに対して、ラインがリフィル中という状況下においても、ヒット判定手段は、そのラインに含まれるワードに対応するダーティビットがダーティを示していれば、リードヒットと判定する。
この構成によれば、リードアクセス対象に係るラインがリフィル中という状況下においても、ヒット判定手段は、リードヒットと判定するので、キャッシュリードミスを減らし、キャッシュリードヒット率を向上できる。これにより、キャッシュリードミスに起因する計算機のオーバーヘッドを軽減することができる。
【００１２】
また、本発明に係るキャッシュメモリは、それぞれ複数のワードを含む複数のラインと、前記ラインに格納されたデータの主記憶におけるアドレスを示すタグと、前記ライン毎にラインがリフィル中であるか否かを示すリフィルビットと、前記ワード毎にワードにおけるデータがダーティであるか否かを示すダーティビットとを格納するタグ格納部と、ライトアクセス対象のタグアドレスと、前記タグに示されるアドレスとが一致し、当該ラインに対応するリフィルビットがリフィル中であることを示す場合には、ライトヒットと判定するヒット判定手段とを備えることを特徴とするとしている。
【００１３】
この構成によれば、ライトアクセス対象に係るラインがリフィル中という状況下においても、ヒット判定手段は、ライトヒットと判定するので、キャッシュライトヒット率を向上できる。
【発明を実施するための最良の形態】
【００１４】
以下、図面を用いて本発明の実施の形態について説明する。また、本実施の形態におけるライトバック方式のキャッシュメモリは、ダイレクトマップ方式を採用しており、キャッシュのライトミス時には、ライトアロケート方式（先に新しいラインをキャッシュメモリに書き込み、その後で書き込みヒット時の動作を行う方式である。）で処理を行うとして説明する。
【００１５】
図１は、キャッシュメモリシステム１の構成図である。
キャッシュメモリシステム１は、ＣＰＵ２、主記憶４、キャッシュメモリ６、ライトバッファ８，１０、リードバッファ１２を含んで構成している。
ＣＰＵ２は、各種演算処理を行う中央処理装置である。
主記憶４は、DRAMなどデータを一時記憶する揮発性メモリから構成される。
【００１６】
キャッシュメモリ６は、主記憶４に格納すべきデータを一時的に格納する。主記憶４よりアクセス速度が速く、記憶階層の構造上、上位のＣＰＵ２と下位の主記憶４との間に介在している。キャッシュメモリ６はライトバック方式であり、キャッシュミス発生時などを契機として保持しているデータを主記憶４へと書き戻す。
キャッシュメモリ６は、制御部６ａ、格納部６ｂ、ヒット判定部６ｃ、調停部６ｄを備える。
【００１７】
制御部（キャッシュメモリ制御部）６ａは、各機能ブロックを制御し、例えば格納部６ｂに格納されたデータの読み書きやタグの更新を行う。また、ヒット判定部６ｃのヒット判定結果に応じてＣＰＵ２にデータを出力する。
格納部６ｂは、データを格納するデータ格納部と、格納されたデータを識別する情報としてのタグを含むタグ格納部とから構成される。
【００１８】
ヒット判定部６ｃは、ＣＰＵ２からのアクセス対象となったデータが、格納部６ｂに格納されているかどうかのヒット判定を行う。詳しくは後述する。
調停部６ｄは、格納部６ｂ内のデータ格納部へのデータへのアクセスが競合する場合などに調停する。
図２は、キャッシュメモリ６の構成を示す図である。
【００１９】
図２上部のアドレス２２は、ＣＰＵ２がキャッシュメモリ６へとアクセスを試みる際に、ＣＰＵ２からリード／ライト要求とともに出力されるアドレスを示している。
アドレス（AD[31:0]）２２は、32ビットであり、上位16ビット(AD[31:16])をタグアドレスとして、ビット4からビット15の12ビット（AD[15:4]）をインデックスアドレスとして、ビット2からビット3の2ビット（AD[3:2]）をラインに含まれるワードを特定するワードアドレスとして利用する。なお、インデックスアドレスは12ビットであるので、4096(=2^12)本のラインを指定することができる。このインデックスアドレスによりアクセス対象のラインが一意に特定されることとなる。
【００２０】
キャッシュメモリ６は、タグ格納部１４、データ格納部１６、セレクタ１８、ヒット判定器２０を含む。
タグ格納部１４は、データ格納部１６における4096本のラインに対応して設けられており、ラインに格納されたデータなどの識別情報を格納している。
具体的には、タグ格納部１４は、ラインのデータが有効であるか否かを示すバリッドビット(V)、ラインがリフィル中であるか否かを示すリフィルビット(R)、ラインに格納されたデータの主記憶におけるアドレスを示すタグビット(Tag)を有する。
【００２１】
これに加えて、タグ格納部１４は、ラインに含まれる４つのワード（Word0,Word1,Word2,Word3）に対応してそれぞれ設けられた４つのダーティビット(D0,D1,D2,D3)を含んでいる。ダーティビットがダーティならば、対応するワードは、更新されたが主記憶には未だ書き戻されていない状態であることを意味しているので、適宜、主記憶に書き戻す必要がある。
【００２２】
データ格納部１６は、４つのワードを1ラインとした4096本のラインを保持している。データ格納部１６は、タグ格納部１４とは別個のメモリとしてＳＲＡＭなどにより構成される。なお、１ワードあたりのサイズは、ＣＰＵ２からのアクセスのビット幅に対応して32ビットであり、データ格納部１６の入出力ポートのビット幅も32ビット（１ワード分）である。
【００２３】
セレクタ１８は、アドレス２２の2ビット（AD[3:2]）に基づいて、4つのワードのうちの1つのワードを選択する。
ヒット判定器２０には、リードかライトを示す信号（Read or Write）、タグアドレス（AD[31:16]）、インデックスアドレス（AD[15:4]）により特定されたラインのバリッドビット(V)、リフィルビット(R)、4つのワード毎のダーティビット(D0,D1,D2,D3)、上記ラインに格納されたデータのアドレスを示すタグビット(Tag)、4つのワードのうちの１つを特定するワードアドレス（AD[3:2]）、の10個の入力に基づいてヒットかミスヒットかを判定する。
【００２４】
ヒット判定器２０の回路構成例を図３に示す。
ヒット判定器２０は、２入力１出力のAND回路２３，２４，２６，２８，３０、３入力１出力のOR回路３２、NOT回路３４，３６、４入力１出力のセレクタ３８、コンパレータ４０を備える。
セレクタ３８は、2ビット（AD[3:2]）の入力に基づいて、D0，D1，D2，D3の４つのうちの１つを選択して出力する。すなわち、ラインに含まれるアクセス対象のワードを特定する入力（AD[3:2]）に基づいて、そのワードに対応するダーティビットを出力することとなる。
【００２５】
コンパレータ４０は、タグビット（Tag）と、タグアドレス（AD[31:16]）とを比較し一致した場合にHIGH出力となる。
図４は、図３のヒット判定器２０が入力に応じて出力する判定結果を示す表５０である。
入力される値の組み合わせに応じて（ａ）から（ｈ）までの８つの場合がある。各場合について順に説明する。なお、リフィル中でない（ａ）、（ｂ）、（ｄ）、（ｅ）、（ｆ）、（ｈ）の場合のヒット判定は基本的には従来と同様である。リフィル中の（ｃ）、（ｇ）の場合が特徴的である。
【００２６】
（ａ）の場合・・・ライトアクセス対象のデータのアドレス２２に含まれるタグアドレス（AD[31:16]）とタグビット（Tag）とが一致し、リフィル中で無く(R=0)、バリッドビットが有効(V=1)な場合であり、ライトヒットとなる。そして、キャッシュメモリ６は、ワードアドレス（AD[3:2]）に示されるワードに書き込み、同時に書き込んだワードに対応するダーティビットをアサートする。
【００２７】
（ｂ）の場合・・・バリッドビットが無効（V=0）であるところだけが（ａ）と異なる場合であり、V=0でデータが無効であるので、ライトミスとなる。
ここで、ライトミスヒットしたデータは、一旦ライトバッファ８に保持し、リフィルの完了を待ってキャッシュメモリ６へと書き込むこととなる。特に本実施の形態では、ライトミスヒットしたデータはキャッシュメモリ６にライトしておく。ライト時には、ライトしたワード毎のダーティビットをダーティに更新し、タグビット(Tag)をライトミスヒットしたアクセスのアドレスに更新する。これに先立って、ライトアクセス対象のラインをリフィルするために、主記憶4へのバスにデータリード要求とアドレスとを出力する。なお、このとき、リードバッファ１２に空きが無い場合には、空くまでリード要求の出力を待つか、リードデータが主記憶４から返ってくるよりも以前にリードバッファ１２が空くことが確定できるまでリード要求の出力を待つ。
【００２８】
（ｃ）の場合・・・ライトアクセス対象のデータのタグビット（Tag）とタグアドレス（AD[31:16]）とが一致し、リフィル中(R=1)の場合であり、ライトヒットとなる。そして、キャッシュメモリ６は、ワードアドレス(AD[3:2])に示されるワードに書き込み、書き込んだワードに対応するダーティビットをアサートする。
（ｄ）の場合・・・リードアクセス対象のデータのタグビット（Tag）とタグアドレス（AD[31:16]）とが一致し、リフィル中で無く(R=0)、バリッドビットが有効(V=1)な場合であり、リードヒットとなる。ＣＰＵ２はワードアドレス（AD[3:2]）に示されるワードのデータを読み出すこととなる。
【００２９】
（ｅ）の場合・・・バリッドビットは無効（V=0）であるところだけが（ｄ）と異なる場合であり、V=0でデータが無効であるので、リードミスとなる。
（ｆ）の場合・・・リードアクセス対象のデータのタグビット（Tag）とタグアドレス（AD[31:16]）とが一致し、リフィル中(R=1)であり、ワードアドレス（AD[3:2]）に示されるワード（図４ではW0）に対応するダーティビット（図４ではD0）がダーティではない（クリーンである）場合である。この場合は、ミスヒットとなり、キャッシュメモリ６の制御部６ａは、リフィル中である旨をＣＰＵ２に通知する。ＣＰＵ２は通知がリフィル中で無くなるまで待機（リフィル完了まで待機）し、リフィル完了後にリードヒットとしてリードヒット時の動作（リフィル済のリードアクセス対象のデータを読み出す）をするか、このミスヒットしたリードアクセスが完了しなくとも進められる後続の処理に移ることとなる。
【００３０】
（ｇ）の場合・・・リードアクセス対象のデータのタグビット（Tag）とタグアドレス（AD[31:16]）とが一致し、リフィル中(R=1)であり、ワードアドレス（AD[3:2]）に示されるワード（図４ではW2）に対応するダーティビット（図４ではD2）がダーティな場合である。この場合は、リードヒットとなり、ＣＰＵ２は、ワードアドレス（AD[3:2]）に示されるワードのデータを読み出す。
【００３１】
（ｈ）の場合・・・タグビット（Tag）とタグアドレス（AD[31:16]）とが一致していない場合である。これは、アクセス対象のデータのアドレスとデータ格納部に実際に格納されているデータのアドレスとが異なることを意味するので、他の条件を判断するまでもなく、ライト・リードに関わらずミスヒットとなる。
以上説明したように、ヒット判定器２０は、（ｇ）の場合のように、リフィル中であったとしても、リードアクセス対象のワードに対応するダーティビットがダーティであればリードヒットとして判定するので、従来よりリードヒット率を向上させることができる。
【００３２】
また、ヒット判定器２０は、（ｃ）の場合のように、リフィル中であったとしても、ライトヒットとして判定するので、従来よりライトヒット率を向上させることができる。
次に、ＣＰＵ２、キャッシュメモリ６、主記憶４の処理の流れについて、ライトアクセス時とリードアクセス時を分けて順に説明する。
図５は、ライトアクセス時におけるＣＰＵ２、キャッシュメモリ６、主記憶４のシーケンス図である。なお、初期状態において、ライトアクセス要求の対象となるラインはリフィル中でない（R=0）として説明する。
【００３３】
ＣＰＵ２がライトアクセス要求するデータは、一旦ライトバッファ８で保持する。そして、ライトバッファ８は、キャッシュメモリへのライトアクセス要求とともに、データとこのデータのアドレス（AD[31:0]）２２とをキャッシュメモリ６へと送る（S0）。
ライトアクセス要求を受けたキャッシュメモリ６のヒット判定器２０は、前述のようにライトバッファ８から送られたデータのアドレス（AD[31:0]）２２のタグアドレス（AD[31:16]）とライトアクセス要求の対象となったデータのラインのタグビット（Tag）との比較や、ラインのリフィルビット（R）などに基づいて、ヒット判定を行う。
【００３４】
ライトヒットと判定すれば（S1:Yes）、ライトアクセス要求の対象となるラインのワードにデータを書き込み、必要に応じてそのワードに対応するダーティビットをアサートする（S11）。
ライトミスと判定すれば（S1:No）、キャッシュメモリ６は、ラインのリフィルビットをアサートし(S2:R=1)、ライトバック処理(S3-S8)に移行する。この時、ライトミスしたライトアクセス要求のタグアドレス(AD[31:16])で、タグビット(Tag)を更新する。
【００３５】
ライトバック処理(S3-S8)では、バリッドビットが無効であれば(S3:No,V=0)、ラインが無効であり書き戻すべきデータが無いので処理を終える。
バリッドビットが有効であれば(S3:Yes,V=1)、ライン中のワードにおいて、ワードに対応するダーティビットがダーティ(D=1)なワードだけをライトバッファ１０に書き戻す(S4,S5)。書き戻しを終えたワードに対応するダーティビットはクリーン(D=0)にネゲートする(S6)。
【００３６】
なお、ライトバッファ１０に書き戻されたデータは、バスが空いているときなど適当なタイミングで主記憶４へとさらにライトバックされることとなる。
ラインに含まれる4つのワードについてＳ４からＳ６までの処理を終えると(S7:Yes)、ラインのバリッドビットを無効化(S8:V=0)する。
ライトバック処理(S3-S8)を終えると、キャッシュメモリ６は、リフィル・タグ更新を行う(S9)。具体的には、リードバッファ１２が主記憶４から読み出し済みのライトアクセス対象のラインのデータを、キャッシュメモリ６のラインに上書きする。
【００３７】
このリフィルでは、D=0のワードのみ上書きし、書き戻しされていないワードの上書きを回避する。
キャッシュメモリ６は、リードバッファ１２からの読み込みを完了すると（S9）、ラインを有効化し(S10:V=1)、リフィルビットをネゲート(S10:R=0)して一連のリフィルを終了する。
【００３８】
なお、図５のフローでは、まず先にライトバック処理(S3-S8)を行い、その後でリフィルの処理を行う(S9)として説明したが、両処理はこれに限らず並行して行っても構わない。
図６は、リードアクセス時におけるＣＰＵ２、キャッシュメモリ６、主記憶４のシーケンス図である。なお、初期状態において、リードアクセス要求の対象となるラインはリフィル中でない（R=0）として説明する。
【００３９】
ＣＰＵ２がキャッシュメモリ６にリードアクセスを要求すると(S20)、要求を受けたキャッシュメモリ６はヒット判定器２０において前述のヒット判定を行う。
リードヒットと判定すれば（S21:Yes）、ＣＰＵ２は、リードアクセス要求の対象となるラインのワードからデータを読み出す。
リードミスヒットと判定すれば（S21:No）、S２からS１０までのリフィル処理に移行する。この処理は図５を用いて既に説明したものと同様であるので説明を省略する。
【００４０】
次に、キャッシュメモリ６のあるラインがリフィル中の場合に、このライン中のワードへのライト／リードアクセスがあったときの例について説明する。
図７は、あるラインのワード（W0,W1,W2,W3）のリフィルを時系列上で説明する図である。（ａ）を用いてライトアクセス時の処理について説明し、（ｂ）を用いてリードアクセス時の処理について説明する。
【００４１】
ライトアクセス時は、図７（ａ）に示すように、キャッシュメモリ６は、ｔ０→ｔ１→ｔ２→ｔ３→ｔ４の間に、それぞれW0→W1→W2→W3の順番でリフィルが完了するものとする。また、リフィル開始時にはリフィルビットをアサートし、リフィルすべき新しいラインのアドレスにラインのタグビット(Tag)を更新する。
本実施の形態においては、リフィル途中にも関わらずライトアクセス要求を受けてデータの上書きを許容するので、ラインのタグビット(Tag)が、現実に上書きしたデータのタグと不一致にならないように、図７（ａ）に示すように、リフィル開始時にタグを更新する。
【００４２】
まず、ｔ０からｔ２までの間にワードW2へのライトアクセス要求があった場合には、ヒット判定器２０は前述のようにライトヒットと判定し、ワードW2へのライトアクセスを受けて対応するダーティビット(D2)をアサートする。その後、ｔ２からｔ３の間は、ワードW2のダーティビット(D2)がアサートされているので、キャッシュメモリ６は、ワードW2への上書きを行わない。
【００４３】
なお、上書きを行わない方法としては、例えば、ライトアクセスは行うが、ワードへの書き込みをマスクする信号を利用することが考えられる。また、ワードへのライトアクセス自体を行わずに処理をスキップしてもよい。
次に、ｔ２からｔ３までの間にワードW2へのライトアクセス要求があった場合には、ライトヒットと判定し、ワードW2へのライトアクセスを受けて対応するダーティビット(D2)をアサートする。この場合、ライトアクセス要求時には、ワードW2は既にリフィル中であるので、キャッシュメモリ６はライト制御を調停して両者の競合を防ぐ。
【００４４】
そして、ｔ３からｔ４までの間にワードW2へのライトアクセス要求があった場合には、ライトヒットと判定し、ワードW2へのライトアクセスを受けて対応するダーティビット(D2)をアサートする。
リードアクセス時は、図７（ｂ）に示すように、図７（ａ）同様に、キャッシュメモリ６は、ｔ０→ｔ１→ｔ２→ｔ３→ｔ４の間に、それぞれW0→W1→W2→W3の順番でリフィルが完了するものとする。
【００４５】
まず、ｔ０からｔ４までの間にワードW2へのリードアクセス要求があった場合、ワードW2に対応するダーティビットが有効であるならば、ヒット判定器２０は前述のようにリードヒットと判定し、ワードW2へのリードアクセスを受け付ける。
これに対して、ｔ０からｔ４までの間にワードW2へのリードアクセス要求があった場合で、ワードW2に対応するダーティビットが無効ならば、ヒット判定器２０は前述のようにリードミスヒットと判定する。ＣＰＵ２は、リフィル完了まで待つこととなる。
【００４６】
＜補足＞
以上、本発明の実施の形態について説明したが、本発明は上記の内容に限定されず、本発明の目的とそれに関連または付随する目的を達成するための各種形態においても実施可能であり、例えば、以下であってもよい。
（１）実施の形態では、ダイレクトマップ方式のキャッシュメモリを例に挙げて説明したが、この方式に限らずフルアソシアティブ方式やセットアソシアティブ方式を採用したキャッシュメモリを用いても構わない。これらの方式の場合には、ライトミスヒット時のリフィル対象のラインがダイレクトマップ方式のように一意のラインに決まるのではなく、LRU（Least Recently Used）方式やラウンドロビン方式などのアルゴリズムなどに基づいて行われる点が異なってくる。
【００４７】
また、共有バスを介して複数のキャッシュメモリが下位層の単一のメモリを共有するような共有メモリ型のキャッシュメモリシステムにおいても、ライトバックキャッシュメモリを構成、制御する方法として本発明を適用することができる。
（２）実施の形態では、対応するダーティビットがダーティなワードのみをライトバックする例について説明したが、ダーティワードを含む数ワード、もしくはラインに含まれるワードすべてをライトバックするとしてもよい。また書き戻しの際には、周知の技術のように、ライトバッファ１０に積まれたデータが主記憶４に書き戻されるよりも以前に、書き戻されるアドレスのデータが主記憶４から読み出されることが無いようにシステム全体は制御することができる。
【００４８】
（３）実施の形態では、図１に示すように、キャッシュメモリ６の入出力につながるパスにライトバッファ８，１０とリードバッファ１２を配することで、中央処理装置からキャッシュメモリへのライトアクセス、キャッシュメモリから主記憶へのライトアクセス、主記憶からキャッシュメモリへのライトアクセスが緩衝され、より柔軟なキャッシュメモリ制御が可能となる。
【００４９】
（４）実施の形態では、特に詳細を述べなかったが、システム全体へのオーバーヘッドを軽減する別のアプローチとして、ライトバッファを配置して制御系に工夫を施すことも考えられる。具体的には、ライトミスへの対応として、上位層メモリとキャッシュメモリとの間に多機能なライトバッファを配置し、リフィル中のラインへのライトは、上記ライトバッファにあるデータに対して上書き更新し、リフィル中のラインのリードは、上記ライトバッファから読み出すという制御を行うというものである。しかし、この制御は非常に複雑なものとなる。
【００５０】
これに対して、実施の形態では、ヒット判定器２０のヒット判定という簡単な制御を通してシステム全体へのオーバーヘッドを軽減することが可能となる。
（５）階層メモリシステムとして、中央処理装置、キャッシュメモリ、主記憶の構成を例示したが、さらに深い階層構成のメモリシステムのキャッシュメモリとしてもよい。例えば、キャッシュメモリが、１次キャッシュメモリと２次キャッシュメモリとから構成される場合がある。この場合、本実施の形態を、１次キャッシュメモリに適用してもよいし、２次キャッシュメモリに適用してもよい。
【産業上の利用可能性】
【００５１】
本発明のキャッシュメモリは、一般的な半導体回路内部に存在するキャッシュメモリとして利用でき、キャッシュヒット率を向上できるので有用である。
【図面の簡単な説明】
【００５２】
【図１】キャッシュメモリシステム１の構成図
【図２】キャッシュメモリ６の構成を示す図
【図３】ヒット判定器２０の回路構成例
【図４】図３のヒット判定器２０が入力に応じて出力する判定結果を示す表５０の図
【図５】ライトアクセス時におけるＣＰＵ２、キャッシュメモリ６、主記憶４のシーケンス図
【図６】リードアクセス時におけるＣＰＵ２、キャッシュメモリ６、主記憶４のシーケンス図
【図７】あるラインのワード（W0,W1,W2,W3）のリフィルを時系列上で説明する図
【符号の説明】
【００５３】
１ キャッシュメモリシステム
２ ＣＰＵ
４ 主記憶
６ キャッシュメモリ
８ ライトバッファ
１０ ライトバッファ
１２ リードバッファ
１４ タグ格納部
２０ ヒット判定器
２２ アドレス
【特許請求の範囲】
【請求項１】
それぞれ複数のワードを含む複数のラインと、
前記ラインに格納されたデータの主記憶におけるアドレスを示すタグと、前記ライン毎にラインがリフィル中であるか否かを示すリフィルビットと、前記ワード毎にワードにおけるデータがダーティであるか否かを示すダーティビットとを格納するタグ格納部と、
リードアクセス対象のタグアドレスと、前記タグに示されるアドレスとが一致し、
リードアクセス対象に係るラインに対応するリフィルビットがリフィル中を示し、
かつ、当該ラインに含まれリードアクセス対象に係るワードに対応するダーティビットがダーティを示していれば、
リードヒットと判定するヒット判定手段と
を備えることを特徴とするキャッシュメモリ。
【請求項２】
前記ヒット判定手段は、ライトアクセス対象に係るラインのアドレスと、前記タグに示されるアドレスが一致するラインであって、当該ラインに対応するリフィルビットがリフィル中であることを示す場合には、ライトヒットと判定する
ことを特徴とする請求項１に記載のキャッシュメモリ。
【請求項３】
前記ヒット判定手段は、当該ワードに対応するダーティビットがダーティを示していなければ、リードミスヒットと判定する
ことを特徴とする請求項１に記載のキャッシュメモリ。
【請求項４】
それぞれ複数のワードを含む複数のラインと、
前記ラインに格納されたデータの主記憶におけるアドレスを示すタグと、前記ライン毎にラインがリフィル中であるか否かを示すリフィルビットと、前記ワード毎にワードにおけるデータがダーティであるか否かを示すダーティビットとを格納するタグ格納部と、
ライトアクセス対象のタグアドレスと、前記タグに示されるアドレスとが一致し、
当該ラインに対応するリフィルビットがリフィル中であることを示す場合には、
ライトヒットと判定するヒット判定手段と
を備えることを特徴とするキャッシュメモリ。
【請求項５】
さらに、前記ヒット判定手段によりライトヒットと判定された場合に、前記ライトアクセスに係るワードへの書き込みがあると、当該ワードに対応するダーティビットをアサートし、
ラインのリフィルに際して、ダーティビットがダーティであることを示さないワードに対してはデータの上書きを許可し、前記アサートによりダーティであることを示すワードに対してはデータの上書きを禁止する制御手段を備える
ことを特徴とする請求項４に記載のキャッシュメモリ。
【請求項６】
中央処理装置と、
請求項１または４に記載のキャッシュメモリと、
前記中央処理装置と前記キャッシュメモリと記憶階層において間の階層に位置し、前記中央処理装置が前記キャッシュメモリへとライトすべきデータを保持する第１ライトバッファと、
前記キャッシュメモリとライトバック対象となるメモリと記憶階層において間の階層に位置し、前記キャッシュメモリから前記ライトバック対象となるメモリへとライトバックすべきデータを保持する第２ライトバッファと、
前記キャッシュメモリと前記ライトバック対象となるメモリと記憶階層において間の階層に位置し、前記キャッシュメモリがリードすべきデータを保持するリードバッファと
を備えることを特徴とするキャッシュメモリシステム。
【請求項１】
それぞれ複数のワードを含む複数のラインと、
前記ラインに格納されたデータの主記憶におけるアドレスを示すタグと、前記ライン毎にラインがリフィル中であるか否かを示すリフィルビットと、前記ワード毎にワードにおけるデータがダーティであるか否かを示すダーティビットとを格納するタグ格納部と、
リードアクセス対象のタグアドレスと、前記タグに示されるアドレスとが一致し、
リードアクセス対象に係るラインに対応するリフィルビットがリフィル中を示し、
かつ、当該ラインに含まれリードアクセス対象に係るワードに対応するダーティビットがダーティを示していれば、
リードヒットと判定するヒット判定手段と
を備えることを特徴とするキャッシュメモリ。
【請求項２】
前記ヒット判定手段は、ライトアクセス対象に係るラインのアドレスと、前記タグに示されるアドレスが一致するラインであって、当該ラインに対応するリフィルビットがリフィル中であることを示す場合には、ライトヒットと判定する
ことを特徴とする請求項１に記載のキャッシュメモリ。
【請求項３】
前記ヒット判定手段は、当該ワードに対応するダーティビットがダーティを示していなければ、リードミスヒットと判定する
ことを特徴とする請求項１に記載のキャッシュメモリ。
【請求項４】
それぞれ複数のワードを含む複数のラインと、
前記ラインに格納されたデータの主記憶におけるアドレスを示すタグと、前記ライン毎にラインがリフィル中であるか否かを示すリフィルビットと、前記ワード毎にワードにおけるデータがダーティであるか否かを示すダーティビットとを格納するタグ格納部と、
ライトアクセス対象のタグアドレスと、前記タグに示されるアドレスとが一致し、
当該ラインに対応するリフィルビットがリフィル中であることを示す場合には、
ライトヒットと判定するヒット判定手段と
を備えることを特徴とするキャッシュメモリ。
【請求項５】
さらに、前記ヒット判定手段によりライトヒットと判定された場合に、前記ライトアクセスに係るワードへの書き込みがあると、当該ワードに対応するダーティビットをアサートし、
ラインのリフィルに際して、ダーティビットがダーティであることを示さないワードに対してはデータの上書きを許可し、前記アサートによりダーティであることを示すワードに対してはデータの上書きを禁止する制御手段を備える
ことを特徴とする請求項４に記載のキャッシュメモリ。
【請求項６】
中央処理装置と、
請求項１または４に記載のキャッシュメモリと、
前記中央処理装置と前記キャッシュメモリと記憶階層において間の階層に位置し、前記中央処理装置が前記キャッシュメモリへとライトすべきデータを保持する第１ライトバッファと、
前記キャッシュメモリとライトバック対象となるメモリと記憶階層において間の階層に位置し、前記キャッシュメモリから前記ライトバック対象となるメモリへとライトバックすべきデータを保持する第２ライトバッファと、
前記キャッシュメモリと前記ライトバック対象となるメモリと記憶階層において間の階層に位置し、前記キャッシュメモリがリードすべきデータを保持するリードバッファと
を備えることを特徴とするキャッシュメモリシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１１−２４８３８９（Ｐ２０１１−２４８３８９Ａ）
【公開日】平成２３年１２月８日（２０１１．１２．８）
【国際特許分類】
【出願番号】特願２００８−２３１４６１（Ｐ２００８−２３１４６１）
【出願日】平成２０年９月９日（２００８．９．９）
【出願人】（０００００５８２１）パナソニック株式会社 (73,050)
【Ｆターム（参考）】
【公開日】平成２３年１２月８日（２０１１．１２．８）
【国際特許分類】
【出願日】平成２０年９月９日（２００８．９．９）
【出願人】（０００００５８２１）パナソニック株式会社 (73,050)
【Ｆターム（参考）】
[ Back to top ]