(57)【特許請求の範囲】
【請求項１】
データに処理を施す処理部と、
前記データが記憶されている記憶部と前記処理部との間に設けられたキャッシュ部とを備え、
前記キャッシュ部は、
前記記憶部のデータがコピーされる複数のデータアレイと、
前記複数のデータアレイにおけるウェイの古さ順を示す第１の情報を保持する情報アレイとを有し、
前記複数のデータアレイの各々はウェイ数が１以上であって、前記複数のデータアレイのうち少なくとも１つはエントリ数が異なり、
所定のサイズで分割された前記記憶部の記憶領域に対し、前記複数のデータアレイにてそれぞれ１つのエントリが割り当てられていることを特徴とする情報処理装置。
【請求項２】
前記処理部からのアクセス先を示すアドレスを基に、各データアレイに応じた前記アドレス中のインデックス部に基づいて前記複数のデータアレイを同時に参照することを特徴とする請求項１記載の情報処理装置。
【請求項３】
前記記憶部のデータを前記データアレイにコピーする場合に、前記複数のデータアレイの何れか１つのデータアレイにコピーすることを特徴とする請求項１又は２記載の情報処理装置。
【請求項４】
各データアレイ毎のデータアレイ内でのウェイの古さ順を示す情報と、前記データアレイ間でのウェイの古さ順を示す情報とに分割して前記第１の情報を前記情報アレイに保持することを特徴とする請求項１〜３の何れか１項に記載の情報処理装置。
【請求項５】
エントリ数が最大である前記データアレイのエントリ数は、当該データアレイ以外の前記データアレイのエントリ数の整数倍であることを特徴とする請求項１〜４の何れか１項に記載の情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュ部を有する情報処理装置に関する。
【背景技術】
【０００２】
プロセッサシステムにおいて、メモリ（主記憶）に記憶されているデータの読み出しに係るプロセッサからメモリへのアクセス速度を速くするために、キャッシュが使用されている。キャッシュ内のデータとメモリ内のデータとの対応に係るキャッシュエントリとメモリアドレスとのマッピング方式としては、ダイレクトマッピング方式、セットアソシアティブ方式、フルアソシアティブ方式がよく知られている。
【０００３】
キャッシュのヒット率については、ダイレクトマッピング方式、セットアソシアティブ方式、フルアソシアティブ方式の順で性能が向上する。一方、実装容易性は、ダイレクトマッピング方式、セットアソシアティブ方式、フルアソシアティブ方式の順で低くなり、フルアソシアティブ方式は現実的に実装困難である。そのため、４ウェイ程度のセットアソシアティブ方式を用いるのが一般的である。
【０００４】
図１１は、４ウェイのセットアソシアティブ方式のキャッシュの構成を示す図である。
図１１において、１１０はタグアレイ、１１１はデータアレイ、１１２（１１２−０〜１１２−３）は比較器、１１３は選択回路、１１４はＬＲＵ（Least Recently Used）アレイである。データアレイ１１１は、キャッシュラインサイズ単位でメモリ（主記憶）内のデータのコピーをブロックに記憶する。タグアレイ１１０は、データアレイ１１１の各ブロックに格納されているデータについてのタグ（メモリアドレスの一部）を記憶する。図示のようにアドレスの全ビットのうち、キャッシュラインサイズに対応する下位ビットをオフセットとして、オフセット部より上位に位置する、エントリ数（データアレイにおける縦方向のブロック数）に対応する所定数のビットがキャッシュのインデックスとなる。インデックス部よりさらに上位の残りのビットがキャッシュのタグとなる。ＬＲＵアレイ１１４は、タグアレイ１１０及びデータアレイ１１１におけるウェイの古さ順（最後に使用されてからの経過時間の順）を示すＬＲＵ情報を保持する。
【０００５】
メモリ空間上のあるアドレスへのアクセスを実行する場合に、アクセス先を示すアドレスが入力されるとアドレス中のインデックス部に基づいてタグアレイ１１０が参照され、各ウェイにおいてインデックスに対応するブロックからタグが読み出される。読み出されたタグとアドレス中のタグ部のビットパターンとがウェイ毎に比較器１１２によって比較され、比較結果が選択回路１１３に出力される。
【０００６】
読み出されたタグとアドレス中のタグ部のビットパターンとが一致する場合にはキャッシュヒットとなる。このとき、インデックスに対応するデータアレイ１１１のブロックからデータが読み出され、タグが一致したウェイに対応するブロックから読み出されたデータが、比較器１１２での比較結果に応じて選択回路１１３により選択されて出力データとして出力される。
【０００７】
一方、いずれのウェイにおいても、読み出されたタグとアドレス中のタグ部のビットパターンとが一致しない場合にはキャッシュミスとなる。キャッシュミスである場合には、メモリにアクセスすることで、アクセス先を示すアドレスに対応するメモリの記憶領域からデータが読み出され出力データとして出力される。また、メモリから読み出されたデータが、キャッシュに入力データとして供給され登録される。アドレスにおけるインデックスに対応するタグアレイ１１０のブロックにアドレスにおけるタグが登録され、インデックスに対応するデータアレイ１１１のブロックにメモリから読み出されたデータが登録される。このとき、ＬＲＵアレイ１１４に保持されているＬＲＵ情報に基づき、インデックスに対応するタグアレイ１１０及びデータアレイ１１１のブロックのうち、最後に使用されてから最も長い時間が経過したブロックにタグ及びデータがリプレース（書き換え）される。
【０００８】
また、キャッシュシステムにおいて、ウェイ数とブロックサイズとの組合せをレジスタに指定することで変更可能なようにするキャッシュ方式が提案されている（特許文献１参照）。このように、アプリケーションに最適なウェイ数及びブロックサイズにキャッシュ構成を変更することで、キャッシュの利用効率やヒット率の向上を図っている。また、キャッシュのヒット率を観測する回路を設けて、適当な閾値に基づきデータアレイへの電源供給をウェイ単位でオン／オフし、動作させるウェイ数を制御できるようにしたキャッシュが提案されている（特許文献２参照）。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２０００−２０３９６号公報
【特許文献２】特開平９−５０４０１号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
キャッシュとしては、ヒット率やハードウェア量の観点から４ウェイ程度のセットアソシアティブ方式のキャッシュを用いるのが一般的である。しかし、実行するアプリケーションによっては、２ウェイ程度で十分なこともあれば、８ウェイ程度でないと頻繁にキャッシュのデータがリプレースされてしまうことがある。また、データアレイ全体のウェイ数だけでなく、エントリ番号毎に使用頻度が偏ることがあり得る。
【００１１】
前述の特許文献１や特許文献２に記載の技術によれば、キャッシュのウェイ数を変更することが可能である。しかし、特許文献１のような、ウェイ数をアプリケーションに応じてユーザが予め決定し、固定的にユーザが手動でウェイ数を指定して使用する方法では、利用の容易性を考えると問題がある。また、すべてのエントリ番号に対して一意にウェイ数を変更させるため、エントリ番号毎の使用頻度に隔たりがあるとキャッシュの利用効率の向上は期待できない。また、特許文献２においても、すべてのエントリ番号に対して一意にウェイ数を変更させるため、エントリ番号毎に使用頻度の偏りがあるとキャッシュの利用効率の向上は期待できない。
【課題を解決するための手段】
【００１２】
本発明の一観点によれば、データに処理を施す処理部と、データが記憶されている記憶部と処理部との間に設けられたキャッシュ部とを備える情報処理装置が提供される。キャッシュ部は、記憶部のデータがコピーされる複数のデータアレイと、複数のデータアレイにおけるウェイの古さ順を示す情報を保持する情報アレイとを有する。複数のデータアレイの各々はウェイ数が１以上であって、複数のデータアレイのうち少なくとも１つはエントリ数が異なり、分割された記憶部の記憶領域に対し、複数のデータアレイにてそれぞれ１つのエントリが割り当てられている。
【発明の効果】
【００１３】
本発明によれば、実行するアプリケーションに応じてエントリ単位で動的にウェイ数を増減し最適なウェイ数に自動で変更することができ、キャッシュの利用効率やヒット率を向上させることができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施形態における情報処理装置の構成例を示す図である。
【図２】本実施形態におけるキャッシュ部の構成例を示す図である。
【図３】本実施形態におけるメモリアドレスとキャッシュエントリとの対応を説明するための図である。
【図４】本実施形態でのアクセス動作の一例を示すフローチャートである。
【図５】ＬＲＵ参照動作処理を示すフローチャートである。
【図６】本実施形態におけるキャッシュのウェイ数の変化を説明するための図である。
【図７】本実施形態におけるＬＲＵ情報の例を示す図である。
【図８】本実施形態におけるＬＲＵ情報のエンコード方式の例を示す図である。
【図９】本実施形態での具体的な動作例を説明するための図である。
【図１０】本実施形態での具体的な動作例を説明するための図である。
【図１１】セットアソシアティブ方式のキャッシュの一例を示す図である。
【発明を実施するための形態】
【００１５】
以下、本発明の実施形態を図面に基づいて説明する。
【００１６】
図１は、本発明の実施形態による情報処理装置の構成例を示すブロック図である。
図１において、１は情報処理装置であり、４はメモリ（主記憶）である。情報処理装置１は、メモリ４からデータを読み出して（ロードして）処理を施したり、処理結果として得られたデータをメモリに書き込んだりする（ストアする）。メモリ４は、情報処理装置１での処理に係るデータ等を記憶する。
【００１７】
情報処理装置１は、命令に応じた処理を行う処理部２と、メモリ４のデータがコピーされるキャッシュ部３とを有する。図１においては、処理部２の一例としてＣＰＵコアを示しているが、これに限定されるものではなく、例えばアクセラレータであっても良い。
【００１８】
情報処理装置１の処理部２がメモリ空間上のあるアドレスへアクセスしてデータをロードする場合、まずキャッシュ部３が参照されて、所望のデータ（当該アドレスにより指定される格納領域のデータ）のコピーがキャッシュ部３に存在するか否かが判断される。その結果、所望のデータのコピーがキャッシュ部３に存在するとき（キャッシュヒット）には、キャッシュ部３より所望のデータのコピーが読み出されて処理部２に供給される。
【００１９】
一方、所望のデータのコピーがキャッシュ部３に存在しないとき（キャッシュミス）には、メモリ４に対するアクセスが行われ、所望のデータが読み出される。そして、メモリ４から読み出された所望のデータが、処理部２に供給されるとともに、キャッシュ部３内のデータ（例えば、最後に使用されてから最も長い時間が経過したデータ）とリプレース（置き換え）されてキャッシュ部３に登録される。
【００２０】
図２は、図１に示したキャッシュ部３の構成例を示す図である。
図２において、１０は第１のアレイ（メインアレイ）、２０は第２のアレイ（サブアレイ）、３０はＬＲＵ（Least Recently Used）アレイである。第１のアレイ（メインアレイ）１０は、例えばウェイ数が２である２ウェイのセットアソシアティブ方式のキャッシュに相当し、第２のアレイ（サブアレイ）２０は、例えばウェイ数が４である４ウェイのセットアソシアティブ方式のキャッシュに相当する。
【００２１】
なお、第１のアレイ（メインアレイ）１０と第２のアレイ（サブアレイ）２０とはエントリ数（アレイにおける縦方向のブロック数）が異なっており、第１のアレイ（メインアレイ）１０のエントリ数は第２のアレイ（サブアレイ）２０のエントリ数より大きい。例えば、第１のアレイ（メインアレイ）１０のエントリ数は、第２のアレイ（サブアレイ）２０のエントリ数の４倍程度が好ましい。
【００２２】
メインアレイ１０は、メインタグアレイ１２、メインデータアレイ１４、比較器１６（１６−０、１６−１）、及び選択回路１８を有する。メインデータアレイ１４は、キャッシュラインサイズ単位でメモリ４内のデータのコピーをブロックに記憶する。メインタグアレイ１２は、メインデータアレイ１４の各ブロックに格納されているデータについてのタグ（メモリアドレスの一部）を記憶する。
【００２３】
比較器１６は、入力されたアクセス先を示すアドレスに基づいてメインタグアレイ１２から読み出されたタグとアドレス中のタグ部のビットパターンとをウェイ毎に比較し、比較結果を選択回路１８に出力する。選択回路１８は、入力されたアドレスに基づいてメインデータアレイ１４から読み出されたデータを、比較器１６での比較結果に応じて選択し出力データとして出力する。詳細には、選択回路１８は、アドレスに基づいてメインデータアレイ１４から読み出されたデータのうち、メインタグアレイ１２から読み出されたタグとアドレス中のタグ部のビットパターンとが一致したウェイのデータを選択し出力する。なお、いずれのウェイにおいても読み出されたタグとアドレス中のタグ部のビットパターンとが一致しない場合には、選択回路１８はデータを出力しない。
【００２４】
また、サブアレイ２０は、サブタグアレイ２２、サブデータアレイ２４、比較器２６（２６−０〜２６−３）、及び選択回路２８を有する。サブデータアレイ２４は、キャッシュラインサイズ単位でメモリ４内のデータのコピーをブロックに記憶する。サブタグアレイ２２は、サブデータアレイ２４の各ブロックに格納されているデータについてのタグ（メモリアドレスの一部）を記憶する。
【００２５】
比較器２６は、入力されたアドレスに基づいてサブタグアレイ２２から読み出されたタグとアドレス中のタグ部のビットパターンとをウェイ毎に比較し、比較結果を選択回路２８に出力する。選択回路２８は、選択回路１８と同様に、入力されたアドレスに基づいてサブデータアレイ２４から読み出されたデータを、比較器２６での比較結果に応じて選択し出力データとして出力する。
【００２６】
ＬＲＵアレイ３０は、各エントリ単位で、メインアレイ１０及びサブアレイ２０におけるウェイの古さ順（最後に使用されてからの経過時間の順）を示すＬＲＵ情報を保持する。また、キャッシュ部３は、キャッシュ部３内の各機能部の制御等を行う図示しないキャッシュ制御部を有する。キャッシュ制御部は、例えば、ＬＲＵ情報の更新を行ったり、キャッシュミスのときのメモリ４へのアクセスや各データアレイのリプレース等の制御を行ったりする。
【００２７】
本実施形態におけるキャッシュ部３において、アドレスの全ビットのうち、キャッシュラインサイズに対応する下位ビットをオフセットとして、オフセット部より上位に位置する、エントリ数に対応する所定数のビットがキャッシュのインデックスとなる。インデックス部よりさらに上位の残りのビットがキャッシュのタグとなる。ここで、メインアレイ１０とサブアレイ２０とはエントリ数が異なる。そのため、任意のアドレスに対し、メインアレイ１０でのキャッシュのタグ及びインデックスと、サブアレイ２０でのキャッシュのタグ及びインデックスとは異なる。
【００２８】
例えば、アドレスがその最下位ビットを１ビット目としその最上位ビットを３２ビット目とする３２ビットであり、キャッシュラインサイズが３２バイトであり、メインアレイ１０のエントリ数が１２８であり、サブアレイ２０のエントリ数が３２であるとする。このとき、メインアレイ１０については、アドレスにおける１ビット目〜５ビット目の５ビットがオフセットとなり、６ビット目〜１２ビット目の７ビットがインデックスとなり、１３ビット目〜３２ビット目の２０ビットがタグとなる。また、サブアレイ２０については、アドレスにおける１ビット目〜５ビット目の５ビットがオフセットとなり、６ビット目〜１０ビット目の５ビットがインデックスとなり、１１ビット目〜３２ビット目の２２ビットがタグとなる。
【００２９】
図３は、本実施形態における情報処理装置でのメモリアドレスとキャッシュエントリとの対応を説明するための図である。図３において、１００はメモリ（主記憶）であり、１０１はキャッシュ部のメインアレイ（メインデータアレイ）であり、１０２はキャッシュ部のサブアレイ（サブデータアレイ）である。なお、図３に示す例では、メインアレイ１０は、エントリ数が８、ウェイ数が２のアレイとし、サブアレイ１０２は、エントリ数が２、ウェイ数が４のアレイとする。また、キャッシュラインサイズは３２バイトとする。
【００３０】
メモリ１００からキャッシュ部のメインアレイ１０１、サブアレイ１０２へのデータのコピーはキャッシュラインサイズを単位として行われる。メモリ空間はキャッシュラインサイズで分割され、分割された記憶領域（空間）を順番に各エントリに割り当てる。
【００３１】
１６進表記でアドレスA〜アドレス（A＋20）の空間を“A”として示すと、図３に示す例では、例えばメモリ１００における“0x0000”、“0x0100”、“0x0200”、・・・が、メインアレイ１０１の１つのエントリ（第０のエントリ）に割り当てられる。同様に、例えばメモリ１００における“0x0000”、“0x0040”、“0x0080”、“0x00c0”、“0x0100”、・・・が、サブアレイ１０２の１つのエントリ（第０のエントリ）に割り当てられる。
【００３２】
このように、本実施形態ではメモリ空間におけるキャッシュラインサイズで分割した１つの記憶領域を、メインアレイ１０１及びサブアレイ１０２にてそれぞれ１つのエントリに割り当てる。例えば、図３に示した例において、メモリ１００における“0x0000”が、メインアレイ１０１の第０のエントリに割り当てられているとともに、サブアレイ１０２の第０のエントリに割り当てられている。
【００３３】
ただし、本実施形態において、メモリ１００のデータをコピーするときには、メインアレイ１０１の割り当てられたエントリ又はサブアレイ１０２の割り当てられたエントリの一方のブロックに登録される。したがって、メモリ１００におけるあるアドレスのデータのコピーが、メインアレイ１０１とサブアレイ１０２との両方に同時に存在することはない。メモリ１００からメインアレイ１０１、サブアレイ１０２へのデータのコピーは、ＬＲＵアレイに保持されているＬＲＵ情報に基づいて行われる。メインアレイ１０１及びサブアレイ１０２の各々の割り当てられたエントリの各ブロックのうち、最後に使用されてから最も長い時間が経過したブロック（以下、最古ブロックとも称す。）にリプレースすることで、メモリ１００のデータのコピーが行われる。
【００３４】
図４は、本実施形態における動作の一例を示すフローチャートである。図４には、処理部（ＣＰＵコア）２がメモリ空間上のあるアドレスのデータをロードするときのキャッシュ部３の動作について示しており、キャッシュ部３の図示しないキャッシュ制御部による制御等に基づいて実行される。
【００３５】
ステップＳ１１で、処理部（ＣＰＵコア）２がメモリ４にアクセスするために、処理部２からアクセス先を示すアドレスが送られると、ステップＳ１２で、当該アドレスを用いて、キャッシュ部３内のメインアレイ１０及びサブアレイ２０が同時に参照される。
【００３６】
ステップＳ１２では、メインアレイ１０のエントリ数に応じたアドレス中のインデックス部に基づいてメインタグアレイ１２が参照されるとともに、サブアレイ２０のエントリ数に応じたアドレス中のインデックス部に基づいてサブタグアレイ２２が参照される。そして、メインタグアレイ１２及びサブタグアレイ２２の各ウェイにおいてインデックスに対応するブロックからタグが読み出され、読み出されたタグとアドレス中のタグ部のビットパターンとがウェイ毎に比較器１６、２６によって比較される。
【００３７】
比較の結果、メインタグアレイ１２及びサブタグアレイ２２のウェイのいずれかにおいて、読み出されたタグとアドレス中のタグ部のビットパターンとが一致する場合には、キャッシュヒットであると判定し（ステップＳ１３のＹ）、ステップＳ１４に進む。一方、比較の結果、メインタグアレイ１２及びサブタグアレイ２２のいずれのウェイにおいても、読み出されたタグとアドレス中のタグ部のビットパターンとが一致しない場合には、キャッシュミスであると判定し（ステップＳ１３のＮ）、ステップＳ１５に進む。
【００３８】
ステップＳ１４では、メインデータアレイ１４又はサブデータアレイ２４にてインデックスに対応し、かつ読み出されたタグとアドレス中のタグ部のビットパターンとが一致したウェイに対応するブロックから読み出されたデータが、選択回路１８、２８より出力データとして出力される。また、出力されるデータが読み出されたブロックを、使用されてから最も時間が経過していないブロック（以下、最新ブロックとも称す。）とするようＬＲＵアレイ３０に保持されているＬＲＵ情報の更新を行い、動作を終了する。
【００３９】
一方、ステップＳ１５では、図５に示すＬＲＵ参照動作処理を行う。ＬＲＵ参照動作処理では、ＬＲＵアレイ３０に保持されているＬＲＵ情報を参照して、メインアレイ１０及びサブアレイ２０のブロックのうちから、既に登録されているデータのコピー及びそれに対応するタグを破棄するブロック（最古ブロック）を決定する。
【００４０】
図５は、図４に示したステップＳ１５でのＬＲＵ参照動作処理の流れを示すフローチャートである。
ステップＳ２１で、アクセス先を示すアドレスに対応するＬＲＵ情報がＬＲＵアレイ３０より読み出される。すなわち、ＬＲＵアレイ３０に保持されているＬＲＵ情報のなかから、アクセス先のアドレスを割り当てたメインアレイ１０及びサブアレイ２０のエントリでのウェイの古さ順が情報として含まれるＬＲＵ情報が読み出される。
【００４１】
ステップＳ２２で、ステップＳ２１において読み出したＬＲＵ情報を参照してメインアレイとサブアレイに跨って最古ブロックを決定し、メモリ４から読み出したデータのコピーがリプレースされる置き換え対象ブロックとする。
【００４２】
図４に戻り、ステップＳ１６では、メモリ４に対するアクセスが実行され、アクセス先を示すアドレスに対応するメモリ４の記憶領域からデータが読み出されて処理部２に供給される。また、メモリ４から読み出されたデータのコピー及びそれに対応するタグが、ステップＳ１５におけるＬＲＵ参照動作処理で決定された最古ブロックに登録（リプレース）される。そして、データのコピー及びタグがリプレースされた最古ブロックを、最新ブロックとするようＬＲＵアレイ３０に保持されているＬＲＵ情報の更新を行い、動作を終了する。
【００４３】
本実施形態によれば、エントリ数が異なるメインアレイ１０とサブアレイ２０とを設け、メモリ空間をキャッシュラインサイズで分割した１つの領域を、メインアレイ１０及びサブアレイ２０のそれぞれにて１つのエントリに割り当てる。
【００４４】
例えば、図６（Ａ）に示すようにメインアレイ（ウェイ数２）のブロックｍｗ００、ｍｗ１０からなる第０のエントリが割り当てられるアドレスについては、サブアレイ（ウェイ数４）のブロックｓｗ００、ｓｗ１０、ｓｗ２０、ｓｗ３０からなる第０のエントリが割り当てられる。また、メインアレイのブロックｍｗ０２、ｍｗ１２からなる第２のエントリが割り当てられるアドレスについては、サブアレイの第０のエントリが割り当てられる。メインアレイのブロックｍｗ０４、ｍｗ１４からなる第４のエントリが割り当てられるアドレス、及びメインアレイのブロックｍｗ０６、ｍｗ１６からなる第６のエントリが割り当てられるアドレスのそれぞれについても、サブアレイの第０のエントリが割り当てられる。
【００４５】
すなわち、サブアレイの第０のエントリは、メインアレイにおける第０のエントリ、第２のエントリ、第４のエントリ、及び第６のエントリの４つのエントリにより共有されることとなる。このように構成することで、メインアレイの４つのエントリがサブアレイの１つのエントリを取り合うような仕組みを実現でき、メインアレイのエントリに対してサブアレイのエントリの各ブロック（ウェイ）を動的に割り当てることができる。これにより、すべてのエントリに対して一様にウェイ数を増減させるのではなく、各エントリ単位で個別にウェイ数を動的に増減させることができる。
【００４６】
例えば、メインアレイのウェイ数をｍ、サブアレイのウェイ数をｎとすると、メインアレイの各エントリのウェイ数は、論理的に最小でｍ、最大で（ｍ＋ｎ）となるように動的に変更可能である。図６に示した例では、図６（Ｂ）に示すように各エントリのウェイ数を最小でメインアレイによる２ウェイとなり、最大でメインアレイとサブアレイによる６ウェイとなるように動的に変更することができる。したがって、アプリケーションの実行中に、ハードウェアが自動的に判定して当該アプリケーションに応じてエントリ単位で動的にウェイ数を増減し最適なウェイ数に自動で変更することができ、キャッシュの利用効率やヒット率を向上させることができる。
【００４７】
本実施形態によれば、サブアレイを設けることによるウェイ数の増加により、メインアレイのみの従来の方式では、キャッシュミスになってしまうようなケースでも、キャッシュヒットとなるケースが増加し、ヒット率を向上させることができる。また、同一データアレイサイズ（データアレイの総ブロック数を同じとした場合）での本実施形態と従来方式とを比較すると、エントリ数を本実施形態におけるサブアレイに合わせた従来の構成と比較すると、比較器の数を少なくできる。
【００４８】
また、同一データアレイサイズ（データアレイの総ブロック数を同じとした場合）での本実施形態と従来方式とを比較すると、必要とするエントリにサブアレイのブロックが動的に割り当てられることができるため、キャッシュの利用効率及びヒット率を向上させることができる。例えば、例示したようなメインアレイを８エントリ、２ウェイとし、サブアレイを２エントリ、４ウェイとした本実施形態におけるキャッシュ部と、８エントリ、３ウェイの従来のキャッシュ部とを比較する。このとき、従来においてはウェイサイズに相当する３回以上同じインデックスに対応するエントリにアクセスするとキャッシュミスとなってしまうが、本実施形態では最大で６回アクセスしてもキャッシュミスとならないことがありヒット率を向上させることができる。
【００４９】
なお、前述した実施形態では、メインアレイのエントリに対してサブアレイのエントリのブロック（ウェイ）のすべてを動的に割り当てるようにしているが、あるブロック（ウェイ）についてメインアレイのあるエントリに固定して割り当てるようにしても良い。
【００５０】
次に、ＬＲＵアレイ３０に保持されるＬＲＵ情報について説明する。
キャッシュミスとなった場合には、キャッシュ部３にてデータのコピー及びタグの追い出しとリプレースがＬＲＵ情報に基づいて行われる。本実施形態では、メインアレイの複数のエントリがサブアレイの１つのエントリを取り合うこととなるため、サブアレイのエントリ数毎にメインアレイを分割して、それらが横に並んでいるとみなしてその総ウェイ数でのＬＲＵ情報とする。
【００５１】
例えば、図７（Ａ）に示すように、メインアレイが８エントリ、２ウェイであるとし、サブアレイが２エントリ、４ウェイであるとすると、ＬＲＵ情報は、図７（Ｂ）に示すようにエントリが配置されているとみなしたときのウェイの古さ順を示す。すなわち、メインアレイの第０のエントリ、第２のエントリ、第４のエントリ、第６のエントリ、及びサブアレイの第０のエントリを１組としたＬＲＵ情報がＬＲＵアレイに保持される。同様に、メインアレイの第１のエントリ、第３のエントリ、第５のエントリ、第７のエントリ、及びサブアレイの第１のエントリを１組としたＬＲＵ情報がＬＲＵアレイに保持される。
【００５２】
ここで、ＬＲＵ情報としてウェイの古さ順を単純にエンコードするとＬＲＵ情報のビット数は膨大となる。それを回避するには、例えばＬＲＵ情報を各アレイ内（メインアレイ内及びサブアレイ内のそれぞれ）とアレイ間（メインアレイ−サブアレイ間）で分割して保持するようにすれば良く、ＬＲＵ情報のデータ量を低減することができる。例えば、図７に示した例では、図７（Ｃ）に示すように各アレイ内のＬＲＵ情報は２項関係によるエンコードとし、アレイ間のＬＲＵ情報は順序関係によるエンコードとすることで、１組あたりのＬＲＵ情報は４６ビットで構成される。なお、この場合、アレイ間のＬＲＵ情報ではブロック単位ではなく、エントリ単位の最古順の識別が出来ればよい。
【００５３】
ここで、２項関係によるエンコードは、図８（Ａ）に示すように２つのブロック（ウェイ）の新旧関係を１ビットで保持する方法である。図８（Ａ）に示した例では、上位側から順に各ビットが、第０ブロックの第１ブロックに対する新旧関係、第０ブロックの第２ブロックに対する新旧関係、第０ブロックの第３ブロックに対する新旧関係、第１ブロックの第２ブロックに対する新旧関係、第１ブロックの第３ブロックに対する新旧関係、第２ブロックの第３ブロックに対する新旧関係を示している。例えば第ｉブロックの第ｊブロックに対する新旧関係（ｉ，ｊは整数）を示すビットは、第ｉブロックが第ｊブロックより新しいときに値“０”とし、第ｉブロックが第ｊブロックより古いときに値“１”とする。したがって、第２ブロック（最古）、第１ブロック、第０ブロック、第３ブロック（最新）の順に古い場合には、ＬＲＵ情報は“００１０１１”となる。
【００５４】
また、順序関係によるエンコードは、図８（Ｂ）に示すようにブロック番号を古い順にＬＲＵ情報として保持する方法である。第２ブロック（最古）、第１ブロック、第０ブロック、第３ブロック（最新）の順に古い場合には、図８（Ｂ）に示したようにＬＲＵ情報は“１００１００１１”となる。
【００５５】
したがって、図７（Ｃ）に示した例のＬＲＵ情報は、ｍｗ０１、ｍｗ１３、ｍｗ１１、ｍｗ１５、ｓｗ２１、ｓｗ１１、ｍｗ０３、ｍｗ０７、ｍｗ１７、ｓｗ０１、ｍｗ０５、ｓｗ３１の順で古いブロックであることを示している。ｍｗＸＹは、メインアレイにおけるウェイＸ、エントリＹのブロックであることを示し、ｓｗＸＹは、サブアレイにおけるウェイＸ、エントリＹのブロックであることを示す。なお、前述した説明では、ＬＲＵ情報として完全な新旧関係を保持する場合を一例として説明したが、ある程度端折って新旧関係を保持するようにしても良い。
【００５６】
次に、図９及び図１０を参照して、本実施形態においてキャッシュ部３のメインアレイ及びサブアレイにて各ウェイが動的にどのように割り当てられるかの具体的な動作例について説明する。以下では、図９（Ａ）に示すプログラム列が実行されたときを一例として示す。また、簡単のためキャッシュ構成は、キャッシュラインサイズが１６バイトであり、図９（Ｂ）に示すようにメインアレイが８エントリ、２ウェイであり、サブアレイが２エントリ、４ウェイであるとして説明する。
【００５７】
図９（Ａ）に示したプログラム列において“ＬＤ＠（ａｄｄ），Ｒ１”は、アドレスａｄｄのデータを読み出してレジスタＲ１へ書き込む処理を示している。また、以下では、メインアレイにおけるウェイｗａｙＸ、エントリ０ｘＹブロックをｍｗＸＹと示し、サブアレイにおけるウェイｗａｙＸ、エントリ０ｘＹブロックをｓｗＸＹと示す。例えば、メインアレイにおけるウェイｗａｙ１のエントリ０ｘ３のブロックはｍｗ１３と示し、サブアレイにおけるウェイｗａｙ２のエントリ０ｘ１のブロックはｓｗ２１と示す。また、メインアレイのエントリ０ｘ１、０ｘ３、０ｘ５、０ｘ７、サブアレイのエントリ０ｘ１を１組とするＬＲＵ情報（旧から新への昇順、以下同様）の初期値は、ｍｗ０１、ｍｗ１１、ｍｗ０３、ｍｗ１３、ｍｗ０５、ｍｗ１５、ｍｗ０７、ｍｗ１７、ｓｗ０１、ｓｗ１１、ｓｗ２１、ｓｗ３１であるとする。
【００５８】
“ＬＤ＠（０ｘ５１０１８），Ｒ１”の命令まで処理したときの様子を図１０（Ａ）に示す。ブロックｍｗ０１にはアドレス０ｘ１１０１＿のデータがコピーされている。（‘＿’（アンダーバー）は命令がアクセスする当該アドレスのワードデータを含むキャッシュラインサイズで分割されたデータを示す。）また、ブロックｍｗ１１、ｍｗ０７にはアドレス０ｘ２１０１＿、０ｘ１２０７＿のデータがそれぞれコピーされ、ブロックｓｗ０１、ｓｗ１１、ｓｗ２１にはアドレス０ｘ１ａ０１＿、０ｘ１３０１＿、０ｘ５１０１＿のデータがそれぞれコピーされている。また、このときＬＲＵ情報は、ｍｗ０３、ｍｗ１３、ｍｗ０５、ｍｗ１５、ｍｗ１７、ｓｗ３１、ｍｗ０１、ｍｗ１１、ｍｗ０７、ｓｗ０１、ｓｗ１１、ｓｗ２１である。
【００５９】
次に、“ＬＤ＠（０ｘ１１０１８），Ｒ１”の命令が実行されるが、アドレス０ｘ１１０１＿のデータのコピーはメインアレイのブロックｍｗ０１に存在するため、キャッシュヒットとなる。したがって、メインアレイ及びサブアレイについてデータの変更はなく、ＬＲＵ情報の更新が行われる。ＬＲＵ情報は、ｍｗ０３、ｍｗ１３、ｍｗ０５、ｍｗ１５、ｍｗ１７、ｓｗ３１、ｍｗ１１、ｍｗ０７、ｓｗ０１、ｓｗ１１、ｓｗ２１、ｍｗ０１と更新される。
【００６０】
続いて、“ＬＤ＠（０ｘａｂ０７８），Ｒ１”、“ＬＤ＠（０ｘ２２０７０），Ｒ１”、の命令が実行される。“ＬＤ＠（０ｘ２２０７０），Ｒ１”の命令の処理完了後の様子を図１０（Ｂ）に示す。図１０（Ａ）に示した状態との違いは、ブロックｍｗ１７にアドレス０ｘａｂ０７＿のデータがコピーされ、ブロックｓｗ３１にアドレス０ｘ２２０７＿のデータがコピーされている点である。命令の実行に伴ってＬＲＵ情報が更新され、このときＬＲＵ情報は、ｍｗ０３、ｍｗ１３、ｍｗ０５、ｍｗ１５、ｍｗ１１、ｍｗ０７、ｓｗ０１、ｓｗ１１、ｓｗ２１、ｍｗ０１、ｍｗ１７、ｓｗ３１である。
【００６１】
次に、“ＬＤ＠（０ｘａｂ０７０），Ｒ１”の命令が実行されるが、アドレス０ｘａｂ０７＿のデータのコピーはメインアレイのブロックｍｗ１７に存在するため、キャッシュヒットとなる。したがって、メインアレイ及びサブアレイについてデータの変更はなく、ＬＲＵ情報の更新が行われる。ＬＲＵ情報は、ｍｗ０３、ｍｗ１３、ｍｗ０５、ｍｗ１５、ｍｗ１１、ｍｗ０７、ｓｗ０１、ｓｗ１１、ｓｗ２１、ｍｗ０１、ｓｗ３１、ｍｗ１７と更新される。
【００６２】
次に、“ＬＤ＠（０ｘｃｂ０７０），Ｒ１”の命令が実行される。このとき、アドレス０ｘｃｂ０７＿のデータのコピーはメインアレイ及びサブアレイには存在せず、キャッシュミスとなる。これにより、メモリよりアドレス０ｘｃｂ０７＿のデータが読み出され最古ブロックにリプレースされる。ただし、リプレース可能なブロックは、アクセスされたアドレス（０ｘｃｂ０７＿）に対応するメインアレイのブロック、すなわちブロックｍｗ０７、ｍｗ１７、及びサブアレイのブロックｓｗ０１、ｓｗ１１、ｓｗ２１、ｓｗ３１である。したがって、ＬＲＵ情報に基づいて、そのなかの最古ブロックｍｗ０７にアドレス０ｘｃｂ０７＿のデータがコピーされる。また、ＬＲＵ情報の更新が行われ、ＬＲＵ情報は、ｍｗ０３、ｍｗ１３、ｍｗ０５、ｍｗ１５、ｍｗ１１、ｓｗ０１、ｓｗ１１、ｓｗ２１、ｍｗ０１、ｓｗ３１、ｍｗ１７、ｍｗ０７となる。
【００６３】
次に、“ＬＤ＠（０ｘ２ｂ０７０），Ｒ１”の命令が実行されるが、この場合もキャッシュミスとなり、メモリからアドレス０ｘ２ｂ０７＿のデータが読み出され最古ブロックにリプレースされる。リプレース可能なブロックは、アクセスされたアドレス（０ｘ２ｂ０７＿）に対応するメインアレイのブロック、すなわちブロックｍｗ０７、ｍｗ１７、及びサブアレイのブロックｓｗ０１、ｓｗ１１、ｓｗ２１、ｓｗ３１である。したがって、ＬＲＵ情報に基づいて、そのなかの最古ブロックｓｗ０１にアドレス０ｘ２ｂ０７＿のデータがコピーされ、図１０（Ｃ）に示すようになる。また、ＬＲＵ情報の更新が行われ、ＬＲＵ情報は、ｍｗ０３、ｍｗ１３、ｍｗ０５、ｍｗ１５、ｍｗ１１、ｓｗ１１、ｓｗ２１、ｍｗ０１、ｓｗ３１、ｍｗ１７、ｍｗ０７、ｓｗ０１となる。
【００６４】
なお、キャッシュ部がメインアレイとサブアレイの２つのアレイを有する場合を一例として説明したが、これに限定されるものではなく、３つ以上のアレイを有するようにしても良い。複数のデータアレイを持ち、各データアレイのなかで少なくとも１つはエントリ数が異なる（すなわち、データアレイのエントリ数が２種以上）ものであれば良い。そして、アクセス先を示すアドレス中のエントリ数に応じたビット数のインデックス部に基づいて同時に複数のアレイを参照するとともに、メモリ空間上のあるアドレスのデータのコピーがある時間においては２以上のデータアレイに同時に存在しないようにする。また、エントリ数が最大であるデータアレイのエントリ数は、他のデータアレイのエントリ数の整数倍であることが好ましい。また、ウェイ数についても２、４としたアレイを一例として示したが、これに限定されることなく、ウェイ数は任意である。なお、ウェイ数を１、すなわちダイレクトマッピング方式相当としても良い。
【００６５】
なお、前記実施形態は、何れも本発明を実施するにあたっての具体化のほんの一例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその技術思想、またはその主要な特徴から逸脱することなく、様々な形で実施することができる。
【符号の説明】
【００６６】
１  情報処理装置
２  処理部
３  キャッシュ部
４  メモリ
１０  第１のアレイ（メインアレイ）
２０  第２のアレイ（サブアレイ）
３０  ＬＲＵアレイ
１２、２２  タグアレイ
１４、２４  データアレイ
１６、２６  比較器
１８、２８  選択回路
【図１】
0005434646.tif 000002
【図２】
0005434646.tif 000003
【図３】
0005434646.tif 000004
【図４】
0005434646.tif 000005
【図５】
0005434646.tif 000006
【図６】
0005434646.tif 000007
【図７】
0005434646.tif 000008
【図８】
0005434646.tif 000009
【図９】
0005434646.tif 000010
【図１０】
0005434646.tif 000011
【図１１】
0005434646.tif 000012