JP2008544366A - 柔軟な構成を有するキャッシュ、それを使用するデータ処理システム、およびそのための方法 - Google Patents

Abstract

キャッシュ（１２０）は、バス（１１６）に結合することができ、アレイ（１２５）と、コントローラ（１２２）とを備える。アレイ（１２５）は、複数のセット（２００，２１０，２２０）を有し、各セットは、複数のキャッシュ・ライン（２０２）を有し、各セット内の各キャッシュ・ラインは、タグおよび複数のデータ語を含む。コントローラ（１２２）は、アレイ（１２５）と結合していて、コンフィグレーション値（２３２，２３４）により、各セットの複数のキャッシュ・ライン（２０２）の第１の部分（２０５）を第１のバス動作タイプと関連付け、各セットの複数のキャッシュ・ライン（２０２）の第２の部分（２０６）を第２のバス動作タイプと関連付ける。コントローラ（１２２）は、また、バス動作中、バス（１１６）を通るデータを、バス動作のタイプが第１のバス動作タイプである場合には、第１の部分（２０５）に選択的に格納するか、またはバス動作のタイプが第２のバス動作タイプである場合には、第２の部分（２０６）に選択的に格納する。

Description

本発明は、概して、データ処理システムに関し、特に、データ処理システムで使用するためのキャッシュに関する。

コンピュータ・システムの性能を向上するための周知の方法は、キャッシュと呼ばれるローカル高速メモリを内蔵させる方法である。キャッシュはシステムの性能を向上する。何故なら、中央処理装置（ＣＰＵ）が特定のアドレスでデータ（データまたはデータ・オペランド）にアクセスした場合、そのすぐ後でそのデータまたは隣接するアドレスのところのデータにアクセスする確率が高いからである。キャッシュは、速度の遅いメインメモリまたは下位レベル・キャッシュから、要求されたデータに隣接して位置するデータを取り出し、格納する。

非常に高性能なコンピュータ・システムにおいては、いくつかのキャッシュを階層的に配置することができる。上位レベルまたは「Ｌ１」キャッシュと呼ばれるＣＰＵに最も近いキャッシュは、階層で最上位レベルのキャッシュであり、一般に最も高速なキャッシュである。次に、他の一般に速度の遅いキャッシュは、メインメモリに接続している最下位レベルのキャッシュまで「Ｌ２」キャッシュから開始して、階層に降順に配置される。最近のシングル・チップ・マイクロプロセッサまたはシステム・オン・チップ（ＳＯＣ）は、通常、チップ上にＬ１およびＬ２キャッシュの両方を備える。

キャッシュ階層のレベルの他に、それが格納しているデータのタイプによりキャッシュを分類することもできる。命令キャッシュは、メモリから取り出した命令を格納する。データ・キャッシュは、メモリからキャッシュに割り当てられたデータ・オペランドを格納する。普及しているシステム構成は、別々のＬ１命令およびデータ・キャッシュおよび複合命令およびＬ２レベルのところにデータ・キャッシュを備える。

基本キャッシュは、複数語キャッシュ・ラインに分割されている大型のスタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）を備える。キャッシュは、キャッシュ・ラインの結合性の度合いによって変わる。完全結合性キャッシュの場合には、メモリからの任意のラインをキャッシュ内の任意のラインに格納することができる。セット結合性キャッシュは、セット内の各キャッシュ・ラインが、セット内の他のキャッシュ・ラインと共通の、セット索引と呼ばれるそのアドレスの一部を有するセットにグループ分けされたキャッシュ・ラインを備える。ダイレクト・マッピングしたキャッシュは、メモリの各ラインのための特定の位置を有する。セット結合性技術が通常使用される。何故なら、この技術は、管理できる量にアクセス中アドレス比較の数を制限し、それにより妥当な大きさの回路エリアで大型のキャッシュ・アレイを構成することができるからである。

セット結合性キャッシュにおいては、セット内の各キャッシュ・ラインまたは「ウェイ」は、アドレスの一部を格納する対応するタグを有する。アクセス・アドレスのこの部分と、対応するセット内の有効なキャッシュ・ラインのタグ間の一致はキャッシュ・ヒットと呼ばれる。タグは、通常、アクセス・アドレスを、セット内の各キャッシュ・ラインのタグと迅速に比較するために、内容アドレス可能メモリ（ＣＡＭ：ｃｏｎｔｅｎｔ ａｄｄｒｅｓｓａｂｌｅ ｍｅｍｏｒｙ）と一緒に実施される。

キャッシュの回路エリアの大部分はＳＲＡＭであるので、キャッシュのある部分を独立ＳＲＡＭとして使用するためにプログラムすることができることはよく知られている。Ｔｅｒｒｙ Ｂｉｇｇｓ他は、米国特許第５，４１０，６６９号に、キャッシュの一部をセット単位でＳＲＡＭとして使用することができるようにする技術を開示している。この分割により、プログラマはより柔軟にプログラムすることができる。

キャッシュが完全にデータで満たされると、近い将来必要になる可能性が低いデータを置換することにより、キャッシュ・ライン内に新しいデータを格納する必要がある。それ故、最長時間未使用（ＬＲＵ：ｌｅａｓｔ−ｒｅｃｅｎｔｌｙ ｕｓｅｄ）キャッシュ・ラインを除去するために選択することが望ましい。真のＬＲＵシステムを実施する際にこの問題を解決するために、大部分のキャッシュは擬似ＬＲＵシステムを使用する。
米国特許第５，４１０，６６９号

ＣＰＵが必要とする命令およびデータ・オペランドの他に、キャッシュは、また、後の処理のためにデータ通信フレームを格納するための便利な場所でもある。しかし、この目的のためにキャッシュを使用すると、高速データ通信トラフィック中に効率が低下する恐れがある。ネットワーク上の集中的活動中に、データ通信フレームのために使用したキャッシュの一部が成長し、ＣＰＵ命令およびデータを格納するために使用することができる位置を押し出す（ｃｒｏｗｄ ｏｕｔ）恐れがある。この押し出しによって、ＣＰＵの動作の効率が低下させる恐れがある。何故なら、ＣＰＵはメモリ階層の下位レベルから必要な命令およびデータを取り出し、より頻繁にメインメモリに比較的遅いアクセスを行わなければならないからである。

それ故、押し出しが制限または制御されるキャッシュ・システムが求められている。

本発明は、そのようなキャッシュ・システムを提供する。その機能および利点は、添付の図面を参照しながら下記の詳細な説明を読めば明らかになるだろう。
類似の参照符号が類似のまたは同一のアイテムを示す添付の図面を参照すれば、当業者であれば本明細書をよりよく理解することができるだろうし、その多くの機能および利点を理解することができるだろう。

異なる図面の同じ参照符号は、類似のまたは同一のアイテムを示す。
ある形態の場合には、キャッシュはバスと結合して、アレイと、コントローラとを備える。アレイは、それぞれが複数のキャッシュ・ラインを有する複数のセットを有し、各セット内の各キャッシュ・ラインは、タグおよび複数のデータ語を含む。コントローラは、アレイに結合していて、コンフィグレーション値により、各セットの複数のキャッシュ・ラインの第１の部分を第１のバス動作タイプと関連付け、各セットの複数のキャッシュ・ラインの第２の部分を第２のバス動作タイプと関連付ける。コントローラは、また、バス動作中、バスを通るデータを、バス動作のタイプが第１のバス動作タイプである場合には、第１の部分に選択的に格納するか、またはバス動作のタイプが第２のバス動作タイプである場合には、第２の部分に選択的に格納する。

このようなキャッシュの場合には、第１のバス動作のタイプは、入出力スタッシュ・バス動作であってもよいし、第２のバス動作のタイプは、プロセッサ・バス動作であってもよい。この場合、コントローラは、さらに、コンフィグレーション値によりスタティック・ランダム・アクセス・メモリとして使用する各セットの複数のキャッシュ・ラインの第３の部分を関連付けることができる。キャッシュは、さらに、コンフィグレーション値を格納するためにコンフィグレーション・レジスタを含むことができる。コンフィグレーション・レジスタは、第１の部分のサイズを決定するための第１のフィールド、および第３の部分のサイズを決定するための第２のフィールドを含むことができる。第２の部分のサイズは、第１の部分または第３の部分に位置していない複数のキャッシュ・ラインの残りの部分である。

またこのようなキャッシュの場合、コントローラは、バス動作のタイプに対応する複数のキャッシュ・ラインの第１および第２の部分のうちの一方から置換のためのキャッシュ・ラインを選択するために、バス動作のアドレスに応じる置換ロジックを含むことができる。置換ロジックは、さらに、置換のためのキャッシュ・ラインを選択するために、擬似最長時間未使用（ＬＲＵ）アルゴリズムを実行することができる。各セットは、また、複数の履歴ビットを格納することができ、コントローラは、コンフィグレーション値により識別した不適格ライン（ｉｎｅｌｉｇｉｂｌｅ ｌｉｎｅ）を避けながら、置換のためのキャッシュ・ラインを決定するために複数の履歴ビット上で動作することができる。

他の形態の場合には、データ処理システムは、第１のバスと、中央処理装置（ＣＰＵ）と、入出力コントローラと、キャッシュとを含む。ＣＰＵは、第１のバスに結合していて、第１のバス上でプロセッサ・バス動作を実行する。入出力コントローラは、第１のバス上で入出力スタッシュ・バス動作を実行する。キャッシュは、第１のバスに結合していて、アレイおよびコントローラを含む。アレイは、それぞれが、複数のキャッシュ・ラインを有する複数のセットを有し、各セットの各キャッシュ・ラインは、タグと複数のデータ語を含む。コントローラは、アレイに結合していて、コンフィグレーション値により、各セットの複数のキャッシュ・ラインの第１の部分を入出力スタッシュ・バス動作と関連付け、各セットの複数のキャッシュ・ラインの第２の部分をプロセッサ・バス動作と関連付ける。コントローラは、また、バス動作中、第２のバスを通るデータを、バス動作が入出力スタッシュ・バス動作である場合には、第１の部分に選択的に格納するか、またはバス動作がプロセッサ・バス動作である場合には、第２の部分に選択的に格納する。

第１のバス、中央処理装置、入出力コントローラ、およびキャッシュを１つの集積回路上で結合することができる。この場合、データ処理システムは、入出力コントローラと結合している第２のバスと、第１のバスおよび第１のバスに第２のバス上の入出力スタッシュ・バス動作を提供する第２のバスと結合しているコヒーレンシ・モジュールとを含むことができる。この場合、入出力コントローラは、さらに、入出力スタッシュ・バス動作でない他のバス動作を実行することができる。例えば、入出力コントローラは、データ通信ヘッダに対して入出力スタッシュ・バス動作を実行することができ、データ通信ペイロード・データに対して入出力スタッシュ・バス動作でない他のバス動作を実行することができる。

ある特定の実施形態の場合には、中央処理装置は、レベル１（Ｌ１）キャッシュと、レベル２（Ｌ２）キャッシュとしてのキャッシュ機能とを含む。
コントローラは、バス動作のタイプに対応する複数のキャッシュ・ラインの第１および第２の部分のうちの一方から置換のためのキャッシュ・ラインを選択するために、バス動作のアドレスに応じる置換ロジックを備えることができる。このような置換ロジックは、さらに、置換のためのキャッシュ・ラインを選択するために、擬似最長時間未使用（ＬＲＵ）アルゴリズムを実行することができる。この場合、各セットは、複数の履歴ビットを格納することができ、コントローラは、コンフィグレーション値により識別した不適格ラインを避けながら、置換のためのキャッシュ・ラインを決定するために複数の履歴ビット上で動作することができる。

さらに他の形態は、キャッシュを編成するための方法を提供する。キャッシュのアレイが、それぞれが複数のキャッシュ・ラインを有する複数のセットに編成され、各キャッシュ・ラインは、タグおよび複数のデータ語を含む。コンフィグレーション値が受信され、格納される。コンフィグレーション値により、各セットの複数のキャッシュ・ラインの第１の部分は、第１のバス動作タイプと関連付けられ、各セットの複数のキャッシュ・ラインの第２の部分は、第２のバス動作タイプと関連付けられる。バス動作中、バスを通るデータは、バス動作が第１のバス動作タイプである場合には、第１の部分に選択的に格納されるか、またはバス動作が第２のバス動作タイプである場合には、第２の部分に選択的に格納される。

複数のキャッシュ・ラインの第１の部分と第１のバス動作タイプとの関連付けのステップは、さらに、複数のキャッシュ・ラインの第１の部分と入出力スタッシュ・バス動作との関連付けのステップを含むことができ、複数のキャッシュ・ラインの第２の部分と第２のバス動作タイプとの関連付けのステップは、複数のキャッシュ・ラインの第２の部分とプロセッサ・バス動作タイプとの関連付けのステップを含むことができる。この方法は、また、コンフィグレーション値によりスタティック・ランダム・アクセス・メモリとして使用する各セットの複数のキャッシュ・ラインの第３の部分の関連付けのステップを含むこともできる。

ここで図面を参照すると、図１は、本発明によるデータ処理システム１００のブロック図である。データ処理システム１００は、一般に、中央処理装置（ＣＰＵ）コア１１０と、レベル２（「Ｌ２」）キャッシュ１２０と、コヒーレンシ・モジュール１３０と、バス１４０と、ダブルデータ・レート（ＤＤＲ）同期式ダイナミック・ランダム・アクセス・メモリ（ＳＤＲＡＭ）コントローラ１５０と、ローカル・バス・インタフェース１６０と、イーサネット（登録商標）・コントローラの形式の入出力コントローラ１７０および１８０と、以下にさらに詳細に説明する種々の周辺装置が取り付けられている周辺ハブ１９０とを含む。図の実施形態の場合には、データ処理システム１００の構成要素は、１つの集積回路に結合している。それ故、ローカル・バス・インタフェース１６０は、オフチップ・ローカル・バスに接続していて、ＤＤＲ ＳＤＲＡＭコントローラ１５０は、オフ・チップＤＤＲ ＳＤＲＡＭに接続している。データ処理システム１００の同じ基本構成要素を使用して、種々の他の集積回路構成が可能であることを理解することができるだろう。

ここでデータ処理システム１００の構成要素を参照すると、ＣＰＵコア１１０は、高性能縮小命令セット・コンピュータ（ＲＩＳＣ）コアである。高性能の一部として、ＣＰＵコア１１０は、レベル１（「Ｌ１」）データ・キャッシュ１１２およびＬ１命令キャッシュ１１４を含む。ＣＰＵコア１１０は、また、ロードおよび格納アクセスを行うフロントサイド・バス１１６へのインタフェースを含む。

Ｌ２キャッシュ１２０は、フロントサイド・バス１１６への２方向接続を含み、非排他的配置構成でＬ１データ・キャッシュ１１２およびＬ１命令キャッシュ１１４と連動して動作する複合命令およびデータ・キャッシュである。より詳細に説明すると、Ｌ２キャッシュ１２０は、ＣＰＵ命令およびデータ・オペランド、および入出力データを格納する。入出力データは、以下にさらに詳細に説明するように、データ通信フレームの一部の形をしている。Ｌ２キャッシュ１２０は、一般に、コントローラ１２２およびキャッシュ・ライン１２５のアレイを含む。以下にさらに詳細に説明するように、アレイ１２５は、キャッシュ・ラインを格納するためのＳＲＡＭ、およびタグを格納するためのキャッシュ・ラインに対応する位置を有するＣＡＭを含む。

コヒーレンシ・モジュール１３０は、フロントサイド・バス１１６および内部バス１４０の両方に２方向に接続している。コヒーレンシ・モジュールは、２つの基本機能を実行する。最初に、このモジュールは、バス１４０上で読取り／書込み動作をスヌープし（ｓｎｏｏｐ）、キャッシュ１１２、１１４および１２０に、キャッシュ・ヒットを探索させ、ある入出力トランザクションのデータを格納させる。次に、このモジュールは、バス１１６とバス１４０の間にブリッジを形成し、そのためＣＰＵコア１１０は、内部バス１４０上の装置にアクセスすることができる。

ローカル・バス・インタフェース１６０は、バス１４０および外部バス上のトランザクション間でブリッジとしての働きをする。外部バスは、例えば、汎用メモリ・バスであってもよい。

イーサネット・コントローラ１７０および１８０は、別のイーサネット・リンクに接続していて、これらのリンクとの間でデータ・フレームを送受信する。図に示すように、これらのコントローラは、データ・リンク層機能の少なくとも一部を実行し、オフ・チップ物理層装置へのインタフェースとしての働きをする。それ故、イーサネット・コントローラ１７０および１８０は、データ通信フレームのためのソースであり、シンクである。コヒーレンシ・モジュール１３０は、スヌープのためにグローバルに可視的でなければならないトランザクションを認識し、それらをＬ２キャッシュ１２０内に格納するためにフロントサイド・バス１１６を通してトランザクションを提供する。それ故、イーサネット・コントローラ１７０および１８０は、データ通信フレーム負荷を有利に提供し、それらをスヌープのためにグローバルに可視的であるものとして識別する属性と一緒にトランザクションを格納する。

ＤＤＲ ＳＤＲＡＭコントローラ１５０は、ＪＥＤＥＣ標準ＪＥＳＤ−７９に適合する外部大容量記憶装置に対してインタフェースとしての働きをする。他の実施形態の場合には、ＤＤＲ ＳＤＲＡＭコントローラ１５０は、いわゆるＤＤＲ−ＩＩ標準、ＪＥＳＤ−９０標準、ある他の標準、または従来の非同期式ＤＲＡＭに適合するものであってもよい。

ハブ１９０は、種々様々な周辺装置へ接続するための相互接続点またはブリッジである。データ処理システム１００は、入出力メッセージング・ユニット１９１と、最大４つのレーンを有するリンク１９３への１つのブロック１９２として示すＲａｐｉｄＩＯ Ｔｒａｄｅ Ａｓｓｏｃｉａｔｉｏｎが発行するプロトコルのシリアル形式により動作する「ＳＲＩＯ」で示す４つのリンクと、最大８つのレーンを有するリンク１９５へのＰＣＩ−Ｅ（Ｐｅｒｉｐｈｅｒａｌ Ｃｏｍｐｏｎｅｎｔ Ｉｎｔｅｒｃｏｎｎｅｃｔ−Ｅｘｐｒｅｓｓ）バス・インタフェース１９４と、対応するＰＣＩリンク１９７に接続している専用ＰＣＩまたはＰＣＩ−Ｘコントローラ１９６と、ダイレクト・メモリ・アクセス（ＤＭＡ）コントローラ１９８とを含むこのような装置の種々のものを含む。ハブ１９０に接続している周辺装置は、単に例示としてのものに過ぎないことを理解されたい。

イーサネット・コントローラ１７０および１８０は、通常の１０メガビット／秒（Ｍｂｐｓ）イーサネット・リンク、１００Ｍｂｐｓでの高速イーサネット、または１ギガビット／秒（Ｇｂｐｓ）でのギガビット・イーサネットで動作することができる。理解してもらえると思うが、このような高速での通信は、時として、Ｌ２キャッシュ１２０内に大容量のフレーム・データが蓄積する結果になり、そうなると最終的には押し出し効果によりＣＰＵコア１１０の性能の劣化が始まる。しかし、本発明によれば、Ｌ２キャッシュ１２０は、入出力（Ｉ／Ｏ）データまたはＣＰＵデータのためにアレイ１２５の一部を専用に使用することができる。Ｉ／Ｏスタッシング（Ｉ／Ｏ ｓｔａｓｈｉｎｇ）と呼ばれるＩ／Ｏ動作については、図２〜図４のところで以下にさらに詳細に説明する。しかし、一般に、Ｉ／Ｏスタッシングという用語は、Ｉ／Ｏバス動作中に行われたデータをキャッシュ内に格納することを意味する。例えば、イーサネット・コントローラ１７０は、バス１４０を通してメモリにイーサネット・フレーム・データを書き込むことができ、Ｌ２キャッシュ１２０は、このデータを有利にスタッシュすることができる。何故なら、すぐ後でＣＰＵコア１１０による処理のためにこれが必要になるからである。この機能により、データ通信タスクをサポートするために、Ｌ２キャッシュ１２０の第１のプログラム可能な部分を入出力動作のために取っておく（すなわち、入出力動作と関連付ける）ことができ、押し出しを実質的に避けるために第２のプログラム可能な部分をＣＰＵ命令およびオペランド・データのために取っておくことができる。さらに、以下に説明するように、キャッシュ１２０の第３のプログラム可能な部分を汎用ＳＲＡＭとして専用に使用することができ、異なるシステムのニーズに対して高度な柔軟性を提供することができる。

図２は、その編成を理解するのに役立つ図１のキャッシュ１２０の一部のブロック図である。図２に示すように、キャッシュ１２０は、アレイ１２５、およびコントローラ１２２と関連する「Ｌ２キャッシュ制御レジスタ」で示す制御レジスタ２３０を含む。アレイ１２５は、「セット０」で示すセット２００と、「セット１」で示すセット２１０と、「セットＮ」で示すセット２２０とを含むＮ組のキャッシュ・ラインを含む。各セットは、８つのキャッシュ・ライン２０２と、共通の一組の擬似最長時間未使用（ＰＬＲＵ）ビット２０４とを有する８ウェイ・アソシアティブである。本明細書に記載するように、ＰＬＲＵビット２０４は、セット２００のキャッシュ・ラインへのアクセスの履歴を格納するための履歴ビットとしての働きをする。各キャッシュ・ラインは、ウェイ０〜ウェイ７のグループのウェイおよび「語［０〜７］」で示す８つのデータ語のグループの両方に対応する「アドレス・タグ０」〜「アドレス・タグ７」で示す対応するタグを有する。各キャッシュ・ラインも、キャッシュ・ラインが有効か否かを示す有効ビットを含む、図２には詳細に示していない、キャッシュ・コヒーレンシを実施するための制御ビットを含む。

アレイ１２５のセットは、さらに、バンクと呼ばれるセットのグループに編成される。例えば、アレイ１２５は、各セットが３２バイトの８つのキャッシュ・ラインまたは「ウェイ」を含む２５６組の８つのバンクに編成される。それ故、キャッシュ１２０は、８×２５６×８×３２＝５１２Ｋバイトのメモリを含む。図２の特定の実施形態の場合には、１語の長さは４バイトであるが、他の実施形態の場合には、キャッシュ・ラインは、異なる長さであってもよいことに留意されたい。

ＰＬＲＵビット２０４は、キャッシュ置換アルゴリズムを実施するために使用される。例えば、特定のアクセス・アドレスのバンクおよびセット索引は、セット０内のラインに新しいデータが割り当てられることを示す。ＰＬＲＵビット２０４は、バス動作タイプおよびロッキング機構の関連と一緒に、図４のところで以下にさらに詳細に説明するように、どのキャッシュ・ラインをキャストアウトしなければならないかを決定する。

押し出しを実質的に避けるために、Ｌ２キャッシュ制御レジスタ２３０は、各セットの第１の部分をＩ／Ｏスタッシュ動作と関連付け、各セットの第２の部分をプロセッサ・バス動作と関連付けるためにコンフィグレーション値を格納する。この関連付けにより、ネットワーク・トラフィックが込み合っている時間でも、ある量のキャッシュをプロセッサが確実に使用できるようにする。プロセッサは引き続き効率的に動作することができる。特定のアーキテクチャにおいては、コントローラ１２２が、バス・トランザクション中に、バス・マスタが発行した「転送タイプ」と呼ばれる一組の信号、およびトランザクションのアドレスの両方を検査することによりバス動作タイプを決定する。転送タイプおよびアドレスの両方を考慮に入れた場合には、コントローラ１２２は、イーサネット・コントローラ１７０および１８０が始動したトランザクションのうちのあるものだけを、キャッシュする必要があるＩ／Ｏスタッシュ動作として解釈することができる。それ故、例えば、ＣＰＵコア１１０によりシーケンシャルに処理されるデータ通信ヘッダ・データをキャッシュ１２０で使用することができ、一方、ペイロード・データはキャッシュに格納されない。しかし、他の実施形態の場合には、これらおよび他の要因をバス動作タイプを決定するために他の方法で使用することができる。

Ｌ２キャッシュ１２０も、各セットの一部をＳＲＡＭ専用に使用することができ、高速スクラッチパッド・メモリ用の専用ＳＲＡＭを必要とするシステムの柔軟性を改善する。
「Ｌ２ＳＲＡＭ」で示す最初の３ビット・フィールド２３２は、上部から開始する各セットのどの部分が、ＳＲＡＭ部分２０７として示すＳＲＡＭ機能と関連するのかを決定する。Ｌ２ＳＲＡＭにより、０、１、２、４および８ウェイのサイズをＳＲＡＭ機能と関連付けることができる。「Ｌ２ＳＴＡＳＨＣＴＬ」で示す第２の２ビット・フィールド２３４は、底部から開始する各セットのどの部分を、Ｉ／Ｏ ＳＴＡＳＨ部分２０５で示すＩ／Ｏスタッシュ機能と関連付けるのかを決定する。Ｌ２ＳＴＡＳＨＣＴＬにより、０、１、２および４ウェイをＩ／Ｏスタッシュ機能と関連付けることができる。中央の残りの任意の部分は、ＰＲＯＣＥＳＳＯＲ ＣＡＣＨＥ部分２０６で示すプロセッサ・キャッシュ機能と関連する。Ｌ２ＳＲＡＭフィールド２３２およびＬ２ＳＴＡＳＨＣＴＬフィールド２３４は、Ｌ２ＣＡＣＨＥ ＣＯＮＴＲＯＬ ＲＥＧＩＳＴＥＲ２３０が、フィールドのうちの任意の２つのサイズを指定することにより各セットの３つのすべての部分のサイズを決定することができ、これら３つの部分のサイズを決定するためのフィールドが他の実施形態で変化することができる３つの部分に対するコンフィグレーション値を集合的に形成する。

図２の例の場合には、Ｌ２ＳＲＡＭフィールド２３２は、ＳＲＡＭ部分が、ウェイ０およびウェイ１に対応する各セット内に上部の２つのキャッシュ・ラインを含んでいることを示すために「１００」の値を有する。Ｌ２ＳＴＡＳＨＣＴＬフィールド２３４は、Ｉ／Ｏスタッシュ・エリアが、ウェイ６およびウェイ７に対応する各セット内に２つのキャッシュ・ラインを含んでいることを示すために「１０」の値を有する。それ故、プロセッサ・キャッシュ・エリアは、ウェイ２〜ウェイ５に対応する各セットの中央に残りの４つのキャッシュ・ラインを含む。

図３は、図１のキャッシュ・コントローラ１２２内のキャッシュ・アクセス・ロジックが使用するキャッシュ・アクセス・アルゴリズムのブロック図である。コントローラ１２２は、「ＡＤＤＲ」３２０で示す３６ビット・アクセス・アドレスを検査することによりルックアップ・プロセスを実行する。ＡＤＤＲ３２０は、８つの使用可能なバンクのうちの１つを選択するために、コントローラ１２２が３ビット・バンクとして使用するビット２０〜２２に対応する第１の部分３２２と、選択したバンク内の２５６の使用可能なセットのうちの１つを選択するために、コントローラ１２２が８ビットのセット索引３３２として使用するビット２３〜３０に対応する第２の部分３２４と、３ビット・ウェイ選択索引３３４を形成するために、コントローラ１２２が間接的に使用するビット０〜１９に対応する第３の部分３２６と、５ビット・バイト選択索引３３６としてコントローラ１２２が使用するビット３１〜３５に対応する第４の部分３２８とを含む。バンクおよびセットが決定すると、２０ビット・ウェイ選択比較が、８つの２０ビット・タグ３１０を使用して並列に８回の比較を行うことにより、キャッシュ内にラインが格納されているか否かを判定する。一致した場合（および有効ビットが示すようにラインが有効である場合）、ＡＤＤＲのタグ部分と一致する８つのキャッシュ・ラインのうちの１つが選択したウェイを示す。

ヒットが存在しない場合には、ＡＤＤＲ３２０に対応するキャッシュ・ラインを、キャッシュの選択したエリアに割り当てることができる。割り当てプロセスは、既存のキャッシュ・ラインを新しいキャッシュ・ラインで置換するステップを含む。コントローラ１２２は、プロセッサ・キャッシュまたはＩ／Ｏスタッシュであるバス動作タイプにより示すように、データのソースに割り当てられているキャッシュの一部内に新しいキャッシュ・ラインを格納するように、特に修正した擬似ＬＲＵアルゴリズムにより既存のどのキャッシュ・ラインを置換するのかを決定する。

以下に置換アルゴリズムについて説明する。図４は、図１のキャッシュ・コントローラ１２２内のキャッシュ置換ロジックが使用するキャッシュ置換アルゴリズム４００である。キャッシュ・ラインを割り当てる場合には、アクセス・アドレスのブロックおよびセット索引によりセットが最初に選択される。次に、ＰＬＲＵビット２０４が、適当なウェイを選択するために使用される。決定ツリーであるキャッシュ置換アルゴリズム４００の一般的な流れについて最初に説明する。ステップ４１０において、ビットＰ０が検査される。Ｐ０＝０である場合には、流れはステップ４２０に進む。ここでビットＰ１の状態が検査される。Ｐ１＝０である場合には、流れはステップ４３０に進み、ここでビットＰ３の状態が試験される。Ｐ３＝０である場合には、キャッシュ・コントローラ１２２は、ウェイ０を割り当てる。一方、Ｐ３＝１である場合には、キャッシュ・コントローラ１２２は、ウェイ１を割り当てる。Ｐ１＝１である場合には、流れはステップ４４０に進み、ここでビットＰ４の状態が試験される。Ｐ４＝０である場合には、キャッシュ・コントローラ１２２は、ウェイ２を割り当てる。一方、Ｐ４＝１である場合には、キャッシュ・コントローラ１２２は、ウェイ３を割り当てる。Ｐ０＝１である場合には、流れはステップ４５０に進み、ここでビットＰ２の状態が検査される。Ｐ２＝０である場合には、流れはステップ４６０に進み、ここでビットＰ５の状態が試験される。Ｐ５＝０である場合には、キャッシュ・コントローラ１２２は、ウェイ４を割り当てる。一方、Ｐ５＝１である場合には、キャッシュ・コントローラ１２２は、ウェイ５を割り当てる。Ｐ２＝１である場合には、流れはステップ４７０に進み、ここでビットＰ６の状態が試験される。Ｐ６＝０である場合には、キャッシュ・コントローラ１２２は、ウェイ６を割り当てる。一方、Ｐ６＝１である場合には、キャッシュ・コントローラ１２２は、ウェイ７を割り当てる。

次に、バス動作タイプを考慮に入れない従来の擬似ＬＲＵアルゴリズムについて説明する。ウェイ３は、ＬＲＵキャッシュ・ラインであると仮定する。ＰＬＲＵビット２０４は、値［０１１ｘｘｘｘ］を有する。ここで、「ｘ」は、「ドントケア」状態を表す。Ｐ０＝０であるので、流れはボックス４１０から左の方向のボックス４２０に進む。Ｐ１＝１であるので、流れは、次に右の方向のボックス４４０に進む。最後にＰ４＝１であるので、ウェイ３が割り当てられる。

本発明により修正した擬似ＬＲＵアルゴリズムについて以下に説明する。一般に、コントローラ１２２は、Ｌ２ ＣＡＣＨＥ ＣＯＮＴＲＯＬ ＲＥＧＩＳＴＥＲ２３０内に格納しているコンフィグレーション値により識別した不適格ラインを避けながら、決定ツリー内を移動するためにキャッシュ置換アルゴリズム４００を修正する。この場合も、ウェイ３はＬＲＵキャッシュ・ラインであるが、バス動作タイプはＩ／Ｏスタッシュ動作であると仮定する。Ｌ２ＳＴＡＳＨＣＴＬが、ウェイ６およびウェイ７に対応する２つのラインをＩ／Ｏスタッシュ動作に割り当てているので、判定ボックス４１０からの左方向への流れは、Ｐ０の状態が何であれ不適格遷移（ｉｎｅｌｉｇｉｂｌｅ ｔｒａｎｓｉｔｉｏｎ）であるので、流れは右方向の判定ボックス４５０に進む。同様に、判定ボックス４５０からの左方向への流れは、不適格遷移であるので、流れは右方向の判定ボックス４７０に進む。次に、Ｐ６の状態がウェイ６またはウェイ７内のキャッシュ・ラインを新しいキャッシュ・ラインで置換するのか否かを判定する。

この擬似ＬＲＵアルゴリズムを使用すれば、キャッシュ・ロッキング機構と容易に統合することができる。キャッシュ内のラインがロックされると、ＰＬＲＵビットの状態が何であれ、割当て解除することはできない。それ故、ロッキングをサポートするために、コントローラ１２２も、ロックしたラインに応じて不適格状態遷移を認識する。

上記詳細な説明では少なくとも１つの例示としての実施形態について説明してきたが、非常に多数の変形版が存在することを理解されたい。また、例示としての１つの実施形態または例示としての複数の実施形態は、単に例示としてのものに過ぎないものであり、これらの実施形態は本発明の範囲、適用性または構成を如何なる意味でも制限するものではないことを理解されたい。それどころか、上記詳細な説明は、当業者に例示としての１つの実施形態または例示としての複数の実施形態を実施するための便利な道しるべである。例えば、データ処理システム１００は、１つの集積回路（ＩＣ）として実施することもできるし、またはＬ２キャッシュ１２０のような種々の構成要素は、別々のＩＣまたはシステムとして実施することができる。コントローラ１２２は、Ｉ／Ｏスタッシュ・バス動作およびプロセッサ・バス動作の他にバス動作タイプの他の組合わせに基づいて各セットの一部を分離することができる。さらに、図の例のほかに多くの他のキャッシュ編成も使用することができる。添付の特許請求の範囲およびその法的等価物に記載する本発明の範囲から逸脱することなしに、要素の機能および配置構成を種々に変更することができることを理解されたい。

本発明によるデータ処理システムのブロック図。 その編成の理解に役に立つ図１のキャッシュの一部のブロック図。 図１のキャッシュ・コントローラ内のキャッシュ・アクセス・ロジックが使用するキャッシュ・アクセス・アルゴリズムのブロック図。 図１のキャッシュ・コントローラ内のキャッシュ置換ロジックが使用するキャッシュ置換アルゴリズムの流れ図。

Claims (20)

1. バス（１１６）と結合することができるキャッシュ（１２０）であって、
   複数のセット（２００，２１０，２２０）を有するアレイ（１２５）であって、各セットが複数のキャッシュ・ライン（２０２）を有し、各セット内の各キャッシュ・ラインがタグおよび複数のデータ語を含むアレイ（１２５）と、
   前記アレイ（１２５）と結合しているコントローラ（１２２）であって、コンフィグレーション値（２３２，２３４）により、各セットの前記複数のキャッシュ・ライン（２０２）の第１の部分（２０５）を第１のバス動作タイプと関連付け、各セットの前記複数のキャッシュ・ライン（２０２）の第２の部分を第２のバス動作タイプと関連付け、バス動作中、前記バス（１１６）を通るデータを、前記バス動作のタイプが前記第１のバス動作タイプである場合には、前記第１の部分（２０５）に選択的に格納するか、または前記バス動作のタイプが前記第２のバス動作タイプである場合には、前記第２の部分（２０６）に選択的に格納するコントローラ（１２２）と、
   を備えるキャッシュ。
2. 前記第１のバス動作タイプが、入出力スタッシュ・バス動作であり、前記第２のバス動作タイプが、プロセッサ・バス動作である請求項１に記載のキャッシュ（１２０）。
3. 前記コントローラ（１２２）が、前記コンフィグレーション値（２３２，２３４）により、スタティック・ランダム・アクセス・メモリとして使用する各セットの前記複数のキャッシュ・ライン（２０２）の第３の部分（２０７）とさらに関連付ける、請求項２に記載のキャッシュ（１２０）。
4. 前記コンフィグレーション値（２３２，２３４）を格納するためのコンフィグレーション・レジスタ（２３０）をさらに備える請求項３に記載のキャッシュ（１２０）。
5. 前記コンフィグレーション・レジスタ（２３０）が、前記第１の部分（２０５）のサイズを決定するための第１のフィールド（２３４）および前記第３の部分（２０７）のサイズを決定するための第２のフィールド（２３２）を含み、前記第２の部分（２０６）のサイズが、前記第１の部分（２０５）または前記第３の部分（２０７）に位置していない前記複数のキャッシュ・ライン（２０２）の残りである請求項４に記載のキャッシュ（１２０）。
6. 前記コントローラ（１２２）が、前記バス動作のタイプに対応する前記複数のキャッシュ・ラインの前記第１および第２の部分のうちの一方から置換のためのキャッシュ・ラインを選択するために、前記バス動作のアドレスに応じる置換ロジック（１２２，４００）を備える請求項１に記載のキャッシュ（１２０）。
7. 前記置換ロジック（１２２，４００）が、置換のための前記キャッシュ・ラインを選択するために、擬似最長時間未使用（ＬＲＵ）アルゴリズムをさらに実行する請求項６に記載のキャッシュ（１２０）。
8. 各セットが、複数の履歴ビット（２０４）を格納し、前記コントローラ（１２２）が、前記コンフィグレーション値（２３２，２３４）が識別した不適格ラインを避けながら、置換のためのキャッシュ・ラインを決定するために、前記複数の履歴ビット（２０４）上で動作する請求項７に記載のキャッシュ（１２０）。
9. データ処理システム（１００）であって、
   第１のバス（１１６）と、
   前記第１のバス（１１６）上でプロセッサ・バス動作を実行するために前記第１のバス（１１６）と結合している中央処理装置（ＣＰＵ）（１１０）と、
   前記第１のバス（１１６）上で入出力スタッシュ・バス動作を実行するための入出力コントローラ（１７０）と、
   前記第１のバス（１１６）と結合しているキャッシュ（１２０）であって、
   複数のセット（２００，２１０，２２０）を有するアレイ（１２５）であって、各セットが、複数のキャッシュ・ライン（２０２）を有し、各セット内の各キャッシュ・ラインが、タグおよび複数のデータ語を含むアレイ（１２５）と、
   前記アレイ（１２５）と結合しているコントローラ（１２２）であって、コンフィグレーション値（２３２，２３４）により、各セットの前記複数のキャッシュ・ライン（２０２）の第１の部分を入出力スタッシュ・バス動作と関連付け、各セットの前記複数のキャッシュ・ライン（２０２）の第２の部分（２０６）を前記プロセッサ・バス動作と関連付け、バス動作中、前記バス（１１６）を通るデータを、前記バス動作が入出力スタッシュ・バス動作である場合には、前記第１の部分（２０５）に選択的に格納するか、または前記バス動作が前記プロセッサ・バス動作である場合には、前記第２の部分（２０６）に選択的に格納するコントローラ（１２２）と
   を備えるキャッシュ（１２０）と
   を備えるデータ処理システム（１００）。
10. 前記第１のバス（１１６）、前記中央処理装置（１１０）、前記入出力コントローラ（１７０）、および前記キャッシュ（１２０）が、１つの集積回路上で結合している、請求項９に記載のデータ処理システム（１００）。
11. 前記入出力コントローラ（１７０）と結合している第２のバス（１４０）と、
    前記第１のバス（１１６）および前記第１のバス（１１６）に前記第２のバス（１４０）上で入出力スタッシュ・バス動作を提供する前記第２のバス（１４０）と結合しているコヒーレンシ・モジュール（１３０）とをさらに備える、請求項９に記載のデータ処理システム（１００）。
12. 前記入出力コントローラ（１７０）が、前記入出力スタッシュ・バス動作でない他のバス動作をさらに実行する請求項１１に記載のデータ処理システム（１００）。
13. 前記入出力コントローラ（１７０）が、データ通信ヘッダ・データのために前記入出力スタッシュ・バス動作を実行し、データ通信ペイロード・データのために前記入出力スタッシュ・バス動作でない前記他のバス動作を実行する請求項１２に記載のデータ処理システム（１００）。
14. 前記中央処理装置（１１０）が、レベル１（Ｌ１）キャッシュ（１１２）を含み、前記キャッシュ（１２０）が、レベル２（Ｌ２）キャッシュとして機能する、請求項９に記載のデータ処理システム（１００）。
15. 前記コントローラ（１２２）が、前記バス動作の前記タイプに対応する前記複数のキャッシュ・ラインの前記第１および第２の部分のうちの一方から置換のためのキャッシュ・ラインを選択するために、前記バス動作のアドレスに応じる置換ロジック（１２２，４００）を備える請求項９に記載のデータ処理システム（１００）。
16. 前記置換ロジック（４００）が、置換のための前記キャッシュ・ラインを選択するために、擬似最長時間未使用（ＬＲＵ）アルゴリズムをさらに実行する、請求項１５に記載のデータ処理システム（１００）。
17. 各セットが、複数の履歴ビット（２０４）を格納し、前記コントローラ（１２２）が、前記コンフィグレーション値（２３２，２３４）が識別した不適格ラインを避けながら、置換のためのキャッシュ・ラインを決定するために、前記複数の履歴ビット（２０４）上で動作する、請求項１６に記載のデータ処理システム（１００）。
18. キャッシュ（１２０）を編成するための方法であって、
    複数のセット（２００，２１０，２２０）に前記キャッシュ（１２０）のアレイ（１２５）を編成するステップであって、各セットが、複数のキャッシュ・ライン（２０２）を有し、各キャッシュ・ラインが、タグおよび複数のデータ語を含むステップと、
    コンフィグレーション値（２３２，２３４）を受信し、格納するステップと、
    前記コンフィグレーション値（２３２，２３４）により、各セットの前記複数のキャッシュ・ライン（２０２）の第１の部分（２０５）を第１のバス動作タイプと関連付け、各セットの前記複数のキャッシュ・ライン（２０２）の第２の部分（２０６）を第２のバス動作タイプと関連付けるステップと、
    バス動作中、バス（１１６）を通るデータを、前記バス動作が前記第１のバス動作タイプであった場合には、前記第１の部分（２０５）に選択的に格納するか、または前記バス動作が前記第２のバス動作タイプであった場合には、前記第２の部分（２０６）に選択的に格納するステップと、を含む方法。
19. 前記複数のキャッシュ・ライン（２０２）の前記第１の部分（２０５）を前記第１のバス動作タイプと関連付ける前記ステップが、前記複数のキャッシュ・ライン（２０２）の前記第１の部分（２０５）を入出力スタッシュ・バス動作と関連付けるステップを含み、前記複数のキャッシュ・ライン（２０２）の前記第２の部分（２０６）を前記第２のバス動作タイプと関連付ける前記ステップが、前記複数のキャッシュ・ライン（２０２）の前記第２の部分（２０６）をプロセッサ・バス動作タイプと関連付けるステップを含む、請求項１８に記載の方法。
20. 前記コンフィグレーション値（２３２，２３４）により、スタティック・ランダム・アクセス・メモリとして使用する各セットの前記複数のキャッシュ・ライン（２０２）の第３の部分を関連付けるステップをさらに含む、請求項１９に記載の方法。

Images