(57)【特許請求の範囲】
【請求項１】
読み出し要求で指定されたメモリ・アドレスを記憶し関連するライン・アドレスを持つ複数のラインを含む、前記読み出し要求を受け取るアドレス・キャッシュ（３１０）と、
該アドレス・キャッシュとメモリ・コントローラ（３９９）に接続されて、前記アドレス・キャッシュから受け取った、前記アドレス・キャッシュ（３１０）における読み出し要求のミスに対応する前記メモリ・アドレスのそれぞれを記憶し、該ミスされたメモリ・アドレスのそれぞれを前記メモリ・コントローラに送るアドレス・キュー（３２０）であって、前記メモリ・コントローラ（３９９）は、前記ミスされたメモリ・アドレスのそれぞれに対応するデータのメモリ（２２０）からの読み出しを行わせるものであるアドレス・キュー（３２０）と、
前記メモリ・コントローラ（３９９）に接続されて、該メモリ・コントローラから受け取った、前記ミスされたメモリ・アドレスのそれぞれに対応する前記データを記憶するデータ・キュー（３５０）と、
前記アドレス・キャッシュ（３１０）に接続されて、前記アドレス・キャッシュ（３１０）で受け取った前記読み出し要求のそれぞれに対応する、前記アドレス・キャッシュ（３１０）から受け取ったライン・アドレス及びヒット／ミス情報を記憶するプローブ結果キュー（３３０）と、
前記データ・キューと前記プローブ結果キューに接続されて、該データ・キューから受け取った、前記ミスされたメモリ・アドレスのそれぞれに対応する前記データを記憶するデータ・キャッシュ（３６０）と、
前記データ・キュー、前記プローブ結果キュー、及び前記データ・キャッシュに接続された手段（３７０）であって、前記プローブ結果キューのヘッド・エントリに記憶された前記ヒット／ミス情報がヒットを指示したときに前記データ・キャッシュからの出力を選択し、前記プローブ結果キューのヘッド・エントリに記憶された前記ヒット／ミス情報がミスを指示したときに、前記データ・キュー（３５０）からの出力を選択するものであり、ここで前記データは前記データ・キュー（３５０）から選択されたときに前記ヘッド・エントリの前記ライン・アドレスにおいて前記データ・キャッシュ（３６０）にも記憶されているものである、ノン  ブロッキング・パイプライン・キャッシュを与える手段（３７０）と、を備え、
出力を選択するための前記手段（３７０）によって選択された前記データは、ヒット又はミスのいずれの場合でも、前記データが前記アドレス・キャッシュ（３１０）において要求されたのと同じ順番であることを特徴とする、データをキャッシュして取り出す装置（３００）。
【請求項２】
前記アドレス・キャッシュ（３１０）は完全連想型の内容参照可能メモリであり、前記メモリ・アドレスはタグとして記憶される請求項１記載の装置。
【請求項３】
前記プローブ結果キュー（３３０）は、さらに、
複数のエントリを持ち、各エントリはＮ＋１ビット幅で、Ｎは固有のライン・アドレスを示し、１ビットはヒット／ミス情報を示す請求項１記載の装置。
【請求項４】
前記データ・キャッシュ（３６０）は、相互接続されたレジスタ・ファイルである請求項１に記載の装置。
【請求項５】
前記記憶されるデータは、テクセル・データである、請求項１に記載の装置。
【請求項６】
前記データを記憶する同期ダイナミック・アクセス・メモリ（２２０）を更に備える請求項１に記載の装置。
【請求項７】
前記ミスされたアドレスにあるデータは、ミスの順番で応答される、請求項１に記載の装置。
【請求項８】
前記複数のラインは、最後に書かれた順番で保持される、請求項１に記載の装置。
【請求項９】
関連したライン・アドレスを有する複数のラインを持つアドレス・キャッシュ（３１０）において受け取った、読み出し要求で指定されるメモリ・アドレスをアドレス・キャッシュ（３１０）に記憶する段階と、
アドレス・キュー（３２０）に、前記アドレス・キャッシュから受け取った、前記アドレス・キャッシュにおける読み出し要求のミスに対応する前記メモリ・アドレスのそれぞれをキューする段階と、
前記ミスされたメモリ・アドレスのそれぞれをメモリ・コントローラ（３９９）に送り、前記ミスされたメモリ・アドレスのそれぞれに対応するデータを前記メモリ・コントローラによってメモリ（２２０）から取り出す段階と、
データ・キュー（３５０）に、前記メモリ・コントローラ（３９９）によって取り出された前記ミスされたメモリ・アドレスのそれぞれに対応する前記データをキューする段階と、
プローブ結果キュー（３３０）に、前記アドレス・キャッシュ（３１０）から受け取った、前記読み出し要求のそれぞれに対応する前記ライン・アドレス及びヒット／ミス情報をキューする段階と、
データ・キャッシュ（３６０）に、前記データ・キューから受け取った、前記ミスされたメモリ・アドレスのそれぞれに対応する前記データを記憶する段階と、
前記データ・キュー、前記プローブ結果キュー、及び前記データ・キャッシュに接続された手段（３７０）によって、前記プローブ結果キューのヘッド・エントリに記憶された前記ヒット／ミス情報がヒットを指示したときに、前記データ・キャッシュ（３６０）からの出力を選択し、前記プローブ結果キューのヘッド・エントリに記憶された前記ヒット／ミス情報がミスを指示したときに、前記データ・キューから出力を選択するものであり、ここで前記データは前記データ・キュー（３５０）から選択されたときに前記ヘッド・エントリの前記キャッシュ・ライン・アドレスにおいて前記データ・キャッシュ（３６０）にも記憶されているものである、ノン  ブロッキング・パイプライン・キャッシュを与える段階と、を含み、
選択された前記データは、ヒット又はミスのいずれの場合でも、前記データが前記アドレス・キャッシュ（３１０）において要求されたのと同じ順番であることを特徴とする、データをキャッシュして取り出す方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、コンピュータ・システム・メモリ、より詳細にはグラフィック・コンピュータ・システムに使われるキャッシュ・メモリに関する。
【０００２】
【従来の技術】
グラフィック・コンピュータ・システムでは、テクスチャ・マッピング（すなわち「テクスチャリング」）により、システムが生成する３次元（３Ｄ）イメージの現実性を高めることができる。テクスチャの例としては、木目、れんが、カーペット、ストーンウォール、草地などが挙げられる。テクスチャは、イメージ・オブジェクトの表面に、より現実的なレンダリングを与える。テクスチャリングは、コンピュータ・メモリ内にテクスチャ・マップとして記憶される一連のテクスチャ・エレメント（テクセル）を使って実行される。テクスチャ・マップは合成されるか、またはスキャンされたイメージから得られる。
低解像度のテクチャ・マップは、６４×６４テクセル含んでいるのに対し、高解像度のテクスチャ・マップは、４０９６×４０９６テクセル含んでいる。典型的な場合には、テクセルは、データのワードとして記憶され、各ワードのアドレスがテクスチャ・マップの特定の座標を表す。データは、色（ＲＢＧ）と、おそらく透過性情報も表す。
【０００３】
表面がテクスチャ化されたオブジェクトを含むグラフィック・イメージを表示するには、グラフィック・ソフトウェアとハードウェアがその表面を、表示可能な画素（ピクセル）に関連するスクリーン座標のアレーに変換する。ピクセル座標は、テクセル・マップの対応する該当のテクセルを探し出すのに使われる。対応するテクセルの色と透過性値は、ピクセルデータに併合され、表示されたピクセルの色と透過性の最終値を決定する。表面よりも内側のテクセル座標は、オブジェクトの頂点に与えられるテクセル座標を補間することにより得られる。
「ポイントサンプリング」と呼ばれる、低品質のテクスチャ・マッピングでは、イメージのピクセルそれぞれに対し、テクセルが１つだけ使われる。その結果、ポイントサンプリングでテクスチャ化されたイメージには、そのテクスチャ化された表面に、識別できる不連続的な形の見苦しいエイリアシングアーティファクトができる傾向がある。これは、テクスチャ化される表面が、ひどく歪められている場合（例えば距離をひき延ばしてある３Ｄイメージの表面）に特にそうである。
【０００４】
３線形のテクスチャ・マッピングなどの高品質のテクスチャリングでは、多重テクセル・マップ、例えば「Multem In Parvo 」（many in place)マップ、もしくは、Mipmaps が使われる。例えば、ある特定のテクスチャを表すのにMipmapが全部で１１ある場合、テクスチャの第１の高解像度Mipmapは、１０２４×１０２４テクセルであり、第２の高解像度Mipmapは、５１２×５１２テクセルである。
その次は、２５６×２５６テクセルで、１番の低解像度のMipmapまで下がると、１×１テクセルとなる。ズームを使用して、３次元感覚を与えるためにオブジェクトのサイズを増減する場合でさえも、これらの複数マップから、歪められた表面を持つテクスチャはスムーズに補間される。
高品質テクスチャ・マッピングでは、１つのピクセルに対し、８または１６のテクセルのマッピングを必要とすることがある。これは、各ピクセルに対して、システムは、８または１６のメモリ・アドレスのテクセル・データにアクセスしなければならないということを意味している。この場合、テクスチャリングは大量のメモリ・システム帯域幅を消費してしまうことが明白である。
【０００５】
テクスチャ・マッピングで必要とされるメモリ帯域幅を減らすことは望ましい。メモリ帯域幅を減らすことによって、テクスチャ専用のメモリ・チップの数を減らすことが可能となり、テクスチャを記憶するのに、より安価な汎用低速ダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）を使用することが可能となる。そして、イメージ生成の間は他のデータに使われるものと同じメモリ内にテクスチャを記憶することが可能となる。
従来技術でのテクスチャ・マッピング装置の中には、専用の高速スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）内にテクスチャ・マップを記憶するものもある。この方法では、連続するデータが同一のアドレスから読み出される場合でさえ、テクセル・データの読み出し要求ごとにＳＲＡＭにアクセスする。
テクスチャ・マッピング用に特別に設計されたＳＲＡＭは、高価で、グラフィック・ハードウェアに内蔵されており、限られた機能しか持たないことが多い。
現在のＤＲＡＭでは、センス・アンプはデータを「キャッシュ」するのに使用される。キャッシュを行うと、データの空間的、時間的局所性を有効に利用できる。例えば、一連のテクセル・アドレスが、すべて同じＤＲＡＭのページにある場合、データを、センス・アンプから直接アクセスすることができる。
【０００６】
ＤＲＡＭを使うと、同じメモリ・ページから取り出すためのメモリ帯域幅は、ＳＲＡＭのメモリ帯域幅に近づくことができる。しかし、現在のぺージのアドレスに「ミス」があると、他のページにアクセスする必要がある。ＤＲＡＭのページ間でスイッチすると、次のページのデータを取り出し、センス・アンプにラッチ（保持）する間、いくつかのプロセッサ・サイクルが必要である。これにより、アクセス待ち時間は増加する。このような待ち時間は、メモリ・システムの平均帯域幅がページ取り出しを処理するのに十分である場合は、アクセス・パス内で長いパイプラインを使用することにより、隠すことができる。
メモリ・システムに実際にキャッシュを追加すると、データに良好な空間的時間的局所性がある場合、必要な帯域幅を減少させることができる。しかし、グラフィック装置用のキャッシュ・メモリを実施することは困難である。キャッシュが従来通りのブロッキング・キャッシュとして構成されている場合、ミスは、次のアクセスを停止する。何故ならば、そのミスが、完全に処理されてからでないと、次のアクセス要求を受け入れることはできないからである。これは、取り出されたデータは、次の要求が処理される前にどこかにラッチされなければならないという事実によるものである。より多くのミスがある場合は、このアクセス停止のために、メモリ・システムが渡すテクセル取り出し用帯域幅は、パイプライン・ノンキャッシュ・メモリ・システムの場合よりも小さくなる。
【０００７】
ミス・サービスされたブックキーピング論理が含まれていると、このキャッシュは、ノンブロッキングになる。しかし、ノンブロッキング・キャッシュが、例えば読み出し要求から入手可能なデータまでのパイプライン内の段階と同じ数のミスをトラックできなければ、そのキャッシュは障害物となってなってしまう。
待ち時間とキャッシュ・サイズの問題は、メモリがテクセル・データ、ピクセル・データを記憶するだけでなく、他の情報も記憶する場合にはさらに難しくなる。メモリが汎用低価格ＤＲＡＭから要望通りに構成されている場合、様々に異なる種類のグラフィック情報を記憶できる。しかし、この場合、様々なバッファへのアクセス要求は、ページ“スラッシング”を避けるために、一括処理されなければならない。アクセスの一括処理によって、テクセル・データに対する要求が遅れ、待ち時間やトラックの必要があるミスの数が増加する。
【０００８】
ダイレクト・マップされたキャッシュは、使用可能と考えられる。しかし、その場合、キャッシュは、アドレスがキャッシュの全体に亘って適当に分布されるように非常に大きいものでなければならないだろう。キャッシュが数十ラインの場合、データの一部が性能を低下させるコンフリクトを頻繁に起こしている間、他のデータの一部は、かなりの時間使われないままキャッシュの無駄になることがある。キャッシュが大きくなると、コストも増大する。
ノン・ブロッキング完全連想型の内容参照可能メモリ（ＣＡＭ）は、データのフル・アドレスをタグとして使用するが、これはテクスチャ・マッピングに、より適していることがある。しかし、それでも、完全連想型キャッシュは適切なサイズであることが必要であり、ミスのある場合の待ち時間が、読み出し要求が出される時間と、データが使用可能になる時間との間に大きな遅れを引き起こすことがある。テクスチャ・マッピングの固有性のために、キャッシュがミスを起こす可能性が増大する。さらに悪いケースでは、各テクセルは正確に一度づつ使われ、その結果各アクセスでミスが起こることにもなり、このキャッシュには、全く利点がない。
【０００９】
【発明が解決しようとする課題】
したがって、従来のキャッシュの持つ欠点がなく、テクセル取り出しによって要求される帯域幅を減少できる、グラフィック・システム用のキャッシュを提供することが望まれている。
【００１０】
【課題を解決するための手段】
本発明は、広義においては、本特許請求の範囲の請求項１に限定されているような、データをキャッシュする装置と、請求項１０に限定されているような、データをキャッシュする方法にある。
以下にテクセル・データにアクセスするグラフィック・プロセッサで使用可能なノンブロッキング・パイプライン・キャッシュについて説明する。ノンブロッキング・パイプライン・キャッシュは、テクセルのアドレスとデータを、先入れ先出しキューにより相互に接続しているアドレスとデータのキャッシュに保存することが好ましい。アドレスとデータは以下に述べる通り、空間的、時間的に別個の方法で保存されると効果的である。
【００１１】
アドレス・キャッシュには、複数のラインがある。各ラインは、読み出し要求で指定されたメモリ・アドレスを記憶できる。各ラインに関連するのは、ライン・アドレスである。第１のキューには、アドレス・キャッシュに接続された入力と、メモリ・コントローラに接続された出力がある。第１のキューは、読み出し要求ミスによるミス・メモリ・アドレスを記憶する。ミス・メモリ・アドレスはメモリ・コントローラに送られる。メモリ・コントローラに接続された第２のキューは、ミス・メモリ・アドレスに保存されたデータを受け取る。
各読み出し要求のためのアドレス・キャッシュに接続された第３のキューは、ライン・アドレスとヒット／ミス情報を保存する。ヒット／ミス情報は、特定の要求されたアドレスがアドレス・キュー内に保存されているかどうかを示す。
【００１２】
データ・キャッシュは、第２と第３のキューの出力に接続されている。データ・キャッシュは、第２のキューから受け取ったミス・メモリ・アドレスにあるデータを保存する。マルチプレクサは、第３のキューに保存されたヒット／ミス情報により、出力へのデータをデータ・キャッシュまたは第２のキューから選択する。
【００１３】
【発明の実施の形態】
本発明についてのより詳細な理解は、以下の好ましい実施態様から、および添付の図を参照して得られる通りである。
図１について、本発明のノンブロッキング・パイプライン・キャッシュの好ましい実施態様について詳細を説明する。グラフィック表示システム１００は、メモリ・バス１１５によってメイン・メモリ１２０に接続されている汎用中央処理装置（ＣＰＵ）１１０を具備する。ＣＰＵ１１０は、汎用バス１２５（例えばＰＣＩバスなど）にも接続されている。バス１２５は、ディスク・サブシステム１３０、入力／出力（Ｉ／Ｏ）サブシステム１４０、グラフィックジェネレータ２００に接続されることができる。グラフィック・ジェネレータ２００は、ライン２７０によって、グラフィック・ディスプレイ装置１５０に接続されている。システム１００は、グラフィック・ワークステーションとして構成されることができる。
【００１４】
ＣＰＵ１１０は、１つ以上の汎用プロセッサチップ、例えば米国マサチューセッツ州メイナードの(Maynard, MA）ディジタル・エキュイプメント・コーポレーション(Digital Equipment Corporation）製のALPHA プロセッサを包含できる。
メインメモリ１２０は、システム１００の動作中に、マシン実行可能な命令とデータを記憶するためのものである。ディスク１３０は、ファイル内に命令とデータを永続的に記憶する。命令とデータは、入力／出力（Ｉ／Ｏ）サブシステム１４０を介して得られることができる。入力／出力（Ｉ／Ｏ）システムは、システム１００の動作を制御するキーボード、マウス、ジョイスティックなどの入力／出力（Ｉ／Ｏ）装置（図示していない）にも接続できる。バス１１５とバス１２５は、アドレス、データ、制御、タイミング信号を運ぶ。
【００１５】
システム１００の動作中に、ソフトウェア・プログラムの命令がＣＰＵ１１０によって実行される。プログラムは、ディスプレイ装置１５０上でグラフィック・イメージを生成するように設計されている。イメージ用のデータとイメージをレンダリングする方法についての命令は、バス１１５およびバス１２５を経由してグラフィック・ジェネレータ２００に送られる。ジェネレータ２００はデジタルデータを、ディスプレイ装置１５０が動かすことができるアナログ信号に変換する。より詳細には、グラフィックジェネレータ２００は、３次元イメージを高速でレンダリングする。
図２に示す通り、ジェネレータ２００は、図１のバス１２５に接続するためのバス・インタフェース205 を包含する。特定目的グラフィック・プロセッサ２１０は、ランダム・アクセス・メモリ／デジタル・ツー・アナログ・コンバータ（ＲＡＭＤＡＣ）２３０に接続される。ＲＡＭＤＡＣ２３０は、ライン２６０上のデジタル・グラフィック・データを受け取り、ライン２７０でアナログ・ビデオ信号を生成する。
【００１６】
さらにグラフィック・プロセッサ２１０は、同期ダイナミック・アクセス・メモリ（ＳＤＲＡＭ）２２０およびテクセル・キャッシュ３００にも接続されている。ＳＤＲＡＭ２２０は、マップとバッファ内にグラフィック・データを記憶する。バッファは、フロント、バック、色、Ｚ、ステンシル、オーバーレイ、フォーマット・バッファを含むことができる。マップは、テクスチャ・データ（テクセル）を記憶できる。エレメント２０５、２１０、３００は、シングル・セミコンダクター・チップ２０１上に配置されることが好ましい。
動作中に、ジェネレータ２００は図１に示すＣＰＵ１１０からグラフィック・データと命令を受け取る。データは、マップおよびバッファとしてＳＤＲＡＭ２２０内に記憶される。バッファとマップのデータは、グラフィック・プロセッサ２１０によって結合され、ライン２６０上にグラフィック・データを生成する。
アクセスされるテクセルが多数あるため、またシステムの性能を良くするために、テクセル・キャッシュ３００は、テクセル・データをキャッシュするために使われる。
【００１７】
一つの実施態様では、各テクセル・キャッシュ３００のために１つのメモリ・コントローラ３９９がある。例えば、８個のテクセル・キャッシュ３００が使われる場合、８個のメモリ・コントローラ３９９があることになる。従来のキャッシュと比較すると、各キャッシュのライン数は、例えば、２、３、４、８、１２などの小さい整数である。
小さいサイズのキャッシュ３００と、長いメモリ待ち時間に対処するためには、キャッシュ３００は、パイプラインを使って空間的かつ時間的にデータ及びそのアドレス・タグを分けるように構成される。これによって、キャッシュ300 はノンブロッキングであることが可能であり、キャッシュ300 内にラインがあるよりも、より多くの“ミスされた”要求を保持することができる。これは、性能を向上させるだけでなく、設計を単純化する。
【００１８】
図３は、より詳細なノンブロッキング・パイプライン・テクセル・キャッシュ３００を示す。キャッシュ３００は、アドレス・キャッシュ３１０を包含する。
アドレス・キャッシュ３１０は、アドレス・タグとして２２ビット使用する完全連想型の内容参照可能メモリ（ＣＡＭ）である。好ましい実施態様では、アドレス・キャッシュ３１０内のライン数は少なく、例えば８である。さらに、アドレス・キャッシュ３１０は、循環カウンター内に書き込まれた最新の情報も保持している。最後に書き込まれたラインは、ミスが起こる場合、次の“犠牲”となる。キャッシュ・ラインは関連するライン・アドレス（例えば０から７）を持つ。
アドレス・キャッシュ３１０は、アドレス・キュー３２０の入力エンド（テール）に結合されている。アドレス・キュー３２０は、２２ビット幅の先入れ先出し（ＦＩＦＯ）バッファである。アドレス・キュー３２０は、最後にミスされたアクセスのアドレス（タグ）を記憶する。
【００１９】
アドレス・キュー３２０の出力エンド（ヘッド）は、図２のメモリ・コントローラ３９９の一つの入力に結合されている。メモリコントローラ３９９からの出力は、データキュー３５０の入力エンド（テール）に接続されている。データ・キューは、３２ビット幅の先入れ先出し（ＦＩＦＯ）バッファである。
アドレス・キャッシュ３１０は、ライン３０２と３０３によってプローブ結果キュー３３０の入力エンドにも接続されている。プローブ結果キュー３０３は、Ｎ＋１ビット幅の先入れ先出し（ＦＩＦＯ）バッファであり、ライン３０３上のＮビットがアドレス・キャッシュ３１０の特定のラインを示すのに使われ、ライン３０２上の１ビットはヒット／ミス情報を示すのに使われる。
データ・キャッシュ３６０とマルチプレクサ（ＭＵＸ）３７０は両方共、プローブ結果キュー３３０のヘッドとデータ・キュー３５０のヘッドから入力を受け取る。データ・キャッシュ３６０は、ＳＲＡＭとして、相互接続されたレジスタ・ファイルとして、もしくはラッチのセットとして実施されうる。ＭＵＸ３７０は、３２ビット幅でライン３０９上に複数の入力と１つの出力を持つ。ＭＵＸの出力はライン３０２と３０３を経由してプローブ結果キュー３３０に与えられ、最終的にライン３０４上に出される情報によって選択される。すなわち、選択にはライン３０２と３０３上の信号によって時間的遅れが発生する。この遅れは、その情報がプローブ結果キュー３３０のヘッドに達する時間である。これは、選択が、プローブ結果キューのヘッド・エントリにある情報にじかに基づいてなされるということを意味している。
【００２０】
動作中に、キャッシュ３００はライン３０１上の読み出しアクセス要求に結びついている「プローブ」アドレスを受け取る。このプローブ・アドレスは、アドレス・キャッシュ３１０のすべてのラインを同時にプローブするのに使われる。
ヒットするものがあると、ライン３０２上のヒット／ミス情報がロジカル「１」（高）にセットされる。ミスの場合、ライン３０２はロジカル「０」にセットされる。
ヒットした場合、ヒット・ライン・アドレス（Ｎビット）は、ライン３０３上で表される。ミスの場合は、犠牲となるライン・アドレスが表される。これは、あるＮ＋１ビット・エントリー（ライン・アドレス＋ヒット／ミス情報）がヒットかミスかとして、各キャッシュ・アクセスのためのプローブ結果キュー３３０のテールに置かれることを意味している。
【００２１】
ミスの場合、プローブ・アドレスはアドレス・キュー３２０に置かれる。アドレス・キュー３２０は、メモリ・コントローラ３９９を介して待ち時間の長いＳＤＲＡＭ２２０に対してなされた要求を処理する。コントローラ３９９からの応答は、ミスしたアドレスのデータである。このデータは、データ・キュー３５０に置かれる。
データ・キャッシュ３６０は、プローブ結果キュー３３０のエントリを使ってアクセスされる。プローブ結果キューのヘッドがヒットを示す場合、ライン３０４上のＮビットはデータ・キャッシュ３６０から要求されたテクセル・データを読み出すためにキャッシュ・ライン・アドレスとして使われる。ヒットの場合、ＭＵＸ３７０は選択されたデータ・キャッシュ・アドレスにあるデータ・キャッシュ３６０からのデータを、ライン３０９上の出力として選択するようにさせられる。
【００２２】
このプローブ・エントリがミスを示した場合、データ・キュー３５０の次の先入れ先出し（ＦＩＦＯ）バッファ・エントリがライン３０４上のプローブ・キュー・エントリのＮビットで指定されるキャッシュ・ライン・アドレスのデータ・キャッシュ３６０内に記憶される。この場合、ＭＵＸ３７０はデータ・キュー３５０からのデータを、ライン３０９上の出力として選択する。ヒットまたはミスのいずれかの場合、データは要求されたのと同一の順番でライン３０９上に与えられる。
選択には、他の方法も使用される。例えば、選択は、「透過性のある」ラッチによって実行される。このラッチは、サイクルの始めにデータ・キュー３３０からデータ・キャッシュ３６０にミスしたデータを「ロード」し、これによって、サイクル中にデータ・キューからのデータは、ラッチを通って「流れる」ことが可能となる。
【００２３】
アドレス・キャッシュ３１０にヒットがある場合、またはアドレス・キャッシュ３２０が一杯でない場合、新しい読み出し要求が受け付けられる。アドレス・キャッシュにミスがあり、かつ、アドレス・キュー３２０が一杯である場合、読み出し要求は、スペースがアドレスキュー３２０において使用しうるようになるまで停止されねばならない。データ・キャッシュ３６０にミスがある場合、またはデータ・キャッシュ３５０が空でない場合、応答データが利用しうる。データ・キャッシュ３６０にミスがあり、さらにデータ・キュー３５０が空の場合は、その応答はデータがデータ・キュー３５０内にて利用しうるようになるまで、停止されねばならない。
図４の「網掛けされた」２×２ピクセルの正方形Ｔ０からＴ１５は、１６のテクスチャ・マップ化されたピクセルがどのようにテクスチャMipmap上でマップ化され、テクセル取り出し要求を生成するかの例を示す。網掛けされた正方形はそれぞれ、その正方形が重なっている４つのテクセルの取り出しを要求する。
ラベルＡＯからＪ３のＡからＪは、異なる２２ビット・アドレスを示す。０、１、２、３の数は、異なるメモリ・コントローラ３９９、したがってテクセル・データがキャッシュされるべき異なるキャッシュを示す。
【００２４】
各キャッシュ３００に８ラインある場合、ヒットとミスの比率は良い。テクセルが適切な方法で取り出される場合、たとえ、ライン・キャッシュが２つであっても、性能は良い。
図５の表５００は、メモリ・コントローラ０のテクセル取り出し要求のための動的なヒットとミス情報５２０を示す。図５ではライン・キャッシュは８と想定して、縦列５１０がテクセル取り出し要求番号を、縦列５１５がプローブ要求アドレスを、縦列５２０がヒットまたはミス情報を、縦列５３０がキャッシュ・ライン・アドレスを示す。
テクセルをキャッシュするためのノンブロッキング・パイプライン・キャッシュの有用性について説明してきた。しかし、同じ設計は他のグラフィック・アプリケーションでも、より大きい行先となる四角形上に小さい元となる四角形をタイルすることにも使用されることができる。
【００２５】
以上は本発明の特有の実施態様を説明したものである。しかし、本発明の範囲内で様々な変更を加えることが可能であることは、当業者にとって明らかである。
【図面の簡単な説明】
【図１】本発明の好ましい実施態様による、ノンブロッキング・パイプライン・キャッシュを使うグラフィック表示システムのブロック図である。
【図２】図１のシステムのグラフィック・ジェネレータのブロック図である。
【図３】本発明の好ましい実施態様による、ノンブロッキング・パイプライン・キャッシュのブロック図である。
【図４】テクスチャ・マップからのテクセル取り出しの線図である。
【図５】８ライン・キャッシュに関連するヒット／ミス情報の表を示す図である。
【符号の説明】
１２０  メイン・メモリ
１１０  中央処理装置（ＣＰＵ）
１３０  ディスク
１４０  入力／出力（Ｉ／Ｏ）
１５０  ディスプレイ
２００  グラフィック・ジェネレータ
２０５  バス・インタフェース
２１０  グラフィック・プロセッサ
２２０  同期ダイナミック・アクセス・メモリ（ＳＤＲＡＭ）
２３０  ランダム・アクセス・メモリ／デジタル・ツー・アナログ・コンバータ（ＲＡＭＤＡＣ）
３００  テクセル・キャッシュ
２２１  メモリ・コントローラ
３０１  読み出し要求
３０２  ヒット／ミス
３０３  エントリ／アドレス
３０９  応答
３１０  アドレス・キャッシュ
３２０  アドレス・キュー
３３０  プローブ結果キュー
３５０  データ・キュー
３６０  データ・キャッシュ
３７０  マルチプレクサ（ＭＵＸ）
５１０  取り出されたテクセル番号
５１５  プローブ要求アドレス
５２０  ヒット／ミス
５３０  キャッシュ・ライン・アドレス
【図１】
0004545242.tif 000002
【図２】
0004545242.tif 000003
【図３】
0004545242.tif 000004
【図４】
0004545242.tif 000005
【図５】
0004545242.tif 000006