(57)【要約】【課題】キャッシュミス発生時の主記憶メモリへのアクセス回数を低減する。【解決手段】記憶手段と、第１のデータアドレスに含まれる第１のインデックスに対応し、前記記憶手段に含まれる第１のキャッシュラインにおいてキャッシュミスが発生する際、当該キャッシュ内リプレースのリプレース先に今まではなっておらず、ダーティビットがクリーンであり、前記記憶手段に含まれる第２のキャッシュラインにおいてキャッシュストアを実行することによりキャッシュ内リプレースを実施する制御手段と、を備える。【選択図】図２
2016157278.tif 000002
【特許請求の範囲】
【請求項１】
キャッシュメモリであって、
記憶手段と、
第１のデータアドレスに含まれる第１のインデックスに対応し、前記記憶手段に含まれる第１のキャッシュラインにおいてキャッシュミスが発生する際、当該キャッシュ内リプレースのリプレース先に今まではなっておらず、ダーティビットがクリーンであり、前記記憶手段に含まれる第２のキャッシュラインにおいてキャッシュストアを実行することによりキャッシュ内リプレースを実施する制御手段と、
を備えることを特徴とするキャッシュメモリ。
【請求項２】
請求項１に記載のキャッシュメモリであって、
前記第１のインデックスから、前記第２のキャッシュラインに対応する第２のインデックスへの変換制御情報を記憶するインデックス変換手段であって、第２のデータアドレスが読み込まれ、該第２のデータアドレスに前記第１のインデックスが含まれる際、前記変換制御情報に基づき、前記第２のデータアドレスに含まれる前記第１のインデックスを前記第２のインデックスに変換し、該第２のインデックスを前記制御手段に出力するインデックス変換手段を更に備え、
前記制御手段は、前記インデックス変換手段からの前記第２のインデックスの入力に応じて、前記第２のキャッシュラインをアクセス先の候補とすることを特徴とするキャッシュメモリ。
【請求項３】
請求項２に記載のキャッシュメモリであって、
前記制御手段が、前記第２のインデックスの入力に応じて前記第２のキャッシュラインをアクセス先の候補とする際、前記第２のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記第２のキャッシュラインにおいてキャッシュストアを実行することを特徴とするキャッシュメモリ。
【請求項４】
請求項２又は３に記載のキャッシュメモリであって、
前記制御手段が、前記第２のインデックスの入力に応じて前記第２のキャッシュラインをアクセス先の候補とする際、前記第２のキャッシュラインにおいてキャッシュミスが発生する場合に、前記第１のキャッシュラインをアクセス先の候補とし、前記第１のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記第１のキャッシュラインにおいてキャッシュストアを実行することを特徴とするキャッシュメモリ。
【請求項５】
請求項２乃至４のいずれか１項に記載のキャッシュメモリであって、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが有効となっている場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュストアの後、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグを無効に設定し、前記第１のキャッシュラインに含まれるダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが無効になっており、前記第１のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュストアの後、前記第１のキャッシュラインに含まれる前記ダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが無効になっており、前記第１のキャッシュラインにおいてキャッシュミスが発生し、前記第２のキャッシュラインが存在する場合に、前記制御手段が、前記第２のキャッシュラインにおけるキャッシュストアの後、前記第２のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグを有効に設定し、前記第２のキャッシュラインに含まれるダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが無効になっており、前記第１のキャッシュラインにおいてキャッシュミスが発生し、前記第２のキャッシュラインが存在しない場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュストアの後、前記第１のキャッシュラインに含まれるダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって前記第２のインデックスに変換され、前記第２のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記制御手段が、前記第２のキャッシュラインにおけるキャッシュストアの後、前記第２のキャッシュラインに含まれるダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって前記第２のインデックスに変換され、前記第２のキャッシュラインにおいてキャッシュミスが発生し、前記第１のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュストアの後、前記第１のキャッシュラインに含まれるダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって前記第２のインデックスに変換され、前記第２のキャッシュラインにおいてキャッシュミスが発生した後、更に、前記第１のキャッシュラインにおいてもキャッシュミスが発生する場合に、前記制御手段が、前記第２のキャッシュラインにおけるキャッシュストアの後、前記第２のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグを無効に設定し、前記第２のキャッシュラインに含まれるダーティビットをダーティに設定することを特徴とするキャッシュメモリ。
【請求項６】
請求項２乃至５のいずれか１項に記載のキャッシュメモリであって、
前記制御手段が、前記第２のインデックスの入力に応じて前記第２のキャッシュラインをアクセス先の候補とする際、前記第２のキャッシュラインにおいてキャッシュヒットが発生する場合は、前記第２のキャッシュラインにおいてキャッシュロードを実行することを特徴とするキャッシュメモリ。
【請求項７】
請求項２乃至６のいずれか１項に記載のキャッシュメモリであって、
前記制御手段が、前記第２のインデックスの入力に応じて前記第２のキャッシュラインをアクセス先の候補とする際、前記第２のキャッシュラインにおいてキャッシュミスが発生する場合は、前記第１のキャッシュラインをアクセス先の候補とし、前記第１のキャッシュラインにおいてキャッシュヒットが発生する場合は、前記第１のキャッシュラインにおいてキャッシュロードを実行することを特徴とするキャッシュメモリ。
【請求項８】
請求項２乃至７のいずれか１項に記載のキャッシュメモリであって、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが有効となっている場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュロードの後、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグを無効に設定し、前記第１のキャッシュラインに含まれるダーティビットをクリーンに設定し、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが無効になっており、前記第１のキャッシュラインにおいてキャッシュミスが発生する場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュロードの後、前記第１のキャッシュラインに含まれるダーティビットをクリーンに設定し、
前記第１のインデックスが前記インデックス変換手段によって前記第２のインデックスに変換され、前記第２のキャッシュラインにおいてキャッシュミスが発生した後、更に、前記第１のキャッシュラインにおいてもキャッシュミスが発生する場合に、前記制御手段が、前記第２のキャッシュラインにおけるキャッシュロードの後、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグと、前記第２のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグとの双方を無効に設定し、前記第２のキャッシュラインに含まれるダーティビットをクリーンに設定することを特徴とするキャッシュメモリ。
【請求項９】
キャッシュメモリにおけるアクセス方法であって、
制御手段が、第１のデータアドレスに含まれる第１のインデックスに対応し、記憶手段に含まれる第１のキャッシュラインにおいてキャッシュミスが発生する際、当該キャッシュ内リプレースのリプレース先に今まではなっておらず、ダーティビットがクリーンであり、前記記憶手段に含まれる第２のキャッシュラインにおいてキャッシュストアを実行することによりキャッシュ内リプレースを実施するステップを有することを特徴とするアクセス方法。
【請求項１０】
キャッシュメモリにおけるアクセス方法をコンピュータに実行させるためのキャッシュメモリアクセス用プログラムであって、
前記アクセス方法は、
制御手段が、第１のデータアドレスに含まれる第１のインデックスに対応し、記憶手段に含まれる第１のキャッシュラインにおいてキャッシュミスが発生する際、当該キャッシュ内リプレースのリプレース先に今まではなっておらず、ダーティビットがクリーンであり、前記記憶手段に含まれる第２のキャッシュラインにおいてキャッシュストアを実行することによりキャッシュ内リプレースを実施するステップを有することを特徴とするキャッシュメモリアクセス用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、主メモリとこれへのアクセス元との間に設けられたキャッシュメモリ、キャッシュメモリにおけるアクセス方法、及びキャッシュメモリアクセス用プログラムに関する。
【背景技術】
【０００２】
主記憶メモリとして利用されるＤＲＡＭ（Dynamic Random Access Memory）は構造的に高速化しにくく、マイクロプロセッサが主記憶メモリにアクセスすることで発生するレイテンシは、コンピュータ・システム性能を著しく抑制する。一方で、近年のマイクロプロセッサの多くには、キャッシュメモリの役割を果たすＳＲＡＭ（Static Random Access Memory）を内包しており、予め主記憶メモリのデータの一部をキャッシュメモリに格納しておくことで、主記憶メモリへのアクセス・レイテンシを短縮し、マイクロ・プロセッサの処理能力の向上が図られている。
【０００３】
一般に、キャッシュメモリは、プロセッサによるデータの書き込み方式の違いにより、ライトスルー型とライトバック型に大別される。ライトスルー型のキャッシュメモリを持つプロセッサでは、プロセッサによるデータの書き込みは、キャッシュメモリ内へのデータの書き込みと主記憶メモリへのデータの書き込みが同時に行われる。これに対して、ライトバック型のキャッシュメモリを持つプロセッサでは、プロセッサによるデータ書き込みは、キャッシュメモリ内へのデータの書き込みだけで完了し、キャッシュメモリと主記憶メモリとの間で、データが不一致であることを示すダーティビットを有効（ダーティ）にする。そのデータは後の然るべきタイミングにより主記憶メモリへ書き込まれ、キャッシュメモリと主記憶メモリとの間でデータ一致がとれることで、ダーティビットは無効（クリーン）の状態となる。
【０００４】
上述のライトバック型のキャッシュメモリの特徴として、プロセッサがキャッシュに対する書き込み命令を実行した場合は、新しいデータをキャッシュブロックに格納する必要があるが、このとき、当該新しいデータを格納するべきキャッシュブロック上に主記憶メモリにおいて別ブロックに対応する更新されたデータが既に入っている場合、そのキャッシュブロック上のデータを主記憶メモリに書き戻し、その後に新しいデータを主記憶ブロックの別ブロックから格納する必要性が生じる。これをリプレースメントと呼ぶ。ここでは特に、説明を分かり易くするために、「メインメモリブロックリプレースメント」と呼ぶ。メインメモリブロックリプレースメントが発生した際に、主記憶メモリとの間で行われるキャッシュブロックのメインメモリブロックリプレース方法としては、リプレース対象となる複数のウェイを有するキャッシュブロックのうち最も古くに使用されたキャッシュブロックをリプレース対象として選択するＬＲＵ（Least Recently Used）方式や、最初にデータが格納されたキャッシュブロックを更新対象とするＦＩＦＯ（First In First Out）方式等がある。ＦＩＦＯは、プログラムの処理は逐次的に進められるという推測に基づいて、最も古くに読み込んだキャッシュブロックを置き換える。一方ＬＲＵは、長い時間参照されていないキャッシュブロックは、近い将来にも参照される可能性が低いという推測に基づいて、最後に参照されてから最も長い時間が経過したキャッシュブロックを置き換える。メインメモリブロックリプレースメントした後に、キャッシュミスを低減し、主記憶メモリへのアクセスを回避するために、上述したアルゴリズムが多くのプロセッサで採用されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平０４−２７３５４９号公報
【特許文献２】特開平０９−０６９０６５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
特許文献１乃至２に開示されるような通常のライトバック型ダイレクトマップ形式のキャッシュメモリ構成には、以下のような問題点があった。即ち、参照頻度の高いアドレスに対応するキャッシュラインへのアクセスと参照頻度の低いアドレスに対応するキャッシュラインへのアクセスとが混在するキャッシュ書き込み命令実行時には、その特定のキャッシュライン選択方式に基づいて、特定のキャッシュラインに対してのみ頻繁にアクセスが行われてしまい、限られたキャッシュスペースを有効に活用することができず、競合性のキャッシュミスが発生する回数が増加する場合がある。このようなキャッシュミス時には、大きなレイテンシを必要とする主記憶メモリに対するアクセスが発生し、競合性のキャッシュミスの発生回数の増加に伴い、システム全体のスループットが著しく低下するという問題点があった。また、ウェイを増やすことで、前述した競合性のキャッシュミスを減らす試みは取られているが、ウェイの数だけ同一アドレスのキャッシュブロックを有するキャッシュメモリを増やすことにより、アクセス時間や不要なコストの増大に繋がるという問題点があった。また、キャッシュメモリと主記憶メモリとの間に、複数個のキャッシュメモリに準じたバッファを用意して、キャッシュメモリから追い出されたデータを当該バッファに格納することで、使用頻度の高いデータを蓄積する試みは取られているが、バッファの数だけコストの増大に繋がるという問題点があった。
【０００７】
本発明は、キャッシュミスに伴って主記憶メモリにアクセスする回数を低減し、メモリシステムのスループットを向上させるキャッシュメモリ、キャッシュメモリにおけるアクセス方法、及びキャッシュメモリアクセス用プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の第１の観点によれば、キャッシュメモリであって、記憶手段と、第１のデータアドレスに含まれる第１のインデックスに対応し、前記記憶手段に含まれる第１のキャッシュラインにおいてキャッシュミスが発生する際、当該キャッシュ内リプレースのリプレース先に今まではなっておらず、ダーティビットがクリーンであり、前記記憶手段に含まれる第２のキャッシュラインにおいてキャッシュストアを実行することによりキャッシュ内リプレースを実施する制御手段と、を備えることを特徴とするキャッシュメモリが提供される。
【０００９】
本発明の第２の観点によれば、キャッシュメモリにおけるアクセス方法であって、制御手段が、第１のデータアドレスに含まれる第１のインデックスに対応し、記憶手段に含まれる第１のキャッシュラインにおいてキャッシュミスが発生する際、当該キャッシュ内リプレースのリプレース先に今まではなっておらず、ダーティビットがクリーンであり、前記記憶手段に含まれる第２のキャッシュラインにおいてキャッシュストアを実行することによりキャッシュ内リプレースを実施するステップを有することを特徴とするアクセス方法が提供される。
【００１０】
本発明の第３の観点によれば、キャッシュメモリにおけるアクセス方法をコンピュータに実行させるためのキャッシュメモリアクセス用プログラムであって、前記アクセス方法は、制御手段が、第１のデータアドレスに含まれる第１のインデックスに対応し、記憶手段に含まれる第１のキャッシュラインにおいてキャッシュミスが発生する際、当該キャッシュ内リプレースのリプレース先に今まではなっておらず、ダーティビットがクリーンであり、前記記憶手段に含まれる第２のキャッシュラインにおいてキャッシュストアを実行することによりキャッシュ内リプレースを実施するステップを有することを特徴とするキャッシュメモリアクセス用プログラムが提供される。
【発明の効果】
【００１１】
本発明によれば、キャッシュミス発生時の主記憶メモリへのアクセス回数を低減するという効果を奏することが出来る。
【図面の簡単な説明】
【００１２】
【図１】本発明の実施形態による中央演算装置の構成例である。
【図２】本発明の実施形態によるキャッシュメモリの構成例である。
【図３Ａ】本発明の実施形態によるキャッシュメモリにおけるキャッシュストア方法のフローチャートを示す図である。
【図３Ｂ】本発明の実施形態によるキャッシュメモリにおけるキャッシュストア方法のフローチャートを示す図である。
【図３Ｃ】本発明の実施形態によるキャッシュメモリにおけるキャッシュストア方法のフローチャートを示す図である。
【図３Ｄ】本発明の実施形態によるキャッシュメモリにおけるキャッシュストア方法のフローチャートを示す図である。
【図４Ａ】本発明の実施形態によるキャッシュメモリにおけるキャッシュロード方法のフローチャートを示す図である。
【図４Ｂ】本発明の実施形態によるキャッシュメモリにおけるキャッシュロード方法のフローチャートを示す図である。
【図４Ｃ】本発明の実施形態によるキャッシュメモリにおけるキャッシュロード方法のフローチャートを示す図である。
【図４Ｄ】本発明の実施形態によるキャッシュメモリにおけるキャッシュロード方法のフローチャートを示す図である。
【図５Ａ】本発明の実施形態によるキャッシュメモリにおけるキャッシュ内データ処理の具体例を示したもので、第一のキャッシュストアアクセスが実行された際のキャッシュメモリの状態を示したものである。
【図５Ｂ】本発明の実施形態によるキャッシュメモリにおけるキャッシュ内データ処理の具体例を示したもので、第二のキャッシュストアアクセスが実行された際のキャッシュメモリの状態を示したものである。
【図５Ｃ】本発明の実施形態によるキャッシュメモリにおけるキャッシュ内データ処理の具体例を示したもので、第三のキャッシュストアアクセスが実行された際のキャッシュメモリの状態を示したものである。
【図５Ｄ】本発明の実施形態によるキャッシュメモリにおけるキャッシュ内データ処理の具体例を示したもので、第四のキャッシュストアアクセスが実行された際のキャッシュメモリの状態を示したものである。
【図５Ｅ】本発明の実施形態によるキャッシュメモリにおけるキャッシュ内データ処理の具体例を示したもので、第五のキャッシュストアアクセスが実行された際のキャッシュメモリの状態を示したものである。
【図５Ｆ】本発明の実施形態によるキャッシュメモリにおけるキャッシュ内データ処理の具体例を示したもので、第六のキャッシュストアアクセスが実行された際のキャッシュメモリの状態を示したものである。
【図５Ｇ】本発明の実施形態によるキャッシュメモリにおけるキャッシュ内データ処理の具体例を示したもので、第七のキャッシュストアアクセスが実行された際のキャッシュメモリの状態を示したものである。
【図５Ｈ】本発明の実施形態によるキャッシュメモリにおけるキャッシュ内データ処理の具体例を示したもので、第八のキャッシュストアアクセスが実行された際のキャッシュメモリの状態を示したものである。
【図６Ａ】本発明の実施形態によるキャッシュメモリにおけるキャッシュ内データ処理の具体例を示したもので、第一のキャッシュロードアクセスが実行された際のキャッシュメモリの状態を示したものである。
【図６Ｂ】本発明の実施形態によるキャッシュメモリにおけるキャッシュ内データ処理の具体例を示したもので、第二のキャッシュロードアクセスが実行された際のキャッシュメモリの状態を示したものである。
【図６Ｃ】本発明の実施形態によるキャッシュメモリにおけるキャッシュ内データ処理の具体例を示したもので、第三のキャッシュロードアクセスが実行された際のキャッシュメモリの状態を示したものである。
【図６Ｄ】本発明の実施形態によるキャッシュメモリにおけるキャッシュ内データ処理の具体例を示したもので、第四のキャッシュロードアクセスが実行された際のキャッシュメモリの状態を示したものである。
【図６Ｅ】本発明の実施形態によるキャッシュメモリにおけるキャッシュ内データ処理の具体例を示したもので、第五のキャッシュロードアクセスが実行された際のキャッシュメモリの状態を示したものである。
【発明を実施するための形態】
【００１３】
以下、図面を参照して本発明を実施するための形態について詳細に説明する。
【００１４】
図１は、本発明の実施形態による中央演算装置の構成例を示すブロック図である。図１を参照すると、当該中央演算装置は、ロード命令及びストア命令の実行機能を備えたプロセッサコア１０１と、ダイレクトマップ方式、もしくは、Ｎウェイセットアソシアティブ方式のキャッシュメモリ１０２とを備えている。キャッシュメモリ１０２はプロセッサコア１０１とプロセッサバス１０３との間に配置されており、これによってメインメモリアクセスが高速化されている。また、プロセッサコア１０１とメインメモリ１０６とは、プロセッサバス１０３とメモリコントローラ１０５を介して接続されており、これらの間でのデータの授受が可能になっている。またプロセッサバス１０３とローカルバス１０７とはブリッジ１０４を介して接続されている。ローカルバスには、ＳＣＳＩコントローラ１０８を介してハードディスク１０９等の入出力機器が接続されている。
【００１５】
図２は、本発明の実施形態によるキャッシュメモリの構成例である。当該キャッシュメモリは、従来のダイレクトマップ方式のキャッシュメモリに、本発明による変更を加えた２Ｋバイトのキャッシュメモリの概念図を示したものである。当該キャッシュメモリの記憶部２２１は、複数のキャッシュライン、例えば１２８ライン分のキャッシュラインを有する。各キャッシュラインは、キャッシュ内リプレースが行われたことを示すキャッシュ内リプレース（ＣＲ）ビット２２３と、キャッシュメモリと対応する主記憶メモリのデータとが一致しているか否かを示すダーティビット２２５と、キャッシュラインが有効／無効であるかを示すＶａｌｉｄフラグ２２７と、アドレスの上位ビットを示すタグ部２２９と、キャッシュラインのインデックスを示すインデックス部２３１と、データ部２３３とを有する（「キャッシュ内リプレース」の詳細については後述する）。
【００１６】
ここで、キャッシュ内リプレース（ＣＲ）ビットの初期値は０であり、当該ＣＲビットを含むキャッシュライン以外のキャッシュラインを、主記憶メモリにリプレースするのではなく、キャッシュ内でリプレースした際、当該ＣＲビットを含むキャッシュライン自身が当該キャッシュ内リプレース先のキャッシュラインである場合に１となる。また、ダーティビットの初期値は０（クリーン）であり、当該ダーティビットを含むキャッシュラインのデータと、当該ダーティビットを含むキャッシュラインに対応する主記憶メモリのデータとが不一致の際は１（ダーティ）となる。また、Ｖａｌｉｄフラグの初期値は１（Ｖａｌｉｄ）であり、ＣＰＵが明示的に０（Ｉｎｖａｌｉｄ）としない限り、１の値を保つ。また、各キャッシュラインの下位４ビット（下位より０〜３ビット）がデータ部に対応する。キャッシュラインは１２８ライン分存在するため、その上位７ビット（下位より４〜１０ビット）であるインデックス部２３１がキャッシュラインのインデックスを表すことになる。そして、更に上位２１ビット（下位より１１〜３１ビット）がタグ部２２９となる。
【００１７】
データアドレス２０１が入力されると、インデックス変換部２１１がインデックス２０５を抜き出し、当該インデックス２０５を変換後インデックスに変換し、当該変換後インデックスを用いて、記憶部２２１内のキャッシュラインを特定する。次に、データアドレス２０１の上位複数ビットであるタグ２０３と、特定されたキャッシュラインのタグ部２２９の値とを比較器２１０−１乃至２０１−ｎで比較する。比較した結果が一致すればキャッシュヒット、不一致であればキャッシュミスとなる。キャッシュヒット時には、上記の特定されたキャッシュラインのデータ部２３３中、データアドレス２０１内のオフセット２０７で指定されたデータブロックに、制御部２１２がデータを書き込む。キャッシュミス時には、所定の条件下では上記の特定されたキャッシュライン以外のキャッシュラインのデータ部２３３中、他の条件下では上記の特定されたキャッシュラインのデータ部２３３中、データアドレス２０１内のオフセット２０７で指定されたデータブロックに、制御部２１２がデータを書き込む。
【００１８】
図３Ａ乃至図３Ｄは、本実施形態によるキャッシュメモリにおけるキャッシュストア方法を説明するためのフローチャートである。
【００１９】
図３Ａ乃至図３Ｄを参照すると、まず、図３Ａにおいて、キャッシュストア命令をＣＰＵから入力することにより、キャッシュストア命令の実行を開始する（ステップＳ３０１）。
【００２０】
次に、キャッシュストア命令に含まれているデータアドレス（ストア先アドレス）２０１を読み込む（ステップＳ３０３）。
【００２１】
次に、データアドレス（ストア先アドレス）２０１に含まれているインデックスｉを得る（ステップＳ３０５）。
【００２２】
次に、制御部２１２が、インデックスｉをインデックス変換部２１１に与える（ステップＳ３０７）。ここでは、インデックス変換部が、入力したインデックスと異なるインデックスを出力する場合と、同値のインデックスを出力する場合とが存在する。入力したインデックスを異なるインデックスに変換するためにインデックス変換部２１１に記憶される情報については、以下のステップＳ３３３で後述する。
【００２３】
次に、インデックス変換部２１１による異なるインデックスへの変換があるか否か、制御部２１２が判定する（ステップＳ３０９）。異なるインデックスへの変換が存在しない、すなわち、ステップＳ３０７においてインデックスｉをインデックス変換部２１１に与えた結果、インデックス変換部２１１が同値のインデックスｉを出力した場合（ステップＳ３０９のＮＯ）は、Ａを経由して、図３ＢのステップＳ３１１に移行し、ストア先第１候補として、制御部２１２が、インデックスがｉのキャッシュラインｉを得る。
【００２４】
次に、キャッシュラインｉのキャッシュ内リプレース（ＣＲ）ビット（ＣＲ（ｉ））が１か否か、すなわち、キャッシュラインｉとは異なるキャッシュラインを以前にキャッシュ内リプレースした際、キャッシュラインｉが当該キャッシュ内リプレースにおけるリプレース先のキャッシュラインであったか否かを、制御部２１２が判定する（ステップＳ３１３）。ＣＲ（ｉ）＝０、すなわち、ＣＲ（ｉ）＝１ではない場合（ステップＳ３１３のＮＯ）、ストア先第１候補のキャッシュラインｉのタグ部２２９と、データアドレス（ストア先アドレス）２０１に含まれるタグ２０３とを、比較器２１０で比較し、一致した場合はキャッシュヒット、一致しなかった場合はキャッシュミスと判定する（ステップＳ３１５）。ただし、初期状態時、すなわち、ストア先第１候補のキャッシュラインｉのＶａｌｉｄフラグ（Ｖ（ｉ））が１で、ダーティビット（Ｄ（ｉ））が０（クリーン）の場合は、キャッシュラインｉのタグ部２２９の値とデータアドレス（ストア先アドレス）２０１に含まれるタグ２０３との双方の値が一致しなくても、キャッシュヒットと判定する。
【００２５】
ステップＳ３１５でキャッシュヒットと判定された場合（ステップＳ３１５のＹＥＳ）は、制御部２１２がストア先第１候補のキャッシュラインｉのデータ部２３３にキャッシュストアの対象データを書き込む（ステップＳ３１７）。なお、ステップＳ３１５でキャッシュヒットと判定した際、ストア先第１候補のキャッシュラインｉのタグ部２２９と、データアドレス（ストア先アドレス）２０１に含まれるタグ２０３とが一致しなかったものの、Ｖ（ｉ）＝１で、Ｄ（ｉ）＝０であるためにキャッシュヒットと判定された場合は、データ部２３３へのキャッシュストアの対象データの書き込みに加えて、タグ部２２９にタグ２０３を書き込む。
【００２６】
次に、当該書き込まれたキャッシュストアの対象データと、キャッシュラインｉに対応する外部メモリ（主記憶メモリ）のデータとが同一ではないことから、制御部２１２がキャッシュラインｉのダーティビット（Ｄ（ｉ））を１（ダーティ）に設定し（ステップＳ３１９）、フローを終了する（ステップＳ３２１）。
【００２７】
上記ステップＳ３１５において、キャッシュミスと判定された場合（ステップＳ３１５のＮＯ）は、Ｂを経由して図３ＣのステップＳ３２３に移行し、制御部２１２がストア先第１候補のキャッシュラインｉ以外のキャッシュラインｋ（≠ｉ）を探す。具体的には、制御部２１２は、ＣＲ（ｋ）＝０、且つ、Ｄ（ｋ）＝０、且つ、Ｖ（ｋ）＝１となるキャッシュラインを検索する。
【００２８】
当該キャッシュラインが存在する場合（ステップＳ３２５でＹＥＳ）は、制御部２１２は、上記条件に該当するキャッシュラインのうち、インデックスが最も若番のキャッシュラインをストア先第２候補のキャッシュラインｋとする。その後、制御部２１２は、キャッシュラインｋのデータ部２３３にキャッシュストアの対象データを書き込む。詳細には、ストア先第１候補のキャッシュラインｉに対応する外部メモリ（主記憶メモリ）内のデータを、キャッシュラインｋのデータ部２３３に書き戻し、その後、キャッシュラインｋのデータ部２３３のうち、データアドレス（ストア先アドレス）２０１に含まれるオフセット２０７で指定されるデータブロック内に、キャッシュストアの対象データを格納する。更に、タグ部２２９にデータアドレス（ストア先アドレス）２０１に含まれるタグ２０３を書き込む（ステップＳ３２７）。
【００２９】
次に、当該書き込まれたキャッシュストアの対象データと、キャッシュラインｋに対応する外部メモリ（主記憶メモリ）のデータとが同一ではないことから、制御部２１２がキャッシュラインｋのダーティビットＤ（ｋ）を１（ダーティ）に設定する（ステップＳ３２９）。
【００３０】
次に、キャッシュラインｋが、キャッシュ内リプレースにおけるリプレース先のキャッシュラインとなったことから、制御部２１２がＣＲ（ｋ）の値を１に設定する（ステップＳ３３１）。
【００３１】
次に、当初はストア先第１候補がキャッシュラインｉであったが、実際にデータをストアしたキャッシュラインがキャッシュラインｋとなったため、この“ｉｎｄｅｘ  ｉ→ｉｎｄｅｘ  ｋ”（ｉ≠ｋ）の変換を、インデックス変換部２１１が記憶し（ステップＳ３３３）、フローを終了する（ステップＳ３３５）。
【００３２】
このステップＳ３３５に至るフローに関しては、従来のキャッシュメモリでは、データアドレス（ストア先アドレス）に含まれるタグと、データアドレス（ストア先アドレス）に含まれるインデックスに対応するキャッシュライン内のタグ部の値との不一致によるキャッシュミスが発生した場合、当該キャッシュラインのデータを外部メモリ（主記憶メモリ）に書き戻す処理（メインメモリブロックリプレース処理）が発生し、多大なディレイを要していた。また、従来のキャッシュメモリでは、リプレースの後にインデックスが指し示すキャッシュライン内の、オフセットが指し示すキャッシュブロックにデータを書き込んでいた。本発明の実施形態によるキャッシュメモリにおいては、このような場合に、上記のようにメインメモリブロックリプレースを行わず、空いているキャッシュラインにデータを格納する（キャッシュ内リプレース処理）。これにより、限られたキャッシュスペースを有効に活用し、外部メモリ（主記憶メモリ）とのアクセスを低減し、ディレイを少なくすることが可能となる。このような制御を可能とするために、各キャッシュラインには上記のキャッシュ内リプレース（ＣＲ）ビットが用意される。更に、本発明の実施形態によるキャッシュメモリは、データアドレス（ストア先アドレス）に含まれるインデックスが指し示すキャッシュラインが、どのインデックスのキャッシュラインに変換されたかを記憶する上記のインデックス変換部を備える。
【００３３】
図３Ｃに戻ると、上記ステップＳ３２５でＮＯ，すなわち、ＣＲ（ｋ）＝０、且つ、Ｄ（ｋ）＝０、且つ、Ｖ（ｋ）＝１のキャッシュラインｋが存在しなかった場合は、制御部２１２がストア先第１候補のキャッシュラインｉをメインメモリブロックリプレースする（ステップＳ３３７）。具体的には、制御部２１２がキャッシュラインｉのデータ部２３３に含まれるデータを外部メモリ（主記憶メモリ）に書き戻す。
【００３４】
次に、制御部２１２が、ストア先第１候補のキャッシュラインｉのデータ部２３３にキャッシュストアの対象データを書き込み、タグ部２２９にデータアドレス（ストア先アドレス）２０１に含まれるタグ２０３を書き込む（ステップＳ３３９）。
【００３５】
次に、当該書き込まれたデータと、キャッシュラインｉに対応する外部メモリ（主記憶メモリ）のデータとが同一ではないことから、制御部２１２がキャッシュラインｉのダーティビットＤ（ｉ）を１（ダーティ）に設定し（ステップＳ３４１）。フローを終了する（ステップＳ３４３）。
【００３６】
図３Ｂに戻ると、ステップＳ３１３でＹＥＳ、すなわち、ストア先第１候補のキャッシュラインｉのＣＲ（ｉ）が１である場合は、ステップＳ３４５に移行し、制御部２１２がストア先第１候補のキャッシュラインｉをメインメモリブロックリプレースする。具体的には、制御部２１２が、キャッシュラインｉのデータ部に含まれるデータを外部メモリ（主記憶メモリ）に書き戻す。
【００３７】
次に、制御部２１２が、ストア先第１候補のキャッシュラインｉのデータ部２３３にキャッシュストアの対象データを書き込み、タグ部２２９にデータアドレス（ストア先アドレス）２０１に含まれるタグ２０３を書き込む（ステップＳ３４７）。
【００３８】
次に、当該書き込まれたキャッシュストアの対象データと、キャッシュラインｉに対応する外部メモリ（主記憶メモリ）のデータとが同一ではないことから、制御部２１２がキャッシュラインｉのダーティビットＤ（ｉ）を１（ダーティ）に設定する（ステップＳ３４９）。
【００３９】
次に、上記ステップＳ３４７において、キャッシュラインｉ内のデータ部２３３に新たにキャッシュストアの対象データが書き込まれたことにより、キャッシュラインｉはキャッシュ内リプレースのリプレース先ではなくなったことから、制御部２１２がＣＲ（ｉ）を０に設定する。
【００４０】
次に、キャッシュラインｉが以前キャッシュ内リプレースのリプレース先となっていた際、当該キャッシュラインｉと依存関係にあったキャッシュラインｌ（ｌ≠ｉ）のＣＲ（ｌ）を０にリセットする（ステップＳ３５３）。
【００４１】
次に、上記のように、キャッシュラインｉがキャッシュ内リプレースのリプレース先ではなくなったことから、インデックス変換部２１１に記憶された“ｉｎｄｅｘ  ｌ→ｉｎｄｅｘ  ｉ”（ｌ≠ｉ）の情報を消去し（ステップＳ３５５）、フローを終了する（ステップＳ３５７）。当該情報の消去に伴い、インデックス変換部２１１にインデックスｌを入力しても、異なるインデックスｉに変換されるのではなく、同一のインデックスｌが出力されるが、これは、上記情報の消去に伴い、インデックス変換部２１１が、新たな変換情報である“ｉｎｄｅｘ  ｌ→ｉｎｄｅｘ  ｌ”を生成し把持することによるものとしても良い。又は、インデックス変換部２１１が、インデックスｌを入力とする変換情報は何ら把持せず、変換制御をしないことによるものとしても良い。インデックス変換情報の消去に関しては、以下で述べるステップにおいても同様である。
【００４２】
図３Ａに戻ると、ステップＳ３０９においてＹＥＳ、すなわち、インデックスｉから異なるインデックスｋ（ｋ≠ｉ）への変換がある場合、ステップＳ３５９において、インデックスをｉ→ｋと変換した後の、ストア先第１候補のキャッシュラインｋ（ｋ≠ｉ）を、制御部２１２が得る。
【００４３】
次に、インデックス変換後のストア先第１候補のキャッシュラインｋのタグ部２２９と、データアドレス（ストア先アドレス）２０１に含まれるタグ２０３とを、比較器２１０で比較し、一致した場合はキャッシュヒット、一致しなかった場合はキャッシュミスと判定する（ステップＳ３６１）。
【００４４】
ステップＳ３６１でＹＥＳ，すなわちキャッシュヒットと判定された場合は、制御部２１２がインデックス変換後のストア先第１候補のキャッシュラインｋのデータ部２３３にデータを書き込む（ステップＳ３６３）。
【００４５】
次に、当該書き込まれたデータと、キャッシュラインｋに対応する外部メモリ（主記憶メモリ）のデータとが同一ではないことから、制御部２１２がキャッシュラインｋのダーティビット（Ｄ（ｋ））を１（ダーティ）とし（ステップＳ３６５）、フローを終了する（ステップＳ３６７）。
【００４６】
ステップＳ３６１でＮＯ、すなわちキャッシュミスと判定された場合は、Ｃを経由して図３ＤのステップＳ３６９に移行する。ここでは、インデックス変換前、すなわちインデックスがｉのキャッシュラインｉをストア先第２候補とし、このキャッシュラインｉのタグ部２２９と、データアドレス（ストア先アドレス）２０１に含まれるタグ２０３とを、比較器２１０で比較し、一致した場合はキャッシュヒット、一致しなかった場合はキャッシュミスと判定する。
【００４７】
ステップＳ３６９でＹＥＳ、すなわちキャッシュヒットと判定された場合は、制御部２１２がストア先第２候補のキャッシュラインｉのデータ部２３３にキャッシュストアの対象データを書き込む（ステップＳ３７１）。
【００４８】
次に、当該書き込まれたキャッシュストアの対象データと、キャッシュラインｉに対応する外部メモリ（主記憶メモリ）のデータとが同一ではないことから、制御部２１２がキャッシュラインｉのダーティビット（Ｄ（ｉ））を１（ダーティ）に設定し（ステップＳ３７３）、フローを終了する（ステップＳ３７５）。
【００４９】
ステップＳ３６９でＮＯ、すなわちキャッシュミスと判定された場合は、制御部２１２がインデックス変換後のストア先第１候補であるキャッシュラインｋをメインメモリブロックリプレースする（ステップＳ３７７）。具体的には、制御部２１２が、キャッシュラインｋのデータ部２３３に含まれるデータを外部メモリ（主記憶メモリ）に書き戻す。
【００５０】
次に、制御部２１２が、ストア先第１候補であるキャッシュラインｋのデータ部２３３にキャッシュストアの対象データを書き込み、タグ部２２９にデータアドレス（ストア先アドレス）２０１に含まれるタグ２０３を書き込む（ステップＳ３７９）。
【００５１】
次に、当該書き込まれたキャッシュストアの対象データと、キャッシュラインｋに対応する外部メモリ（主記憶メモリ）のデータとが同一ではないことから、制御部２１２がキャッシュラインｋのダーティビットＤ（ｋ）を１（ダーティ）に設定する（ステップＳ３８１）。
【００５２】
次に、上記ステップＳ３７９において、キャッシュラインｋ内のデータ部２３３に新たにキャッシュストアの対象データが書き込まれたことにより、キャッシュラインｋはキャッシュ内リプレースのリプレース先ではなくなったことから、制御部２１２が、ＣＲ（ｋ）を０に設定する（ステップＳ３８３）。
【００５３】
次に、上記のように、キャッシュラインｋがキャッシュ内リプレースのリプレース先ではなくなったことから、制御部２１２が、インデックス変換部に記憶された“ｉｎｄｅｘ  ｉ→ｉｎｄｅｘ  ｋ”（ｉ≠ｋ）の情報を消去し（ステップＳ３８５）、フローを終了する（ステップＳ３８７）。
【００５４】
なお、上記の図３Ａ乃至図３Ｄに記載のフローの説明においては、簡略化のため、ストア先候補を第２候補までとした場合のフローについて説明したが、本発明の実施形態はこれには限定されず、ストア先候補として、第３候補、第４候補・・・を設定することも可能である。具体的には、図３Ｃに記載のステップＳ３２５からステップＳ３３３のステップが実施されることにより、“ｉｎｄｅｘ  ｉ→ｉｎｄｅｘ  ｋ”（ｉ≠ｋ）の変換制御情報が、インデックス変換部２１１に記憶された後、更に異なるキャッシュラインについて、ステップＳ３２５からステップＳ３３３のステップを実施することにより、“ｉｎｄｅｘ  ｉ→ｉｎｄｅｘ  ｍ”（ｉ≠ｍ）の変換制御情報が、インデックス変換部２１１に記憶されることをもって、ストア先第３候補のキャッシュラインを設定することが可能であり、以下同様である。
【００５５】
図４Ａ乃至図４Ｄは、本実施形態によるキャッシュメモリにおけるキャッシュロード方法を説明するためのフローチャートである。
【００５６】
図４Ａ乃至図４Ｄを参照すると、まず、図４Ａにおいて、キャッシュロード命令をＣＰＵから入力することにより、キャッシュロード命令の実行を開始する（ステップＳ４０１）。
【００５７】
次に、キャッシュロード命令に含まれているデータアドレス（ロード先アドレス）２０１を読み込む（ステップＳ４０３）。
【００５８】
次に、データアドレス（ロード先アドレス）２０１に含まれているインデックスｉを得る（ステップＳ４０５）。
【００５９】
次に、インデックスｉをインデックス変換部２１１に与える（ステップＳ４０７）。ここでは、インデックス変換部が、入力したインデックスと異なるインデックスを出力する場合と、同値のインデックスを出力する場合とが存在する。
【００６０】
次に、インデックス変換部２１１による異なるインデックスへの変換があるか否か、制御部２１２が判定する（ステップＳ４０９）。異なるインデックスへの変換が存在しない、すなわち、ステップＳ４０９においてインデックスｉをインデックス変換部２１１に与えた結果、インデックス変換部２１１が同値のインデックスｉを出力した場合（ステップＳ４０９のＮＯ）は、Ａを経由して、図４ＢのステップＳ４１１に移行し、ロード先の第１候補として、インデックスがｉのキャッシュラインｉを得る。
【００６１】
次に、キャッシュラインｉのキャッシュ内リプレース（ＣＲ）ビット（ＣＲ（ｉ））が１か否か、すなわち、キャッシュラインｉとは異なるキャッシュラインを以前にキャッシュ内リプレースした際、キャッシュラインｉが当該キャッシュ内リプレースにおけるリプレース先のキャッシュラインであったか否かを、制御部２１２が判定する（ステップＳ４１３）。ＣＲ（ｉ）＝０、すなわち、ＣＲ（ｉ）＝１ではない場合（ステップＳ４１３のＮＯ）、ロード先第１候補のキャッシュラインｉのタグ部２２９と、データアドレス（ロード先アドレス）２０１に含まれるタグ２０３とを、比較器２１０で比較し、一致した場合はキャッシュヒット、一致しなかった場合はキャッシュミスと判定する（ステップＳ４１５）。
【００６２】
ステップＳ４１５でＹＥＳ、すなわちキャッシュヒットと判定された場合は、制御部２１２がロード先第１候補のキャッシュラインｉのデータ部２３３からキャッシュロードの対象データを読み出し（ステップＳ４１７）、フローを終了する（ステップＳ４１９）。
【００６３】
なお、上記のステップＳ４１９に至るまでのフローは、異なるインデックスへの変換の有無、及びＣＲ（ｉ）の値の判定を除けば、一般的なキャッシュヒット時のロード動作と同一である。
【００６４】
ステップＳ４１５でＮＯ、すなわちキャッシュミスと判定された場合は、Ｂを経由して図４ＣのステップＳ４２１に移行し、ロード先第１候補のキャッシュラインｉをメインメモリブロックリプレースする（ステップＳ４２１）。具体的には、ロード先第１候補のキャッシュラインｉに対応する外部メモリ（主記憶メモリ）のデータを、キャッシュラインｉのデータ部２３３に書き込む。更に、キャッシュラインｉのタグ部に、データアドレス（ロード先アドレス）２０１に含まれるタグ２０３を書き込む。
【００６５】
次に、制御部２１２がロード先第１候補のキャッシュラインｉのデータ部２３３からキャッシュロードの対象データを読み出す（ステップＳ４２３）。
【００６６】
次に、上記ステップＳ４２１により、ロード先第１候補のキャッシュラインｉのデータ部２３３内のデータと、キャッシュラインｉに対応する外部メモリ（主記憶メモリ）のデータとが同一となったことから、制御部２１２がキャッシュラインｉのダーティビット（Ｄ（ｉ））を０（クリーン）に設定し（ステップＳ４２５）、フローを終了する（ステップＳ４２７）。
【００６７】
なお、上記のステップＳ４２７に至るまでのフローは、異なるインデックスへの変換の有無、及びＣＲ（ｉ）の値の判定を除けば、一般的なキャッシュミス時のロード動作と同一である。
【００６８】
図４Ｂに戻ると、ステップＳ４１３でＹＥＳ、すなわちロード先第１候補のキャッシュラインｉのＣＲ（ｉ）が１である場合は、ステップＳ４２９に移行し、制御部２１２がロード先第１候補のキャッシュラインｉをメインメモリブロックリプレースする。具体的には、制御部２１２が、キャッシュラインｉに対応する外部メモリ（主記憶メモリ）のデータを、キャッシュラインｉのデータ部２３３に書き込む。更に、キャッシュラインｉのタグ部２２９に、データアドレス（ロード先アドレス）に含まれるタグ２０３を書き込む。
【００６９】
次に、制御部２１２が、ロード先第１候補のキャッシュラインｉのデータ部２３３からキャッシュロードの対象データを読み出す（ステップＳ４３１）。
【００７０】
次に、上記ステップＳ４２９により、ロード先第１候補のキャッシュラインｉが、キャッシュ内リプレースのリプレース先ではなくなったため、制御部２１２が、ロード先第１候補のキャッシュラインｉのＣＲ（ｉ）を０に設定する（ステップＳ４３３）。
【００７１】
次に、上記ステップＳ４２９により、ロード先第１候補のキャッシュラインｉのデータ部２３３内のデータと、キャッシュラインｉに対応する外部メモリ（主記憶メモリ）のデータとが同一となったことから、制御部２１２がキャッシュラインｉのダーティビット（Ｄ（ｉ））を０（クリーン）に設定する（ステップＳ４３５）。
【００７２】
次に、上記のように、キャッシュラインｉがキャッシュ内リプレースのリプレース先ではなくなったことから、制御部２１２が、インデックス変換部２１１に記憶された“ｉｎｄｅｘ  ｌ→ｉｎｄｅｘ  ｉ”（ｌ≠ｉ）の情報を消去し（ステップＳ４３７）、フローを終了する（ステップＳ４３９）。
【００７３】
図４Ａに戻ると、ステップＳ４０９でＹＥＳ、すなわち、インデックスｉから異なるインデックスｋ（ｋ≠ｉ）への変換がある場合、ステップＳ４４１において、インデックスをｉ→ｋと変換した後の、ロード先第１候補のキャッシュラインｋを、制御部２１２が得る。
【００７４】
次に、インデックス変換後のロード先第１候補のキャッシュラインｋのタグ部２２９と、データアドレス（ロード先アドレス）２０１に含まれるタグ２０３とを、比較器２０１で比較し、一致した場合はキャッシュヒット、一致しなかった場合はキャッシュミスと判定する（ステップＳ４４３）。
【００７５】
ステップＳ４４３でＹＥＳ、すなわちキャッシュヒットと判定された場合は、制御部２１２がインデックス変換後のロード先第１候補のキャッシュラインｋのデータ部２３３からデータを読み出し（ステップＳ４４５）、フローを終了する（ステップＳ４４７）。
【００７６】
ステップＳ４４３でＮＯ、すなわちキャッシュミスと判定された場合は、Ｃを経由して図４ＤのステップＳ４４９に移行する。ここでは、インデックス変換前、すなわちインデックスがｉのキャッシュラインをロード先第２候補とする。その上で、このキャッシュラインｉのタグ部２２９と、データアドレス（ロード先アドレス）２０１に含まれるタグ２０３とを、比較器２１０で比較し、一致した場合はキャッシュヒット、一致しなかった場合はキャッシュミスと判定する。
【００７７】
ステップＳ４４９でＹＥＳ、すなわちキャッシュヒットと判定された場合は、制御部２１２がロード先第２候補のキャッシュラインｉのデータ部２３３からキャッシュロードの対象データを読み出し（ステップＳ４５１）、フローを終了する（ステップＳ４５３）。
【００７８】
ステップＳ４４９でＮＯ、すなわちキャッシュミスと判定された場合は、制御部２１２がロード先第１候補であるキャッシュラインｋをメインメモリブロックリプレースする（ステップＳ４５５）。具体的には、制御部２１２が、キャッシュラインｋに対応する外部メモリ（主記憶メモリ）のデータを、キャッシュラインｋのデータ部２３３に書き込む。
【００７９】
次に、ロード先第１候補であるキャッシュラインｋのデータ部２３３からキャッシュロードの対象データを読み出す（ステップＳ４５７）。
【００８０】
次に、上記ステップＳ４５５により、ロード先第１候補のキャッシュラインｋが、キャッシュ内リプレースのリプレース先ではなくなったため、制御部２１２が、ロード先第１候補のキャッシュラインｋのＣＲ（ｋ）を０に設定する。同時に、キャッシュラインｋが以前キャッシュ内リプレースのリプレース先となっていた際、当該キャッシュラインｋと依存関係にあったキャッシュラインｉのＣＲ（ｉ）も０に設定する（ステップＳ４５９）。
【００８１】
次に、上記ステップＳ４５５により、ロード先第１候補のキャッシュラインｋのデータ部２３３内のデータと、キャッシュラインｋに対応する外部メモリ（主記憶メモリ）のデータとが同一となったことから、制御部２１２がキャッシュラインｋのダーティビット（Ｄ（ｋ））を０（クリーン）に設定する（ステップＳ４６１）。
【００８２】
次に、上記のように、キャッシュラインｋがキャッシュ内リプレースのリプレース先ではなくなったことから、インデックス変換部に記憶された“ｉｎｄｅｘ  ｉ→ｉｎｄｅｘ  ｋ”（ｉ≠ｋ）の情報を消去し（ステップＳ４６３）、フローを終了する（ステップＳ４６５）。
【００８３】
なお、上記の図３Ａ乃至図３Ｄに記載のキャッシュストア時のフローの説明において、ストア先候補として、第３候補、第４候補・・・を設定することも可能である旨、述べたが、図４Ａ乃至図４Ｄに記載のキャッシュロード時のロード先候補に関しても、本発明の実施形態は、上記で説明したロード先候補を第２候補までしか設定しない態様には限定されない。具体的には、図４Ｄ記載のステップＳ４４９においてＮＯであった場合、更に、第３候補のキャッシュラインがヒットしたかどうか調べ、更にＮＯだった場合は、第４候補のキャッシュラインがヒットしたかどうか調べることを繰り返すことにより、ロード先第３候補、ロード先第４候補・・・を設定することも可能である。
【実施例】
【００８４】
図５Ａ乃至図５Ｈ、及び図６Ａ乃至図６Ｅは、本発明のキャッシュメモリにおける、キャッシュ内データの動作を具体的なアクセス例を提示して表したものである。より具体的には、図５Ａ乃至図５Ｈは、キャッシュストアアクセスが発生した場合のキャッシュメモリの状態の変遷を表し、図６Ａ乃至図６Ｅは、キャッシュロードアクセスが発生した場合のキャッシュメモリの状態の変遷を表す。
【００８５】
まず前提として、本実施例に用いるキャッシュメモリのアーキテクチャについて説明する。説明を分かり易くするため、データアドレス（ストア先アドレス、又はロード先アドレス）のビット数を８ｂｉｔ、キャッシュメモリに備わるキャッシュライン数を４ライン（ｉｎｄｅｘ０〜ｉｎｄｅｘ３）、各キャッシュラインに備わるキャッシュブロックの数を２（ＤＡＴＡ（０）〜ＤＡＴＡ（１））とし、各キャッシュブロックには、４ｂｉｔのデータが格納可能とする。また、アドレス８ｂｉｔの内、先頭から順に、タグ＝５ｂｉｔ、インデックス＝２ｂｉｔ、オフセット＝１ｂｉｔのキャッシュメモリを構成することとする。しかし、本発明の実施形態は、このようなキャッシュメモリのアーキテクチャに限定されるものではなく、任意のビット数、キャッシュライン数、キャッシュブロック数でアーキテクチャを構成することが可能である。
【００８６】
上記の図５Ａ乃至図５Ｈ、及び図６Ａ乃至図６Ｅの各図面には、上下２つのキャッシュメモリの概念図が示されるが、各図面内の上方に示された概念図は、キャッシュストア命令又はキャッシュロード命令によるアクセスを実施するよりも前のキャッシュメモリの状態を表す概念図であり、下方に示された概念図は、キャッシュストア命令又はキャッシュロード命令によるアクセスを実施した後のキャッシュメモリの状態を表す概念図である。下方の概念図において、白抜き文字で示されている欄は、キャッシュストア命令又はキャッシュロード命令によるアクセスを経て上方の概念図から変化した箇所である。
【００８７】
また、図５Ａ下方の概念図で示されるキャッシュメモリの状態と、図５Ｂ上方の概念図で示されるキャッシュメモリの状態とは同一である。図５Ｂ下方の概念図で示されるキャッシュメモリの状態と、図５Ｃ上方の概念図で示されるキャッシュメモリ状態とも同一であり、以下同様である。すなわち、図５Ａから、図５Ｈ、図６Ａを経て、図６Ｅに至るまで、各図面は、当該図面内に示されたキャッシュストア命令又はキャッシュロード命令によるアクセスを順次実行した場合の、キャッシュメモリの状態の変遷順に従って並んでいる。
【００８８】
まず図５Ａを参照すると、上方に示された概念図は、キャッシュメモリの初期状態を示す図である。ここで、図５Ａ中の矢印の右上方に示されるように、アドレス“８’ｂ００００＿１０１０”にデータ“０ｘＡ”をライトするキャッシュストア命令の実行を開始するものとする（ステップＳ３０１）。
【００８９】
まず、ステップＳ３０３において、データアドレス（ストア先アドレス）を読み込む。
【００９０】
次に、ステップＳ３０５において、読み込んだアドレス中の先頭から６〜７ｂｉｔ目が“０１”であることから、インデックスとしてｉｎｄｅｘ  １を得る。
【００９１】
次に、ステップＳ３０７において、制御部２１２が、ｉｎｄｅｘ  １をインデックス変換部に与える。しかし、初期状態において、インデックス変換部はｉｎｄｅｘ  １を入力とする変換制御情報は記憶していない（又は、“ｉｎｄｅｘ  １→ｉｎｄｅｘ  １”の変換制御情報を記憶している）ため、ｉｎｄｅｘ  １を異なるインデックスに変換することなく（ステップＳ３０９のＮＯ）、Ａを経由してステップＳ３１１に移行し、制御部２１２が、ストア先第１候補としてｉｎｄｅｘ  １のキャッシュライン１を得る。
【００９２】
次に、ステップＳ３１３において、キャッシュライン１のＣＲ（１）が０であることから、ステップＳ３１５に進み、キャッシュライン１がキャッシュヒットしたか否かを判定する。ここで、上記のように、初期状態時、すなわち、ストア先第１候補であるキャッシュライン１のＶａｌｉｄフラグ（Ｖ（１））が１で、ダーティビット（Ｄ（１））が０（クリーン）の場合は、キャッシュヒットと判定され（ステップＳ３１５のＹＥＳ）、ステップＳ３１７に移行する。
【００９３】
ステップＳ３１７において、ストア先第１候補であるキャッシュライン１にデータ“０ｘＡ”を書き込む。ここで、データアドレス（ストア先アドレス）に含まれるオフセット、すなわち、アドレスの先頭から８ｂｉｔ目が０であることから、オフセット０に対応するＤＡＴＡ（０）のデータブロックに、制御部２１２がデータ“０ｘＡ”を書き込む。なお、図５Ａに示すフロー中のステップＳ３１５では、キャッシュヒットと判定されたものの、データアドレス（ストア先アドレス）に含まれるタグ“００００１”と、キャッシュストア命令の実行前のキャッシュライン１のタグ部の値“０００００”とは一致していない。そのため、データ“０ｘＡ”の書き込みに加えて、キャッシュライン１のタグ部にデータアドレス（ストア先アドレス）２０１に含まれるタグ“００００１”を書き込む。
【００９４】
次に、ステップＳ３１９において、制御部２１２がストア先第１候補であるキャッシュライン１のＤ（１）を１に設定し、ステップＳ３２１においてフローを終了する。
【００９５】
その結果、キャッシュメモリは、図５Ａの下方の概念図に示す状態となる。
【００９６】
繰り返しになるが、図５Ａに示されるキャッシュストア命令を実行した場合のフローは、図５Ａ内の矢印の右下方に示されるように、「Ｓ３０１→Ｓ３０３→Ｓ３０５→Ｓ３０７→Ｓ３０９→Ｓ３１１→Ｓ３１３→Ｓ３１５→Ｓ３１７→Ｓ３１９→Ｓ３２１」となる。
【００９７】
次に、図５Ｂを参照し、当該図５Ｂ中の矢印の右上方に示されるように、アドレス“８’ｂ０００１＿００１０”にデータ“０ｘＢ”をライトするキャッシュストア命令を、更に実行する場合のフローについて説明する。
【００９８】
ステップＳ３０１からステップＳ３１５に至るまでのフローは、図５Ａを参照して説明したフローと同一であるため省略する。
【００９９】
ステップＳ３１５において、データアドレス（ストア先アドレス）に含まれるタグ“０００１０”と、キャッシュライン１のタグ部の値“００００１”とが一致しないことから、制御部２１２がキャッシュミスであると判定し、Ｂを経由してステップＳ３２３に移行する。すなわち、ストア先第１候補であるキャッシュライン１以外のキャッシュラインを、制御部２１２が検索する。
【０１００】
ステップＳ３２５において、ＣＲ（ｋ）＝０、且つ、Ｄ（ｋ）＝０、且つ、Ｖ（ｋ）＝１となるキャッシュラインは、ｉｎｄｅｘ  ０、ｉｎｄｅｘ  ２、ｉｎｄｅｘ  ３の３ライン分存在すると、制御部２１２が判定する。
【０１０１】
次に、ステップＳ３２７において、上記条件に該当するキャッシュラインのうち、インデックスが最も若番のキャッシュライン、すなわちｉｎｄｅｘ  ０のキャッシュライン０のデータ部に、データ“０ｘＢ”を書き込み、タグ部にデータアドレス（ストア先アドレス）に含まれるタグ“０００１０”を書き込む。
【０１０２】
次に、ステップＳ３２９においてＤ（０）を１に、ステップＳ３３１においてＣＲ（０）を１に設定する。
【０１０３】
次に、ステップＳ３３３において、インデックス変換部が“ｉｎｄｅｘ  １→ｉｎｄｅｘ  ０”の変換を記憶し、ステップＳ３３５においてフローを終了する。
【０１０４】
その結果、キャッシュメモリは、図５Ｂの下方の概念図に示す状態となる。
【０１０５】
繰り返しになるが、図５Ｂに示されるキャッシュストア命令を実行した場合のフローは、矢印の右下方に示されるように、「Ｓ３０１→Ｓ３０３→Ｓ３０５→Ｓ３０７→Ｓ３０９→Ｓ３１１→Ｓ３１３→Ｓ３１５→Ｓ３２３→Ｓ３２５→Ｓ３２７→Ｓ３２９→Ｓ３３１→Ｓ３３３→Ｓ３３５」となる。
【０１０６】
次に、図５Ｃを参照し、当該図５Ｃ中の矢印の右上方に示されるように、アドレス“８’ｂ０００１＿００１０”にデータ“０ｘＣ”をライトするキャッシュストア命令を、更に実行する場合のフローについて説明する。
【０１０７】
ステップＳ３０１からステップＳ３０９に至るまでのフローは、図５Ａを参照して説明したフローと同一であるため省略する。
【０１０８】
ステップＳ３０９において、データアドレス（ストア先アドレス）に含まれるインデックス１は、インデックス変換部２１１が有する変換制御情報“ｉｎｄｅｘ  １→ｉｎｄｅｘ  ０”に対応するため、インデックス変換部により、異なるインデックス０に変換される（ステップＳ３０９のＹＥＳ）。
【０１０９】
次に、ステップＳ３５９において、制御部２１２がインデックス変換後のストア先第１候補のキャッシュライン０を得る。
【０１１０】
次に、ステップＳ３６１において、ストア先第１候補のキャッシュライン０がキャッシュヒットしたか否かが判定される。具体的には、データアドレス（ストア先アドレス）に含まれるタグが“０００１０”であり、キャッシュライン０のタグ部の値が“０００１０”であるため、キャッシュヒットと判定される（ステップＳ３６１のＹＥＳ）。
【０１１１】
次に、ステップＳ３６３において、ストア先第１候補のキャッシュライン０にデータ“０×Ｃ”が書き込まれる。
【０１１２】
次に、ステップＳ３６５において、Ｄ（０）が１に設定され（ただし、キャッシュストア命令の実行前の段階で、Ｄ（０）＝１となっていたため、Ｄ（０）の状態には変化はない）、ステップＳ３６７においてフローを終了する。
【０１１３】
その結果、キャッシュメモリは、図５Ｃの下方の概念図に示す状態となる。
【０１１４】
繰り返しになるが、図５Ｃに示されるキャッシュストア命令を実行した場合のフローは、矢印の右下方に示されるように、「Ｓ３０１→Ｓ３０３→Ｓ３０５→Ｓ３０７→Ｓ３０９→Ｓ３５９→Ｓ３６１→Ｓ３６３→Ｓ３６５→Ｓ３６７」となる。
【０１１５】
次に、図５Ｄを参照し、当該図５Ｄ中の矢印の右上方に示されるように、アドレス“８’ｂ０００１＿００００”にデータ“０ｘＤ”をライトするキャッシュストア命令を、更に実行する場合のフローについて説明する。
【０１１６】
ステップＳ３０１からステップＳ３１３に至るまでのフローは、図５Ａを参照して説明したフローと同一であるため省略する。
【０１１７】
ステップＳ３１３において、ストア先第１候補のキャッシュライン０のＣＲ（０）が１であるため（ステップＳ３１３のＹＥＳ）、ステップＳ３４５に移行し、制御部２１２がストア先第１候補のキャッシュライン０をメインメモリブロックリプレースする。具体的には、制御部２１２がキャッシュライン０のデータブロックＤＡＴＡ（０）に含まれるデータ“０×Ｃ”を外部メモリ（主記憶メモリ）に書き戻す。
【０１１８】
次に、ステップＳ３４７において、制御部２１２が、ストア先第１候補のキャッシュライン０のデータブロックＤＡＴＡ（０）に、データ“０ｘＤ”を書き込み、タグ部２２９にデータアドレス（ストア先アドレス）に含まれるタグ“０００１０”を書き込む（ただし、キャッシュストア命令の実行前の段階で、タグ部には“０００１０”の値が格納されているため、タグ部の状態には変化はない）。
【０１１９】
次に、ステップＳ３４９において、制御部２１２がキャッシュライン０のダーティビットＤ（０）を１（ダーティ）に設定する（ただし、キャッシュストア命令の実行前の段階で、Ｄ（０）＝１となっていたため、Ｄ（０）の状態には変化はない）。
【０１２０】
次に、ステップＳ３５１において、制御部２１２がＣＲ（０）＝０に設定する。
【０１２１】
次に、ステップＳ３５３において、制御部２１２がキャッシュライン０と依存関係にあったキャッシュライン１のＣＲ（１）を０にリセットする（ただし、キャッシュストア命令の実行前の段階で、ＣＲ（１）＝０となっていたため、ＣＲ（１）の状態には変化はない）。
【０１２２】
次に、ステップＳ３５５において、制御部２１２がインデックス変換部２１１に記憶された“ｉｎｄｅｘ  １→ｉｎｄｅｘ  ０”の情報を消去し、ステップＳ３５７においてフローを終了する。
【０１２３】
その結果、キャッシュメモリは、図５Ｄの下方の概念図に示す状態となる。
【０１２４】
繰り返しになるが、図５Ｄに示されるキャッシュストア命令を実行した場合のフローは、矢印の右下方に示されるように、「Ｓ３０１→Ｓ３０３→Ｓ３０５→Ｓ３０７→Ｓ３０９→Ｓ３１１→Ｓ３１３→Ｓ３４５→Ｓ３４７→Ｓ３４９→Ｓ３５１→Ｓ３５３→Ｓ３５５→Ｓ３５７」となる。
【０１２５】
次に、図５Ｅを参照し、当該図５Ｅ中の矢印の右上方に示されるように、アドレス“８’ｂ０００１＿１０００”にデータ“０ｘＥ”をライトするキャッシュストア命令を、更に実行する場合のフローについて説明する。
【０１２６】
図５Ｅ中の矢印の右下方に示されるように、当該キャッシュストア命令を実行する場合の全フローは、図５Ｂを参照して説明したフローと同一であるため、説明は省略する。
【０１２７】
その結果、キャッシュメモリは、図５Ｅの下方の概念図に示す状態となる。
【０１２８】
次に、図５Ｆを参照し、当該図５Ｆ中の矢印の右上方に示されるように、アドレス“８’ｂ０００１＿００００”にデータ“０ｘＦ”をライトするキャッシュストア命令を、更に実行する場合のフローについて説明する。
【０１２９】
ステップＳ３０１からステップＳ３６１に至るまでのフローは、図５Ｃを参照して説明したフローと同一であるため省略する。
【０１３０】
ステップＳ３６１において、インデックス変換後であるストア先第１候補であるキャッシュライン２がキャッシュヒットしたか否かが判定される。具体的にはデータアドレス（ストア先アドレス）に含まれるタグが“０００１０”であり、キャッシュライン２のタグ部の値が“０００１１”であるため、お互いに一致せず、制御部２１２がキャッシュミスと判定する（ステップＳ３６１のＮＯ）。この場合、Ｃを経由して、ステップＳ３６９に移行する。
【０１３１】
ステップＳ３６９では、インデックス変換前、すなわちインデックスが０のキャッシュライン０をストア先第２候補とする。このキャッシュライン０のタグ部の値“０００１０”と、データアドレス（ストア先アドレス）に含まれるタグ“０００１０”とを、比較器２１０で比較すると、それらの値は互いに一致するため、キャッシュヒットと判定する（ステップＳ３６９のＹＥＳ）。
【０１３２】
次に、ステップＳ３７１において、制御部２１２がストア先第２候補のキャッシュライン０のデータブロックＤＡＴＡ（０）にデータ“０ｘＦ”を書き込む。
【０１３３】
次に、ステップＳ３７３において、制御部２１２がキャッシュライン０のＤ（０）を１に設定し（ただし、キャッシュストア命令の実行前の段階で、Ｄ（０）＝１となっていたため、Ｄ（０）の状態には変化はない）、ステップＳ３７５においてフローを終了する。
【０１３４】
その結果、キャッシュメモリは、図５Ｆの下方の概念図に示す状態となる。
【０１３５】
繰り返しになるが、図５Ｆに示されるキャッシュストア命令を実行した場合のフローは、矢印の右下方に示されるように、「Ｓ３０１→Ｓ３０３→Ｓ３０５→Ｓ３０７→Ｓ３０９→Ｓ３５９→Ｓ３６１→Ｓ３６９→Ｓ３７１→Ｓ３７３→Ｓ３７５」となる。
【０１３６】
次に、図５Ｇを参照し、当該図５Ｇ中の矢印の右上方に示されるように、アドレス“８’ｂ００１０＿００００”にデータ“０ｘ１”をライトするキャッシュストア命令を、更に実行する場合のフローについて説明する。
【０１３７】
ステップＳ３０１からステップＳ３６９に至るまでのフローは、図５Ｆを参照して説明したフローと同一であるため省略する。
【０１３８】
ステップＳ３６９では、インデックス変換前、すなわちインデックスが０のキャッシュライン０をストア先第２候補とする。このキャッシュライン０のタグ部の値“０００１０”と、データアドレス（ストア先アドレス）に含まれるタグ“００１００”とを、比較器２１０で比較すると、それらの値は互いに異なるため、制御部２１２がキャッシュミスと判定する（ステップＳ３６９のＮＯ）。
【０１３９】
次に、ステップＳ３７７において、制御部２１２がストア先第１候補であるキャッシュライン２をメインメモリブロックリプレースする。具体的には、制御部２１２が、キャッシュライン２のデータブロックＤＡＴＡ（０）に含まれるデータ“０ｘＥ”を外部メモリ（主記憶メモリ）に書き戻す。
【０１４０】
次に、ステップＳ３７９において、制御部２１２が、ストア先第１候補であるキャッシュライン２のデータブロックＤＡＴＡ（０）にデータ“０ｘ１”を書き込み、タグ部にデータアドレス（ストア先アドレス）２０１に含まれるタグ“００１００”を書き込む。
【０１４１】
次に、ステップＳ３８１において、制御部２１２がキャッシュライン２のダーティビットＤ（２）を１（ダーティ）に設定する（ただし、キャッシュストア命令の実行前の段階で、Ｄ（２）＝１となっていたため、Ｄ（２）の状態には変化はない）。
【０１４２】
次に、ステップＳ３８３において、制御部２１２が、ＣＲ（２）を０に設定する。
【０１４３】
次に、ステップＳ３８５において、制御部２１２が、インデックス変換部に記憶された“ｉｎｄｅｘ  ０→ｉｎｄｅｘ  ２”の情報を消去し、ステップＳ３８７において、フローは終了する。
【０１４４】
その結果、キャッシュメモリは、図５Ｇの下方の概念図に示す状態となる。
【０１４５】
繰り返しになるが、図５Ｇに示されるキャッシュストア命令を実行した場合のフローは、矢印の右下方に示されるように、「Ｓ３０１→Ｓ３０３→Ｓ３０５→Ｓ３０７→Ｓ３０９→Ｓ３５９→Ｓ３６１→Ｓ３６９→Ｓ３７７→Ｓ３７９→Ｓ３８１→Ｓ３８３→Ｓ３８５→Ｓ３８７」となる。
【０１４６】
次に、図５Ｈを参照し、当該図５Ｈ中の矢印の右上方に示されるように、アドレス“８’ｂ１１１１＿１０１０にデータ０ｘ９をライトするキャッシュストア命令を、更に実行する場合のフローについて説明する。
【０１４７】
図５Ｈ中の矢印の右下方に示されるように、当該キャッシュストア命令を実行する場合の全フローは、図５Ｂを参照して説明したフローと同一であるため、説明は省略する。
【０１４８】
その結果、キャッシュメモリは、図５Ｈの下方の概念図に示す状態となる。
【０１４９】
次に、図６Ａを参照し、当該図６Ａ中の矢印の右上方に示されるように、アドレス“８’ｂ０００１＿００００”からデータをロードするキャッシュロード命令を、更に実行する場合のフローについて説明する。
【０１５０】
まず、ステップＳ４０１において、キャッシュロード命令をＣＰＵから入力することにより、キャッシュロード命令の実行を開始する。
【０１５１】
次に、ステップＳ４０３において、キャッシュロード命令に含まれているデータアドレス（ロード先アドレス）である“８’ｂ０００１＿００００”を読み込む。
【０１５２】
次に、ステップＳ４０５において、読み込んだアドレス中の先頭から６〜７ｂｉｔ目が“００”であることから、インデックスとしてｉｎｄｅｘ  ０を得る。
【０１５３】
次に、ステップＳ４０７において、ｉｎｄｅｘ  ０をインデックス変換部に与える。しかし、インデックス変換部はｉｎｄｅｘ  ０を入力とする変換制御情報は記憶していないため、ｉｎｄｅｘ  ０を変換することなく（ステップＳ４０９のＮＯ）、Ａを経由してステップＳ４１１に移行し、制御部２１２が、ロード先第１候補としてｉｎｄｅｘ  ０のキャッシュライン０を得る。
【０１５４】
次に、ステップＳ４１３において、キャッシュライン０のＣＲ（０）が０であることから、ステップＳ３１５に進み、キャッシュライン０がキャッシュヒットしたか否かを、制御部２１２が判定する。ここで、データアドレス（ロード先アドレス）に含まれるタグ“０００１０”と、キャッシュライン０のタグ部の値“０００１０”とが一致することから、キャッシュヒットと判定され（ステップＳ４１５のＹＥＳ）、ステップＳ４１７に移行する。
【０１５５】
ステップＳ４１７において、ロード先第１候補であるキャッシュライン０からデータを読み出す。ここで、データアドレス（ロード先アドレス）に含まれるオフセット、すなわち、アドレスの先頭から８ｂｉｔ目が０であることから、オフセット０に対応するＤＡＴＡ（０）のデータブロックから、データ“０ｘＦ”が読み出され、ステップＳ４１９においてフローは終了する。
【０１５６】
その結果、キャッシュメモリは、図６Ａの下方の概念図に示す状態となる。図６Ａのフローにおいてはデータのリプレースが発生しなかったため、キャッシュロード命令によるアクセスの前と後とでは、キャッシュメモリの状態に変化はない。
【０１５７】
繰り返しになるが、図６Ａに示されるキャッシュロード命令を実行した場合のフローは、矢印の右下方に示されるように、「Ｓ４０１→Ｓ４０３→Ｓ４０５→Ｓ４０７→Ｓ４０９→Ｓ４１１→Ｓ４１３→Ｓ４１５→Ｓ４１７→Ｓ４１９」となる。
【０１５８】
次に、図６Ｂを参照し、当該図６Ｂ中の矢印の右上方に示されるように、アドレス“８’ｂ０００１＿１０００”からデータをロードするキャッシュロード命令を、更に実行する場合のフローについて説明する。
【０１５９】
ステップＳ４０１からステップＳ４１５に至るまでのフローは、図６Ａを参照して説明したフローと同一であるため省略する。
【０１６０】
ステップＳ４１５において、データアドレス（ロード先アドレス）に含まれるタグ“０００１１”と、キャッシュライン０のタグ部の値“０００１０”とが一致しないことから、キャッシュミスと判定し、Ｂを経由してステップＳ４２１に移行する。
【０１６１】
次に、ステップＳ４２１において、ロード先第１候補のキャッシュライン０をメインメモリブロックリプレースする。具体的には、ロード先第１候補のキャッシュライン０に対応する外部メモリ（主記憶メモリ）のデータを、キャッシュライン０のデータブロックＤＡＴＡ（０）に書き込む。ここで、外部メモリ（主記憶メモリ）からデータブロックＤＡＴＡ（０）に書き込まれるデータは、仮に“０ｘ４”とする。更に、キャッシュライン０のタグ部に、データアドレス（ロード先アドレス）に含まれるタグ“０００１１”を書き込む。
【０１６２】
次に、ステップＳ４２３において、制御部２１２がロード先第１候補のキャッシュライン０のデータブロックＤＡＴＡ（０）から、データ“０ｘ４”を読み出す。
【０１６３】
次に、ステップＳ４２５において、制御部２１２がキャッシュライン０のＤ（０）を０に設定し、ステップＳ４２７において、フローを終了する。
【０１６４】
その結果、キャッシュメモリは、図６Ｂの下方の概念図に示す状態となる。
【０１６５】
繰り返しになるが、図６Ｂに示されるキャッシュロード命令を実行した場合のフローは、矢印の右下方に示されるように、「Ｓ４０１→Ｓ４０３→Ｓ４０５→Ｓ４０７→Ｓ４０９→Ｓ４１１→Ｓ４１３→Ｓ４１５→Ｓ４２１→Ｓ４２３→Ｓ４２５→Ｓ４２７」となる。
【０１６６】
次に、図６Ｃを参照し、当該図６Ｃ中の矢印の右上方に示されるように、アドレス“８’ｂ１１１１＿１０１０”からデータをロードするキャッシュロード命令を、更に実行する場合のフローについて説明する。
【０１６７】
ステップＳ４０１からステップＳ４０９に至るまでのフローは、図６Ａを参照して説明したフローと同一であるため省略する。
【０１６８】
ステップＳ４０９において、データアドレス（ロード先アドレス）に含まれるインデックス１は、インデックス変換部２１１が有する変換制御情報“ｉｎｄｅｘ  １→ｉｎｄｅｘ  ３”に対応するため、インデックス変換部２１１により、異なるインデックス３に変換される（ステップＳ４０９のＹＥＳ）。
【０１６９】
次に、ステップＳ４４１において、インデックスを１→３と変換した後の、ロード先第１候補のキャッシュライン３を、制御部２１２が得る。
【０１７０】
次に、ステップＳ４４３において、インデックス変換後のロード先第１候補のキャッシュライン３のタグ部の値“１１１１１”と、データアドレス（ロード先アドレス）に含まれるタグ“１１１１１”とを比較器２０１で比較し、それらの値が一致するため、キャッシュヒットと判定する。
【０１７１】
次に、ステップＳ４４５において、制御部２１２がインデックス変換後のロード先第１候補のキャッシュライン３のデータブロックＤＡＴＡ（０）からデータ“０ｘ９”を読み出し、ステップＳ４４７においてフローを終了する。
【０１７２】
その結果、キャッシュメモリは、図６Ｃの下方の概念図に示す状態となる。図６Ｃのフローにおいてはデータのリプレースが発生しなかったため、キャッシュロード命令によるアクセスの前と後とでは、キャッシュメモリの状態に変化はない。
【０１７３】
繰り返しになるが、図６Ｃに示されたキャッシュロード命令を実行した場合のフローは、矢印の右下方に示されるように、「Ｓ４０１→Ｓ４０３→Ｓ４０５→Ｓ４０７→Ｓ４０９→Ｓ４４１→Ｓ４４３→Ｓ４４５→Ｓ４４７」となる。
【０１７４】
次に、図６Ｄを参照し、当該図６Ｄ中の矢印の右上方に示されるように、アドレス“８’ｂ００００＿１０１０”からデータをロードするキャッシュロード命令を、更に実行する場合のフローについて説明する。
【０１７５】
ステップＳ４０１からステップＳ４４３に至るまでのフローは、図６Ｃを参照して説明したフローと同一であるため省略する。
【０１７６】
ステップＳ４４３において、インデックス変換後のロード先第１候補のキャッシュライン３のタグ部の値“１１１１１”と、データアドレス（ロード先アドレス）に含まれるタグ“００００１”とを比較器２０１で比較し、それらの値が異なるためキャッシュミスと判定する（ステップＳ４４３のＮＯ）。この場合は、Ｃを経由してステップＳ４４９に移行する。
【０１７７】
ステップＳ４４９において、インデックス変換前、すなわちインデックスが１のキャッシュラインをロード先第２候補とする。その上で、このキャッシュライン１のタグ部の値“００００１”と、データアドレス（ロード先アドレス）に含まれるタグ“００００１”とを、比較器２１０で比較し、それらの値が一致するためキャッシュヒットと判定し（ステップＳ４４９のＹＥＳ）、ステップＳ４５１に移行する。
【０１７８】
次に、ステップＳ４５１において、制御部２１２がロード先第２候補のキャッシュライン１のデータブロックＤＡＴＡ（０）からデータ“０ｘＡ”を読み出し、ステップＳ４５３においてフローを終了する。
【０１７９】
その結果、キャッシュメモリは、図６Ｄの下方の概念図に示す状態となる。図６Ｄのフローにおいてはデータのリプレースが発生しなかったため、キャッシュロード命令によるアクセスの前と後とでは、キャッシュメモリの状態に変化はない。
【０１８０】
繰り返しになるが、図６Ｄに示されるキャッシュロード命令を実行した場合のフローは、矢印の右下方に示されるように、「Ｓ４０１→Ｓ４０３→Ｓ４０５→Ｓ４０７→Ｓ４０９→Ｓ４４１→Ｓ４４３→Ｓ４４９→Ｓ４５１→Ｓ４５３」となる。
【０１８１】
次に、図６Ｅを参照し、当該図６Ｅ中の矢印の右上方に示されるように、アドレス“８’ｂ１１１１＿１１１０”からデータをロードするキャッシュロード命令を、更に実行する場合のフローについて説明する。
【０１８２】
ステップＳ４０１からステップＳ４１３に至るまでのフローは、図６Ａを参照して説明したフローと同一であるため省略する。
【０１８３】
ステップＳ４１３において、制御部２１２が、ロード先第１候補のキャッシュライン３のＣＲ（３）が１か否かを判定する。ＣＲ（３）＝１であるため（ステップＳ４１３のＹＥＳ）、ステップＳ４２９に移行する。
【０１８４】
ステップＳ４２９において、制御部２１２が、ロード先第１候補のキャッシュライン３をメインメモリブロックリプレースする。具体的には、制御部２１２が、キャッシュライン２に対応する外部メモリ（主記憶メモリ）のデータを、キャッシュライン３のデータブロックＤＡＴＡ（０）に書き込む。ここで、外部メモリ（主記憶メモリ）からデータブロックＤＡＴＡ（０）に書き込まれるデータは、仮に“０ｘＥ”とする。更に、キャッシュライン３のタグ部に、データアドレス（ロード先アドレス）に含まれるタグ“１１１１１”を書き込む（ただし、キャッシュロード命令の実行前の段階で、キャッシュライン３のタグ部の値は“１１１１１”となっていたため、タグ部の状態には変化はない）。
【０１８５】
次に、ステップＳ４３１において、制御部２１２が、ロード先第１候補のキャッシュラインｉのデータブロックＤＡＴＡ（０）からデータ“０ｘＥ”を読み出す。
【０１８６】
次に、ステップＳ４３３において、制御部２１２が、ロード先第１候補のキャッシュライン３のＣＲ（３）を０に設定する。
【０１８７】
次に、ステップＳ４３５において、制御部２１２がキャッシュライン３のＤ（３）を０に設定する。
【０１８８】
次に、ステップＳ４３７において、制御部２１２が、インデックス変換部２１１に記憶された“ｉｎｄｅｘ  １→ｉｎｄｅｘ  ３”の情報を消去し、ステップＳ４３９においてフローを終了する。
【０１８９】
その結果、キャッシュメモリは、図６Ｅの下方の概念図に示す状態となる。
【０１９０】
繰り返しになるが、図６Ｅに示されたキャッシュロード命令を実行した場合のフローは、矢印の右下方に示されるように、「Ｓ４０１→Ｓ４０３→Ｓ４０５→Ｓ４０７→Ｓ４０９→Ｓ４１１→Ｓ４１３→Ｓ４２９→Ｓ４３１→Ｓ４３３→Ｓ４３５→Ｓ４３７→Ｓ４３９」となる。
【０１９１】
本発明は、従来のライトバック型ダイレクトマップ形式のキャッシュメモリと比較して、キャッシュラインのダーティな状態と使用状況とを事前に解析し、キャッシュメモリ書き込みミス等に起因した、主記憶メモリに対するデータ書き戻しを行う代わりに、他の使用可能なキャッシュラインを利用するように制御することを可能とするものである。即ち、従来以上にキャッシュスペースの有効活用を可能とすることで、従来キャッシュアクセス中に発生していた、キャッシュメモリ上のデータを主記憶メモリへ書き戻す機会を低減可能とするものである。これにより、従来方式と比較して、大きなレイテンシを必要とする主記憶メモリに対するデータ書き戻し回数を低減することを可能とし、メモリシステム全体のスループット向上が期待できる。
【０１９２】
以上、上記各実施例を参照して本願発明を説明したが、本願発明は上記各実施例に限定されるものではない。本願発明の構成や詳細には、本願発明の範囲内で当業者が理解し得る様々な変更をすることができる。
【０１９３】
なお、上記のキャッシュメモリの各部分は、ハードウェア、ソフトウェアのいずれか又はこれらの組み合わせにより実現することができる。また、上記のキャッシュメモリにより行われるキャッシュメモリへのアクセス方法も、ハードウェア、ソフトウェアのいずれか又はこれらの組み合わせにより実現することができる。ここで、ソフトウェアによって実現されるとは、コンピュータがプログラムを読み込んで実行すること、又は、ハードウェアがプログラムに相当するマイクロコードに従って動作することにより実現されることを意味する。
【０１９４】
プログラムは、様々なタイプの非一時的なコンピュータ可読媒体(non-transitory computer readable medium)を用いて格納され、コンピュータに供給することができる。非一時的なコンピュータ可読媒体は、様々なタイプの実体のある記録媒体(tangible storage medium)を含む。非一時的なコンピュータ可読媒体の例は、磁気記録媒体（例えば、フレキシブルディスク、磁気テープ、ハードディスクドライブ）、光磁気記録媒体（例えば、光磁気ディスク）、ＣＤ−ＲＯＭ(Read Only Memory)、ＣＤ−Ｒ、ＣＤ−Ｒ／Ｗ、半導体メモリ（例えば、マスクＲＯＭ、ＰＲＯＭ(Programmable ROM)、ＥＰＲＯＭ(Erasable PROM)、フラッシュＲＯＭ、ＲＡＭ(random access memory)）を含む。また、プログラムは、様々なタイプの一時的なコンピュータ可読媒体(transitory computer readable medium)によってコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、プログラムをコンピュータに供給できる。
【０１９５】
上記の実施形態の一部または全部は、以下の付記のようにも記載されるが、以下には限られない。
【０１９６】
（付記１）
キャッシュメモリであって、
記憶手段と、
第１のデータアドレスに含まれる第１のインデックスに対応し、前記記憶手段に含まれる第１のキャッシュラインにおいてキャッシュミスが発生する際、当該キャッシュ内リプレースのリプレース先に今まではなっておらず、ダーティビットがクリーンであり、前記記憶手段に含まれる第２のキャッシュラインにおいてキャッシュストアを実行することによりキャッシュ内リプレースを実施する制御手段と、
を備えることを特徴とするキャッシュメモリ。
【０１９７】
（付記２）
付記１に記載のキャッシュメモリであって、
前記第１のインデックスから、前記第２のキャッシュラインに対応する第２のインデックスへの変換制御情報を記憶するインデックス変換手段であって、第２のデータアドレスが読み込まれ、該第２のデータアドレスに前記第１のインデックスが含まれる際、前記変換制御情報に基づき、前記第２のデータアドレスに含まれる前記第１のインデックスを前記第２のインデックスに変換し、該第２のインデックスを前記制御手段に出力するインデックス変換手段を更に備え、
前記制御手段は、前記インデックス変換手段からの前記第２のインデックスの入力に応じて、前記第２のキャッシュラインをアクセス先の候補とすることを特徴とするキャッシュメモリ。
【０１９８】
（付記３）
付記２に記載のキャッシュメモリであって、
前記制御手段が、前記第２のインデックスの入力に応じて前記第２のキャッシュラインをアクセス先の候補とする際、前記第２のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記第２のキャッシュラインにおいてキャッシュストアを実行することを特徴とするキャッシュメモリ。
【０１９９】
（付記４）
付記２又は３に記載のキャッシュメモリであって、
前記制御手段が、前記第２のインデックスの入力に応じて前記第２のキャッシュラインをアクセス先の候補とする際、前記第２のキャッシュラインにおいてキャッシュミスが発生する場合に、前記第１のキャッシュラインをアクセス先の候補とし、前記第１のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記第１のキャッシュラインにおいてキャッシュストアを実行することを特徴とするキャッシュメモリ。
【０２００】
（付記５）
付記２乃至４のいずれか１に記載のキャッシュメモリであって、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが有効となっている場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュストアの後、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグを無効に設定し、前記第１のキャッシュラインに含まれるダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが無効になっており、前記第１のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュストアの後、前記第１のキャッシュラインに含まれる前記ダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが無効になっており、前記第１のキャッシュラインにおいてキャッシュミスが発生し、前記第２のキャッシュラインが存在する場合に、前記制御手段が、前記第２のキャッシュラインにおけるキャッシュストアの後、前記第２のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグを有効に設定し、前記第２のキャッシュラインに含まれるダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが無効になっており、前記第１のキャッシュラインにおいてキャッシュミスが発生し、前記第２のキャッシュラインが存在しない場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュストアの後、前記第１のキャッシュラインに含まれるダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって前記第２のインデックスに変換され、前記第２のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記制御手段が、前記第２のキャッシュラインにおけるキャッシュストアの後、前記第２のキャッシュラインに含まれるダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって前記第２のインデックスに変換され、前記第２のキャッシュラインにおいてキャッシュミスが発生し、前記第１のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュストアの後、前記第１のキャッシュラインに含まれるダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって前記第２のインデックスに変換され、前記第２のキャッシュラインにおいてキャッシュミスが発生した後、更に、前記第１のキャッシュラインにおいてもキャッシュミスが発生する場合に、前記制御手段が、前記第２のキャッシュラインにおけるキャッシュストアの後、前記第２のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグを無効に設定し、前記第２のキャッシュラインに含まれるダーティビットをダーティに設定することを特徴とするキャッシュメモリ。
【０２０１】
（付記６）
付記２乃至５のいずれか１に記載のキャッシュメモリであって、
前記制御手段が、前記第２のインデックスの入力に応じて前記第２のキャッシュラインをアクセス先の候補とする際、前記第２のキャッシュラインにおいてキャッシュヒットが発生する場合は、前記第２のキャッシュラインにおいてキャッシュロードを実行することを特徴とするキャッシュメモリ。
【０２０２】
（付記７）
付記２乃至６のいずれか１に記載のキャッシュメモリであって、
前記制御手段が、前記第２のインデックスの入力に応じて前記第２のキャッシュラインをアクセス先の候補とする際、前記第２のキャッシュラインにおいてキャッシュミスが発生する場合は、前記第１のキャッシュラインをアクセス先の候補とし、前記第１のキャッシュラインにおいてキャッシュヒットが発生する場合は、前記第１のキャッシュラインにおいてキャッシュロードを実行することを特徴とするキャッシュメモリ。
【０２０３】
（付記８）
付記２乃至７のいずれか１に記載のキャッシュメモリであって、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが有効となっている場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュロードの後、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグを無効に設定し、前記第１のキャッシュラインに含まれるダーティビットをクリーンに設定し、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが無効になっており、前記第１のキャッシュラインにおいてキャッシュミスが発生する場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュロードの後、前記第１のキャッシュラインに含まれるダーティビットをクリーンに設定し、
前記第１のインデックスが前記インデックス変換手段によって前記第２のインデックスに変換され、前記第２のキャッシュラインにおいてキャッシュミスが発生した後、更に、前記第１のキャッシュラインにおいてもキャッシュミスが発生する場合に、前記制御手段が、前記第２のキャッシュラインにおけるキャッシュロードの後、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグと、前記第２のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグとの双方を無効に設定し、前記第２のキャッシュラインに含まれるダーティビットをクリーンに設定することを特徴とするキャッシュメモリ。
【０２０４】
（付記９）
キャッシュメモリにおけるアクセス方法であって、
制御手段が、第１のデータアドレスに含まれる第１のインデックスに対応し、記憶手段に含まれる第１のキャッシュラインにおいてキャッシュミスが発生する際、当該キャッシュ内リプレースのリプレース先に今まではなっておらず、ダーティビットがクリーンであり、前記記憶手段に含まれる第２のキャッシュラインにおいてキャッシュストアを実行することによりキャッシュ内リプレースを実施するステップを有することを特徴とするアクセス方法。
【０２０５】
（付記１０）
付記９に記載のアクセス方法であって、
インデックス変換手段が、前記第１のインデックスから、前記第２のキャッシュラインに対応する第２のインデックスへの変換制御情報を記憶するステップと、
前記インデックス変換手段が、第２のデータアドレスが読み込まれ、該第２のデータアドレスに前記第１のインデックスが含まれる際、前記変換制御情報に基づき、前記第２のデータアドレスに含まれる前記第１のインデックスを前記第２のインデックスに変換し、該第２のインデックスを前記制御手段に出力するステップとを更に有し、
前記制御手段は、前記インデックス変換手段からの前記第２のインデックスの入力に応じて、前記第２のキャッシュラインをアクセス先の候補とすることを特徴とするアクセス方法。
【０２０６】
（付記１１）
付記１０に記載のアクセス方法であって、
前記制御手段が、前記第２のインデックスの入力に応じて前記第２のキャッシュラインをアクセス先の候補とする際、前記第２のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記第２のキャッシュラインにおいてキャッシュストアを実行することを特徴とするアクセス方法。
【０２０７】
（付記１２）
付記１０又は１１に記載のアクセス方法であって、
前記制御手段が、前記第２のインデックスの入力に応じて前記第２のキャッシュラインをアクセス先の候補とする際、前記第２のキャッシュラインにおいてキャッシュミスが発生する場合に、前記第１のキャッシュラインをアクセス先の候補とし、前記第１のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記第１のキャッシュラインにおいてキャッシュストアを実行することを特徴とするアクセス方法。
【０２０８】
（付記１３）
付記１０乃至１２のいずれか１に記載のアクセス方法であって、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが有効となっている場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュストアの後、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグを無効に設定し、前記第１のキャッシュラインに含まれるダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが無効になっており、前記第１のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュストアの後、前記第１のキャッシュラインに含まれる前記ダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが無効になっており、前記第１のキャッシュラインにおいてキャッシュミスが発生し、前記第２のキャッシュラインが存在する場合に、前記制御手段が、前記第２のキャッシュラインにおけるキャッシュストアの後、前記第２のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグを有効に設定し、前記第２のキャッシュラインに含まれるダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが無効になっており、前記第１のキャッシュラインにおいてキャッシュミスが発生し、前記第２のキャッシュラインが存在しない場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュストアの後、前記第１のキャッシュラインに含まれるダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって前記第２のインデックスに変換され、前記第２のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記制御手段が、前記第２のキャッシュラインにおけるキャッシュストアの後、前記第２のキャッシュラインに含まれるダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって前記第２のインデックスに変換され、前記第２のキャッシュラインにおいてキャッシュミスが発生し、前記第１のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュストアの後、前記第１のキャッシュラインに含まれるダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって前記第２のインデックスに変換され、前記第２のキャッシュラインにおいてキャッシュミスが発生した後、更に、前記第１のキャッシュラインにおいてもキャッシュミスが発生する場合に、前記制御手段が、前記第２のキャッシュラインにおけるキャッシュストアの後、前記第２のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグを無効に設定し、前記第２のキャッシュラインに含まれるダーティビットをダーティに設定することを特徴とするアクセス方法。
【０２０９】
（付記１４）
付記１０乃至１３のいずれか１に記載のアクセス方法であって、
前記制御手段が、前記第２のインデックスの入力に応じて前記第２のキャッシュラインをアクセス先の候補とする際、前記第２のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記第２のキャッシュラインにおいてキャッシュロードを実行することを特徴とするアクセス方法。
【０２１０】
（付記１５）
付記１０乃至１４のいずれか１に記載のアクセス方法であって、
前記制御手段が、前記第２のインデックスの入力に応じて前記第２のキャッシュラインをアクセス先の候補とする際、前記第２のキャッシュラインにおいてキャッシュミスが発生する場合に、前記第１のキャッシュラインをアクセス先の候補とし、前記第１のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記第１のキャッシュラインにおいてキャッシュロードを実行することを特徴とするアクセス方法。
【０２１１】
（付記１６）
付記１０乃至１５のいずれか１に記載のアクセス方法であって、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが有効となっている場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュロードの後、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグを無効に設定し、前記第１のキャッシュラインに含まれるダーティビットをクリーンに設定し、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが無効になっており、前記第１のキャッシュラインにおいてキャッシュミスが発生する場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュロードの後、前記第１のキャッシュラインに含まれるダーティビットをクリーンに設定し、
前記第１のインデックスが前記インデックス変換手段によって前記第２のインデックスに変換され、前記第２のキャッシュラインにおいてキャッシュミスが発生した後、更に、前記第１のキャッシュラインにおいてもキャッシュミスが発生する場合に、前記制御手段が、前記第２のキャッシュラインにおけるキャッシュロードの後、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグと、前記第２のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグとの双方を無効に設定し、前記第２のキャッシュラインに含まれるダーティビットをクリーンに設定することを特徴とするアクセス方法。
【０２１２】
（付記１７）
キャッシュメモリにおけるアクセス方法をコンピュータに実行させるためのキャッシュメモリアクセス用プログラムであって、
前記アクセス方法は、
制御手段が、第１のデータアドレスに含まれる第１のインデックスに対応し、記憶手段に含まれる第１のキャッシュラインにおいてキャッシュミスが発生する際、当該キャッシュ内リプレースのリプレース先に今まではなっておらず、ダーティビットがクリーンであり、前記記憶手段に含まれる第２のキャッシュラインにおいてキャッシュストアを実行することによりキャッシュ内リプレースを実施するステップを有することを特徴とするキャッシュメモリアクセス用プログラム。
【０２１３】
（付記１８）
付記１７に記載のキャッシュメモリアクセス用プログラムであって、
前記アクセス方法は、
インデックス変換手段が、前記第１のインデックスから、前記第２のキャッシュラインに対応する第２のインデックスへの変換制御情報を記憶するステップと、
前記インデックス変換手段が、第２のデータアドレスが読み込まれ、該第２のデータアドレスに前記第１のインデックスが含まれる際、前記変換制御情報に基づき、前記第２のデータアドレスに含まれる前記第１のインデックスを前記第２のインデックスに変換し、該第２のインデックスを前記制御手段に出力するステップとを更に有し、
前記制御手段は、前記インデックス変換手段からの前記第２のインデックスの入力に応じて、前記第２のキャッシュラインをアクセス先の候補とすることを特徴とするキャッシュメモリアクセス用プログラム。
【０２１４】
（付記１９）
付記１８に記載のキャッシュメモリアクセス用プログラムであって、
前記制御手段が、前記第２のインデックスの入力に応じて前記第２のキャッシュラインをアクセス先の候補とする際、前記第２のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記第２のキャッシュラインにおいてキャッシュストアを実行することを特徴とするキャッシュメモリアクセス用プログラム。
【０２１５】
（付記２０）
付記１８又は１９に記載のキャッシュメモリアクセス用プログラムであって、
前記制御手段が、前記第２のインデックスの入力に応じて前記第２のキャッシュラインをアクセス先の候補とする際、前記第２のキャッシュラインにおいてキャッシュミスが発生する場合に、前記第１のキャッシュラインをアクセス先の候補とし、前記第１のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記第１のキャッシュラインにおいてキャッシュストアを実行することを特徴とするキャッシュメモリアクセス用プログラム。
【０２１６】
（付記２１）
付記１８乃至２０のいずれか１に記載のキャッシュメモリアクセス用プログラムであって、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが有効となっている場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュストアの後、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグを無効に設定し、前記第１のキャッシュラインに含まれるダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが無効になっており、前記第１のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュストアの後、前記第１のキャッシュラインに含まれる前記ダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが無効になっており、前記第１のキャッシュラインにおいてキャッシュミスが発生し、前記第２のキャッシュラインが存在する場合に、前記制御手段が、前記第２のキャッシュラインにおけるキャッシュストアの後、前記第２のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグを有効に設定し、前記第２のキャッシュラインに含まれるダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが無効になっており、前記第１のキャッシュラインにおいてキャッシュミスが発生し、前記第２のキャッシュラインが存在しない場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュストアの後、前記第１のキャッシュラインに含まれるダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって前記第２のインデックスに変換され、前記第２のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記制御手段が、前記第２のキャッシュラインにおけるキャッシュストアの後、前記第２のキャッシュラインに含まれるダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって前記第２のインデックスに変換され、前記第２のキャッシュラインにおいてキャッシュミスが発生し、前記第１のキャッシュラインにおいてキャッシュヒットが発生する場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュストアの後、前記第１のキャッシュラインに含まれるダーティビットをダーティに設定し、
前記第１のインデックスが前記インデックス変換手段によって前記第２のインデックスに変換され、前記第２のキャッシュラインにおいてキャッシュミスが発生した後、更に、前記第１のキャッシュラインにおいてもキャッシュミスが発生する場合に、前記制御手段が、前記第２のキャッシュラインにおけるキャッシュストアの後、前記第２のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグを無効に設定し、前記第２のキャッシュラインに含まれるダーティビットをダーティに設定することを特徴とするキャッシュメモリアクセス用プログラム。
【０２１７】
（付記２２）
付記１８乃至２１のいずれか１に記載のキャッシュメモリアクセス用プログラムであって、
前記制御手段が、前記第２のインデックスの入力に応じて前記第２のキャッシュラインをアクセス先の候補とする際、前記第２のキャッシュラインにおいてキャッシュヒットが発生する場合は、前記第２のキャッシュラインにおいてキャッシュロードを実行することを特徴とするキャッシュメモリアクセス用プログラム。
【０２１８】
（付記２３）
付記１８乃至２２のいずれか１に記載のキャッシュメモリアクセス用プログラムであって、
前記制御手段が、前記第２のインデックスの入力に応じて前記第２のキャッシュラインをアクセス先の候補とする際、前記第２のキャッシュラインにおいてキャッシュミスが発生する場合は、前記第１のキャッシュラインをアクセス先の候補とし、前記第１のキャッシュラインにおいてキャッシュヒットが発生する場合は、前記第１のキャッシュラインにおいてキャッシュロードを実行することを特徴とするキャッシュメモリアクセス用プログラム。
【０２１９】
（付記２４）
付記１８乃至２３のいずれか１に記載のキャッシュメモリアクセス用プログラムであって、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが有効となっている場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュロードの後、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグを無効に設定し、前記第１のキャッシュラインに含まれるダーティビットをクリーンに設定し、
前記第１のインデックスが前記インデックス変換手段によって変換されず、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグが無効になっており、前記第１のキャッシュラインにおいてキャッシュミスが発生する場合に、前記制御手段が、前記第１のキャッシュラインにおけるキャッシュロードの後、前記第１のキャッシュラインに含まれるダーティビットをクリーンに設定し、
前記第１のインデックスが前記インデックス変換手段によって前記第２のインデックスに変換され、前記第２のキャッシュラインにおいてキャッシュミスが発生した後、更に、前記第１のキャッシュラインにおいてもキャッシュミスが発生する場合に、前記制御手段が、前記第２のキャッシュラインにおけるキャッシュロードの後、前記第１のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグと、前記第２のキャッシュラインに含まれ、且つ、キャッシュ内リプレースのリプレース先になっていることを示すフラグとの双方を無効に設定し、前記第２のキャッシュラインに含まれるダーティビットをクリーンに設定することを特徴とするキャッシュメモリアクセス用プログラム。
【産業上の利用可能性】
【０２２０】
本発明は、キャッシュメモリを含むコンピュータで利用することができる。また、本発明は、コンピュータ上のキャッシュメモリを管理するプログラム又はハードウェア構造を最適化するアルゴリズムの一つとして利用することが出来る。
【符号の説明】
【０２２１】
１０１  プロセッサコア
１０２  キャッシュメモリ
１０３  プロセッサバス
１０４  ブリッジ
１０５  メモリコントローラ
１０６  メインメモリ
１０７  ローカルバス
１０８  ＳＣＳＩコントローラ
１０９  ハードディスクドライブ
２０１  データアドレス
２０３  タグ
２０５  インデックス
２０７  オフセット
２０１−１  第１の比較器
２０１−２  第２の比較器
２０１−ｎ  第ｎの比較器
２１１  インデックス変換部
２１２  制御部
２２１  記憶部
２２３  ＣＲビット
２２５  ダーティビット
２２７  有効フラグ
２２９  タグ部
２３１  インデックス部
２３３  データ部
【図１】
2016157278.tif 000003
【図２】
2016157278.tif 000004
【図３Ａ】
2016157278.tif 000005
【図３Ｂ】
2016157278.tif 000006
【図３Ｃ】
2016157278.tif 000007
【図３Ｄ】
2016157278.tif 000008
【図４Ａ】
2016157278.tif 000009
【図４Ｂ】
2016157278.tif 000010
【図４Ｃ】
2016157278.tif 000011
【図４Ｄ】
2016157278.tif 000012
【図５Ａ】
2016157278.tif 000013
【図５Ｂ】
2016157278.tif 000014
【図５Ｃ】
2016157278.tif 000015
【図５Ｄ】
2016157278.tif 000016
【図５Ｅ】
2016157278.tif 000017
【図５Ｆ】
2016157278.tif 000018
【図５Ｇ】
2016157278.tif 000019
【図５Ｈ】
2016157278.tif 000020
【図６Ａ】
2016157278.tif 000021
【図６Ｂ】
2016157278.tif 000022
【図６Ｃ】
2016157278.tif 000023
【図６Ｄ】
2016157278.tif 000024
【図６Ｅ】
2016157278.tif 000025