(57)【特許請求の範囲】
【請求項１】
プロセッサ（１０６）と、記憶装置（１１５，１１６）と、上位キャッシュ（１０７，１０８）と、下位キャッシュ（１１０）とを含むコンピュータのキャッシュ・コントローラであって、
複数の前記記憶装置の特定のアドレスのそれぞれを並列にデコードし、下位キャッシュのアドレスであるデコード結果を出力する複数のアドレス・デコーダ（１２０）と、
前記特定のアドレスそれぞれに関係する前記上位キャッシュのアクセスがミスしたことに応じて、前記特定のアドレスのデコード結果のいずれかを選択し、選択された前記特定のアドレスのデコード結果を前記下位キャッシュに供給するデコード結果選択回路（１２２，１２４）とを含み、
前記複数のアドレス・デコーダそれぞれは、前記上位キャッシュへのアクセスがヒットしたかミスしたかが判明する前に、前記複数の記憶装置の特定のアドレスのそれぞれのデコードを開始する、
キャッシュ・コントローラ。
【請求項２】
前記デコード結果選択回路は、
前記特定のアドレスそれぞれに関係する前記上位キャッシュへのアクセスがヒットしたかミスしたかに応じて、前記特定のアドレスのデコード結果に優先順位を与える優先順位論理（１２４）
を含む請求項１に記載のキャッシュ・コントローラ。
【請求項３】
前記デコード結果選択回路は、
前記与えられた優先順位に従って、前記特定のアドレスのデコード結果のいずれかを選択し、前記下位キャッシュに供給するマルチプレクサ（１２２）
を含む請求項２に記載のキャッシュ・コントローラ。
【請求項４】
前記優先順位論理は、前記マルチプレクサが、アクセスのミスが生じた前記特定のアドレスのデコード結果を選択し、前記下位キャッシュに供給するように、前記特定のアドレスのデコード結果に優先順位を与える
請求項３に記載のキャッシュ・コントローラ。
【請求項５】
前記下位キャッシュは、前記プロセッサと、前記上位キャッシュと、前記記憶装置とに接続され、
前記下位キャッシュが、前記供給されたデコード結果に関係する値を、直接、前記プロセッサに供給する
請求項４に記載のキャッシュ・コントローラ。
【請求項６】
前記上位キャッシュおよび前記下位キャッシュの両方で前記特定のアドレスへのアクセスのミスが生じた場合には、前記上位キャッシュおよび前記下位キャッシュに、前記記憶装置から前記特定のアドレスの値が充填される
請求項１〜５のいずれかに記載のキャッシュ・コントローラ。
【請求項７】
プロセッサと、記憶装置と、上位キャッシュと、下位キャッシュとを含むコンピュータにおけるキャッシュ・コントロール方法であって、
複数のアドレス・デコーダにより前記記憶装置の複数の特定のアドレスそれぞれを並列にデコードし、デコード結果それぞれを出力し、
前記特定のアドレスそれぞれに関係する前記上位キャッシュへのアクセスがヒットしたかミスしたかに応じて、選択された前記特定のアドレスのデコード結果を前記下位キャッシュに供給し、
前記上位キャッシュへのアクセスがヒットしたかミスしたかが判明する前に、前記特定のアドレスのデコードを開始する、
キャッシュ・コントロール方法。
【請求項８】
前記デコード結果の選択において、
前記特定のアドレスそれぞれに関係する前記上位キャッシュへのアクセスがヒットしたかミスしたかに応じて、前記特定のアドレスのデコード結果に優先順位を与える
請求項７に記載のキャッシュ・コントロール方法。
【請求項９】
前記デコード結果の選択において、
前記与えられた優先順位に従って、前記特定のアドレスのデコード結果のいずれかを選択し、前記下位キャッシュに供給する
を含む請求項８に記載のキャッシュ・コントロール方法。
【請求項１０】
前記優先順位を与える際に、アクセスにミスが生じた前記特定のアドレスのデコード結果を選択し、前記下位キャッシュに供給するように、前記特定のアドレスのデコード結果に優先順位を与える
請求項９に記載のキャッシュ・コントロール方法。
【請求項１１】
前記下位キャッシュは、前記プロセッサと、前記上位キャッシュと、前記記憶装置とに接続され、
前記下位キャッシュが、前記供給されたデコード結果に関係する値を、直接、前記プロセッサに供給する
請求項１０に記載のキャッシュ・コントロール方法。
【請求項１２】
前記上位キャッシュおよび前記下位キャッシュの両方で前記特定のアドレスへのアクセスのミスが生じた場合には、前記上位キャッシュおよび前記下位キャッシュに、前記記憶装置から前記特定のアドレスの値が充填される
請求項７〜１１のいずれかに記載のキャッシュ・コントロール方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は一般にコンピュータ・システムに関し、さらに詳細には、メモリ・アクセス待ち時間を短縮するためにキャッシュがマルチレベル・アーキテクチャを有する、処理装置のキャッシュ・メモリにアクセスするための改善された方法に関する。
【０００２】
【従来の技術】
従来のコンピュータ・システムの代表的な構造は、システム・メモリ装置（ランダム・アクセス・メモリすなわちＲＡＭ）と、表示モニタやキーボード、グラフィカル・ポインタ（マウス）、不揮発性記憶装置（ハード・ディスク）など様々な周辺または入出力（Ｉ／Ｏ）装置とに接続された、１つまたは複数の処理装置を含む。システム・メモリ装置は、プログラム命令を実行する際に処理装置によって使用され、こうした命令、およびプログラムによって供給または生成されたデータ値を記憶する。処理装置は、汎用相互接続またはバス、あるいは直接メモリ・アクセス・チャネルも含めた様々な手段で周辺装置と通信する。コンピュータ・システムは、例えばモデム、プリンタ、ネットワーク・アダプタに接続するためのシリアル・ポートや並列ポートなど、多くの追加構成要素を有することができる。前述のものとともにその他の構成要素をさらに使用することもでき、例えばディスプレイ・アダプタを使用してビデオ表示モニタを制御する、あるいはメモリ制御装置を使用してシステム・メモリにアクセスすることもできる。
【０００３】
従来の処理装置は、様々な実行ユニットおよびレジスタ、ならびに命令を適当な実行ユニットに転送するブランチおよびディスパッチ・ユニットを有するプロセッサ・コアを含む。システム・メモリ（ＲＡＭ）から値をロードする長い段階を回避することによって処理速度を上げるために、キャッシュは一般に、命令とデータの両方について、プロセッサが繰り返しアクセスする可能性のある値を一時的に記憶するようになっている。これらのキャッシュは、単一の集積チップ上にプロセッサ・コアと一体化してパックされるときには、「搭載」と呼ばれる。各キャッシュは、プロセッサ・コアとキャッシュ・メモリの間の値の転送を管理するキャッシュ・コントローラまたはバス・インタフェース・ユニットと連動している。
【０００４】
処理装置は、搭載（レベル１）キャッシュを支援するレベル２（Ｌ２）キャッシュなど、追加キャッシュを含むことができる。換言すれば、Ｌ２キャッシュはシステム・メモリと搭載キャッシュの間の中間物として働き、搭載キャッシュよりはるかに大量の情報（命令およびデータ両方）を記憶することができるが、アクセスのペナルティは長くなる。多くのレベルの相互接続されたキャッシュが存在する、マルチレベル・キャッシュ階層を設けることができる。
【０００５】
代表的なシステム・アーキテクチャを図１に示すが、これはインターナショナル・ビジネス・マシーンズ・コーポレイションが販売するＰｏｗｅｒＰＣTMプロセッサの例である。コンピュータ・システム１０は、処理装置１２ａと、様々な入出力装置１４と、ＲＡＭ１６と、コンピュータが最初にオンになったときに周辺装置の１つからオペレーティング・システムを探し出してロードすることをその主な目的とするファームウェア１８とを含む。処理装置１２ａは、システム・バス２０を使用して周辺装置と通信する（ローカル周辺バス（例えばＰＣＩ）をシステム・バスとともに使用することもできる）。処理装置１２ａは、プロセッサ・コア２２、ならびに高速メモリ装置を使用して実施される、単一の集積チップ２８上にプロセッサ・コアと一体化してパックされた命令キャッシュ２４およびデータ・キャッシュ２６を含む。キャッシュ３０（Ｌ２）は、プロセッサ・バス３２を介してキャッシュ２４および２６を支援する。例えば、キャッシュ３０は、２５６または５１２キロバイトの記憶容量を有するチップにすることができ、プロセッサは、６４キロバイトの全記憶域を有する搭載キャッシュを有するＩＢＭ製ＰｏｗｅｒＰＣTM６０４シリーズ・プロセッサにすることができる。キャッシュ３０はバス２０に接続され、メモリ１６からプロセッサ・コア２２への全ての情報のロードは、キャッシュ３０を経由しなければならない。処理装置１２ｂで示すように、複数のプロセッサを設けることもできる。
【０００６】
例示的なキャッシュ線（ブロック）は、アドレス・タグ・フィールド、状態ビット・フィールド、包括ビット・フィールド、および実際の命令およびデータを記憶する値フィールドを含む。状態ビット・フィールドおよび包括ビット・フィールドは、マルチプロセッサ・コンピュータ・システム中のキャッシュ・コヒーレンシを維持するために使用される（キャッシュに記憶された値の妥当性を示す）。アドレス・タグは、対応するメモリ・ブロックの完全なアドレスのサブセットである。着信アドレスとアドレス・タグ・フィールド内のタグの１つとを比較して一致すると、キャッシュ「ヒット」が示される。キャッシュ中の全てのアドレス・タグの集合体はディレクトリと呼ばれ（時には状態ビット・フィールドおよび包括ビット・フィールドを含み）、全ての値フィールドの集合体はキャッシュ・エントリ・アレイである。
【０００７】
コンピュータ・システムの性能を、いくつかの要素を有するものとして考えることができる。その第１は、プロセッサが完璧なキャッシュ・メモリを有する場合、すなわちプロセッサ・コアがメモリ・アクセスの待ち時間なしでその第１キャッシュ・レベルからのメモリ要求を常に満たすことができる場合と同じプロセッサの性能である。この動作方式では当然最高の性能が与えられるが、現実的ではない。マルチレベル・キャッシュ・アーキテクチャでは、その次にシステムの性能に寄与するのは、アクセス要求がキャッシュ・メモリの第１レベルでは「ミス」となるが、要求された値をキャッシュ・メモリの第２レベルから取り出す動作方式である。この要素は、メモリの第２レベルにアクセスするのに必要となる追加サイクルの数に依存し、第１レベルのキャッシュのミスが発生する頻度に反比例する。現在のコンピュータでは、第２レベルのメモリへのアクセスは、ある要求が第１レベルでミスとなったものと判定された後でのみ開始される。結果として、第２レベルのキャッシュの全アクセス時間は、性能のペナルティとして現れる。
【０００８】
第１キャッシュ・レベルでのミスによる性能低下を表すものと同様の項を、メモリ階層の全てのレベルでのミスについてのシステム性能に組み込んで、システム性能の推定を洗練させることができる。したがって、システム全体の性能を改善するには、上位レベルのメモリから取り出すのに必要となる追加サイクルの数を減少させることが明らかに望ましい。比較的わずかなハードウェア費用で、過度の電力を必要とすることなくこの改善を達成することができれば、さらに有利となるはずである。
【０００９】
【発明が解決しようとする課題】
したがって、本発明の目的は、データ処理システム用の改良されたキャッシュ・メモリを提供することである。
【００１０】
本発明の別の目的は、少なくとも２つのキャッシュ・レベルを有し、第２（下位）キャッシュ・レベルによって満たされる第１レベルのキャッシュのミスにともなうメモリ・アクセスの待ち時間が短縮される、改良されたこのようなキャッシュ・メモリを提供することである。
【００１１】
本発明の別の目的は、費用および設計の考慮事項を最小限に抑えるように既存のハードウェア設計から容易に適合されるアーキテクチャを有する、このようなマルチレベル・キャッシュを提供することである。
【００１２】
【課題を解決するための手段】
前述の目的は、下位レベルのキャッシュ（例えばＬ２）に値をロードする段階と、上位レベルのキャッシュ（例えばＬ１）から値を供給するよう求めるプロセッサからの要求を発行する段階と、その値のキャッシュのミスが上位レベルのキャッシュで発生したと判定する段階と、前記判定段階中に下位レベルのキャッシュに要求を転送する段階と、下位レベルのキャッシュから値を供給する段階とを一般に含む、キャッシュからコンピュータ・システムのプロセッサにデータを提供する方法によって達成される。下位レベルがＬ２キャッシュである実施形態では、Ｌ２キャッシュは、プロセッサに直接値を供給することができる。複数のデコーダを使用して、コンピュータ・システムのシステム・メモリ装置中の特定の位置に関係するアドレスをデコードすることができ、デコーダは、上位レベルのキャッシュでは並列に動作して、複数の同時メモリ要求を満たすことができる。アドレスの１つ（上位レベルのキャッシュからのヒット／ミス情報に基づいて優先順位論理によって選択）は、マルチプレクサによって、下位レベルのキャッシュのメモリ・アレイのワード線ドライバにゲートされる。仮想から実への変換を必要としないアドレス中のいくつかのビットは、直ちにデコードすることができる。その他のビットは、前記判定段階を完了する前に変換することができる。この実施形態は、わずかなハードウェア費用で待ち時間のペナルティを短縮する。
【００１３】
本発明の上記および追加の目的、特徴、および利点は、以下の詳細な説明から明らかになるであろう。
【００１４】
【発明の実施の形態】
ここで図面、特に図２を参照すると、本発明の一実施形態による、キャッシュ・メモリを組み込むことができるデータ処理システムのブロック図が示されている。図２には単一のプロセッサ１０４しか示していないが、本発明の機構はマルチプロセッサ・システムでも有効である。スーパースカラＲＩＳＣタイプにすることができるＣＰＵ１０６を有するプロセッサ１０４は、オンチップの命令キャッシュ１０７およびデータ・キャッシュ１０８を含むシングル・チップ装置として構築される。キャッシュ１０７、１０８はともに、ローカル・バス構造内で別々のパスによってＣＰＵ１０６に接続される。命令キャッシュ１０７はキャッシュ・コントローラ１０９ａを介してローカル・バス１０５に接続され、データ・キャッシュ１０８はキャッシュ・コントローラ１０９ｂを介してローカル・バス１０５に接続される。２次キャッシュ１１０も、キャッシュ・コントローラ１１１を介してローカル・バス１０５に接続される。２次キャッシュ１１０は、命令キャッシュ１０７またはデータ・キャッシュ１０８よりはるかに大きく、２次キャッシュ１１０へのアクセスは命令キャッシュ１０７またはデータ・キャッシュ１０８へのアクセスよりいくらか遅くなる。ＣＰＵ１０６も、ローカル・バス１０５とシステム・バス１１３の間で調時および制御変換を行うバス・インタフェース１１２を介してシステム・バス１１３に接続される。さらに、メイン・メモリ１１５およびディスク記憶装置１１６もシステム・バス１１３に結合される。Peripheral Component Interconnect（ＰＣＩ）バスなど、１つまたは複数の仲介バスを使用して、その他の周辺装置をシステム・バス１１３に接続することができる。
【００１５】
メモリ階層は、最高速から最低速へ、最小から最大へ、ビットあたり最も高価なものからビットあたり最も安価なものへ、キャッシュ１０７、１０８から次第に２次キャッシュ１１０、メイン・メモリ１１５、ディスク記憶装置１１６へとなっている。メイン・メモリ１１５は、ディスク記憶装置１１６の内容のサブセットを含み、２次キャッシュ１１０はメイン・メモリ１１５の内容のサブセットを含み、キャッシュ１０７、１０８はそれぞれ２次キャッシュ１１０の内容のサブセットを含む。ＣＰＵ１０６は、キャッシュ１０７、１０８にはプロセッサ・サイクル内でアクセスすることができるが、２次キャッシュ１１０にアクセスするには、数プロセッサ・サイクルかかることもある。キャッシュ１０７、１０８および２次キャッシュ１１０でキャッシュ・ミスが発生した場合には、メイン・メモリ１１５にアクセスして、キャッシュ線充填動作を実行する、つまりあるキャッシュ線をアドレスされたデータを含むメイン・メモリ１１５からの等価なビット部分で置換する。このキャッシュ線充填動作は、キャッシュ・ミスが発生した試みられたキャッシュ・アクセスを満たすように実行されなければならない。メイン・メモリ１１５がキャッシュ線充填動作を試みる位置を含まない場合には、キャッシュ線充填動作を完了することができるように、ディスク記憶装置１１６からこのデータを含むページが得られる。ディスク記憶装置１１６からページを獲得し、これをメイン・メモリ１１５に書き込む時間は、プロセッサ・サイクルを何千も必要とすることもあり、その間、ＣＰＵ１０６は、切り替わって別のタスクを行う、または停止してデータが要求を満たすのを待機することもある。
【００１６】
本発明では、上位キャッシュ・レベルでミスとなった要求を満たすためにメモリ階層中の次のレベルに進む際の時間ペナルティを短縮する。メモリ・アクセス待ち時間の短縮は、階層中の第１レベルへのアクセスを、好ましくは可能な限り多く、第２レベルへのアクセスとオーバラップさせることによって達成される。２つのアクセスをオーバラップさせることにより、第１レベル・キャッシュのミスについての任意のペナルティは、ちょうど第２レベルにアクセスするのに必要となるサイクルと、第１レベルにアクセスする際のサイクルとの差となる。
【００１７】
Ｌ１キャッシュおよびＬ２キャッシュへの２つのアクセスは、図３に示すように、メモリ中の特定の位置に関係するアドレスをデコードすることによって効率的にオーバラップさせることができる。最大数の潜在的な同時メモリ要求を満たすために、多数のデコーダ１２０を必要に応じて上位メモリ・レベルで並列に使用することができる。アドレスは、実際にメモリ・アレイにアクセスせずに利用できる情報が許す限り完全にデコードされる。例えば仮想から実への変換を必要としないアドレスのビットは、直ちにデコードすることができる。例えば変換索引緩衝機構（ＴＬＢ）中での変換後に利用可能となるアドレスのビットは、それらが利用可能となった直後に、通常はキャッシュ・ヒットまたはミス信号が決定される前にデコードすることができる。理想的には、アドレスは、第２レベル・キャッシュ・メモリ・アレイのワード線ドライバまでデコードされる。このデコードは、第１レベル・キャッシュのアクセスと並列に、完全に実施することができる。第１レベル・キャッシュ・ミスが発生したと判定されたときには、マルチプレクサ１２２を使用して、デコードされた適当なアドレスをワード線ドライバにゲートし、第２レベル・キャッシュ中の要求されたデータにアクセスすることができる。マルチプレクサ１２２は、Ｌ１ヒット／ミス情報を各アドレスについて受信する優先順位論理１２４によって制御される。したがって、キャッシュ・レベル・ミスのペナルティは、第２レベル・キャッシュ中のデコーダの待ち時間だけ短縮される。
【００１８】
アクセスのオーバラップを達成するこの実施形態は、わずかなハードウェア費用で待ち時間のペナルティを短縮するので魅力的である。デコーダは一般に、最終的には多数の信号のうち１つしかオンにしないので、ほとんど電力を消費しない。複数の潜在的なソースに対応するのに必要な重複したデコーダの他には、本発明では、デコードされた適当な信号をワード線ドライバにゲートするためのマルチプレクサが必要となるだけである。
【００１９】
特定の実施形態に関連して本発明について説明したが、この説明は、限定的な意味で解釈すべきものではない。開示の実施形態の様々な修正形態、および本発明の代替の実施形態は、本発明の説明を参照すれば当業者には明らかであろう。例えば、本発明は、第２レベル・キャッシュ・ミスが第３キャッシュ・レベルによって満たされるときにメモリ・アクセス待ち時間を短縮することによって、２つを超えるキャッシュ・レベルに拡張することができる。したがって、添付の特許請求の範囲に定義する本発明の趣旨または範囲を逸脱することなく、このような修正を行うことができることが企図されている。
【００２０】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００２１】
（１）下位レベルのキャッシュに値をロードする段階と、
上位レベルのキャッシュから値を供給するよう求めるプロセッサからの要求を発行する段階と、
前記発行段階に応答して、その値のキャッシュのミスが上位レベルのキャッシュで発生したと判定する段階と、
前記判定段階中に下位レベルのキャッシュに要求を転送する段階と、
前記判定段階に応答して、下位レベルのキャッシュから値を供給する段階と
を含む、キャッシュからコンピュータ・システムのプロセッサにデータを提供する方法。
（２）値が下位レベルのキャッシュからプロセッサに直接供給される、上記（１）に記載の方法。
（３）前記転送段階が、コンピュータ・システムのシステム・メモリ装置中の値の特定の位置に関係するアドレスをデコードする段階を含む、上記（１）に記載の方法。
（４）前記デコード段階が、複数のデコーダを上位レベルのキャッシュで並列に動作させて複数の同時メモリ要求を満たす段階を含む、上記（３）に記載の方法。
（５）前記供給段階が、下位レベルのキャッシュの複数のメモリ・アレイのワード線ドライバにアドレスをゲートする段階を含む、上記（３）に記載の方法。
（６）前記デコード段階が、仮想から実への変換を必要としないアドレスの複数のビットを直ちにデコードする段階を含む、上記（３）に記載の方法。
（７）前記デコード段階が、アドレスの別の複数のビットを前記判定段階が完了する前に変換する段階を含む、上記（６）に記載の方法。
（８）上位キャッシュ・レベルと、
下位キャッシュ・レベルと、
ある値のキャッシュ・ミスが前記上位キャッシュ・レベルで発生し、この値が前記下位キャッシュ・レベルから供給されるときのメモリ・アクセス待ち時間を短縮する手段とを含む、コンピュータ・システムのプロセッサに値を提供するキャッシュ。
（９）前記上位キャッシュ・レベルが、プロセッサに接続された第１キャッシュ・レベルであり、
前記下位キャッシュ・レベルが、前記第１キャッシュ・レベルに接続された第２キャッシュ・レベルである、
上記（８）に記載のキャッシュ。
（１０）前記第２キャッシュ・レベルがさらに第３キャッシュ・レベルに接続される、上記（８）に記載のキャッシュ。
（１１）前記メモリ・アクセス待ち時間を短縮する前記手段が、前記下位キャッシュ・レベルからプロセッサに直接値を供給する、上記（８）に記載のキャッシュ。
（１２）前記メモリ・アクセス待ち時間を短縮する前記手段が、前記上位キャッシュ・レベルの第１アクセスと前記下位キャッシュ・レベルの第２アクセスのオーバラップを実現する、上記（８）に記載のキャッシュ。
（１３）短縮手段が、前記第１キャッシュ・レベルがキャッシュ・ミスが発生したかどうかを判定する間にプロセッサから前記下位キャッシュ・レベルに値の要求を転送することによって、前記オーバラップを実現する、上記（１２）に記載のキャッシュ。
（１４）短縮手段が、コンピュータ・システムのシステム・メモリ装置中の値の特定の位置に関係するアドレスをデコードすることによって要求を転送する、上記（１３）に記載のキャッシュ。
（１５）短縮手段が、前記下位キャッシュ・レベルの複数のメモリ・アレイのワード線ドライバにアドレスをゲートすることによって値を供給する、上記（１４）に記載のキャッシュ。
【図面の簡単な説明】
【図１】従来技術のマルチ・プロセッサ・コンピュータ・システムを示すブロック図である。
【図２】本発明の一実施形態によるキャッシュ・メモリを有するデータ処理システムを示すブロック図である。
【図３】上位キャッシュ・メモリ・レベル（Ｌ１）との並列アクセスを実現するための下位キャッシュ・メモリ・レベル（Ｌ２）でのアドレス（または部分アドレス）のデコードをさらに詳細に示す、図２のキャッシュ・メモリのブロック図である。
【符号の説明】
１０４  プロセッサ
１０５  ローカル・バス
１０６  ＣＰＵ
１０７  命令キャッシュ
１０８  データ・キャッシュ
１０９ａ  キャッシュ・コントローラ
１０９ｂ  キャッシュ・コントローラ
１１０  ２次キャッシュ
１１１  キャッシュ・コントローラ
１１２  バス・インタフェース
１１３  システム・バス
１１５  メイン・メモリ
１１６  ディスク記憶装置
【図１】
0003683739.tif 000002
【図２】
0003683739.tif 000003
【図３】
0003683739.tif 000004