JPH11102435A - ノンブロッキング・パイプライン・キャッシュ - Google Patents
ノンブロッキング・パイプライン・キャッシュInfo
- Publication number
- JPH11102435A JPH11102435A JP10154408A JP15440898A JPH11102435A JP H11102435 A JPH11102435 A JP H11102435A JP 10154408 A JP10154408 A JP 10154408A JP 15440898 A JP15440898 A JP 15440898A JP H11102435 A JPH11102435 A JP H11102435A
- Authority
- JP
- Japan
- Prior art keywords
- address
- cache
- queue
- data
- memory
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
- G06F12/0844—Multiple simultaneous or quasi-simultaneous cache accessing
- G06F12/0855—Overlapped cache accessing, e.g. pipeline
- G06F12/0859—Overlapped cache accessing, e.g. pipeline with reload from main memory
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Memory System Of A Hierarchy Structure (AREA)
- Image Generation (AREA)
- Controls And Circuits For Display Device (AREA)
- Image Input (AREA)
- Image Processing (AREA)
Abstract
(57)【要約】
【課題】 従来のキャッシュの持つ欠点がなく、テクセ
ル取り出しによって要求される帯域幅を減少できる、グ
ラフィック・システム用のキャッシュを提供する。 【解決手段】 キャッシュは、メモリ・アドレスを記憶
するためのアドレス・キャッシュを包含する。アドレス
・キューは、アドレス・キャッシュに接続されて、アド
レス・キャッシュがプローブされる順番でミスされたア
ドレスを記憶する。メモリ・コントローラは、アドレス
・キューから、ミスされたアドレスを受け取る。データ
・キューは、メモリ・コントローラから、ミスされたア
ドレスに保存されたデータを受け取る。プローブ結果キ
ューは、データ・キャッシュ・ライン・アドレスとヒッ
ト／ミス情報を記憶するアドレス・キャッシュに接続さ
れている。データ・キャッシュ、データ・キュー、プロ
ーブ結果キューに接続されているマルチプレクサは、ヒ
ット／ミス情報によってデータ・キャッシュまたはデー
タ・キューから出力データを選択する。
ル取り出しによって要求される帯域幅を減少できる、グ
ラフィック・システム用のキャッシュを提供する。 【解決手段】 キャッシュは、メモリ・アドレスを記憶
するためのアドレス・キャッシュを包含する。アドレス
・キューは、アドレス・キャッシュに接続されて、アド
レス・キャッシュがプローブされる順番でミスされたア
ドレスを記憶する。メモリ・コントローラは、アドレス
・キューから、ミスされたアドレスを受け取る。データ
・キューは、メモリ・コントローラから、ミスされたア
ドレスに保存されたデータを受け取る。プローブ結果キ
ューは、データ・キャッシュ・ライン・アドレスとヒッ
ト／ミス情報を記憶するアドレス・キャッシュに接続さ
れている。データ・キャッシュ、データ・キュー、プロ
ーブ結果キューに接続されているマルチプレクサは、ヒ
ット／ミス情報によってデータ・キャッシュまたはデー
タ・キューから出力データを選択する。
Description
【０００１】
【産業上の利用分野】本発明は、コンピュータ・システ
ム・メモリ、より詳細にはグラフィック・コンピュータ
・システムに使われるキャッシュ・メモリに関する。
ム・メモリ、より詳細にはグラフィック・コンピュータ
・システムに使われるキャッシュ・メモリに関する。
【０００２】
【従来の技術】グラフィック・コンピュータ・システム
では、テクスチャ・マッピング（すなわち「テクスチャ
リング」）により、システムが生成する３次元（３Ｄ）
イメージの現実性を高めることができる。テクスチャの
例としては、木目、れんが、カーペット、ストーンウォ
ール、草地などが挙げられる。テクスチャは、イメージ
・オブジェクトの表面に、より現実的なレンダリングを
与える。テクスチャリングは、コンピュータ・メモリ内
にテクスチャ・マップとして記憶される一連のテクスチ
ャ・エレメント（テクセル）を使って実行される。テク
スチャ・マップは合成されるか、またはスキャンされた
イメージから得られる。低解像度のテクチャ・マップ
は、６４×６４テクセル含んでいるのに対し、高解像度
のテクスチャ・マップは、４０９６×４０９６テクセル
含んでいる。典型的な場合には、テクセルは、データの
ワードとして記憶され、各ワードのアドレスがテクスチ
ャ・マップの特定の座標を表す。データは、色（ＲＢ
Ｇ）と、おそらく透過性情報も表す。
では、テクスチャ・マッピング（すなわち「テクスチャ
リング」）により、システムが生成する３次元（３Ｄ）
イメージの現実性を高めることができる。テクスチャの
例としては、木目、れんが、カーペット、ストーンウォ
ール、草地などが挙げられる。テクスチャは、イメージ
・オブジェクトの表面に、より現実的なレンダリングを
与える。テクスチャリングは、コンピュータ・メモリ内
にテクスチャ・マップとして記憶される一連のテクスチ
ャ・エレメント（テクセル）を使って実行される。テク
スチャ・マップは合成されるか、またはスキャンされた
イメージから得られる。低解像度のテクチャ・マップ
は、６４×６４テクセル含んでいるのに対し、高解像度
のテクスチャ・マップは、４０９６×４０９６テクセル
含んでいる。典型的な場合には、テクセルは、データの
ワードとして記憶され、各ワードのアドレスがテクスチ
ャ・マップの特定の座標を表す。データは、色（ＲＢ
Ｇ）と、おそらく透過性情報も表す。
【０００３】表面がテクスチャ化されたオブジェクトを
含むグラフィック・イメージを表示するには、グラフィ
ック・ソフトウェアとハードウェアがその表面を、表示
可能な画素（ピクセル）に関連するスクリーン座標のア
レーに変換する。ピクセル座標は、テクセル・マップの
対応する該当のテクセルを探し出すのに使われる。対応
するテクセルの色と透過性値は、ピクセルデータに併合
され、表示されたピクセルの色と透過性の最終値を決定
する。表面よりも内側のテクセル座標は、オブジェクト
の頂点に与えられるテクセル座標を補間することにより
得られる。「ポイントサンプリング」と呼ばれる、低品
質のテクスチャ・マッピングでは、イメージのピクセル
それぞれに対し、テクセルが１つだけ使われる。その結
果、ポイントサンプリングでテクスチャ化されたイメー
ジには、そのテクスチャ化された表面に、識別できる不
連続的な形の見苦しいエイリアシングアーティファクト
ができる傾向がある。これは、テクスチャ化される表面
が、ひどく歪められている場合（例えば距離をひき延ば
してある３Ｄイメージの表面）に特にそうである。
含むグラフィック・イメージを表示するには、グラフィ
ック・ソフトウェアとハードウェアがその表面を、表示
可能な画素（ピクセル）に関連するスクリーン座標のア
レーに変換する。ピクセル座標は、テクセル・マップの
対応する該当のテクセルを探し出すのに使われる。対応
するテクセルの色と透過性値は、ピクセルデータに併合
され、表示されたピクセルの色と透過性の最終値を決定
する。表面よりも内側のテクセル座標は、オブジェクト
の頂点に与えられるテクセル座標を補間することにより
得られる。「ポイントサンプリング」と呼ばれる、低品
質のテクスチャ・マッピングでは、イメージのピクセル
それぞれに対し、テクセルが１つだけ使われる。その結
果、ポイントサンプリングでテクスチャ化されたイメー
ジには、そのテクスチャ化された表面に、識別できる不
連続的な形の見苦しいエイリアシングアーティファクト
ができる傾向がある。これは、テクスチャ化される表面
が、ひどく歪められている場合（例えば距離をひき延ば
してある３Ｄイメージの表面）に特にそうである。
【０００４】３線形のテクスチャ・マッピングなどの高
品質のテクスチャリングでは、多重テクセル・マップ、
例えば「Multem In Parvo 」（many in place)マップ、
もしくは、Mipmaps が使われる。例えば、ある特定のテ
クスチャを表すのにMipmapが全部で１１ある場合、テク
スチャの第１の高解像度Mipmapは、１０２４×１０２４
テクセルであり、第２の高解像度Mipmapは、５１２×５
１２テクセルである。その次は、２５６×２５６テクセ
ルで、１番の低解像度のMipmapまで下がると、１×１テ
クセルとなる。ズームを使用して、３次元感覚を与える
ためにオブジェクトのサイズを増減する場合でさえも、
これらの複数マップから、歪められた表面を持つテクス
チャはスムーズに補間される。高品質テクスチャ・マッ
ピングでは、１つのピクセルに対し、８または１６のテ
クセルのマッピングを必要とすることがある。これは、
各ピクセルに対して、システムは、８または１６のメモ
リ・アドレスのテクセル・データにアクセスしなければ
ならないということを意味している。この場合、テクス
チャリングは大量のメモリ・システム帯域幅を消費して
しまうことが明白である。
品質のテクスチャリングでは、多重テクセル・マップ、
例えば「Multem In Parvo 」（many in place)マップ、
もしくは、Mipmaps が使われる。例えば、ある特定のテ
クスチャを表すのにMipmapが全部で１１ある場合、テク
スチャの第１の高解像度Mipmapは、１０２４×１０２４
テクセルであり、第２の高解像度Mipmapは、５１２×５
１２テクセルである。その次は、２５６×２５６テクセ
ルで、１番の低解像度のMipmapまで下がると、１×１テ
クセルとなる。ズームを使用して、３次元感覚を与える
ためにオブジェクトのサイズを増減する場合でさえも、
これらの複数マップから、歪められた表面を持つテクス
チャはスムーズに補間される。高品質テクスチャ・マッ
ピングでは、１つのピクセルに対し、８または１６のテ
クセルのマッピングを必要とすることがある。これは、
各ピクセルに対して、システムは、８または１６のメモ
リ・アドレスのテクセル・データにアクセスしなければ
ならないということを意味している。この場合、テクス
チャリングは大量のメモリ・システム帯域幅を消費して
しまうことが明白である。
【０００５】テクスチャ・マッピングで必要とされるメ
モリ帯域幅を減らすことは望ましい。メモリ帯域幅を減
らすことによって、テクスチャ専用のメモリ・チップの
数を減らすことが可能となり、テクスチャを記憶するの
に、より安価な汎用低速ダイナミック・ランダム・アク
セス・メモリ（ＤＲＡＭ）を使用することが可能とな
る。そして、イメージ生成の間は他のデータに使われる
ものと同じメモリ内にテクスチャを記憶することが可能
となる。従来技術でのテクスチャ・マッピング装置の中
には、専用の高速スタティック・ランダム・アクセス・
メモリ（ＳＲＡＭ）内にテクスチャ・マップを記憶する
ものもある。この方法では、連続するデータが同一のア
ドレスから読み出される場合でさえ、テクセル・データ
の読み出し要求ごとにＳＲＡＭにアクセスする。テクス
チャ・マッピング用に特別に設計されたＳＲＡＭは、高
価で、グラフィック・ハードウェアに内蔵されており、
限られた機能しか持たないことが多い。現在のＤＲＡＭ
では、センス・アンプはデータを「キャッシュ」するの
に使用される。キャッシュを行うと、データの空間的、
時間的局所性を有効に利用できる。例えば、一連のテク
セル・アドレスが、すべて同じＤＲＡＭのページにある
場合、データを、センス・アンプから直接アクセスする
ことができる。
モリ帯域幅を減らすことは望ましい。メモリ帯域幅を減
らすことによって、テクスチャ専用のメモリ・チップの
数を減らすことが可能となり、テクスチャを記憶するの
に、より安価な汎用低速ダイナミック・ランダム・アク
セス・メモリ（ＤＲＡＭ）を使用することが可能とな
る。そして、イメージ生成の間は他のデータに使われる
ものと同じメモリ内にテクスチャを記憶することが可能
となる。従来技術でのテクスチャ・マッピング装置の中
には、専用の高速スタティック・ランダム・アクセス・
メモリ（ＳＲＡＭ）内にテクスチャ・マップを記憶する
ものもある。この方法では、連続するデータが同一のア
ドレスから読み出される場合でさえ、テクセル・データ
の読み出し要求ごとにＳＲＡＭにアクセスする。テクス
チャ・マッピング用に特別に設計されたＳＲＡＭは、高
価で、グラフィック・ハードウェアに内蔵されており、
限られた機能しか持たないことが多い。現在のＤＲＡＭ
では、センス・アンプはデータを「キャッシュ」するの
に使用される。キャッシュを行うと、データの空間的、
時間的局所性を有効に利用できる。例えば、一連のテク
セル・アドレスが、すべて同じＤＲＡＭのページにある
場合、データを、センス・アンプから直接アクセスする
ことができる。
【０００６】ＤＲＡＭを使うと、同じメモリ・ページか
ら取り出すためのメモリ帯域幅は、ＳＲＡＭのメモリ帯
域幅に近づくことができる。しかし、現在のぺージのア
ドレスに「ミス」があると、他のページにアクセスする
必要がある。ＤＲＡＭのページ間でスイッチすると、次
のページのデータを取り出し、センス・アンプにラッチ
（保持）する間、いくつかのプロセッサ・サイクルが必
要である。これにより、アクセス待ち時間は増加する。
このような待ち時間は、メモリ・システムの平均帯域幅
がページ取り出しを処理するのに十分である場合は、ア
クセス・パス内で長いパイプラインを使用することによ
り、隠すことができる。メモリ・システムに実際にキャ
ッシュを追加すると、データに良好な空間的時間的局所
性がある場合、必要な帯域幅を減少させることができ
る。しかし、グラフィック装置用のキャッシュ・メモリ
を実施することは困難である。キャッシュが従来通りの
ブロッキング・キャッシュとして構成されている場合、
ミスは、次のアクセスを停止する。何故ならば、そのミ
スが、完全に処理されてからでないと、次のアクセス要
求を受け入れることはできないからである。これは、取
り出されたデータは、次の要求が処理される前にどこか
にラッチされなければならないという事実によるもので
ある。より多くのミスがある場合は、このアクセス停止
のために、メモリ・システムが渡すテクセル取り出し用
帯域幅は、パイプライン・ノンキャッシュ・メモリ・シ
ステムの場合よりも小さくなる。
ら取り出すためのメモリ帯域幅は、ＳＲＡＭのメモリ帯
域幅に近づくことができる。しかし、現在のぺージのア
ドレスに「ミス」があると、他のページにアクセスする
必要がある。ＤＲＡＭのページ間でスイッチすると、次
のページのデータを取り出し、センス・アンプにラッチ
（保持）する間、いくつかのプロセッサ・サイクルが必
要である。これにより、アクセス待ち時間は増加する。
このような待ち時間は、メモリ・システムの平均帯域幅
がページ取り出しを処理するのに十分である場合は、ア
クセス・パス内で長いパイプラインを使用することによ
り、隠すことができる。メモリ・システムに実際にキャ
ッシュを追加すると、データに良好な空間的時間的局所
性がある場合、必要な帯域幅を減少させることができ
る。しかし、グラフィック装置用のキャッシュ・メモリ
を実施することは困難である。キャッシュが従来通りの
ブロッキング・キャッシュとして構成されている場合、
ミスは、次のアクセスを停止する。何故ならば、そのミ
スが、完全に処理されてからでないと、次のアクセス要
求を受け入れることはできないからである。これは、取
り出されたデータは、次の要求が処理される前にどこか
にラッチされなければならないという事実によるもので
ある。より多くのミスがある場合は、このアクセス停止
のために、メモリ・システムが渡すテクセル取り出し用
帯域幅は、パイプライン・ノンキャッシュ・メモリ・シ
ステムの場合よりも小さくなる。
【０００７】ミス・サービスされたブックキーピング論
理が含まれていると、このキャッシュは、ノンブロッキ
ングになる。しかし、ノンブロッキング・キャッシュ
が、例えば読み出し要求から入手可能なデータまでのパ
イプライン内の段階と同じ数のミスをトラックできなけ
れば、そのキャッシュは障害物となってなってしまう。
待ち時間とキャッシュ・サイズの問題は、メモリがテク
セル・データ、ピクセル・データを記憶するだけでな
く、他の情報も記憶する場合にはさらに難しくなる。メ
モリが汎用低価格ＤＲＡＭから要望通りに構成されてい
る場合、様々に異なる種類のグラフィック情報を記憶で
きる。しかし、この場合、様々なバッファへのアクセス
要求は、ページ“スラッシング”を避けるために、一括
処理されなければならない。アクセスの一括処理によっ
て、テクセル・データに対する要求が遅れ、待ち時間や
トラックの必要があるミスの数が増加する。
理が含まれていると、このキャッシュは、ノンブロッキ
ングになる。しかし、ノンブロッキング・キャッシュ
が、例えば読み出し要求から入手可能なデータまでのパ
イプライン内の段階と同じ数のミスをトラックできなけ
れば、そのキャッシュは障害物となってなってしまう。
待ち時間とキャッシュ・サイズの問題は、メモリがテク
セル・データ、ピクセル・データを記憶するだけでな
く、他の情報も記憶する場合にはさらに難しくなる。メ
モリが汎用低価格ＤＲＡＭから要望通りに構成されてい
る場合、様々に異なる種類のグラフィック情報を記憶で
きる。しかし、この場合、様々なバッファへのアクセス
要求は、ページ“スラッシング”を避けるために、一括
処理されなければならない。アクセスの一括処理によっ
て、テクセル・データに対する要求が遅れ、待ち時間や
トラックの必要があるミスの数が増加する。
【０００８】ダイレクト・マップされたキャッシュは、
使用可能と考えられる。しかし、その場合、キャッシュ
は、アドレスがキャッシュの全体に亘って適当に分布さ
れるように非常に大きいものでなければならないだろ
う。キャッシュが数十ラインの場合、データの一部が性
能を低下させるコンフリクトを頻繁に起こしている間、
他のデータの一部は、かなりの時間使われないままキャ
ッシュの無駄になることがある。キャッシュが大きくな
ると、コストも増大する。ノン・ブロッキング完全連想
型の内容参照可能メモリ（ＣＡＭ）は、データのフル・
アドレスをタグとして使用するが、これはテクスチャ・
マッピングに、より適していることがある。しかし、そ
れでも、完全連想型キャッシュは適切なサイズであるこ
とが必要であり、ミスのある場合の待ち時間が、読み出
し要求が出される時間と、データが使用可能になる時間
との間に大きな遅れを引き起こすことがある。テクスチ
ャ・マッピングの固有性のために、キャッシュがミスを
起こす可能性が増大する。さらに悪いケースでは、各テ
クセルは正確に一度づつ使われ、その結果各アクセスで
ミスが起こることにもなり、このキャッシュには、全く
利点がない。
使用可能と考えられる。しかし、その場合、キャッシュ
は、アドレスがキャッシュの全体に亘って適当に分布さ
れるように非常に大きいものでなければならないだろ
う。キャッシュが数十ラインの場合、データの一部が性
能を低下させるコンフリクトを頻繁に起こしている間、
他のデータの一部は、かなりの時間使われないままキャ
ッシュの無駄になることがある。キャッシュが大きくな
ると、コストも増大する。ノン・ブロッキング完全連想
型の内容参照可能メモリ（ＣＡＭ）は、データのフル・
アドレスをタグとして使用するが、これはテクスチャ・
マッピングに、より適していることがある。しかし、そ
れでも、完全連想型キャッシュは適切なサイズであるこ
とが必要であり、ミスのある場合の待ち時間が、読み出
し要求が出される時間と、データが使用可能になる時間
との間に大きな遅れを引き起こすことがある。テクスチ
ャ・マッピングの固有性のために、キャッシュがミスを
起こす可能性が増大する。さらに悪いケースでは、各テ
クセルは正確に一度づつ使われ、その結果各アクセスで
ミスが起こることにもなり、このキャッシュには、全く
利点がない。
【０００９】
【発明が解決しようとする課題】したがって、従来のキ
ャッシュの持つ欠点がなく、テクセル取り出しによって
要求される帯域幅を減少できる、グラフィック・システ
ム用のキャッシュを提供することが望まれている。
ャッシュの持つ欠点がなく、テクセル取り出しによって
要求される帯域幅を減少できる、グラフィック・システ
ム用のキャッシュを提供することが望まれている。
【００１０】
【課題を解決するための手段】本発明は、広義において
は、本特許請求の範囲の請求項１に限定されているよう
な、データをキャッシュする装置と、請求項１０に限定
されているような、データをキャッシュする方法にあ
る。以下にテクセル・データにアクセスするグラフィッ
ク・プロセッサで使用可能なノンブロッキング・パイプ
ライン・キャッシュについて説明する。ノンブロッキン
グ・パイプライン・キャッシュは、テクセルのアドレス
とデータを、先入れ先出しキューにより相互に接続して
いるアドレスとデータのキャッシュに保存することが好
ましい。アドレスとデータは以下に述べる通り、空間
的、時間的に別個の方法で保存されると効果的である。
は、本特許請求の範囲の請求項１に限定されているよう
な、データをキャッシュする装置と、請求項１０に限定
されているような、データをキャッシュする方法にあ
る。以下にテクセル・データにアクセスするグラフィッ
ク・プロセッサで使用可能なノンブロッキング・パイプ
ライン・キャッシュについて説明する。ノンブロッキン
グ・パイプライン・キャッシュは、テクセルのアドレス
とデータを、先入れ先出しキューにより相互に接続して
いるアドレスとデータのキャッシュに保存することが好
ましい。アドレスとデータは以下に述べる通り、空間
的、時間的に別個の方法で保存されると効果的である。
【００１１】アドレス・キャッシュには、複数のライン
がある。各ラインは、読み出し要求で指定されたメモリ
・アドレスを記憶できる。各ラインに関連するのは、ラ
イン・アドレスである。第１のキューには、アドレス・
キャッシュに接続された入力と、メモリ・コントローラ
に接続された出力がある。第１のキューは、読み出し要
求ミスによるミス・メモリ・アドレスを記憶する。ミス
・メモリ・アドレスはメモリ・コントローラに送られ
る。メモリ・コントローラに接続された第２のキュー
は、ミス・メモリ・アドレスに保存されたデータを受け
取る。各読み出し要求のためのアドレス・キャッシュに
接続された第３のキューは、ライン・アドレスとヒット
／ミス情報を保存する。ヒット／ミス情報は、特定の要
求されたアドレスがアドレス・キュー内に保存されてい
るかどうかを示す。
がある。各ラインは、読み出し要求で指定されたメモリ
・アドレスを記憶できる。各ラインに関連するのは、ラ
イン・アドレスである。第１のキューには、アドレス・
キャッシュに接続された入力と、メモリ・コントローラ
に接続された出力がある。第１のキューは、読み出し要
求ミスによるミス・メモリ・アドレスを記憶する。ミス
・メモリ・アドレスはメモリ・コントローラに送られ
る。メモリ・コントローラに接続された第２のキュー
は、ミス・メモリ・アドレスに保存されたデータを受け
取る。各読み出し要求のためのアドレス・キャッシュに
接続された第３のキューは、ライン・アドレスとヒット
／ミス情報を保存する。ヒット／ミス情報は、特定の要
求されたアドレスがアドレス・キュー内に保存されてい
るかどうかを示す。
【００１２】データ・キャッシュは、第２と第３のキュ
ーの出力に接続されている。データ・キャッシュは、第
２のキューから受け取ったミス・メモリ・アドレスにあ
るデータを保存する。マルチプレクサは、第３のキュー
に保存されたヒット／ミス情報により、出力へのデータ
をデータ・キャッシュまたは第２のキューから選択す
る。
ーの出力に接続されている。データ・キャッシュは、第
２のキューから受け取ったミス・メモリ・アドレスにあ
るデータを保存する。マルチプレクサは、第３のキュー
に保存されたヒット／ミス情報により、出力へのデータ
をデータ・キャッシュまたは第２のキューから選択す
る。
【００１３】
【発明の実施の形態】本発明についてのより詳細な理解
は、以下の好ましい実施態様から、および添付の図を参
照して得られる通りである。図１について、本発明のノ
ンブロッキング・パイプライン・キャッシュの好ましい
実施態様について詳細を説明する。グラフィック表示シ
ステム１００は、メモリ・バス１１５によってメイン・
メモリ１２０に接続されている汎用中央処理装置（ＣＰ
Ｕ）１１０を具備する。ＣＰＵ１１０は、汎用バス１２
５（例えばＰＣＩバスなど）にも接続されている。バス
１２５は、ディスク・サブシステム１３０、入力／出力
（Ｉ／Ｏ）サブシステム１４０、グラフィックジェネレ
ータ２００に接続されることができる。グラフィック・
ジェネレータ２００は、ライン２７０によって、グラフ
ィック・ディスプレイ装置１５０に接続されている。シ
ステム１００は、グラフィック・ワークステーションと
して構成されることができる。
は、以下の好ましい実施態様から、および添付の図を参
照して得られる通りである。図１について、本発明のノ
ンブロッキング・パイプライン・キャッシュの好ましい
実施態様について詳細を説明する。グラフィック表示シ
ステム１００は、メモリ・バス１１５によってメイン・
メモリ１２０に接続されている汎用中央処理装置（ＣＰ
Ｕ）１１０を具備する。ＣＰＵ１１０は、汎用バス１２
５（例えばＰＣＩバスなど）にも接続されている。バス
１２５は、ディスク・サブシステム１３０、入力／出力
（Ｉ／Ｏ）サブシステム１４０、グラフィックジェネレ
ータ２００に接続されることができる。グラフィック・
ジェネレータ２００は、ライン２７０によって、グラフ
ィック・ディスプレイ装置１５０に接続されている。シ
ステム１００は、グラフィック・ワークステーションと
して構成されることができる。
【００１４】ＣＰＵ１１０は、１つ以上の汎用プロセッ
サチップ、例えば米国マサチューセッツ州メイナードの
(Maynard, MA）ディジタル・エキュイプメント・コーポ
レーション(Digital Equipment Corporation）製のALPH
A プロセッサを包含できる。メインメモリ１２０は、シ
ステム１００の動作中に、マシン実行可能な命令とデー
タを記憶するためのものである。ディスク１３０は、フ
ァイル内に命令とデータを永続的に記憶する。命令とデ
ータは、入力／出力（Ｉ／Ｏ）サブシステム１４０を介
して得られることができる。入力／出力（Ｉ／Ｏ）シス
テムは、システム１００の動作を制御するキーボード、
マウス、ジョイスティックなどの入力／出力（Ｉ／Ｏ）
装置（図示していない）にも接続できる。バス１１５と
バス１２５は、アドレス、データ、制御、タイミング信
号を運ぶ。
サチップ、例えば米国マサチューセッツ州メイナードの
(Maynard, MA）ディジタル・エキュイプメント・コーポ
レーション(Digital Equipment Corporation）製のALPH
A プロセッサを包含できる。メインメモリ１２０は、シ
ステム１００の動作中に、マシン実行可能な命令とデー
タを記憶するためのものである。ディスク１３０は、フ
ァイル内に命令とデータを永続的に記憶する。命令とデ
ータは、入力／出力（Ｉ／Ｏ）サブシステム１４０を介
して得られることができる。入力／出力（Ｉ／Ｏ）シス
テムは、システム１００の動作を制御するキーボード、
マウス、ジョイスティックなどの入力／出力（Ｉ／Ｏ）
装置（図示していない）にも接続できる。バス１１５と
バス１２５は、アドレス、データ、制御、タイミング信
号を運ぶ。
【００１５】システム１００の動作中に、ソフトウェア
・プログラムの命令がＣＰＵ１１０によって実行され
る。プログラムは、ディスプレイ装置１５０上でグラフ
ィック・イメージを生成するように設計されている。イ
メージ用のデータとイメージをレンダリングする方法に
ついての命令は、バス１１５およびバス１２５を経由し
てグラフィック・ジェネレータ２００に送られる。ジェ
ネレータ２００はデジタルデータを、ディスプレイ装置
１５０が動かすことができるアナログ信号に変換する。
より詳細には、グラフィックジェネレータ２００は、３
次元イメージを高速でレンダリングする。図２に示す通
り、ジェネレータ２００は、図１のバス１２５に接続す
るためのバス・インタフェース205 を包含する。特定目
的グラフィック・プロセッサ２１０は、ランダム・アク
セス・メモリ／デジタル・ツー・アナログ・コンバータ
（ＲＡＭＤＡＣ）２３０に接続される。ＲＡＭＤＡＣ２
３０は、ライン２６０上のデジタル・グラフィック・デ
ータを受け取り、ライン２７０でアナログ・ビデオ信号
を生成する。
・プログラムの命令がＣＰＵ１１０によって実行され
る。プログラムは、ディスプレイ装置１５０上でグラフ
ィック・イメージを生成するように設計されている。イ
メージ用のデータとイメージをレンダリングする方法に
ついての命令は、バス１１５およびバス１２５を経由し
てグラフィック・ジェネレータ２００に送られる。ジェ
ネレータ２００はデジタルデータを、ディスプレイ装置
１５０が動かすことができるアナログ信号に変換する。
より詳細には、グラフィックジェネレータ２００は、３
次元イメージを高速でレンダリングする。図２に示す通
り、ジェネレータ２００は、図１のバス１２５に接続す
るためのバス・インタフェース205 を包含する。特定目
的グラフィック・プロセッサ２１０は、ランダム・アク
セス・メモリ／デジタル・ツー・アナログ・コンバータ
（ＲＡＭＤＡＣ）２３０に接続される。ＲＡＭＤＡＣ２
３０は、ライン２６０上のデジタル・グラフィック・デ
ータを受け取り、ライン２７０でアナログ・ビデオ信号
を生成する。
【００１６】さらにグラフィック・プロセッサ２１０
は、同期ダイナミック・アクセス・メモリ（ＳＤＲＡ
Ｍ）２２０およびテクセル・キャッシュ３００にも接続
されている。ＳＤＲＡＭ２２０は、マップとバッファ内
にグラフィック・データを記憶する。バッファは、フロ
ント、バック、色、Ｚ、ステンシル、オーバーレイ、フ
ォーマット・バッファを含むことができる。マップは、
テクスチャ・データ（テクセル）を記憶できる。エレメ
ント２０５、２１０、３００は、シングル・セミコンダ
クター・チップ２０１上に配置されることが好ましい。
動作中に、ジェネレータ２００は図１に示すＣＰＵ１１
０からグラフィック・データと命令を受け取る。データ
は、マップおよびバッファとしてＳＤＲＡＭ２２０内に
記憶される。バッファとマップのデータは、グラフィッ
ク・プロセッサ２１０によって結合され、ライン２６０
上にグラフィック・データを生成する。アクセスされる
テクセルが多数あるため、またシステムの性能を良くす
るために、テクセル・キャッシュ３００は、テクセル・
データをキャッシュするために使われる。
は、同期ダイナミック・アクセス・メモリ（ＳＤＲＡ
Ｍ）２２０およびテクセル・キャッシュ３００にも接続
されている。ＳＤＲＡＭ２２０は、マップとバッファ内
にグラフィック・データを記憶する。バッファは、フロ
ント、バック、色、Ｚ、ステンシル、オーバーレイ、フ
ォーマット・バッファを含むことができる。マップは、
テクスチャ・データ（テクセル）を記憶できる。エレメ
ント２０５、２１０、３００は、シングル・セミコンダ
クター・チップ２０１上に配置されることが好ましい。
動作中に、ジェネレータ２００は図１に示すＣＰＵ１１
０からグラフィック・データと命令を受け取る。データ
は、マップおよびバッファとしてＳＤＲＡＭ２２０内に
記憶される。バッファとマップのデータは、グラフィッ
ク・プロセッサ２１０によって結合され、ライン２６０
上にグラフィック・データを生成する。アクセスされる
テクセルが多数あるため、またシステムの性能を良くす
るために、テクセル・キャッシュ３００は、テクセル・
データをキャッシュするために使われる。
【００１７】一つの実施態様では、各テクセル・キャッ
シュ３００のために１つのメモリ・コントローラ３９９
がある。例えば、８個のテクセル・キャッシュ３００が
使われる場合、８個のメモリ・コントローラ３９９があ
ることになる。従来のキャッシュと比較すると、各キャ
ッシュのライン数は、例えば、２、３、４、８、１２な
どの小さい整数である。小さいサイズのキャッシュ３０
０と、長いメモリ待ち時間に対処するためには、キャッ
シュ３００は、パイプラインを使って空間的かつ時間的
にデータ及びそのアドレス・タグを分けるように構成さ
れる。これによって、キャッシュ300 はノンブロッキン
グであることが可能であり、キャッシュ300 内にライン
があるよりも、より多くの“ミスされた”要求を保持す
ることができる。これは、性能を向上させるだけでな
く、設計を単純化する。
シュ３００のために１つのメモリ・コントローラ３９９
がある。例えば、８個のテクセル・キャッシュ３００が
使われる場合、８個のメモリ・コントローラ３９９があ
ることになる。従来のキャッシュと比較すると、各キャ
ッシュのライン数は、例えば、２、３、４、８、１２な
どの小さい整数である。小さいサイズのキャッシュ３０
０と、長いメモリ待ち時間に対処するためには、キャッ
シュ３００は、パイプラインを使って空間的かつ時間的
にデータ及びそのアドレス・タグを分けるように構成さ
れる。これによって、キャッシュ300 はノンブロッキン
グであることが可能であり、キャッシュ300 内にライン
があるよりも、より多くの“ミスされた”要求を保持す
ることができる。これは、性能を向上させるだけでな
く、設計を単純化する。
【００１８】図３は、より詳細なノンブロッキング・パ
イプライン・テクセル・キャッシュ３００を示す。キャ
ッシュ３００は、アドレス・キャッシュ３１０を包含す
る。アドレス・キャッシュ３１０は、アドレス・タグと
して２２ビット使用する完全連想型の内容参照可能メモ
リ（ＣＡＭ）である。好ましい実施態様では、アドレス
・キャッシュ３１０内のライン数は少なく、例えば８で
ある。さらに、アドレス・キャッシュ３１０は、循環カ
ウンター内に書き込まれた最新の情報も保持している。
最後に書き込まれたラインは、ミスが起こる場合、次の
“犠牲”となる。キャッシュ・ラインは関連するライン
・アドレス（例えば０から７）を持つ。アドレス・キャ
ッシュ３１０は、アドレス・キュー３２０の入力エンド
（テール）に結合されている。アドレス・キュー３２０
は、２２ビット幅の先入れ先出し（ＦＩＦＯ）バッファ
である。アドレス・キュー３２０は、最後にミスされた
アクセスのアドレス（タグ）を記憶する。
イプライン・テクセル・キャッシュ３００を示す。キャ
ッシュ３００は、アドレス・キャッシュ３１０を包含す
る。アドレス・キャッシュ３１０は、アドレス・タグと
して２２ビット使用する完全連想型の内容参照可能メモ
リ（ＣＡＭ）である。好ましい実施態様では、アドレス
・キャッシュ３１０内のライン数は少なく、例えば８で
ある。さらに、アドレス・キャッシュ３１０は、循環カ
ウンター内に書き込まれた最新の情報も保持している。
最後に書き込まれたラインは、ミスが起こる場合、次の
“犠牲”となる。キャッシュ・ラインは関連するライン
・アドレス（例えば０から７）を持つ。アドレス・キャ
ッシュ３１０は、アドレス・キュー３２０の入力エンド
（テール）に結合されている。アドレス・キュー３２０
は、２２ビット幅の先入れ先出し（ＦＩＦＯ）バッファ
である。アドレス・キュー３２０は、最後にミスされた
アクセスのアドレス（タグ）を記憶する。
【００１９】アドレス・キュー３２０の出力エンド（ヘ
ッド）は、図２のメモリ・コントローラ３９９の一つの
入力に結合されている。メモリコントローラ３９９から
の出力は、データキュー３５０の入力エンド（テール）
に接続されている。データ・キューは、３２ビット幅の
先入れ先出し（ＦＩＦＯ）バッファである。アドレス・
キャッシュ３１０は、ライン３０２と３０３によってプ
ローブ結果キュー３３０の入力エンドにも接続されてい
る。プローブ結果キュー３０３は、Ｎ＋１ビット幅の先
入れ先出し（ＦＩＦＯ）バッファであり、ライン３０３
上のＮビットがアドレス・キャッシュ３１０の特定のラ
インを示すのに使われ、ライン３０２上の１ビットはヒ
ット／ミス情報を示すのに使われる。データ・キャッシ
ュ３６０とマルチプレクサ（ＭＵＸ）３７０は両方共、
プローブ結果キュー３３０のヘッドとデータ・キュー３
５０のヘッドから入力を受け取る。データ・キャッシュ
３６０は、ＳＲＡＭとして、相互接続されたレジスタ・
ファイルとして、もしくはラッチのセットとして実施さ
れうる。ＭＵＸ３７０は、３２ビット幅でライン３０９
上に複数の入力と１つの出力を持つ。ＭＵＸの出力はラ
イン３０２と３０３を経由してプローブ結果キュー３３
０に与えられ、最終的にライン３０４上に出される情報
によって選択される。すなわち、選択にはライン３０２
と３０３上の信号によって時間的遅れが発生する。この
遅れは、その情報がプローブ結果キュー３３０のヘッド
に達する時間である。これは、選択が、プローブ結果キ
ューのヘッド・エントリにある情報にじかに基づいてな
されるということを意味している。
ッド）は、図２のメモリ・コントローラ３９９の一つの
入力に結合されている。メモリコントローラ３９９から
の出力は、データキュー３５０の入力エンド（テール）
に接続されている。データ・キューは、３２ビット幅の
先入れ先出し（ＦＩＦＯ）バッファである。アドレス・
キャッシュ３１０は、ライン３０２と３０３によってプ
ローブ結果キュー３３０の入力エンドにも接続されてい
る。プローブ結果キュー３０３は、Ｎ＋１ビット幅の先
入れ先出し（ＦＩＦＯ）バッファであり、ライン３０３
上のＮビットがアドレス・キャッシュ３１０の特定のラ
インを示すのに使われ、ライン３０２上の１ビットはヒ
ット／ミス情報を示すのに使われる。データ・キャッシ
ュ３６０とマルチプレクサ（ＭＵＸ）３７０は両方共、
プローブ結果キュー３３０のヘッドとデータ・キュー３
５０のヘッドから入力を受け取る。データ・キャッシュ
３６０は、ＳＲＡＭとして、相互接続されたレジスタ・
ファイルとして、もしくはラッチのセットとして実施さ
れうる。ＭＵＸ３７０は、３２ビット幅でライン３０９
上に複数の入力と１つの出力を持つ。ＭＵＸの出力はラ
イン３０２と３０３を経由してプローブ結果キュー３３
０に与えられ、最終的にライン３０４上に出される情報
によって選択される。すなわち、選択にはライン３０２
と３０３上の信号によって時間的遅れが発生する。この
遅れは、その情報がプローブ結果キュー３３０のヘッド
に達する時間である。これは、選択が、プローブ結果キ
ューのヘッド・エントリにある情報にじかに基づいてな
されるということを意味している。
【００２０】動作中に、キャッシュ３００はライン３０
１上の読み出しアクセス要求に結びついている「プロー
ブ」アドレスを受け取る。このプローブ・アドレスは、
アドレス・キャッシュ３１０のすべてのラインを同時に
プローブするのに使われる。ヒットするものがあると、
ライン３０２上のヒット／ミス情報がロジカル「１」
（高）にセットされる。ミスの場合、ライン３０２はロ
ジカル「０」にセットされる。ヒットした場合、ヒット
・ライン・アドレス（Ｎビット）は、ライン３０３上で
表される。ミスの場合は、犠牲となるライン・アドレス
が表される。これは、あるＮ＋１ビット・エントリー
（ライン・アドレス＋ヒット／ミス情報）がヒットかミ
スかとして、各キャッシュ・アクセスのためのプローブ
結果キュー３３０のテールに置かれることを意味してい
る。
１上の読み出しアクセス要求に結びついている「プロー
ブ」アドレスを受け取る。このプローブ・アドレスは、
アドレス・キャッシュ３１０のすべてのラインを同時に
プローブするのに使われる。ヒットするものがあると、
ライン３０２上のヒット／ミス情報がロジカル「１」
（高）にセットされる。ミスの場合、ライン３０２はロ
ジカル「０」にセットされる。ヒットした場合、ヒット
・ライン・アドレス（Ｎビット）は、ライン３０３上で
表される。ミスの場合は、犠牲となるライン・アドレス
が表される。これは、あるＮ＋１ビット・エントリー
（ライン・アドレス＋ヒット／ミス情報）がヒットかミ
スかとして、各キャッシュ・アクセスのためのプローブ
結果キュー３３０のテールに置かれることを意味してい
る。
【００２１】ミスの場合、プローブ・アドレスはアドレ
ス・キュー３２０に置かれる。アドレス・キュー３２０
は、メモリ・コントローラ３９９を介して待ち時間の長
いＳＤＲＡＭ２２０に対してなされた要求を処理する。
コントローラ３９９からの応答は、ミスしたアドレスの
データである。このデータは、データ・キュー３５０に
置かれる。データ・キャッシュ３６０は、プローブ結果
キュー３３０のエントリを使ってアクセスされる。プロ
ーブ結果キューのヘッドがヒットを示す場合、ライン３
０４上のＮビットはデータ・キャッシュ３６０から要求
されたテクセル・データを読み出すためにキャッシュ・
ライン・アドレスとして使われる。ヒットの場合、ＭＵ
Ｘ３７０は選択されたデータ・キャッシュ・アドレスに
あるデータ・キャッシュ３６０からのデータを、ライン
３０９上の出力として選択するようにさせられる。
ス・キュー３２０に置かれる。アドレス・キュー３２０
は、メモリ・コントローラ３９９を介して待ち時間の長
いＳＤＲＡＭ２２０に対してなされた要求を処理する。
コントローラ３９９からの応答は、ミスしたアドレスの
データである。このデータは、データ・キュー３５０に
置かれる。データ・キャッシュ３６０は、プローブ結果
キュー３３０のエントリを使ってアクセスされる。プロ
ーブ結果キューのヘッドがヒットを示す場合、ライン３
０４上のＮビットはデータ・キャッシュ３６０から要求
されたテクセル・データを読み出すためにキャッシュ・
ライン・アドレスとして使われる。ヒットの場合、ＭＵ
Ｘ３７０は選択されたデータ・キャッシュ・アドレスに
あるデータ・キャッシュ３６０からのデータを、ライン
３０９上の出力として選択するようにさせられる。
【００２２】このプローブ・エントリがミスを示した場
合、データ・キュー３５０の次の先入れ先出し（ＦＩＦ
Ｏ）バッファ・エントリがライン３０４上のプローブ・
キュー・エントリのＮビットで指定されるキャッシュ・
ライン・アドレスのデータ・キャッシュ３６０内に記憶
される。この場合、ＭＵＸ３７０はデータ・キュー３５
０からのデータを、ライン３０９上の出力として選択す
る。ヒットまたはミスのいずれかの場合、データは要求
されたのと同一の順番でライン３０９上に与えられる。
選択には、他の方法も使用される。例えば、選択は、
「透過性のある」ラッチによって実行される。このラッ
チは、サイクルの始めにデータ・キュー３３０からデー
タ・キャッシュ３６０にミスしたデータを「ロード」
し、これによって、サイクル中にデータ・キューからの
データは、ラッチを通って「流れる」ことが可能とな
る。
合、データ・キュー３５０の次の先入れ先出し（ＦＩＦ
Ｏ）バッファ・エントリがライン３０４上のプローブ・
キュー・エントリのＮビットで指定されるキャッシュ・
ライン・アドレスのデータ・キャッシュ３６０内に記憶
される。この場合、ＭＵＸ３７０はデータ・キュー３５
０からのデータを、ライン３０９上の出力として選択す
る。ヒットまたはミスのいずれかの場合、データは要求
されたのと同一の順番でライン３０９上に与えられる。
選択には、他の方法も使用される。例えば、選択は、
「透過性のある」ラッチによって実行される。このラッ
チは、サイクルの始めにデータ・キュー３３０からデー
タ・キャッシュ３６０にミスしたデータを「ロード」
し、これによって、サイクル中にデータ・キューからの
データは、ラッチを通って「流れる」ことが可能とな
る。
【００２３】アドレス・キャッシュ３１０にヒットがあ
る場合、またはアドレス・キャッシュ３２０が一杯でな
い場合、新しい読み出し要求が受け付けられる。アドレ
ス・キャッシュにミスがあり、かつ、アドレス・キュー
３２０が一杯である場合、読み出し要求は、スペースが
アドレスキュー３２０において使用しうるようになるま
で停止されねばならない。データ・キャッシュ３６０に
ミスがある場合、またはデータ・キャッシュ３５０が空
でない場合、応答データが利用しうる。データ・キャッ
シュ３６０にミスがあり、さらにデータ・キュー３５０
が空の場合は、その応答はデータがデータ・キュー３５
０内にて利用しうるようになるまで、停止されねばなら
ない。図４の「網掛けされた」２×２ピクセルの正方形
Ｔ０からＴ１５は、１６のテクスチャ・マップ化された
ピクセルがどのようにテクスチャMipmap上でマップ化さ
れ、テクセル取り出し要求を生成するかの例を示す。網
掛けされた正方形はそれぞれ、その正方形が重なってい
る４つのテクセルの取り出しを要求する。ラベルＡＯか
らＪ３のＡからＪは、異なる２２ビット・アドレスを示
す。０、１、２、３の数は、異なるメモリ・コントロー
ラ３９９、したがってテクセル・データがキャッシュさ
れるべき異なるキャッシュを示す。
る場合、またはアドレス・キャッシュ３２０が一杯でな
い場合、新しい読み出し要求が受け付けられる。アドレ
ス・キャッシュにミスがあり、かつ、アドレス・キュー
３２０が一杯である場合、読み出し要求は、スペースが
アドレスキュー３２０において使用しうるようになるま
で停止されねばならない。データ・キャッシュ３６０に
ミスがある場合、またはデータ・キャッシュ３５０が空
でない場合、応答データが利用しうる。データ・キャッ
シュ３６０にミスがあり、さらにデータ・キュー３５０
が空の場合は、その応答はデータがデータ・キュー３５
０内にて利用しうるようになるまで、停止されねばなら
ない。図４の「網掛けされた」２×２ピクセルの正方形
Ｔ０からＴ１５は、１６のテクスチャ・マップ化された
ピクセルがどのようにテクスチャMipmap上でマップ化さ
れ、テクセル取り出し要求を生成するかの例を示す。網
掛けされた正方形はそれぞれ、その正方形が重なってい
る４つのテクセルの取り出しを要求する。ラベルＡＯか
らＪ３のＡからＪは、異なる２２ビット・アドレスを示
す。０、１、２、３の数は、異なるメモリ・コントロー
ラ３９９、したがってテクセル・データがキャッシュさ
れるべき異なるキャッシュを示す。
【００２４】各キャッシュ３００に８ラインある場合、
ヒットとミスの比率は良い。テクセルが適切な方法で取
り出される場合、たとえ、ライン・キャッシュが２つで
あっても、性能は良い。図５の表５００は、メモリ・コ
ントローラ０のテクセル取り出し要求のための動的なヒ
ットとミス情報５２０を示す。図５ではライン・キャッ
シュは８と想定して、縦列５１０がテクセル取り出し要
求番号を、縦列５１５がプローブ要求アドレスを、縦列
５２０がヒットまたはミス情報を、縦列５３０がキャッ
シュ・ライン・アドレスを示す。テクセルをキャッシュ
するためのノンブロッキング・パイプライン・キャッシ
ュの有用性について説明してきた。しかし、同じ設計は
他のグラフィック・アプリケーションでも、より大きい
行先となる四角形上に小さい元となる四角形をタイルす
ることにも使用されることができる。
ヒットとミスの比率は良い。テクセルが適切な方法で取
り出される場合、たとえ、ライン・キャッシュが２つで
あっても、性能は良い。図５の表５００は、メモリ・コ
ントローラ０のテクセル取り出し要求のための動的なヒ
ットとミス情報５２０を示す。図５ではライン・キャッ
シュは８と想定して、縦列５１０がテクセル取り出し要
求番号を、縦列５１５がプローブ要求アドレスを、縦列
５２０がヒットまたはミス情報を、縦列５３０がキャッ
シュ・ライン・アドレスを示す。テクセルをキャッシュ
するためのノンブロッキング・パイプライン・キャッシ
ュの有用性について説明してきた。しかし、同じ設計は
他のグラフィック・アプリケーションでも、より大きい
行先となる四角形上に小さい元となる四角形をタイルす
ることにも使用されることができる。
【００２５】以上は本発明の特有の実施態様を説明した
ものである。しかし、本発明の範囲内で様々な変更を加
えることが可能であることは、当業者にとって明らかで
ある。
ものである。しかし、本発明の範囲内で様々な変更を加
えることが可能であることは、当業者にとって明らかで
ある。
【図１】本発明の好ましい実施態様による、ノンブロッ
キング・パイプライン・キャッシュを使うグラフィック
表示システムのブロック図である。
キング・パイプライン・キャッシュを使うグラフィック
表示システムのブロック図である。
【図２】図１のシステムのグラフィック・ジェネレータ
のブロック図である。
のブロック図である。
【図３】本発明の好ましい実施態様による、ノンブロッ
キング・パイプライン・キャッシュのブロック図であ
る。
キング・パイプライン・キャッシュのブロック図であ
る。
【図４】テクスチャ・マップからのテクセル取り出しの
線図である。
線図である。
【図５】８ライン・キャッシュに関連するヒット／ミス
情報の表を示す図である。
情報の表を示す図である。
１２０ メイン・メモリ １１０ 中央処理装置（ＣＰＵ） １３０ ディスク １４０ 入力／出力（Ｉ／Ｏ） １５０ ディスプレイ ２００ グラフィック・ジェネレータ ２０５ バス・インタフェース ２１０ グラフィック・プロセッサ ２２０ 同期ダイナミック・アクセス・メモリ（ＳＤＲ
ＡＭ） ２３０ ランダム・アクセス・メモリ／デジタル・ツー
・アナログ・コンバータ（ＲＡＭＤＡＣ） ３００ テクセル・キャッシュ ２２１ メモリ・コントローラ ３０１ 読み出し要求 ３０２ ヒット／ミス ３０３ エントリ／アドレス ３０９ 応答 ３１０ アドレス・キャッシュ ３２０ アドレス・キュー ３３０ プローブ結果キュー ３５０ データ・キュー ３６０ データ・キャッシュ ３７０ マルチプレクサ（ＭＵＸ） ５１０ 取り出されたテクセル番号 ５１５ プローブ要求アドレス ５２０ ヒット／ミス ５３０ キャッシュ・ライン・アドレス
ＡＭ） ２３０ ランダム・アクセス・メモリ／デジタル・ツー
・アナログ・コンバータ（ＲＡＭＤＡＣ） ３００ テクセル・キャッシュ ２２１ メモリ・コントローラ ３０１ 読み出し要求 ３０２ ヒット／ミス ３０３ エントリ／アドレス ３０９ 応答 ３１０ アドレス・キャッシュ ３２０ アドレス・キュー ３３０ プローブ結果キュー ３５０ データ・キュー ３６０ データ・キャッシュ ３７０ マルチプレクサ（ＭＵＸ） ５１０ 取り出されたテクセル番号 ５１５ プローブ要求アドレス ５２０ ヒット／ミス ５３０ キャッシュ・ライン・アドレス
───────────────────────────────────────────────────── フロントページの続き (72)発明者 ケニス ダブリュー コーレル アメリカ合衆国 マサチューセッツ州 01523ランカスター ノース メイン ス トリート 2221 (72)発明者 バートン ダブリュー バーコウィッツ アメリカ合衆国 マサチューセッツ州 01701フレミンガム アンジェリカ ドラ イヴ 84 (72)発明者 クリストファー シー ジャーノス アメリカ合衆国 マサチューセッツ州 01564スターリング パイクス ヒル ロ ード 14
Claims (10)
- 【請求項１】 読み出し要求で指定されたメモリ・アド
レスを記憶し関連するライン・アドレスを持つ複数のラ
インを含むアドレス・キャッシュと、 該アドレス・キャッシュとメモリ・コントローラに接続
されて、読み出し要求のミスのためにミスされたメモリ
・アドレスを記憶し、該ミスされたメモリ・アドレスを
メモリ・コントローラに送る第１のキューと、 前記メモリ・コントローラに接続されて、該メモリ・コ
ントローラから受け取ったミス・メモリ・アドレスにあ
るデータを記憶する第２のキューと、 前記アドレス・キャッシュに接続されて、ライン・アド
レス情報を記憶する第３のキューと、 前記第２と第３のキューに接続されて、該第２のキュー
から受け取ったミス・メモリ・アドレスにあるデータを
記憶するデータ・キャッシュと、 前記第３のキューのヘッド・エントリに記憶されたライ
ン・アドレス情報によって前記データ・キャッシュまた
は前記第２のキューからの出力を選択して、ノン ブロ
ッキング・パイプライン・キャッシュを与える手段と、
を備えることを特徴とする、データをキャッシュする装
置。 - 【請求項２】 前記アドレス・キャッシュは完全連想型
の内容参照可能メモリであり、前記メモリ・アドレスは
タグとして記憶される請求項１記載の装置。 - 【請求項３】 前記第３のキューは、さらに、 複数のエントリを持ち、各エントリはＮ＋１ビット幅
で、Ｎは固有のライン・アドレスを示し、１ビットはヒ
ット／ミス情報を示す請求項１記載の装置。 - 【請求項４】 前記データ・キャッシュは、相互接続さ
れたレジスタ・ファイルである請求項１に記載の装置。 - 【請求項５】 前記記憶されるデータは、テクセル・デ
ータである、請求項１に記載の装置。 - 【請求項６】 前記データを記憶する同期ダイナミック
・アクセス・メモリを更に備える請求項１に記載の装
置。 - 【請求項７】 前記ミスされたアドレスにあるデータ
は、ミスの順番で応答される、請求項１に記載の装置。 - 【請求項８】 前記複数のラインは、最後に書かれた順
番で保持される、請求項１に記載の装置。 - 【請求項９】 前記第３のキューは、ヒット／ミス情報
を記憶する請求項１に記載の装置。 - 【請求項１０】 関連したライン・アドレスを有する複
数のラインを持つアドレス・キャッシュに読み出し要求
で指定されるメモリ・アドレスを記憶する段階と、 前記アドレス・キャッシュとメモリ・コントローラに接
続された第１のキューに、読み出し要求ミスのためにミ
スされたメモリ・アドレスをキューする段階と、 前記ミス・メモリ・アドレスを前記メモリ・コントロー
ラに送る段階と、 前記メモリ・コントローラに接続された第２のキュー
に、前記メモリ・コントローラから受け取った前記ミス
・メモリ・アドレスにあるデータをキューする段階と、 前記アドレスキャッシュに接続された第３のキューに、
前記ライン・アドレスをキューする段階と、 前記第２及び第３のキューに接続されたデータ・キャッ
シュに、前記第２のキューから受け取ったミス・メモリ
・アドレスにあるデータを記憶する段階と、 前記第３のキューのヘッド・エントリに記憶された情報
により、前記データ・キャッシュまたは前記第２のキュ
ーから出力を選択する段階と、を含むことを特徴とす
る、データをキャッシュする方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/870,152 US6085292A (en) | 1997-06-05 | 1997-06-05 | Apparatus and method for providing non-blocking pipelined cache |
| US08/870152 | 1997-06-05 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH11102435A true JPH11102435A (ja) | 1999-04-13 |
| JP4545242B2 JP4545242B2 (ja) | 2010-09-15 |
Family
ID=25354879
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP15440898A Expired - Fee Related JP4545242B2 (ja) | 1997-06-05 | 1998-06-03 | ノンブロッキング・パイプライン・キャッシュ |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US6085292A (ja) |
| EP (1) | EP0883065B1 (ja) |
| JP (1) | JP4545242B2 (ja) |
| CA (1) | CA2238586A1 (ja) |
| DE (1) | DE69812223T2 (ja) |
Families Citing this family (22)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7136068B1 (en) | 1998-04-07 | 2006-11-14 | Nvidia Corporation | Texture cache for a computer graphics accelerator |
| US6490652B1 (en) * | 1999-02-03 | 2002-12-03 | Ati Technologies Inc. | Method and apparatus for decoupled retrieval of cache miss data |
| US6919895B1 (en) | 1999-03-22 | 2005-07-19 | Nvidia Corporation | Texture caching arrangement for a computer graphics accelerator |
| US6266744B1 (en) | 1999-05-18 | 2001-07-24 | Advanced Micro Devices, Inc. | Store to load forwarding using a dependency link file |
| US6473837B1 (en) | 1999-05-18 | 2002-10-29 | Advanced Micro Devices, Inc. | Snoop resynchronization mechanism to preserve read ordering |
| US6473832B1 (en) * | 1999-05-18 | 2002-10-29 | Advanced Micro Devices, Inc. | Load/store unit having pre-cache and post-cache queues for low latency load memory operations |
| US6442673B1 (en) * | 1999-11-05 | 2002-08-27 | I.P. First L.L.C. | Update forwarding cache for address mode |
| US6593931B1 (en) * | 1999-12-01 | 2003-07-15 | Intel Corporation | Method and apparatus for improving system memory bandwidth utilization during graphics translational lookaside buffer cache miss fetch cycles |
| US6757793B1 (en) * | 2000-03-29 | 2004-06-29 | Advanced Micro Devices, Inc. | Reducing probe traffic in multiprocessor systems using a victim record table |
| US6629234B1 (en) | 2000-03-30 | 2003-09-30 | Ip. First, L.L.C. | Speculative generation at address generation stage of previous instruction result stored in forward cache for use by succeeding address dependent instruction |
| US6549985B1 (en) * | 2000-03-30 | 2003-04-15 | I P - First, Llc | Method and apparatus for resolving additional load misses and page table walks under orthogonal stalls in a single pipeline processor |
| US7107438B2 (en) * | 2003-02-04 | 2006-09-12 | Via Technologies, Inc. | Pipelined microprocessor, apparatus, and method for performing early correction of conditional branch instruction mispredictions |
| US7185182B2 (en) * | 2003-02-04 | 2007-02-27 | Via Technologies, Inc. | Pipelined microprocessor, apparatus, and method for generating early instruction results |
| US7100024B2 (en) | 2003-02-04 | 2006-08-29 | Via Technologies, Inc. | Pipelined microprocessor, apparatus, and method for generating early status flags |
| US6933945B2 (en) * | 2003-03-31 | 2005-08-23 | Sun Microsystems, Inc. | Design for a non-blocking cache for texture mapping |
| US20050216713A1 (en) * | 2004-03-25 | 2005-09-29 | International Business Machines Corporation | Instruction text controlled selectively stated branches for prediction via a branch target buffer |
| US20050270870A1 (en) * | 2004-06-02 | 2005-12-08 | Sangho Shin | Time slot interchange switch with cache |
| US7944876B2 (en) * | 2004-06-02 | 2011-05-17 | Integrated Device Technology, Inc | Time slot interchange switch with bit error rate testing |
| US20080218527A1 (en) * | 2007-03-09 | 2008-09-11 | Romanick Ian D | Method and Apparatus for Improving Hit Rates of a Cache Memory for Storing Texture Data During Graphics Rendering |
| US8966230B2 (en) * | 2009-09-30 | 2015-02-24 | Intel Corporation | Dynamic selection of execution stage |
| KR102061069B1 (ko) | 2013-02-28 | 2020-01-02 | 삼성전자주식회사 | 텍스쳐 맵핑 파이프라인을 위한 논블로킹 방식의 텍스쳐 캐쉬 메모리 시스템 및 논블로킹 방식의 텍스쳐 캐쉬 메모리의 동작 방법 |
| US11194617B2 (en) * | 2019-05-24 | 2021-12-07 | Texas Instruments Incorporated | Merging data for write allocate |
Citations (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0290265A (ja) * | 1988-07-25 | 1990-03-29 | Digital Equip Corp <Dec> | コンピューター処理装置用の積分キャッシュを有するパイプライン |
| JPH03217985A (ja) * | 1990-01-23 | 1991-09-25 | Hitachi Ltd | データ処理装置とこれを含む画像診断装置 |
| JPH04270431A (ja) * | 1990-03-27 | 1992-09-25 | Digital Equip Corp <Dec> | データ 処理装置のメモリ システム |
| JPH0612323A (ja) * | 1992-02-27 | 1994-01-21 | Hewlett Packard Co <Hp> | キャッシュメモリシステム |
| JPH06318177A (ja) * | 1992-04-29 | 1994-11-15 | Sun Microsyst Inc | キャッシュ・ミス・ペナルティを減少させる方法、装置及びコンピュータ・システム |
| JPH07234819A (ja) * | 1993-12-27 | 1995-09-05 | Matsushita Electric Ind Co Ltd | キャッシュメモリ |
| JPH08314802A (ja) * | 1995-05-05 | 1996-11-29 | Rockwell Internatl Corp | キャッシュシステム、キャッシュメモリアドレスユニット、およびキャッシュメモリを動作させる方法 |
| JPH08328952A (ja) * | 1995-06-06 | 1996-12-13 | Hewlett Packard Co <Hp> | データ割り当て方法 |
| JPH08339331A (ja) * | 1995-06-12 | 1996-12-24 | Alps Lsi Technol Kk | キャッシュメモリー |
Family Cites Families (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5544342A (en) * | 1993-06-30 | 1996-08-06 | International Business Machines Corporation | System and method for prefetching information in a processing system |
| US5555392A (en) * | 1993-10-01 | 1996-09-10 | Intel Corporation | Method and apparatus for a line based non-blocking data cache |
| US5555391A (en) * | 1993-12-23 | 1996-09-10 | Unisys Corporation | System and method for storing partial blocks of file data in a file cache system by merging partial updated blocks with file block to be written |
| US5826109A (en) * | 1994-01-04 | 1998-10-20 | Intel Corporation | Method and apparatus for performing multiple load operations to the same memory location in a computer system |
| US5526510A (en) * | 1994-02-28 | 1996-06-11 | Intel Corporation | Method and apparatus for implementing a single clock cycle line replacement in a data cache unit |
| US5671444A (en) * | 1994-02-28 | 1997-09-23 | Intel Corporaiton | Methods and apparatus for caching data in a non-blocking manner using a plurality of fill buffers |
| US5559987A (en) * | 1994-06-30 | 1996-09-24 | Digital Equipment Corporation | Method and apparatus for updating a duplicate tag status in a snoop bus protocol based computer system |
| US5790130A (en) * | 1995-06-08 | 1998-08-04 | Hewlett-Packard Company | Texel cache interrupt daemon for virtual memory management of texture maps |
| US5752069A (en) * | 1995-08-31 | 1998-05-12 | Advanced Micro Devices, Inc. | Superscalar microprocessor employing away prediction structure |
| US5829029A (en) * | 1996-12-18 | 1998-10-27 | Bull Hn Information Systems Inc. | Private cache miss and access management in a multiprocessor system with shared memory |
-
1997
- 1997-06-05 US US08/870,152 patent/US6085292A/en not_active Expired - Lifetime
-
1998
- 1998-05-13 DE DE69812223T patent/DE69812223T2/de not_active Expired - Lifetime
- 1998-05-13 EP EP98303741A patent/EP0883065B1/en not_active Expired - Lifetime
- 1998-05-25 CA CA002238586A patent/CA2238586A1/en not_active Abandoned
- 1998-06-03 JP JP15440898A patent/JP4545242B2/ja not_active Expired - Fee Related
Patent Citations (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0290265A (ja) * | 1988-07-25 | 1990-03-29 | Digital Equip Corp <Dec> | コンピューター処理装置用の積分キャッシュを有するパイプライン |
| JPH03217985A (ja) * | 1990-01-23 | 1991-09-25 | Hitachi Ltd | データ処理装置とこれを含む画像診断装置 |
| JPH04270431A (ja) * | 1990-03-27 | 1992-09-25 | Digital Equip Corp <Dec> | データ 処理装置のメモリ システム |
| JPH0612323A (ja) * | 1992-02-27 | 1994-01-21 | Hewlett Packard Co <Hp> | キャッシュメモリシステム |
| JPH06318177A (ja) * | 1992-04-29 | 1994-11-15 | Sun Microsyst Inc | キャッシュ・ミス・ペナルティを減少させる方法、装置及びコンピュータ・システム |
| JPH07234819A (ja) * | 1993-12-27 | 1995-09-05 | Matsushita Electric Ind Co Ltd | キャッシュメモリ |
| JPH08314802A (ja) * | 1995-05-05 | 1996-11-29 | Rockwell Internatl Corp | キャッシュシステム、キャッシュメモリアドレスユニット、およびキャッシュメモリを動作させる方法 |
| JPH08328952A (ja) * | 1995-06-06 | 1996-12-13 | Hewlett Packard Co <Hp> | データ割り当て方法 |
| JPH08339331A (ja) * | 1995-06-12 | 1996-12-24 | Alps Lsi Technol Kk | キャッシュメモリー |
Also Published As
| Publication number | Publication date |
|---|---|
| DE69812223D1 (de) | 2003-04-24 |
| CA2238586A1 (en) | 1998-12-05 |
| EP0883065A2 (en) | 1998-12-09 |
| JP4545242B2 (ja) | 2010-09-15 |
| US6085292A (en) | 2000-07-04 |
| DE69812223T2 (de) | 2004-01-22 |
| EP0883065B1 (en) | 2003-03-19 |
| EP0883065A3 (en) | 1999-01-20 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4545242B2 (ja) | ノンブロッキング・パイプライン・キャッシュ | |
| US6426753B1 (en) | Cache memory for high latency and out-of-order return of texture data | |
| US6104418A (en) | Method and system for improved memory interface during image rendering | |
| US6288730B1 (en) | Method and apparatus for generating texture | |
| US6011565A (en) | Non-stalled requesting texture cache | |
| US5831640A (en) | Enhanced texture map data fetching circuit and method | |
| US7050063B1 (en) | 3-D rendering texture caching scheme | |
| US6204863B1 (en) | Method for dynamic XY tiled texture caching | |
| US6812929B2 (en) | System and method for prefetching data from a frame buffer | |
| US5579473A (en) | Interface controller for frame buffer random access memory devices | |
| US8200917B2 (en) | Multi-media processor cache with cache line locking and unlocking | |
| US5999199A (en) | Non-sequential fetch and store of XY pixel data in a graphics processor | |
| JP2012530953A (ja) | 原画像をワープさせて表示する装置および方法 | |
| US6836272B2 (en) | Frame buffer addressing scheme | |
| US6795078B2 (en) | Parallel read with source-clear operation | |
| US6741256B2 (en) | Predictive optimizer for DRAM memory | |
| US6636227B1 (en) | Apparatus and method for grouping texture cache requests | |
| US6167498A (en) | Circuits systems and methods for managing data requests between memory subsystems operating in response to multiple address formats | |
| US6720969B2 (en) | Dirty tag bits for 3D-RAM SRAM | |
| US7069387B2 (en) | Optimized cache structure for multi-texturing | |
| US6933945B2 (en) | Design for a non-blocking cache for texture mapping | |
| US6778179B2 (en) | External dirty tag bits for 3D-RAM SRAM | |
| US7580042B2 (en) | Systems and methods for storing and fetching texture data using bank interleaving | |
| US7360020B2 (en) | Method for improving cache-miss performance | |
| US20050195200A1 (en) | Embedded system with 3D graphics core and local pixel buffer |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20050518 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20080620 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20080630 |
|
| A601 | Written request for extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A601 Effective date: 20080930 |
|
| A711 | Notification of change in applicant |
Free format text: JAPANESE INTERMEDIATE CODE: A712 Effective date: 20080930 |
|
| A602 | Written permission of extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A602 Effective date: 20081003 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20090608 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20091008 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20091124 |
|
| A911 | Transfer of reconsideration by examiner before appeal (zenchi) |
Free format text: JAPANESE INTERMEDIATE CODE: A911 Effective date: 20091130 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20100225 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20100525 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20100617 |
|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20100630 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130709 Year of fee payment: 3 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| LAPS | Cancellation because of no payment of annual fees |