(57)【要約】      （修正有）【課題】キャッシュ・ミス時のプロセッサの遊休時間を少なくする。【解決手段】少なくとも２つのレベルを有するコンピュータ・キャッシュ・メモリが、一致グループに割り振られた連想セットを含み、各一致グループは、高レベル・キャッシュにおいて複数の（望ましくは、２つの）連想セットを有し、低レベル・キャッシュにおいて複数の（望ましくは、３つの）連想セットを有する。高レベル・キャッシュにおける連想セットのアドレス範囲は同じ一致グループにおける低レベルキャッシュ内の連想セットにすべて分散され、従って、これらの低レベル・キャッシュの連想セットは同じ一致グループにおける高レベル・キャッシュ内のすべての連想セットによって効果的に共用される。低レベル・キャッシュは、高レベル・キャッシュのビクティム・キャッシュであることが望ましい。【選択図】図１
2005174341.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つのプロセッサと、
メモリと、
前記メモリの一部分を一時的に保持し、複数のアドレス可能な連想セットを有する第１キャッシュであって、各連想セットがそれぞれの１つまたは複数のキャッシュ・ラインを含む、第１キャッシュと、
前記メモリの一部分を一時的に保持し、複数のアドレス可能な連想セットを有する第２キャッシュであって、各連想セットがそれぞれの１つまたは複数のキャッシュ・ラインを含む、第２キャッシュと、
を含み、
前記第１キャッシュの前記連想セットおよび前記第２キャッシュの前記連想セットが複数の一致グループに対応し、各一致グループがそれぞれ、前記第１キャッシュの複数の連想セットおよび前記第２キャッシュの複数の連想セットを含み、
前記第１キャッシュの各連想セットにそれぞれ対応するアドレスが、同じ一致グループ内の前記第２キャッシュにおける前記複数の連想セットの間で、前記第１キャッシュのそれぞれの連想セットとして割り振られる、
ディジタル・データ処理装置。
【請求項２】
前記第１キャッシュの各連想セットのそれぞれに対応するアドレスが、同じ一致グループ内の第２キャッシュにおける前記複数の連想セットの間で、前記それぞれの連想セットを決定するために使用されたアドレス・ビット以外の少なくとも幾つかのアドレス・ビットのハッシュ関数を用いて、割り振られる、請求項１に記載のディジタル・データ処理装置。
【請求項３】
前記ハッシュ関数がモジュロＮ関数であり、Ｎは前記一致グループにおける前記第２キャッシュの連想セットの数である、請求項２に記載のディジタル・データ処理装置。
【請求項４】
前記一致グループの各々が、前記第１キャッシュのＭ個の連想セットおよび前記第２キャッシュのＮ個の連想セットを含み、ＭおよびＮの最大公約数が１である、請求項１に記載のディジタル・データ処理装置。
【請求項５】
前記第１キャッシュおよび前記第２キャッシュにおいてデータが重複しない、請求項１に記載のディジタル・データ処理装置。
【請求項６】
前記第１キャッシュが前記第２キャッシュよりも高いレベルにある、請求項１に記載のディジタル・データ処理装置。
【請求項７】
前記第２キャッシュが前記第１キャッシュのビクティム・キャッシュである、請求項６に記載のディジタル・データ処理装置。
【請求項８】
第３キャッシュを含み、前記第３キャッシュが前記第１キャッシュおよび前記第２キャッシュよりも高いレベルにある、請求項６に記載のディジタル・データ処理装置。
【請求項９】
前記第１キャッシュおよび前記第２キャッシュが実メモリ・アドレスを使ってアドレス可能である、請求項１に記載のディジタル・データ処理装置。
【請求項１０】
前記第１キャッシュにおける前記連想セットの各々が複数のキャッシュ・ラインをそれぞれ含み、前記第２キャッシュにおける前記連想セットの各々が複数のキャッシュ・ラインをそれぞれ含む、請求項１に記載のディジタル・データ処理装置。
【請求項１１】
少なくとも１つのプロセッサ・コアと、
第１キャッシュをアクセスするための第１キャッシュ・アクセス・ロジックであって、前記第１キャッシュがメモリの一部分を一時的に保持し、前記第１キャッシュ・アクセス・ロジックが前記第１キャッシュの複数の連想セットの中から前記プロセッサ・コアによって生成された入力アドレスに対応した前記第１キャッシュの連想セットを決定し、各連想セットがそれぞれの１つまたは複数のキャッシュ・ラインを含む、第１キャッシュ・アクセス・ロジックと、
第２キャッシュをアクセスするための第２キャッシュ・アクセス・ロジックであって、前記第２キャッシュが前記メモリの一部分を一時的に保持し、前記第２キャッシュ・アクセス・ロジックが前記第２キャッシュの複数の連想セットの中から前記プロセッサ・コアによって生成された前記入力アドレスに対応した前記第２キャッシュの連想セットを決定し、各連想セットがそれぞれの１つまたは複数のキャッシュ・ラインを含む、第２キャッシュ・アクセス・ロジックと、
を含み、
前記第１キャッシュの前記連想セットおよび前記第２キャッシュの前記連想セットが複数の一致グループに対応し、各一致グループがそれぞれ、前記第１キャッシュの複数の連想セットおよび前記第２キャッシュの複数の連想セットを含み、
前記第１キャッシュの各連想セットにそれぞれ対応するアドレスが、同じ一致グループ内の前記第２キャッシュにおける前記複数の連想セットの間で、前記第１キャッシュのそれぞれの連想セットとして割り振られる、
ディジタル・データ処理のための集積回路チップ。
【請求項１２】
前記第１キャッシュの各連想セットのそれぞれに対応するアドレスが、同じ一致グループ内の第２キャッシュにおける前記複数の連想セットの間で、前記それぞれの連想セットを決定するために使用されたアドレス・ビット以外の少なくとも幾つかのアドレス・ビットのハッシュ関数を用いて割り振られる、請求項１１に記載の集積回路チップ。
【請求項１３】
前記ハッシュ関数がモジュロＮ関数であり、Ｎは前記一致グループにおける前記第２キャッシュの連想セットの数である、請求項１２に記載の集積回路チップ。
【請求項１４】
前記一致グループの各々が、前記第１キャッシュのＭ個の連想セットおよび前記第２キャッシュのＮ個の連想セットを含み、ＭおよびＮの最大公約数が１である、請求項１１に記載の集積回路チップ。
【請求項１５】
前記第１キャッシュおよび前記第２キャッシュにおいてデータが重複しない、請求項１１に記載の集積回路チップ。
【請求項１６】
前記第１キャッシュが前記第２キャッシュよりも高いレベルにある、請求項１１に記載の集積回路チップ。
【請求項１７】
前記第２キャッシュが前記第１キャッシュのビクティム・キャッシュである、請求項１６に記載の集積回路チップ。
【請求項１８】
前記第１キャッシュおよび前記第２キャッシュが実メモリ・アドレスを使ってアドレス可能である、請求項１１に記載の集積回路チップ。
【請求項１９】
前記第１キャッシュにおける前記連想セットの各々が複数のキャッシュ・ラインをそれぞれ含み、前記第２キャッシュにおける前記連想セットの各々が複数のキャッシュ・ラインをそれぞれ含む、請求項１１に記載の集積回路チップ。
【請求項２０】
前記第１キャッシュおよび前記第２キャッシュの少なくとも１つを含む、請求項１１に記載の集積回路チップ。
【請求項２１】
複数のプロセッサ・コアを含み、前記複数のプロセッサ・コアが前記第１キャッシュおよび前記第２キャッシュを共用する、請求項１１に記載の集積回路チップ。
【請求項２２】
入力アドレスに応答して、前記入力アドレスに対応した第１キャッシュの連想セットを前記第１キャッシュの複数の連想セットの中から決定するステップであって、各連想セットがそれぞれの１つまたは複数のキャッシュ・ラインを含む、ステップと、
第１キャッシュの連想セットを決定する前記ステップに応答して、第１キャッシュの連想セットを決定する前記ステップにより決定された連想セットが前記入力アドレスに対応するデータを含むかどうかを決定するステップと、
前記入力アドレスに応答して、前記入力アドレスに対応した第２キャッシュの連想セットを前記第２キャッシュの複数の連想セットの中から決定するステップであって、各連想セットがそれぞれの１つまたは複数のキャッシュ・ラインを含む、ステップと、
第２キャッシュの連想セットを決定する前記ステップに応答して、第２キャッシュの連想セットを決定する前記ステップにより決定された連想セットが前記入力アドレスに対応するデータを含むかどうかを決定するステップと、
を含み、
前記第１キャッシュの前記連想セットおよび前記第２キャッシュの前記連想セットが複数の一致グループに対応し、各一致グループがそれぞれ、前記第１キャッシュの複数の連想セットおよび前記第２キャッシュの複数の連想セットを含み、
前記第１キャッシュの各連想セットにそれぞれ対応するアドレスが、同じ一致グループ内の前記第２キャッシュにおける前記複数の連想セットの間で前記第１キャッシュのそれぞれの連想セットとして割り振られる、
ディジタル・データ処理装置においてキャッシュ・メモリを操作する方法。
【請求項２３】
前記第１キャッシュの各連想セットのそれぞれに対応するアドレスが、同じ一致グループ内の第２キャッシュにおける前記複数の連想セットの間で、前記それぞれの連想セットを決定するために使用されたアドレス・ビット以外の少なくとも幾つかのアドレス・ビットのハッシュ関数を用いて割り振られる、請求項２２に記載の方法。
【請求項２４】
前記ハッシュ関数がモジュロＮ関数であり、Ｎは前記一致グループにおける前記第２キャッシュの連想セットの数である、請求項２３に記載の方法。
【請求項２５】
前記一致グループの各々が、前記第１キャッシュのＭ個の連想セットおよび前記第２キャッシュのＮ個の連想セットを含み、ＭおよびＮの最大公約数が１である、請求項２２に記載の方法。
【請求項２６】
前記第１キャッシュおよび前記第２キャッシュにおいてデータが重複しない、請求項２２に記載の方法。
【請求項２７】
前記第１キャッシュが前記第２キャッシュよりも高いレベルにある、請求項２２に記載の方法。
【請求項２８】
前記第２キャッシュが前記第１キャッシュのビクティム・キャッシュである、請求項２７に記載の方法。
【請求項２９】
前記第１キャッシュおよび前記第２キャッシュが実メモリ・アドレスを使ってアドレス可能である、請求項２２に記載の方法。
【請求項３０】
前記第１キャッシュにおける前記連想セットの各々が複数のキャッシュ・ラインをそれぞれ含み、前記第２キャッシュにおける前記連想セットの各々が複数のキャッシュ・ラインをそれぞれ含む、請求項２２に記載の方法。
【請求項３１】
少なくとも１つのプロセッサと、
メモリと、
前記メモリの一部分を一時的に保持する第１キャッシュであって、前記第１キャッシュが複数のアドレス可能な連想セットを有し、各連想セットがそれぞれの１つまたは複数のキャッシュ・ラインを含む、第１キャッシュと、
前記メモリの一部分を一時的に保持する第２キャッシュであって、前記第２キャッシュが複数のアドレス可能な連想セットを有し、各連想セットがそれぞれの１つまたは複数のキャッシュ・ラインを含む、第２キャッシュと、
を含み、
前記第１キャッシュの前記連想セットの各々が前記第１キャッシュの前記連想セットに記憶可能なデータの複数のアドレスにそれぞれ対応し、前記第２キャッシュの前記連想セットの各々が前記第２キャッシュの前記連想セットに記憶可能なデータの複数のアドレスにそれぞれ対応し、
前記第１キャッシュの各連想セットにそれぞれ対応するアドレスが前記第２キャッシュにおける複数の連想セットの間でそれぞれ割り振られ、
前記第２キャッシュの各連想セットにそれぞれ対応するアドレスが前記第１キャッシュにおける複数の連想セットの間でそれぞれ割り振られる、
ディジタル・データ処理装置。
【請求項３２】
前記第１キャッシュの各連想セットにそれぞれ対応するアドレスが、前記第２キャッシュにおける複数の連想セットの間で、前記第１キャッシュの前記それぞれの連想セットを決定するために使用されたアドレス・ビット以外の少なくとも幾つかのアドレス・ビットのハッシュ関数を用いて割り振られる、請求項３１に記載のディジタル・データ処理装置。
【請求項３３】
前記ハッシュ関数がモジュロＮ関数であり、Ｎは前記第１キャッシュの連想セットにおけるアドレスが割り振られる前記第２キャッシュの連想セットの数である、請求項３２に記載のディジタル・データ処理装置。
【請求項３４】
前記第１キャッシュおよび前記第２キャッシュにおいてデータが重複しない、請求項３１に記載のディジタル・データ処理装置。
【請求項３５】
前記第１キャッシュが前記第２キャッシュよりも高いレベルにある、請求項３１に記載のディジタル・データ処理装置。
【請求項３６】
前記第２キャッシュが前記第１キャッシュのビクティム・キャッシュである、請求項３５に記載のディジタル・データ処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ディジタル・データ処理ハードウェアに関し、特に、ディジタル・データ処理装置の処理ユニットのためのキャッシュ・メモリおよび支援ハードウェアの設計および操作に関するものである。
【背景技術】
【０００２】
二十世紀の後半に、情報革命として知られている現象が始まった。情報革命はいずれの事象またはマシンよりも範囲の広範な歴史的開発であるけれども、ディジタル電子式コンピュータ以上に情報革命を代表する単一の装置は現れていない。コンピュータ・システムの開発は、確かに１つの革命であった。毎年、コンピュータ・システムは、より高速になり、より多くのデータを記憶し、そして、より多くのアプリケーションをユーザに提供している。
【０００３】
近代のコンピュータ・システムは、一般に、中央演算処理装置（ＣＰＵ）、並びに、通信情報を記憶し、検索し、および転送するために必要なバスおよびメモリのような支援ハードウェアを含む。更に、それは、入出力コントローラ又はストレージ・コントローラ、並びに、それらに接続され、キーボード、モニタ、テープ・ドライブ、ディスク・ドライブ、ネットワークに結合された通信回線、等のような外界と通信するに必要なハードウェアを含む。ＣＰＵは、システムの心臓である。それは、コンピュータ・プログラムを含む命令を実行し、他のシステム・コンポーネントのオペレーションを指示する。
【０００４】
コンピュータのハードウェアの立場からいえば、ほとんどのシステムが機能的に同じ態様で動作する。プロセッサは、演算、論理比較、および一方ロケーションから他方のロケーションへのデータの移動のような限定されたセットの非常に単純なオペレーションを遂行することができる。しかし、各オペレーションは非常に素早く実行される。膨大な数のこれらの単純なオペレーションを遂行するようにコンピュータに指示するプログラムは、コンピュータが何か複雑なことを行っているという幻想を与える。実質的に同じセットの非常に単純なオペレーションを遂行することおよびそれを非常に高速に行うことによって、コンピュータ・システムの新たなまたは改良された機能をとしてユーザが認めているものが可能になる。従って、コンピュータ・システムに対する改良を継続することは、これらのシステムを絶えずより高速にすることを必要とする。
【０００５】
コンピュータ・システムの全体的な速度（「スループット」とも呼ばれる）は、大雑把にいえば、単位時間あたりに実行されるオペレーションの数として測定することが可能である。概念的には、システム速度に対するすべての可能な改良のうちの最も簡単なものは、種々のコンポーネントのクロック速度、特に、プロセッサのクロック速度を高めることである。例えば、すべてのものが２倍の速さで動作するが、全く同じ態様で働く場合、システムは所与のタスクを半分の時間で遂行するであろう。数多くの個別のコンポーネントから構成された初期のコンピュータ・プロセッサは、コンポーネントを減らすこと、コンポーネントを結合すること、および、最終的にはプロセッサ全体を単一のチップ上に集積回路としてパッケージ化することによって、かなりのクロック速度の改善を得やすかったし、更なるサイズの縮小およびその他の改良によるクロック速度の増加が最終目的であることが続いた。クロック速度の増加に加えて、クロック・サイクル当たりに実行されるオペレーションの平均数を増加させることによって個々のＣＰＵのスループットを高めることが可能である。
【０００６】
一般的なコンピュータ・システムは大量のデータを記憶することができ、プロセッサはこのデータの任意の部分を使用することを要求される。大量のデータを記憶するための一般的に使用される装置（例えば、回転磁気ハードディスク・ドライブ記憶装置）は、記憶されたデータをアクセスするために比較的長い待ち時間を必要とする。プロセッサが１つのオペレーションを実行する度にそのような大容量記憶装置から直接にデータをアクセスすべきであるとすれば、その記憶装置がデータを戻すのを待つことでその時間のほとんどすべてを費やすことになり、実際に、そのスループットが非常に低くなっていることであろう。その結果、コンピュータ・システムは、メモリまたは記憶装置の階層において各次段のレベルがより速いアクセスを行うのに、より少ないデータしか記憶し得ずにデータを記憶する。大容量記憶装置は最低のレベルにあり、その比較的低速の装置上にすべてのデータを記憶する。階層を上げると、メイン・メモリがあり、一般には、メイン・メモリは半導体メモリである。メイン・メモリは、大容量記憶装置よりも遥かに小さいデータ容量しか持たないが、遥かに早いアクセスを行う。更に高いアクセス速度のものがキャッシュであり、これは、単一レベルまたは複数レベルの階層（レベル１が最も高い）におけるものである。キャッシュも半導体メモリであるが、メイン・メモリよりも高速であり、より小さいデータ容量を有する。ネットワーク接続によってアクセス可能なデータ、のような外部記憶されたデータを、コンピュータ・システム自身の大容量記憶装置よりも低い階層の更なるレベルのものであると見なすこともある。これは、ネットワーク接続（例えば、インターネット）から潜在的に得られるデータの量が更に大きいが、アクセス・タイムが更に遅いためである。
【０００７】
プロセッサがメモリ参照アドレスを生成するとき、プロセッサは、先ず、キャッシュにおいて必要なデータを探す（それは、複数のキャッシュ・レベルにおける探索を必要とすることがある）。そのデータがそこにない（「キャッシュ・ミス」と呼ばれる）場合、プロセッサはそのデータをメモリから得るか、または、必要な場合、記憶装置から得る。メモリ・アクセスは比較的大きな数のプロセッサ・サイクルを必要とする。なお、そのプロセッサ・サイクルの間、プロセッサは一般にアイドル状態にある。プロセッサがメモリ参照を生成するとき、比較的長い待ち時間のデータ・アクセスが完了するのをプロセッサが待つ必要がないように、プロセッサが現在必要としているデータを、そのプロセッサに最も近いレベルのキャッシュが記憶していることが理想的である。しかし、いずれのキャッシュ・レベルの容量もメイン・メモリの容量のわずか数分の一であり、メイン・メモリ自身の容量が大容量記憶装置の容量のわずか数分の一であるので、データをすべてキャッシュに単純にロードすることは不可能である。プロセッサが特定のデータ項目を必要とするとき、それがキャッシュ内にあるよう、キャッシュに記憶されるべきデータを選択するための何らかの手法が存在しなければならない。
【０００８】
キャッシュは、一般に、ラインと呼ばれるデータの単位に分割される。なお、ラインは、キャッシュに独立してロードすることまたはキャッシュから除去することが可能な最小単位のデータである。種々の選択的キャッシュ手法のいずれかを支援するためにも、キャッシュとは、一般に、キャッシュ・ラインの連想セットを使用してアドレスされる。連想セットは、１セットのキャッシュ・ラインであり、すべてのキャッシュ・ラインが共通のキャッシュ・インデックス番号を共用する。キャッシュ・インデックス番号は、他のビットも同様に含めることもできるが、一般には、参照アドレスの上位桁ビットから得られる。キャッシュはメイン・メモリよりも遥かに小さく、連想セットは、キャッシュ・インデックス番号に対応したメイン・メモリ・アドレスの小さな一部分しか保持しない。各連想セットは、一般に、複数のキャッシュ・ラインを含むので、連想セットの内容は、種々の手法のいずれによってもメイン・メモリから選択的に選出することが可能である。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
一般に、キャッシュ・ミスの発生時にデータが高レベル・キャッシュにロードされる。キャッシュに記憶されるべきデータを選択するための一般的な手法は、種々のプリフェッチ手法を含み、そのプリフェッチ手法は、特定のキャッシュ・ラインにおけるデータが必要とされることを、そのキャッシュ・ラインに対する実際のメモリ参照に先立って予測し、従って将来の必要性を予想して、キャッシュにデータをロードしようとするものである。キャッシュは限られた容量しか持たないので、キャッシュ・ミス時、またはプリフェッチによってデータをロードするということは、現在キャッシュ内にある幾つかのデータがキャッシュから除去されるかまたは追放されることを意味する。再び、そのような場合にどのデータが追放されるかを決定するための種々の一般的な手法が存在する。
【００１０】
キャッシュの内容を選択するための一般的な手法は限られた成功は得たが、多くの環境では、プロセッサがキャッシュ・ミス時に大量の遊休時間を費やすことがわかっている。この問題に対する一般的な解決方法は、キャッシュのサイズおよび／または連想性を増加させることであった。それらのいずれもかなりの追加ハードウェアを伴う。従って、キャッシュの設計およびオペレーションに対する改良された手法を求めるニーズが存在する。本発明は、このようなニーズに応えるものである。
【課題を解決するための手段】
【００１１】
コンピュータ・システムは、メイン・メモリ、少なくとも１つのプロセッサ、および少なくとも２つのレベルを有するキャッシュ・メモリを含む。高レベルのキャッシュは、複数の連想セットを含み、各連想セットは、それぞれの合同（congruence）グループに含まれ、各一致グループは高レベル・キャッシュの複数の連想セットを有する。低レベルのキャッシュも同様に複数の連想セットを含み、各連想セットは、それぞれの一致グループに含まれ、各一致グループは低レベル・キャッシュの複数の連想セットを有する。高レベル・キャッシュにおける連想セットのキャッシュ・ライン・アドレスは、同じ一致グループ内の低レベル・キャッシュにおける複数の連想セットの間に分散される。
【００１２】
好適な実施例の１つの局面では、低レベル・キャッシュは高レベル・キャッシュのビクティム・キャッシュである。即ち、データは、高レベル・キャッシュから追放されるとき、低レベル・キャッシュにロードされる。データは、高レベル・キャッシュおよび低レベル・キャッシュにおいて重複しないことが望ましい。キャッシュ・ラインは、キャッシュ・ミスのとき、低レベル・キャッシュから、または他のソースから低レベル・キャッシュをバイパスして、高レベル・キャッシュにロードされる。１つのキャッシュ・ラインが高レベル・キャッシュからの追放のために選択されるとき、それは、低レベル・キャッシュにおける１つのラインを追放のために選択させて、自動的に低レベル・キャッシュにロードされる。
【００１３】
好適な実施例では、一致グループは、高レベル・キャッシュ内に１対の連想セットを含み、低レベル・キャッシュ内に３つの連想セットを含む。それらは、インデックス・アドレス・ビットを共用する。モジュロ３のようなアドレス・ハッシュ関数が高レベル・キャッシュにおける連想セット内の幾つかの非共用アドレス・ビットを、低レベル・キャッシュにおける連想セットを選択するインデックスに変換する。
【００１４】
本願では「高レベル・キャッシュ」および「低レベル・キャッシュ」という用語が使用されるけれども、これらは、相対的なキャッシュ・レベル関係を指定するように意図するだけであり、システムが２レベルのキャッシュしか含まないと意味することを意図するものではない。本願において使用されるように、「高レベル」は、プロセッサ・コアに相対的に近いレベルのことをいう。好適な実施例では、「高レベル・キャッシュ」の上に少なくとも１つのレベルのキャッシュが存在し、そのキャッシュは種々の一般的な原理のいずれにおいても動作するものである。
【００１５】
一般に、キャッシュにおける連想セットをインデックスするために使用されるアドレス・ハッシュ手法は連想セットに対するメモリ参照の無作為な分散を生じるものと仮定されているが、これは、データが比較的長いキャッシュ・ライフを有する第２、第３、あるいは更に低いレベルのキャッシュに対しては当てはまらないことが多いと本発明者は考えた。ある連想セットは他の連想セットよりもかなり「ホット」になることが多い。本発明の好適な実施例によれば、高レベル・キャッシュにおける複数の連想セットの中で、次の最低レベル・キャッシュにおける連想セットを効果的に共用することによって、高レベル・キャッシュにおける「ホットな」連想セットからの追放のために低レベル・キャッシュの使用可能な連想セットを増加させることが可能である。その結果、高レベル・キャッシュにおけるキャッシュ・ミスが低レベル・キャッシュから満たされる可能性は、プロセッサがキャッシュ・ミス時にアイドル待ちしている平均時間の必然的な減少と共に増加する。
【００１６】
本発明の構成およびオペレーションに関する詳細は、添付図面を参照することで最もよく理解することが可能である。なお、これらの図面において、同じ参照番号は同様の部分を指す。
【発明を実施するための最良の形態】
【００１７】
図面を参照すると、幾つもの図を通して、同じ参照番号は同じ部分を示し、図１は、本発明の好適な実施例に従って、種々のキャッシュ・レベルにおける重畳した連想セットの一致グループを利用するコンピュータ・システム１００の主要なハードウェア・コンポーネントの高レベル表示である。コンピュータ・システム１００の主要なコンポーネントは、１つまたは複数の中央演算処理装置（ＣＰＵ）１０１Ａ−１０１Ｄ、メイン・メモリ１０２、キャッシュ・メモリ１０６、端末インターフェース１１１、記憶装置インターフェース１１２、入出力（Ｉ／Ｏ）装置インターフェース１１３、および通信／ネットワーク・インターフェース１１４を含み、これらはすべてバス１０３、１０４およびバス・インターフェース１０５を介してコンポーネント間通信のために結合される。
【００１８】
コンピュータ・システム１００は、１つまたは複数の汎用プログラマブル中央演算処理装置（ＣＰＵ）１０１Ａ−１０１Ｄを含む。好適な実施例では、システム１００は、比較的大型のシステムを代表する複数プロセッサを含み、それらは、本願では、フィーチャ１０１と一般的に呼ばれる。しかし、システム１００は、それとは別に、単一ＣＰＵシステムであってもよい。各プロセッサ１０１は、メモリ１０２に記憶された命令を実行する。命令およびデータは、処理のためにメイン・メモリ１０２からキャッシュ・メモリ１０６にロードされる。メイン・メモリ１０２は、データおよびプログラムを記憶するためのランダム・アクセス半導体メモリである。メイン・メモリ１０２およびキャッシュ・メモリ１０６は、図１では、単一の構成要素として概念的に示されるが、実際には、これらが更に複雑であること、特に、本願において更に詳細に記述されるように、キャッシュ・メモリが複数の異なるレベルで存在することがわかるであろう。
【００１９】
メモリ・バス１０３は、ＣＰＵ１０１およびキャッシュ・メモリ１０６と、メイン・メモリ１０２およびＩ／Ｏバス・インターフェース・ユニット（Ｉ／Ｆ）１０５との間でデータを転送するためのデータ・通信・パスを提供する。Ｉ／Ｏバス・インターフェース・ユニット１０５は、更に、種々のＩ／Ｏ装置に及び種々のＩ／Ｏからデータを転送するためのシステムＩ／Ｏバス１０４に接続される。Ｉ／Ｏバス・インターフェース・ユニット１０５は、システムＩ／Ｏバス１０４を介して、Ｉ／Ｏプロセッサ（ＩＯＰ）またはＩ／Ｏアダプタ（ＩＯＡ）としても知られている複数のＩ／Ｏインターフェース・ユニット１１１−１１４と通信を行う。システムＩ／Ｏバス１０４は、例えば、業界標準のＰＣＩバスまたは他の任意の適正なバス・テクノロジであってもよい。Ｉ／Ｏ・バス・インターフェース・ユニット１０５は、種々の記憶装置およびＩ／Ｏ装置との通信をサポートする。例えば、端末インターフェース・ユニット１１１は、１つまたは複数のユーザ端末１２１−１２４の接続をサポートする。記憶装置インターフェース・ユニット１１２は、１つまたは複数のダイレクト・アクセス記憶装置（ＤＡＳＤ）１２５−１２７の接続をサポートする（なお、それらのＤＡＳＤは、一般に、回転磁気ディスク・ドライブ記憶装置であるが、代わりに、ホストにとっては単一の大型記憶装置として見えるように構成されたディスク・ドライブのアレイを含む他の装置であってもよい）。Ｉ／Ｏおよび他の装置インターフェース１１３は、他のタイプの他の任意の入出力装置に対するインターフェースを提供する。２つのそのような入出力装置としてプリンタ１２８およびファクシミリ機器１２９が図１の実施例に示されるが、他の多くのそのような装置が存在し得るし、それは種々のタイプのものであってよい。ネットワーク・インターフェース１１４は、システム１００から他のディジタル装置およびコンピュータ・システムへの１つまたは複数の通信パスを提供する。そのような通信パスには、例えば、インターネット、ローカル・エリア・ネットワークまたは他のネットワークのように１つまたは複数のネットワーク１３０を含めることができるし、或いは、遠隔装置通信回線、無線接続等を含めることができる。
【００２０】
図１は、システム１００の代表的な主要コンポーネントを示すことを意図するものである。個々のコンポーネントは図１に示されたものよりも更に複雑であってもよく、図１に示されたもの以外のコンポーネントまたはそれに付加されたコンポーネントが存在してもよく、そのようなコンポーネントの数、タイプ、および構成が変わっていてもよいことは当然である。本願では、そのような更なる複雑性および更なる変更に関する幾つもの特定の例が開示され、これらが単に例としたものあること、および、必ずしもそのような変更が唯一のものではないことは当然である。
【００２１】
図１では、メイン・メモリ１０２が単一の一体構造の構成要素として示されるけれども、メモリは更に分散されることが可能であり、種々の、いわゆる、いずれの非均一メモリ・アクセス（ＮＵＭＡ）・コンピュータ・アーキテクチャにおいても知られているように、種々のＣＰＵまたはＣＰＵのセットと関連付けることが可能である。図１では、メモリ・バス１０３が、キャッシュ・メモリ１０６、メイン・メモリ１０２、およびＩ／Ｏバス・インターフェース・ユニット１０５の間の直接通信パスを提供する比較的簡単な単一バス構造体として示されるが、実際には、メモリ・バス１０３は、階層構成、スター型構成、またはウェブ構成における２地点間リンクや、複数階層のバスや、並列および冗長パス、等といった種々の形式のいずれにも配列可能な複数の異なるバスまたは通信パスを含むことができる。更に、Ｉ／Ｏバス・インターフェース１０５およびＩ／Ｏバス１０４が単一の個別のユニットとして示されているが、実際には、システム１００は複数のＩ／Ｏバス・インターフェース・ユニット１０５および／または複数のＩ／Ｏバス１０４を含むことができる。システムＩ／Ｏバス１０４を種々のＩ／Ｏ装置に結合する種々の通信パスから分離する複数のＩ／Ｏインターフェース・ユニットが示されているが、それとは別に、幾つかのまたはすべてのＩ／Ｏ装置を１つまたは複数のシステムＩ／Ｏバスに直接に接続することも可能である。
【００２２】
図１に示されたコンピュータ・システム１００は、マルチユーザ・「メインフレーム」・コンピュータ・システムによくあるような複数の付加端末１２１&#12316;１２４を有する。一般に、そのような場合、付加装置の実際の数は図１に示されたものよりも大きいが、本発明はいかなる特定の大きさのシステムにも限定されない。それとは別に、コンピュータ・システム１００は、一般には単一のユーザ・ディスプレイおよびキーボード入力しか含まない単一ユーザ・システムであってもよく、或いは、直接ユーザ・インターフェースをほとんど持たないか、またはまったく持たないが、他のコンピュータ・システム(クライアント)からリクエストを受けるサーバまたは同様の装置であってもよい。
【００２３】
種々のシステム・コンポーネントを説明し、それを高いレベルで示したが、代表的なコンピュータ・システムが、本発明の理解にとって本質的ではない他の多くの図示されてないコンポーネントを含むことは当然である。
【００２４】
図２は、好適な実施例に従った、連想キャッシュ構造体を含むＣＰＵ１０１の主要コンポーネントの高レベル図であり、図１に示されたＣＰＵよりも更に詳細にＣＰＵ１０１を示す。この実施例では、２つのＣＰＵ１０１が、所定のキャッシュ構造体と共に、単一の半導体チップ内にパッケージされる。このために、ＣＰＵ１０１は、一対のＣＰＵを含むチップとそれとを区別するために、「プロセッサ・コア」または「ＣＰＵコア」とも呼ばれることがある。ＣＰＵ１０１は、命令ユニット部分２０１、実行ユニット部分２１１、レベル１命令キャッシュ（Ｌ１ I-キャッシュ）２０５、レベル１データ・キャッシュ（Ｌ１ Ｄ-キャッシュ）２０６、およびアドレス変換ハードウェア（ＡＤＤＲ  ＸＬＡＴＥ）２０７を含む。図２に示されたレベル２キャッシュ（Ｌ２キャッシュ）２０８は、実際には、単一のチップ内の両方のＣＰＵコアによって共用され、従って、ＣＰＵ１０１の一部分とは見なされない。一般に、命令ユニット２０１は、Ｌ１I-キャッシュ２０５から命令を得て、遂行すべきオペレーションを決定するために命令をデコードし、プログラム・フローを制御するためにブランチ条件を決定する。実行ユニット２１１は、レジスタにおけるデータに関して演算および論理的オペレーションを遂行し、Ｌ１Ｄ-キャッシュからデータをロードまたはそのキャッシュに記憶する。Ｌ２キャッシュ２０８はレベル２キャッシュであり、一般には、Ｌ１ I-キャッシュまたはＬ１ Ｄ-キャッシュよりも大きく、Ｌ１I-キャッシュ２０５およびＬ１ Ｄ-キャッシュ２０６にデータを供給する。Ｌ２キャッシュ２０８は、更に低いレベルのキャッシュまたはメイン・メモリから外部インターフェースを介してデータを得る。
【００２５】
命令ユニット２０１は、ブランチ・ユニット２０２、命令デコード／ディスパッチ・ユニット２０３、および命令レジスタ／バッファ２０４を含む。Ｌ１ I-キャッシュ２０５からの命令は、実行前にバッファ２０４にロードされる。ＣＰＵの設計次第で、複数のバッファ（例えば、命令の順次系列のためのものおよびブランチ・トゥー・ロケーションのための別のもの）が存在してもよく、それらのバッファの各々は複数の命令を含むことが可能である。デコード／ディスパッチ・ユニット２０３は、実行されるべき現命令をバッファの１つから受け取り、その命令をデコードして遂行されるべきオペレーションまたはブランチ条件を決定する。ブランチ・ユニット２０２は、ブランチ条件を評価することによってプログラム・フローを制御し、Ｌ１I-キャッシュ２０５からバッファを再補充する。
【００２６】
実行ユニット２１１は、データを記憶するための一組の汎用レジスタ２１２と、命令ユニット２０１によってデコードされた命令に応答して汎用レジスタ２１２におけるデータに関して演算および論理的オペレーションを遂行する整数演算論理ユニット（ＡＬＵ）２１３とを含む。更に、実行ユニット２１１は、浮動小数点演算のような数学的集中オペレーションを遂行するための複合オペレーション・サブユニット２１４を含む。サブユニット２１４は、それ自身の特殊レジスタ（図示されてない）を含むことが可能である。整数ＡＬＵ２１３および複合オペレーション・サブユニット２１４は、一般に、マルチステージ・パイプラインとして実現される。図２に示されたコンポーネントのほかに、実行ユニット２１１は、更なる特殊目的レジスタおよびカウンタ、データをキャッシュ・メモリまたはメイン・メモリからフェッチまたはそれらに記憶するためのロードおよびストア・ハードウェア、コントロール・ハードウェア、等を含むことが可能である。特に、実行ユニット２１１は、整数ＡＬＵ２１３および複合オペレーション・サブユニット２１４のほかにパイプライン(図示されてない)を含むことができる。命令フェッチおよびデコード・パイプラインのような更なるパイプラインはプロセッサ１０１内に存在してもよい。
【００２７】
アドレス変換ハードウェア２０７は、命令ユニット２０１または実行ユニット２１１によって生成された有効アドレスをメモリにおける対応する実アドレスに変換する。好適な実施例では、プロセッサが、それぞれの実行プロセスに対応した有効アドレス空間における「有効アドレス」を生成する。有効アドレスは、更に大きいユニバーサル仮想アドレス空間における「仮想アドレス」に変換される。なお、ユニバーサル仮想アドレス空間には、すべてのプロセスによって共用される１つの仮想アドレス空間が存在する。更に、仮想アドレスは、データが置かれる実際のアドレス・ロケーションに対応する「実アドレス」に変換される。しかし、種々のコンピュータ・アーキテクチャが種々のアドレス構造を使用していること、および本発明がいかなる特定のアドレシング形式にも限定されないことは明らかであろう。
【００２８】
キャッシュ・メモリは、実アドレスを使用してアドレスされることが望ましく、従って、キャッシュ・メモリにおけるデータをアクセスするためには、プロセッサによって生成された有効アドレスが、先ず、アドレス変換ハードウェア２０７によって実アドレスに変換される。アドレス変換ハードウェア２０７は、図２において単一概念の構成要素として示され、変換ルックアサイド・バッファ、セグメント・ルックアサイド・バッファ、有効・実アドレス変換テーブル、またはその他の機構といった、この分野で知られている各種の変換機構のいずれをも、これらの構成のいずれのものにもおけるデータのアクセスおよび変換に関連するハードウェアと共に含むことができる。それとは別に、あるコンピュータ・システム設計において知られているように、プロセッサによって生成された有効アドレスを使用して、幾つかのまたはすべてのキャッシュ・レベルをアクセスすることが可能であろう。
【００２９】
Ｌ１ I-キャッシュ２０５およびＬ１ Ｄ-キャッシュ２０６は、データを命令ユニット２０１および実行ユニット２１１に提供する別々の命令キャッシュおよびデータ・キャッシュである。Ｌ２キャッシュは、命令および非命令データの両方を含む非判別キャッシュである。一般に、データは、命令ユニットまたは実行ユニットによってＬ１キャッシュから取り出されるかまたはＬ１キャッシュに記憶され、そしてデータがＬ１キャッシュにおいて得られない場合、それはＬ２キャッシュ２０８からＬ１キャッシュにロードされる。なお、Ｌ２キャッシュは、そのデータを外部ロケーションから得る。その後、そのデータは、Ｌ１キャッシュから対応するユニット２０１または２１１に転送される。プロセッサの設計次第で、Ｌ１キャッシュをバイパスし、Ｌ２キャッシュ２０８から実行レジスタまたは命令レジスタにデータをロードすることも可能であろう。
【００３０】
好適な実施例では、ＣＰＵ１０１が複数の（望ましくは、２つの）スレッドの同時実行をサポートする。ＧＰレジスタ２１２の別セット（図示されてない）および所定の他の構成体が各スレッドに対して存在する。しかし、サポートされるスレッドの数は変わることがあるし、本発明は、単一スレッドの実行のみをサポートするプロセッサにおいて使用することが可能である。
【００３１】
種々のＣＰＵコンポーネントを説明し、高レベルで図示したが、好適な実施例のＣＰＵが、本発明の理解にとっては本質的でない多くの他のコンポーネント（図示されてない）を含むことは当然である。例えば、一般的な設計では、種々の更なる特殊目的のレジスタが必要であろう。更に、図２のＣＰＵがＣＰＵアーキテクチャの単なる一例であること、およびＣＰＵ１０１内のコンポーネントの数、タイプ、および構成には多くの種々の変更が存在し得ること、図示されたコンポーネントに加えて、図示されてないコンポーネントが存在し得ること、および、図示されたコンポーネントすべてがＣＰＵ設計に存在するわけではないことは明らかであろう。例えば、バッファおよびキャッシュの数および構成が変わってもよく、実行ユニットのパイプラインの数および機能も変わってもよく、レジスタは種々のアレイおよびセットとして構成されてもよく、専用の浮動小数点ハードウェアが存在しても存在しなくてもよい。更に、ＣＰＵ１０１は、各プロセッサ・サイクルによって単一のオペレーションまたは複数のオペレーションのディスパッチをサポートする単純なまたは複雑な命令を有することが可能である。
【００３２】
Ｌ１キャッシュ２０５および２０６は、各ＣＰＵがそれ自身のそれぞれのＬ１キャッシュを有するので、図２ではＣＰＵ１０１の一部として示される。体系的には、キャッシュは、メモリ１０２の一部として見なすことが可能であり、或いは、全体的に別個の構成要素として見なすことも可能である。図２の表示は、典型的なものであることを意図するもので、本発明を任意の特定の物理的なキャッシュ具現化に限定することを意図するものではない。プロセッサ・チップは、図２に表示されたものよりも多くのキャッシュまたは少ないキャッシュを含むことができる。
【００３３】
図３は、好適な実施例に従って、データを記憶およびアドレスするための種々のキャッシュおよび関連構造の階層を更に詳細に示す。この実施例には、メイン・メモリのほかに３つのレベルのキャッシュ・メモリが存在する。プロセッサ１０１は、集積回路プロセッサ・チップ３０１Ａ、３０１Ｂ（本願では、全体的に、フィーチャ３０１と呼ばれる）の上にパッケージされる。各プロセッサ・チップは、一対のプロセッサ１０１（プロセッサ・コア）、チップ上の両プロセッサによって共用される単一のＬ２キャッシュ２０８Ａ、２０８Ｂ（本願では、全体的に、フィーチャ２０８と呼ばれる）、チップ上の両プロセッサによって共用される単一のＬ３キャッシュ・ディレクトリ３０２Ａ、３０２Ｂ（本願では、全体的に、フィーチャ３０２と呼ばれる）、および外部データ・インターフェース３０４Ａ、３０４Ｂ（本願では、全体的に、フィーチャ３０４と呼ばれる）を含む。各Ｌ３キャッシュ・ディレクトリ３０２と関連したＬ３キャッシュ３０３Ａ、３０３Ｂ（本願では、全体的に、フィーチャ３０３と呼ばれる）が、メイン・メモリ１０２よりもプロセッサに物理的に近い位置のプロセッサ・チップの外に設置される。例えば、Ｌ３キャッシュ３０３は、対応するプロセッサ・チップ３０１と共に共通のプリント回路基板上に装着された別の集積回路チップとしてパッケージされてもよい。外部データ・インターフェース３０４は、プロセッサ・チップ境界を横切って、更にプロセッサ・チップとメイン・メモリ１０２との間またはプロセッサ・チップとＬ３キャッシュ３０３との間にある、マラは他の構成体へ向かうメモリ・バス１０３を介して、データの転送を処理する。
【００３４】
レベル３キャッシュは、レベル２キャッシュのビクティム・キャッシュとして作用する。メイン・メモリからのデータは、先ず、Ｌ３キャッシュ３０３をバイパスすることによってＬ２キャッシュ２０８にロードされる。データがＬ２キャッシュ２０８から追放されるとき、そのデータはＬ３キャッシュ３０３にロードされる。それは、Ｌ３キャッシュからＬ２キャッシュに再ロードされるか、または最終的にメイン・メモリに追放される。データは、Ｌ２キャッシュ２０８からＬ１ I-キャッシュ２０５またはＬ１ Ｄ-キャッシュ２０６にロードされる。設計次第で、データをロードするとき、例えば、データをＬ３キャッシュからＬ１キャッシュに直接にロードするよう、他のキャッシュ・レベルをバイパスすることも可能である。
【００３５】
Ｌ２キャッシュおよびＬ３キャッシュにおいてデータが重複してないことが望ましい。即ち、データのキャッシュ・ラインが任意の所与の時間にそれらのキャッシュのいずれか１つにはあってもよいが、両方にはあってはならない。
【００３６】
好適な実施例では、Ｌ２キャッシュおよびＬ３キャッシュの間に１対１の対応が存在するが、これは必ずしも必要ではなく、各Ｌ３キャッシュに対して複数のＬ２キャッシュが存在することも可能である。Ｌ２／Ｌ３のキャッシュ対が単一チップ３０１上の一対のプロセッサ（プロセッサ・コア）によって共用されることが望ましい。
【００３７】
キャッシュは高速になり、より高いレベルでは（プロセッサにより近いレベルでは）漸進的に少ないデータを記憶する。本願において開示された大型コンピュータ・システムを代表する実施例では、各Ｌ２キャッシュ２０８は１２８バイトのキャッシュ・ライン・サイズおよび１６Ｍバイトの合計記憶容量を有する。各Ｌ３キャッシュは１２８バイトのキャッシュ・ライン・サイズおよび４８Ｍバイトの合計記憶容量を有する。Ｌ２キャッシュは８ウェイ連想のものであり、１６Ｋの連想セットに分割される（即ち、各連想セットは８キャッシュ・ラインのデータ、即ち、１Ｋバイトのデータを含む）。Ｌ３キャッシュは１６ウェイ連想のものであり、２４Ｋの連想セットに分割される（即ち、各々が１６キャッシュ・ラインのデータ、即ち、２Ｋバイトのデータを含む）。Ｌ２キャッシュに対するアクセス・タイムは約２０プロセッサ・サイクルであり、Ｌ３キャッシュに対するアクセス・タイムは約１００プロセッサ・サイクルである。同様の目的で、メイン・メモリに対するアクセス・タイムは１０００プロセッサ・サイクルのオーダーであり、従って、メイン・メモリのアクセスとは反対に、Ｌ２または高レベルにおけるキャッシュ・ミスがＬ３キャッシュにおけるデータによって満たされる場合、大きなパフォーマンス利得が実現可能である。一般に、Ｌ１キャッシュは小型で、高速のアクセス・タイムを有する。しかし、これらのパラメータは、単に、現在のテクノロジを使用する大型システムにおける典型的なキャッシュを表す。これらの典型的なパラメータは、テクノロジが進歩するに従って変わり得る。小型のコンピュータ・システムは、一般に、それに対応して小型のキャッシュを有するであろうし、それのキャッシュ・レベルは少ないであろう。本発明は、いかなる特定のキャッシュ・サイズ、アクセス・タイム、キャッシュ・ライン・サイズ、キャッシュ・レベルの数にも限定されないし、特定なレベルにおけるキャッシュが複数のプロセッサによって共用されるかどうか、あるいは単一のプロセッサ専用であるかどうか、または同様の設計パラメータにも限定されない。
【００３８】
その分野では知られているように、キャッシュは、選択的アドレス・ビット（または、ある場合には、スレッド識別子ビットのような付加ビット）から連想セットの識別をデコードすること、および連想セットにおけるキャッシュ・ラインのアドレスと所望のデータ・アドレスとを比較することによってアクセスされる。例えば、キャッシュに１Ｋの連想セットが存在する場合、その１Ｋの中から特定の連想セットを指定するために１０ビットが必要である。理論的に云えば、これらの１０ビットは、各連想セットが、同等の確率でアクセスされるように決定される。
【００３９】
一般的に云えば、コンピュータ・システムの設計者は、典型的には、相対的下位実アドレス・ビットを使用して、これらの下位ビットがメモリ・アクセスの無作為割り振りに対応するという仮定のもとに、連想セットを決定する。その結果、各連想セットが同じ頻度でアクセスされる。しかし、必ずしも十分には理解されていない種々の理由のために、多くの環境では、メモリ・アクセスは、典型的なＬ２またはＬ３キャッシュのレベルにおける下位アドレス・スライスにおいてランダムには分散されない。この現象は、多くのデータベースおよび他のソフトウェア・データ構造の設計によって少なくとも部分的に生じるように見えるが、他の要素が貢献しているかもしれない。これらのデータ構造は、所定のアドレス境界上に揃えられることが多く、ある低レベル・アドレス・ビットにおけるデータをより頻繁にアクセスさせる。この現象は、一般に、数が少ない連想セットおよび平均存続期間が短いデータを有するＬ１キャッシュのレベルでは取るに足りないことである。しかし、Ｌ２またはＬ３キャッシュのレベルでは、種々の連想セット間におけるアクセス頻度の大きな偏差を検出して、アクセス頻度が低い他の連想セットの間に「ホットな」セットを作成することが可能である。
【００４０】
本発明の好適な実施例によれば、連想セットの一致グループはＬ２およびＬ３キャッシュ・レベルで確立される。各一致グループは、Ｌ２レベルにおける複数の連想セットおよびＬ３レベルにおける複数の連想セットを含む。具体的にいうと、好適な実施例では、各グループは、Ｌ２レベルにおける２つの連想セットおよびＬ３レベルにおける３つの連想セットを含む。単一の一致グループ内のＬ２レベルにおける連想セットの各々は、同じ一致グループ内のＬ３レベルにおける連想セットをすべて共用する。従って、Ｌ２レベルにおける連想セットの１つがホットであるが他の連想セットはホットでない場合、Ｌ３キャッシュの同じ一致グループにおける連想セットは、Ｌ２キャッシュのホット連想セットに対応したデータを記憶するためにその大部分が使用され、Ｌ２キャッシュにおけるホット連想セットの観点からＬ３キャッシュの連想性を効果的に増加させる。
【００４１】
図４は、好適な実施例に従って、Ｌ２およびＬ３キャッシュにおける連想セットの一致グループを概念的に表示したものである。図４に示されるように、一致グループ４０１は、Ｌ２キャッシュ２０８内の２つの連想セット４０２、４０３およびＬ３キャッシュ３０３内の３つの連想セット４０４−４０６を含む。一致グループ４０１における各Ｌ２連想セット（即ち、セット４０２および４０３）は、その一致グループにおける３つのＬ３連想セットに対応する。即ち、セット４０２のようなＬ２連想セットにマップされるデータ・アドレスが分散態様で３つのＬ３連想セット４０４−４０６にマップされる。理想的には、これらのアドレスは、３つのＬ３連想セットすべてに対するデータ・アクセスの頻度が等しくなるように、それら３つのＬ３連想セットに分散している。
【００４２】
Ｌ２キャッシュには１６Ｋの連想セットが存在して各一致グループがそのようなセットを２つ含み、Ｌ３キャッシュには２４Ｋの連想セットが存在して各一致グループがそのようなセットを３つ含むので、Ｌ２／Ｌ３キャッシュの対に対して合計８Ｋの一致グループが存在することになる。システムは２つ以上のＬ２／Ｌ３キャッシュの対を有することがあり、その場合、そのような対の各々は８Ｋの一致グループを有する。
【００４３】
図４に示されるように、アクセスされるべきデータの実アドレス４１１が、Ｌ２およびＬ３キャッシュの連想セットを選択するために使用される。この図では、実アドレス４１１は、１２乃至６３の番号を付された５２ビットを含み、ビット６３は最下位ビットである。７個の下位アドレス・ビット、即ち、ビット５７&#12316;６３はアドレスのオフセット部分を構成し、中間範囲のビット(ビット４３&#12316;５６)はインデックス部分であり、そして上位アドレス・ビット（ビット１２&#12316;４３）はタグと呼ばれることがある。オフセット・ビットは、１２８ビットのキャッシュ・ライン内のデータのアドレスを決定する。Ｌ２キャッシュ２０８には１６Ｋの連想セットが存在するので、そのＬ２キャッシュにおける１６Ｋのセットの中から単一の連想セットを指定するためには１４ビットが必要である。好適な実施例では、オフセットのすぐ上の下位実アドレス・ビットであるインデックス・ビット（実アドレス・ビット４３&#12316;５６）がＬ２キャッシュにおける連想セットを選択するために使用される。これらの実アドレス・ビットは、上位キャッシュにおける連想セットを選択するために変更なしに使用される。この実施例では、一致グループ４０１におけるＬ２連想セット４０２、４０３の両方とも同じビット４３&#12316;５５(１３ビット)を共用するので、実質的には、ビット４３&#12316;５５が一致グループを決定し、一方、ビット５６がその一致グループにおける２つの連想セットの１つを選択する。
【００４４】
Ｌ３キャッシュにおける連想セットは、変更されない実アドレス・ビットとハッシュ関数とを結合したものを使用して選択される。詳しく云えば、実アドレス・インデックス・ビット４３&#12316;５５(１３ビット)が一致グループを指定するために使用される。それは、Ｌ２キャッシュにおける一致グループを指定するために使用されたビットと同じビットである。その一致グループにおける３つの連想セット４０４&#12316;４０６の１つを選択するためにハッシュ関数が使用される。
【００４５】
ハッシュ関数とは、任意の所与のデータ・アドレスに対して反復可能であり、かつ一致グループの３つの連想セットにおけるデータ・アクセスのほぼ均等な分散を生じる任意の関数である。好適な実施例では、ハッシュ関数は、実アドレスのある部分のモジュロ３関数である。実アドレスのすべてのタグ・ビット（即ち、７ビットのオフセットおよび１４ビットのインデックスの上にある実アドレス・ビット１２&#12316;４２）のモジュロ３関数を導出することは可能であろうが、付加ビットが更なる遅れおよび／または回路要件を課し、しかも、上位のビットでは、益々恩恵を少なくするので、これらのビットのうちのあるものだけを使用することが望ましい。例えば、モジュロ３関数は、実アドレス・ビット３５&#12316;４２から導出されてもよい。しかし、他の実アドレス・ビットを使用することもできる他のビットの組み合わせや他のハッシュ関数を使用することも可能であろう。３つの連想セットに対するデータ・アドレスの完全に均等な割り振りを、２の累乗である範囲から得ることは不可能であることがわかるであろうが、ハッシュ関数において十分に大きい数のアドレス・ビットが使用される場合、この矛盾は取るに足りないことである。
【００４６】
ハッシュ関数は、低レベル・キャッシュにおけるアドレスの割り振りを散在させることが望ましい。即ち、インデックス・ビットの上のアドレス・ビット（実アドレス・ビット１２&#12316;４２）を考える場合、この範囲における順次アドレスは、一般に、低レベル・キャッシュでは種々の連想セットに割り振られる。モジュロ３の場合、この範囲におけるアドレスは、ラウンド・ロビンに基づき割り振られる。しかし、ハッシュ関数は、一般にはおおむね均等にアドレスを分散すべきであるが、厳密にはラウンド・ロビンでない割り振りを小さな単位（望ましくは、単一キャッシュ・ラインの単位）でもって実行することもある。
【００４７】
図５は、好適な実施例に従って、関連あるアクセス機構を含むＬ２キャッシュ２０８の構造を示したものである。図５を参照すると、Ｌ２キャッシュは、キャッシュ・データ・テーブル５０５およびインデックス５０４を含む。データ・テーブル５０５は、連想セット４０２においてグループ化された複数のキャッシュ・ラインを含む。好適な実施例では、各キャッシュ・ライン５０１が１２８バイトを含み、各連想セット４０２が８個のキャッシュ・ラインを含む。インデックス５０４はインデックス・エントリ５０２の行５０３を含む。各行５０３は、連想セット４０２に対応し、８個のインデックス・エントリを含む。各インデックス・エントリ５０２は、対応するキャッシュ・ライン５０１の実アドレスの少なくとも一部分および制御ビットを含む。制御ビットは、その分野では知られているように、ダーティ・ビットや、最低使用頻度（ＬＲＵ）ビットといった追放されるべきキャッシュ・ラインを選択するための１つまたは複数のビットや、キャッシュ・コヒーレンシ（首尾一貫性）を維持するためのセマフォー、ロック、または同様の機構、として使用される１つまたは複数のビットや、その他を含むことができるが必ずしもそれに限定されない。
【００４８】
セレクタ・ロジック５０６を使用して、所望のデータの実アドレス４１１の所定部分に対応するインデックス５０４の行５０３を選択することによって、１つのキャッシュ・ラインが参照される。好適な実施例では、実アドレスのビット４３乃至５６における１４ビットがセレクタ・ロジック５０６に入力される。しかる後、その選択された行５０３の個別の各インデックス・エントリ５０２における実アドレス５１１が、比較ロジック５０８によって、その参照されたデータの実アドレス４１１と比較される。実際には、実アドレスの上位桁ビット部分（即ち、ビット１２乃至４２）を比較することが必要なだけである。それは、ビット４３&#12316;５６が、本来は、行選択によって比較し、オフセット・ビット５７&#12316;６３はキャッシュ・ラインを決定する必要がないためである。比較一致が得られる場合、比較ロジック５０８は、８個のインデックス・エントリの一致したものに対応する選択信号を出力する。セレクタ・ロジック５０７が、セレクタ５０６によって使用される同じ実アドレス・ビットを使って、キャッシュ・ライン５０１の連想セット４０２を選択し、比較ロジック５０８の出力がその選択された連想セットにおける８個のキャッシュ・ライン５０１の１つを選択する。
【００４９】
図５にはセレクタ・ロジック５０６および５０７が別々の構成要素として示されるが、それらが同様の機能を遂行することは明らかであろう。チップの設計にも依存するが、これらは実際、インデックス５０４におけるインデック行５０３およびキャッシュ・データ・テーブル５０５における連想セット４０２の両方を同時に選択する出力を持った単一のセレクタであってもよい。
【００５０】
Ｌ３キャッシュも同じであるが、キャッシュ・ラインの連想セットを選択するために変更されない実アドレス・ビットのほかにハッシュ関数が使用される。図６は、本発明の好適な実施例に従って、図３におけるＬ３キャッシュ３０３、Ｌ３キャッシュ・ディレクトリ３０２、および関連のアクセス機構の構造を示したものである。
【００５１】
図６を参照すると、Ｌ３キャッシュは、キャッシュ・データ・テーブル６０５およびインデックス６０４を含む。キャッシュ・データ・テーブル６０５は、連想セット４０４におけるグループ化された複数キャッシュ・ラインのデータ６０１を含む。好適な実施例では、各キャッシュ・ライン６０１は１２８バイトを含み、各連想セット４０４は１６個のキャッシュ・ラインを含む。インデックス６０４はインデックス・エントリ６０２の行を含み、各行は連想セット４０４に対応し、１６個のインデックス・エントリを含む。各インデックス・エントリは、対応するキャッシュ・ライン６０１の実アドレス６１１の少なくとも一部分及び制御ビット６１２を含む。制御ビットは、その分野では知られているように、ダーティ・ビットや、最低使用頻度（ＬＲＵ）ビットといった追放されるべきキャッシュ・ラインを選択するための１つまたは複数のビットや、キャッシュ・コヒーレンシを維持するためのセマフォー、ロック、または同様の機構、として使用される１つまたは複数のビットや、その他を含むことができるが、必ずしもそれに限定されない
【００５２】
セレクタ・ロジック６０６を使用して、所望のデータの実アドレス４１１のある部分に対応するインデックス６０４の３つの行６０３のグループを選択することによって、１つのキャッシュ・ラインが参照される。この３行のグループは一致グループ４０１に対応する。好適な実施例では、その一致グループを選択するために、実アドレスのビット４３乃至５５における１３ビットがセレクタ・ロジック６０６に入力される。ハッシュ関数ジェネレータ６０９の出力を使用して、セレクタ６０６により選択された３行のグループから、行６０３の１つが選択される。前に説明したように、ハッシュ関数は実アドレスのある部分のモジュロ３関数であることが望ましいが、代わりに、他のハッシュ関数が使用されてもよい。次に、選択されたデータの各インデックス・エントリのそれぞれにおける実アドレス部分６１１が、参照されたデータの実アドレス４１１の対応する部分と比較ロジック６０８によって比較される。比較一致がある場合、比較ロジック６０８が、１６個のインデックス・エントリの比較一致したものに対応する選択信号を出力する。セレクタ６０６によって使用された同じ実アドレス・ビットを使用して、セレクタ・ロジック６０７がキャッシュ・ライン６０１の３つの連想セットのグループ（即ち、一致グループ）を選択する。ハッシュ関数ジェネレータ６０９の出力を使用して、一致グループにおける単一の連想セット４０４がその３つの連想セットから選択される。比較ロジック６０８の出力が、その選択された連想セット４０４における１６個のキャッシュ・ライン６０１の１つを選択する。
【００５３】
図６に示された構造全体が、ときにはＬ３キャッシュと呼ばれ、あるいはまた、キャッシュ・データ・テーブル６０５および関連の構造体がＬ３キャッシュと呼ばれる。好適な実施例では、一般に、インデックス・テーブル６０４、セレクタ・ロジック６０６、ハッシュ関数ジェネレータ６０９、および比較ロジック６０８を含むＬ３キャッシュ・ディレクトリ３０２が物理的にプロセッサ・チップ３０１内に実現され、一方、キャッシュ・データ・テーブル６０５およびセレクタ・ロジック６０７が物理的にそのチップの外において実現される。ハッシュ関数ジェネレータ６０９は、図３においてフィーチャ３０３として総体的に表されたＬ３キャッシュのオフ・チップ部分において重複してもよい。
【００５４】
動作時には、可能であれば、Ｌ１キャッシュからのメモリ参照が満足される。Ｌ１キャッシュがミスする場合、Ｌ２およびＬ３キャッシュ・インデックス（ディレクトリ）が、選択的実アドレス・ビットを使用して同時にアクセスされ、必要なデータがどちらかのキャッシュにあるかどうかを決定する。そのデータがＬ２キャッシュにある場合、一般に、それはＬ２キャッシュからＬ１キャッシュにロードされるが、変更されないままＬ２キャッシュに残る。（なぜなら、Ｌ２キャッシュが共用され、そのデータが他のプロセッサのＬ１キャッシュ内にあって、一時的に利用し得ないという状況が起こり得るためである）。
【００５５】
データがＬ３キャッシュにある（即ち、Ｌ２キャッシュにない）場合、それは、Ｌ３キャッシュからＬ２およびＬ１キャッシュに同時にロードされる。この場合、最低使用頻度のような種々の一般的な選択手法のいずれかを使用して、Ｌ２キャッシュの１つのデータ・ラインが、Ｌ３キャッシュへの追放のために選択される。Ｌ３キャッシュはＬ２キャッシュにそのラインの１つをロードしようとするので、そのラインがＬ２キャッシュにロードされることはＬ２キャッシュからの追放ラインのための空きを作るであろうし、Ｌ３キャッシュからラインを追放する必要はない。Ｌ１キャッシュに空きを作るために、既存のラインの１つが追放のために選択されるであろう。しかし、Ｌ１キャッシュ・エントリがＬ２キャッシュにおいても重複しているので、この追放ラインは、既にＬ２キャッシュに必ず存在し、それのための空きを作る必要はない。
【００５６】
データがＬ２キャッシュおよびＬ３キャッシュのいずれにもない場合、それはメイン・メモリからＬ２キャッシュおよびＬ１キャッシュにフェッチされる。この場合、任意の一般的な手法を用いて、Ｌ２キャッシュの１つのキャッシュ・ラインがＬ３キャッシュに追放するために選択される。Ｌ３キャッシュに空きを作るためには、再び任意の一般的な手法を用いて、Ｌ３キャッシュにおけるキャッシュ・ラインがメイン・メモリへの追放のために選択されなければならない。
【００５７】
上記のような好適な実施例では、Ｌ２キャッシュは要求時において（即ち、データ参照が行われるときのキャッシュ・ミスの場合に）のみロードされ、Ｌ３キャッシュはＬ２キャッシュのビクティム・キャッシュであり、データはＬ２およびＬ３キャッシュにおいて重複しない。しかし、現在知られている、または今後開発される種々の選択方法のうちのいずれかを使用して、これらのキャッシュの１つまたは両方を操作することは可能であろう。例えば、実際のデータ参照およびキャッシュ・ミスに先立って、データをＬ２キャッシュまたはＬ３キャッシュに将来を見越してロードするために、何らかのプリフェッチ手法を使用することも可能である。
【００５８】
好適な実施例では、一致グループが、高レベルのキャッシュにおいて２つの連想セットを含み、低レベルのキャッシュにおいて３つの連想セットを含む。しかし、これらの数が１つの実施例を表すだけであること、および一致グループが異なる数の連想セットを有し得ることは明らかであろう。一致グループにおける連想セットの数とアクセスの複雑さとの間には何らかの設計トレード・オフが存在するであろう。一般に、各一致グループにおけるより多くの数の連想セットが概して無作為化を改善するが、実装の複雑性を増大させるであろう。
【００５９】
低レベルの連想セットの１つにおける不測のホット・アクティビティを回避するために、同じ２の累乗の境界内におけるアドレスが低レベル・キャッシュにおける種々の連想セット内に分散するよう、一致グループにおける連想セットの数およびハッシュ関数が選択されることが望ましい。このためには、好適な実施例におけるように、２または３のような公約数を持たない数の対を使用することに幾つかの利点がある。例えば、低レベル・キャッシュが各一致グループにおいて３つの連想セットを含む場合、モジュロ３ハッシュ関数が２の累乗の境界内にアドレスを分散させる。しかし、適切なハッシュ関数だけを使用して同様の効果を得ることも可能である。例えば、アドレスの配置を分散させるキャッシュ関数を使用して一致グループ内の低レベル・キャッシュの連想セットが選択される場合、高レベル・キャッシュには２つの連想セットが存在することがあり、低レベル・キャッシュには４つの連想セットが存在することがある。
【００６０】
上述のように、低レベル・キャッシュにおける２の累乗の境界内でアドレスの配置を分散させることが望ましいが、それは厳密には必要とされず、別の方法で、あるいはアドレス配置を分散させることなく、本発明の利点で実現可能である。例えば、他には、（例えば、各一致グループにおける３つの高レベルの連想セットを使用して）高レベル・キャッシュにおいてアドレスの配置を分散させることが可能であろう。
【００６１】
好適な実施例では、高レベル・キャッシュの連想セットにおけるアドレスを低レベル・キャッシュにおける３つの連想セットに分散するために、実アドレスの上位桁ビットを使用するモジュロ３ハッシュ関数が使用される。高レベル・キャッシュの連想セットにおけるアドレスを低レベル・キャッシュにおける複数のセットに分散するために、種々のハッシュ関数または他の関数を使用することも可能である。高レベル・キャッシュのアドレスは小さい単位または１の単位でもって分散されることが望ましく、それは、高レベル・キャッシュにおける連想セットを決定するために用いられる実アドレス・インデックスの上の各順次実アドレス部分について、一般に、異なる連想セットが低レベル・キャッシュにおいては、異なる連想セットが一般に選択されるということを意味する。しかし、これとは別に、実アドレス・インデックスの上に実アドレス部分の連続ブロックを割り振ることも可能であろう。
【００６２】
好適な実施例では、キャッシュまたはメモリをアクセスするとき、有効アドレスが仮想アドレスに変換され、その仮想アドレスが順次実アドレスに変換されるという３レベル・アドレシング方式をコンピュータ・システムが使用する。しかし、本発明は、いずれの特定のアドレシング方式にも限定されないし、３レベルよりも少ないレベルのアドレシング、または３レベルよりも多いレベルのアドレシングを有するシステムに適用することも可能であろう。
【００６３】
本発明の特定の実施例を、代替方法と共に開示したが、「特許請求の範囲」の範囲内で形式および詳細に関する更なる変更を行い得ることは当業者には明らかであろう。
【図面の簡単な説明】
【００６４】
【図１】本発明の好適な実施例に従って、種々のキャッシュ・レベルにおける連想セットを重畳する一致グループを利用したコンピュータ・システムの主要ハードウェア・コンポーネントの高レベル・ブロック図である。
【図２】好適な実施例のコンピュータ・システムにおけるＣＰＵコアの主要コンポーネントの高レベル・ブロック図である。
【図３】好適な実施例に従って、データを記憶し、アドレスするための種々のキャッシュおよび関連構造の階層を更に詳細に示す図である。
【図４】好適な実施例に従って、高レベル・キャッシュおよび低レベル・キャッシュにおける連想セットの一致グループの概念的表示を示す図である。
【図５】好適な実施例に従って、関連あるアクセス機構を含むＬ２キャッシュの構成を示す図である。
【図６】好適な実施例に従って、関連あるアクセス機構を含むＬ３キャッシュの構成を示す図である。
【図１】
2005174341.tif 000003
【図２】
2005174341.tif 000004
【図３】
2005174341.tif 000005
【図４】
2005174341.tif 000006
【図５】
2005174341.tif 000007
【図６】
2005174341.tif 000008