(57)【特許請求の範囲】
【請求項１】
グラフィック要素のテクスチャマッピング動作に使用されるテクスチャマップデータを含むメモリユニットを有するコンピュータ制御されたグラフィック表示システムにおける、テクスチャマップデータを検索するための回路であって、
該メモリユニットの該テクスチャマップデータの最近アクセスされたテクスチャマップデータを含むキャッシュメモリと、
受け取られたテクスチャマップアドレスが、該キャッシュメモリの内容に対してヒットアドレスであるかまたはミスアドレスであるかを決定するキャッシュルックアップ回路と、
該キャッシュルックアップ回路に結合され、複数の受け取られたテクスチャマップアドレスを格納するＦＩＦＯメモリと、
該メモリユニット、該キャッシュルックアップ回路、該ＦＩＦＯメモリ、および該キャッシュメモリに結合されたキャッシュコントローラ回路であって、
（１）該キャッシュルックアップ回路が第１の該テクスチャマップのミスアドレスを決定してから、該第１のテクスチャマップデータが該キャッシュメモリに格納されるまでの期間中に、該ＦＩＦＯメモリの第１のロケーション内に格納されるテクスチャマップミスアドレスに対応する該第１のテクスチャマップデータを、該キャッシュメモリに格納するために該メモリユニットからフェッチし、
（２）該キャッシュルックアップ回路が該第１のテクスチャマップのミスアドレスを決定してから、該第１のテクスチャマップデータが該キャッシュメモリに格納されるまでの期間中に、該ＦＩＦＯメモリの第２のロケーションに格納されるテクスチャマップヒットアドレスに対応し、該キャッシュメモリ内に格納されている第２の該テクスチャマップデータを提供する、キャッシュコントローラ回路と、
を有する回路。
【請求項２】
前記ＦＩＦＯメモリの前記第１のロケーションにデータが格納される時間が、前記第２のロケーションにデータが格納される時間よりも後である、請求項１に記載の回路。
【請求項３】
前記キャッシュメモリが１キロバイトのサイズである、請求項１に記載の回路。
【請求項４】
レンダリングのためのグラフィック要素にそれぞれ対応する前記受け取られたテクスチャマップアドレスを生成するための、前記キャッシュルックアップ回路に結合したアドレス生成回路をさらに含む、請求項１に記載の回路。
【請求項５】
前記ＦＩＦＯメモリがまた規定の期間にテクスチャマップヒットアドレスを受け取り格納するためのものであり、前記キャッシュコントローラ回路が、前記メモリユニットから前記第１のテクスチャマップデータをフェッチし、前記キャッシュメモリに格納する、請求項１に記載の回路。
【請求項６】
前記キャッシュコントローラ回路から供給されるテクスチャマップデータを処理するための、前記キャッシュコントローラ回路に結合されたテクスチャフィルタ回路をさらに含む、請求項１に記載の回路。
【請求項７】
命令を実行し、データを処理するためのホストプロセッサと、該ホストプロセッサに結合されたバスと、グラフィック画像を表示するための表示スクリーンと、テクスチャマップデータを検索するための回路とを有するコンピュータ制御されたグラフィック表示システムであって、該回路が、
グラフィック要素のテクスチャマッピング動作に使用されるテクスチャマップデータを含むメモリユニットと、
該メモリユニットの該テクスチャマップデータの最近アクセスされたテクスチャマップデータを含むテクスチャマップキャッシュメモリと、
受け取られたテクスチャマップアドレスが、該キャッシュメモリの内容に対してヒットアドレスであるかまたはミスアドレスであるかを決定するキャッシュルックアップ回路と、
複数の受け取られたテクスチャマップアドレスを格納するための、該キャッシュルックアップ回路に結合されたＦＩＦＯメモリと、
該メモリユニット、該キャッシュルックアップ回路、該ＦＩＦＯメモリ、および該テクスチャマップキャッシュメモリに結合されたキャッシュコントローラ回路であって、（１）該キャッシュルックアップ回路が第１の該テクスチャマップのミスアドレスを決定してから、該第１のテクスチャマップデータが該キャッシュメモリに格納されるまでの期間中に、該ＦＩＦＯメモリの第１のロケーション内に格納されるテクスチャマップミスアドレスに対応する該第１のテクスチャマップデータを、該キャッシュメモリに格納するために該メモリユニットからフェッチし、（２）該キャッシュルックアップ回路が該第１のテクスチャマップのミスアドレスを決定してから、該第１のテクスチャマップデータが該キャッシュメモリに格納されるまでの期間中に、該ＦＩＦＯメモリの第２のロケーションに格納されるテクスチャマップヒットアドレスに対応し、該キャッシュメモリ内に格納されている第２の該テクスチャマップデータを提供する、キャッシュコントローラ回路と、
を有するコンピュータ制御されたグラフィック表示システム。
【請求項８】
前記キャッシュコントローラ回路がまた、前記期間中に、前記テクスチャマップキャッシュメモリ内に格納された第３のテクスチャマップデータを提供するためのものであり、該第３のテクスチャマップデータが、前記ＦＩＦＯメモリの第３のロケーションに格納された第２のテクスチャマップヒットアドレスに対応し、該第２のテクスチャマップヒットアドレスが、該テクスチャマップミスアドレスの後に、該ＦＩＦＯメモリによって受け取られる、請求項７に記載のシステム。
【請求項９】
グラフィック要素にそれぞれ対応する前記受け取られたテクスチャマップアドレスを生成するための、前記キャッシュルックアップ回路に結合されたアドレス生成回路をさらに有する、請求項７に記載のシステム。
【請求項１０】
前記ＦＩＦＯメモリがまた、前記期間中にテクスチャマップヒットアドレスを受け取り格納するためのものである、請求項７に記載のシステム。
【請求項１１】
前記テクスチャマップキャッシュメモリが１キロバイトのサイズである、請求項７に記載のシステム。
【請求項１２】
前記キャッシュコントローラ回路によって供給されるテクスチャマップデータを処理するための、前記キャッシュコントローラ回路に結合されたテクスチャフィルタ回路をさらに含む、請求項７に記載のシステム。
【請求項１３】
コンピュータ制御されたグラフィック表示システムにおける、テクスチャマップデータを検索する方法であって、
ａ）グラフィック要素のテクスチャマッピング動作に使用されるテクスチャマップデータをメモリユニット内に格納するステップと、
ｂ）該メモリユニットの該テクスチャマップデータの最近アクセスされたテクスチャマップデータをキャッシュメモリ内に格納するステップと、
ｃ）特定のテクスチャマップアドレスが、該キャッシュメモリの内容に対してヒットアドレスであるかまたはミスアドレスであるかを決定するステップと、
ｄ）複数の受け取られたテクスチャマップアドレスをＦＩＦＯメモリ内に格納し、該テクスチャマップアドレスに関連したテクスチャデータが該キャッシュメモリから供給されると、該ＦＩＦＯメモリのボトムから個々に格納されたテクスチャマップアドレスを除去するステップと、
ｅ）（１）該キャッシュルックアップ回路が第１の該テクスチャマップのミスアドレスを決定してから、該第１のテクスチャマップデータが該キャッシュメモリに格納されるまでの期間中に、該ＦＩＦＯメモリの第１のロケーション内に格納されるテクスチャマップミスアドレスに対応する該第１のテクスチャマップデータを、該キャッシュコントローラ回路を用いて該メモリユニットからフェッチして該キャッシュメモリに格納するステップと、
ｆ）該キャッシュルックアップ回路が該第１のテクスチャマップのミスアドレスを決定してから、該第１のテクスチャマップデータが該キャッシュメモリに格納されるまでの期間中に、該テクスチャマップミスアドレスの前に該ＦＩＦＯメモリによって受け取られた該ＦＩＦＯメモリの第２のロケーションに格納されるテクスチャマップヒットアドレスに対応し、該キャッシュメモリ内に格納されている第２の該テクスチャマップデータを該キャッシュコントローラ回路を用いて提供するステップと、
を包含する方法。
【請求項１４】
前記キャッシュコントローラ回路を用いて、前記期間中に、前記キャッシュメモリ内に格納された第３のテクスチャマップデータを提供するステップであって、該第３のテクスチャマップデータが、前記ＦＩＦＯメモリの第３のロケーション内に格納された第２のテクスチャマップヒットアドレスに対応し、該第２のテクスチャマップヒットアドレスが、該テクスチャマップミスアドレスの後に、該ＦＩＦＯメモリによって受け取られる、ステップをさらに包含する、請求項１３に記載の方法。
【請求項１５】
前記期間中に、前記ＦＩＦＯメモリにテクスチャマップヒットアドレスを受け取り、格納するステップをさらに包含する、請求項１３に記載の方法。
【請求項１６】
テクスチャフィルタ回路を用いて前記キャッシュコントローラ回路によって供給されるテクスチャデータを処理するステップをさらに包含する、請求項１３に記載の方法。
【請求項１７】
テクスチャマップミスアドレスを前記ＦＩＦＯメモリが受け取った際、他のテクスチャマップミスアドレスが該ＦＩＦＯメモリ内に格納されている場合に前記ステップｄ）を停止するステップをさらに包含する、請求項１３に記載の方法。
【請求項１８】
テクスチャマップミスアドレスが前記ＦＩＦＯメモリのボトムに到達した際、その対応するテクスチャマップデータが前記メモリユニットからまだ供給されていない場合に前記ステップｄ）を停止するステップをさらに包含する、請求項１３に記載の方法。
【発明の詳細な説明】
発明の分野
本発明は、コンピュータ制御グラフィックディスプレイシステムの分野に関する。具体的には、本発明は、テクスチャマップデータ取出サブシステムにおけるデータスループットの増強のためのシステムおよび方法に関する。
発明の背景
典型的に、コンピュータ制御グラフィックディスプレイシステムは、グラフィック命令を高速で処理するための専用回路およびコード化された手順を含むグラフィックハードウェアユニット（例えば、「グラフィックカード」）に対して、データおよび制御信号を提供する。グラフィック命令は、典型的にはコンピュータメモリ内の「ディスプレイリスト」に格納される。命令は、いくつかのグラフィック要素およびグラフィックコマンドの表現を規定する。グラフィック要素は、例えば、個別の点、線、ポリゴン、充填体、BIT BLT(ビットブロックトランスファー）、テクスチャ、などである。グラフィック要素の集合は、３次元空間で表されるオブジェクトを、ディスプレイスクリーン上において２次元画像で表現するために用いられ得る。表現は、上記グラフィック要素およびグラフィック命令のラスタコード化データへの翻訳を含み、次いで、翻訳されたものは、ディスプレイスクリーン上での表示（「リフレッシュ」）のためにフレームバッファメモリ内にロードされる。
いくつかのポリゴングラフィック要素は、ポリゴン内で表示される、グラフィック画像を表すテクスチャデータの仕様を含む。テクスチャマッピングは、２次元ディスプレイスクリーン上に表示されるポリゴンの領域または表面に、表面詳細を追加する技術を称する。元のグラフィックオブジェクトは３次元であるので、テクスチャマッピングは、しばしば、要素に追加される表面詳細に対する特定の見込み属性の維持を伴う。メモリ内に格納され、典型的なテクスチャマップは、テクスチャ座標空間（u，v）に存在する点要素（「テクセル（ｔｅｘｅｌ）」）を含む。テクスチャ画像は、コンピュータメモリにおいて、ビットマップまたは他のラスタ型コード化フォーマットとして表される。更に、ディスプレイスクリーンは、表示座標空間（x，y）に存在する点要素（画素）を含む。
一般的に、テクスチャマッピングのプロセスは、表面詳細（例えば、画像）を格納するメモリユニットからのコード化された表面詳細点または「テクセル」へのアクセス、およびその表面詳細テクセルの、テクスチャマップされるグラフィック要素の所定の点への転送によって、発生する。テクスチャマップデータの個別のテクセルはメモリから読み出され、関連するポリゴンの位置および見込みによって、特定の形においてそのポリゴン内で適用される。したがって、（x，y）表示座標空間についての画素の色値は、テクスチャマップ値のサンプルに基づいて決定される。テクスチャマッピングのプロセスは、（u，v）テクスチャマップにおけるテクセルの色または視覚的属性を、ディスプレイスクリーンにおけるグラフィック要素の、対応する画素に対して適用することにより動作する。テクスチャマッピングの後、テクスチャ画像の型はグラフィック要素の表面上に見られ、適切な見込みがある場合、その見込みと共に見られる。
しかし、テクスチャマッピングのプロセスでは、グラフィックディスプレイシステムのメモリ容量に対する需要が大きい。なぜなら、典型的なディスプレイスクリーンアップデート周期の間に、多くのテクスチャマップがメモリからアクセスされるからである。スクリーンアップデート周期の周波数は速いので、スクリーンの個別のポリゴンは非常に速い周波数でアクセスされ、アップデートされる必要があり、それは、大きいデータスループット容量を必要とすることになる。上述のメモリ需要の観点から、高パフォーマンスグラフィックハードウェアユニットは、典型的には、テクスチャマップされたデータの高速での格納および取出のための、低アクセス時間キャッシュメモリユニットおよびキャッシュメモリコントローラユニットを含む。テクスチャキャッシュにより、テクスチャマップされたポリゴンがグラフィックユニットを介して処理される場合、そのポリゴン用のテクスチャマップがテクスチャキャッシュ内に格納されているかどうかのアドレスチェックが、グラフィックコントローラによって行われる。要求されるメモリアドレスがテクスチャキャッシュ内に存在しない場合、従来技術のシステムにおけるキャッシュコントローラユニットは停止するが、所望のテクスチャデータは外部メモリから獲得される。通常、キャッシュコントローラユニットが外部メモリに要求を出してから、その外部メモリから実際にテクスチャデータがフェッチされるまで、長い待ち時間（停止）がある。
停止している間グラフィックユニットの特定の部分は、キャッシュコントローラが、キャッシュデータの最も古い時期に用いられた（LRU）組を外部源から新たにフェッチされたデータと置き換えることを待つ。その間、グラフィックユニットの多くの部分は有益な作業を行うことを一時的に妨げられる。それは、それらの部分のデータが停止したためか（例えば、要求されたテクセルが存在しないためにテクスチャエンジンが停止したため）、またはそれらの部分からデータを受け取るユニットが使用中であり、データを受けつけないかのいずれかの理由からである。これまで以上に上昇しているグラフィックデータスループットへの強い要求（例えば、リアルタイムオーディオ／ビデオマルチメディアアプリケーション）の観点から、上述の待ち状態は、高パフォーマンスグラフィックディスプレイシステムにおける欠点である。
したがって、本発明は、コンピュータ制御グラフィックディスプレイシステムにおける、テクスチャマップデータの効率的な取出を提供するシステムおよび方法を提供する。更に、本発明は上述のようなシステムを提供し、そのシステムでは、テクスチャキャッシュミスに関連するテクスチャデータのフェッチを待つ間、テクスチャデータの有益な処理を行い得るテクスチャデータキャッシュコントローラユニットを提供する。上述に特に記載されていない、これらおよび他の利点は、以下の本発明についての考察から明らかになる
【図面の簡単な説明】
図１は、本発明による、コンピュータ制御グラフィックディスプレイシステムのブロック図である。
図２は、本発明による、コンピュータ制御グラフィックディスプレイシステムの３Ｄグラフィックサブユニットを示すブロック図である。
図３は、本発明による、グラフィックユニットのテクスチャマップデータアクセス（TDA）回路のブロック図である。
図４Ａおよび図４Ｂは、本発明のテクスチャマップアドレス（TMA）FIFOメモリユニットのトップエントリに位置づけられる、テクスチャマップデータ要求ミスアドレスおよびテクスチャマップデータ要求ヒットアドレスを示す。
図５Ａおよび図５Ｂは、図４Ａおよび図４ＢのFIFO構成の後にテクスチャマップアドレスFIFOメモリユニットのトップエントリに位置づけられる、テクスチャマップデータ要求ヒットアドレスを示す。
図６Ａは、本発明のキャッシュコントローラによって第（n＋１）番目の未処理ミスアドレスが受け取られる、第１のテクスチャエンジン停止状態を示す。
図６Ｂは、ミスアドレスがテクスチャマップアドレスFIFOメモリユニットの最終エントリに及ぶが、キャッシュコントローラが依然データフェッチ動作を終了していないという、第２のテクスチャエンジン停止状態を示す。
図７Ａは、フェッチされたテクスチャデータが、テクスチャマップアドレスFIFOメモリユニットにおける最も古いアドレスであるミスアドレス用に供給される、テクスチャマップアドレスFIFOメモリユニットのFIFO構成の図である。
図７Ｂは、第（n＋１）番目のミスアドレスが同時にテクスチャマップアドレスFIFOメモリユニット内に入る、図７Ａに示されるテクスチャマップアドレスFIFOメモリユニットのFIFO構成の図である。
図７Ｃ、図７Ｄ、図７Ｅ、および図７Ｆは、テクスチャマップアドレスFIFOメモリユニットの上部エントリに格納されるミスアドレス用のデータフェッチ動作の処理と同時に供給されるそれぞれ第１、第２、第３および第４のヒットアドレス用に、メモリキャッシュ内に格納されるテクスチャデータを示す。
図７Ｇは、図７Ｂ〜７Ｆにおける、ミスアドレス用のデータフェッチ動作の処理の間において、引き続き受け取られたヒットアドレスがテクスチャマップアドレスFIFOメモリユニット上部に位置づけられる状態を示す。
図８は、テクスチャデータヒットおよびミスアドレスをテクスチャマップアドレスFIFOメモリユニット上に位置づける、本発明の動作のフローチャート内におけるステップを示す。
図９は、テクスチャデータヒットおよびミスアドレスをテクスチャマップアドレスFIFOメモリユニットから除去する、本発明の動作のフローチャート内におけるステップを示す。
発明の要旨
コンピュータ制御されたグラフィックディスプレイシステム内のテクスチャマップデータ要求の処理効率を向上するための回路および方法を説明する。３Ｄグラフィックディスプレイサブユニットはグラフィックディスプレイシステム内に含まれ、このサブユニットはポリゴンエンジン、テクスチャマップエンジンおよび画素パイプラインを含む。テクスチャマップエンジンは、（u,v）座標空間内に格納された使用中のテクスチャマップを含むためのコンピュータ読み出し可能キャッシュメモリを備えたキャッシュコントローラを有するテクスチャマップデータアクセス（ＴＤＡ）回路を含む。キャッシュコントローラは、ｎ個のキャッシュミス動作を同時に処理するだけに制限される。ある実施形態において、ｎは１である。ＴＤＡ回路はまた、キャッシュメモリユニット内でヒットまたはミスするテクスチャデータ要求に関連するテクスチャマップアドレスを格納するためのテクスチャマップアドレスＦＩＦＯメモリユニットも含む。キャッシュコントローラはミスをｎ個まで処理するので、（ｎ＋１）番目の未処理テクスチャ要求ミスに遭遇した場合に、テクスチャエンジンは停止する。従って、ＴＭＡ ＦＩＦＯは、任意の時間において最大ｎ個のミスアドレスを含む。１つのミスに遭遇したがＴＭＡ ＦＩＦＯが未処理ヒットアドレスを含む場合、処理効率は向上する。この時、ミスしたアドレスについてのテクスチャデータをフェッチするキャッシュコントローラで同時に、（１）以前に遭遇し、格納したヒットアドレスについて、キャッシュメモリからのデータを供給すること、および（２）新たなヒットアドレスをＴＭＡ ＦＩＦＯ内に受け取ることにより、テクスチャエンジンの停止を効率的に回避することを有利に行い得る。これは、テクスチャミス上のヒットアドレスを処理せずに、テクスチャエンジンを停止させる従来技術のシステムとは全く異なるものである。
具体的には、本発明の実施形態は、命令および処理データを実行するためのホストプロセッサ、ホストプロセッサに結合されたバス、グラフィックイメージを表示するためのディスプレイスクリーン、およびテクスチャマップデータを取り出すための回路を含む。回路は、グラフィック要素（graphic primitive）のテクスチャマッピング動作に使用されるテクスチャマップデータを含むためのメインメモリ（またはローカルフレームバッファ）と、メインメモリ（またはローカルフレームバッファメモリ）のテクスチャマップデータのアクセス中のサブテクスチャマップデータを含むためのテクスチャマップキャッシュメモリと、キャッシュメモリのコンテンツについて、受け取られたテクスチャマップアドレスがヒットアドレスあるいはミスアドレスのいずれなのかを判定するためのキャッシュコントローラ回路に結合されたキャッシュルックアップ回路と、複数の受け取られたテクスチャマップアドレスを格納するためのキャッシュルックアップ回路に結合されたＦＩＦＯメモリと、メインメモリ、ＦＩＦＯメモリ、およびテクスチャマップキャッシュメモリに結合されたキャッシュコントローラ回路とを含み、キャッシュコントローラ回路は（１）フェッチインターバルの間に、テクスチャマップキャッシュメモリ内への格納のためにメインメモリから第１のテクスチャマップデータをフェッチし、第１のテクスチャマップデータはＦＩＦＯメモリの第１の位置に格納されたテクスチャマップミスアドレスに対応し、更にキャッシュコントローラ回路は（２）フェッチインターバル内で、テクスチャマップキャッシュメモリ内に格納された第２のテクスチャマップデータを提供し、第２のテクスチャマップデータはＦＩＦＯメモリの第２の位置に格納された第１のテクスチャマップヒットアドレスに対応し、第１のテクスチャマップヒットアドレスはテクスチャマップミスアドレスの前にＦＩＦＯメモリによって受け取られる。
本発明の実施形態は上記を含み、キャッシュコントローラはまた、フェッチインターバルの間に、テクスチャマップキャッシュメモリ内に格納された第３のテクスチャマップデータを提供し、第３のテクスチャマップデータはＦＩＦＯメモリの第３の位置に格納された第２のテクスチャマップヒットアドレスに対応し、第２のテクスチャマップヒットアドレスはテクスチャマップミスアドレスの前にＦＩＦＯメモリによって受け取られ、ＦＩＦＯメモリはまたフェッチインターバルの間にテクスチャマップヒットアドレスを受け取って、格納する。
好適な実施形態の説明
本発明、つまりテクスチャデータキャッシュメモリに関連して使用される効率的なテクスチャデータ取り出し方法の以下の詳細な説明において、本発明の完全な理解を提供するために複数の特定的な詳細を説明する。しかし、本発明はこれらの特定的な詳細なしで実施し得ること、または異なるエレメントまたはプロセスを用いることによって実施し得ることが、当業者には明らかになる。他の例において、周知のプロセス、手順、構成要素、および回路は、本発明の必ずしも明瞭にする必要のない局面については、詳細には説明されていない。
表記法および用語法
以下の詳細な説明のいくつかの部分は、手順、論理ブロック、処理、およびコンピュータメモリ内のデータビット上の動作の他の記号表記に関して提示される。これらの説明および表記は、データ処理業界の当業者によって他の当業者に作業の内容を最も効果的に伝えるために使用される手段である。手順、論理ブロック、プロセス等は、本明細書中では、通常、所望の結果が得られる自己矛盾のないステップまたは命令のシーケンスと考えられる。ステップは、物理的な量の物理的な操作を要求するステップである。通常、必ずしもそうではないが、これらの物理的な操作は、コンピュータシステム内で格納、転送、結合、比較および他の操作が可能である電気信号または磁気信号の形態をとる。本明細書中において、本発明を参照して、これらの信号はビット、値、エレメント、記号、文字、語句または数等として参照される。
しかし、これら全ての語句が、物理的な操作および物理的な量を参照して解釈されるべきものであり、単に便利なラベルに過ぎず、更に当業界で通常使用される語句を鑑みて解釈されるべきものであることに留意されたい。特定的に述べない限りは以下の説明から明らかなように、本発明全体を通しての説明、つまり、「処理」、「演算」、「計算」、「判定」または「表示」等の語句を利用した説明が、コンピュータシステムまたはデータを操作し且つ変換する同様の電子演算装置の働きおよびプロセスを指す。データは、コンピュータシステムのレジスタおよびメモリ内の物理的な（電子的な）量として示され、コンピュータシステムメモリ、コンピュータシステムレジスタ、もしくは、他の情報格納装置、情報転送装置または情報表示装置内に同様に物理的な量として示された他のデータへと転換される。
コンピュータ制御されたグラフィックディスプレイシステム
図１に、本発明に従って使用されるコンピュータ制御されたグラフィックディスプレイシステム１１２のブロック図を示す。通常、本発明の実施形態によって使用されるホストコンピュータシステム１１２は、情報を通信するためのバス１００と、情報および命令を処理するためのバス１００と結合した１つ以上のホストプロセッサ１０１、ホストプロセッサ１０１についての情報および命令を格納するためのバス１００に結合されたコンピュータ読み出し可能揮発性メモリユニット１０２（例えばランダムアクセスメモリユニット）と、ホストプロセッサ１０１についてのスタティック情報および命令を格納するためのバス１００と結合したコンピュータ読み出し可能不揮発性メモリユニット１０３（例えば読み出し専用メモリユニット）と、情報および命令を格納するためのバス１００と結合された磁気ディスクまたは光ディスクならびにディスクドライブ（例えばハードドライブまたはフロッピーディスケット）等のコンピュータ読み出し可能データ格納装置１０４と、コンピュータユーザに情報を表示するためのバス１００に結合された表示装置１０５とを含む。本発明のコンピュータシステム１１２で利用される表示装置１０５は、液晶装置、陰極線管、またはユーザが認識できるグラフィックイメージおよび英数字を作成するのに適した他の表示装置であり得る。
ホストコンピュータシステム１１２は、データおよび制御信号をバス１００を介して例えば「グラフィックカード」１０８等のグラフィックハードウェアユニットまたはシステムに提供する。グラフィックハードウェアシステム１０８はコンピュータメモリ内に格納された表示リスト内に見られる一連の表示命令を実行するための３Ｄグラフィックサブユニット１０９を含む。通常、表示リストは例えば独立した点、線、ポリゴン、フィル（fill）、ＢＩＴ ＢＬＴ（ビットブロック転送）、テクスチャ等の複数のグラフィック要素のレンダリングに関する命令を含む。ポリゴン表示命令の多くが、ポリゴン内に表示されるテクスチャデータを含む。テクスチャデータは、システム１１２のコンピュータ読み出し可能（例えば揮発性）メモリユニット、または、（u,v）座標系内に格納されたラスタ型データの形態の（例えばビットマップされた形態の）ローカルフレームバッファ１１０内に格納される。テクスチャデータの個々の構成要素（例えば「テクセル」）がメモリから読み出され、関連するポリゴンの配置および視点に依存する特定の様式でポリゴン内に与えられる。関連するテクスチャデータでポリゴンのレンダリングを行う処理は「テクスチャマッピング」と呼ばれる。多くのテクスチャマップがメモリからアクセスされて、表示されたフレームを構築するので、テクスチャマッピングはコンピュータシステム１１２のメモリ容量に対する大きな需要を必要とする。スクリーンの更新は、素早く実行される必要があるので、ポリゴンは極めて素早く更新される必要があり、更なるテクスチャマップがアクセスされ、極めて早急な様式で与えられ、それによりメモリ需要を増大する。バス１００”上方のグラフィックハードウェアシステム１０８は、データおよび制御信号を、表示装置１０５上の画像（グラフィックイメージを含む）をレンダリングするために表示装置１０５をリフレッシュするローカルフレームバッファメモリ１１０に供給する。グラフィックハードウェアシステム１０８の構成要素（例えば３Ｄグラフィックサブユニット１０９）を以下により詳細に説明する。
図２は、テクスチャエンジン１０、ポリゴンエンジン１２および画素パイプライン１６を含むグラフィックサブユニット１０９の回路の一部分を示す。テクスチャエンジン１０は、バス５上の、レンダリングされる各ポリゴンに対応するポリゴンの頂点データを受け取る。ポリゴンの頂点データは、ポリゴンの各頂点についてのデータポイントを含む。トライアングルポリゴンに関して、３頂点の各々が、自身の位置座標値（x,y,z）と、自身の色値（赤、緑、青）と、自身のテクスチャマップ座標値（u,v）と、自身の視点値（w）と、もし存在するなら、ポリゴンについてのテクスチャマップデータの識別を含む他の要求された値とを含む。テクスチャエンジン１０は、ポリゴンについてのテクスチャマップデータの取り出しおよびポリゴンの画素上へのテクスチャデータのテクセルのマッピングに対して管理義務がある。一旦テクスチャエンジン１０がトライアングルの各頂点についてのテクスチャマップ座標（u,v）を与えられると、テクスチャキャッシュコントローラ２５０に進み、トライアングルへの配置のために適合するテクセルにアクセスし得る。このプロセスの間に、テクスチャエンジン１０はポリゴンの表面の３次元視野を維持する。テクスチャマップデータ取り出し（ＴＤＡ）回路２００は、本発明に従ってテクスチャマップデータ取り出しプロセスを実行する。テクスチャエンジン１０のテクスチャ取り出しシステムはさておき、複数の周知の手順および回路が、視野を維持するため、ならびに、テクスチャエンジン１０内で実行されるテクスチャマッピング動作の実行のために使用され得る。テクスチャマップ画素データは、テクスチャエンジン１０からバス１４ａ上の画素パイプライン１６に供給される。
図２のポリゴンエンジン12は、バス５を介してポリゴンデータを受信し、そしてポリゴン要素の位置、色、および奥行きに関して周知のポリゴンレンダリング機能を実行する。本質的には、ポリゴンエンジンは、ポリゴン頂点データに基づいて、補間を使用してポリゴン要素内の画素の画素位置および色を計算する。ポリゴンエンジン１２から得られた画素情報は、バス１４ｂを介して画素パイプラインへ転送される。画素パイプライン１６は、テクスチャエンジン１０からのテクスチャデータ（テクセル）とポリゴンエンジン１２からの画素データとを混合し、合成ポリゴン画像を形成する。合成画像のデータ（画素）は、バス１８上をラスタコード化形式で転送され、ラスタコード化フレームバッファ（グラフィックサブユニット１０９内に存在するが、図２に示されない）に格納され、そして最後にディスプレイスクリーン１０５（図１）に表示される。上記動作は、各受信されたポリゴン要素に対して個々に行われる。１つの実施例において、画素パイプライン１６は、プログラム可能な画像特徴に依存して、約５クロック周期から７クロック周期の呼び出し時間を含む。
本発明のテクスチャマップデータ検索（TDA）回路200
図３は、本発明によるテクスチャマップデータアクセス（TDA）回路200の構成要素を例示する。TDA回路200は、（アドレス形態の）テクスチャマップデータ要求を処理するための効率的な機構を提供し、これによって有用なテクスチャマップデータが、フェッチ間隔中にキャッシュメモリ251からフィルタ260へ供給され得、ここで同時に、他のテクスチャデータがメインメモリ102またはローカルフレームバッファ110（図１）からフェッチされる。この動作は、フェッチ間隔中に、テクスチャエンジンが停止し、そしてフェッチが完了するまで有用なテクスチャマップデータが提供されない従来技術とは異なる。さらに、フェッチ間隔中に、後に受信されるヒットアドレスがTDA回路200によって受信され、これによってアドレスをTDA回路200に供給する回路の停止を防止する。
上述のように、テクスチャエンジン10によって受信されたポリゴンデータは、現在処理中のポリゴンによって使用されたテクスチャマップ（例えば、テクスチャマップのベースアドレス）の指示（例えば、ポインタ）を含む。TDA回路200は、バス205を介して上記参照されたテクスチャマップベースアドレスを受信するアドレス制御ユニット210を含む。テクスチャマップベースアドレス情報はまた、バス207上をアドレス生成器ユニット220へ転送される。アドレス生成器ユニット220は、アドレス制御ユニット210から始まるライン237の制御信号によって制御される。アドレス生成器ユニット220はまた、現在のポリゴン要素に対応するテクスチャ座標（ｕ，ｖ）を受信する。アドレス生成器ユニット220は、（ｕ，ｖ）テクセルアドレスおよび詳細レベル（LOD）情報をポリゴン要素の各対応画素に対して生成する。これらの新しい「受信された」テクスチャマップアドレス（「テクセルアドレス」）は、個々にユニット220からキャッシュルックアップユニット230へ転送される。
多くの異なるテクセルアドレス生成機構が、本発明内において、アドレス生成器ユニット220によって使用され得る。１つの実施態様において、アドレス生成器ユニット220は、要求されたテクセルアドレスを計算するためにu_main、v_main、du_main、du_ortho、dv_main、およびdv_orthoを入力する。この実施態様において、これらの用語は、代理人事件整理番号CRUS-096-050を用いて本発明の譲受人に譲渡された、Vaswaniらの同時係属特許出願第 、出願日 、および題名「Non-Homogenous Second Order Perspective Texture Mapping Coordinates Using Linear Interpolation」において規定される。
図３のキャッシュルックアップユニット230は、制御およびアドレスバス235を使用して、テクスチャマップキャッシュメモリ回路（「キャッシュメモリ」）251の内容を調べ、各受信されたテクスチャマップアドレスがキャッシュメモリ251に格納されたテクスチャマップデータと対応するかどうかを判断する。キャッシュメモリ251は、キャッシュコントローラ回路250内に存在し、そして１つの実施態様において所定の大きさ（例えば、１ｋバイト）の16ビット完全関連づけ（fully-associated）キャッシュである。１つの実施態様において、キャッシュメモリ251は、16セット（各64バイト）に分割される。受信されたテクスチャマップアドレスは、キャッシュ回路251中に格納されたテクスチャマップデータに対応する場合、それはテクスチャマップヒットアドレス（「ヒットアドレス」）である。受信されたテクスチャマップアドレスは、キャッシュ回路251中に格納されたテクスチャマップデータに対応しない場合、それはテクスチャマップミスアドレス（「ミスアドレス」）である。後者の場合において、フェッチ間隔は、キャッシュコントローラ回路250がキャッシュメモリ251に格納するためのメインメモリ102またはローカルフレームバッファ110からの要求されたテクスチャマップデータをフェッチするように要求される。１つの実施態様において、数個のスクリーンラインからなる部分（例えば、単一のセットサイズに対応する64バイト）を表す１ブロックのテクスチャデータが各フェッチ間隔においてフェッチされる。本発明の１つの実施態様において、フェッチされたテクスチャマップデータは、８×８マトリクスのテクスチャマップデータからそれぞれなる64バイトブロック中（セットに対応する）にフェッチされる。
キャッシュコントローラ250は、テクスチャデータがメインメモリ102（またはローカルフレームバッファ110）からフェッチされそしてキャッシュメモリ251内に格納されるｎ個の同時フェッチ動作を行う回路を含む。１つの実施態様において、ｎ＝１である。ｎ個より多いフェッチ動作が要求される場合、ｎ個のフェッチ動作が完了するまでさらなるフェッチ動作が遅延される。上述の実施態様において、第２のフェッチ動作が要求され、そして待機状態中のフェッチ動作がまだ完了していない場合、第２のフェッチ動作は待機状態中のフェッチ動作の完了まで遅延される。フェッチ動作の間隔は、フェッチ間隔と称される。フェッチ動作は、システム112のバス100と通信的にインターフェースされるバス202を使用して、メインメモリ102またはローカルフレームバッファ110からのバス110”からテクスチャマップデータを受信する。多くの周知の回路および技術が、テクスチャマップデータフェッチ動作を実施するために、本発明の範囲内でキャッシュコントローラ回路250によって使用され得る。
本発明の１つの実施形態において、フェッチ動作と並列に（同時に）、キャッシュコントローラ回路250およびキャッシュメモリ251が、キャッシュメモリ251内に格納され、フェッチ間隔の開始前に受信されたテクスチャマップヒットアドレスに対応するテクスチャマップデータを供給するために使用され得る。
図３の先入れ先出し（FIFO）メモリ回路240は、キャッシュルックアップユニット230からテクスチャマップアドレスを受信し、入力に結合される。FIFOメモリ240（TMA FIFOとも称される）は、ヒットまたはミスアドレスを格納するための多くのエントリ（１）−（ｍ）を含む。FIFOメモリユニット240のボトムエントリ（物理的または論理的）にあるテクスチャマップアドレスは、テクセルがテクスチャキャッシュ251において利用できる場合に、対応するテクスチャマップデータがキャッシュメモリユニット251からフェッチされ、そしてバス253上に供給されるように処理される。キャッシュメモリユニット251は、アドレスおよび制御バス238上のFIFOメモリ240のボトムエントリによって、アドレッシングされる。ボトムエントリアドレスに対応するテクスチャマップデータがキャッシュメモリ251においてまだ利用できない場合、FIFOメモリ240は、データが利用できるまで停止される。対応するテクスチャマップデータがキャッシュメモリ251から供給される場合、ボトムエントリテクスチャマップアドレスは、FIFOメモリ240から取り除かれる。
フィルタユニット260は、キャッシュコントローラ回路250からバス253を介してテクスチャマップデータを受信し、そして線形フィルタ、双線形フィルタ、および三線形フィルタを行うことを含む多くの周知のデータフィルタ動作を行う。次に、フィルタユニット260は、ポリゴンに対するテクスチャマップデータを、外部バス273に結合されたオプションの出力FIFO270へ出力する。バス273は、バス14a（図２）へそして画素パイプライン回路16へ結合される。
本発明のTDA回路200のFIFOメモリ240の動作がここで説明される。図4Aは、FIFOメモリ240が空でそしてミスアドレスがトップエントリ（１）へプッシュされるFIFO構成を例示する。この構成上で、キャッシュコントローラ250は、ミスアドレスに対するテクスチャマップを得るためにフェッチ間隔を開始する。図4Bは、FIFOメモリ240が空でそしてヒットアドレスがトップエントリ（１）へプッシュされるFIFO構成を例示する。
図5Aは、図4AのFIFO構成を例示するが、後に受信されるヒットアドレスが、次にトップエントリ（１）上へプッシュされ、そしてミスアドレスが次にエントリ（２）へコピーされる。この構成において、エントリ（２）のミスアドレスに対するフェッチ間隔は、まだ完了しないことが理解される。図5Aは、多重の後に受信されるヒットアドレスがフェッチ間隔中にFIFOメモリ240上へプッシュされ得ることを例示する。この後に受信されるヒットアドレスは、まだキャッシュメモリユニット251によって処理されないが、FIFOメモリ240中に残る。したがって、本発明は、TDA回路200がフェッチ間隔中に新しいテクスチャマップアドレスを受信することを可能にするという利点があり、したがってフェッチ間隔中にこれらのテクスチャマップアドレスを供給する回路の停止を防止する。図5Bは、図4BのFIFO構成を例示するが、後にフェッチされるヒットアドレスが、次にトップエントリ（１）上へプッシュされ、そして第１のヒットアドレスがFIFO240の外へポップされる。
図6Aおよび図6Bは、FIFOメモリ240停止状態を起こす２つのFIFO構成を例示する。停止中に、FIFOメモリ240およびTDA回路200は、これ以上のテクスチャマップアドレスを受信しない。図6Aは、初期に受信されたミスアドレスがFIFOメモリ240のボトム近くのエントリ（ｍ’）中にあり、多くのヒットアドレスが受信されそしてエントリ（１）から（ｍ’−１）中に格納され、そして次に別のミスアドレス310aが受信される、FIFO停止状態を例示する。エントリ（ｍ’）中のミスアドレスがまだ待機状態中である（例えば、まだフェッチ間隔がオープンである）。ｎ＝１である実施態様において、この状態は、キャッシュコントローラ回路250が一度に１つのフェッチ間隔だけを処理するので、FIFO停止を起こす。したがって、FIFOメモリ240は、停止し、そしてエントリ（ｍ’）中のミスアドレスを取り除くまで、新しいテクスチャマップアドレスを受信しない。
図6Bは、待機状態のミスアドレスがFIFOメモリ240のボトムエントリ（ｍ）に到達し、そしてFIFOメモリ240の残りであるエントリ（１）から（ｍ−１）が、ヒットアドレスで満たされる、第２のFIFO停止構成を示す。新しいテクスチャマップアドレスが受信されないが、この構成において、エントリ（ｍ）中のミスアドレスに対応するテクスチャマップデータは、そのフェッチ間隔がまだ完了していないので、まだ利用できない。この構成において、FIFOメモリ240は、エントリ（ｍ）中のミスアドレスに対するテクスチャマップデータが利用できるようになるまで（この時点でこのミスアドレスは、FIFOメモリ240から取り除かれる）、停止する。
図７Ａは、ＦＩＦＯメモリ２４０の「ボトム」エントリが、実際の最後の物理的エントリ（ｍ）または、最も古いテクスチャマップアドレスを含むエントリとして定義される論理ボトムエントリと見なし得る様子を示している。本発明の一実施形態において、ＦＩＦＯメモリ２４０の最後の物理的エントリ（ｍ）は、キャッシュメモリ２５１にアドレスして対応するテクスチャマップデータを検索するために用いられる。しかし、図７Ａに示すように、論理ボトムエントリ（ｍ’）は本発明の別の実施形態においても用いられ得る。図７Ａにおいて、ミスアドレスはＦＩＦＯメモリ２４０内の最も古いアドレスとして位置（ｍ’）にあり、その他の後に受け取られたヒットアドレスは、エントリ（ｌ）〜（ｍ’−ｌ）に格納される。このとき、エントリ（ｍ’）におけるミスアドレスのフェッチ期間が完了し、その対応するテクスチャデータをキャッシュメモリ２５１から供給させる。次にエントリ（ｍ’）におけるミスアドレスはＦＩＦＯメモリ２４０から除去される。
図７Ｂ〜図７Ｇは、本発明のＴＤＡ回路２００のテクスチャマップデータ検索における効果的な使用法を示す。この使用法において、テクスチャマップデータはフェッチ期間中においてＴＤＡ回路２００からテクスチャエンジン１０に供給される。図７Ｂは、第１のミスアドレスが待機中であり、（ｍ’）エントリに格納されており、ＦＩＦＯメモリ２４０のエントリ（１）から（ｍ’−１）に数個のヒットアドレスが格納されており、その後第２のミスアドレス３２０ａが受け取られた場合のＦＩＦＯ構成を示す。この時点ｔ＝０において、図７Ｂに示すように第１のミスアドレスのテクスチャマップデータがキャッシュメモリ２５１中で利用可能になる。
図７Ｃは、次のクロックサイクルｔ＝１において、第２のミスアドレスがエントリ（１）に格納され、ヒットアドレスが各々下方にシフトされてＦＩＦＯメモリ２４０のエントリ（２）〜（ｍ’）を占めている状態のＦＩＦＯ構成を示す。またｔ＝１において、キャッシュコントローラ回路２５０は第２のミスアドレスについてメインメモリ１０２からテクスチャマップデータを検索するためのフェッチ期間を開始する。このフェッチ期間と同時に、キャッシュコントローラ回路２５０は、ＦＩＦＯメモリ２４０のボトムエントリ（ｍ’）（物理ボトムまたは論理ボトム）に位置するヒットアドレス（アドレス１）を用いて、キャッシュメモリ２５１にもアクセスする。次にキャッシュコントローラ回路２５０は、このヒットアドレス１に対応するテクスチャマップデータを、テクスチャフィルタ２６０に供給する。従って、本発明のＴＤＡ回路２００は、テクスチャデータフェッチ期間中にテクスチャデータを供給することを可能にするという利点を有する。
図７Ｄは、次のクロックサイクルｔ＝２において、第２のミスアドレスがエントリ（２）に格納され、以前に受け取られたヒットアドレスが各々下方にシフトされてＦＩＦＯメモリ２４０のエントリ（３）〜（ｍ’）を占めている状態のＦＩＦＯ構成を示す。また、新しく受け取られたヒットアドレスが、ＦＩＦＯメモリ２４０のエントリ（１）中にシフトされる。このように、本発明は、フェッチ期間中において、ＦＩＦＯメモリ２４０が新しいヒットアドレスを受け入れることを可能にするという利点を有する。ｔ＝２において、ｔ＝１で開始されたフェッチ期間はまだ待機中である。この待機中のフェッチ期間と同時に、キャッシュコントローラ回路２５０は、ＦＩＦＯメモリ２４０のボトムエントリ（ｍ’）（物理ボトムまたは論理ボトム）に位置するヒットアドレス（アドレス２）を用いて、キャッシュメモリ２５１にもアクセスする。次にキャッシュコントローラ２５０は、このヒットアドレス２に対応するテクスチャマップデータを、テクスチャフィルタ２６０に供給する。
図７Ｅは、クロックサイクルｔ＝３において、第２のミスアドレスがエントリ（３）に格納され、以前に受け取られたヒットアドレスが各々下方にシフトされてＦＩＦＯメモリ２４０のエントリ（４）〜（ｍ’）を占めている状態のＦＩＦＯ構成を示す。ｔ＝２において受け取られたヒットアドレスはエントリ（２）中にシフトされ、新しく受け取られたヒットアドレスが、ＦＩＦＯメモリ２４０のエントリ（１）中にシフトされる。ｔ＝３において、ｔ＝１で開始されたフェッチ期間はまだ待機中である。この待機中のフェッチ期間と同時に、キャッシュコントローラ回路２５０は、ＦＩＦＯメモリ２４０のボトムエントリ（ｍ’）（物理ボトムまたは論理ボトム）に位置するヒットアドレス（アドレス３）を用いて、キャッシュメモリ２５１にもアクセスする。次にキャッシュコントローラ２５０は、このヒットアドレス３に対応するテクスチャマップデータを、テクスチャフィルタ２６０に供給する。
図７Ｆは、クロックサイクルｔ＝４において、第２のミスアドレスがエントリ（４）に格納され、唯一残っている以前に受け取られたヒットアドレスが下方にシフトされてＦＩＦＯメモリ２４０のエントリ（ｍ’）に入れられた状態のＦＩＦＯ構成を示す。ｔ＝３において受け取られたヒットアドレスはシフトされてエントリ（２）〜（３）を占めており、新しく受け取られたヒットアドレスはＦＩＦＯメモリ２４０のエントリ（１）中にシフトされる。ｔ＝４において、ｔ＝１で開始されたフェッチ期間はまだ待機中である。この待機中のフェッチ期間と同時に、キャッシュコントローラ回路２５０は、ＦＩＦＯメモリ２４０のボトムエントリ（ｍ’）に位置するヒットアドレス（アドレス４）を用いて、キャッシュメモリ２５１にもアクセスする。次にキャッシュコントローラ２５０は、このヒットアドレス４に対応するテクスチャマップデータを、テクスチャフィルタ２６０に供給する。このプロセスは、（１）待機中のミスアドレスに対して以前に受け取られたヒットアドレスが存在し、且つ（２）フェッチ期間がまだ待機中である限り、各次のクロックサイクルについて継続され得る。図７Ｃから図７Ｆを参照して、各ヒットアドレスは処理された後にＦＩＦＯメモリ２４０からポップされることが理解される。
図７Ｇは、待機中のフェッチ期間（ｔ＞４）の完了時において、ミスアドレスに対する要求されたテクスチャデータがキャッシュメモリ２５１に格納された状態のＦＩＦＯ構成を示す。次に、キャッシュコントローラ２５０は、ＦＩＦＯメモリ２４０のボトムエントリ（ｍ’）に位置するミスアドレスを用いて、キャッシュメモリ２５１にアクセスする。次にキャッシュコントローラ回路２５０は、このミスアドレスに対応するテクスチャマップデータを、テクスチャフィルタ２６０に供給する。次に、エントリ（１）〜（４）中に位置するヒットアドレスは、新しいテクスチャマップアドレスがＦＩＦＯメモリ２４０の先頭で受け取られたとき、次の４クロックサイクルにわたって処理される。
ｔ＝１からｔ＝４のサイクルの間、本発明のＴＤＡ回路２００は、フェッチ期間の間にヒットアドレスを処理することによりテクスチャマップデータを供給するという利点を有する。またこの期間中において、新しいヒットアドレスはＦＩＦＯメモリユニット２４０によって受け入れられる。この環境において最高の性能利得を得るためには、ＦＩＦＯメモリ２４０のエントリサイズは、キャッシュコントローラ２５０がデータフェッチを行うために必要とするクロックサイクル数におよそ等しくされるべきである。本発明の一実施形態においてこの値は２０サイクルであり、例えば（ｍ）はおよそ２０エントリにされるべきである。一実施形態において、各テクスチャマップデータフェッチ期間は、テクスチャマップデータの１ブロック、例えば６４バイト（１６バイトが４ラインあるいは８バイトが８ラインにそれぞれ対応する）をフェッチすることを包含する。
テクスチャマッピングおよびテクスチャフィルタリング手順は、所与のアドレススペース近隣内において近く位置するテクスチャデータに対して動作することが多いため、動作においてＴＤＡ回路２００は非常に効果的であることが理解される。従って、テクスチャマップアドレスミスは通常は時間的に立て続けには受け取られず、むしろヒットアドレスの間に分散（spaced out）される。この期待される動作環境において、ＦＩＦＯメモリ２４０は２つの待機中のミスアドレスに出会うことによってしばしば停止することがなく、その結果キャッシュメモリ２５１の良好なデータスループットを提供する。
本発明のＴＤＡ回路２００の動作
図８は、本発明のＴＤＡ回路２００によって行われる、新しいテクスチャマップアドレス（ヒット／ミス）をＦＩＦＯメモリ２４０のエントリに入れるための処理４００のステップを示す。開始時において、ＦＩＦＯ２４０が空であると仮定する。処理４００は、ステップ４１０において開始し、アドレス発生器ユニット２２０において新しいテクスチャマップアドレス、例えば新しい（ｕ、ｖ）座標およびテクスチャマップベースアドレスが受け取られたか否かをチェックする。もしそうであれば、ステップ４１０においてアドレス発生器回路２２０は新しいテクスチャマップアドレスを計算する。ステップ４２０において、キャッシュルックアップ回路２３０は、新しいアドレスがヒットアドレスであるかミスアドレスであるかをチェックする。もしアドレスがヒットアドレスであれば、ステップ４３０に入ってヒットアドレスがＦＩＦＯ２４０に押し入れられ、ステップ４１０に再度入る。ステップ４２０においてアドレスがミスアドレスであれば、ステップ４４０に入る。
ステップ４４０において、ＴＤＡ回路２００はこのミスアドレスをＦＩＦＯ２４０中に押し入れる。これにより、待機中のミスアドレスについてのフェッチ期間が開始される。ステップ４５０において、もう一つの新しく受け取られたテクスチャマップアドレスがＴＭＡ回路２００によって受け取られた際、ステップ４５５に入る。ステップ４５５において、キャッシュルックアップ回路２３０は、新しいアドレスがヒットアドレスであるかミスアドレスであるかをチェックする。もし新しいアドレスがヒットアドレスであれば、ステップ４６０においてＴＭＡ回路２００は、ＦＩＦＯ２４０にすき間があるか否かをチェックする。すき間があれば、ステップ４４０に入って新しく受け取られたアドレスをＦＩＦＯ２４０に入れる。ステップ４６０において、ＦＩＦＯ２４０にすき間がなければ、ステップ４６５に入ってＴＭＡ回路２００は停止し、待機中のテクスチャデータフェッチ期間が完了して新しいＦＩＦＯエントリが利用可能になり得るまで待機する。
図８のステップ４５５において、新しく受け取られたアドレスがミスアドレスであれば、ステップ４７０においてＴＭＡ回路２００は別のミスアドレスがＴＭＡＦＩＦＯ２４０において既に待機中であるか否かをチェックする。もしそうであれば、ステップ４７５においてＴＭＡ回路２００は停止し、待機中のテクスチャデータフェッチ期間が完了して新しく受け取られたミスアドレスがキャッシュコントローラ２５０に供給可能になるまで待機する。ステップ４７５の完了時において、ステップ４４０に入って新しいミスアドレスをＦＩＦＯ２４０に押し入れる。この時点においてフェッチ期間が開始されることにより、キャッシュコントローラ回路２５０は、メインメモリ１０２（あるいはローカルフレームバッファ１１０）にアクセスして、新しく格納された待機中のミスアドレスに対するテクスチャマップデータを検索する。ステップ４７０において、別のミスアドレスがＦＩＦＯ２４０中に既に待機中でないのならば、ステップ４４０に入って新しいミスアドレスをＦＩＦＯ２４０に押し入れる。この時点において、フェッチ期間が開始されることにより、キャッシュコントローラ回路２５０は、メインメモリ１０２（あるいはローカルフレームバッファ１１０）にアクセスして、新しく格納された待機中のミスアドレスに対するテクスチャマップデータを検索する。
図９は、本発明のＴＤＡ回路２００によって行われる、テクスチャマップアドレスをＦＩＦＯメモリ２４０のボトムエントリから除去するための処理５００のステップを示す。処理５００はステップ５１０において開始し、ＴＤＡ回路２００が、ＦＩＦＯ２４０が空であるか否かをチェックする。空でなければ、ステップ５２０に入る。ステップ５２０において、本発明のＴＭＡ回路２００は、ＦＩＦＯの最後のエントリ（例えば論理ボトムまたは物理ボトム）に格納されたアドレスに対応するテクスチャデータがキャッシュメモリ２５１中に存在するか否かをチェックする。もし存在しなければ、ステップ５１０に入る。ステップ５２０において、最後のエントリに対するテクスチャデータがテクスチャキャッシュメモリ２５１に格納されていれば、ステップ５３０に入る。
ステップ５３０において、ＴＭＡ回路２００は、ＦＩＦＯ２４０から最後のＦＩＦＯエントリをポップする。ステップ５４０において、キャッシュコントローラ２５０は、最後のエントリアドレスに対応するキャッシュメモリ２５１からのテクスチャデータにアクセスし、このテクスチャデータをフィルタユニット２６０に供給する。
結論
本発明の好適な実施形態である、テクスチャデータキャッシュメモリとともに用いられる効率的なテクスチャデータ検索方法を以上に説明した。本発明を特定の実施形態について説明したが、本発明はそのような実施形態によって限定されると解釈されるべきではなく、以下の請求の範囲に従って解釈されるべきであることが理解される。
【図１】
0004110239.tif 000002
【図２】
0004110239.tif 000003
【図３】
0004110239.tif 000004
【図４Ａ】
0004110239.tif 000005
【図４Ｂ】
0004110239.tif 000006
【図５Ａ】
0004110239.tif 000007
【図５Ｂ】
0004110239.tif 000008
【図６Ａ】
0004110239.tif 000009
【図６Ｂ】
0004110239.tif 000010
【図７Ａ】
0004110239.tif 000011
【図７Ｂ】
0004110239.tif 000012
【図７Ｃ】
0004110239.tif 000013
【図７Ｄ】
0004110239.tif 000014
【図７Ｅ】
0004110239.tif 000015
【図７Ｆ】
0004110239.tif 000016
【図７Ｇ】
0004110239.tif 000017
【図８】
0004110239.tif 000018
【図９】
0004110239.tif 000019