(57)【要約】【課題】並列計算機での無駄なメモリアクセスを回避可能なキャッシュメモリシステムを提供する。【解決手段】並列演算する複数の演算装置に個別に接続されるキャッシュメモリシステムは、複数のブロックを有するデータアレイ、少なくとも１つのワードにデータが格納されたブロックに対応する共有メモリのアドレス群を格納する格納手段、書込み時に演算装置からのアドレスが格納手段にないとブロックのいずれかを書込み用としその内のいずれかのワードをそのアドレスに対応づけそのワードに演算装置からのデータを書き込む書込み手段、演算装置からのデータが書き込まれたワードを特定するワード状態情報をそのワードに対応するアドレスと関連づけて記憶するワード状態記憶手段、ワード状態記憶手段を参照して書込み用ブロック内でデータが書き込まれたワード内のデータを共有メモリ内の対応するブロックにライトバックするデータ転送手段を含む。【選択図】図１Ａ
2009151457.tif 000002
【特許請求の範囲】
【請求項１】
共有メモリにアクセスして並列演算を行う複数の演算装置のそれぞれに対して、個別に接続されるキャッシュメモリシステムであって、
複数のワードからなる複数のブロックを有するデータアレイと、
前記複数のブロックのうち、少なくとも１つの前記ワードにデータが格納されたブロックについて、当該ブロックに対応づけられた前記共有メモリのアドレス群を格納する格納手段と、
前記演算装置からの書込み時に、当該演算装置からのアドレスが前記格納手段内にない場合、前記複数のブロックのいずれかを書込み用ブロックとして割り当て、当該書込み用ブロック内のいずれかのワードを当該アドレスに対応づけ、当該ワードに当該演算装置からのデータを書き込む書込み手段と、
前記演算装置からのデータが書き込まれたワードを特定するためのワード状態情報を、当該ワードに対応づけられたアドレスと関連づけて記憶するワード状態記憶手段と、
キャッシュメモリ上の前記書き込み用ブロックが異なるブロックに置き換えられる時、前記ワード状態記憶手段を参照して、前記書込み用ブロック内で前記データが書き込まれた１つまたは複数のワードを特定し、当該特定された１つまたは複数のワード内のデータを、前記共有メモリ内の対応するブロックにライトバックするデータ転送手段と、を含むキャッシュメモリシステム。
【請求項２】
請求項１に記載のキャッシュメモリシステムにおいて、
前記演算装置からの読み出し時に、当該演算装置からのアドレスに対応する前記ワード状態情報を前記ワード状態記憶手段が記憶している場合、当該ワード状態情報にて特定されるワードからデータを読み出す読出し手段をさらに含む、キャッシュメモリシステム。
【請求項３】
請求項１または２に記載のキャッシュメモリシステムにおいて、
前記ブロックに対応するアドレス群ごとに、当該ブロック内の前記演算装置からのデータが書き込まれていないワードに前記共有メモリから読み出されたデータが記憶されているか否かを示すブロック状態情報を記憶するブロック状態記憶手段と、
前記演算装置からの読み出し時に当該演算装置からアドレスを受け付けた場合に、前記ワード状態記憶手段および前記ブロック状態記憶手段を参照して、当該アドレスについてキャッシュヒットまたはキャッシュミスが生じたかを判断する判断手段と、をさらに含むキャッシュメモリシステム。
【請求項４】
請求項３に記載のキャッシュメモリシステムにおいて、
前記読出し手段は、前記演算装置からの読み出し時にキャッシュミスが生じた時、当該演算装置からのアドレスに対応するブロック内のデータを、前記共有メモリから読み出し、前記ワード状態記憶手段を参照して、前記データアレイの当該ブロック内でデータが書き込まれていない１つまたは複数のワードを特定し、当該特定された１つまたは複数のワードにだけ、前記共有メモリから読み出したブロックのデータを書き込み、前記ブロック状態記憶手段に、当該ブロック内の前記演算装置からデータが書き込まれていない１つまたは複数のワードに前記共有メモリから読み出されたデータが記憶されていることを示す前記ブロック状態情報を記憶する、キャッシュメモリシステム。
【請求項５】
共有メモリにアクセスして並列演算を行う複数の演算装置のそれぞれに対して個別に接続され、かつ、複数のワードからなる複数のブロックを有するデータアレイを含むキャッシュメモリシステムが行うキャッシュメモリ制御方法であって、
前記複数のブロックのうち、少なくとも１つの前記ワードにデータが格納されたブロックについて、当該ブロックに対応づけられた前記共有メモリのアドレス群を格納手段に格納する格納ステップと、
前記演算装置からの書込み時に、当該演算装置からのアドレスが前記格納手段内にない場合、前記複数のブロックのいずれかを書込み用ブロックとして割り当て、当該書込み用ブロック内のいずれかのワードを当該アドレスに対応づけ、当該ワードに当該演算装置からのデータを書き込む書込みステップと、
前記演算装置からのデータが書き込まれたワードを特定するためのワード状態情報を、当該ワードに対応づけられたアドレスと関連づけてワード状態記憶手段に記憶するワード状態記憶ステップと、
キャッシュメモリ上の前記書き込み用ブロックが異なるブロックに置き換えられる時、前記ワード状態記憶手段を参照して、前記書込み用ブロック内で前記データが書き込まれた１つまたは複数のワードを特定し、当該特定された１つまたは複数のワード内のデータを、前記共有メモリ内の対応するブロックにライトバックするデータ転送ステップと、を含むキャッシュメモリ制御方法。
【請求項６】
請求項５に記載のキャッシュメモリ制御方法において、
前記演算装置からの読み出し時に、当該演算装置からのアドレスに対応する前記ワード状態情報を前記ワード状態記憶手段が記憶している場合、当該ワード状態情報にて特定されるワードからデータを読み出す読出しステップをさらに含むキャッシュメモリ制御方法。
【請求項７】
請求項５または６に記載のキャッシュメモリ制御方法において、
前記ブロックに対応するアドレス群ごとに、当該ブロック内の前記演算装置からのデータが書き込まれていないワードに前記共有メモリから読み出されたデータが記憶されているか否かを示すブロック状態情報をブロック状態記憶手段に記憶するブロック状態記憶ステップと、
前記演算装置からの読み出し時に当該演算装置からアドレスを受け付けた場合に、前記ワード状態記憶手段および前記ブロック状態記憶手段を参照して、当該アドレスについてキャッシュヒットまたはキャッシュミスが生じたかを判断する判断ステップと、をさらに含むキャッシュメモリ制御方法。
【請求項８】
請求項７に記載のキャッシュメモリ制御方法において、
前記読出しステップでは、前記演算装置からの読み出し時にキャッシュミスが生じた時、当該演算装置からのアドレスに対応するブロック内のデータを、前記共有メモリから読み出し、前記ワード状態記憶手段を参照して、前記データアレイの当該ブロック内でデータが書き込まれていない１つまたは複数のワードを特定し、当該特定された１つまたは複数のワードにだけ、前記共有メモリから読み出したブロックのデータを書き込み、前記ブロック状態記憶手段に、当該ブロック内の前記演算装置からデータが書き込まれていない１つまたは複数のワードに前記共有メモリから読み出されたデータが記憶されていることを示す前記ブロック状態情報を記憶する、キャッシュメモリ制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のＣＰＵ（Central Processing Unit）からアクセス可能な共有メモリを有する並列計算機システムにおけるキャッシュメモリシステムおよびキャッシュメモリ制御方法に関し、特に、複数のＣＰＵで並列処理を行う場合にフォールスシェアリング（false sharing）による無駄なメモリアクセスを回避できるキャッシュメモリシステムおよびキャッシュメモリ制御方法に関する。
【背景技術】
【０００２】
キャッシュメモリを用いたデータ処理技術が知られている。
【０００３】
特許文献１には、単一プロセッサシステムにおいて、キャッシュメモリ内のデータをブロック単位で主記憶部にライトバックするキャッシュ装置が記載されている。
【０００４】
特許文献２には、１つの共有メモリに複数のプロセッサが接続された並列計算機で使用されるキャッシュメモリ装置が記載されている。
【０００５】
図１７は、特許文献２に記載された並列計算機を示したブロック図である。
【０００６】
図１７において、並列計算機では、１つの共有メモリ１７０１に複数のＣＰＵ１７０２が接続されている。各ＣＰＵ１７０２は、キャッシュメモリ１７０３を有する。各ＣＰＵ１７０２は、キャッシュメモリ１７０３を用いて、共有メモリ１７０１内のデータをキャッシュすることができる。
【０００７】
このような構成の並列計算機では、１つのプログラムを複数のＣＰＵが並列に処理することで、高い性能が達成される。
【０００８】
例えば、非特許文献１の図１４には、３重のＤＯループの最も外側のＤＯループを複数のＣＰＵで並列に処理する方法が開示されている。
【０００９】
非特許文献１には、内側の２つのＤＯループの部分をベクトル化することにより高速化を図ることが記載されている。なお、内側の２つのＤＯループの部分を、スカラプロセッサのＳＩＭＤ（Single Instruction Multiple Data：単一命令多重データ）命令により高速化することも可能である。
【００１０】
非特許文献１に記載の例では、３次元配列ＢとＣの積を３次元配列Ａに格納する処理を示している。なお、最も外側のＫによるＤＯループを複数のＣＰＵが並列処理した場合、配列Ａ（Ｉ，Ｊ，Ｋ）のそれぞれの要素には、配列の３つ目の添え字Ｋによって決まる１つのＣＰＵからのみ、値が書き込まれる。
【００１１】
一方、非特許文献２の図７．１０には、多次元の配列が１次元のメモリに格納される場合の各要素の配置について記載されている。
【００１２】
メモリでの配列の要素の配置は、プログラミング言語により異なる。FORTRAN（フォートラン）の場合には、同じ列の要素がメモリ上で連続する列優先配置が採用されている。FORTRAN以外の場合には、同じ行の要素がメモリ上で連続する行優先配置が採用されている。
【００１３】
ここで、図１８に示すFORTRANのプログラムの外側のループを、８個のＣＰＵが並列処理する場合を考える。
【００１４】
図１７に記載の並列計算機では、各ＣＰＵ１７０２が、キャッシュメモリ１７０３を用いて、共有メモリ１７０１内の内容をキャッシュする。このため、データアクセスが高速化し、高性能が達成される。
【００１５】
キャッシュメモリのブロックサイズを６４バイトとすると、配列Ａが６４バイト境界から始まった場合のキャッシュメモリでの要素の配置は、図１９に示すようになる。
【００１６】
FORTRANは列優先配置なので、配列Ａの同じ列が連続する。よって、Ａ（0,k）〜Ａ（7,k）（k＝0〜7）が、同じキャッシュブロック上のワードに配置される。
【００１７】
各ＣＰＵは、Ａ（i,0）〜Ａ（i,7）（i＝0〜7）を個別に更新する。このため、１つのキャッシュブロックに、８個のＣＰＵから１ワードずつデータが書き込まれることになる。
【００１８】
１つのキャッシュブロックに対して複数のＣＰＵがそれぞれ異なるワードへデータの書き込みを行う場合には、非特許文献３に記載されたように、無効化型一貫性制御を行うキャッシュメモリでは、フォールスシェアリング（false sharing）と呼ばれる問題が起こり、メモリアクセス性能が低下することが知られている。
【００１９】
特許文献２には、フォールスシェアリング（false sharing）によるキャッシュヒット率の低下を回避する方法が開示されている。
【００２０】
この方法では、キャッシュブロックをサブブロックに分割して、サブブロックごとに有効ビットをつけておく。他のＣＰＵが、あるサブブロックへデータの書き込みを行った場合には、データが書き込まれたサブブロックの無効化要求が出され、データが書き込まれたサブブロックだけが無効化され、ブロックのほかのサブブロックは有効としてキャッシュメモリに保持される。これにより、フォールスシェアリング（false sharing）によるキャッシュヒット率の低下が回避される。
【非特許文献１】「ＮＥＣ技報」、第45巻  第2号、日本電気文化センター、1992年2月28日、ｐｐ．64
【非特許文献２】デイビッド・パターソン、ジョン・へネシー著「コンピュータ・アーキテクチャ―設計・実現・評価の定量的アプローチ―」日経BP出版センター、1992年12月25日、ｐｐ．364-365
【非特許文献３】John L. Hennessey、David A. Patterson「コンピュータ アーキテクチャ：ア クオンティテイティブ  アプローチ」(Computer Architecture : A Quantitative Approach)、Morgan Kaufmann Publishers, Inc.、1996年、ｐｐ．669-670
【特許文献１】特開平９−２５１４２４号公報
【特許文献２】特開２０００−２６７９３５号公報
【発明の開示】
【発明が解決しようとする課題】
【００２１】
特許文献２に記載の方法では、図１８に示した例のように、８個のＣＰＵがそれぞれキャッシュブロックの異なるサブブロックに書き込むような並列処理の場合には、次のような問題が発生する。
【００２２】
特許文献２に記載の方法は、ライトバック型のキャッシュメモリで行われるので、他のＣＰＵが、あるブロックに書き込みを行う場合には、いったん、そのブロックがキャッシュメモリに読み込まれる。
【００２３】
したがって、特許文献２に記載の方法では、８個のＣＰＵがそれぞれキャッシュブロックの異なるサブブロックに書き込むような並列処理の場合には、複雑なライトバック処理と、共有メモリからのブロック読み出しとを、各ブロックに対して、最初に書き込んだＣＰＵ以外の書き込み時に、７回行うことになる。
【００２４】
また、図１８の配列Ａのように、ループによりブロック全体が書き換わり、その結果をループ内ですぐに参照しない場合には、配列Ａへの書き込みごとに一貫性を保つための無効化処理を行う必要はなく、一貫性制御はオーバヘッドとなる。
【００２５】
なお、図１８に示した例のような場合は、ループが終わったときに、各ＣＰＵがキャッシュ上への書き込みをメモリにライトバックすればよい。
【００２６】
ここで、無効化型一貫性制御のライトバック型キャッシュメモリの問題点について説明する。
【００２７】
この問題点は、１つのキャッシュブロックに複数のＣＰＵから書き込みが行われる場合に、新たな書き込みが行われるごとに、書き込んだＣＰＵ以外のＣＰＵのキャッシュメモリの無効化と、ライトバック処理と、ブロックの読み出しとが行われることである。
【００２８】
特に、図１８に示すような外側ループを複数のＣＰＵで並列処理する場合には、一貫性制御によるライトバックとブロックの読み出しによるメモリアクセスが大きなオーバヘッドとなる。
【００２９】
図２０Ａ〜図２０Ｈは、ＣＰＵ２０００〜２００７が、同一ブロック２００８内の各ワードＡ０〜Ａ７に、順番に、データの書き込みを行うときの処理を示した説明図である。
【００３０】
ブロック２００８は、共有メモリ２００９に登録されている。ＣＰＵ２０００〜２００７は、キャッシュメモリ２０１０〜２０１７を有する。各ワードＡ０〜Ａ７には、データＡ（0,2）〜Ａ（7,2）が書き込まれている。
【００３１】
図２０Ａは、ループに入る前の状態を示した説明図である。
【００３２】
まず、ＣＰＵ２０００は、ブロック２００８内のワードＡ０（Ａ（0,2））に、処理結果Ａ（0,2）’を書き込むため、ブロック２００８のデータＡ（0,2）〜Ａ（7,2）を、共有メモリ２００９から読み出してキャッシュメモリ２０１０に書き込む。続いて、ＣＰＵ２０００は、キャッシュメモリ２０１０上のブロック２００８のワードＡ０に、処理結果Ａ（0,2）’を書き込む（図２０Ｂ参照）。
【００３３】
次に、ＣＰＵ２００１は、ブロック２００８内のワードＡ１（Ａ（1,2））に、処理結果Ａ（1,2）’を書き込むため、無効化要求を出して、ＣＰＵ２０００のキャッシュメモリ２０１０からブロック２００８のデータを共有メモリ２００９にライトバックさせる（図２０Ｃ参照）。
【００３４】
続いて、ＣＰＵ２００１は、共有メモリ２００９からブロック２００８のデータを読み出してキャッシュメモリ２０１１に書き込む。続いて、ＣＰＵ２００１は、キャッシュメモリ２０１１上のブロック２００８のワードＡ１に、処理結果Ａ（1,2）’を書き込む（図２０Ｄ参照）。
【００３５】
次に、ＣＰＵ２００２は、ブロック２００８内のワードＡ２（Ａ（2,2））に、処理結果Ａ（2,2）’を書き込むため、無効化要求を出して、ＣＰＵ２００１のキャッシュメモリ２０１１からブロック２００８のデータを共有メモリ２００９にライトバックさせる（図２０Ｅ参照）。
【００３６】
続いて、ＣＰＵ２００２は、共有メモリ２００９からブロック２００８のデータを読み出してキャッシュメモリ２０１２に書き込む。続いて、ＣＰＵ２００２は、キャッシュメモリ２０１２上のブロック２００８のワードＡ２に、処理結果Ａ（2,2）’を書き込む（図２０Ｆ参照）。
【００３７】
以下同様の処理を、ＣＰＵ２００３〜ＣＰＵ２００６が行い、最後に、ＣＰＵ２００７は、ブロック２００８内のワードＡ７（Ａ（7,2））に、処理結果Ａ（7,2）’を書き込むため、無効化要求を出して、ＣＰＵ２００６のキャッシュメモリ２０１６からブロック２００８のデータを共有メモリ２００９にライトバックさせる（図２０Ｇ参照）。
【００３８】
続いて、ＣＰＵ２００７は、共有メモリ２００９からブロック２００８のデータを読み出してキャッシュメモリ２０１７に書き込む。続いて、ＣＰＵ２００７は、キャッシュメモリ２０１７上のブロック２００８のワードＡ７に、処理結果Ａ（7,2）’を書き込む（図２０Ｈ参照）。
【００３９】
このように、書き込みを行うごとに、書き込まれたブロックのライトバックとそのブロックのメモリからの読み出しが起こる。
【００４０】
このようなメモリアクセスは、更新された最新の値を参照できるよう一貫性制御のために行われるが、図１８に示すようなループでは、ループ実行中は、更新された新しい値を参照することはない。
【００４１】
したがって、図１８に示すようなループを並列処理する場合には、メモリアクセスを頻発させる一貫性制御は、性能低下を招くオーバヘッドとなる。
【００４２】
本発明の目的は、上述した課題を解決可能なキャッシュメモリシステムおよびキャッシュメモリ制御方法を提供することである。
【課題を解決するための手段】
【００４３】
本発明のキャッシュメモリシステムは、共有メモリにアクセスして並列演算を行う複数の演算装置のそれぞれに対して、個別に接続されるキャッシュメモリシステムであって、複数のワードからなる複数のブロックを有するデータアレイと、前記複数のブロックのうち、少なくとも１つの前記ワードにデータが格納されたブロックについて、当該ブロックに対応づけられた前記共有メモリのアドレス群を格納する格納手段と、前記演算装置からの書込み時に、当該演算装置からのアドレスが前記格納手段内にない場合、前記複数のブロックのいずれかを書込み用ブロックとして割り当て、当該書込み用ブロック内のいずれかのワードを当該アドレスに対応づけ、当該ワードに当該演算装置からのデータを書き込む書込み手段と、前記演算装置からのデータが書き込まれたワードを特定するためのワード状態情報を、当該ワードに対応づけられたアドレスと関連づけて記憶するワード状態記憶手段と、キャッシュメモリ上の前記書き込み用ブロックが異なるブロックに置き換えられる時、前記ワード状態記憶手段を参照して、前記書込み用ブロック内で前記データが書き込まれた１つまたは複数のワードを特定し、当該特定された１つまたは複数のワード内のデータを、前記共有メモリ内の対応するブロックにライトバックするデータ転送手段と、を含む。
【００４４】
本発明のキャッシュメモリ制御方法は、共有メモリにアクセスして並列演算を行う複数の演算装置のそれぞれに対して個別に接続され、かつ、複数のワードからなる複数のブロックを有するデータアレイを含むキャッシュメモリシステムが行うキャッシュメモリ制御方法であって、前記複数のブロックのうち、少なくとも１つの前記ワードにデータが格納されたブロックについて、当該ブロックに対応づけられた前記共有メモリのアドレス群を格納手段に格納する格納ステップと、前記演算装置からの書込み時に、当該演算装置からのアドレスが前記格納手段内にない場合、前記複数のブロックのいずれかを書込み用ブロックとして割り当て、当該書込み用ブロック内のいずれかのワードを当該アドレスに対応づけ、当該ワードに当該演算装置からのデータを書き込む書込みステップと、前記演算装置からのデータが書き込まれたワードを特定するためのワード状態情報を、当該ワードに対応づけられたアドレスと関連づけてワード状態記憶手段に記憶するワード状態記憶ステップと、キャッシュメモリ上の前記書き込み用ブロックが異なるブロックに置き換えられる時、前記ワード状態記憶手段を参照して、前記書込み用ブロック内で前記データが書き込まれた１つまたは複数のワードを特定し、当該特定された１つまたは複数のワード内のデータを、前記共有メモリ内の対応するブロックにライトバックするデータ転送ステップと、を含む。
【発明の効果】
【００４５】
本発明によれば、並列計算機においてフォールスシェアリングに起因する無駄なメモリアクセスを回避することが可能になる。
【発明を実施するための最良の形態】
【００４６】
以下、本発明の実施形態について図面を参照して詳細に説明する。
【００４７】
図１Ａは、本発明の第１の実施の形態のキャッシュメモリシステムを示したブロック図である。
【００４８】
図１Ａにおいて、キャッシュメモリシステム１、４および６は、共有メモリ（以下、単に「メモリ」と称する。）３にアクセスして並列演算を行う複数のＣＰＵ２、５および７のそれぞれに対して、個別に接続される。なお、図１Ａでは、キャッシュメモリシステムとＣＰＵの数を３としたが、これらの数は３に限らず複数であればよい。
【００４９】
具体的には、キャッシュメモリシステム１は、ＣＰＵ２およびメモリ３と接続される。キャッシュメモリシステム４は、ＣＰＵ５およびメモリ３と接続される。キャッシュメモリシステム６は、ＣＰＵ７およびメモリ３と接続される。なお、ＣＰＵは、一般的に演算装置と呼ぶことができる。
【００５０】
キャッシュメモリシステム１、４および６は、同一構成である。このため、以下では、キャッシュメモリシステム１、４および６のうち、キャッシュメモリシステム１についてのみ説明を行う。
【００５１】
キャッシュメモリシステム１は、アドレスレジスタ１０１、アドレスアレイ１０２、データアレイ１０３、比較器１０４、および、キャッシュ制御ユニット１０５を含む。比較部１０４とキャッシュ制御ユニット１０５は、制御部１１５に含まれる。
【００５２】
アドレスレジスタ１０１は、ＣＰＵ２が要求したアドレスを格納する。アドレスレジスタ１０１に格納されるアドレスは、上位ｍビット１１１、中位ｎビット１０９、および、下位ｋビット１１４によって表される。
【００５３】
上位ｍビット１１１のデータは、比較器１０４に提供され、中位ｎビット１０９のデータは、アドレスアレイ１０２とデータアレイ１０３に提供される。
【００５４】
アドレスアレイ１０２は、２のｎ乗個のエントリ（以下「アドレスエントリ」と称する。）を持つメモリである。なお、データアレイ１０３も、２のｎ乗個のエントリ（以下「データエントリ」と称する。）を持つメモリである。データアレイ１０３は、複数のワードからなる複数のブロック（データエントリ）を有する。
【００５５】
各アドレスエントリは、中位ｎビット１０９のデータに基づいて、各データエントリと１対１で対応している。
【００５６】
各アドレスエントリは、中位ｎビット１０９のデータが表すことが可能な値に対応するオフセットを有する。このため、各アドレスエントリは、中位ｎビット１０９に対応する。なお、オフセットは、一般的にインデックスとも呼ばれる。
【００５７】
アドレスアレイ１０２は、データアレイ１０３のデータエントリにブロック単位で格納されているデータ（ブロックデータ）の索引として使用される。
【００５８】
アドレスアレイ１０２の１つのアドレスエントリは、中位ｎビット１０９に対応するオフセットごとに、アドレスの上位ｍビット１０６と、そのブロックの状態他を表すビット列（以下「状態他ビット列」とも称する。）１０７と、を含む。アドレスの上位ｍビット１０６は、ブロックデータのアドレス（ブロックアドレス）の一部である。
【００５９】
アドレスアレイ１０２のうち、中位ｎビット１０９に対応するオフセットごとに、上位ｍビット１０６を格納する部分は、格納手段の一例である。
【００６０】
格納手段は、少なくとも１つのワードにデータが格納されたデータエントリに対応する、メモリ３のアドレス群（上位ｍビットのデータと中位ｎビットのデータ）を格納する。
【００６１】
このアドレス群は、上位ｍビットと中位ｎビットのデータが規定され、かつ、下位ｋビットのデータが任意の値となる複数のアドレスを意味する。
【００６２】
アドレスアレイ１０２のうち、状態他ビット列１０７を格納する部分は、ワード状態記憶部１０７ａと、ブロック状態記憶部１０７ｂと、を含む（図２参照）。
【００６３】
ワード状態記憶部１０７ａは、一般的にワード状態記憶手段と呼ぶことができる。
【００６４】
ワード状態記憶部１０７ａは、ＣＰＵ２からのデータが書き込まれたワードを特定するためのワード状態情報（W(1)〜W（8））を、そのワードに対応づけられたアドレスと関連づけて記憶する。
【００６５】
ブロック状態記憶部１０７ｂは、一般的にブロック状態記憶手段と呼ぶことができる。
【００６６】
ブロック状態記憶部１０７ｂは、データアレイ１０３のブロックに対応するアドレス群ごとに、そのブロック内のＣＰＵ２から書き込まれていないワードにメモリ３から読み出されたデータが記憶されているか否かを示すブロック状態情報（ＢＶ）を記憶する。
【００６７】
なお、状態他ビット列１０７の詳細については後述する。
【００６８】
アドレスアレイ１０２は、中位ｎビット１０９のデータをオフセット１１０として受け付けると、オフセット１１０に対応するアドレスエントリから、上位ｍビット１０６のデータと、状態他ビット列１０７のデータと、を出力する。
【００６９】
上位ｍビット１０６のデータは、比較器１０４に提供され、状態他ビット列１０７のデータは、キャッシュ制御ユニット１０５に提供される。
【００７０】
データアレイ１０３の１つのデータエントリは、２のｋ乗バイトのブロックデータ（以下、単に「ブロック」とも称する。）１０８を格納する。
【００７１】
各データエントリは、各アドレスエントリと１対１で対応しているため、各データエントリ内のブロックも、各アドレスエントリと１対１で対応する。
【００７２】
比較器１０４は、アドレスアレイ１０２からの上位ｍビット１０６のデータと、アドレスレジスタ１０１からの上位ｍビット１１１のデータと、を比較する。
【００７３】
上位ｍビット１０６のデータと上位ｍビット１１１のデータが一致した場合は、アドレスレジスタ１０１内のアドレスにて指定されたデータを含むブロックが、キャッシュメモリ（具体的には、アドレスアレイ１０２とデータアレイ１０３）上にあることになる。
【００７４】
キャッシュ制御ユニット１０５は、比較器１０４からの比較結果１１２、アクセスが読み出しか書き込みかを示す情報１１３、および、アドレスアレイ１０２からの状態他ビット列１０７に基づいて、キャッシュメモリ（具体的には、アドレスアレイ１０２とデータアレイ１０３）を制御する。
【００７５】
制御部１１５は、一般的に制御手段と呼ぶことができる。
【００７６】
制御部１１５は、キャッシュメモリシステム１の動作を制御する。
【００７７】
図１Ｂは、制御部１１５が有する機能を機能部として示したブロック図である。
【００７８】
図１Ｂにおいて、制御部１１５は、書込み部１１５ａと、読出し部１１５ｂと、判断部１１５ｃと、データ転送部１１５ｄとを含む。
【００７９】
書込み部１１５ａは、一般的に書込み手段と呼ぶことができる。
【００８０】
書込み部１１５ａは、ＣＰＵ２からの書込み時に、ＣＰＵ２からのアドレスが、アドレスアレイ１０２（具体的には、中位ｎビット１０９に対応するオフセットごとに上位ｍビット１０６を格納する部分）内にない場合、データアレイ１０３内の複数のブロックのいずれかを書込み用ブロックとして割り当てる。
【００８１】
書込み部１１５ａは、ＣＰＵ２からのアドレスに対応するブロックのデータをメモリ３から読み込まずに、その書込み用ブロック内のいずれかのワードを、ＣＰＵ２からのアドレスに対応づけ、そのワードにＣＰＵ２からのデータを書き込む。
【００８２】
読出し部１１５ｂは、一般的に読出し手段と呼ぶことができる。
【００８３】
読出し部１１５ｂは、ＣＰＵ２からの読み出し時に、ＣＰＵ２からのアドレスに対応するワード状態情報（W(i)＝１）をワード状態記憶部１０７ａが記憶している場合、または、ＣＰＵ２からのアドレスに対応するブロック状態情報（ＢＶ＝１）をブロック状態記憶部１０７ｂが記憶している場合、そのアドレスから特定される、データアレイ１０３内のワードからデータを読み出す。
【００８４】
また、読出し部１１５ｂは、ＣＰＵ２からの読み出し時にキャッシュミスが生じた時、ＣＰＵ２からのアドレスに対応するブロック内のデータをメモリ３から読み出す。
【００８５】
読出し部１１５ｂは、続いて、ワード状態記憶部１０７ａを参照して、データアレイ１０３のそのブロック内でＣＰＵ２からデータが書き込まれていない１つまたは複数のワードを特定する。
【００８６】
読出し部１１５ｂは、その特定された１つまたは複数のワードにだけ、メモリ３から読み出したブロックのデータを書き込む。
【００８７】
読出し部１１５ｂは、続いて、ブロック状態記憶部１０７ｂに、そのブロック内のＣＰＵ２から書き込まれていない１つまたは複数のワードに、メモリ３から読み出されたデータが記憶されていることを示すブロック状態情報（ＢＶ＝１）を記憶する。
【００８８】
判断部１１５ｃは、一般的に判断手段と呼ぶことができる。
【００８９】
判断部１１５ｃは、ＣＰＵ２からの読み出し時にＣＰＵ２からアドレスを受け付けた場合に、ワード状態記憶部１０７ａおよびブロック状態記憶部１０７ｂを参照して、そのアドレスについてキャッシュヒットまたはキャッシュミスが生じたかを判断する。
【００９０】
データ転送部１１５ｄは、一般的にデータ転送手段と呼ぶことができる。
【００９１】
データ転送部１１５ｄは、データアレイ１０３内のブロック内の指定された１つまたは複数のワードのデータだけを、メモリ３内の対応するブロックに書き込む。
【００９２】
例えば、データ転送部１１５ｄは、データアレイ１０３内のブロックと対応するメモリ３のアドレスが切り替えられる時、ワード状態記憶部１０７ａを参照して、そのブロック内のすべてのワードにＣＰＵ２からデータが書き込まれた場合には、そのブロック全体をメモリ３内の対応するブロックにライトバックする。そうでない場合には、そのブロック内でデータが書き込まれた１つまたは複数のワードを特定し、その特定された１つまたは複数のワード内のデータだけを、メモリ３内の対応するブロックにライトバックする。
【００９３】
なお、以下の説明では、アドレスレジスタ１０１に格納されるアドレスは、６４ビットとし、ｋ＝６、すなわちブロックのサイズを６４バイトとし、ｎ＝１０、すなわちアドレスアレイ１０２のアドレスエントリ数、および、データアレイ１０３のデータエントリ数を１０２４とし、ｍ＝４８とする。また、６４バイトのブロックは、８個のワードからなる。なお、１ワードは８バイトである。
【００９４】
本実施の形態では、ダイレクトマップ方式のキャッシュメモリを示しているが、セットアソシアティブ方式のキャッシュメモリでも本実施の形態のキャッシュメモリを適用することができる。その場合は、ウェイ数分、アドレスアレイ１０２、データアレイ１０３、および、比較器１０４が必要である。
【００９５】
次に、図１Ａおよび１Ｂに示したキャッシュメモリシステム１の動作を説明する。
【００９６】
キャッシュメモリシステム１へのアクセスがあった場合に、アドレスレジスタ１０１は、そのアドレスを格納する。なお、このアドレスは、論理アドレスでも物理アドレスでもよい。
【００９７】
本実施の形態では、このアドレスを、何らかのアドレス変換の手段により仮想アドレスから変換された物理アドレスとして説明を行う。
【００９８】
ブロックのサイズは６４バイトなので、アドレスレジスタ１０１の下位６（ｋ）ビット１１４のデータは、データアレイ１０３のブロック内のワードのアドレスとなる。
【００９９】
中位１０（ｎ）ビット１０９のデータが、アドレスアレイ１０２のオフセット１１０として使用されて、アドレスアレイ１０２のアドレスエントリ内のデータ（上位４８（ｍ）ビット１０６のデータと状態他ビット列１０７のデータ）が読み出される。
【０１００】
比較器１０４は、読み出された上位４８（ｍ）ビット１０６のデータと、アドレスレジスタ１０１内の上位４８（ｍ）ビット１１１のデータと、を比較して、アドレスレジスタ１０１内のアドレスにて指定されたデータを含むブロックが、すでにキャッシュメモリにあるかどうかを判断する。
【０１０１】
キャッシュ制御ユニット１０５は、比較器１０４の比較結果１１２と、情報１１３と、状態他ビット列１０７とを受け付ける。
【０１０２】
キャッシュ制御ユニット１０５は、比較結果１１２、情報１１３、および、ビット列１０７に基づいて、キャッシュメモリの動作を決定する。
【０１０３】
キャッシュ制御ユニット１０５の動作の詳細ついては、後述する。
【０１０４】
図２は、アドレスアレイ１０２に格納される状態他ビット列１０７の一例を示した説明図である。
【０１０５】
状態他ビット列１０７は、９ビットで構成される。具体的には、状態他ビット列１０７は、１ビットのＢＶ２０２と、８ビットのW(i)（i＝1〜8）２０３とからなる。W(i)（i＝1〜8）２０３は、１ビットのW(1)〜W(8)からなる。
【０１０６】
W(1)〜W(8)２０３は、データアレイ１０３のブロックデータの各ワードのアドレス、すなわち各ワードに対応する。ブロックデータは、８ワードからなるので、W(1)は、ブロックデータ２０４の１ワード目に対応し、W(2)は２ワード目、W(3)は３ワード目、W(4)は４ワード目、W(5)は５ワード目、W(6)は６ワード目、W(7)は７ワード目、W(8)は８ワード目に対応する。
【０１０７】
W(i)２０３の値が１のときは、i番目のワードにＣＰＵ２からデータが書き込まれたことを示す。つまり、W(i)２０３が１のときは、ブロックデータ２０４のi番目のワードには、ＣＰＵ２から書き込まれた有効なデータが格納されていることになる。
【０１０８】
W(i)２０３の値が０のときは、i番目のワードにＣＰＵ２からデータが書き込まれていないことを示す。
【０１０９】
ＢＶ２０２は、ＢＶ２０２を含むアドレスエントリに対応する、データアレイ１０３内のブロック全体が有効かどうかを示す。
【０１１０】
具体的には、ＢＶ２０２の値が１のときは、ＣＰＵ２から書き込まれていないワード（Ｗ(i) ２０３が０）にメモリ３から読み出されたデータが格納されていることを示しており、対応するブロック全体が有効であることを意味する。すなわち、ＢＶ２０２の値が１のときは、i番目のワードの状態を示すW(i)２０３の値が０、つまり、W(i)２０３がi番目のワードにＣＰＵ２からデータが書き込まれていないことを示す場合であったとしても、i番目のワードにメモリ３から読み出されたデータが書き込まれたことによりi番目のワードに有効なデータが格納されていることを示す。
【０１１１】
また、ＢＶ２０２の値が０の場合には、i番目のワードの状態を示すW(i)２０３の値が１であるワードのデータだけが有効で、W(i)２０３の値が０であるワードのデータは無効であることを示す。
【０１１２】
図３は、図２に示したＢＶ２０２とW(i)２０３の値によるi番目のワードの有効／無効を示す説明図である。
【０１１３】
次に、図１Ａ、図１Ｂおよび図２を参照しながら、第１の実施の形態の動作について詳細に説明する。
【０１１４】
図４は、キャッシュ制御ユニット１０５の動作を説明するためのフローチャートである。
【０１１５】
アドレスレジスタ１０１が、キャッシュメモリにアクセスされたアドレスを格納すると、その後、そのアドレスの中位１０（ｎ）ビット１０９のデータが、アドレスアレイ１０２およびデータアレイ１０３のオフセット１１０として使用されて、アドレスアレイ１０２のアドレスエントリ内の上位４８（ｍ）ビット１０６のデータと状態他ビット列１０７のデータが読み出され、データアレイ１０３のデータエントリがアクセスされる。
【０１１６】
比較器１０４は、読み出された上位４８（ｍ）ビット１０６のデータと、アドレスレジスタ１０１内の上位４８（ｍ）ビット１１１のデータと、を比較して、アドレスレジスタ１０１内のアドレスにて指定されたデータを含むブロックが、すでにキャッシュメモリにあるかどうかを判断する。
【０１１７】
キャッシュ制御ユニット１０５は、比較器１０４の比較結果１１２と、状態他ビット列１０７のデータと、アクセスが読み出しか書き込みかを示す情報１１３と、を受け付ける。
【０１１８】
なお、情報１１３は、ＣＰＵ２から提供される。また、キャッシュ制御ユニット１０５は、下位６（ｋ）ビットのデータも受け付ける。また、キャッシュ制御ユニット１０５は、アクセスが書き込みの場合、ＣＰＵ２から書き込み用データも受け付ける。
【０１１９】
キャッシュ制御ユニット１０５は、情報１１３に基づいて、アクセスが書き込みなのか読み出しなのかを判断する（ステップ４０１）。
【０１２０】
まず、アクセスが書き込みの場合（ステップ４０２）、キャッシュ制御ユニット１０５は、ステップ４０３を実行する。
【０１２１】
ステップ４０３では、キャッシュ制御ユニット１０５は、比較器１０４の比較結果１１２に基づいて、アクセスされたブロックを格納しているエントリが、すでにキャッシュ（アドレスアレイ１０２とデータアレイ１０３）にあるかどうかを判断する。
【０１２２】
比較結果１１２が一致を示す場合、キャッシュ制御ユニット１０５は、アクセスされたブロックはキャッシュにあると判断する（ステップ４０４）。
【０１２３】
一方、比較結果１１２が一致を示さない場合は、キャッシュ制御ユニット１０５は、アクセスされたブロックがキャッシュにないと判断する（ステップ４０５）。
【０１２４】
アクセスされたブロックがキャッシュにあった場合は（ステップ４０４）、キャッシュ制御ユニット１０５は、下位６（ｋ）ビットのデータに基づいて、そのブロックのデータ１０８内のワードを特定し、そのワードに対して、書き込み用データを書き込み（ステップ４０６）、データが書き込まれたワードに対応するW(i) ２０３の値を１にする（ステップ４０７）。
【０１２５】
アクセスされたブロックがキャッシュにない場合は（ステップ４０５）、キャッシュ制御ユニット１０５は、新しいブロックを割り当てる処理を行う（ステップ４０８）。
【０１２６】
新しいブロックを割り当てる処理（ステップ４０８）については、後に、図５を使って詳しく述べる。
【０１２７】
ステップ４０８の後、キャッシュ制御ユニット１０５は、新しく割り当てたデータアレイ１０３のブロックに対応するアドレスアレイ１０２のエントリの上位４８（ｍ）ビット１０６に、アドレスレジスタ１０１の上位４８（ｍ）ビット１１１のデータを書き込み、同じく対応するアドレスアレイ１０２のエントリの状態他のビット列１０７をゼロクリア（BV＝0、W(1〜8)＝0）して初期化する（ステップ４０９）。
【０１２８】
ステップ４０９の後、キャッシュ制御ユニット１０５は、下位６（ｋ）ビットのデータに基づいて、新しく割り当てたデータアレイ１０３のブロック内のワードを特定し、そのワードに対して、書き込み用データを書き込み（ステップ４０６）、データが書き込まれたワードに対応するW(i) ２０３の値を１にする（ステップ４０７）。
【０１２９】
一方、アクセスが読み出しの場合（ステップ４１０）、キャッシュ制御ユニット１０５は、ステップ４１１を実行する。
【０１３０】
ステップ４１１では、キャッシュ制御ユニット１０５は、比較器１０４の比較結果１１２に基づいて、アクセスされたブロックを格納しているエントリが、すでにキャッシュにあるかどうかを判断する。
【０１３１】
比較結果１１２が一致を示す場合、キャッシュ制御ユニット１０５は、アクセスされたブロックはキャッシュにあると判断する（ステップ４１２）。
【０１３２】
一方、比較結果１１２が一致を示さない場合は、キャッシュ制御ユニット１０５は、アクセスされたブロックがキャッシュにないと判断する（ステップ４１３）。
【０１３３】
アクセスされたブロックがキャッシュにあり（ステップ４１２）、かつ、アクセスされたワードに対応するW(i)の値が１またはアクセスされたブロックのＢＶが１の場合（ステップ４２０）、キャッシュ制御ユニット１０５は、データアレイ１０３のアクセスされたブロックデータ１０８内のワードからデータを読み出す（ステップ４１４）。
【０１３４】
一方、アクセスされたブロックがキャッシュにあり（ステップ４１２）、かつ、アクセスされたワードに対応するW(i)の値が０でかつアクセスされたブロックのＢＶが０の場合（ステップ４１５）、キャッシュ制御ユニット１０５は、メモリ３から、そのブロックのデータを読み出し、データアレイ１０３のそのエントリのブロックデータ１０８中のW(i)＝0のワードだけに、読み出したデータを書き込む（ステップ４１６）。
【０１３５】
続いて、キャッシュ制御ユニット１０５は、そのブロックに対応するアドレスアレイ１０２のエントリ内のＢＶ２０２を１にする（ステップ４１７）。
【０１３６】
続いて、キャッシュ制御ユニット１０５は、データアレイ１０３から、アクセスされたワードからデータを読み出す（ステップ４１４）。
【０１３７】
アクセスされたブロックがキャッシュにない場合（ステップ４１３）、キャッシュ制御ユニット１０５は、新しいブロックを割り当てる処理を行う（ステップ４１８）。
【０１３８】
新しいブロックを割り当てる処理（ステップ４１８）については、後に図５を使って詳しく述べる。
【０１３９】
続いて、キャッシュ制御ユニット１０５は、新しく割り当てたブロックに対応するアドレスアレイ１０２のエントリの上位４８（ｍ）ビット１０６に、アドレスレジスタ１０１の上位４８（ｍ）ビット１１１のデータを書き込み、同じく対応するアドレスアレイ１０２のエントリの状態他のビット列１０７をゼロクリア（BV＝0、W(1〜8)＝0）して、初期化する（ステップ４１９）。
【０１４０】
続いて、キャッシュ制御ユニット１０５は、メモリ３から、そのブロックのデータを読み出し、そのブロックに対応するデータアレイ１０３のエントリのブロックデータ１０８中のW(i)＝0のワードだけに、読み出したデータを書き込む（ステップ４１６）。この場合、ステップ４１９で状態他のビット列１０７をゼロクリアしているので、ブロックデータ１０８全体が書かれる。
【０１４１】
続いて、キャッシュ制御ユニット１０５は、アドレスアレイ１０２の対応するエントリ内のＢＶ２０２を１にする（ステップ４１７）。
【０１４２】
続いて、キャッシュ制御ユニット１０５は、データアレイ１０３から、アクセスされたワードを読み出す（ステップ４１４）。
【０１４３】
次に、図５を参照して、図４に示したステップ４０８および４１８について説明する。
【０１４４】
まず、キャッシュ制御ユニット１０５は、新しいエントリを割り当てるために、データが置き換えられるエントリを選択する（ステップ５０１）。
【０１４５】
本実施形態では、ダイレクトマップ方式のキャッシュメモリが用いられている。このため、新しいブロックを割り当てるためにデータが置き換えられるエントリは、アクセスされたアドレスから一意に決まる。
【０１４６】
もしも、セットアソシアティブ方式のキャッシュメモリが用いられた場合には、アドレスから決定される置き換え対象になるエントリは複数あり、その中のどれを置き換えるかはアクセス履歴等により決定することが可能である。
【０１４７】
次に、キャッシュ制御ユニット１０５は、データが置き換えられるエントリのブロックに、ＣＰＵ２からデータが書き込まれているかどうか判断する。
【０１４８】
もし、選択されたエントリのすべてのワードのW(i)２０３が０ならば（ステップ５０２）、そのブロックには、ＣＰＵ２からデータが書き込まれていなかったことになる。この場合、キャッシュ制御ユニット１０５は、ライトバックすることなく、そのまま、そのエントリを使うことができる。
【０１４９】
もし、選択されたエントリのすべてのワードのW(i)２０３が１の場合（ステップ５０３）には、そのブロック全体が書き換えられたことになる。この場合、キャッシュ制御ユニット１０５は、そのブロック全体のデータをメモリ３にライトバックする（ステップ５０４）。
【０１５０】
もし、選択されたエントリの一部のワードのW(i)２０３が１の場合（ステップ５０５）には、Ｗ(i)２０３が１のワードだけが書き換えられたことになる。この場合、キャッシュ制御ユニット１０５は、W(i)２０３が１のワードのデータだけを、メモリ３にライトバックする（ステップ５０６）。なお、W(i)２０３が０のワードのデータは、メモリ３に書き込まない。
【０１５１】
なお、比較器１０４とキャッシュ制御ユニット１０５が行うデータの書込みに関する動作は、書込み部１１５ａによって行われる。
【０１５２】
また、比較器１０４とキャッシュ制御ユニット１０５が行うデータの読出しに関する動作は、読出し部１１５ｂによって行われる。
【０１５３】
また、比較器１０４とキャッシュ制御ユニット１０５が行うキャッシュヒットかキャッシュミスかの判断に関する動作は、判断部１１５ｃによって行われる。
【０１５４】
また、比較器１０４とキャッシュ制御ユニット１０５が行うデータアレイ１０３とメモリ３との間のデータ転送に関する動作はデータ転送部１１５ｄによって行われる。
【０１５５】
図６は、キャッシュメモリシステム１（具体的には、キャッシュ制御ユニット１０５）がメモリ３に送るコマンドと、そのコマンドに対するメモリ３からキャッシュメモリシステム１（具体的には、キャッシュ制御ユニット１０５）へのリプライを説明するための説明図である。
【０１５６】
図６（Ａ）と図６（Ｂ）は、ブロック全体を読み出すコマンドとそのリプライの一例を示した説明図である。
【０１５７】
本実施形態では、アドレスは６４ビットで、ブロックの大きさは６４バイトなので、メモリ３は、そのコマンドのブロックアドレス６０１（５８ビット）で指定されるブロックを読み出して、図６（Ｂ）で示すデータリプライの形式で、ブロックデータ６０２（６４バイト）を、キャッシュ制御ユニット１０５に送る。
【０１５８】
図６（Ｃ）は、キャッシュメモリシステム１（具体的には、キャッシュ制御ユニット１０５）が、ブロック全体をメモリ３に書き込むコマンドの一例を示した説明図である。
【０１５９】
このコマンドは、ブロックアドレス６０３（５８ビット）と、ブロックデータ６０４（６４バイト）から構成される。
【０１６０】
図６（Ｄ）は、ブロックデータ６０４内のワードうち、W(i)２０３が１のワードのデータだけを、キャッシュメモリシステム１からメモリ３に書き込むためのコマンドの一例である。
【０１６１】
このコマンドは、ブロックアドレス６０５（５８ビット）と、W(1〜8)６０６（８ビット）と、W(i)２０３が１のワード（８バイト〜５４バイト）のデータからなる部分ブロックデータ６０７と、を含む。
【０１６２】
このコマンドは、W(i)２０３が１であるワードの個数に応じて長さが変わる。
【０１６３】
次に、図７〜図１５を使ってキャッシュ上のあるブロックを例にして、本実施形態での状態他のビット列とメモリアクセスなどの動作について説明する。
【０１６４】
図７は、ＣＰＵ２から１ワードの書き込みがあったときにキャッシュミスした場合の動作を説明するための説明図である。
【０１６５】
１ワードの書き込みにキャッシュミスが生じると、そのワードを含むブロックが新たにキャッシュメモリシステム１に割り付けられ（BV＝0、W＝00000000）、書き込みデータ７０３が、書き込み時のアドレスに応じて、データアレイ１０３のブロックデータ７０４の４ワード目に書き込まれ、状態他ビット列７０５のうち、書き込まれたワードに対応するW(4)が１に設定される(BV＝0、W＝00010000)。
【０１６６】
新たなブロックの割り付けに伴うブロックの置き換えにより、メモリアクセスが発生するかもしれないが、書き込み自体に伴ってメモリ３へのアクセスは発生しない。
【０１６７】
図８は、図７と同じブロックの２ワード目にＣＰＵ２から１ワードの書き込みがあり、キャッシュヒットした場合の動作を説明するための説明図である。
【０１６８】
１ワードの書き込みがキャッシュヒットして、データ８０２が、データアレイ１０２のブロックデータ８０３の２ワード目に書き込まれ、状態他ビット列８０４のW(2)が１となる(BV＝0、W＝01010000)。この場合も。書き込みによるメモリ３へのアクセスは発生しない。
【０１６９】
図９は、ＣＰＵ２が、図８と同じブロックの４ワード目を読み出し、キャッシュヒットした場合の動作を説明するための説明図である。
【０１７０】
１ワードの読み出しがキャッシュヒットして、データアレイ１０２のブロックデータ９０３の４ワード目からデータが読み出され、読み出しデータ９０２としてＣＰＵ２に返される。
【０１７１】
この場合、状態他ビット列９０４は更新されない（BV＝0、W＝01010000）。
【０１７２】
ただし、キャッシュメモリがセットアソシアティブ方式の場合は、置き換えのためのアクセス履歴の部分が更新される可能性がある。また、読み出しに伴うメモリ３へのアクセスは発生しない。
【０１７３】
図１０は、ＣＰＵ２が図９に示したブロックと同じブロックの６ワード目を読み出し、キャッシュミスした場合の動作を示している。
【０１７４】
状態他ビット列１００２が、W(6)＝０でかつＢＶ＝０なので、１ワードの読み出しがキャッシュミスして、キャッシュ制御ユニット１０５は、図６（Ａ）に示したコマンドを使って、メモリ３から、図９に示したブロックと同じブロックを読み出す。
【０１７５】
そして、メモリ３から読み出されたブロックのデータ１００４が、図６（Ｂ）のデータリプライの形式でキャッシュメモリシステム１（キャッシュ制御ユニット１０５）に返されると、読み出したブロックのデータ１００４のうち、W(i)＝０のワードのデータだけ（１番目、３番目、５〜８番目のワードのデータ）が、ブロック１００６に書き込まれ、状態他ビット列１００７のＢＶ２０２が１となる（BV＝1、W＝01010000）。
【０１７６】
そして、６番目のワードのデータが、読み出しデータ１００８として、ＣＰＵ２に返される。
【０１７７】
図１１は、ＣＰＵ２が、図１０に示したブロックと同じブロックの１ワード目を読み出し、キャッシュヒットした場合の動作を示している。
【０１７８】
状態他ビット列１１０２のＢＶ２０２が１なので、１ワードの読み出しがキャッシュヒットして、ブロックデータ１１０３の１ワード目が読み出しデータ１１０４としてＣＰＵ２に返される。
【０１７９】
この場合、状態他ビット列１１０２は更新されない（BV＝1、W＝01010000）。
【０１８０】
ただし、キャッシュメモリがセットアソシアティブ方式の場合は、置き換えのためのアクセス履歴の部分が更新される可能性がある。また、読み出しによるメモリアクセスは発生しない。
【０１８１】
図１２は、図１１に示したブロックと同じブロックのエントリが置き換えの対象になった場合の動作を示している。
【０１８２】
２ワード目と４ワード目がＣＰＵ２から書き込まれていて、状態他ビット列１２０２のW(2)とW(4)が１になっている(W＝01010000)ので、図６（Ｄ）に示したコマンドを使って、２ワード目と4ワード目のデータ１２０３、１２０４だけがメモリ３に書き込まれる。そして、状態他ビット列１２０２が初期化される(BV＝0、W＝00000000)。
【０１８３】
図１３は、ＣＰＵ２が、あるワードを読み出してキャッシュミスした場合の動作を示している。
【０１８４】
読み出されたワードのブロックはキャッシュメモリ１上になく、新しいブロックが割り当てられ、状態他ビット列１３０３が初期化される(BV＝0、W＝00000000)。
【０１８５】
続いて、読み出されたワードのブロックが、図６（Ａ）に示したコマンドを使って、メモリ３から読み出される。
【０１８６】
メモリ３から読み出されたブロック１３０５は、図６（Ｂ）のデータリプライの形式で、キャッシュメモリ１に返され、ブロックデータ１３０６に書き込まれる。
【０１８７】
続いて、状態他のビット列１３０７のＢＶが１になる(BV＝1、W＝00000000) 。そして、読み出しデータ１３０８がＣＰＵ２に返される。
【０１８８】
図１４は、図１３に示したブロックと同じブロックのエントリが置き換えの対象になった場合の動作を示している。
【０１８９】
このブロックの状態他のビット列１４０１のW(i)がすべて０なので(W=00000000)、ＢＶを０にするだけである(BV＝0、W＝00000000)。エントリの置き換えによるメモリアクセスは発生しない。
【０１９０】
図１５は、あるブロックのエントリが置き換えの対象になった場合の動作を示している。
【０１９１】
このブロックは状態他ビット列１５０１のW(i)がすべて１なので（W=11111111)、ブロックデータ１５０２全体が図６（Ｃ）のコマンドを使ってメモリ３に書き込まれる。
【０１９２】
続いて、状態他のビット列１５０１が初期化される(BV＝0、W＝00000000) 。
【０１９３】
次に、図１に示したような並列計算機で、図１８に示すループの並列処理を行った場合の動作と効果について、図１６Ａ〜図１６Ｆを用いて説明する。なお、図１６Ａ〜図１６Ｆにおいて、ＣＰＵ１６００〜１６０７は、メモリ３にアクセスして並列演算を行う。また、キャッシュメモリシステム１６１０〜１６１７は、図１Ａに示したキャッシュメモリシステム１と同一構成とする。
【０１９４】
ここでは、ＣＰＵ１６００〜１６０７がワードＡ０〜Ａ７に対して順番にデータを書き込むときの処理を説明する。
【０１９５】
図１６Ａは、ループに入る前の状態である。
【０１９６】
まず、ＣＰＵ１６００が、ワードＡ０にデータを書き込もうとして、キャッシュミスが起こると、ＣＰＵ１６００は、キャッシュメモリシステム１６１０上に、ワードＡ０〜Ａ７のブロックを割り当てて、ワードＡ０に、データA(0,2)’を書き込む（BV＝0、W＝10000000）（図１６Ｂ参照)。
【０１９７】
次に、ＣＰＵ１６０１が、ワードＡ１にデータを書き込もうとして、キャッシュミスが起こると、ＣＰＵ１６０１は、キャッシュメモリシステム１６１１上に、ワードＡ０〜Ａ７のブロックを割り当てて、ワードＡ１に、データA(1,2)’を書き込む（(BV＝0、W＝01000000)（図１６Ｃ参照）。
【０１９８】
次に、ＣＰＵ１６０２が、ワードＡ２にデータを書き込もうとして、キャッシュミスが起こると、ＣＰＵ１６０２は、キャッシュメモリシステム１６１２上に、ワードＡ０〜Ａ７のブロックを割り当てて、ワードＡ２に、データA(2,2)’を書き込む（BV＝0、W＝00100000）（図１６Ｄ参照)。
【０１９９】
以下同様の処理を、ＣＰＵ１６０３〜ＣＰＵ１６０６が行い、続いて、ＣＰＵ１６０７が、ワードＡ７にデータを書き込もうとして、キャッシュミスが起こると、ＣＰＵ１６０７は、キャッシュメモリシステム１６１７上に、ワードＡ０〜Ａ７のブロックを割り当てて、ワードＡ７に、データA(7,2)’を書き込む（BV＝0、W＝00000001）（図１６Ｅ参照)。
【０２００】
最後に、各ＣＰＵ１６００〜１６０７が、キャッシュメモリ上の更新をメモリ３に反映するために、更新データをメモリ３にライトバックする（図１６Ｆ参照）。
【０２０１】
各ＣＰＵからは、書き込んだワードのデータだけがメモリ３に書き込まれるので、ライトバックは、同時に行われなくてもよい。
【０２０２】
すべてのＣＰＵからのライトバックが完了した時点で、最新のデータがメモリ３上に格納される。
【０２０３】
このように、本実施の形態のキャッシュメモリを用いた場合には、最後のキャッシュからメモリへのライトバックのときにだけ、メモリアクセスが発生する。つまり、書き込み時に、メモリアクセスは発生しない。
【０２０４】
一方、図２０で説明した方法では、共有メモリからのブロックの読み出しが８回、共有メモリへのブロックの書き込みが７回発生する。
【０２０５】
本実施の形態によれば、制御部１１５（書込み部１１５ａ）は、ＣＰＵ２からの書込み時に、ＣＰＵ２からのアドレスがアドレスアレイ１０２（中位ｎビット１０９に対応するオフセットごとに上位ｍビット１０６を格納する部分）内にない場合、データアレイ１０３内の複数のブロックのいずれかを書込み用ブロックとして割り当てる。そして、制御部１１５（書込み部１１５ａ）は、その書込み用ブロック内のいずれかのワードを、ＣＰＵ２からのアドレスに対応づけ、そのワードにＣＰＵ２からのデータを書き込む。
【０２０６】
ワード状態記憶部１０７ａは、ＣＰＵ２からのデータが書き込まれたワードを特定するためのワード状態情報を、そのワードに対応づけられたアドレスと関連づけて記憶する。
【０２０７】
メモリ上の前記書き込み用ブロックが異なるブロックに置き換えられる時、制御部１１５（データ転送部１１５ｄ）は、ワード状態記憶部１０７ａを参照して、そのブロック内でデータが書き込まれた１つまたは複数のワードを特定し、その特定された１つまたは複数のワード内のデータだけを、メモリ３内の対応するブロックにライトバックする。
【０２０８】
このため、キャッシュメモリへのデータ書き込み時にキャッシュミスが発生した場合に、メモリ３からデータを読み出すことなく、ワード単位でデータをキャッシュメモリに格納することが可能となる。また、ライトバックする時は、ＣＰＵ２から書き込まれたデータのみを、メモリ３に書き込むことが可能となる。
【０２０９】
よって、図１８に示すようなループを複数のＣＰＵで並列処理する場合、１つのブロックが複数のＣＰＵにより書き込まれた場合でも、ＣＰＵからの書き込みごとに、ブロックのデータを読み出すためのメモリ読み出しを行わなくてもよくなる。
【０２１０】
また、ＣＰＵの書き込みごとに、他のＣＰＵのキャッシュを無効化してメモリ３にライトバックさせなくてもよくなる。
【０２１１】
また、ループ実行終了時に各ＣＰＵが明示的にキャッシュメモリ上のブロックをライトバックする場合に、それぞれ独立に行うことができる。それぞれ別のタイミングでライトバックしても、すべてのライトバックが完了した時点で、メモリ３には最新のデータが格納される。
【０２１２】
したがって、ＤＯループ実行中の無駄なキャッシュの一貫性制御によるメモリアクセスを行わないキャッシュメモリシステムを提供することが可能になる。
【０２１３】
なお、本実施形態のキャッシュメモリシステム１において、アドレスレジスタ１０１、ブロック状態記憶部１０７ｂ、読出し部１１５ｂ、および、判断部１１５ｃが省略されても、上記と同様の作用効果を生じる。
【０２１４】
また、本実施形態では、読出し部１１５ｂは、ＣＰＵ２からの読み出し時に、ＣＰＵ２からのアドレスに対応するワード状態情報をワード状態記憶部１０７ａが記憶している場合、そのワード状態情報にて特定されるワードからデータを読み出す。
【０２１５】
この場合、メモリ３と通信することなく、その書き換えられたデータをＣＰＵ２に提供することが可能となる。
【０２１６】
また、本実施形態では、ブロック状態記憶部１０７ｂは、データアレイ１０３のブロックに対応するアドレス群ごとに、そのブロック内のＣＰＵ２から書き込まれていないワードに、メモリ３から読み出されたデータが記憶されているか否かを示すブロック状態情報（BV）を記憶する。
【０２１７】
そして、制御部１１５（判断部１１５ｃ）は、ＣＰＵ２からの読み出し時にＣＰＵ２からアドレスを受け付けた場合に、ワード状態記憶部１０７ａおよびブロック状態記憶部１０７ｂを参照して、そのアドレスについてキャッシュヒットまたはキャッシュミスが生じたかを判断する。
【０２１８】
この場合、ワード単位で、キャッシュヒットか否かを判断することが可能となる。
【０２１９】
また、本実施形態では、制御部１１５（読出し部１１５ｂ）は、ＣＰＵ２からの読み出し時にキャッシュミスが生じた時、ＣＰＵ２からのアドレスに対応するブロック内のデータをメモリ３から読み出す。
【０２２０】
さらに、制御部１１５（読出し部１１５ｂ）は、ワード状態記憶部１０７ａを参照して、データアレイ１０３のそのブロック内でデータが書き込まれていない１つまたは複数のワードを特定する。
【０２２１】
さらに、制御部１１５（読出し部１１５ｂ）は、その特定された１つまたは複数のワードにだけ、メモリ３から読み出したブロックのデータを書き込む。
【０２２２】
さらに、制御部１１５（読出し部１１５ｂ）は、ブロック状態記憶部１０７ｂに、そのブロック内のＣＰＵ２からデータが書き込まれていない１つまたは複数のワードに、メモリ３から読み出されたデータが記憶されていることを示すブロック状態情報を記憶する。
【０２２３】
この場合、データアレイ１０３に格納する必要があるデータだけをデータアレイ１０３に書き込むことが可能になり、その書き込みが行われたことをブロック状態記憶部１０７ｂに記憶することが可能になる。
【０２２４】
なお、本実施形態は、並列計算機のキャッシュメモリといった用途に適用できる。
【０２２５】
以上説明した実施形態において、図示した構成は単なる一例であって、本発明はその構成に限定されるものではない。
【図面の簡単な説明】
【０２２６】
【図１Ａ】本発明の第１の実施の形態のキャッシュメモリの構成を示す図である。
【図１Ｂ】制御部１１５の機能ブロックを示したブロック図である。
【図２】キャッシュメモリの状態他のビット列を示す図である。
【図３】キャッシュメモリの状態他のビット列とブロックデータの有効／無効との関係を示す図である。
【図４】キャッシュメモリの動作を表すフローチャートである。
【図５】キャッシュメモリの新しいブロックを割り当てる場合の動作を表すフローチャートである。
【図６】キャッシュメモリのキャッシュからメモリに送るコマンドと、それに対するメモリからキャッシュへのリプライと、その機能について説明している図である。
【図７】キャッシュメモリの書き込み時のキャッシュミスの動作を説明している図である。
【図８】キャッシュメモリの書き込み時のキャッシュヒットの動作を説明している図である。
【図９】キャッシュメモリの読み出し時のキャッシュヒットの動作を説明している図である。
【図１０】キャッシュメモリの読み出し時のキャッシュミスの動作を説明している図である。
【図１１】キャッシュメモリの読み出し時のキャッシュミスの動作を説明している図である。
【図１２】キャッシュメモリのエントリの置き換え時の動作を説明している図である。
【図１３】キャッシュメモリの読み出し時のキャッシュミスの動作を説明している図である。
【図１４】キャッシュメモリのエントリの置き換え時の動作を説明している図である。
【図１５】キャッシュメモリのエントリの置き換え時の動作を説明している図である。
【図１６Ａ】並列計算機の動作を説明している図である。
【図１６Ｂ】並列計算機の動作を説明している図である。
【図１６Ｃ】並列計算機の動作を説明している図である。
【図１６Ｄ】並列計算機の動作を説明している図である。
【図１６Ｅ】並列計算機の動作を説明している図である。
【図１６Ｆ】並列計算機の動作を説明している図である。
【図１７】並列計算機の構成を説明した図である。
【図１８】並列計算機で並列に処理するプログラム例を示した図である。
【図１９】並列計算機で並列に処理するプログラム例での配列のキャッシュメモリのブロックでの配置を説明した図である。
【図２０Ａ】無効化型一貫性制御のライトバック型キャッシュメモリを用いた並列計算機での動作を説明している図である。
【図２０Ｂ】無効化型一貫性制御のライトバック型キャッシュメモリを用いた並列計算機での動作を説明している図である。
【図２０Ｃ】無効化型一貫性制御のライトバック型キャッシュメモリを用いた並列計算機での動作を説明している図である。
【図２０Ｄ】無効化型一貫性制御のライトバック型キャッシュメモリを用いた並列計算機での動作を説明している図である。
【図２０Ｅ】無効化型一貫性制御のライトバック型キャッシュメモリを用いた並列計算機での動作を説明している図である。
【図２０Ｆ】無効化型一貫性制御のライトバック型キャッシュメモリを用いた並列計算機での動作を説明している図である。
【図２０Ｇ】無効化型一貫性制御のライトバック型キャッシュメモリを用いた並列計算機での動作を説明している図である。
【図２０Ｈ】無効化型一貫性制御のライトバック型キャッシュメモリを用いた並列計算機での動作を説明している図である。
【符号の説明】
【０２２７】
１、４、６  キャッシュメモリ
２、５、７  ＣＰＵ
３          共有メモリ
１０１      アドレスレジスタ
１０２      アドレスアレイ
１０３      データアレイ
１０４      比較器
１０５      キャッシュ制御ユニット
１１５      制御部
１１５ａ    書込み部
１１５ｂ    読出し部
１１５ｃ    判断部
１１５ｄ    データ転送部
１０７ａ    ワード状態記憶部
１０７ｂ    ブロック状態記憶部
【図１Ａ】
2009151457.tif 000003
【図１Ｂ】
2009151457.tif 000004
【図２】
2009151457.tif 000005
【図３】
2009151457.tif 000006
【図４】
2009151457.tif 000007
【図５】
2009151457.tif 000008
【図６】
2009151457.tif 000009
【図７】
2009151457.tif 000010
【図８】
2009151457.tif 000011
【図９】
2009151457.tif 000012
【図１０】
2009151457.tif 000013
【図１１】
2009151457.tif 000014
【図１２】
2009151457.tif 000015
【図１３】
2009151457.tif 000016
【図１４】
2009151457.tif 000017
【図１５】
2009151457.tif 000018
【図１６Ａ】
2009151457.tif 000019
【図１６Ｂ】
2009151457.tif 000020
【図１６Ｃ】
2009151457.tif 000021
【図１６Ｄ】
2009151457.tif 000022
【図１６Ｅ】
2009151457.tif 000023
【図１６Ｆ】
2009151457.tif 000024
【図１７】
2009151457.tif 000025
【図１８】
2009151457.tif 000026
【図１９】
2009151457.tif 000027
【図２０Ａ】
2009151457.tif 000028
【図２０Ｂ】
2009151457.tif 000029
【図２０Ｃ】
2009151457.tif 000030
【図２０Ｄ】
2009151457.tif 000031
【図２０Ｅ】
2009151457.tif 000032
【図２０Ｆ】
2009151457.tif 000033
【図２０Ｇ】
2009151457.tif 000034
【図２０Ｈ】
2009151457.tif 000035