(57)【特許請求の範囲】
【請求項１】
主記憶に記憶しているデータを一時的に記憶するキャッシュ・メモリを備え、プロセッサが前記キャッシュ・メモリにアクセスするキャッシュ・メモリ・システムであって、
前記キャッシュ・メモリと前記主記憶との間で置き換えるデータのサイズを、前記キャッシュ・メモリ内の予め定めた大きさの複数の記憶空間毎に記憶するブロック・サイズ情報記憶手段を備え、
前記キャッシュ・メモリ内の前記記憶空間に対する前記プロセッサのアクセスがキャッシュ・ミスを起こした時に、
前記キャッシュ・メモリ内の前記キャッシュ・ミスを起こした前記記憶空間と前記主記憶との間で、
前記ブロック・サイズ情報記憶手段に記憶している前記サイズの中で、前記キャッシュ・ミスを起こした前記記憶空間に該当するブロック・サイズで、
データを置き換える手段を備えたキャッシュ・メモリ・システムにおいて、
前記プロセッサが出力するアクセス・アドレスは、タグ・アドレスとインデックス・アドレスとバンク・アドレスとバンク内オフセットの各フィールドを備え、
前記キャッシュ・メモリは少なくとも二つのキャッシュ・バンクから成り、
前記の各キャッシュ・バンクは、前記バンク内オフセットで指定する語数のデータを記憶するエレメントの集合から成るデータ・アレイと、前記データ・アレイの各エレメントに記憶しているデータが有効であるか否かを記憶する有効フラグの集合から成る有効フラグ・アレイと、前記データ・アレイの各エレメントに記憶しているデータの各タグ・アドレスを記憶するタグ・アレイを有し、
前記データ・アレイと前記有効フラグ・アレイと前記タグ・アレイとは、それぞれ、前記インデックス・アドレスによって指定された前記エレメントのデータと、当該データの有効フラグの値と、当該データのタグ・アドレスとを出力するものであり、
さらに前記の各キャッシュ・バンクは、前記有効フラグの値が前記エレメントに有効なデータを記憶していることを示すときに、前記タグ・アレイが出力したタグ・アドレスと前記アクセス・アドレス中のタグ・アドレスとを比較して比較結果を出力する比較器を備え、
前記バンク・アドレスによって指定された前記キャッシュ・バンクの比較器の比較結果を選択して出力する第１のマルチプレクサと、
前記キャッシュ・メモリ内の前記記憶空間毎の前記サイズを、前記インデックス・アドレスで参照する前記ブロック・サイズ情報記憶手段と、
前記キャッシュ・メモリと前記主記憶との間でデータを置き換える制御を行うメモリ・アクセス制御回路とを備え、
前記メモリ・アクセス制御回路が、前記プロセッサが前記アクセス・アドレスを出力した時に、前記第１のマルチプレクサの出力によってキャッシュ・ミスが起きたか否かを判定し、キャッシュ・ミスが起きた時には、前記メモリ・アクセス制御回路が、前記ブロック・サイズ情報記憶手段に記憶している前記サイズの中で、前記キャッシュ・ミスを起こした前記記憶空間に該当するブロック・サイズで、前記キャッシュ・ミスを起こした前記記憶空間と前記アクセス・アドレスによって指定された前記主記憶との間でデータを置き換えることを特徴とするキャッシュ・メモリ・システム。
【請求項２】
主記憶に記憶しているデータを一時的に記憶するキャッシュ・メモリを備え、プロセッサが前記キャッシュ・メモリにアクセスするキャッシュ・メモリ・システムであって、
前記キャッシュ・メモリと前記主記憶との間で置き換えるデータのサイズを、前記キャッシュ・メモリ内の予め定めた大きさの複数の記憶空間毎に記憶するブロック・サイズ情報記憶手段を備え、
前記キャッシュ・メモリ内の前記記憶空間に対する前記プロセッサのアクセスがキャッシュ・ミスを起こした時に、
前記キャッシュ・メモリ内の前記キャッシュ・ミスを起こした前記記憶空間と前記主記憶との間で、
前記ブロック・サイズ情報記憶手段に記憶している前記サイズの中で、前記キャッシュ・ミスを起こした前記記憶空間に該当するブロック・サイズで、
データを置き換える手段を備えたキャッシュ・メモリ・システムにおいて、
前記プロセッサが出力するアクセス・アドレスは、タグ・アドレスとインデックス・アドレスとバンク・アドレスとバンク内オフセットの各フィールドを備え、
前記キャッシュ・メモリは少なくとも二つのキャッシュ・バンクから成り、
前記の各キャッシュ・バンクは、前記バンク内オフセットで指定する語数のデータを記憶するエレメントの集合から成るデータ・アレイと、前記データ・アレイの各エレメントに記憶しているデータが有効であるか否かを記憶する有効フラグの集合から成る有効フラグ・アレイと、前記データ・アレイの各エレメントに記憶しているデータの各タグ・アドレスを記憶するタグ・アレイと、前記データ・アレイの各エレメントに記憶している各データが、それぞれ前記エレメントに読み込まれてから、これまでの間に前記プロセッサによって参照されたか否かを記憶するアクセス・ビットの集合から成るアクセス・ビット・アレイとを有し、
前記データ・アレイと前記有効フラグ・アレイと前記タグ・アレイと前記アクセス・ビット・アレイとは、それぞれ、前記インデックス・アドレスによって指定された前記エレメントのデータと、当該データの有効フラグの値と、当該データのタグ・アドレスと、当該データのアクセス・ビットの値とを出力するものであり、
さらに前記の各キャッシュ・バンクは、前記有効フラグの値が前記エレメントに有効なデータを記憶していることを示すときに、前記タグ・アレイが出力したタグ・アドレスと前記アクセス・アドレス中のタグ・アドレスとを比較して比較結果を出力する比較器を備え、
前記バンク・アドレスによって指定された、前記キャッシュ・バンクの比較器の比較結果を選択して出力する第１のマルチプレクサと、
前記インデックス・アドレスによって指定された、前記キャッシュ・メモリ内の前記記憶空間毎の前記サイズを出力する前記ブロック・サイズ情報記憶手段と、
前記の全てのキャッシュ・バンクの比較器が出力する比較結果と、前記の全てのキャッシュ・バンクのアクセス・ビットが出力する値とが入力されると、前記比較結果が一致しており、かつ、前記出力されたアクセス・ビットの値が前記プロセッサによって参照されたことを示す時に、当該キャッシュ・バンクを指す信号を出力するライン利用状況判定回路と、
前記インデックス・アドレスによって指定された前記キャッシュ・メモリ内の前記記憶空間の前記サイズと、前記バンク・アドレスと、前記ライン利用状況判定回路の出力とが入力されると、当該記憶空間の新たな前記サイズを決定するブロック・サイズ決定回路と、
前記キャッシュ・メモリと前記主記憶との間でデータを置き換える制御を行うメモリ・アクセス制御回路とを備え、
前記メモリ・アクセス制御回路が、前記プロセッサが前記アクセス・アドレスを出力した時に、前記第１のマルチプレクサの出力によってキャッシュ・ミスが起きたか否かを判定し、
キャッシュ・ミスが起きた時には、前記メモリ・アクセス制御回路が、前記ブロック・サイズ情報記憶手段に記憶している前記サイズの中で、前記キャッシュ・ミスを起こした前記記憶空間に該当するブロック・サイズで、前記キャッシュ・ミスを起こした前記記憶空間と前記アクセス・アドレスによって指定された前記主記憶との間でデータを置き換え、
前記ブロック・サイズ決定回路が、前記ブロック・サイズ情報記憶手段に記憶する前記サイズを更新することを特徴とするキャッシュ・メモリ・システム。
【請求項３】
前記ブロック・サイズ情報記憶手段は、前記キャッシュ・メモリ内の各エレメント毎に前記サイズを記憶し、前記バンク・アドレスによって指定されたキャッシュ・バンクの前記サイズを選択して出力する第２のマルチプレクサを有し、
前記メモリ・アクセス制御回路が、キャッシュ・ミスが起きた時には、前記第２のマルチプレクサが出力した前記サイズで、前記キャッシュ・ミスを起こした前記記憶空間と前記アクセス・アドレスによって指定された前記主記憶との間でデータを置き換えることを特徴とする請求項１または２記載のキャッシュ・メモリ・システム。
【請求項４】
前記ブロック・サイズ情報記憶手段は、
前記主記憶に書き戻したデータの、タグ・アドレスを記憶する第２のタグ・アレイと前記サイズを記憶するテーブルとを備え、
前記インデックス・アドレスで前記第２のタグ・アレイと前記テーブルとを参照すると前記タグ・アドレスと前記サイズとが出力され、前記第２のタグ・アレイが出力したタグ・アドレスと前記アクセス・アドレス中のタグ・アドレスとを比較して比較結果を出力する第２の比較器と、
前記の全てのキャッシュ・バンクのタグ・アレイの出力から、前記第２のタグ・アレイに入力するタグ・アドレスを前記バンク・アドレスで選択するタグ選択回路とを具備し、
前記メモリ・アクセス制御回路は、
キャッシュ・ミスが起きた時に、前記第２の比較器による、前記アクセス・アドレスのタグ・アドレスと前記第２のタグ・アレイが出力したタグ・アドレスとの比較結果が一致していれば、前記インデックス・アドレスで指定される前記テーブルに記憶している前記サイズで、前記主記憶に書き戻したデータを再度キャッシュ・メモリに読み込み、
前記タグ選択回路で選択されたタグ・アドレスと、前記キャッシュ・ミスを起こした前記インデックス・アドレスによって指定される、前記キャッシュ・メモリ内の前記記憶空間に該当する前記サイズとを、それぞれ前記第２のタグ・アレイと前記テーブルとに記憶する構成としたことを特徴とする請求項２記載のキャッシュ・メモリ・システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、キャッシュ・メモリを有する半導体回路において、キャッシュ・メモリと主記憶との間でデータを置き換える回数を低減するためのキャッシュ・メモリ・システムに関する。
【０００２】
【従来の技術】
従来のキャッシュ・メモリ・システムは図１１のような構成をしている。
キャッシュ・メモリ１００はデータを記憶するデータ・アレイ１０２を備え、プロセッサ１３０と主記憶１０６と接続している。データ・アレイ１０２と主記憶１０６との間で転送するデータのサイズは設計時に決定されており、このサイズに従って、メモリ・アクセス制御手段１１１が両者の間でデータを転送する。このように、従来のキャッシュ・メモリ・システムでは、主記憶１０６とキャッシュ・メモリ１００との間で転送するデータのサイズが任意の大きさに固定されていた。
なお、これ以降は、主記憶とキャッシュ・メモリとの間でデータを置き換える操作をリプレイスと呼び、置き換えるデータのサイズをブロック・サイズと呼ぶことにする。
【０００３】
ブロック・サイズが任意の値に固定されていると、プログラムの振舞いの特性次第ではリプレイスの回数が増加する場合が２通りある。
一つは、主記憶１０６からキャッシュ・メモリ１００に転送すべきデータの大きさに比べて、一度の転送でリプレイスできるブロック・サイズが小さい場合である。
このときは、プロセッサが必要とするデータを主記憶１０６からキャッシュ・メモリ１００に転送する回数と、不必要とするデータをキャッシュ・メモリ１００から主記憶１０６に転送する回数とが増加する。
なお、以降は、データを主記憶からキャッシュ・メモリに転送する操作をリプレイス・インと呼び、データをキャッシュ・メモリから主記憶に転送する操作をリプレイス・アウトと呼ぶことにする。
【０００４】
もう一つは、主記憶１０６からキャッシュ・メモリ１００に転送すべきデータの大きさに比べて、一度の転送でリプレイス・インできるブロック・サイズが大きい場合である。このときは、元来キャッシュ・メモリ１００内に記憶しておくべきデータを、キャッシュ・メモリ１００から主記憶１０６にリプレイス・アウトすべきデータと一緒にリプレイス・アウトする可能性がある。
そのため、元来キャッシュ・メモリ１００内に記憶しておくべきでありながらもリプレイス・アウトしたデータをプロセッサが参照しようとするときに、再度リプレイス・インする手間が生じる。
【０００５】
これらの問題を解決するために、特開昭６２−１１８４５６号公報や特開昭６３−１５７２４９号公報に記載されたような構成のキャッシュメモリが提案された。
いずれも、初期化時あるいはプログラム実行中に、命令等によってブロック・サイズを予め定めた一つの値に設定するものであった。
これにより、プログラム毎に異なる空間局所性の及ぶ範囲の違い、あるいは、ある一つのプログラムの実行中における空間局所性の及ぶ範囲の変化に対応して、ブロック・サイズを変更することが可能となった。
【０００６】
しかしながら、従来のコンピュータ・システムはプロセッサとキャッシュ・メモリとが別個のＬＳＩであったために、ＬＳＩのピン制約の理由から、プロセッサとキャッシュ・メモリとの間のデータ・バス幅を広く設計することが出来ず、データ・バス幅に比べてブロック・サイズを大きく設計していた。
しかし、データ・バス幅に比べてブロック・サイズを大きく設計することで、データ転送に要するクロック・サイクル数が増加する問題があった。
【０００７】
これらの問題を解決するために、可変ラインサイズ・キャッシュ・メモリ（情報処理学会アーキテクチャ研究会報告書、ＡＲＣ−１１９−２８、１９９６年８月）が提案された。
このキャッシュ・メモリは、プロセッサとキャッシュ・メモリと主記憶であるＤＲＡＭとを１つのＬＳＩに混載することを前提としており、キャッシュ・メモリと主記憶とをＬＳＩ内で直接接続するので、両者間を接続するデータ・バス幅を広く設計できることが特徴であった。さらに、ブロック・サイズをキャッシュ全体のモードとして、予め定めた一つの値に設定することが可能であった。
そのため、データ・バス幅に比べてブロック・サイズが小さい範囲では、データ転送に要するサイクルを増やすことなくブロック・サイズを設定することが可能となった。
【０００８】
【発明が解決しようとする課題】
一般に、キャッシュ・メモリは、一度アクセスされたデータが近い時間内に再度アクセスされる可能性が高い性質（時間局所性）と、アクセスされたデータの近傍のデータが間もなくアクセスされる可能性が高い性質（空間局所性）とを利用して、プロセッサが近い将来に参照する可能性の高いデータを記憶するための記憶装置である。
【０００９】
特に空間局所性に着目すると、空間局所性の及ぶ範囲がプログラム毎に異なるだけでなく、単一のプログラムであってもアドレス空間によって異なっている。これは、ある時間内において、互いに離れたアドレス空間に記憶している、大きさの異なる２つの配列の各要素に、それぞれ同じ回数だけアクセスする例を考えれば明らかである。すなわち、大きい方の配列が記憶される広いアドレス空間と、小さい方の配列が記憶される狭いアドレス空間とを比較すると、前者の方が空間局所性が高いと言える。
【００１０】
しかし、前述の提案されたアーキテクチャは、いずれもブロック・サイズをキャッシュ全体のモードとして一意に定めるだけなので、アドレス空間中における空間局所性の及ぶ範囲の違いに対応することは難しい。
設定されたブロック・サイズが適切でないと、前述したように不必要なリプレイスを起こす原因となる。
【００１１】
そこで、本発明が解決しようとする第１の課題は、アドレス空間中における空間局所性の及ぶ範囲の違いに対応するために、アドレス空間毎にブロック・サイズを適切に設定する手段を提供し、不必要なリプレイスの発生を抑えることである。
【００１２】
さらに、プログラムの実行が進むにつれて、同じアドレス空間に対するプロセッサの参照頻度が変化する。
この例としては、あるデータが、ある時間には頻繁に参照されていたものが、プログラムの実行が進むにつれて、稀に（あるいは、より頻繁に）アクセスされる場合などがある。
【００１３】
そこで、本発明が解決しようとする第２の課題は、プログラムの実行に伴う空間局所性の及ぶ範囲の変化に対応するために、第１の課題への対応に加えて、プログラムの実行中にアドレス空間毎にブロック・サイズを更新する手段を備えることにより、不必要なリプレイスの発生を抑えることである。
【００１４】
【課題を解決するための手段】
前記第１の課題を解決するため、本発明のキャッシュ・メモリ・システムは、主記憶に記憶しているデータを一時的に記憶するキャッシュ・メモリを備え、プロセッサが前記キャッシュ・メモリにアクセスするキャッシュ・メモリ・システムにおいて、前記キャッシュ・メモリと前記主記憶との間で置き換えるデータのサイズを、前記キャッシュ・メモリ内の予め定めた大きさの複数の記憶空間毎に記憶するブロック・サイズ情報記憶手段を備え、前記キャッシュ・メモリ内の前記記憶空間に対する前記プロセッサのアクセスがキャッシュ・ミスを起こした時に、前記キャッシュ・メモリ内の前記キャッシュ・ミスを起こした前記記憶空間と前記主記憶との間で、前記ブロック・サイズ情報記憶手段に記憶している前記サイズの中で、前記キャッシュ・ミスを起こした前記記憶空間に該当するブロック・サイズで、データを置き換える手段を備えたものである。
【００１５】
そして、請求項１の発明は、前記キャッシュ・メモリ・システムにおいて、前記プロセッサが出力するアクセス・アドレスは、タグ・アドレスとインデックス・アドレスとバンク・アドレスとバンク内オフセットの各フィールドを備え、前記キャッシュ・メモリは少なくとも二つのキャッシュ・バンクから成り、前記の各キャッシュ・バンクは、前記バンク内オフセットで指定する語数のデータを記憶するエレメントの集合から成るデータ・アレイと、前記データ・アレイの各エレメントに記憶しているデータが有効であるか否かを記憶する有効フラグの集合から成る有効フラグ・アレイと、前記データ・アレイの各エレメントに記憶しているデータの各タグ・アドレスを記憶するタグ・アレイを有し、前記データ・アレイと前記有効フラグ・アレイと前記タグ・アレイとは、それぞれ、前記インデックス・アドレスによって指定された前記エレメントのデータと、当該データの有効フラグの値と、当該データのタグ・アドレスとを出力するものであり、さらに前記の各キャッシュ・バンクは、前記有効フラグの値が前記エレメントに有効なデータを記憶していることを示すときに、前記タグ・アレイが出力したタグ・アドレスと前記アクセス・アドレス中のタグ・アドレスとを比較して比較結果を出力する比較器を備え、前記バンク・アドレスによって指定された前記キャッシュ・バンクの比較器の比較結果を選択して出力する第１のマルチプレクサと、前記キャッシュ・メモリ内の前記記憶空間毎の前記サイズを、前記インデックス・アドレスで参照する前記ブロック・サイズ情報記憶手段と、前記キャッシュ・メモリと前記主記憶との間でデータを置き換える制御を行うメモリ・アクセス制御回路とを備え、前記メモリ・アクセス制御回路が、前記プロセッサが前記アクセス・アドレスを出力した時に、前記第１のマルチプレクサの出力によってキャッシュ・ミスが起きたか否かを判定し、キャッシュ・ミスが起きた時には、前記メモリ・アクセス制御回路が、前記ブロック・サイズ情報記憶手段に記憶している前記サイズの中で、前記キャッシュ・ミスを起こした前記記憶空間に該当するブロック・サイズで、前記キャッシュ・ミスを起こした前記記憶空間と前記アクセス・アドレスによって指定された前記主記憶との間でデータを置き換えることを特徴とする。
【００１６】
また、前記第２の課題を解決する請求項２のキャッシュ・メモリ・システムは、前記キャッシュ・メモリ・システムにおいて、前記プロセッサが出力するアクセス・アドレスは、タグ・アドレスとインデックス・アドレスとバンク・アドレスとバンク内オフセットの各フィールドを備え、前記キャッシュ・メモリは少なくとも二つのキャッシュ・バンクから成り、前記の各キャッシュ・バンクは、前記バンク内オフセットで指定する語数のデータを記憶するエレメントの集合から成るデータ・アレイと、前記データ・アレイの各エレメントに記憶しているデータが有効であるか否かを記憶する有効フラグの集合から成る有効フラグ・アレイと、前記データ・アレイの各エレメントに記憶しているデータの各タグ・アドレスを記憶するタグ・アレイと、前記データ・アレイの各エレメントに記憶している各データが、それぞれ前記エレメントに読み込まれてから、これまでの間に前記プロセッサによって参照されたか否かを記憶するアクセス・ビットの集合から成るアクセス・ビット・アレイとを有し、前記データ・アレイと前記有効フラグ・アレイと前記タグ・アレイと前記アクセス・ビット・アレイとは、それぞれ、前記インデックス・アドレスによって指定された前記エレメントのデータと、当該データの有効フラグの値と、当該データのタグ・アドレスと、当該データのアクセス・ビットの値とを出力するものであり、さらに前記の各キャッシュ・バンクは、前記有効フラグの値が前記エレメントに有効なデータを記憶していることを示すときに、前記タグ・アレイが出力したタグ・アドレスと前記アクセス・アドレス中のタグ・アドレスとを比較して比較結果を出力する比較器を備え、前記バンク・アドレスによって指定された、前記キャッシュ・バンクの比較器の比較結果を選択して出力する第１のマルチプレクサと、前記インデックス・アドレスによって指定された、前記キャッシュ・メモリ内の前記記憶空間毎の前記サイズを出力する前記ブロック・サイズ情報記憶手段と、前記の全てのキャッシュ・バンクの比較器が出力する比較結果と、前記の全てのキャッシュ・バンクのアクセス・ビットが出力する値とが入力されると、前記比較結果が一致しており、かつ、前記出力されたアクセス・ビットの値が前記プロセッサによって参照されたことを示す時に、当該キャッシュ・バンクを指す信号を出力するライン利用状況判定回路と、前記インデックス・アドレスによって指定された前記キャッシュ・メモリ内の前記記憶空間の前記サイズと、前記バンク・アドレスと、前記ライン利用状況判定回路の出力とが入力されると、当該記憶空間の新たな前記サイズを決定するブロック・サイズ決定回路と、前記キャッシュ・メモリと前記主記憶との間でデータを置き換える制御を行うメモリ・アクセス制御回路とを備え、前記メモリ・アクセス制御回路が、前記プロセッサが前記アクセス・アドレスを出力した時に、前記第１のマルチプレクサの出力によってキャッシュ・ミスが起きたか否かを判定し、キャッシュ・ミスが起きた時には、前記メモリ・アクセス制御回路が、前記ブロック・サイズ情報記憶手段に記憶している前記サイズの中で、前記キャッシュ・ミスを起こした前記記憶空間に該当するブロック・サイズで、前記キャッシュ・ミスを起こした前記記憶空間と前記アクセス・アドレスによって指定された前記主記憶との間でデータを置き換え、前記ブロック・サイズ決定回路が、前記ブロック・サイズ情報記憶手段に記憶する前記サイズを更新することを特徴とする。
【００１７】
前記ブロック・サイズ情報記憶手段は、前記キャッシュ・メモリ内の各エレメント毎に前記サイズを記憶し、前記バンク・アドレスによって指定されたキャッシュ・バンクの前記サイズを選択して出力する第２のマルチプレクサを有し、前記メモリ・アクセス制御回路が、キャッシュ・ミスが起きた時には、前記第２のマルチプレクサが出力した前記サイズで、前記キャッシュ・ミスを起こした前記記憶空間と前記アクセス・アドレスによって指定された前記主記憶との間でデータを置き換える構成とすることができる。
【００１８】
前記ブロック・サイズ情報記憶手段は、前記主記憶に書き戻したデータの、タグ・アドレスを記憶する第２のタグ・アレイと前記サイズを記憶するテーブルとを備え、前記インデックス・アドレスで前記第２のタグ・アレイと前記テーブルとを参照すると前記タグ・アドレスと前記サイズとが出力され、前記第２のタグ・アレイが出力したタグ・アドレスと前記アクセス・アドレス中のタグ・アドレスとを比較して比較結果を出力する第２の比較器と、前記の全てのキャッシュ・バンクのタグ・アレイの出力から、前記第２のタグ・アレイに入力するタグ・アドレスを前記バンク・アドレスで選択するタグ選択回路とを具備し、前記メモリ・アクセス制御回路は、キャッシュ・ミスが起きた時に、前記第２の比較器による、前記アクセス・アドレスのタグ・アドレスと前記第２のタグ・アレイが出力したタグ・アドレスとの比較結果が一致していれば、前記インデックス・アドレスで指定される前記テーブルに記憶している前記サイズで、前記主記憶に書き戻したデータを再度キャッシュ・メモリに読み込み、前記タグ選択回路で選択されたタグ・アドレスと、前記キャッシュ・ミスを起こした前記インデックス・アドレスによって指定される、前記キャッシュ・メモリ内の前記記憶空間に該当する前記サイズとを、それぞれ前記第２のタグ・アレイと前記テーブルとに記憶する構成とすることができる。
【００１９】
【発明の実施の形態】
以下、本発明のブロック・サイズを変更可能なキャッシュ・メモリ・システムの実施の形態について、図１から図１０を参照しながら説明する。
【００２０】
［第１の実施の形態］
図１は、本発明のブロック・サイズを変更可能なキャッシュ・メモリと、キャッシュ・メモリと接続する主記憶とプロセッサとを示す、第１の実施の形態を示すブロック図である。
第１の実施の形態において、キャッシュ・メモリ・システムはキャッシュ・メモリ１００と、メモリ・アクセス制御手段１１１と、ブロック・サイズ情報記憶手段１０９とで構成される。
このブロック・サイズ情報記憶手段１０９は、キャッシュ・メモリ１００内にあるデータ・アレイ１０２を予め定めた大きさを単位として分割した、複数の記憶空間毎にブロック・サイズを記憶している。
【００２１】
さらに、キャッシュ・メモリ１００は、プロセッサ１３０と主記憶１０６と接続している。
プロセッサ１３０は、アクセス・アドレスによってキャッシュ・メモリ１００を参照する。
プロセッサ１３０によるキャッシュ・メモリ１００の参照がキャッシュ・ミスを起こしたときには、メモリ・アクセス制御手段１１１が、アクセス・アドレスによってブロック・サイズ情報記憶手段１０９からリプレイスするデータのブロック・サイズを読み出し、キャッシュ・メモリ１００と主記憶１０６との間でデータをリプレイスする。
【００２２】
キャッシュ・メモリ１００がダイレクト・マップ方式の場合は、キャッシュ・メモリ１００内の任意の記憶空間には、主記憶１００内においてタグ・アドレスが異なりインデックス・アドレスが等しい個々のデータが、互いに排他的に記憶される。よって、この第１の実施の形態に示すように、ブロック・サイズ情報記憶手段１０９がキャッシュ・メモリ内の任意の記憶空間毎にブロック・サイズを記憶することで、アドレス空間中における空間局所性の及ぶ範囲の違いに対応したブロック・サイズの設定を行うことができる。
なお、キャッシュ・メモリ１００がセット・アソシアティブ方式の場合においても、ブロック・サイズ情報記憶手段１０９がキャッシュ・メモリ内の任意の記憶空間毎にブロック・サイズを記憶することで、アドレス空間中における空間局所性の及ぶ範囲の違いに対応したブロック・サイズの設定を行うことができる。
【００２３】
［第２の実施の形態］
図２に示す第２の実施の形態において、プロセッサ１３０が出力するアクセス・アドレスでキャッシュ・メモリ１００を参照する。アクセス・アドレスは、タグ・アドレスと、インデックス・アドレスと、バンク・アドレスと、バンク内オフセットの各フィールドを備えている。
また、キャッシュ・メモリ１００は、データ・アレイ１０２−１〜１０２−４と、有効フラグ・アレイ１０５−１〜１０５−４と、タグ・アレイ１０３−１〜１０３−４と、比較器１０４−１〜１０４−４とから成る複数のキャッシュ・バンク１０１−１〜１０１−４で構成されている。
【００２４】
データ・アレイ１０２−１〜１０２−４は、アクセスアドレスの一部である、バンク内オフセットで指定する語数を単位として、各バンク毎に、それぞれデータを記憶している。
有効フラグ・アレイ１０５−１〜１０５−４は、データ・アレイ１０２−１〜１０２−４に記憶している各データが、それぞれ有効であるか否かを記憶している。
タグ・アレイ１０３−１〜１０３−４は、データ・アレイ１０２−１〜１０２−４に記憶している各データの、それぞれのタグ・アドレスを記憶している。
データ・アレイ１０２−１〜１０２−４と、有効フラグ・アレイ１０５−１〜１０５−４と、タグ・アレイ１０３−１〜１０３−４とは、インデックス・アドレスによって指定され、プロセッサからアクセスされると、それぞれが記憶している値を出力する。
バンク・アドレスで指定されたキャッシュ・バンクの比較器は、当該キャッシュ・バンクの有効フラグ・アレイの出力値が有効を示すときに、タグ・アレイが出力するタグ・アドレスと、アクセス・アドレス中のタグ・アドレスとを比較する。
【００２５】
さらに、比較器は、タグ・アレイが出力するタグ・アドレスとアクセス・アドレス中のタグ・アドレスとが一致したときにはキャッシュ・ヒットを示す信号を出力し、不一致、あるいは、バンク・アドレスで指定されたキャッシュ・バンクの有効フラグ・アレイの値が無効を示すときにはキャッシュ・ミス・ヒットを示す信号を出力する。
マルチプレクサ１１０は、バンク・アドレスで指定された比較器の出力値を選択して出力する。
【００２６】
メモリ・アクセス制御回路１１１は、マルチプレクサ１１０の出力値によってキャッシュ・ミスが起きたか否かを判断する。キャッシュ・ミスが起きたときは、メモリ・アクセス制御回路１１１が、ブロック・サイズ情報記憶部１０９に記憶しているブロック・サイズに従って、キャッシュ・メモリ１００と主記憶１０６との間でデータをリプレイスする。
キャッシュ・ヒットしたときは、メモリ・アクセス制御回路１１１はリプレイスしない。
実施の形態２を示す例では、主記憶１０６は４個のメモリ・バンク１０６−１〜１０６−４で構成され、前記各キャッシュ・バンク１０１−１〜１０１−４と前記各メモリ・バンク１０６−１〜１０６−４とが、それぞれ接続されている。
【００２７】
図３は、実施の形態２におけるキャッシュ・メモリ１００内のデータ・アレイ１０２−１〜１０２−４と主記憶１０６との接続を示している。
この例では、キャッシュ・メモリ１００と主記憶１０６は、いずれも４つのバンクから成っている。データ・アレイはバンク・アドレスによって指定される。各データ・アレイはキャッシュ・ライン・エレメントと呼ぶ記憶要素の集合であり、キャッシュ・ライン・エレメント内のデータに対する参照は、バンク内オフセットを用いて行う。キャッシュ・ラインは、インデックス・アドレスが共通するキャッシュ・ライン・エレメントの集合として定義される。図３では、各キャッシュ・ライン・エレメントは３２バイトのデータを記憶する例を示している。
一方、主記憶１０６の各メモリ・バンク１０６−１〜１０６−４は、メモリ・ライン・エレメントと呼ぶ記憶要素の集合である。
【００２８】
同一アクセス・アドレス中のタグ・アドレスとインデックス・アドレスとで参照するメモリ・ライン・エレメントの集合をメモリ・ラインと呼ぶ。図３では、同一メモリ・ライン内において最も左のバンク・アドレスが最下位となるアドレシングの例を示している。
ブロック・サイズとキャッシュ・ラインの大きさとは必ずしも一致しないので、任意のキャッシュ・ラインには、同一のメモリ・ラインのデータ同士を記憶する場合もあれば、異なるメモリ・ラインのデータ同士を記憶する場合もある。
【００２９】
この実施の形態２を示す例では、ブロック・サイズ情報記憶部１０９が、まず、各キャッシュ・ライン毎にブロック・サイズを記憶するブロック・サイズ情報テーブル１１２を持つ例について説明する。
キャッシュ・ミスが起きたときに、ブロック・サイズ情報テーブル１１２に記憶したブロック・サイズでリプレイスが実行される。ブロック・サイズ情報テーブル１１２には、プログラムの実行前に、予め見積もっておいたブロック・サイズを記憶しておく。各キャッシュ・ライン毎に任意の大きさのブロック・サイズを設定することが可能である。この実施の形態２では、ブロック・サイズとして大（キャッシュ・ライン全体の大きさ）、中（同一キャッシュ・ライン内で、偶数番地のバンク・アドレスから連続する２個のキャッシュ・ライン・エレメント分）、小（１つのキャッシュ・ライン・エレメント分）の異なる３つが存在する例について説明する。
【００３０】
ブロック・サイズ情報テーブル１１２の任意のキャッシュ・ラインに該当するフィールドに、ブロック・サイズが大と設定された場合、プロセッサの当該キャッシュ・ライン内の、いずれかのキャッシュ・ライン・エレメントへのアクセスがキャッシュ・ミスを起こすと、当該キャッシュ・ライン全体がリプレイスの対象になる。
ブロック・サイズが中と設定された場合、キャッシュ・ミスを起こしたアクセスのバンク・アドレスによってリプレイスの対象になるキャッシュ・ライン・エレメントが異なる。
【００３１】
キャッシュ・バンクが４つに分割される実施の形態２の例では２とおりがある。
一つはキャッシュ・バンク１０１−１または１０１−２へのアクセスがキャッシュ・ミスを起こした場合で、このときは、キャッシュ・バンク１０１−１と１０１−２のキャッシュ・ライン・エレメントがリプレイスの対象になる。
もう一つは、キャッシュ・バンク１０１−３または１０１−４へのアクセスがキャッシュ・ミスを起こした場合で、このときは、キャッシュ・バンク１０１−３と１０１−４のキャッシュ・ライン・エレメントがリプレイスの対象になる。
最後に、ブロック・サイズが小であると設定された場合には、キャッシュ・ミスを起こしたキャッシュ・ライン・エレメントのみがリプレイスの対象になる。
このように、キャッシュ・ライン毎にブロック・サイズを設定する方式を採ることで、アドレス空間中における空間局所性の及ぶ範囲の違いに対応したブロック・サイズの設定を簡易に行いながら、不必要なリプレイスの発生を抑えることができる。
【００３２】
前述の第２の実施の形態の説明では、特定の実施例を挙げたが、これに限定されるものではなく、次に挙げる実施例とすることもできる。
（１）前述のキャッシュ・メモリ・システムがダイレクト・マップ方式を採る場合の例のほか、セット・アソシアティブ方式を採る場合でも、ブロック・サイズ情報テーブル１１２の各フィールドに設定したブロック・サイズをウェイ間で共用することで、本発明の、データのブロック・サイズを変更可能なキャッシュ・メモリ・システムを実現できる。
【００３３】
（２）前述のキャッシュ・ライン・エレメントの語長が３２バイトの例のほか、異なるサイズでもバンク内オフセットに割り当てる語長を変更することで、本発明の、データのブロック・サイズを変更可能なキャッシュ・メモリ・システムを実現することができる。
【００３４】
（３）前述のキャッシュ・メモリが、４つのバンクから成る例のほか、バンク数が異なる場合でも、バンク・アドレスに割り当てる語長を変更することで、本発明の、データのブロック・サイズを変更可能なキャッシュ・メモリ・システムを実現することができる。
【００３５】
（４）前述のブロック・サイズの種類が３つである場合のほか、ブロック・サイズの種類が３つ以外でも、リプレイスの対象となるキャッシュ・ライン・エレメントの組合せを変更することで、また、ブロック・サイズの種類が３つである場合でも、リプレイスの対象となるキャッシュ・ライン・エレメントの組合せを変更することで、本発明の、データのブロック・サイズを変更可能なキャッシュ・メモリ・システムを実現することができる。
【００３６】
（５）前述のキャッシュ・メモリ１００の各キャッシュ・バンクが、前述の主記憶の各メモリ・バンクと、それぞれ直接にデータ・バスで接続している例のほか、キャッシュ・メモリ１００と主記憶１０６との間を接続するデータ・バスの幅が前述の例より狭い場合においても、マルチプレクサとデ・マルチプレクサとをデータ・バスのインタフェースに設けることで、本発明の、データのブロック・サイズを変更可能なキャッシュ・メモリ・システムを実現できる。
【００３７】
（６）前述の主記憶とキャッシュ・メモリのバンク数が等しい例のほか、互いのバンク数が異なっても、データ線をマルチプレクスあるいはデ・マルチプレクスすることで、本発明の、データのブロック・サイズを変更可能なキャッシュ・メモリ・システムを実現することができる。
【００３８】
（７）前述のブロック・サイズ情報記憶部１０９が、キャッシュ・ライン毎にブロック・サイズを記憶するブロック・サイズ情報テーブル１１２を持つ場合のほか、任意の複数個のキャッシュ・ライン毎に共通のブロック・サイズを設定しても、本発明の、データのブロック・サイズを変更可能なキャッシュ・メモリ・システムを実現できる。図４に、２つのキャッシュ・ライン毎にブロック・サイズを共有するブロック・サイズ情報テーブル２１２を持つ例を示す。このように、ブロック・サイズをキャッシュ・ライン間で共有することで設定の粒度が大きくなるので、アドレス空間中における空間局所性の及ぶ範囲の違いに細かく対応することが困難になるが、ブロック・サイズ情報テーブルの容量が小さくて済むので、ハードウェア量を削減する効果がある。
【００３９】
［第３の実施の形態］
図５は、本発明のブロック・サイズを変更可能なキャッシュ・メモリと、キャッシュ・メモリと接続する主記憶とプロセッサとを示す、第３の実施の形態を示すブロック図である。
図５に示すように、ブロック・サイズ情報記憶部１０９が、キャッシュ・ライン・エレメント毎にブロック・サイズを記憶しているブロック・サイズ情報テーブル３１２−１〜３１２−４を持つ。
【００４０】
さらに、キャッシュ・ミスが起きたバンクのブロック・サイズをバンク・アドレスによって選択する第２のマルチプレクサ１１７を具備し、選択されたブロック・サイズをメモリ・アクセス制御回路１１１に入力している点が第２の実施の形態と異なる。その他の構成は第２の実施の形態と同様であるので同一の符号を付して説明を省略する。
【００４１】
この第３の実施の形態の特徴は、キャッシュ・ミスが起きたキャッシュ・ライン・エレメントに設定されたブロック・サイズが、リプレイス時のデータ転送のサイズとして用いられることである。ブロック・サイズをキャッシュ・ライン・エレメント毎に設定することで、アドレス空間中における空間局所性の及ぶ範囲の違いに細かく対応することができる。
【００４２】
第２の実施の形態と異なる点は、同一のキャッシュ・ライン内において互いに異なるブロック・サイズが設定され得ることである。リプレイス時には、キャッシュ・ミスが起きたキャッシュ・バンクのブロック・サイズ情報テーブルに設定されたブロック・サイズが使用され、他のキャッシュ・ライン・エレメントに記憶しているブロック・サイズは使用されない。
このように、ブロック・サイズ情報テーブルの容量が増えハードウェア量が増加するが、アドレス空間中における空間局所性の及ぶ範囲の違いに細かく対応することができるため、元来リプレイスを行う必要のないデータをリプレイスすることを抑える効果が高まる。
【００４３】
なお、図５が示す第３の実施の形態では、全てのキャッシュ・バンク毎にブロック・サイズ情報テーブルを設ける例を示しているが、複数のキャッシュ・バンク毎にブロック・サイズ情報テーブルを共有しても良い。このとき、ブロック・サイズ情報テーブルの数を１つまで縮退すると、第２の実施の形態と同様になる。
また、第２の実施の形態における任意の複数個のキャッシュ・ライン毎に共通のブロック・サイズを設定する方法と組み合わせ、各バンク毎に、任意の複数個のキャッシュ・ライン毎にブロック・サイズを共有し、ブロック・サイズ情報テーブルの容量を削減しても良い。
【００４４】
［第４の実施の形態］
図６は、本発明のブロック・サイズを変更可能なキャッシュ・メモリと、キャッシュ・メモリと接続する主記憶の全体構成を示す、第４の実施の形態を示すブロック図である。
図６に示すように、アクセス・ビット・アレイ１０５−１〜１０５−４と、ライン利用状況判定回路１０７と、ブロック・サイズ決定回路１０８とを備える点が第２の実施の形態と異なる。その他の構成は第２の実施の形態と同様であるので、同一の符号を付して説明を省略する。
【００４５】
アクセス・ビット・アレイ１０５−１〜１０５−４は、データ・アレイ１０２−１〜１０２−４の各キャッシュ・ライン・エレメントに記憶しているデータが、それぞれ当該キャッシュ・ライン・エレメントに読み込まれてから、これまでの間にプロセッサ１３０によってアクセスされたか否かを記憶するものである。ライン利用状況判定回路１０７は、同一のキャッシュ・ライン内において、現在プロセッサ１３０がアクセスしているキャッシュ・ライン・エレメントとは別のキャッシュ・ライン・エレメントの中で、キャッシュ・ライン・エレメントが有効であり、かつ、親データのタグ・アドレスと等しいタグ・アドレスを持つデータを記憶しており、かつ、当該データがリプレイス・インされてから、これまでの間にアクセスされたキャッシュ・ライン・エレメントを判定するものである。
この判定は、ライン利用状況判定回路１０７に比較器１０４−１〜１０４−４の出力とアクセス・ビット・アレイ１０５−１〜１０５−４の出力とを入力して、その論理積をキャッシュ・バンク毎に求めることで行うことができる。
【００４６】
なお、これ以降では、現在プロセッサ１３０によってアクセスされているキャッシュ・ライン・エレメントが記憶しているデータを親データと呼び、ライン利用状況判定回路１０７によって、データがリプレイス・インしてから、これまでの間にアクセスされたと判断されたキャッシュ・ライン・エレメントに記憶しているデータの中で、親データ以外のデータを子データと呼ぶことにする。
もし、親データと子データの関係にある各データが同一キャッシュ・ライン内に存在しているならば、両者は既に同一ブロックとして取り扱われているか、または、将来同一ブロックとして取り扱われる可能性がある。
ただし、親データと同一キャッシュ・ライン内で他のキャッシュ・ライン・エレメントに記憶しているデータのタグ・アドレスが、親データのタグ・アドレスと一致したとしても、当該データが一度もアクセスされていないならば、当該データは子データと判定されない。
【００４７】
ブロック・サイズ決定回路１０８は、親データが属するキャッシュ・バンクをバンク・アドレスによって判断し、さらに、ライン利用状況判定回路１０７の出力により親データと子データの関係にある全てのキャッシュ・ライン・エレメントを判断し、これに並行して、親データが属するキャッシュ・ラインの現在のブロック・サイズをブロック・サイズ情報記憶部１０９から得て、親データが属するキャッシュ・ラインの新たなブロック・サイズを決定し、ブロック・サイズ情報記憶テーブル１１２を更新する。
【００４８】
ブロック・サイズ決定回路１０８がブロック・サイズを決定するアルゴリズムは次のとおりである。
ブロック・サイズを決定する方法は２つあり、第１の方法は親データと子データの総数と位置関係とに基づいて決定するもので、第２の方法は親データと子データの総数だけで決定するものである。
【００４９】
第１の方法では、親データと子データの総数に加えて、両者の位置関係によりブロック・サイズが決定される。
ここで、キャッシュのバンク数が４で、ブロック・サイズの種類として第２の実施の形態で説明した３種類が存在し、最も左のバンクのバンク・アドレスが０番地となるようにアドレスを割り当てる例を用いて説明する。
まず、現在のブロック・サイズが小のときには、親データと子データとが偶数番地のバンク・アドレスから上位の番地に連続する２個以上のキャッシュ・ライン・エレメントに記憶されているときにブロック・サイズを拡大する。
【００５０】
次に、現在のブロック・サイズが中のときには、親データと子データの総数が４個であればブロック・サイズを拡大する。
一方、親データだけのとき、または、親データと子データとが隣接しないとき、または、親データと子データとが奇数番地のバンク・アドレスから上位の番地に２個だけ連続するときにはブロック・サイズを縮小する。
最後に、現在のブロック・サイズが大のときには、親データと子データの総数が２以下のときにブロック・サイズを縮小する。
各ブロック・サイズにおいて、該当しない条件のときにはブロック・サイズを変更しない。
【００５１】
このように、親データと子データの総数に加えて両者の位置関係を用いることで、ブロック・サイズを適切に設定することができる。
なお、第１の方法を説明する上記の例以外にも、ブロック・サイズを変更するか否かを決める閾値となる親データと子データの総数と、各データの位置関係を変更することでブロック・サイズを更新する条件を適宜変更することができる。第２の方法では、親データと子データの総数が予め定めた数よりも大きければブロック・サイズが拡大され、一方、予め定めた数よりも小さければブロック・サイズが縮小される。
【００５２】
ここで、キャッシュのバンク数が４で、ブロック・サイズの種類として第２の実施の形態で説明した３種類がある場合を例に挙げて説明する。
まず、現在のブロック・サイズが小のときには、親データと子データの総数が２個以上であればブロック・サイズを拡大する。
次に、現在のブロック・サイズが中のときには、親データと子データの総数が４個であればブロック・サイズを拡大し、親データだけであれば縮小する。
最後に、現在のブロック・サイズが大のときには、親データと子データの総数が２個以下であれば縮小する。
各ブロック・サイズにおいて、該当しない条件のときにはブロック・サイズを変更しない。
このように、親データと子データの総数だけを用いることで、ブロック・サイズの決定を簡易に行うことができる。
【００５３】
なお、第２の方法を説明する上記の例以外にも、ブロック・サイズを変更するか否かを決める閾値となる親データと子データの総数を変更することで、ブロック・サイズを更新する条件を適宜変更することができる。
さらに、第１または第２の方法では、キャッシュ・バンクの数の増減に関わらず、閾値となる親データと子データの総数と、それらの位置関係を適宜設定することで、ブロック・サイズを変更できる。
また、第１または第２の方法では、キャッシュ・バンクの数の増減に関わらず、閾値となる親データと子データの総数と、それらの位置関係を適宜設定することでブロック・サイズの種類を変更できる。
【００５４】
さらに、ブロック・サイズの変化を段階的に行うか否かについて２つの方法があり、第３の方法は現在の親データのブロック・サイズを基に新たなブロック・サイズを決定するもので、第４の方法は現在の親データのブロック・サイズに関わらずに新たなブロック・サイズを決定するものである。
【００５５】
ここで、キャッシュのバンク数が４で、ブロック・サイズの種類として第２の実施の形態で説明した３種類がある場合を例に挙げて説明する。
第３の方法では、ブロック・サイズが大から中へ、または、中から小へと段階的に更新し、大から小へといった非連続な変化を行わない。
これにより、空間局所性が及ぶ範囲が大きく異なるデータに稀にアクセスすることによるブロック・サイズの急激な変化を防ぎ、リプレイスに要するサイクル数を平均化することで、プロセッサの処理性能を安定させることができる。
【００５６】
一方、第４の方法では、現在のブロック・サイズに無関係に、新たなブロック・サイズを決定するので、小から大へ、または、大から小への変更も起き得る。現在のブロック・サイズを用いないために、新たなブロック・サイズを簡易に決定することができる。
なお、第３または第４の方法では、ブロック・サイズの数の増減に関わらず、いずれのブロック・サイズを更新する方法を採ることができる。
【００５７】
ここまでの第１の手法または第２の手法と、第３の手法または第４の手法とを任意に組み合せることで、ブロック・サイズを決定するアルゴリズムとして４通りがある。
また、ブロック・サイズ決定回路１０８がブロック・サイズを更新する時期として、全てのメモリ参照時、キャッシュにヒットした参照時のみ、キャッシュにミス・ヒットした参照時のみなどがある。
さらに、これらの４通りの手法に対して、ブロック・サイズの更新に過去の参照履歴を利用するか否かを組み合わせても良い。過去の参照履歴を利用するとは、ブロック・サイズを更新するきっかけとなる事象の発生回数を累算し、累算した値が予め定めた値になったときにブロック・サイズを更新するものである。
【００５８】
例えば、ブロック・サイズ情報記憶テーブル１１２のブロック・サイズを記憶する個々のフィールド毎に初期値を０とするカウンタを持たせ、ブロック・サイズ決定回路１０８が、任意のフィールドのブロック・サイズを大きくすると判断したときに当該カウンタがインクリメントされ、ブロック・サイズを小さくすると判断したときに当該カウンタがデクリメントされる。このようにして、カウンタの値が予め定めた値を越えたときに、当該キャッシュ・エレメントのブロック・サイズを大きくし、カウンタの値が予め定めた値を下回ったときにブロック・サイズを小さくする。
このようにすることで、例外処理などの稀な処理を行うことによるブロック・サイズの急激な変化を抑える効果が高まる。
【００５９】
なお、リセット直後のコールド・スタート時等において、キャッシュ・メモリに初めてデータをリプレイス・インする時のブロック・サイズとしては、予め定めた所定のブロック・サイズを用いれば良い。
このように、プログラムの実行中にブロック・サイズ情報記憶テーブル１１２に記憶するブロック・サイズを随時更新することで、時間の経過に伴って変化する空間局所性の及ぶ範囲の変化に対応することが可能となり、不必要なリプレイスの発生を抑えることができる。
【００６０】
ここで、この第４の実施の形態を説明する例では、ブロック・サイズ情報記憶部１０９が、キャッシュ・ライン毎にブロック・サイズを記憶するブロック・サイズ情報テーブル１１２を持っていたが、任意の複数個のキャッシュ・ライン毎に共通のブロック・サイズを設定しても同様である。
図７に、２つのキャッシュ・ライン毎にブロック・サイズを共有するブロック・サイズ情報テーブル２１２を持つ例を示す。
【００６１】
このように、ブロック・サイズをキャッシュ・ライン間で共有することで設定の粒度が大きくなるので、アドレス空間中における空間局所性の及ぶ範囲の違いに細かく対応することが困難になるが、ブロック・サイズ情報テーブルの容量が小さくて済むので、ハードウェア量を削減する効果がある。
【００６２】
前述の第４の実施の形態の説明では、特定の実施例を挙げたが、これに限定されるものではなく、次に挙げる実施例とすることもできる。
【００６３】
（１）前述のキャッシュ・メモリ・システムがダイレクト・マップ方式を採る場合の例のほか、セット・アソシアティブ方式を採る場合でも、ブロック・サイズ情報テーブル１１２の各フィールドに設定したブロック・サイズをウェイ間で共用することで、本発明の、データのブロック・サイズを変更可能なキャッシュ・メモリ・システムを実現できる。
【００６４】
（２）前述のキャッシュ・ライン・エレメントの語長が３２バイトの例のほか、異なるサイズでもバンク内オフセットに割り当てる語長を変更することで、本発明の、データのブロック・サイズを変更可能なキャッシュ・メモリ・システムを実現することができる。
【００６５】
（３）前述のキャッシュ・メモリが、４つのバンクから成る例のほか、バンク数が異なる場合でも、バンク・アドレスに割り当てる語長を変更することで、本発明の、データのブロック・サイズを変更可能なキャッシュ・メモリ・システムを実現することができる。
【００６６】
（４）前述のブロック・サイズの種類が３つである場合のほか、ブロック・サイズの種類が３つ以外でも、リプレイスの対象となるキャッシュ・ライン・エレメントの組合せを変更することで、また、ブロック・サイズの種類が３つである場合でも、リプレイスの対象となるキャッシュ・ライン・エレメントの組合せを変更することで、本発明の、データのブロック・サイズを変更可能なキャッシュ・メモリ・システムを実現することができる。
【００６７】
（５）前述のキャッシュ・メモリ１００の各キャッシュ・バンクが、前述の主記憶の各メモリ・バンクと、それぞれ直接にデータ・バスで接続している例のほか、キャッシュ・メモリ１００と主記憶１０６との間を接続するデータ・バスの幅が前述の例より狭い場合においても、マルチプレクサとデ・マルチプレクサとをデータ・バスのインタフェースに設けることで、本発明の、データのブロック・サイズを変更可能なキャッシュ・メモリ・システムを実現できる。
【００６８】
（６）前述の主記憶とキャッシュ・メモリのバンク数が等しい例のほか、互いのバンク数が異なっても、データ線をマルチプレクスあるいはデ・マルチプレクスすることで、本発明の、データのブロック・サイズを変更可能なキャッシュ・メモリ・システムを実現することができる。
【００６９】
（７）前述のブロック・サイズ情報記憶部１０９が、キャッシュ・ライン毎にブロック・サイズを記憶するブロック・サイズ情報テーブル１１２を持つ場合のほか、任意の複数個のキャッシュ・ライン毎に共通のブロック・サイズを設定しても、本発明の、データのブロック・サイズを変更可能なキャッシュ・メモリ・システムを実現できる。図４に、２つのキャッシュ・ライン毎にブロック・サイズを共有するブロック・サイズ情報テーブル２１２を持つ例を示す。このように、ブロック・サイズをキャッシュ・ライン間で共有することで設定の粒度が大きくなるので、アドレス空間中における空間局所性の及ぶ範囲の違いに細かく対応することが困難になるが、ブロック・サイズ情報テーブルの容量が小さくて済むので、ハードウェア量を削減する効果がある。
【００７０】
［第５の実施の形態］
図８は、本発明のブロック・サイズを変更可能なキャッシュ・メモリと、キャッシュ・メモリと接続する主記憶とプロセッサとを示す、第５の実施の形態を示すブロック図である。
【００７１】
図８に示すように、ブロック・サイズ情報記憶部１０９が、キャッシュ・ライン・エレメント毎にブロック・サイズを記憶しているブロック・サイズ情報テーブル３１２−１〜３１２−４を持つ。
さらに、キャッシュ・ミスが起きたバンクのブロック・サイズをバンク・アドレスによって選択する第２のマルチプレクサ１１７と、更新しようとするブロック・サイズ情報テーブル３１２−１〜３１２−４をバンク・アドレスによって選択するデ・マルチプレクサとを具備している点が第４の実施の形態と異なる。
その他の構成は第４の実施の形態と同様であるので、同一の符号を付して説明を省略する。
【００７２】
この第５の実施の形態の特徴は、第３の実施の形態と同様にキャッシュ・ミスが起きたキャッシュ・ライン・エレメントに設定されたブロック・サイズが、リプレイス時のデータ転送のサイズとして用いられることである。ブロック・サイズをキャッシュ・ライン・エレメント毎に設定することで、アドレス空間中における空間局所性の及ぶ範囲の違いに細かく対応することができる。
第５の実施の形態と異なる点は、第３の実施の形態と同様に同一のキャッシュ・ライン内において互いに異なるブロック・サイズが設定され得ることである。リプレイス時には、キャッシュ・ミスが起きたキャッシュ・バンクのブロック・サイズ情報テーブルに設定されたブロック・サイズが使用され、他のキャッシュ・ライン・エレメントに記憶しているブロック・サイズは使用されない。
【００７３】
このように、キャッシュ・ライン・エレメント毎にブロック・サイズを設定することで、ブロック・サイズ情報テーブルの容量が増えハードウェア量が増加するが、アドレス空間中における空間局所性の及ぶ範囲の違いに細かく対応することができるため、元来リプレイスを行う必要のないデータをリプレイスすることを抑える効果が高まる。
なお、図８が示す第５の実施の形態では、全てのキャッシュ・バンク毎にブロック・サイズ情報テーブルを設ける例を示しているが、複数のキャッシュ・バンク毎にブロック・サイズ情報テーブルを共有しても良い。このとき、ブロック・サイズ情報テーブルの数を１つまで縮退すると、第４の実施の形態と同様になる。
なお、第４の実施の形態における任意の複数個のキャッシュ・ライン毎に共通のブロック・サイズを設定する方法と組み合わせ、各バンク毎に、任意の複数個のキャッシュ・ライン毎にブロック・サイズを共有し、ブロック・サイズ情報テーブルの容量を削減しても良い。
【００７４】
［第６の実施の形態］
図９は、本発明のブロック・サイズの変更可能なキャッシュ・メモリと、キャッシュ・メモリと接続する主記憶の全体構成を示す第６の実施の形態を示すブロック図である。
【００７５】
基本的には図６に示す第４の実施の形態と同様であるが、ブロック・サイズ情報記憶部１０９が、キャッシュ・ライン毎にブロック・サイズを記憶するヒストリ・テーブル１１３と、ヒストリ・テーブル１１３に記憶したブロック・サイズに該当するキャッシュ・ラインのタグ・アドレスを記憶する第２のタグ・アレイ１１９と、アクセス・アドレス中のタグ・アドレスと第２のタグ・アレイ１１９の出力を比較する第２の比較器１２０とを備え、さらに、アクセス・アドレス中のバンク・アドレスによって第２のタグ・アレイ１１９に入力するタグ・アドレスを選択する、タグ選択回路１１４とを具備し、データを主記憶にリプレイス・アウトする場合に、キャッシュ・ライン全体がリプレイス・アウトの対象となる点が、第４の実施の形態と異なる。
その他の構成は図６に示す第４の実施の形態と同様であるので、同一の符号を付して説明を省略する。
【００７６】
この第６の実施の形態では、データを主記憶にリプレイス・アウトするときに、タグ選択回路１１４が選択したキャッシュ・バンクのタグ・アドレスを第２のタグ・アレイ１１９に記憶し、主記憶にリプレイス・アウトするデータのブロック・サイズをヒストリ・テーブル１１３に記憶する。
データを主記憶からキャッシュ・メモリにリプレイス・インするときには、当該データが過去にキャッシュ・メモリから主記憶にリプレイス・アウトされた時にヒストリ・テーブル１１３に記憶した、当該データのブロック・サイズが、現在もヒストリ・テーブル１１３内に記憶されているか否かを調べる。
【００７７】
これは、アクセス・アドレスのインデックス・アドレスとタグ・アドレスとを用い、キャッシュ・メモリ中に記憶しているデータを検索する方法と同様の方法で実現することができる。つまり、アクセス・アドレス中のインデックス・アドレスでヒストリ・テーブル１１３と第２のタグ・アレイとを検索し、アクセス・アドレス中のタグ・アドレスと第２のタグ・アレイが出力したタグ・アドレスとが一致した場合、当該データのブロック・サイズがヒストリ・テーブルに記憶されていると判断する。当該データのブロック・サイズがヒストリ・テーブル１１３に記憶されていた場合には、メモリ・アクセス制御回路１１１が、そのブロック・サイズでデータをリプレイス・インする。当該データのブロック・サイズがヒストリ・テーブルに記憶されていない場合には、予め定めた所定のブロック・サイズで、当該データを含むメモリ・ラインのデータをキャッシュ・メモリにリプレイス・インする。
【００７８】
なお、この第６の実施の形態を説明する例では、リプレイス・アウトするときに、キャッシュ・ミスを起こしたキャッシュ・ライン全体をリプレイス・アウトしていたが、ダーティになっているキャッシュ・ライン・エレメントのデータのみをリプレイス・アウトしても良い。これは、更新されていないキャッシュ・ライン・エレメントのデータをリプレイス・アウトする必要はないからである。
【００７９】
また、この第６の実施の形態を説明する例では、ブロック・サイズ情報記憶部１０９が、キャッシュ・ライン毎にブロック・サイズを記憶するブロック・サイズ情報テーブル１１２を持っていたが、任意の複数個のキャッシュ・ライン毎に共通のブロック・サイズを設定しても同様である。図１０に、２つのキャッシュ・ライン毎にブロック・サイズを共有するブロック・サイズ情報テーブル２１２を持つ例を示す。
【００８０】
このように、ブロック・サイズをキャッシュ・ライン間で共有することで設定の粒度が大きくなるので、アドレス空間中における空間局所性の及ぶ範囲の違いに細かく対応することが困難になるが、ブロック・サイズ情報テーブルの容量が小さくて済むので、ハードウェア量を削減する効果がある。
【００８１】
【発明の効果】
以上に述べたように、本発明によれば下記の効果を奏する。
（１）第１の課題を解決するための、第１の実施の形態によれば、キャッシュ・メモリと主記憶との間でリプレイスするデータのブロック・サイズをキャッシュ・メモリ内の任意の記憶空間毎に設定する手段を設けることで、アドレス空間中における空間局所性の及ぶ範囲の違いに対応してブロック・サイズを設定することが可能となり、不必要なリプレイスの発生を抑えることができる。
【００８２】
（２）特に、第２または第３の実施の形態によれば、キャッシュ・メモリと主記憶との間でリプレイスするデータのブロック・サイズをキャッシュ・メモリ内の任意の記憶空間毎に設定する手段を設け、プログラムの実行前に解析しておいた記憶空間毎のブロック・サイズを設定することで、アドレス空間中における空間局所性の及ぶ範囲の違いに対応してブロック・サイズを設定することを実現する。
【００８３】
（３）第２の課題を解決するための、第４または第５または第６の実施の形態によれば、キャッシュ・メモリと主記憶との間でリプレイスするデータのブロック・サイズをキャッシュ・メモリ内の任意の記憶空間毎に設定する手段と、このブロック・サイズを設定する手段に設定するブロック・サイズを、キャッシュ・メモリに記憶しているデータに対してプロセッサが参照した履歴を基に決定する手段とを設けて、随時ブロックサイズを更新することで、プログラムの実行に伴う空間局所性の及ぶ範囲の変化に対応することが可能となる。
【図面の簡単な説明】
【図１】  本発明のブロック・サイズを変更可能なキャッシュ・メモリの概念を示す、第１の実施の形態のブロック図である。
【図２】  本発明のブロック・サイズを変更可能なキャッシュ・メモリの、キャッシュ・ライン毎にブロック・サイズを設定する第２の実施の形態を示すブロック図である。
【図３】  本発明におけるアドレッシングを示すブロック図である。
【図４】  本発明のブロック・サイズを変更可能なキャッシュ・メモリの第２の実施の形態を基に、複数のキャッシュ・ライン毎にブロック・サイズを設定する形態に変更した例を示すブロック図である。
【図５】  本発明のブロック・サイズを変更可能なキャッシュ・メモリの、キャッシュ・ライン・エレメント毎にブロックサイズを設定する第３の実施の形態を示すブロック図である。
【図６】  本発明のブロック・サイズを変更可能なキャッシュ・メモリの、キャッシュ・ライン毎にブロック・サイズを更新可能な第４の実施の形態を示すブロック図である。
【図７】  本発明のブロック・サイズを変更可能なキャッシュ・メモリの、第４の実施の形態を基に、複数のキャッシュ・ライン毎にブロック・サイズを更新可能な形態に変更した例を示すブロック図である。
【図８】  本発明のブロック・サイズを変更可能なキャッシュ・メモリの、キャッシュ・ライン・エレメント毎にブロック・サイズを更新可能な第５の実施の形態を示すブロック図である。
【図９】  本発明のブロック・サイズを変更可能なキャッシュ・メモリにおいて、第４の実施の形態を基に、キャッシュ・メモリから主記憶にリプレイス・アウトしたデータのブロック・サイズを記憶する手段を設け、当該データをリプレイス・インするときに当該ブロック・サイズに従って行うことを特徴とする第６の実施の形態を示すブロック図である。
【図１０】  本発明のブロック・サイズを変更可能なキャッシュ・メモリにおいて、第６の実施の形態を基に、複数のキャッシュ・ライン毎にブロック・サイズを更新可能な形態に変更した例を示すブロック図である。
【図１１】  従来のキャッシュ・メモリの実施例を示すブロック図である。
【符号の説明】
１００  キャッシュ・メモリ
１０１−１〜１０１−４  キャッシュ・バンク
１０２−１〜１０２−４  データ・アレイ
１０３−１〜１０３−４  タグ・アレイ
１０４−１〜１０４−４  比較器
１０５−１〜１０５−４  有効フラグ・アレイ
１０６  主記憶
１０６−１〜１０６−４  メモリ・バンク
１０７  ライン利用状況判定回路
１０８  ブロック・サイズ決定回路
１０９  ブロック・サイズ情報記憶部
１１０  第１のマルチ・プレクサ
１１１  メモリ・アクセス制御回路
１１２、２１２、３１２−１〜３１２−４  ブロック・サイズ情報テーブル
１１３  ヒストリ・テーブル
１１４  タグ選択回路
１１６−１〜１１６−４  アクセス・ビット・アレイ
１１７  第２のマルチプレクサ
１１８  デ・マルチプレクサ
１１９  第２のタグ・アレイ
１２０  第２の比較器
１３０  プロセッサ
【図１】
0004071886.tif 000002
【図２】
0004071886.tif 000003
【図３】
0004071886.tif 000004
【図４】
0004071886.tif 000005
【図５】
0004071886.tif 000006
【図６】
0004071886.tif 000007
【図７】
0004071886.tif 000008
【図８】
0004071886.tif 000009
【図９】
0004071886.tif 000010
【図１０】
0004071886.tif 000011
【図１１】
0004071886.tif 000012