(57)【要約】キャッシュメモリを、ＣＡＭ構成で、格納されているデータブロックの先頭アドレスを示す先頭ポインタを格納するＣＡＭ部と、ＣＡＭ部に格納されている先頭ポインタからの、データブロックを構成するデータのアドレスを示すポインタ間の一連の接続関係を格納するポインタマップメモリと、ポインタで示されたアドレスのデータを格納するポインタデータメモリで構成する。ポインタの接続関係を自由に設定可能であるため、キャッシュメモリに格納されるデータブロックの大きさを自由に設定でき、キャッシュメモリに使用率を向上することができる。
2004077299.tif 000002
【特許請求の範囲】
【請求項１】
格納されているデータブロックの先頭アドレスに対応する先頭ポインタを格納する先頭ポインタ格納手段と、
該データブロックを構成するデータが格納されているアドレスに対応するポインタと、該先頭ポインタからの該ポインタ間の接続関係を格納するポインタマップ格納手段と、
該ポインタに対応するアドレスに格納されるデータを格納するポインタデータ格納手段と、
からなることを特徴とするキャッシュメモリ。
【請求項２】
前記データブロックは、プロセッサからの指示により、先頭と末尾が決定されたデータ列であることを特徴とする請求項１に記載のキャッシュメモリ。
【請求項３】
前記データブロックは、プログラム内の命令をデコードした結果によって、先頭と末尾が決定されたデータ列であることを特徴とする請求項１に記載のキャッシュメモリ。
【請求項４】
前記命令は、サブルーチンコール及び復帰命令、条件分岐命令、あるいは、例外処理及び復帰命令であることを特徴とする請求項３に記載のキャッシュメモリ。
【請求項５】
前記先頭ポインタ格納手段は、該データブロックの先頭アドレスと、該データブロックのサイズと、該データブロックの先頭ポインタを対応付けて格納することを特徴とする請求項１に記載のキャッシュメモリ。
【請求項６】
前記先頭ポインタ格納手段は、連想記憶メモリ方式を採用した格納手段であることを特徴とする請求項１に記載のキャッシュメモリ。
【請求項７】
使用されていないポインタを保持する空きポインタキュー手段を更に備え、
新たにデータブロックを格納する必要が生じたときは、該空きポインタキュー手段の示す空きポインタを使用することを特徴とする請求項１に記載のキャッシュメモリ。
【請求項８】
新たにデータブロックを格納する必要が生じたが、前記空きポインタキュー手段が、空きポインタを保持していない場合には、現在格納されているデータブロックの１つを破棄することによって、空きポインタを生成することを特徴とする請求項７に記載のキャッシュメモリ。
【請求項９】
前記破棄は、古いデータブロックから順に行われることを特徴とする請求項８に記載のキャッシュメモリ。
【請求項１０】
プロセッサがアクセスすべきデータが格納されておらず、かつ、該データがデータブロックの先頭となるべきデータである場合には、該プロセッサがアクセスすべきデータを先頭とするデータブロックを新たに格納することを特徴とする請求項１に記載のキャッシュメモリ。
【請求項１１】
プロセッサがアクセスすべきデータが格納されておらず、かつ、該データがデータブロックの先頭となるべきデータ以外のデータである場合には、該プロセッサがアクセスすべきデータを含むデータブロックを既に格納されているデータブロックに接続する形で新たに格納することを特徴とする請求項１に記載のキャッシュメモリ。
【請求項１２】
前記先頭ポインタ格納手段の有するデータは、プロセッサの発行する仮想アドレスを物理アドレスに変換する機構の有するデータと一緒に管理されることを特徴とする請求項１に記載のキャッシュメモリ。
【請求項１３】
前記データは、命令データであることを特徴とする請求項１に記載のキャッシュメモリ。
【請求項１４】
格納されているデータブロックの先頭アドレスに対応する先頭ポインタを格納する先頭ポインタ格納ステップと、
該データブロックを構成するデータが格納されているアドレスに対応するポインタと、該先頭ポインタからの該ポインタ間の接続関係を格納するポインタマップ格納ステップと、
該ポインタに対応するアドレスに格納されるデータを格納するポインタデータ格納ステップと、
を有し、
可変長のデータブロックを格納可能としたことを特徴とするキャッシュメモリの制御方法。
【発明の詳細な説明】
【技術分野】  本発明は、キャッシュメモリの構成に関する。
【背景技術】  プロセッサが使用する命令キャッシュメモリ（主記憶（メモリ）からの命令データを一時的に保持し、メモリアクセス遅延を緩和する一時記憶（メモリ））には、ダイレクトマップ、あるいは、Ｎウェイセットアソシエイティブ方式が主に使用されている。これらの方式では、アクセスアドレスのインデックス（キャッシュメモリのエントリ番号に相当するアドレス下位ビット）を用いてキャッシュを索引し、タグ（キャッシュメモリのエントリ数より上位のメモリアドレスと有効ビット）を用いてキャッシュデータの一致判定を行っている。ここで、特定のインデックスを持つプログラムは、同一時刻に２つ以上（Ｎウェイセット方式では、Ｎ＋１個以上）、同一時刻にキャッシュ上に存在することができないため、キャッシュの使用効率が低下するという問題点がある。
図１は、従来技術のダイレクトマップ方式を採用したキャッシュメモリの概念構成を示す図である。
ダイレクトマップキャッシュメモリにおいては、インデックス（キャッシュメモリの記憶領域を表すアドレス）として、２桁の１６進数（０ｘというは１６進数の数であることを表し、同図では、１６進数で００〜ｆｆまでのインデックスが設けられている）を取っている。そして、キャッシュメモリの１つのインデックスで表されるエントリの長さが０ｘ４０バイト、すなわち、６４バイトとなっている。ここで、同図では、主記憶の１６進数のアドレスの内、下位２桁の値によって、そのアドレスのデータをどのキャッシュエントリに格納するかを決めている。例えば、主記憶の０ｘ００００番地のデータは、下位２桁のアドレスとして００を持っており、これは、キャッシュメモリのインデックス０ｘ００で表されるエントリに格納される。また、主記憶のアドレスの下位２桁が８０のデータは、キャッシュメモリのインデックス０ｘ０２のエントリに格納される。このように、主記憶の下位２桁のアドレス値のみを見て、キャッシュメモリへの格納領域を決定しているので、同図に示されるように、主記憶のアドレスが０ｘ１０４０と０ｘ００４０の両方をキャッシュメモリに格納したい場合には、キャッシュメモリにインデックス０ｘ０１のエントリが１つしかないため、格納できないことになる。従って、いずれかのみを格納することになるが、キャッシュメモリに格納しなかった方がプロセッサから呼び出された場合、キャッシュミスが生じ、再び主記憶にアクセスしなければならなくなる。
図２は、従来の２ウェイセットアソシエイティブキャッシュメモリの概念構成図である。
この場合には、主記憶のアドレスの下位２桁のみを検出して、キャッシュメモリ内のどのエントリに格納するかを決定するが、同じインデックスのエントリが２つ設けられる（ウェイ１とウェイ２と呼ばれる）ので、ダイレクトマップキャッシュメモリの時に比べ、キャッシュミスが生じる可能性は小さくなるが、それでも、主記憶のアドレスの下位２桁が同じデータを３つ以上記憶することができないので、やはり、キャッシュミスが生じる。
図３は、従来の連想記憶メモリの概念構成図である。
連想記憶メモリ（ＣＡＭ）を用いれば、Ｎウェイがエントリ数と同一に出来、使用効率の問題を解決可能であるが、回路の増大による高コスト化という問題がある。
同図の場合には、２５６ウェイセットアソシエイティブキャッシュメモリと同等である。すなわち、主記憶のアドレスにおいて、下位２桁が同じアドレスが２５６個である場合には、主記憶のデータを全てキャッシュメモリに記憶可能となるのである。従って、主記憶からキャッシュメモリにデータが格納できないと言うことが無く、従って、キャッシュミスも起きない。しかし、主記憶のデータを全て格納するだけのキャッシュメモリを設けることは、それだけハードウェアが多くなることになり、また、多くのウェイを制御する必要も生じることから、キャッシュメモリ自体が高価になってしまう。
上記のキャッシュメモリの構成については、下記の参照文献を参考にされたい。
”コンピュータアーキテクチャ”第８章［記憶階層の設計］日経ＢＰ社／ＩＳＢＮ４−８２２２−７１５２−８
図４は、従来の４ウェイセットアソシエイティブキャッシュメモリのデータアクセス機構の構成図である。
プログラムカウンタからの命令アクセスリクエスト／アドレス（１）は命令アクセスＭＭＵ１０に送られ、物理アドレス（８）に変換された後、キャッシュタグ１２−１〜１２−４及びキャッシュデータ１３−１〜１３−４にアドレスとして送られる。同一下位アドレス（インデックス）で検索されたタグ出力のうち、タグ出力が示すアドレス上位ビット（タグ）が、命令アクセスＭＭＵ１０からのリクエストアドレスと一致したものがあれば、それはキャッシュデータ１３−１〜１３−４内に有効なデータが存在する（ヒット）ことを示す。これらの一致検出を比較器１５で行い、同時にそのヒット情報（４）でセレクタ１６を起動する。ヒットしていれば、そのデータは命令データ（５）として命令バッファに送られる。ヒットしなかった場合は、キャッシュミスリクエスト（３）として、二次キャッシュに出力される。キャッシュミスリクエスト（３）は、リクエストそのもの（３）−１とミスアドレス（３）−２からなる。その後、二次キャッシュからの戻りデータは、キャッシュタグ１２−１〜１２−４及びキャッシュデータ１３−１〜１３−４を更新し、同様に命令バッファにデータを返す。キャッシュタグ１２−１〜１２−４及びキャッシュデータ１３−１〜１３−４を更新する場合には、書き込みアドレス（７）が命令アクセスＭＭＵ１０から出力される。キャッシュタグ１２−１〜１２−４及びキャッシュデータ１３−１〜１３−４の更新は、タグ更新制御部１１及びデータ更新制御部１４により行われる。Ｎウェイ構成の場合、比較器１５及びセレクタ１６の入力がＮになる。また、ダイレクトマップ構成の場合はセレクタは不要になる。
特開平１１−３２８０１４号公報には、キャッシュメモリの使用効率を上げるために、アドレス空間中における空間局所性の及ぶ範囲の違いに対応するために、アドレス空間毎にブロックサイズを適切に設定する技術が開示されている。
特開２００１−２９７０３６号公報には、ダイレクトマップ方式やセットアソシエイティブ方式と共に用いることのできる、ＲＡＭセットキャッシュを設ける技術が記載されている。ＲＡＭセットキャッシュは、セットアソシエイティブ方式の１つのウェイを構成するように設けられ、行単位の読み書きを行う。
【発明の開示】
本発明の課題は、低コストで使用効率の高いキャッシュメモリを提供することである。
本発明のキャッシュメモリは、格納されているデータブロックの先頭アドレスに対応する先頭ポインタを格納する先頭ポインタ格納手段と、該データブロックを構成するデータが格納されているアドレスに対応するポインタと、該先頭ポインタからの該ポインタ間の接続関係を格納するポインタマップ格納手段と、該ポインタに対応するアドレスに格納されるデータを格納するポインタデータ格納手段とからなることを特徴とする。
本発明によれば、ポインタの接続関係を格納することにより、データをブロックとして格納するようにしている。従って、ポインタの接続関係を変更すれば、可変長のデータブロックを格納可能となる。
すなわち、格納するデータブロックの単位が決定されている従来の方式に比べ、キャッシュメモリの記憶容量を可能な限り有効に使い切ることができ、また、大きなブロック単位で格納すべき場合と小さなブロック単位でよい場合に対して柔軟に対応できる。よって、キャッシュメモリの使用効率が上がり、結果として、キャッシュミスの可能性を小さくすることができる。
【図面の簡単な説明】  図１は、従来技術のダイレクトマップ方式を採用したキャッシュメモリの概念構成を示す図である。
図２は、従来の２ウェイセットアソシエイティブキャッシュメモリの概念構成図である。
図３は、従来の連想記憶メモリの概念構成図である。
図４は、従来の４ウェイセットアソシエイティブキャッシュメモリのデータアクセス機構の構成図である。
図５及び図６は、本発明の概念を説明する図である。
図７は、本発明を含む全体構成図である。
図８は、本発明の実施形態の構成図である。
図９は、プロセッサの命令アクセスＭＭＵのページ管理機構とＣＡＭとを共用する場合の構成を示したものである。
図１０〜図１３は、本発明の実施形態の動作を説明する図である。
【発明を実施するための最良の形態】  図５及び図６は、本発明の概念を説明する図である。
本発明では、プロセッサの命令実行はキャッシュ１エントリ分ではなく、数ブロック〜数十ブロック以上で行われることが多いことに着目した。ＣＡＭを全エントリに対し適用可能ならば、問題は解決可能であるが、高コストになることは前述の通りである。そこで、ＣＡＭをキャッシュエントリごとではなく、命令ブロック単位毎に適用する。具体的には、ある命令ブロックの情報（先頭アドレス、命令ブロックのサイズ、命令ブロックの先頭ポインタの番号）のみＣＡＭ上に保持する（図５参照）。命令データ自体は先頭ポインタで示されるＦＩＦＯ構造のポインタメモリに記憶する（図６参照）。ポインタメモリはポインタマップメモリとポインタデータメモリの２つのメモリから構成され、ポインタマップメモリはポインタ間の接続情報を、ポインタデータメモリはそのポインタにおけるデータそのものを表し、複数のＦＩＦＯを１つのメモリ上に仮想的に構築可能としている。すなわち、記憶領域は、例えば、ＲＡＭなどの連続領域であるが、データの連続性がポインタの接続情報を保持することによって保たれているということである。よって、連続性を持つポインタによって示されるデータは１つのブロックを構成し、ブロック毎に本発明の実施形態のキャッシュメモリに格納されていることになる。ここで、特に、本発明の実施形態のキャッシュメモリは、ポインタの接続情報を操作することによって、格納されるデータのブロックサイズを自由に変更可能となっている。すなわち、物理的なＦＩＦＯが複数用意されているわけではない。本発明における命令キャッシュの読み込みは（１）アドレスからＣＡＭを索引して、アクセスすべきデータが含まれるブロックの先頭アドレスが格納されているポインタを取得する、（２）ポインタマップメモリからアクセスすべきデータが含まれるブロックへのポインタを取得する、（３）ポインタデータメモリから取得したポインタで示されるアドレスの命令データブロックから、アクセスしたい命令データを読み込む、（４）実行する、となる。これにより、命令ブロック毎に異なる長さのデータ記録領域を実装したのと同じキャッシュ使用効率が得られる。また、全エントリにＣＡＭを用いるより索引情報が少ないため回路を相対的に削減することができる。キャッシュミス時は、ＣＡＭにタグをセットすると同時に空きポインタを空きポインタ供給部（不図示）から提供し、メモリからのデータを空きポインタが示すポインタメモリのエントリに書き込む。継続アクセスがプロセッサから要求された場合は、空きポインタを再度供給し、同様にキャッシュに書き込み、２番目のポインタをポインタキューに追加する。空きポインタが枯渇した場合は、古いデータから破棄するなどの方法で命令ブロックを破棄し、空きポインタを確保する。
図７は、本発明を含む全体構成図である。
同図はマイクロプロセッサの概略を示しており、動作は以下のようになる。
１）命令フェッチ
実行するための命令を外部バスより外部バスインターフェース２０を介して獲得する。まず、プログラムカウンタ２１の指し示す命令が命令バッファ２２に存在するかを確認し、ない場合、命令バッファ２２は命令をフェッチする要求を命令アクセスＭＭＵ２３に送る。命令アクセスＭＭＵ２３はプログラムが使用する論理アドレスから、ハードウェアのマッピング順序に依存する物理アドレスに変換する。そのアドレスを用いて命令アクセス一次キャッシュタグ２４を検索し、一致すれば命令アクセス一次キャッシュデータ２５に該当データが存在するため、読み出しアドレスを送り、命令データを命令バッファ２２に返す。存在しない場合は、更に二次キャッシュタグ２６を検索し、なお存在しない場合は外部バスというように要求を発行し、戻りデータを順次、二次キャッシュデータ２７、命令アクセス一次キャッシュデータ２５へと補充する。このとき、補充されたことを二次キャッシュタグ２６、命令アクセス一次キャッシュタグ２４の更新により記憶する。補充されたデータは、命令アクセス一次キャッシュデータ２５に存在しているときと同じ要領で、命令バッファ２２に格納する。
２）命令の実行
命令バッファ２２に格納された命令列は、実行ユニット２８に送られ、それぞれの命令の種別に応じて演算器２９、ロードストアユニット３０に転送される。演算命令や分岐命令は演算器２９の出力を汎用レジスタファイル３１に記録するか、あるいはプログラムカウンタ（不図示）を更新する、といった処理を行う。また、ロードストア命令は、ロードストアユニット３０にて、命令アクセスと同様にデータアクセスＭＭＵ３２−データアクセス一次キャッシュタグ３３−データアクセス一次キャッシュデータ３４と順次アクセスし、そのデータを汎用レジスタファイル３１にコピーするロード命令、あるいは、そのエントリに対し、汎用レジスタファイル３１からコピーするストア命令、と命令に応じて実行する。一次キャッシュにない場合は、命令実行機構と共用の二次キャッシュ、あるいは外部バスよりデータを獲得して、同様に実行する。実行の完了後、プログラムカウンタは逐次加算されるか、あるいは、分岐指示アドレスに更新され、再度１）の命令フェッチを行う。
３）全体
このように命令フェッチ、命令実行を繰り返し、マイクロプロセッサは動作するが本発明では、点線部の命令アクセスＭＭＵ２３、命令アクセス一次キャッシュタグ２４、命令アクセス一次キャッシュデータ２５の新しい構成を提供する。
図８は、本発明の実施形態の構成図である。
プログラムカウンタからの命令アクセスリクエスト／アドレスは命令アクセスＭＭＵ２３に送られ、物理アドレスに変換された後、ＣＡＭ４１にアドレスとして送られる。ＣＡＭ４１はタグ、サイズ、先頭ポインタデータを出力する。アドレス・サイズ判定／ヒット判定ブロック４２では、最終的な希望ポインタの検索を行い、そのポインタが存在した場合はポインタデータを読み出し、そのデータは命令データ（１）として命令バッファ（不図示）に送られる。存在しない場合、キャッシュミスリクエスト（２）として、二次キャッシュに出力される。その後、二次キャッシュからの戻りデータは、ブロック先頭判定ブロック４３を経由し、戻りデータが先頭命令であれば、ＣＡＭ４１の更新を、先頭命令でなければポインタマップメモリ４４の更新とＣＡＭサイズ情報４２の更新と共に、ポインタデータメモリ４５を更新し、同様に命令バッファにデータを返す。ブロック先頭判定ブロック４３では、書き込みに際し、空きポインタＦＩＦＯ４６からの空きポインタの供給を受けるが、枯渇してしまった場合は、空きポインタＦＩＦＯ４６から破棄ポインタ選択制御ブロック４７に指示が送られ、任意のＣＡＭエントリに破棄指示を行う。その出力はアドレス・サイズ判定／ヒット判定ブロック４２で無効化され、空きポインタＦＩＦＯ４６に返却される。
図９は、プロセッサの命令アクセスＭＭＵのページ管理機構とＣＡＭとを共用する場合の構成を示したものである。
なお、同図において、図８と同じ構成要素には同じ参照符号を付して、説明を省略する。
この構成は、ＭＭＵのアドレス変換単位（ページ）とキャッシュの管理単位を同一サイズにすることにより、ＭＭＵ内のＣＡＭに同一機能を持たせ、ＣＡＭの削減をはかったものである（同図の５０）。すなわち、命令アクセスＭＭＵでは、仮想アドレスを物理アドレスに変換するテーブルを有しているわけであるが、このテーブルと、ＣＡＭのテーブルとを１つのテーブルに併合し、命令アクセスＭＭＵの機構で、ＣＡＭの検索などの動作を行うようにしたものである。これによれば、テーブルの検索機構を命令アクセスＭＭＵとＣＡＭの検索機構を１つのハードウェアで扱うことができるので、ハードウェアの削減となる。
また、本発明の実施形態においては、キャッシュメモリに読み込む命令データを一塊りずつ格納するので、プログラムをブロック化して読み込む必要がある。この場合、命令がプロセッサが読み込んだとき、読み込んだ命令がサブルーチンコール及びその復帰命令、条件分岐命令、例外処理及びその復帰命令であると判断した場合には、プログラムの先頭あるいは最後であると判断して、その命令間のブロックを単位としてキャッシュメモリに格納する。このように、プログラムの内容に従って、読み込む命令をブロック化してキャッシュメモリに読み込む場合は、ブロックの大きさが、読み込む度に異なることになるが、本発明の実施形態によれば、ポインタを用いて、可変長のブロックをメモリ上に構成可能であるので、このような方法が採用できる。あるいは、ブロックの大きさを強制的に決定し、順次プログラムの命令をデコードする際に、任意の命令をブロックの先頭とし、所定の大きさのブロックが得られた時点で、最後の命令をブロックの最後の命令とするような方法が可能である。この場合、図８、９のブロック先頭判定の命令デコードを変更するだけで、任意のブロック化方法が採用可能である。例えば、プログラムの記述に従ってブロック化する場合には、ＣＡＬＬ命令／レジスタライト命令等を判定して、ブロックの先頭と判断することになる。
本発明の実施形態においては、プロセッサで命令ブロックの先頭と末尾を検出し、命令ブロックＣＡＭに制御信号を送出する。本制御機構では、先頭信号を受け取ると、キャッシュタグを記録し、主記憶よりデータを獲得し、ポインタが示すキャッシュアドレスに命令を書き込む。プロセッサの要求が１キャッシュエントリに達する毎に、空きポインタキューより空きエントリを補充し、そのエントリ番号をキャッシュタグ・キューに追加すると同時に、命令ブロックサイズを加算する。同一ブロックを複数回、またはブロック内の途中に分岐する場合は、キャッシュタグ＋サイズからエントリ番号を割り出し、アクセスを行う。また、上記において、命令ブロックの先頭と末尾の通知を特定のレジスタアクセスで通知する。この場合、命令によるブロックの明示的開始／終了を宣言する必要がある。これは、前述した、プログラムの中で命令によらず、強制的にブロック化する場合である。
図１０〜図１３は、本発明の実施形態の動作を説明する図である。
図１０は、本発明の実施形態に従ったキャッシュメモリに命令が存在した場合、すなわち、命令ヒットの場合の動作である。
プロセッサ６０から、アクセスすべき命令データのアドレスが出力されると、ＣＡＭ部６１を検索して、アクセスすべき命令データを含むブロックの先頭ポインタを検索する。命令ヒットの場合には、アクセスすべき命令データを含むブロックの先頭ポインタが存在した場合である。次には、得られた先頭ポインタから、ポインタマップメモリ６２を検索し、ブロックを構成する命令データのポインタを全て取得する。そして、取得したポインタを用いて、ポインタデータメモリ６３から命令データを取得し、プロセッサ６０に返す。
図１１は、本発明の実施形態に従ったキャッシュメモリに命令が存在しない、すなわち、命令ミスの場合であって、アクセスすべき命令がブロックの先頭に有るべき場合を示している。
この場合、プロセッサ６０からアドレス指定が行われ、命令データへのアクセスが試みられる。ＣＡＭ部６１では、このアドレスに従ってポインタを検索するが、今の場合、対応する命令が含まれているブロックが無く、しかも、対応する命令がブロックの先頭となるべきものであると判断される。この場合、空きポインタキュー６４から、空きのポインタを獲得し、主記憶から当該命令データを含むブロックを読み込み、ＣＡＭの先頭ポインタで示される先頭アドレスを更新する。また、ポインタマップメモリ６２も、獲得された空きポインタをブロックとして関連付けて、ポインタデータメモリ６３は、各ポインタに主記憶から読み込まれた命令データを対応付けて、命令データをプロセッサ６０に返す。空きポインタキュー６４は、通常のＦＩＦＯによるポインタデータバッファであり、初期値は、ポインタが０から最大値まで記録されるものである。
図１２は、アクセスすべき命令データが本発明の実施形態に従ったキャッシュメモリに存在せず、命令データがブロックの先頭以外の場所に存在すべきものである場合の動作を示す図である。
プロセッサ６０からアドレスが出力され、ＣＡＭ部６１で命令データの検索をするが、キャッシュメモリに存在しないと判断される。すると、空きポインタキュー６４から空きポインタを取得し、主記憶から当該命令データを含むブロックを読み込む。そして、当該ブロックに隣接する、既にＣＡＭ部６１に登録されているブロックに、読み込んだブロックをつなげる要領で、ＣＡＭ部６１のブロックサイズを更新し、ポインタマップメモリ６２を更新し、ポインタデータメモリ６３が、読み込んだブロックの命令データを格納し、命令データをプロセッサ６０に返す。
図１３は、命令データのブロックを読み込む必要があるが、空きポインタがない場合の動作を示す図である。
プロセッサ６０から命令データへのアクセスがＣＡＭ部６１になされる。しかし、命令データがキャッシュメモリ内にないと判断される。更に、主記憶から命令データのブロックを読み込むために空きポインタキューから空きポインタを獲得しようとするが、空きポインタがないため、任意の１ブロックを破棄する命令が出される。ポインタマップメモリ６２は、ポインタマップから１ブロック分を破棄し、破棄したポインタを空きポインタキュー６４に通知する。これにより、空きポインタキュー６４は、空きポインタを獲たので、これをＣＡＭ部６１に通知して、主記憶から新しい命令データブロックを読み込む。
【産業上の利用可能性】  本発明による、キャッシュメモリの構成としてＣＡＭを採用するよりも少ない回路量で、キャッシュ使用効率を大幅に改善したキャッシュメモリ機構を提供可能となる。
【図１】
2004077299.tif 000003
【図２】
2004077299.tif 000004
【図３】
2004077299.tif 000005
【図４】
2004077299.tif 000006
【図５】
2004077299.tif 000007
【図６】
2004077299.tif 000008
【図７】
2004077299.tif 000009
【図８】
2004077299.tif 000010
【図９】
2004077299.tif 000011
【図１０】
2004077299.tif 000012
【図１１】
2004077299.tif 000013
【図１２】
2004077299.tif 000014
【図１３】
2004077299.tif 000015
【手続補正書】
【提出日】平成17年7月25日(2005.7.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
格納されているデータブロックの先頭アドレスに対応する先頭ポインタを格納する先頭ポインタ格納手段と、
該データブロックを構成するデータが格納されているアドレスに対応するポインタと、該先頭ポインタからの該ポインタ間の接続関係を格納するポインタマップ格納手段と、
該ポインタに対応するアドレスに格納されるデータを格納するポインタデータ格納手段と、
を備え、
前記先頭ポインタ格納手段は、連想記憶メモリ方式を採用した格納手段であることを特徴とするキャッシュメモリ。
【請求項２】
前記データブロックは、プロセッサからの指示により、先頭と末尾が決定されたデータ列であることを特徴とする請求項１に記載のキャッシュメモリ。
【請求項３】
前記データブロックは、プログラム内の命令をデコードした結果によって、先頭と末尾が決定されたデータ列であることを特徴とする請求項１に記載のキャッシュメモリ。
【請求項４】
前記命令は、サブルーチンコール及び復帰命令、条件分岐命令、あるいは、例外処理及び復帰命令であることを特徴とする請求項３に記載のキャッシュメモリ。
【請求項５】
前記先頭ポインタ格納手段は、該データブロックの先頭アドレスと、該データブロックのサイズと、該データブロックの先頭ポインタを対応付けて格納することを特徴とする請求項１に記載のキャッシュメモリ。
【請求項６】
使用されていないポインタを保持する空きポインタキュー手段を更に備え、
新たにデータブロックを格納する必要が生じたときは、該空きポインタキュー手段の示す空きポインタを使用することを特徴とする請求項１に記載のキャッシュメモリ。
【請求項７】
新たにデータブロックを格納する必要が生じたが、前記空きポインタキュー手段が、空きポインタを保持していない場合には、現在格納されているデータブロックの１つを破棄することによって、空きポインタを生成することを特徴とする請求項６に記載のキャッシュメモリ。
【請求項８】
前記破棄は、古いデータブロックから順に行われることを特徴とする請求項８に記載のキャッシュメモリ。
【請求項９】
プロセッサがアクセスすべきデータが格納されておらず、かつ、該データがデータブロックの先頭となるべきデータである場合には、該プロセッサがアクセスすべきデータを先頭とするデータブロックを新たに格納することを特徴とする請求項１に記載のキャッシュメモリ。
【請求項１０】
プロセッサがアクセスすべきデータが格納されておらず、かつ、該データがデータブロックの先頭となるべきデータ以外のデータである場合には、該プロセッサがアクセスすべきデータを含むデータブロックを既に格納されているデータブロックに接続する形で新たに格納することを特徴とする請求項１に記載のキャッシュメモリ。
【請求項１１】
前記先頭ポインタ格納手段の有するデータは、プロセッサの発行する仮想アドレスを物理アドレスに変換する機構の有するデータと一緒に管理されることを特徴とする請求項１に記載のキャッシュメモリ。
【請求項１２】
前記データは、命令データであることを特徴とする請求項１に記載のキャッシュメモリ。
【請求項１３】
格納されているデータブロックの先頭アドレスに対応する先頭ポインタを格納する先頭ポインタ格納ステップと、
該データブロックを構成するデータが格納されているアドレスに対応するポインタと、該先頭ポインタからの該ポインタ間の接続関係を格納するポインタマップ格納ステップと、
該ポインタに対応するアドレスに格納されるデータを格納するポインタデータ格納ステップと、
を有し、
可変長のデータブロックを格納可能としたことを特徴とするキャッシュメモリの制御方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュメモリの構成に関する。
【背景技術】
【０００２】
プロセッサが使用する命令キャッシュメモリ（主記憶（メモリ）からの命令データを一時的に保持し、メモリアクセス遅延を緩和する一時記憶（メモリ））には、ダイレクトマップ、あるいは、Ｎウェイセットアソシエイティブ方式が主に使用されている。これらの方式では、アクセスアドレスのインデックス（キャッシュメモリのエントリ番号に相当するアドレス下位ビット）を用いてキャッシュを索引し、タグ（キャッシュメモリのエントリ数より上位のメモリアドレスと有効ビット）を用いてキャッシュデータの一致判定を行っている。ここで、特定のインデックスを持つプログラムは、同一時刻に２つ以上（Ｎウェイセット方式では、Ｎ＋１個以上）、同一時刻にキャッシュ上に存在することができないため、キャッシュの使用効率が低下するという問題点がある。
【０００３】
図１は、従来技術のダイレクトマップ方式を採用したキャッシュメモリの概念構成を示す図である。
ダイレクトマップキャッシュメモリにおいては、インデックス（キャッシュメモリの記憶領域を表すアドレス）として、２桁の１６進数（０ｘというは１６進数の数であることを表し、同図では、１６進数で００〜ｆｆまでのインデックスが設けられている）を取っている。そして、キャッシュメモリの１つのインデックスで表されるエントリの長さが０ｘ４０バイト、すなわち、６４バイトとなっている。ここで、同図では、主記憶の１６進数のアドレスの内、下位２桁の値によって、そのアドレスのデータをどのキャッシュエントリに格納するかを決めている。例えば、主記憶の０ｘ００００番地のデータは、下位２桁のアドレスとして００を持っており、これは、キャッシュメモリのインデックス０ｘ００で表されるエントリに格納される。また、主記憶のアドレスの下位２桁が８０のデータは、キャッシュメモリのインデックス０ｘ０２のエントリに格納される。このように、主記憶の下位２桁のアドレス値のみを見て、キャッシュメモリへの格納領域を決定しているので、同図に示されるように、主記憶のアドレスが０ｘ１０４０と０ｘ００４０の両方をキャッシュメモリに格納したい場合には、キャッシュメモリにインデックス０ｘ０１のエントリが１つしかないため、格納できないことになる。従って、いずれかのみを格納することになるが、キャッシュメモリに格納しなかった方がプロセッサから呼び出された場合、キャッシュミスが生じ、再び主記憶にアクセスしなければならなくなる。
【０００４】
図２は、従来の２ウェイセットアソシエイティブキャッシュメモリの概念構成図である。
この場合には、主記憶のアドレスの下位２桁のみを検出して、キャッシュメモリ内のどのエントリに格納するかを決定するが、同じインデックスのエントリが２つ設けられる（ウェイ１とウェイ２と呼ばれる）ので、ダイレクトマップキャッシュメモリの時に比べ、キャッシュミスが生じる可能性は小さくなるが、それでも、主記憶のアドレスの下位２桁が同じデータを３つ以上記憶することができないので、やはり、キャッシュミスが生じる。
【０００５】
図３は、従来の連想記憶メモリの概念構成図である。
連想記憶メモリ（ＣＡＭ）を用いれば、Ｎウェイがエントリ数と同一に出来、使用効率の問題を解決可能であるが、回路の増大による高コスト化という問題がある。
【０００６】
同図の場合には、２５６ウェイセットアソシエイティブキャッシュメモリと同等である。すなわち、主記憶のアドレスにおいて、下位２桁が同じアドレスが２５６個である場合には、主記憶のデータを全てキャッシュメモリに記憶可能となるのである。従って、主記憶からキャッシュメモリにデータが格納できないと言うことが無く、従って、キャッシュミスも起きない。しかし、主記憶のデータを全て格納するだけのキャッシュメモリを設けることは、それだけハードウェアが多くなることになり、また、多くのウェイを制御する必要も生じることから、キャッシュメモリ自体が高価になってしまう。
【０００７】
上記のキャッシュメモリの構成については、下記の参照文献を参考にされたい。
”コンピュータアーキテクチャ”第８章［記憶階層の設計］日経ＢＰ社／ＩＳＢＮ４−８２２２−７１５２−８
図４は、従来の４ウェイセットアソシエイティブキャッシュメモリのデータアクセス機構の構成図である。
【０００８】
プログラムカウンタからの命令アクセスリクエスト／アドレス（１）は命令アクセスＭＭＵ１０に送られ、物理アドレス（８）に変換された後、キャッシュタグ１２−１〜１２−４及びキャッシュデータ１３−１〜１３−４にアドレスとして送られる。同一下位アドレス（インデックス）で検索されたタグ出力のうち、タグ出力が示すアドレス上位ビット（タグ）が、命令アクセスＭＭＵ１０からのリクエストアドレスと一致したものがあれば、それはキャッシュデータ１３−１〜１３−４内に有効なデータが存在する（ヒット）ことを示す。これらの一致検出を比較器１５で行い、同時にそのヒット情報（４）でセレクタ１６を起動する。ヒットしていれば、そのデータは命令データ（５）として命令バッファに送られる。ヒットしなかった場合は、キャッシュミスリクエスト（３）として、二次キャッシュに出力される。キャッシュミスリクエスト  （３）は、リクエストそのもの（３）−１とミスアドレス（３）−２からなる。その後、二次キャッシュからの戻りデータは、キャッシュタグ１２−１〜１２−４及びキャッシュデータ１３−１〜１３−４を更新し、同様に命令バッファにデータを返す。キャッシュタグ１２−１〜１２−４及びキャッシュデータ１３−１〜１３−４を更新する場合には、書き込みアドレス（７）が命令アクセスＭＭＵ１０から出力される。キャッシュタグ１２−１〜１２−４及びキャッシュデータ１３−１〜１３−４の更新は、タグ更新制御部１１及びデータ更新制御部１４により行われる。Ｎウェイ構成の場合、比較器１５及びセレクタ１６の入力がＮになる。また、ダイレクトマップ構成の場合はセレクタは不要になる。
【０００９】
特開平１１−３２８０１４号公報には、キャッシュメモリの使用効率を上げるために、アドレス空間中における空間局所性の及ぶ範囲の違いに対応するために、アドレス空間毎にブロックサイズを適切に設定する技術が開示されている。
【００１０】
特開２００１−２９７０３６号公報には、ダイレクトマップ方式やセットアソシエイティブ方式と共に用いることのできる、ＲＡＭセットキャッシュを設ける技術が記載されている。ＲＡＭセットキャッシュは、セットアソシエイティブ方式の１つのウェイを構成するように設けられ、行単位の読み書きを行う。
【発明の開示】
【００１１】
本発明の課題は、低コストで使用効率の高いキャッシュメモリを提供することである。
本発明のキャッシュメモリは、格納されているデータブロックの先頭アドレスに対応する先頭ポインタを格納する先頭ポインタ格納手段と、該データブロックを構成するデータが格納されているアドレスに対応するポインタと、該先頭ポインタからの該ポインタ間の接続関係を格納するポインタマップ格納手段と、該ポインタに対応するアドレスに格納されるデータを格納するポインタデータ格納手段とからなることを特徴とする。
【００１２】
本発明によれば、ポインタの接続関係を格納することにより、データをブロックとして格納するようにしている。従って、ポインタの接続関係を変更すれば、可変長のデータブロックを格納可能となる。
【００１３】
すなわち、格納するデータブロックの単位が決定されている従来の方式に比べ、キャッシュメモリの記憶容量を可能な限り有効に使い切ることができ、また、大きなブロック単位で格納すべき場合と小さなブロック単位でよい場合に対して柔軟に対応できる。よって、キャッシュメモリの使用効率が上がり、結果として、キャッシュミスの可能性を小さくすることができる。
【発明を実施するための最良の形態】
【００１４】
図５及び図６は、本発明の概念を説明する図である。
本発明では、プロセッサの命令実行はキャッシュ１エントリ分ではなく、数ブロック〜数十ブロック以上で行われることが多いことに着目した。ＣＡＭを全エントリに対し適用可能ならば、問題は解決可能であるが、高コストになることは前述の通りである。そこで、ＣＡＭをキャッシュエントリごとではなく、命令ブロック単位毎に適用する。具体的には、ある命令ブロックの情報（先頭アドレス、命令ブロックのサイズ、命令ブロックの先頭ポインタの番号）のみＣＡＭ上に保持する（図５参照）。命令データ自体は先頭ポインタで示されるＦＩＦＯ構造のポインタメモリに記憶する（図６参照）。ポインタメモリはポインタマップメモリとポインタデータメモリの２つのメモリから構成され、ポインタマップメモリはポインタ間の接続情報を、ポインタデータメモリはそのポインタにおけるデータそのものを表し、複数のＦＩＦＯを１つのメモリ上に仮想的に構築可能としている。すなわち、記憶領域は、例えば、ＲＡＭなどの連続領域であるが、データの連続性がポインタの接続情報を保持することによって保たれているということである。よって、連続性を持つポインタによって示されるデータは１つのブロックを構成し、ブロック毎に本発明の実施形態のキャッシュメモリに格納されていることになる。ここで、特に、本発明の実施形態のキャッシュメモリは、ポインタの接続情報を操作することによって、格納されるデータのブロックサイズを自由に変更可能となっている。すなわち、物理的なＦＩＦＯが複数用意されているわけではない。本発明における命令キャッシュの読み込みは（１）アドレスからＣＡＭを索引して、アクセスすべきデータが含まれるブロックの先頭アドレスが格納されているポインタを取得する、（２）ポインタマップメモリからアクセスすべきデータが含まれるブロックへのポインタを取得する、（３）ポインタデータメモリから取得したポインタで示されるアドレスの命令データブロックから、アクセスしたい命令データを読み込む、（４）実行する、となる。これにより、命令ブロック毎に異なる長さのデータ記録領域を実装したのと同じキャッシュ使用効率が得られる。また、全エントリにＣＡＭを用いるより索引情報が少ないため回路を相対的に削減することができる。キャッシュミス時は、ＣＡＭにタグをセットすると同時に空きポインタを空きポインタ供給部（不図示）から提供し、メモリからのデータを空きポインタが示すポインタメモリのエントリに書き込む。継続アクセスがプロセッサから要求された場合は、空きポインタを再度供給し、同様にキャッシュに書き込み、２番目のポインタをポインタキューに追加する。空きポインタが枯渇した場合は、古いデータから破棄するなどの方法で命令ブロックを破棄し、空きポインタを確保する。
【００１５】
図７は、本発明を含む全体構成図である。
同図はマイクロプロセッサの概略を示しており、動作は以下のようになる。
１）命令フェッチ
実行するための命令を外部バスより外部バスインターフェース２０を介して獲得する。まず、プログラムカウンタ２１の指し示す命令が命令バッファ２２に存在するかを確認し、ない場合、命令バッファ２２は命令をフェッチする要求を命令アクセスＭＭＵ２３に送る。命令アクセスＭＭＵ２３はプログラムが使用する論理アドレスから、ハードウェアのマッピング順序に依存する物理アドレスに変換する。そのアドレスを用いて命令アクセス一次キャッシュタグ２４を検索し、一致すれば命令アクセス一次キャッシュデータ２５に該当データが存在するため、読み出しアドレスを送り、命令データを命令バッファ２２に返す。存在しない場合は、更に二次キャッシュタグ２６を検索し、なお存在しない場合は外部バスというように要求を発行し、戻りデータを順次、二次キャッシュデータ２７、命令アクセス一次キャッシュデータ２５へと補充する。このとき、補充されたことを二次キャッシュタグ２６、命令アクセス一次キャッシュタグ２４の更新により記憶する。補充されたデータは、命令アクセス一次キャッシュデータ２５に存在しているときと同じ要領で、命令バッファ２２に格納する。
２）命令の実行
命令バッファ２２に格納された命令列は、実行ユニット２８に送られ、それぞれの命令の種別に応じて演算器２９、ロードストアユニット３０に転送される。演算命令や分岐命令は演算器２９の出力を汎用レジスタファイル３１に記録するか、あるいはプログラムカウンタ（不図示）を更新する、といった処理を行う。また、ロードストア命令は、ロードストアユニット３０にて、命令アクセスと同様にデータアクセスＭＭＵ３２−データアクセス一次キャッシュタグ３３−データアクセス一次キャッシュデータ３４と順次アクセスし、そのデータを汎用レジスタファイル３１にコピーするロード命令、あるいは、そのエントリに対し、汎用レジスタファイル３１からコピーするストア命令、と命令に応じて実行する。一次キャッシュにない場合は、命令実行機構と共用の二次キャッシュ、あるいは外部バスよりデータを獲得して、同様に実行する。実行の完了後、プログラムカウンタは逐次加算されるか、あるいは、分岐指示アドレスに更新され、再度１）の命令フェッチを行う。
３）全体
このように命令フェッチ、命令実行を繰り返し、マイクロプロセッサは動作するが本発明では、点線部の命令アクセスＭＭＵ２３、命令アクセス一次キャッシュタグ２４、命令アクセス一次キャッシュデータ２５の新しい構成を提供する。
【００１６】
図８は、本発明の実施形態の構成図である。
プログラムカウンタからの命令アクセスリクエスト／アドレスは命令アクセスＭＭＵ２３に送られ、物理アドレスに変換された後、ＣＡＭ４１にアドレスとして送られる。ＣＡＭ４１はタグ、サイズ、先頭ポインタデータを出力する。アドレス・サイズ判定／ヒット判定ブロック４２では、最終的な希望ポインタの検索を行い、そのポインタが存在した場合はポインタデータを読み出し、そのデータは命令データ（１）として命令バッファ（不図示）に送られる。存在しない場合、キャッシュミスリクエスト（２）として、二次キャッシュに出力される。その後、二次キャッシュからの戻りデータは、ブロック先頭判定ブロック４３を経由し、戻りデータが先頭命令であれば、ＣＡＭ４１の更新を、先頭命令でなければポインタマップメモリ４４の更新とＣＡＭサイズ情報４２の更新と共に、ポインタデータメモリ４５を更新し、同様に命令バッファにデータを返す。ブロック先頭判定ブロック４３では、書き込みに際し、空きポインタＦＩＦＯ４６からの空きポインタの供給を受けるが、枯渇してしまった場合は、空きポインタＦＩＦＯ４６から破棄ポインタ選択制御ブロック４７に指示が送られ、任意のＣＡＭエントリに破棄指示を行う。その出力はアドレス・サイズ判定／ヒット判定ブロック４２で無効化され、空きポインタＦＩＦＯ４６に返却される。
【００１７】
図９は、プロセッサの命令アクセスＭＭＵのページ管理機構とＣＡＭとを共用する場合の構成を示したものである。
なお、同図において、図８と同じ構成要素には同じ参照符号を付して、説明を省略する。
【００１８】
この構成は、ＭＭＵのアドレス変換単位（ページ）とキャッシュの管理単位を同一サイズにすることにより、ＭＭＵ内のＣＡＭに同一機能を持たせ、ＣＡＭの削減をはかったものである（同図の５０）。すなわち、命令アクセスＭＭＵでは、仮想アドレスを物理アドレスに変換するテーブルを有しているわけであるが、このテーブルと、ＣＡＭのテーブルとを１つのテーブルに併合し、命令アクセスＭＭＵの機構で、ＣＡＭの検索などの動作を行うようにしたものである。これによれば、テーブルの検索機構を命令アクセスＭＭＵとＣＡＭの検索機構を１つのハードウェアで扱うことができるので、ハードウェアの削減となる。
【００１９】
また、本発明の実施形態においては、キャッシュメモリに読み込む命令データを一塊りずつ格納するので、プログラムをブロック化して読み込む必要がある。この場合、命令がプロセッサが読み込んだとき、読み込んだ命令がサブルーチンコール及びその復帰命令、条件分岐命令、例外処理及びその復帰命令であると判断した場合には、プログラムの先頭あるいは最後であると判断して、その命令間のブロックを単位としてキャッシュメモリに格納する。このように、プログラムの内容に従って、読み込む命令をブロック化してキャッシュメモリに読み込む場合は、ブロックの大きさが、読み込む度に異なることになるが、本発明の実施形態によれば、ポインタを用いて、可変長のブロックをメモリ上に構成可能であるので、このような方法が採用できる。あるいは、ブロックの大きさを強制的に決定し、順次プログラムの命令をデコードする際に、任意の命令をブロックの先頭とし、所定の大きさのブロックが得られた時点で、最後の命令をブロックの最後の命令とするような方法が可能である。この場合、図８、９のブロック先頭判定の命令デコードを変更するだけで、任意のブロック化方法が採用可能である。例えば、プログラムの記述に従ってブロック化する場合には、ＣＡＬＬ命令／レジスタライト命令等を判定して、ブロックの先頭と判断することになる。
【００２０】
本発明の実施形態においては、プロセッサで命令ブロックの先頭と末尾を検出し、命令ブロックＣＡＭに制御信号を送出する。本制御機構では、先頭信号を受け取ると、キャッシュタグを記録し、主記憶よりデータを獲得し、ポインタが示すキャッシュアドレスに命令を書き込む。プロセッサの要求が１キャッシュエントリに達する毎に、空きポインタキューより空きエントリを補充し、そのエントリ番号をキャッシュタグ・キューに追加すると同時に、命令ブロックサイズを加算する。同一ブロックを複数回、またはブロック内の途中に分岐する場合は、キャッシュタグ＋サイズからエントリ番号を割り出し、アクセスを行う。また、上記において、命令ブロックの先頭と末尾の通知を特定のレジスタアクセスで通知する。この場合、命令によるブロックの明示的開始／終了を宣言する必要がある。これは、前述した、プログラムの中で命令によらず、強制的にブロック化する場合である。
【００２１】
図１０〜図１３は、本発明の実施形態の動作を説明する図である。
図１０は、本発明の実施形態に従ったキャッシュメモリに命令が存在した場合、すなわち、命令ヒットの場合の動作である。
【００２２】
プロセッサ６０から、アクセスすべき命令データのアドレスが出力されると、ＣＡＭ部６１を検索して、アクセスすべき命令データを含むブロックの先頭ポインタを検索する。命令ヒットの場合には、アクセスすべき命令データを含むブロックの先頭ポインタが存在した場合である。次には、得られた先頭ポインタから、ポインタマップメモリ６２を検索し、ブロックを構成する命令データのポインタを全て取得する。そして、取得したポインタを用いて、ポインタデータメモリ６３から命令データを取得し、プロセッサ６０に返す。
【００２３】
図１１は、本発明の実施形態に従ったキャッシュメモリに命令が存在しない、すなわち、命令ミスの場合であって、アクセスすべき命令がブロックの先頭に有るべき場合を示している。
【００２４】
この場合、プロセッサ６０からアドレス指定が行われ、命令データへのアクセスが試みられる。ＣＡＭ部６１では、このアドレスに従ってポインタを検索するが、今の場合、対応する命令が含まれているブロックが無く、しかも、対応する命令がブロックの先頭となるべきものであると判断される。この場合、空きポインタキュー６４から、空きのポインタを獲得し、主記憶から当該命令データを含むブロックを読み込み、ＣＡＭの先頭ポインタで示される先頭アドレスを更新する。また、ポインタマップメモリ６２も、獲得された空きポインタをブロックとして関連付けて、ポインタデータメモリ６３は、各ポインタに主記憶から読み込まれた命令データを対応付けて、命令データをプロセッサ６０に返す。空きポインタキュー６４は、通常のＦＩＦＯによるポインタデータバッファであり、初期値は、ポインタが０から最大値まで記録されるものである。
【００２５】
図１２は、アクセスすべき命令データが本発明の実施形態に従ったキャッシュメモリに存在せず、命令データがブロックの先頭以外の場所に存在すべきものである場合の動作を示す図である。
【００２６】
プロセッサ６０からアドレスが出力され、ＣＡＭ部６１で命令データの検索をするが、キャッシュメモリに存在しないと判断される。すると、空きポインタキュー６４から空きポインタを取得し、主記憶から当該命令データを含むブロックを読み込む。そして、当該ブロックに隣接する、既にＣＡＭ部６１に登録されているブロックに、読み込んだブロックをつなげる要領で、ＣＡＭ部６１のブロックサイズを更新し、ポインタマップメモリ６２を更新し、ポインタデータメモリ６３が、読み込んだブロックの命令データを格納し、命令データをプロセッサ６０に返す。
【００２７】
図１３は、命令データのブロックを読み込む必要があるが、空きポインタがない場合の動作を示す図である。
プロセッサ６０から命令データへのアクセスがＣＡＭ部６１になされる。しかし、命令データがキャッシュメモリ内にないと判断される。更に、主記憶から命令データのブロックを読み込むために空きポインタキューから空きポインタを獲得しようとするが、空きポインタがないため、任意の１ブロックを破棄する命令が出される。ポインタマップメモリ６２は、ポインタマップから１ブロック分を破棄し、破棄したポインタを空きポインタキュー６４に通知する。これにより、空きポインタキュー６４は、空きポインタを獲たので、これをＣＡＭ部６１に通知して、主記憶から新しい命令データブロックを読み込む。
【産業上の利用可能性】
【００２８】
本発明による、キャッシュメモリの構成としてＣＡＭを採用するよりも少ない回路量で、キャッシュ使用効率を大幅に改善したキャッシュメモリ機構を提供可能となる。
【図面の簡単な説明】
【００２９】
【図１】従来技術のダイレクトマップ方式を採用したキャッシュメモリの概念構成を示す図である。
【図２】従来の２ウェイセットアソシエイティブキャッシュメモリの概念構成図である。
【図３】従来の連想記憶メモリの概念構成図である。
【図４】従来の４ウェイセットアソシエイティブキャッシュメモリのデータアクセス機構の構成図である。
【図５】本発明の概念を説明する図である。
【図６】本発明の概念を説明する図である。
【図７】本発明を含む全体構成図である。
【図８】本発明の実施形態の構成図である。
【図９】プロセッサの命令アクセスＭＭＵのページ管理機構とＣＡＭとを共用する場合の構成を示したものである。
【図１０】本発明の実施形態の動作を説明する図である。
【図１１】本発明の実施形態の動作を説明する図である。
【図１２】本発明の実施形態の動作を説明する図である。
【図１３】本発明の実施形態の動作を説明する図である。
【国際調査報告】
2004077299.tif 000016
2004077299.tif 000017
2004077299.tif 000018
2004077299.tif 000019