(57)【要約】【課題】ウェイの数を変更可能な場合に、ウェイの数を変更するか否かの判定を自動的に行えるようにする。【解決手段】情報処理装置が、セットアソシアティブ方式でデータを記憶する記憶部と、前記セットアソシアティブ方式の行毎に前記行に含まれる記憶領域のうち少なくとも１つの領域にデータが格納されたか否かを示す使用履歴フラグと、前記行毎に前記行でデータの追い出しが行われたか否かを示すリプレースフラグと、前記使用履歴フラグの値及び前記リプレースフラグの値に基づいて、前記セットアソシアティブ方式におけるウェイの数を増やすか否かを決定するウェイ拡張指示部と、前記ウェイ拡張指示部が前記ウェイの数を増やすことに決定した場合、前記ウェイの数を増やすウェイ拡張部と、を備える。【選択図】図５
2018133038.tif 000002
【特許請求の範囲】
【請求項１】
セットアソシアティブ方式でデータを記憶する記憶部と、
前記セットアソシアティブ方式の行毎に前記行に含まれる記憶領域のうち少なくとも１つの領域にデータが格納されたか否かを示す使用履歴フラグと、
前記行毎に前記行でデータの追い出しが行われたか否かを示すリプレースフラグと、
前記使用履歴フラグの値及び前記リプレースフラグの値に基づいて、前記セットアソシアティブ方式におけるウェイの数を増やすか否かを決定するウェイ拡張指示部と、
前記ウェイ拡張指示部が前記ウェイの数を増やすことに決定した場合、前記ウェイの数を増やすウェイ拡張部と、
を備える情報処理装置。
【請求項２】
前記ウェイ拡張部は、前記セットアソシアティブ方式の行数を半分にし、前記ウェイの数を２倍にする、請求項１に記載の情報処理装置。
【請求項３】
前記ウェイ拡張部は、前記セットアソシアティブ方式の行のうち、前記使用履歴フラグが、前記領域にデータが格納されたことを示す行と、前記リプレースフラグが、前記データの追い出しが行われたことを示す行とを１つの行に纏める、
請求項１または請求項２に記載の情報処理装置。
【請求項４】
セットアソシアティブ方式でデータを記憶する記憶部の前記セットアソシアティブ方式の行毎に、前記行に含まれる記憶領域のうち少なくとも１つの領域にデータが格納されたか否かを示す使用履歴フラグの値と、前記行毎に、前記行でデータの追い出しが行われたか否かを示すリプレースフラグの値とに基づいて、前記セットアソシアティブ方式におけるウェイの数を増やすか否かを決定するウェイ拡張指示部と、
前記ウェイ拡張指示部が前記ウェイの数を増やすことに決定した場合、前記ウェイの数を増やすウェイ拡張部と、
を備える制御装置。
【請求項５】
セットアソシアティブ方式でデータを記憶する記憶部の前記セットアソシアティブ方式の行毎に、前記行に含まれる記憶領域のうち少なくとも１つの領域にデータが格納されたか否かを示す使用履歴フラグの値と、前記行毎に、前記行でデータの追い出しが行われたか否かを示すリプレースフラグの値とに基づいて、前記セットアソシアティブ方式におけるウェイの数を増やすか否かを決定し、
前記ウェイの数を増やすことに決定した場合、前記ウェイの数を増やす、
制御方法。
【請求項６】
セットアソシアティブ方式でデータを記憶する記憶部を制御するコンピュータに、
前記セットアソシアティブ方式の行毎に、前記行に含まれる記憶領域のうち少なくとも１つの領域にデータが格納されたか否かを示す使用履歴フラグの値と、前記行毎に、前記行でデータの追い出しが行われたか否かを示すリプレースフラグの値とに基づいて、前記セットアソシアティブ方式におけるウェイの数を増やすか否かを決定させ、
前記ウェイの数を増やすことに決定した場合、前記ウェイの数を増やさせる、
ためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、制御装置、制御方法及びプログラムに関する。
【背景技術】
【０００２】
キャッシュメモリの制御に関連して幾つかの技術が提案されている。
例えば、特許文献１には、ストアバッファ部からストアデータを追い出す制御が簡単になるストア制御装置が示されている。このストア制御装置は、プロセッサからブロック単位のストアデータを受け取ってストアバッファ部に格納し、連続する複数のブロックであるライン単位でストアバッファ部から主記憶装置へストアデータを追い出す。ストアデータを追い出す際、ストア制御装置は、ライン内の全てのブロックがストアバッファ部内に存在するウェイ（ｗａｙ）を優先してストアデータを追い出す。
【０００３】
このようなストア制御装置で、ウェイの数が不足する場合にも対応することができれば更に好ましい。
この点に関して、特許文献２には、セットアソシアティブ方式でセット数及びウェイ数を変更可能なキャッシュシステムが示されている。このキャッシュシステムは、ｉ組のｍウェイｎセットのキャッシュアレイを備え、セットの選択とウェイの選択とを制御することで、セット数及びウェイ数を変更する。ｉ、ｍ、ｎは、いずれも２の乗数であってもよい。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１４−０５２７５４号公報
【特許文献２】特開２００５−２９３３００号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
特許文献２に記載のキャッシュシステムのようにウェイの数を変更可能な場合に、ウェイの数を変更するか否かの判定を自動的に行えることが更に好ましい。
【０００６】
本発明は、上述の課題を解決することのできる情報処理装置、制御装置、制御方法及びプログラムを提供することを目的としている。
【課題を解決するための手段】
【０００７】
本発明の第１の態様によれば、情報処理装置は、セットアソシアティブ方式でデータを記憶する記憶部と、前記セットアソシアティブ方式の行毎に前記行に含まれる記憶領域のうち少なくとも１つの領域にデータが格納されたか否かを示す使用履歴フラグと、前記行毎に前記行でデータの追い出しが行われたか否かを示すリプレースフラグと、前記使用履歴フラグの値及び前記リプレースフラグの値に基づいて、前記セットアソシアティブ方式におけるウェイの数を増やすか否かを決定するウェイ拡張指示部と、前記ウェイ拡張指示部が前記ウェイの数を増やすことに決定した場合、前記ウェイの数を増やすウェイ拡張部と、を備える。
【０００８】
本発明の第２の態様によれば、制御装置は、セットアソシアティブ方式でデータを記憶する記憶部の前記セットアソシアティブ方式の行毎に、前記行に含まれる記憶領域のうち少なくとも１つの領域にデータが格納されたか否かを示す使用履歴フラグの値と、前記行毎に、前記行でデータの追い出しが行われたか否かを示すリプレースフラグの値とに基づいて、前記セットアソシアティブ方式におけるウェイの数を増やすか否かを決定するウェイ拡張指示部と、前記ウェイ拡張指示部が前記ウェイの数を増やすことに決定した場合、前記ウェイの数を増やすウェイ拡張部と、を備える。
【０００９】
本発明の第３の態様によれば、制御方法は、セットアソシアティブ方式でデータを記憶する記憶部の前記セットアソシアティブ方式の行毎に、前記行に含まれる記憶領域のうち少なくとも１つの領域にデータが格納されたか否かを示す使用履歴フラグの値と、前記行毎に、前記行でデータの追い出しが行われたか否かを示すリプレースフラグの値とに基づいて、前記セットアソシアティブ方式におけるウェイの数を増やすか否かを決定し、前記ウェイの数を増やすことに決定した場合、前記ウェイの数を増やすことを含む。
【００１０】
本発明の第４の態様によれば、プログラムは、セットアソシアティブ方式でデータを記憶する記憶部を制御するコンピュータに、前記セットアソシアティブ方式の行毎に、前記行に含まれる記憶領域のうち少なくとも１つの領域にデータが格納されたか否かを示す使用履歴フラグの値と、前記行毎に、前記行でデータの追い出しが行われたか否かを示すリプレースフラグの値とに基づいて、前記セットアソシアティブ方式におけるウェイの数を増やすか否かを決定させ、前記ウェイの数を増やすことに決定した場合、前記ウェイの数を増やさせるためのプログラムである。
【発明の効果】
【００１１】
この発明によれば、ウェイの数を変更可能な場合に、ウェイの数を変更するか否かの判定を自動的に行うことができる。
【図面の簡単な説明】
【００１２】
【図１】本発明の実施形態に係る情報処理装置の構成例を示す概略構成図である。
【図２】同実施形態に係る中央処理装置が出力するリクエストのデータ構造の例を示す図である。
【図３】同実施形態に係るマージ回路の構成例を示す概略構成図である。
【図４】同実施形態に係るマージ処理されたストアデータの例を示す図である。
【図５】同実施形態に係るストアバッファの構成例を示す概略構成図である。
【図６】同実施形態に係るアドレスアレイが記憶するデータのデータ構造の例を示す図である。
【図７】同実施形態に係るエントリフル検出回路の構成例を示す図である。
【図８】同実施形態に係る追い出し制御回路が追い出し指示信号を生成する際の生成規則の例を示す図である。
【図９】同実施形態に係るロード時における情報処理装置の動作の第１例を示す図である。
【図１０】同実施形態に係るロード時における情報処理装置の動作の第２例を示す図である。
【図１１】同実施形態に係るストアバッファがストアデータを記憶する場合の情報処理装置の処理手順の例を示す図である。
【図１２】同実施形態に係るストアバッファがストアリクエストの追い出し処理を行う場合の情報処理装置の処理手順の例を示す図である。
【図１３】同実施形態に係るストアバッファがアドレスアレイ及びデータアレイのウェイを拡張する処理手順の例を示す図である。
【図１４】同実施形態に係る使用履歴フラグ及びリプレースフラグの値の第１例を示す図である。
【図１５】同実施形態に係るウェイ拡張後のアドレスアレイの構成の第１例を示す図である。
【図１６】同実施形態に係る使用履歴フラグ及びリプレースフラグの値の第２例を示す図である。
【図１７】同実施形態に係るウェイ拡張後のアドレスアレイの構成の第２例を示す図である。
【図１８】本発明に係る情報処理装置の最小構成の例を示す図である。
【図１９】本発明に係る制御装置の最小構成の例を示す図である。
【発明を実施するための形態】
【００１３】
以下、本発明の実施形態を説明するが、以下の実施形態は請求の範囲にかかる発明を限定するものではない。また、実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
図１は、本発明の実施形態に係る情報処理装置の構成例を示す概略構成図である。図１に示すように、情報処理装置１０は、中央処理装置（Central Processing Unit）１と、マージ回路２と、ストアバッファ３と、エントリフル検出回路４と、追い出し制御回路５と、主記憶装置６と、を備える。
【００１４】
中央処理装置１は、マージ回路２及び主記憶装置６と接続されている。中央処理装置１は、ストアリクエスト及びストアデータをマージ回路２へ出力する。ストアリクエストは、ストアデータの主記憶装置６への書き込みを要求する命令である。
また、中央処理装置１は、マージ回路２を介して主記憶装置６へロードリクエストを出力し主記憶装置６よりロードデータを受け取る。ロードリクエストは、主記憶装置６からのデータの読み出しを要求する命令である。ロードデータは、ロードリクエストに応じて主記憶装置６から読み出されたデータである。
以下では、ストアリクエストとロードリクエストとを総称してリクエストと表記する。
【００１５】
中央処理装置１がストアリクエストにて出力するストアデータのデータ長は、主記憶装置６がロードリクエストに応じて出力するロードデータのデータ長よりも短い。以下では、中央処理装置１が出力するストアデータのデータ長が８バイト（Ｂ）であり、主記憶装置６が出力するロードデータのデータ長が１２８バイトである場合を例に説明する。但し、中央処理装置１が出力するストアデータのデータ長、主記憶装置６が出力するロードデータのデータ長のいずれも、特定のデータ長に限定されない。中央処理装置１が出力するストアデータのデータ長が、主記憶装置６が出力するロードデータのデータ長よりも短ければよい。さらに、主記憶装置６が出力するロードデータのデータ長が、中央処理装置１が出力するストアデータのデータ長の整数倍であることが好ましいが、これに限らない。
以下では、データ長が、主記憶装置６が出力するロードデータのデータ長であるデータをラインと称する。また、ラインのデータ長をライン長と称する。
【００１６】
図２は、中央処理装置１が出力するリクエスト（ストアリクエスト及びロードリクエスト）のデータ構造の例を示す図である。図２に示すように、中央処理装置１が出力するリクエストは、コマンドとアドレスとを含む。
コマンドは、主記憶装置６に対して指示する動作を示す。具体的には、コマンドは、ロード又はストアの何れかの動作指示を示す。
【００１７】
アドレスは、主記憶装置６におけるアドレスを示す。ロードリクエストの場合、アドレス欄には主記憶装置６がロードデータを読み出すべき位置を示すアドレスが格納される。ストアデータの場合、アドレス欄には、主記憶装置６がストアデータを格納すべき位置を示すアドレスが格納される。
リクエストのアドレスは、上位アドレス、中位アドレス、下位アドレスの３つに分けることができる。
【００１８】
後述するように、ストアバッファ３はセットアソシアティブ（Set Associative）方式でストアデータを記憶しており、中位アドレスは、セットアソシアティブにおけるインデックス（Index）として用いられる。すなわち、中位アドレスは、セットアソシアティブにおける行と一対一に対応付けられる。
上位アドレスは、セットアソシアティブにおけるタグ（Tag）として用いられる。すなわち、上位アドレスは、セットアソシアティブで１つの行にウェイ（Way）の数だけ含まれる記憶領域を区別するために用いられる。
【００１９】
上位アドレスと中位アドレスとの組み合わせで、主記憶装置６の記憶領域における位置をライン単位で指定することができ、下位アドレスは、ライン内での位置を示す。
ストアバッファ３及び主記憶装置６は、データをライン単位で処理するため、下位アドレスを無視する。一方、上記のように、中央処理装置１はラインよりも小さい単位でストアデータを出力する。マージ回路２は、中央処理装置１が出力したストアデータをラインにマージ（Merge）する際、ストアデータをライン上で位置合わせするために下位アドレスを用いる。
【００２０】
マージ回路２は、中央処理装置１及びストアバッファ３と接続されている。マージ回路２は、中央処理装置１が出力したリクエストをストアバッファ３へ出力する。
中央処理装置１がストアリクエストを出力した場合、マージ回路２は、ストアデータをストアバッファ３が記憶しているデータにマージする。
ここで、ストアバッファ３および主記憶装置６がライン単位でデータの入出力を行うのに対し、上記のようにストアデータはライン長よりも短い。そこで、ストアデータを格納すべきアドレスを含むラインをストアバッファ３が記憶している場合、マージ回路２は、このラインをストアバッファ３から読み出す。そして、マージ回路２は、読み出したラインのうち、ストアリクエストのアドレスで指定される位置にストアデータを書き込む。マージ回路２は、ストアデータを書き込んだラインをストアバッファ３へのストアリクエストにて出力し、ストアバッファ３は、マージ回路２へ読み出したラインをマージ回路２が出力したラインに置き換える（上書きする）。
【００２１】
図３は、マージ回路２の構成例を示す概略構成図である。図３の例で、マージ回路２は、シフタ２０１と、マージャ２０２とを備える。
シフタ２０１は、ライン内のアドレスを示す下位アドレスに従ってストアデータのシフト処理を行う。これにより、シフタ２０１は、中央処理装置１が出力したストアデータのラインにおける位置合わせを行う。
【００２２】
マージャ２０２は、ライン単位のストアデータ内の該当領域のデータを更新する。すなわち、マージャ２０２は、シフタ２０１による位置合わせに基づいて、中央処理装置１が出力したストアデータを、ストアバッファ３が記憶しているライン単位のストアデータにマージする。
マージャ２０２は、マージされたライン単位のストアデータをストアバッファ３へ出力する。ストアバッファ３は、マージャ２０２が出力したライン単位のストアデータを、マージ前のストアデータ読出元の記憶領域へ上書きする。
【００２３】
図４は、マージ処理されたストアデータの例を示す図である。図４の例で、中央処理装置１は、ストアリクエストと共に８バイトのストアデータを出力する。これに対して主記憶装置６は、主記憶装置６自らの記憶領域を１２８バイト毎に分割したラインを、データの入出力を行う際の単位としている。
中央処理装置１が主記憶装置６に対して２４バイトのデータのストアを要求する場合、中央処理装置１は、この２４バイトのデータを、図４のストアデータ１、２及び３のように８バイト毎に分割し、３つのストアリクエストを出力する。このストアデータ１、２及び３は元々連続するデータであり、主記憶装置６において同一のラインに格納されるべきデータとなる。
【００２４】
仮に、ストアバッファ３が中央処理装置１からストアリクエストを受け取る毎に、主記憶装置６からライン単位でデータを読み出し、ストアリクエストを反映させたライン単位のデータを書き戻すと、主記憶装置６からのデータ読出と、主記憶装置６へのデータ書込とを、それぞれ３回行う必要がある。
これに対し、ストアバッファ３が、主記憶装置６からライン単位でデータを読み出し、図４に示すように、中央処理装置１からの３つのストアリクエストを全て反映させたデータを生成し、生成したデータを書き戻すようにすれば、主記憶装置６からのデータ読出と、主記憶装置６へのデータ書込とが、それぞれ１回で済む。そこで、ストアバッファ３は、主記憶装置６から読み出したデータに中央処理装置１からのストアリクエストを反映させた後、直ちに主記憶装置６へストアリクエストの出力を行わずにストアバッファ３自らに一旦蓄える。同一ラインのストアの場合、マージ回路２がマージ処理を行う。ストアバッファ３は、追い出しの要因となる事象が発生した場合に主記憶装置６にストアリクエストを出力する。
【００２５】
ストアバッファ３は、マージ回路２、エントリフル検出回路４、追い出し制御回路５及び主記憶装置６と接続されている。ストアバッファ３は、主記憶装置６のキャッシュメモリとして機能し、主記憶装置６へのストアデータをセットアソシアティブ方式で記憶する。
ロードリクエストを取得した場合、ストアバッファ３は、ロードリクエストとストアバッファ３内のストアリクエストとのアドレス比較を行う。アドレスが一致した場合、ストアバッファ３は、一致したアドレスのストアデータを読み出してストアリクエストと共に主記憶装置６へ出力する。また、ストアバッファ３は、ストアデータを読み出してマージ回路２へ出力し、マージ回路２の出力であるマージ後のストアデータをストアバッファ３の元の格納場所へ格納する。更に、ストアバッファ３は、ストアバッファ３内のデータ格納状況を示すエントリ情報をエントリフル検出回路４へ出力する。また、ストアバッファ３は、追い出し制御回路５の指示に従ってストアデータを主記憶装置６へ出力する。
【００２６】
図５は、ストアバッファ３の構成例を示す概略構成図である。図５において、ストアバッファ３は、アドレスアレイ３０１と、データアレイ３０２と、アドレス差替回路３０３と、アドレス選択回路３０４と、レジスタ３０５と、エントリ選択回路３０６と、アレイ制御回路３０７及び３０８と、使用履歴フラグレジスタ３０９と、リプレース（Replace）フラグレジスタ３１０と、ウェイ拡張指示回路３１１とを備える。
【００２７】
アドレスアレイ３０１と、データアレイ３０２との組み合わせは、セットアソシアティブ方式の記憶装置を構成し、ストアリクエスト及びストアデータを一時的に記憶する。アドレスアレイ３０１及びデータアレイ３０２は、記憶部の例に該当する。
アドレスアレイ３０１は、ストアリクエストのアドレス及びストアデータのマージ状態を記憶する。
【００２８】
図６は、アドレスアレイ３０１が記憶するデータのデータ構造の例を示す図である。図６に示すように、アドレスアレイ３０１は、アドレス＋有効バイト情報の形式のデータを記憶する。
ここで有効バイト情報とは、ライン単位のストアデータのうちマージ済みの部分の位置を８バイト単位で示す情報である。ここでの８バイトは、中央処理装置１からのストアデータのデータ長の例である。
【００２９】
例えばマージ回路２がストアバッファ３における１２８バイトのストアデータに対して８バイト単位でマージを行う場合、有効バイト情報として１６（＝１２８÷８）ビットを用いてマージ済みの８バイトを「１」で示す。ここでの１２８バイトは、ライン長の例である。
有効バイト情報が１６ビット全て「１」である場合、ラインのマージ完了を表す。ラインのマージが完了している場合、マスキング等の処理を行う必要無しにこのラインを主記憶装置６に格納させることができる。
【００３０】
アドレスアレイ３０１の記憶領域は、ｍ行×ｎ列（ｍ、ｎは正整数）の領域に分割され、１つの領域に１つのアドレスが格納される。アドレスアレイ３０１の各行はストアリクエストにおける中位アドレス値と１対１に対応付けられており、ストアリクエストのアドレスは、その中位アドレス値に応じた行の記憶領域に格納される。各行はｎ個のアドレス格納領域を有するので、アドレスアレイ３０１は、中位アドレス値が同一かつ上位アドレスが異なるアドレスをｎ個まで記憶し得る。
以下では、アドレスアレイ３０１の各行、及び、データアレイ３０２の各行をエントリと称する。
【００３１】
アドレスアレイ３０１の領域のうち、有効なアドレス値が格納されていない領域には、アドレス値と区別可能な値が格納される。アドレス値と区別可能な値として、例えばマイナスの整数値を用いることができるが、これに限らない。アドレス値と区別可能な値により、その領域が空き領域であることが示される。ここでいう空き領域は、新たなデータを書込可能な領域である。
【００３２】
なお、ストアバッファ３は、主記憶装置６のラインに合わせてライン単位でデータの書込および読出を行う。このため、ストアバッファ３は、ストアリクエストの下位アドレスを無視する。すなわち、ストアバッファ３は、上位アドレス値および中位アドレス値が同一であれば、下位アドレス値が異なっていても同一のアドレス値として扱い、データの読出等の処理を行う。
【００３３】
データアレイ３０２は、ストアデータを記憶する。
データアレイ３０２の記憶領域も、アドレスアレイ３０１と同様に、ｍ行×ｎ列の領域に分割されている。データアレイ３０２の、各行はアドレスアレイ３０１の各行と１対１に対応付けられ、データアレイ３０２の各列はアドレスアレイの各列と１対１に対応付けられている。これにより、アドレスアレイ３０１とデータアレイ３０２とでｎウェイ（ｗａｙ）セットアソシアティブ方式の記憶装置を構成する。
【００３４】
アドレス差替回路３０３は、追い出し制御回路５が出力した追い出し指示信号を受けると、リクエストに示されるアドレスから追い出し指示信号に示されるアドレスへの差し替えを行う。
アドレス選択回路３０４は、アドレスアレイ３０１がウェイ毎に出力したアドレス値の何れかを、リクエストに示されるアドレスに基づいて選択する。アドレス選択回路３０４は、選択したアドレスに基づいて主記憶装置６に対するストアリクエストを生成し、主記憶装置６へ出力する。
【００３５】
レジスタ３０５は、ロードリクエストを一時的に記憶する。ロードリクエストと同一アドレスのエントリがアドレスアレイ３０１から追い出された際に、レジスタ３０５がロードリクエストを一時的に待たせることによりロードリクエストがストアリクエストを追い越すことを防止する。
エントリ選択回路３０６は、マージ回路２が出力したリクエスト、及び、追い出し制御回路５が出力した追い出し指示信号を受けて、ストアバッファ３の各部を制御する。
【００３６】
アレイ制御回路３０７及び３０８は、それぞれアドレスアレイ３０１及びデータアレイ３０２に対するストアリクエスト（アドレス値およびストアデータ）の読み出し及び書き込みの制御を行う。
具体的には、アレイ制御回路３０７は、リクエスト又は追い出し指示信号に含まれるアドレス値を読み出し、中位アドレス値に基づいてアドレスアレイ３０１の該当行を選択する。アレイ制御回路３０８は、リクエスト又は追い出し指示信号に含まれるアドレス値を読み出し、中位アドレス値に基づいてデータアレイ３０２の該当行を選択する。
【００３７】
ストアリクエストを読み出す場合、アレイ制御回路３０７は、選択した行の各領域のアドレス値を出力するようアドレスアレイ３０１を制御する。また、アレイ制御回路３０８は、選択した行の各領域のストアデータを出力するようデータアレイ３０２を制御する。
ストアリクエストを書き込む場合、アレイ制御回路３０７は、選択した行の領域のうち空き領域を選択し、選択した空き領域に図６に示されるデータを書き込む。また、アレイ制御回路３０８は、データアレイ３０２の領域のうち、アドレスを書き込んだアドレスアレイ３０１の領域と同じ行かつ同じ列の領域に、マージ回路２から出力されたストアデータを書き込む。
【００３８】
また、アレイ制御回路３０７は、アドレスアレイ３０１の行毎に、格納されているアドレスの数を計数し、計数結果と当該行を示すアドレス値とを含むエントリ情報を生成する。アレイ制御回路３０７は、生成したエントリ情報をエントリフル検出回路４へ出力する。アレイ制御回路３０７は、例えば所定周期毎にエントリ情報を生成し、エントリフル検出回路４へ出力する。
【００３９】
また、アレイ制御回路３０７及び３０８は、アドレスアレイ３０１及びデータアレイ３０２の記憶領域の構成制御を行う。具体的には、アレイ制御回路３０７及び３０８は、使用履歴フラグレジスタ３０９及びリプレースフラグレジスタ３１０の各情報に基づいて、アドレスアレイ３０１及びデータアレイ３０２の使用状態を判定する。アレイ制御回路３０７及び３０８は、判定結果に基づいてセットアソシアティブメモリにおける行数及び列数の変更を行う。例えば、アレイ制御回路３０７及び３０８は、ｍ行×ｎ列の記憶領域を（ｍ／２）行×２ｎ列などに読み替える。これにより、各アレイを２ｎウェイでｍ／２行の領域を持つ記憶領域として扱うことができる。
また、アレイ制御回路３０７及び３０８は、ウェイ拡張部の例に該当し、ウェイの数を増加させる。具体的には、アレイ制御回路３０７及び３０８は、ある行のウェイを、他のある行の既存のウェイに後続するウェイと読み替えることで、ウェイの数を増加させる。
【００４０】
使用履歴フラグレジスタ３０９は、アドレスアレイ３０１の行毎に１ビットのレジスタを有する。使用履歴フラグレジスタ３０９は、アドレスアレイ３０１の１つの行のｎ個の格納領域のいずれかにデータが格納された場合、対応するレジスタの値を「１」にする。一方、アドレスアレイ３０１の１つの行のｎ個の格納領域のいずれも使用されていない場合、使用履歴フラグレジスタ３０９は、対応するレジスタの値を「０」にする。
【００４１】
リプレースフラグレジスタ３１０は、アドレスアレイ３０１の行毎に１ビットのレジスタを有する。リプレースフラグレジスタ３１０は、アドレスアレイ３０１の１つの行のｎ個の格納領域が全てエントリで満たされた状態で中央処理装置１からストアリクエストが出力されてエントリの追い出しが発生した場合に、対応するレジスタの値を「１」にする。それ以外の場合、リプレースフラグレジスタ３１０は、レジスタの値を「０」にする。
【００４２】
ウェイ拡張指示回路３１１は使用履歴フラグレジスタ３０９及びリプレースフラグレジスタ３１０の各フラグを入力として、ウェイ拡張指示信号を生成しアレイ制御回路３０７及び３０８へ送出する。ウェイ拡張指示回路３１１は、ウェイ拡張指示部の例に該当する。
アレイ制御回路３０７及び３０８はウェイ拡張指示回路３１１よりウェイ拡張指示信号を受け付けると、アドレスアレイ３０１及びデータアレイ３０２の記憶領域を予め設定された行数及び列数に読み替えて各エントリを制御する。例えば、アレイ制御回路３０７及び３０８は、上記のようにｍ行×ｎ列の記憶領域を（ｍ／２）行×２ｎ列などに読み替える。
アドレスアレイ３０１及びデータアレイ３０２を制御する各部が、制御装置として構成されて情報処理装置１０に組み込まれていてもよい。特に、ウェイ拡張指示回路３１１と、アレイ制御回路３０７及び３０８とが制御装置に含まれて構成されていてもよい。
【００４３】
エントリフル検出回路４は、ストアバッファ３及び追い出し制御回路５と接続されている。エントリフル検出回路４は、ストアバッファ３よりエントリ情報を受け取ってエントリフルの判定を行う。エントリフルと判定した場合、エントリフル検出回路４は、エントリフル情報を追い出し制御回路５へ出力する。
後述するように、ここでいうエントリは、ストアバッファ３が備えるセットアソシアティブ方式の記憶装置の行である。ここでいうエントリ情報は、セットアソシアティブ方式の記憶装置の１つの行に格納されているアドレスの数を示す情報である。ここでのアドレスの数は、１つの行に格納されているライン単位のストアデータの数を示す。ここでのエントリフルは、１つの行に含まれるウェイ数分の記憶領域のいずれにもデータが格納されていることである。
【００４４】
図７は、エントリフル検出回路４の構成例を示す図である。図７の例で、エントリフル検出回路４は、レジスタ４０１と、比較回路４０２とを備える。
レジスタ４０１は、ストアバッファ３のウェイ数（アドレスアレイ３０１の列数）を予め記憶している。
比較回路４０２は、ストアバッファ３が出力するエントリ情報に示される、アドレスアレイ３０１の各行に記憶されているアドレス数（ストアリクエスト数）と、レジスタ４０１の記憶するウェイ数とを比較する。アドレス数がウェイ数より多い行を検出した場合、比較回路４０２は、エントリフル信号として、エントリフルを示す「１」と、当該行を示すアドレス値とを出力する。
【００４５】
追い出し制御回路５は、ストアバッファ３及びエントリフル検出回路４と接続されている。追い出し制御回路５は、エントリフル検出回路４が出力したエントリフル情報に基づいてストアデータの追い出し判定を行う。ここでいう追い出し判定は、ストアバッファ３から主記憶装置６へデータを出力する必要があるか否かの判定である。ストアバッファ３のエントリがフルの状態で中央処理装置１がさらにストアリクエストを出力した場合、このストアリクエストをストアバッファ３に格納するための空きを作る必要がある。この空きを作るためのストアバッファ３から主記憶装置６へのデータの出力をデータの追い出しと称する。この追い出しを行う必要があるか否かの判定を追い出し判定と称する。
追い出しが必要と判定した場合、追い出し制御回路５は、追い出し指示信号をストアバッファ３へ出力する。
【００４６】
図８は、追い出し制御回路５が追い出し指示信号を生成する際の生成規則の例を示す図である。図８の例で、追い出し制御回路５は、取得したエントリフル情報がエントリフルを示す場合、追い出し制御回路５は、追い出し指示信号の値を「１」＋アドレス値にする。この値の「１」は、追い出しが必要であることを示す。アドレス値は、追い出しの対象となるデータを示す。
一方、取得したエントリフル情報がエントリフルでないことを示す場合、追い出し制御回路５は、追い出し指示信号の値を「０」にする。追い出し指示信号の値「０」は、追い出しが不要であること示す。
【００４７】
主記憶装置６は、中央処理装置１及びストアバッファ３と接続されている。主記憶装置６は、ストアバッファ３が出力したリクエストに従ってデータの入出力を行う。
ストアバッファ３がロードリクエストを出力した場合、主記憶装置６は、リクエスト内のアドレス情報に従ってロードデータを読み出して中央処理装置１へ出力する。ストアバッファ３がストアリクエストを出力した場合、主記憶装置６は、リクエスト内のアドレス情報に従ってストアデータを保持する。具体的には、主記憶装置６は、主記憶装置６自らの記憶領域のうちリクエスト内のアドレス情報が示す記憶領域にストアデータを記憶する。
【００４８】
次に、情報処理装置１０の動作について説明する。
図９は、ロード時における情報処理装置１０の動作の第１例を示す図である。図９は、ロードリクエストが示すアドレスに該当するデータをストアバッファ３が記憶していない場合の例を示している。
図９の処理で、中央処理装置１がロードリクエストを出力し、マージ回路２は、このロードリクエストをそのままストアバッファ３へ転送する（シーケンスＳ１１１）。
【００４９】
ロードリクエストを取得したストアバッファ３は、ロードリクエストのアドレスとストアバッファ内のストアリクエストのアドレスとを比較し、ストアデータの追い出し要否を判定する（シーケンスＳ１１２）。
図５を参照して説明したように、ストアバッファ３はｎウェイ（ｎは１，２，４，８等の整数）のセットアソシアティブ方式のキャッシュ構成を成している。追い出し要否の判定で、ストアバッファ３は、ロードリクエスト内の中位アドレスを参照してアドレスアレイ３０１の行を特定し、各ウェイからストアリクエストを読み出す。ストアバッファ３は、読み出したストアリクエストのアドレスがロードリクエスト内の上位アドレスと一致するか否かを判定する。図９の例では、ストアバッファ３は、アドレスが一致せず追い出しは不要であると判定している。
【００５０】
追い出し不要と判定したストアバッファ３は、ロードリクエストをそのまま主記憶装置６へ送出する（シーケンスＳ１１３）。
主記憶装置６は受け取ったロードリクエスト内のアドレスに対応するロードデータを読み出して中央処理装置１へ出力する（シーケンスＳ１１４）。
シーケンスＳ１１４の後、図９の処理を終了する。
【００５１】
図１０は、ロード時における情報処理装置１０の動作の第２例を示す図である。図１０は、ロードリクエストが示すアドレスに該当するデータをストアバッファ３が記憶している場合の例を示している。
図１０のシーケンスＳ１２１は、図９のシーケンスＳ１１１と同様である。
【００５２】
ロードリクエストを取得したストアバッファ３は、図９のシーケンスＳ１１２の場合と同様、ストアデータの追い出し要否を判定する（シーケンスＳ１２２）。
図１０の例では、ストアバッファ３は、アドレスが一致して追い出しが必要であると判定している。
【００５３】
追い出し必要と判定したストアバッファ３は、ロードリクエストをレジスタ３０５に待避させる（シーケンスＳ１２３）。そして、ストアバッファ３は、シーケンスＳ１２２で一致すると判定したアドレスのストアリクエスト及びストアデータを読み出して主記憶装置６へ出力する（シーケンスＳ１２４）。主記憶装置６は、ストアリクエストに従ってストアデータを記憶する（シーケンスＳ１２５）。
【００５４】
その後、ストアバッファ３は、待避していたロードリクエストを主記憶装置６へ転送する（シーケンスＳ１２６）。主記憶装置６は、ロードリクエストに従ってロードデータを読み出し中央処理装置１へ出力する（シーケンスＳ１２７）。
このように、ストアバッファ３が主記憶装置６へストアリクエストを出力してストアを実行させた後にロードリクエストを主記憶装置６へ出力することで、ストアリクエストを後続のロードリクエストが追い越すことを抑止することができる。
シーケンスＳ１２７の後、図１０の処理を終了する。
【００５５】
図１１は、ストアバッファ３がストアデータを記憶する場合の情報処理装置１０の処理手順の例を示す図である。
図１１の処理で、中央処理装置１はストアリクエストをマージ回路２へ出力する（シーケンスＳ２１１）。
ストアリクエストを取得したマージ回路２は、ストアリクエストが示すアドレスに該当するライン単位のストアデータをストアバッファ３から読み出す（シーケンスＳ２１２）。
【００５６】
そして、マージ回路２は、ストアバッファ３から読み出したライン単位のストアデータに、ストアリクエストのストアデータをマージする（シーケンスＳ２１３）。
マージ回路２は、マージされたライン単位のストアデータとアドレスとを併せたストアリクエストをストアバッファ３へ出力する（シーケンスＳ２１４）。ストアバッファ３は、マージ回路２からのストアリクエストを、シーケンスＳ２１２でストアデータを読み出されたストアリクエストに上書きする（シーケンスＳ２１５）。
また、ストアバッファ３は、データを書き込んだ領域に対応する使用履歴フラグの値を「１」にする（シーケンスＳ２１６）。
シーケンスＳ２１６の後、図１１の処理を終了する。
【００５７】
なお、ストアバッファ３がマージ可能なストアデータを記憶していない場合、マージ回路２は、中央処理装置１からのストアデータをライン単位のストアデータに整形する。マージ回路２は、整形したストアデータとアドレスとを併せたストアリクエストをストアバッファ３に記憶させる。そして、ストアバッファ３は、データを書き込んだ領域に対応する使用履歴フラグの値を「１」にする。
【００５８】
図１２は、ストアバッファ３がストアリクエストの追い出し処理を行う場合の情報処理装置１０の処理手順の例を示す図である。
図１２の例で、ストアバッファ３がエントリフル検出回路４へエントリ情報を出力する（シーケンスＳ２２１）。エントリフル検出回路４は、ストアバッファ３からのエントリ情報に基づいて、エントリフルか否かを判定する（シーケンスＳ２２２）。図１２の例では、エントリフル検出回路４は、エントリフルを検出している。すなわち、エントリフル検出回路４は、エントリフルであると判定している。
【００５９】
エントリフルと判定したエントリフル検出回路４は、エントリフル信号を追い出し制御回路５へ出力する（シーケンスＳ２２３）。
エントリフル信号を取得した追い出し制御回路５は、追い出し判定を行う（シーケンスＳ２２４）。図１２の例では、追い出し制御回路５は、追い出しが必要と判定している。追い出しが必要と判定した追い出し制御回路５は、追い出し指示信号をストアバッファ３へ出力する（シーケンスＳ２２５）。
【００６０】
ストアバッファ３は、追い出し指示信号に従ってストアデータの追い出しを行う（シーケンスＳ２２６）。ストアバッファ３はストアデータをライン単位で格納しており、追い出し指示信号に従って主記憶装置６へストアデータをライン単位で出力する。
具体的には、ストアバッファ３、ストアリクエスト内の中位アドレスを参照してアドレスアレイ３０１の行を特定する。ストアバッファ３は、特定された行の各ウェイから読み出したアドレスがストアリクエスト内の上位アドレスと一致するか比較を行う。ストアバッファ３は、データアレイ３０２から読み出したライン単位のストアデータのうち一致したアドレスに対応するものを出力する。通常は、ストアバッファ３は、ストアリクエストに示される中位アドレス及び上位アドレスに該当するストアデータを読み出す。一方、追い出し指示信号を取得した場合、ストアバッファ３のアドレス差替回路３０３が追い出し指示信号に示されるアドレスに差し替える。ストアバッファ３は、差し替えられたアドレスに対応するストアデータを読み出す。
【００６１】
ストアデータの追い出しを行ったストアバッファ３は、データを追い出した領域に対応するリプレースフラグの値を「１」にする（シーケンスＳ２２７）。
ストアバッファ３から追い出されたストアリクエストを取得した主記憶装置６は、取得したストアリクエスト内のアドレスに対応する領域に行単位のストアデータを記憶する（シーケンスＳ２２８）。
シーケンスＳ２２８の後、図１２の処理を終了する。
【００６２】
ストアバッファ３が追い出すストアリクエストを選択する方式として、既存のいろいろな方式を用いることができる。例えば、ストアバッファ３が、ＦＩＦＯ（First-In First-Out）でストアリクエストの追い出しを行うようにしてもよい。この場合、追い出し指示信号を受けたストアバッファ３は、追い出し指示信号が示す行に格納しているストアリクエストのうち、最も古いストアリクエストを追い出す。ストアバッファ３は、ストアリクエストを追い出した空き領域に後続のストアリクエストを格納する。
【００６３】
図１３は、ストアバッファ３がアドレスアレイ３０１及びデータアレイ３０２のウェイを拡張する処理手順の例を示す図である。
図１３の処理で、ウェイ拡張指示回路３１１は、使用履歴フラグレジスタ３０９から使用履歴フラグを読み出し（シーケンスＳ２３１）、リプレースフラグレジスタ３１０からリプレースフラグを読み出す（シーケンスＳ２３２）。
【００６４】
そして、ウェイ拡張指示回路３１１は、使用履歴フラグ及びリプレースフラグに基づいて、ウェイを拡張するか否かを決定する（シーケンスＳ２３３）。ここでのウェイ拡張は、ウェイの数を増やすことである。ここでのウェイの数は、セットアソシアティブにおける列数に対応しており、ウェイを拡張するすると列数が増加する。図１３の例では、ウェイ拡張指示回路３１１は、ウェイを拡張することに決定している。
【００６５】
ウェイの拡張をすることに決定したウェイ拡張指示回路３１１は、ウェイ拡張指示をアレイ制御回路３０７、３０８のそれぞれに出力する。
ウェイ拡張指示を受けたアレイ制御回路３０７及び３０８は、アドレスアレイ及びデータアレイのウェイを拡張する（シーケンスＳ２３５）。
シーケンスＳ２３５の後図１３の処理を終了する。
【００６６】
図１４は、使用履歴フラグ及びリプレースフラグの値の第１例を示す図である。図１４の例で、アドレスアレイ３０１は、ウェイ拡張前の状態にある。また、図１４の例でアドレスアレイ３０１の行数（Indexの数）は８、列数（Wayの数）は４になっている。データアレイ３０２の行数、列数は、アドレスアレイ３０１の行数、列数と同数に設定されるので、データアレイ３０２もウェイ拡張前の状態にある。
【００６７】
図１４の例で、領域Ａ１１に含まれる各行のリプレースフラグの値は、いずれも「１」となっている。リプレースフラグの値「１」は、該当行でストアリクエストの格納領域（空きウェイ）が不足して追い出しが行われたことを示している。一方、領域Ａ１２に含まれる各行の使用履歴フラグの値は「０」になっている。使用履歴フラグの値「０」は、対応する行の格納領域が使われていないことを示している。
【００６８】
このように領域Ａ１１に含まれる各行では、ストアリクエストの格納領域が不足し、領域Ａ１２に含まれる各行では、ストアリクエストの格納領域が未使用のまま残っている。
そこで、ストアバッファ３は、領域Ａ１１の行と領域Ａ１２の行とを纏める。
例えば、ウェイ拡張指示回路３１１は、図１４に示す使用履歴フラグ及びリプレースフラグの状態を検出すると、ウェイ拡張指示信号を生成してアレイ制御回路３０７及び３０８へ出力する。アレイ制御回路３０７及び３０８はウェイ拡張指示回路３１１からウェイ拡張指示信号を取得すると、アドレスアレイ３０１及びデータアレイ３０２の行数（Indexの数）を４にし、列数（Wayの数）を８にする。そのために、アレイ制御回路３０７及び３０８は、領域Ａ１２の各行のウェイ０〜ウェイ３を、領域Ａ１１の各行のウェイ４〜ウェイ７として扱う。
【００６９】
図１５は、ウェイ拡張後のアドレスアレイ３０１の構成の第１例を示す図である。
図１５に示すアドレスアレイ３０１では、領域Ａ１１の１つの行と領域Ａ１２の１つの行とが結合され（１つの行に纏められ）、ウェイの数が２倍に増加している。特に、リプレースフラグの値が「１」になっている行と使用履歴フラグの値が「０」になっている行とが結合されている。ストアバッファ３は、データアレイ３０２の構成についてもアドレスアレイと同様に変更する。
ウェイの数が増えることで、図１５の例のアドレスアレイ３０１では、１行当たりのストアリクエストの格納領域の数を増やすことができ、ストアリクエストの追い出しを行う回数が減少することが期待される。
【００７０】
ストアバッファ３は、例えば、リプレースフラグの値が「１」の行数が所定の閾値以上かつ、使用履歴フラグの値が「０」の行数が所定の閾値以上である場合に、データアレイの行数を半分にし、列数を２倍にする変更を行う。変更の方法として、例えば特開２００５−２９３３００に示されている方法など公知の方法を用いることができる。
例えば、ストアバッファ３は、中位アドレスの先頭ビットを上位アドレスに含めることで、アレイの行数を半分にし、列数を倍にする。
このように、情報処理装置１０では、使用履歴フラグとリプレースフラグとを用いてウェイの数を調整することで、空き領域を減らしてストアバッファ３の利用効率を向上させることができる。ストアバッファの利用効率が向上することで、ストアデータを効率的に圧縮することができ、主記憶装置６へのアクセス効率を向上させることができる。
【００７１】
図１６は、使用履歴フラグ及びリプレースフラグの値の第２例を示す図である。図１６の例で、アドレスアレイ３０１は、ウェイ拡張前の状態にある。また、図１６の例でアドレスアレイ３０１の行数は８、列数は４になっている。データアレイ３０２の行数、列数は、アドレスアレイ３０１の行数、列数と同数に設定されるので、データアレイ３０２もウェイ拡張前の状態にある。
【００７２】
図１６の例で、領域Ａ２１に含まれる行のリプレースフラグの値は「１」となっている。一方、領域Ａ２２に含まれる行の使用履歴フラグの値は「０」になっている。
リプレースフラグ及び使用履歴フラグの値から、領域Ａ２１に含まれる行ではストアリクエストの格納領域が不足し、領域Ａ２２に含まれる行では、ストアリクエストの格納領域が未使用のまま残っている。
そこで、ストアバッファ３は、領域Ａ２１の行と領域Ａ２２の行とを纏める。
【００７３】
図１７は、ウェイ拡張後のアドレスアレイ３０１の構成の第２例を示す図である。
図１７の例では、ある１つの行（Index）のみウェイ拡張を行っている点で、図１５の場合と異なる。
アドレスアレイ３０１の状態を図１６の状態から図１７の状態にするために、例えば、ウェイ拡張指示回路３１１の判定条件を
（１）ある行の使用履歴フラグの値とリプレースフラグの値とが共に「１」、且つ、
（２）他のある行のウェイが全て空きである場合
とする。ウェイ拡張指示回路３１１は、この条件が成立した場合に、ウェイ拡張指示信号を出力する。
【００７４】
ウェイ拡張指示回路３１１は、ウェイ拡張指示信号と対象インデックス番号とをアレイ制御回路３０７及び３０８へ出力する。アレイ制御回路３０７及び３０８は、対象インデックスのみウェイの読み変えを行う。
このように、ある１つのインデックスのみウェイ拡張を行うことで、情報処理装置１０では、一部の行のみでウェイが不足している場合、及び、一部の行のみで空きがある場合にもウェイ拡張を行い、ストアバッファ３の利用効率を向上させることができる。また、１つの行に纏めた行以外はウェイの数が４のままである点で、行内の領域を検索する負荷が比較的小さくて済む。
【００７５】
以上のように、使用履歴フラグレジスタ３０９の使用履歴フラグは、アドレスアレイ３０１及びデータアレイ３０２におけるセットアソシアティブ方式の行毎に、その行に含まれる記憶領域のうち少なくとも１つの領域にデータが格納されたか否かを示す。また、リプレースフラグレジスタ３１０のリプレースフラグは、行毎にその行でデータの追い出しが行われたか否かを示す。ウェイ拡張指示回路３１１は、使用履歴フラグの値及びリプレースフラグの値に基づいて、セットアソシアティブ方式におけるウェイの数を増やすか否かを決定する。アレイ制御回路３０７及び３０８は、ウェイ拡張指示回路３１１がウェイの数を増やすことに決定した場合、ウェイの数を増やす。
このように、情報処理装置１０では、使用履歴フラグ及びリプレースフラグを参照してウェイの数を増やすか否かを自動的に判定することができる。また、情報処理装置１０が、使用履歴フラグ及びリプレースフラグを備えることで、領域が不足している行及び領域が使用されていない行を検出することができる。領域が不足している行と領域が使用されていない行とを１つの行に纏めることで、ヒット率を高めデータの追い出しを行う回数を減らすことができる。また、領域が不足している行と領域が使用されていない行とを１つの行に纏めることで、メモリアクセス効率を高めることができる。
【００７６】
また、アレイ制御回路３０７及び３０８は、セットアソシアティブ方式の行数（インデックス数）を半分にし、ウェイの数（列数）を２倍にする。これにより、行毎のウェイの数を同数に保つことができる。行毎のウェイの数が同数であることで、アレイ制御回路３０７及び３０８は、比較的簡単な処理でアドレスアレイ３０１及びデータアレイ３０２を制御することができる。
【００７７】
また、アレイ制御回路３０７及び３０８は、セットアソシアティブ方式の行のうち、使用履歴フラグが、領域にデータが格納されたことを示す行と、リプレースフラグが、データの追い出しが行われたことを示す行とを１つの行に纏める。
このようにある１つのインデックスのみウェイ拡張を行うことで、情報処理装置１０では、一部の行のみでウェイが不足している場合、及び、一部の行のみで空きがある場合にもウェイ拡張を行い、ストアバッファ３の利用効率を向上させることができる。また、１つに纏めた行以外はウェイの数が４のままである点で、行内の領域を検索する負荷が比較的小さくて済む。
【００７８】
次に、図１８及び図１９を参照して、本発明の最小構成について説明する。
図１８は、本発明に係る情報処理装置の最小構成の例を示す図である。図１８に示す情報処理装置２０は、記憶部２１と、使用履歴フラグ２２と、リプレースフラグ２３と、ウェイ拡張指示部２４と、ウェイ拡張部２５とを備える。
かかる構成にて、記憶部２１は、セットアソシアティブ方式でデータを記憶する。使用履歴フラグ２２は、セットアソシアティブ方式の行毎にその行に含まれる記憶領域のうち少なくとも１つの領域にデータが格納されたか否かを示す。リプレースフラグ２３は、行毎にその行でデータの追い出しが行われたか否かを示す。ウェイ拡張指示部２４は、使用履歴フラグ２２の値及びリプレースフラグ２３の値に基づいて、セットアソシアティブ方式におけるウェイの数を増やすか否かを決定する。ウェイ拡張部２５は、ウェイ拡張指示部２４がウェイの数を増やすことに決定した場合、ウェイの数を増やす。
【００７９】
これにより、情報処理装置２０では、使用履歴フラグ２２及びリプレースフラグ２３を参照してウェイの数を増やすか否かを自動的に判定することができる。また、情報処理装置２０が、使用履歴フラグ２２及びリプレースフラグ２３を備えることで、領域が不足している行及び領域が使用されていない行を検出することができる。領域が不足している行と領域が使用されていない行とを１つの行に纏めることで、ヒット率を高めデータの追い出しを行う回数を減らすことができる。また、領域が不足している行と領域が使用されていない行とを１つの行に纏めることで、メモリアクセス効率を高めることができる。
【００８０】
図１９は、本発明に係る制御装置の最小構成の例を示す図である。図１９に示す制御装置３０は、ウェイ拡張指示部３１と、ウェイ拡張部３２とを備える。
かかる構成にて、ウェイ拡張指示部３１は、セットアソシアティブ方式でデータを記憶する記憶部におけるセットアソシアティブ方式の行毎に、その行に含まれる記憶領域のうち少なくとも１つの領域にデータが格納されたか否かを示す使用履歴フラグの値と、行毎に、その行でデータの追い出しが行われたか否かを示すリプレースフラグの値とに基づいて、セットアソシアティブ方式におけるウェイの数を増やすか否かを決定する。ウェイ拡張部３２は、ウェイ拡張指示部３１がウェイの数を増やすことに決定した場合、ウェイの数を増やす。
【００８１】
これにより、制御装置３０では、使用履歴フラグ及びリプレースフラグ２３を参照してウェイの数を増やすか否かを自動的に判定することができる。また、制御装置３０が、使用履歴フラグ及びリプレースフラグを参照することで、領域が不足している行及び領域が使用されていない行を検出することができる。領域が不足している行と領域が使用されていない行とを１つの行に纏めることで、ヒット率を高めデータの追い出しを行う回数を減らすことができる。また、領域が不足している行と領域が使用されていない行とを１つの行に纏めることで、メモリアクセス効率を高めることができる。
【００８２】
なお、情報処理装置１０及び２０と、制御装置３０との全部または一部を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより各部の処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【００８３】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００８４】
１  中央処理装置
２  マージ回路
３  ストアバッファ
４  エントリフル検出回路
５  追い出し制御回路
６  主記憶装置
１０  情報処理装置
２０１  シフタ
２０２  マージャ
３０１  アドレスアレイ
３０２  データアレイ
３０３  アドレス差替回路
３０４  アドレス選択回路
３０５  レジスタ
３０６  エントリ選択回路
３０７、３０８  アレイ制御回路
３０９  使用履歴フラグレジスタ
３１０  リプレースフラグレジスタ
３１１  ウェイ拡張指示回路
４０１  レジスタ
４０２  比較回路
【図１】
2018133038.tif 000003
【図２】
2018133038.tif 000004
【図３】
2018133038.tif 000005
【図４】
2018133038.tif 000006
【図５】
2018133038.tif 000007
【図６】
2018133038.tif 000008
【図７】
2018133038.tif 000009
【図８】
2018133038.tif 000010
【図９】
2018133038.tif 000011
【図１０】
2018133038.tif 000012
【図１１】
2018133038.tif 000013
【図１２】
2018133038.tif 000014
【図１３】
2018133038.tif 000015
【図１４】
2018133038.tif 000016
【図１５】
2018133038.tif 000017
【図１６】
2018133038.tif 000018
【図１７】
2018133038.tif 000019
【図１８】
2018133038.tif 000020
【図１９】
2018133038.tif 000021