(57)【要約】【課題】メインメモリへのデータ書き戻しにかかる時間を短縮できるキャッシュメモリ装置を提供する。【解決手段】アドレス、ダーティビット、有効ビット及びデータを含むキャッシュラインを複数有する記憶部２と、書き戻しアドレス範囲を出力する演算部１と、前記記憶部が有するキャッシュラインを重複無く乱数的に又は一定の規則性をもって指定し、指定されたキャッシュラインに含まれるアドレスが前記書き戻しアドレス範囲内であるか、及びデータがダーティかつ有効であるかの検出を行い、前記記憶部へ書き戻し実行信号を出力する書き戻し制御回路３と、を備える。【選択図】図１
2008107905.tif 000002
【特許請求の範囲】
【請求項１】
アドレス、ダーティビット、有効ビット及びデータを含むキャッシュラインを複数有する記憶部と、
前記キャッシュラインをランダムに指定し、指定された前記キャッシュラインに含まれる前記アドレス、ダーティビット及び有効ビットに基づいて書き戻しを行うか否かの判定を行う制御部と、
を備えることを特徴とするキャッシュメモリ装置。
【請求項２】
アドレス、ダーティビット、有効ビット及びデータを含むキャッシュラインを複数有する記憶部と、
書き戻しアドレス範囲を出力する演算部と、
前記記憶部が有するキャッシュラインを指定するインデックスをランダムに出力し、前記指定されたキャッシュラインに含まれるアドレスが前記書き戻しアドレス範囲内であるか、前記ダーティビット及び前記有効ビットから前記指定されたキャッシュラインに含まれるデータがダーティかつ有効であるかの検出を行い、前記記憶部へ書き戻し実行信号を出力する書き戻し制御回路と、
を備えることを特徴とするキャッシュメモリ装置。
【請求項３】
インデックスをランダムに出力する乱数発生装置と、
アドレス、ダーティビット、有効ビット及びデータをそれぞれ含む複数のキャッシュラインとキャッシュラインインデックスとを有するキャッシュデータ保持部と、入力された前記インデックスと同じ前記キャッシュラインインデックスのキャッシュラインを指定し、前記指定されたキャッシュラインが有する前記アドレス、ダーティビット、及び有効ビットを取り出し、出力し、前記指定されたキャッシュラインの書き戻しまたは無効化を行うキャッシュ制御部と、を有するキャッシュメモリと、
書き戻しアドレス範囲または無効化アドレス範囲を出力する演算部と、
前記指定されたキャッシュラインに含まれる前記アドレスが前記書き戻しアドレス範囲内であるか、前記ダーティビットが前記指定されたキャッシュラインに含まれるデータがダーティであることを示しているか、及び前記有効ビットが前記指定されたキャッシュラインに含まれるデータが有効であることを示しているかの検出をし、検出結果に基づいて前記キャッシュ制御部へ書き戻し実行信号を出力する、又は前記指定されたキャッシュラインに含まれる前記アドレスが前記無効化アドレス範囲内であるか、及び前記有効ビットが前記指定されたキャッシュラインに含まれるデータが有効であることを示しているかの検出をし、検出結果に基づいて前記キャッシュ制御部へ無効化実行信号を出力するアドレス範囲内検出部と、
を備えることを特徴とするキャッシュメモリ装置。
【請求項４】
インデックスをランダムに出力する乱数発生装置と、
アドレス、ダーティビット、有効ビット及びデータをそれぞれ含む複数のキャッシュラインとキャッシュラインインデックスとを有するキャッシュデータ保持部と、入力された前記インデックスと同じ前記キャッシュラインインデックスのキャッシュラインを指定し、前記指定されたキャッシュラインが有する前記アドレス、ダーティビット、及び有効ビットを取り出し、出力し、前記指定されたキャッシュラインの書き戻しまたは無効化を行うキャッシュ制御部と、を有するキャッシュメモリと、
書き戻しアドレス範囲または無効化アドレス範囲をそれぞれ独立して出力するｎ個（ｎは２以上の整数）の演算部と、
前記指定されたキャッシュラインに含まれる前記アドレスが前記書き戻しアドレス範囲内であるか、前記ダーティビットが前記指定されたキャッシュラインに含まれるデータがダーティであることを示しているか、及び前記有効ビットが前記指定されたキャッシュラインに含まれるデータが有効であることを示しているかの検出をし、検出結果に基づいて前記キャッシュ制御部へ書き戻し実行信号を出力する、又は前記指定されたキャッシュラインに含まれる前記アドレスが前記無効化アドレス範囲内であるか、及び前記有効ビットが前記指定されたキャッシュラインに含まれるデータが有効であることを示しているかの検出をし、検出結果に基づいて前記キャッシュ制御部へ無効化実行信号を出力するアドレス範囲内検出部と、
を備えることを特徴とするキャッシュメモリ装置。
【請求項５】
前記乱数発生装置は、
初期化信号及び更新信号が入力され、前記初期化信号及び更新信号に基づいてＭ系列信号を生成し、出力をするＭ系列発生器と、
前記Ｍ系列信号が入力され、前記Ｍ系列の系列長に応じて出力するフラグの値を変化させるフラグ出力部と、
前記Ｍ系列信号及び所定値が入力され、前記フラグに基づいてどちらか一方を選択し前記インデックスとして出力する選択器と、
を有することを特徴とする請求項３又は４に記載のキャッシュメモリ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュメモリ装置に関するものである。
【背景技術】
【０００２】
プロセッサの処理性能を上げるため、動作速度の遅いメインメモリ（主記憶領域）とプロセッサとの間に高速アクセスが可能なキャッシュメモリを設け、プロセッサがメインメモリにアクセスする頻度を少なくすることが行われている。
【０００３】
キャッシュメモリに対するデータの書き込み方式にはライトスルー方式とライトバック方式がある。ライトスルー方式は、メインメモリへの書き込みが発生したときに、キャッシュメモリとメインメモリの両方に対して書き込みを行う方式である。
【０００４】
ライトバック方式は、メインメモリへの書き込みが発生したときに、まず、キャッシュメモリにのみ書き込みを行い、次にメインメモリへ書き込みを行う方式である。このライトバック方式は、読み出し時間だけでなく、書き込み時間をも短縮することができるため、キャッシュメモリの高速性を活かすことができる。しかし、このライトバック方式では、キャッシュメモリとメインメモリとの間のデータの整合性を取る制御を行う必要がある。例えば、キャッシュメモリのデータをフラッシュ（解放）するときなどは、キャッシュメモリを無効化した上で、キャッシュメモリのデータをメインメモリに書き戻す必要がある。
【０００５】
キャッシュメモリの無効化をする場合に無効化にかかる時間を短縮する技術として、ラインインデックスを生成するカウンタを用いてすべてのキャッシュラインのタグアドレスを順に読み出し、設定されたアドレスの範囲に該当するかをチェックし、該当するキャッシュラインを無効化するキャッシュメモリ装置が提案されている（例えば、特許文献１参照）。
【０００６】
しかし、上記のような方法をメインメモリへのデータの書き戻しに適用した場合、メインメモリへ書き戻すデータは連続したキャッシュラインに存在することが多いため、処理待ちが多く発生し、書き戻しに要する時間が長くなるという問題を有する。
【特許文献１】特開平８−３３５１８９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
そこで、本発明はメインメモリへのデータ書き戻しにかかる時間を短縮できるキャッシュメモリ装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一態様によるキャッシュメモリ装置は、アドレス、ダーティビット、有効ビット及びデータを含むキャッシュラインを複数有する記憶部と、前記キャッシュラインをランダムに指定し、指定された前記キャッシュラインに含まれる前記アドレス、ダーティビット及び有効ビットに基づいて書き戻しを行うか否かの判定を行う制御部と、を備えるものである。
【０００９】
また、本発明の一態様によるキャッシュメモリ装置は、アドレス、ダーティビット、有効ビット及びデータを含むキャッシュラインを複数有する記憶部と、書き戻しアドレス範囲を出力する演算部と、前記記憶部が有するキャッシュラインをランダムに指定し、指定されたキャッシュラインに含まれるアドレスが前記書き戻しアドレス範囲内であるか、前記ダーティビット及び前記有効ビットから前記指定されたキャッシュラインに含まれるデータがダーティかつ有効であるかの検出を行い、前記記憶部へ書き戻し実行信号を出力する書き戻し制御回路と、を備えるものである。
【００１０】
また、本発明の一態様によるキャッシュメモリ装置は、インデックスをランダムに出力する乱数発生装置と、アドレス、ダーティビット、有効ビット及びデータをそれぞれ含む複数のキャッシュラインとキャッシュラインインデックスとを有するキャッシュデータ保持部と、入力された前記インデックスと同じ前記キャッシュラインインデックスのキャッシュラインを指定し、前記指定されたキャッシュラインが有する前記アドレス、ダーティビット、及び有効ビットを取り出し、出力し、前記指定されたキャッシュラインの書き戻しまたは無効化を行うキャッシュ制御部と、を有するキャッシュメモリと、書き戻しアドレス範囲または無効化アドレス範囲を出力する演算部と、前記指定されたキャッシュラインに含まれる前記アドレスが前記書き戻しアドレス範囲内であるか、前記ダーティビットが前記指定されたキャッシュラインに含まれるデータがダーティであることを示しているか、及び前記有効ビットが前記指定されたキャッシュラインに含まれるデータが有効であることを示しているかの検出をし、検出結果に基づいて前記キャッシュ制御部へ書き戻し実行信号を出力する、又は前記指定されたキャッシュラインに含まれる前記アドレスが前記無効化アドレス範囲内であるか、及び前記有効ビットが前記指定されたキャッシュラインに含まれるデータが有効であることを示しているかの検出をし、検出結果に基づいて前記キャッシュ制御部へ無効化実行信号を出力するアドレス範囲内検出部と、を備えるものである。
【００１１】
また、本発明の一態様によるキャッシュメモリ装置は、インデックスをランダムに出力する乱数発生装置と、アドレス、ダーティビット、有効ビット及びデータをそれぞれ含む複数のキャッシュラインとキャッシュラインインデックスとを有するキャッシュデータ保持部と、入力された前記インデックスと同じ前記キャッシュラインインデックスのキャッシュラインを指定し、前記指定されたキャッシュラインが有する前記アドレス、ダーティビット、及び有効ビットを取り出し、出力し、前記指定されたキャッシュラインの書き戻しまたは無効化を行うキャッシュ制御部と、を有するキャッシュメモリと、書き戻しアドレス範囲または無効化アドレス範囲をそれぞれ独立して出力するｎ個（ｎは２以上の整数）の演算部と、前記指定されたキャッシュラインに含まれる前記アドレスが前記書き戻しアドレス範囲内であるか、前記ダーティビットが前記指定されたキャッシュラインに含まれるデータがダーティであることを示しているか、及び前記有効ビットが前記指定されたキャッシュラインに含まれるデータが有効であることを示しているかの検出をし、検出結果に基づいて前記キャッシュ制御部へ書き戻し実行信号を出力する、又は前記指定されたキャッシュラインに含まれる前記アドレスが前記無効化アドレス範囲内であるか、及び前記有効ビットが前記指定されたキャッシュラインに含まれるデータが有効であることを示しているかの検出をし、検出結果に基づいて前記キャッシュ制御部へ無効化実行信号を出力するアドレス範囲内検出部と、を備えるものである。
【発明の効果】
【００１２】
本発明によれば、キャッシュメモリからメインメモリへのデータ書き戻しにかかる時間を短縮できる。
【発明を実施するための最良の形態】
【００１３】
以下、本発明にかかるキャッシュメモリ装置の実施の形態を図面に基づいて説明する。
【００１４】
（第１の実施形態）図１に本発明の第１の実施形態に係るキャッシュメモリ装置０を含むキャッシュシステムの概略構成を示す。キャッシュメモリ装置０及びバスマスタ６はバス５を介してメインメモリ４に接続されている。キャッシュメモリ装置０はプロセッサ１、キャッシュメモリ２及び書き戻し制御回路３を有する。プロセッサ１はキャッシュメモリ２にアクセスし、キャッシュメモリ２が保持するデータの読み出し、キャッシュメモリ２へのデータ書き込みを行うことができる。書き戻し制御回路３はキャッシュメモリ２が保持するデータをランダムに選択し、選択したデータをメインメモリ４へ書き戻すかどうかの判定を行う。
【００１５】
キャッシュメモリ２は、キャッシュコントローラ１０及びキャッシュデータ保持部１１を有する。キャッシュコントローラ１０はキャッシュメモリ２のコントローラであり、プロセッサ１からのアクセスに応じて、例えばキャッシュデータ保持部１１に格納されるデータの読み出し等を実行する。
【００１６】
次に、キャッシュデータ保持部１１の構造を図２に示す。キャッシュデータ保持部１１は複数（ｎ個）のキャッシュラインからなり、各々のキャッシュラインは、データメモリ２５と、タグメモリ２６と、キャッシュラインインデックス２７とを有する。データメモリ２５は、メインメモリ４上のデータ２１を格納する。タグメモリ２６は、データ２１に対応するメインメモリ４上のアドレス２２、データ２１が有効か否かを示すバリッド（有効）ビット２４及びデータ２１をメインメモリ４へ書き戻す必要があるか否かを示すダーティビット２３を有する。
【００１７】
バリッドビット２４は、キャッシュライン上のデータをメインメモリ４上のデータとみなしてよいかを示すビットである。プロセッサ１がキャッシュメモリ２にアクセスしたとき、アクセスしたアドレスが対応するキャッシュラインのタグアドレス（タグメモリ２６が有するアドレス２２）と一致しており、かつこのキャッシュラインのバリッドビット２４が１である場合にのみキャッシュヒットとなり、プロセッサ１はこのキャッシュラインが有するデータ２１を用いることができる。
【００１８】
プロセッサ１がキャッシュメモリ２にアクセスしたとき、アクセスしたアドレスと対応するキャッシュラインのタグアドレス（タグメモリ２６が有するアドレス２２）が異なるとき、又はこのキャッシュラインのバリッドビット２４が０の場合はキャッシュミスとなり、プロセッサ１はこのキャッシュラインが有するデータ２１を用いることができない。その場合はキャッシュメモリ２（キャッシュコントローラ１０）はメインメモリ４上のデータをキャッシュライン上に取得し、プロセッサ１からのアクセスに対応する。さらに、キャッシュラインのタグアドレス２２をアクセスしたメインメモリ４のアドレスに設定し、バリッドビット２４を１とする。  
以後、バリッドビット２４が０の場合はデータ２１が無効と定義し、バリッドビット２４が１の場合はデータ２１が有効と定義する。
【００１９】
ダーティビット２３は、キャッシュライン上のデータ２１にプロセッサ１による書き込みが行われているかを示すビットである。ダーティビット２３が１の場合、このキャッシュラインのデータ２１とメインメモリ４上のデータとが一致しない可能性があるため、上記キャッシュミスの際には、このキャッシュライン上のデータをメインメモリ４へ書き戻して、プロセッサ１からのアクセスに対応するメインメモリ４上のデータを取得する。ダーティビット２３はメインメモリ４からデータをキャッシュライン上に取得した際に０となり、プロセッサ１からのデータ書き込みによって１となる。
【００２０】
キャッシュラインのアドレスをキャッシュラインインデックス２７といい、キャッシュラインを選択するために用いられる。
【００２１】
このような構成を備えるキャッシュメモリ装置０の動作について説明する。プロセッサ１が、メインメモリ４が保持するデータの読み出しアクセスを行うと、キャッシュコントローラ１０はアクセスされたメインメモリ４のアドレスに対応するデータを保持するかを調べる。アクセスされたメインメモリ４のアドレスに対応するデータを保持する場合は、キャッシュコントローラ１０はキャッシュラインインデックス２７の値をキャッシュデータ保持部１１に送り、当該キャッシュラインを特定する。キャッシュコントローラ１０は、当該キャッシュラインのタグメモリ２６とデータメモリ２５が格納するデータを読み出す。バリッドビット２４が１の場合は、キャッシュヒットとなり、データメモリ２５が格納するデータ２１をプロセッサ１に送信する。バリッドビット２４が０の場合、もしくは、アクセスされたメインメモリ４のアドレスに対応するデータを保持していない場合は、キャッシュミスとなり、キャッシュコントローラ１０はバス５を介してメインメモリ４に読み出しアクセスを行い、プロセッサ１が要求するデータを取得し、プロセッサ１に送信する。キャッシュコントローラ１０は、同時に、取得したデータとメインメモリ４のアドレスとを、キャッシュデータ保持部１１上の任意の１つのキャッシュラインに記憶させる。これは即ち、キャッシュコントローラ１０は、任意の１つのキャッシュライン上のデータ２１に取得したデータを格納し、アドレス２２にメインメモリ４のアドレスを格納する。このとき、キャッシュコントローラ１０はバリッドビット２４を１、ダーティビット２３を０にする。また、このキャッシュミスの際、キャッシュコントローラ１０はダーティビット２３が１になっているキャッシュライン上のデータをメインメモリ４に書き戻し、ダーティビット２３を０にする。
【００２２】
プロセッサ１がメインメモリ４へ書き込みアクセスを行うと、キャッシュコントローラ１０はアクセスされたメインメモリ４のアドレスに対応するデータを保持するかを調べる。アクセスされたメインメモリ４のアドレスに対応するデータを保持する場合は、キャッシュコントローラ１０はキャッシュラインインデックス２７の値をキャッシュデータ保持部に送り、当該キャッシュラインを特定する。キャッシュコントローラ１０は、プロセッサ１が送信する書き込みデータをデータ２１に格納する。このとき、キャッシュコントローラ１０はダーティビット２３を１にする。アクセスされたメインメモリ４のアドレスに対応するデータを保持していない場合は、プロセッサ１は書き込みデータを、キャッシュコントローラ１０を介して、メインメモリ４に書き込む。または、キャッシュコントローラ１０がバス５を介してメインメモリ４に読み出しアクセスを行い、プロセッサ１が書き込みを行うアドレスに対応するデータをメインメモリ４から読み出し、キャッシュデータ保持部１１上の任意の１つのキャッシュラインに記憶させると共に、プロセッサ１が送信する書き込みデータをこのキャッシュライン上のデータ２１に格納し、アドレス２２にメインメモリ４のアドレスを格納する。このとき、キャッシュコントローラ１０は、ダーティビット２３を１にする。
【００２３】
バス５にはキャッシュメモリ２を介さずにメインメモリ４にアクセスするバスマスタ６が接続されている。バスマスタ６は例えばＣＰＵやＩ／Ｏ装置である。キャッシュコントローラ１０はバスマスタ６によるメインメモリ４への書き込みアクセスを監視し、その書き込みアクセスによってメインメモリ４上のデータが更新されたとき、更新されたデータのメインメモリ４におけるアドレスと同じアドレスをアドレス２２に格納しているキャッシュラインがあるかどうかを調べる。メインメモリ４のアドレスと同じアドレスをアドレス２２に格納しているキャッシュラインがある場合は、当該キャッシュラインのバリッドビット２４を０にし、データ２１の無効化を行う。これにより、キャッシュデータ保持部１１が保持するデータ２１が、バスマスタ６による書き込みアクセスによってメインメモリ４上のデータと異なるものとなった場合に、プロセッサ１がメインメモリ４上のデータよりも古いデータを読み出すことを未然に防止する。
【００２４】
また、バスマスタ６によるメインメモリ４への書き込み後、バスマスタ６がプロセッサ１に対して書き込みを行ったことを通知し、この通知に基づきプロセッサ１がキャッシュコントローラ１０に対して対応するキャッシュライン上のデータを無効化するよう要求するようにしてもよい。このような構成でも、キャッシュデータ保持部１１が保持するデータ２１が、バスマスタ６による書き込みアクセスによってメインメモリ４上のデータと異なるものとなった場合に、プロセッサ１がメインメモリ４上のデータよりも古いデータを読み出すことを未然に防止することができ、さらに無効化処理を行うことも可能となる。
【００２５】
キャッシュデータ保持部１１が保持するデータをメインメモリ４に書き戻す場合、プロセッサ１が書き戻しを行うデータのメインメモリ４上のアドレス情報を有する書き戻し対象アドレス範囲信号及び書き戻し制御信号を書き戻し制御回路３へ送信する。書き戻し制御回路３は書き戻し対象アドレス範囲信号及び書き戻し制御信号に基づき、書き戻し制御を行う。書き戻し制御回路３はキャッシュデータ保持部１１が有するキャッシュラインをランダムに指定し、指定したキャッシュラインのデータをメインメモリ４に書き戻すかを判定し、書き戻すと判定した場合はキャッシュコントローラ１０へ書き戻し実行信号を送信する。書き戻し制御回路３は、キャッシュデータ保持部１１が有するすべてのキャッシュラインを指定した後、最終値フラグをプロセッサ１へ送信する。
【００２６】
図３にキャッシュメモリ装置０の概略構成を示す。プロセッサ１が送信する書き戻し対象アドレス範囲信号を書き戻しアドレス範囲格納レジスタ３１が受信する。書き戻し対象アドレス範囲信号は書き戻し対象アドレス範囲の最小アドレス及び最大アドレスを有する。乱数発生装置３２は書き戻し制御信号に基づいて、数値をランダムに発生させ、キャッシュコントローラ１０へ送信する。キャッシュコントローラ１０は受信した数値に対応するラインインデックスのキャッシュラインを指定し、そのキャッシュラインが保持するタグ情報（アドレス、ダーティビット及びバリッドビット）を取り出し、範囲内検出回路３３へ送信する。範囲内検出回路３３は、このタグ情報（アドレス、ダーティビット、バリッドビット）及び書き戻しアドレス範囲格納レジスタ３１が送信する書き戻し対象アドレス範囲信号を受信し、これらに基づいて、キャッシュラインのデータを書き戻すかどうかを判定する。範囲内検出回路３３が書き戻すと判定した場合は、書き戻し実行信号をキャッシュコントローラ１０へ送信する。乱数発生装置３２はすべてのラインインデックスに対応する数値を発生し、キャッシュコントローラ１０へ送信すると、プロセッサ１へ最終値フラグを送信し、数値の発生を終了する。
【００２７】
乱数発生装置３２は図４に示すようにＭ系列発生器を用いて構成することができる。Ｍ系列発生器４１は書き戻し制御信号（初期化信号、出力値更新信号）が入力される。Ｍ系列発生器４１に初期化信号が入力されると、Ｍ系列発生器４１は１を設定し、出力する。その後、出力値更新信号に基づいてＭ系列信号が順次出力される。最終値フラグ出力部４３が出力する最終値フラグはＭ系列発生器４１から２度目に１が出力されるときに１となり、それ以外は０である。
【００２８】
例えば、Ｍ系列発生器４１がｍ次（ｍは２以上の整数）のＭ系列（系列長２ｍ−１）を発生する場合、Ｍ系列発生器４１は１（初期値）〜２ｍ−１の値をランダムに重複なく出力する。Ｍ系列発生器４１が１〜２ｍ−１の値を出力しているときは、最終値フラグ出力部４３が出力する最終値フラグの値は０である。Ｍ系列発生器４１は１〜２ｍ−１の値をすべて出力すると再び初期値である１を出力する。初期値である１が２度目に出力された時、最終値フラグ出力部４３が出力する最終値フラグの値は１になる。
【００２９】
セレクタ４２はＭ系列発生器４１の出力及び０が入力され、最終値フラグの値に応じて一方を選択、出力する。最終値フラグ＝０のときＭ系列発生器４１の出力するＭ系列信号を選択、出力し、最終値フラグ＝１のとき０を選択、出力する。セレクタ４２の出力する数値がキャッシュコントローラ１０へ送信され、この数値に対応するラインインデックスのキャッシュラインが指定される。最終値フラグ出力部４３が１を出力すると、Ｍ系列発生器の内部状態の更新が止まる。
【００３０】
Ｍ系列発生器の構成例を図５に示す。ここでは系列長２８−１（＝２５５）のＭ系列を発生させるＭ系列発生器の構成例を示す。Ｍ系列発生器はシフトレジスタｂ０〜ｂ７、排他的論理和（ＸＯＲ）ゲート５１〜５３を有する。Ｍ系列発生器に初期化信号が入力されるとｂ０＝１、ｂ１＝ｂ２＝ｂ３＝…＝ｂ７＝０が設定される。そしてＭ系列発生器はｂ７乃至ｂ０の順に値が並べられるＭ系列信号を出力する。Ｍ系列発生器は出力値更新信号に基づき内部状態を更新する。０００００００１（＝１）のＭ系列信号の出力後、出力値更新信号が入力されると、内部状態は１０００１１１０となり、値が１０００１１１０（＝１４２）のＭ系列信号を出力する。さらに内部状態が更新されると、値が０１０００１１１（＝７１）のＭ系列信号を出力する。このようにＭ系列発生器は１〜２５５の数値をランダムに重複なく出力し、この数値に対応するラインインデックスのキャッシュラインが指定される。即ち、キャッシュラインをランダムに重複なく指定することができる。
【００３１】
範囲内検出回路３３の概略構成を図６に示す。最小アドレス設定レジスタ６１にはプロセッサ１から出力される書き戻し対象アドレス範囲信号が有する最小アドレスが入力される。また、最大アドレス設定レジスタ６２にはプロセッサ１から出力される書き戻し対象アドレス範囲信号が有する最大アドレスが入力される。比較器６３、６４にはそれぞれキャッシュコントローラ１０が送信したタグ情報に含まれるアドレスが入力され、比較器６３はタグ情報に含まれるアドレスが最小アドレスと同じか又は大きいときに１を出力する。また、比較器６４はタグ情報に含まれるアドレスが最大アドレスと同じか又は小さいときに１を出力し、それ以外は０を出力する。論理積回路６５は比較器６３及び比較器６４の出力値が入力され、比較器６３及び比較器６４の出力値が共に１の場合に１を出力し、それ以外は０を出力する。論理積回路６５の出力は範囲内フラグとなり、範囲内フラグ＝１のときはタグ情報に含まれるアドレスが書き戻し対象アドレス範囲に含まれていることを示し、範囲内フラグ＝０のときはタグ情報に含まれるアドレスが書き戻し対象アドレス範囲に含まれていないことを示す。
【００３２】
範囲内フラグ及びキャッシュコントローラ１０が送信したタグ情報に含まれるバリッドビット、ダーティビットが書き戻し判定部６６に入力される。範囲内フラグ＝バリッドビット＝ダーティビット＝１の場合は書き戻しを行うと判定され、書き戻し実行信号が出力される。範囲内フラグ、バリッドビット、ダーティビットのうち少なくとも１つが０の場合は書き戻しを行わない。
【００３３】
データ書き戻し処理について図７に示すフローチャートを用いて説明する。
【００３４】
（ステップＳ１）書き戻し制御信号（初期化信号）に基づき、乱数発生装置３２が初期化される。
【００３５】
（ステップＳ２）乱数発生装置３２によりキャッシュラインインデックスのいずれか１つを指定するランダムな値Ａが出力される。値Ａは未だ出力されていない値である。
【００３６】
（ステップＳ３）ステップＳ２で出力された値Ａに対応するキャッシュラインインデックスが示すキャッシュラインのアドレス、有効ビット、ダーティビットをキャッシュコントローラ１０が取得し、範囲内検出回路３３へ送信する。
【００３７】
（ステップＳ４）範囲内検出回路３３が受信したアドレスが書き戻し対象アドレス範囲にあり（範囲内フラグ＝１）、かつ有効ビット＝１、かつダーティビット＝１という条件を満たすか否かが調べられる。有効ビットが０のときは無効データなので書き戻しは行われない。また、ダーティビットが０のときはメインメモリとキャッシュメモリのデータは一致しているので書き戻しの必要がない。条件を満たす場合はステップＳ５に進み、満たさない場合はステップＳ６に進む。
【００３８】
（ステップＳ５）範囲内検出回路３３から書き戻し実行信号が出力され、値Ａに対応するキャッシュラインインデックスが示すキャッシュラインのデータをキャッシュコントローラ１０がメインメモリ４に書き戻し、ダーティビットを０にする。
【００３９】
（ステップＳ６）乱数発生装置３２がすべての数値を出力したか（すべてのキャッシュラインが指定されたか）が最終値フラグの値から検出される。すべての数値を出力した場合は、書き戻し処理が終了する。出力していない場合は書き戻し制御信号（出力値更新信号）に基づきＭ系列発生器の内部状態を更新してステップ２に戻り、書き戻し処理を進める。
【００４０】
データ書き戻し処理の一例を図８〜１０を用いて説明する。キャッシュメモリは図８に示すように８個のキャッシュラインＣ０〜Ｃ７（ラインインデックス０〜７）を有し、ラインインデックス３〜５のキャッシュラインＣ３〜Ｃ５のデータがダーティであるとする。キャッシュラインは８個なのでＭ系列発生器は図９（ａ）に示すように系列長２３−１のＭ系列を発生するような構成になっている。すべてのキャッシュラインが保持するアドレスが書き戻し対象アドレス範囲内であるとし、キャッシュメモリの一括書き戻しを行う。
【００４１】
まず、初期化信号に基づきｂ０＝１、ｂ１＝ｂ２＝０が設定される。その後、出力値更新信号に基づきＭ系列発生器の内部状態が更新され、１００、０１０、…と出力される。Ｍ系列の発生シーケンスは図９（ｂ）のようになり、データの書き戻しはラインインデックス１、４、２、５、６、７、３、０の順に行われる。
【００４２】
データの書き戻しのタイムチャートを図１０に示す。まずキャッシュラインＣ１の書き戻しが必要か否か調査される。キャッシュラインＣ１は書き戻し不要なため、続いてキャッシュラインＣ４について調査される。キャッシュラインＣ４はデータがダーティであるためデータ書き戻しが必要であり、書き戻しが開始される。
【００４３】
キャッシュラインＣ４のデータ書き戻しを行っている間にキャッシュラインＣ２について調査される。キャッシュラインＣ２は書き戻し不要なため、続いてキャッシュラインＣ５が調査される。キャッシュラインＣ５は書き戻しが必要なため、キャッシュラインＣ４の書き戻し処理が終わるまで処理待ちとなる。キャッシュラインＣ４の書き戻しが終了すると、キャッシュラインＣ５の書き戻しが始まる。
【００４４】
キャッシュラインＣ５の書き戻しを行っている間にキャッシュラインＣ６の調査が行われる。キャッシュラインＣ６は書き戻し不要なため、続いてキャッシュラインＣ７の調査が行われる。キャッシュラインＣ７は書き戻し不要なため、続いてキャッシュラインＣ３の調査が行われる。キャッシュラインＣ３は書き戻しが必要なため、キャッシュラインＣ５の書き戻し処理が終わるまで処理待ちとなる。キャッシュラインＣ５の書き戻しが終了すると、キャッシュラインＣ３の書き戻しが始まる。
【００４５】
キャッシュラインＣ３の書き戻しを行っている間にキャッシュラインＣ０の調査が行われる。キャッシュラインＣ０は書き戻しが不要である。キャッシュラインＣ３の書き戻しが終了すると書き戻し処理を終了する。
【００４６】
（比較例）比較例によるキャッシュメモリ装置の概略構成を図１１に示す。ラインインデックスカウンタ９１はプロセッサ１から初期化信号が入力されると０を出力し、以後出力値更新信号に基づき１ずつ増加させた値を出力する。キャッシュデータ保持部１１のキャッシュラインはラインインデックス０、１、２、…と順番に指定される。
【００４７】
この比較例によるキャッシュメモリ装置を用いたデータ書き戻し処理の例を図１２を用いて説明する。キャッシュメモリは図１２（ａ）に示すように８個のキャッシュラインＣ０〜Ｃ７（ラインインデックス０〜７）を有し、ラインインデックス３〜５のキャッシュラインＣ３〜Ｃ５のデータがダーティであるとする。データの書き戻しはラインインデックス０、１、２、３、４、５、６、７の順に行われる。
【００４８】
データの書き戻しのタイムチャートを図１２（ｂ）に示す。まずキャッシュラインＣ０の書き戻しが必要か否か調査される。キャッシュラインＣ０は書き戻し不要なため、続いてキャッシュラインＣ１について調査される。キャッシュラインＣ１は書き戻しが不要なため、続いてキャッシュラインＣ２について調査される。キャッシュラインＣ２は書き戻しが不要なため、続いてキャッシュラインＣ３について調査される。キャッシュラインＣ３は書き戻しが必要であり、書き戻しが開始される。
【００４９】
キャッシュラインＣ３の書き戻しを行っている間にキャッシュラインＣ４の調査が行われる。キャッシュラインＣ４は書き戻しが必要なため、キャッシュラインＣ３の書き戻しが終わるまで処理待ちとなる。キャッシュラインＣ３の書き戻しが終了すると、キャッシュラインＣ４の書き戻しが始まる。
【００５０】
キャッシュラインＣ４の書き戻しを行っている間にキャッシュラインＣ５の調査が行われる。キャッシュラインＣ５は書き戻しが必要なため、キャッシュラインＣ４の書き戻しが終わるまで処理待ちとなる。キャッシュラインＣ４の書き戻しが終了すると、キャッシュラインＣ５の書き戻しが始まる。
【００５１】
キャッシュラインＣ５の書き戻しを行っている間にキャッシュラインＣ６の調査が行われる。キャッシュラインＣ６は書き戻しが不要なため、続いてキャッシュラインＣ７について調査が行われる。キャッシュラインＣ７は書き戻しが不要である。キャッシュラインＣ５の書き戻しが終了すると、書き戻し処理を終了する。
【００５２】
比較例によるキャッシュメモリ装置を用いると、書き戻しデータが連続したキャッシュラインに存在する場合、処理待ち時間が長くなる。
【００５３】
一方、本発明の第１の実施形態によるキャッシュメモリ装置を用いると、ラインインデックス値をランダムに出力し、キャッシュラインをランダムに指定するため、書き戻し処理を分散して行うことができ、処理待ち時間が短くなり、メインメモリへのデータ書き戻しにかかる時間を短縮することができる。
【００５４】
（第２の実施形態）図１３に本発明の第２の実施形態によるキャッシュメモリ装置を含むキャッシュシステムの概略構成を示す。キャッシュメモリ装置はプロセッサＰ１〜Ｐｎ、２次キャッシュメモリ２´及び書き戻し制御回路３を有する。２次キャッシュメモリ２´はキャッシュコントローラ１０´及びキャッシュデータ保持部１１´を有する。
【００５５】
プロセッサＰ１〜Ｐｎはそれぞれ内部に１次キャッシュメモリＭ１〜Ｍｎを有し、１次バスを介して２次キャッシュメモリ２´を共有する。プロセッサＰ１〜Ｐｎはそれぞれ独立して書き戻しアドレス範囲を出力する。１次キャッシュメモリＭ１〜Ｍｎはそれぞれキャッシュコントローラ（図示しない）及びキャッシュデータ保持部（図示しない）を有する。
【００５６】
ここで、プロセッサＰ１が有する１次キャッシュメモリＭ１の一括書き戻し処理を行うとする。１次キャッシュメモリＭ１のデータはキャッシュコントローラ１０´によりキャッシュデータ保持部１１´に格納され、続いてキャッシュコントローラ１０´によりキャッシュデータ保持部１１´からメインメモリ４へ書き戻される。書き戻し制御回路３は２次キャッシュメモリ２´にのみ適用されているため、書き戻し制御回路３と各プロセッサＰ１〜Ｐｎは並行して動作することができる。
【００５７】
２次キャッシュメモリ２´におけるデータ書き戻し処理では、書き戻し制御回路３によりキャッシュデータ保持部１１´のキャッシュラインがランダムに指定され、指定されたキャッシュラインについて書き戻しを行うかの判定が行われる。上記第１の実施形態と同様に、書き戻し処理に要する時間を短縮化することができる。
【００５８】
このように、書き戻し制御回路３をマルチプロセッサ（プロセッサＰ１〜Ｐｎ）が共有する２次キャッシュメモリ２´に適用することで、２次キャッシュメモリ２´の性能がプロセッサＰ１〜Ｐｎから安定してみえるようになる。
【００５９】
上述した実施の形態はいずれも一例であって制限的なものではないと考えられるべきである。例えば、上記実施形態では乱数発生装置３２にＭ系列発生器を用いた構成を示していたが、図１４に示すようにバイナリカウンタ４４とシャッフル回路４５を用いる構成にしてもよい。バイナリカウンタ４４は初期化信号によって０が設定され、出力値更新信号によって１ずつ加算される。バイナリカウンタ４４から出力された値はシャッフル回路４５によりシャッフルされて出力される。シャッフル回路４５の一例を図１５に示す。各ビット（ここでは８ビット）がシャッフルされて出力される。最終値フラグ出力部４６から出力される最終値フラグは、バイナリカウンタから最終値（８ビットの場合は１１１１１１１１＝２５５）が出力されたら１となる。
【００６０】
また、図１６に示すようなキャッシュメモリ装置を用いて書き戻し処理だけでなく、無効化処理を行うことができる。無効化処理を行う場合は、プロセッサ１が無効化するアドレス範囲の情報を有する信号を送信し、無効化・書き戻しアドレス範囲格納レジスタ３４に受信される。無効化処理のフローチャートを図１７に示す。ステップＳ４にて、指定されたキャッシュラインが有するアドレスが無効化対象アドレス範囲にあるか、有効ビット＝１であるかの検出が行われる。検出結果から無効化を行うと判定された場合は、範囲内検出回路３３がキャッシュコントローラ１０へ無効化実行信号を送信し、ステップＳ５にてキャッシュコントローラ１０がキャッシュラインの有効ビットが０にする。
【００６１】
本発明の技術的範囲は特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【図面の簡単な説明】
【００６２】
【図１】本発明の第１の実施形態に係るキャッシュメモリ装置を含むキャッシュシステムの概略構成図である。
【図２】同キャッシュメモリ装置におけるキャッシュメモリの概略構成図である。
【図３】同キャッシュメモリ装置の概略構成図である。
【図４】同キャッシュメモリ装置における乱数発生装置の概略構成図である。
【図５】同キャッシュメモリ装置におけるＭ系列発生器の概略構成図である。
【図６】同キャッシュメモリ装置における範囲内検出回路の概略構成図である。
【図７】同キャッシュメモリ装置におけるデータ書き戻し処理のフローチャートである。
【図８】同キャッシュメモリ装置におけるキャッシュメモリ構成の一例を示す図である。
【図９】同キャッシュメモリ装置におけるＭ系列発生器の一例を示す図である。
【図１０】同キャッシュメモリ装置におけるデータ書き戻し処理の一例を示す図である。
【図１１】比較例によるキャッシュメモリ装置の概略構成図である。
【図１２】比較例によるキャッシュメモリ装置を用いたデータ書き戻し処理を示す図である。
【図１３】本発明の第２の実施形態によるキャッシュメモリ装置を含むキャッシュシステムの概略構成図である。
【図１４】上記第１及び第２の実施形態における一変形例による乱数発生装置を示す図である。
【図１５】同乱数発生装置におけるシャッフル回路の一例を示す図である。
【図１６】上記第１及び第２の実施形態における他の変形例によるキャッシュメモリ装置の概略構成図である。
【図１７】同他の変形例によるキャッシュメモリ装置を用いた無効化処理のフローチャートである。
【符号の説明】
【００６３】
１  プロセッサ
２  キャッシュメモリ
３  書き戻し制御回路
４  メインメモリ
５  バス
６  バスマスタ
１０  キャッシュコントローラ
１１  キャッシュデータ保持部
【図１】
2008107905.tif 000003
【図２】
2008107905.tif 000004
【図３】
2008107905.tif 000005
【図４】
2008107905.tif 000006
【図５】
2008107905.tif 000007
【図６】
2008107905.tif 000008
【図７】
2008107905.tif 000009
【図８】
2008107905.tif 000010
【図９】
2008107905.tif 000011
【図１０】
2008107905.tif 000012
【図１１】
2008107905.tif 000013
【図１２】
2008107905.tif 000014
【図１３】
2008107905.tif 000015
【図１４】
2008107905.tif 000016
【図１５】
2008107905.tif 000017
【図１６】
2008107905.tif 000018
【図１７】
2008107905.tif 000019