テセレーションエンジン及びそのアプリケーション
【解決手段】
グラフィクス処理を行うための方法、装置及びシステムが開示される。この点において、処理ユニットは、テセレーションモジュール及び接続性モジュールを含む。テセレーションモジュールは、幾何学的形状の部分を逐次的にテセレートして幾何学的形状に対する一連のテセレーション点を提供するように構成される。接続性モジュールは、テセレーション点の１つ以上のグループを一連のテセレーション点が提供される順序で１つ以上のプリミティブ内へと接続するように構成される。
グラフィクス処理を行うための方法、装置及びシステムが開示される。この点において、処理ユニットは、テセレーションモジュール及び接続性モジュールを含む。テセレーションモジュールは、幾何学的形状の部分を逐次的にテセレートして幾何学的形状に対する一連のテセレーション点を提供するように構成される。接続性モジュールは、テセレーション点の１つ以上のグループを一連のテセレーション点が提供される順序で１つ以上のプリミティブ内へと接続するように構成される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概してコンピューティングシステムにおいて行われるコンピューティング動作に向けられている。より特定的には、本発明はコンピューティング動作を行う処理ユニット（例えばグラフィクス処理ユニット（ＧＰＵ））及びそのアプリケーションに向けられている。
【背景技術】
【０００２】
ＧＰＵは、グラフィクス処理タスク等のデータ並列コンピューティングタスクを行うように特別に設計される複雑な集積回路である。ＧＰＵは、例えば、ビデオゲームアプリケーション等のエンドユーザアプリケーションによって要求されるグラフィクス処理タスクを実行することができる。
【０００３】
図１はエンドユーザアプリケーション１０２とＧＰＵ１０８の間に何層ものソフトウエアが存在し得ることを示している。エンドユーザアプリケーション１０２は、アプリケーションプログラミングインタフェース（ＡＰＩ）１０４と通信する。ＡＰＩ１０４は、ＧＰＵ１０８に依存するフォーマットでよりはむしろ標準的なフォーマットでエンドユーザアプリケーション１０２がグラフィクスデータ及びコマンドを出力することを可能にする。ＡＰＩ１０４はドライバ１０６と通信する。ドライバ１０６は、ＡＰＩ１０４から受信した標準コードを、ＧＰＵ１０８によって理解されるネイティブフォーマットの命令にトランスレートする。ドライバ１０６は典型的にはＧＰＵ１０８の製造業者によって書かれる。ＧＰＵ１０８は次いでドライバからの命令を実行する。
【０００４】
様々なＡＰＩが商業的に利用可能である。エンドユーザアプリケーションの大部分は、ワシントン、レドモンドのマイクロソフト社(Microsoft Corporation of Redmond, Washington)によって開発されたダイレクトＸ(DirectX)（登録商標）に適合する。エンドユーザアプリケーションのこの大部分に広がるためには、ＧＰＵはダイレクトＸ（登録商標）に適合すべきである。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ダイレクトＸの最新バージョンはダイレクトＸ１１（「ＤＸ１１」）として知られている。ＤＸ１１は、ＧＰＵがシェーダのシーケンスを実装している統合化シェーダモデルを用いる。例えば、図２はＤＸ１１によって指定されるシェーダ２００の例示的なシーケンスを示している。図２に示されるように、ＧＰＵは、頂点シェーダ(vertex shader)２０２、次いでハルシェーダ(hull shader)２０４、次いでテセレーションシェーダ(tessellation shader)２０６、そしてその後に１つ以上の追加シェーダ２０８を実行して結果データを提供する。統合化シェーダモデルにおいては、先に実行されたシェーダ（例えばハルシェーダ２０４）によって提供される中間結果は、ＧＰＵが後続のシェーダ（例えばテセレーションシェーダ２０６）を実行するために用いられ得る。残念なことに、ＤＸ１１は、ＧＰＵハードウエア視点からは最適ではないスキームを含んでいる。
【０００６】
従って、ＤＸ１１に適合するだけでなく、ＧＰＵハードウエア視点からも効率的に動作するシステム、装置及び方法が必要とされている。
【課題を解決するための手段】
【０００７】
本発明の実施形態は、上述の必要性を満たす。例えば、本発明の実施形態は、処理ユニット内に実装されるグラフィクス処理方法を提供する。このグラフィクス処理方法は、幾何学的形状の部分を逐次的にテセレートして幾何学的形状に対する一連のテセレーション点を提供することを含む。このグラフィクス処理方法は更に、テセレーション点の１つ以上のグループを一連のテセレーション点が提供される順序で１つ以上のプリミティブ内へと接続することを含む。
【０００８】
本発明の別の実施形態は、テセレーションモジュール及び接続性モジュールを含む処理ユニットを提供する。テセレーションモジュールは、幾何学的形状の部分を逐次的にテセレートして幾何学的形状に対する一連のテセレーション点を提供するように構成される。接続性モジュールは、テセレーション点の１つ以上のグループを一連のテセレーション点が提供される順序で１つ以上のプリミティブ内へと接続するように構成される。
【０００９】
本発明の更なる実施形態は、システムメモリと、処理ユニットと、システムメモリ及び処理ユニットに結合されるバスと、を含むコンピューティングシステムを提供する。処理ユニットは、テセレーションモジュール及び接続性モジュールを含む。テセレーションモジュールは、幾何学的形状の部分を逐次的にテセレートして幾何学的形状に対する一連のテセレーション点を提供するように構成される。接続性モジュールは、テセレーション点の１つ以上のグループを一連のテセレーション点が提供される順序で１つ以上のプリミティブ内へと接続するように構成される。
【００１０】
本発明の更なる特徴及び利点の他、本発明の種々の実施形態の構成及び動作は、添付の図面を参照して以下に詳細に説明される。尚、本発明はここに説明される特定の実施形態に限定されない。そのような実施形態は例示の目的のみのためにここに提示されている。追加的な実施形態はここに含まれる教示に基き関連分野を含めた当業者にとって明らかであろう。
【図面の簡単な説明】
【００１１】
ここに組み込まれ且つ出願書類の一部をなす添付の図面は本発明を示し、そして明細書と共に、本発明の原理を説明すること及び関連分野を含めた当業者が本発明を作りそして使用するのを可能にすることに更に役立つ。
【００１２】
【図１】図１はグラフィクスを処理するための例示的なワークフローを示すブロック図である。
【００１３】
【図２】図２は例示的な３次元グラフィクスＡＰＩのグラフィクスパイプラインに含まれる例示的なシェーダを示す図である。
【００１４】
【図３】図３は本発明の実施形態に従う例示的なコンピューティングシステムのブロック図である。
【００１５】
【図４】図４は本発明の実施形態に従う例示的なコンピューティングシステムに含まれる追加的な要素を示す図である。
【００１６】
【図５】図５は本発明の実施形態に従う例示的なＧＰＵのブロック図である。
【００１７】
【図６】図６は図５のＧＰＵの追加的な詳細のブロック図である。
【００１８】
【図７】図７は本発明の実施形態に従いテセレーションシェーダを実行するための処理ユニットの例示的な機能ブロックを示す図である。
【００１９】
【図８】図８は本発明の実施形態に従い図７のテセレーションモジュールによって実装される、テセレーション点を作成するための例示的な方法を示す図である。
【００２０】
【図９Ａ】図９Ａは本発明の実施形態に従いパッチのテセレーション点を作成するための例示的なシーケンスを示す図（その１）である。
【図９Ｂ】図９Ｂは本発明の実施形態に従いパッチのテセレーション点を作成するための例示的なシーケンスを示す図（その２）である。
【図９Ｃ】図９Ｃは本発明の実施形態に従いパッチのテセレーション点を作成するための例示的なシーケンスを示す図（その３）である。
【００２１】
【図１０】図１０は本発明の実施形態に従い図７の接続性モジュールによって実装される、テセレーション点をプリミティブ内へと接続するための例示的な方法を示す図である。
【００２２】
【図１１】図１１は本発明の実施形態に従い接続性を決定するために用いられる例示的なルックアップテーブル（ＬＵＴ）を示す図である。
【００２３】
【図１２】図１２は本発明の実施形態に従い図７の接続性モジュールによって実装される、プリミティブの頂点を再使用するための例示的な方法を示す図である。
【００２４】
【図１３】図１３は本発明の実施形態に従い図９Ａのテセレーション点がどのようにしてプリミティブ内へと接続され得るのかを示す図である。
【００２５】
本発明の特徴及び利益は、図面と共に以下に記述される詳細な説明からより明らかになり、図面において同様の参照番号は全体を通して対応する要素を識別する。図面において、同様の参照数字は一般的に同一の、機能的に類似の、及び／又は構造的に類似の要素を示す。ある要素が最初に現れる図面は対応する参照番号の一番左の単一又は複数の桁によって示される。
【発明を実施するための形態】
【００２６】
I．概説
本発明のある実施形態は、テセレーションエンジンを伴う処理ユニット及びそのアプリケーションを提供する。以下の詳細な説明において、「１つの実施形態」、「ある実施形態」、「例示的実施形態」等に対する言及は、説明される実施形態が特定の特徴、構造又は特性を含んでいてよいが、全ての実施形態が必ずしも当該特定の特徴、構造又は特性を含む必要がなくてよいことを示している。また、そのような表現は必ずしも同じ実施形態を参照しているとは限らない。更に、特定の特徴、構造又は特性がある実施形態に関連して説明されている場合には、明示的に説明されていようとなかろうと、他の実施形態に関連して当該特定の特徴、構造又は特性を具現化することは当業者の知識の範囲内にあることと言える。
【００２７】
図２に関して上述したように、典型的なグラフィクスパイプラインは複数のシェーダを含み、これらのシェーダはテセレーションシェーダ２０６を含む。テセレーションシェーダ２０６への入力は、パッチ(patch)、即ち幾何学的形状（例えば長方形、三角形、又は線）を含む。テセレーションシェーダ２０６の１つの目的は、パッチを複数の点へとテセレートする(tessellate)ことである。グラフィクスパイプラインの後続の段階の間、これらの点は更なる処理を被るであろう。例えば、これらの点はプリミティブ(primitives)（例えば三角形）内へと接続されることがある。本発明の実施形態に従う処理ユニットは、ハードウエア視点からテセレーションシェーダ２０６を効率的に実行するように構成されるテセレーションエンジンを含むことにより、従来の処理ユニットと比べて低減された面積のフットプリント(footprint)と共により良好な性能（例えばより高速な処理）を提供する。
【００２８】
例示のみを目的とし且つ限定を目的とせずに、本発明の実施形態はＧＰＵに関してここに説明されることになる。しかし、関連分野を含めた当業者であれば、本発明はテセレーションシェーダを実行する他の種類の処理ユニット、例えば中央処理ユニット及びコプロセッサ、にも適用され得ることを理解するであろう。これら他の種類のプロセッサは本発明の精神及び範囲内で検討される。
【００２９】
本発明の実施形態によると、ＧＰＵは、テセレーションシェーダの実行及びそのアプリケーションに対してオフチップメモリ及びオンチップメモリを動的に用いる。オフチップメモリはオフチップローカルデータシェア（ＬＤＳ）と称され、そしてオンチップメモリはオンチップＬＤＳと称される。テセレーションが低い場合（例えば１００未満の頂点が関与する場合）には、オンチップＬＤＳが用いられる。テセレーションが高い場合（例えば１００を超える頂点が関与する場合）には、オフチップＬＤＳが用いられる。ＧＰＵドライバは、レジスタ書き込み（例えば１ビット）を通して、オンチップＬＤＳ又はオフチップＬＤＳのどちらが用いられるのかを表示する。テセレーション出力に対してオンチップＬＤＳ又はオフチップＬＤＳのどちらを用いるかの決定は、動的になされる。
【００３０】
本発明の別の実施形態は、ＤＸ１１によって指定されるスキームに適合する一方でＤＸ１１によって指定されるスキームよりもハードウエア視点からは効率的な方法でＧＰＵがテセレーションのための点を生成することを可能にするテセレーションエンジンに向けられている。上述したように、テセレーションは、パッチ上、即ち幾何学的形状（例えば長方形、三角形、又は線）上で実行される。ＧＰＵのテセレーションエンジンは、パッチをテセレートして、接続性エンジン(connectivity engine)がテセレーション点を接続するように構成される順序でテセレーション点を提供するように構成される。対照的に、ＤＸ１１アルゴリズムは、全てのテセレーション点を作成すると共にテセレーション点をメモリ内に記憶し、次いで接続性処理の間にこれらのテセレーション点をメモリからリトリーブする（retrieves)。ＤＸ１１アルゴリズムとは異なり、本発明の実施形態のテセレーションエンジンは、テセレーション点をメモリ内に記憶する必要はなく、その理由は、テセレーションエンジンはそれらが接続性エンジンにおいて処理される順序で生成されるところにある。
【００３１】
ある実施形態においては、テセレーションエンジンは、テセレーション点を作成する２つの演算ユニット(math units)を含む。第１の演算ユニットはパッチの外側エッジに対する点を作成するように構成され、また第２の演算ユニットはそのパッチの内側エッジに対する点を作成するように構成される。各演算ユニットは出力ＦＩＦＯ及び入力ＦＩＦＯを含む。出力ＦＩＦＯは２つの読み出し点を有しており、２つの点がクロックサイクル毎に読み出されることを可能にしている。結果として、テセレーションエンジンの２つの演算ユニットは、単一クロックサイクル内でプリミティブ（例えば三角形）の点を作成することができる。数クロックサイクルの後、テセレーションエンジンは、蛇紋路(serpentine path)を辿ることによってパッチの全ての点を作成する。このようにして、パッチの点は後続の接続性処理に対して適切な方法によりオンザフライ(on the fly)で作成されるが、ＤＸ１１によって指定されるようにメモリがパッチの全ての点を記憶する必要はない。
【００３２】
本発明の更なる実施形態は、固有のテセレートされた点のデータ(unique tessellated-point data)のみを提供するＧＰＵ及びそのアプリケーションに向けられており、それにより処理資源を節約している。ある実施形態においては、ＧＰＵはテセレーションモジュール及び接続性モジュールを含む。テセレーションモジュールはテセレートされた点のデータを接続性モジュールへ提供する。接続性モジュールは、テセレートされた点のデータのトポロジ（例えば点、線、又は三角形）に基づいてプリミティブを作成する。接続性モジュールはデータをストリップフォーム(strip form)で送り出し、そしてプリミティブに対する相対的索引(relative indices)を送る。
【００３３】
本発明の更なる実施形態は、複数のルックアップテーブル（ＬＵＴ）からＬＵＴを選択してパッチのテセレーション点が接続されているかどうかを決定するテセレーションエンジン及びそのアプリケーションに向けられている。複数のＬＵＴから１つのＬＵＴを選択することによって、本発明の実施形態のテセレーションレーションエンジンは、クロックサイクル毎に１つのプリミティブを提供することができる。対照的に、ＤＸ１１によって指定される単一ＬＵＴを用いることは、プリミティブを提供するために最大で３２クロックサイクルを必要とすることがある。
【００３４】
本発明の実施形態に従う例示的なテセレーションエンジンの更なる詳細が以下に説明される。しかし、これらの詳細を提供するのに先立ちそのようなテセレーションエンジンが実装され得る例示的なシステムを説明することは有用である。
【００３５】
II．例示的なシステム
図３はある実施形態に従うコンピューティングシステム３００のブロック図である。コンピューティングシステム３００は、ＣＰＵ３０２、ＧＰＵ３１０を含み、そして随意的にコプロセッサ３１２を含んでいてよい。図３に示される実施形態においては、ＣＰＵ３０２及びＧＰＵ３１０は別個の集積回路（ＩＣ）又はパッケージに含まれている。しかし、他の実施形態においては、ＣＰＵ３０２及びＧＰＵ３１０、又はそれらの集合的な機能は、単一のＩＣ又はパッケージ内に含まれていてよい。
【００３６】
加えて、コンピューティングシステム３００はまた、ＣＰＵ３０２、ＧＰＵ３１０及びコプロセッサ３１２によってアクセスされてよいシステムメモリ３０４を含む。実施形態においては、コンピューティングシステム３００は、スーパーコンピュータ、デスクトップコンピュータ、ラップトップコンピュータ、ビデオゲームコンソール、埋め込みデバイス、携帯デバイス（例えば携帯電話、スマートフォン、ＭＰ３プレイヤ、カメラ、ＧＰＳデバイス等）、又はＧＰＵを含み若しくはＧＰＵを含むように構成される何らかの他のデバイスを備えていてよい。図３には具体的に示されていないが、コンピューティングシステム３００は、コンピューティングシステム３００のコンテンツ（例えばグラフィクス、ビデオ等）を表示するためのディスプレイデバイス（例えば陰極線管、液晶ディスプレイ、プラズマディスプレイ等）を含んでいてもよい。ディスプレイデバイスは、コンテンツをユーザに表示するために用いられる（例えば、コンピューティングシステム３００がコンピュータ、ビデオゲームコンソール又は携帯デバイスを備えている場合）。
【００３７】
ＧＰＵ３１０は、特定の特別の機能（例えばグラフィクス処理タスク及びデータ並列一般計算タスク）を、ＣＰＵ３０２がソフトウエアにおいてそれらを行い得るであろうよりも通常は高速に行うことによって、ＣＰＵ３０２を支援する。実施形態においては、ＧＰＵ３１０はチップセット及び／又はＣＰＵ３０２若しくは他のプロセッサ内に集積化されていてよい。ＧＰＵ３１０の追加的な詳細は後で提供される。
【００３８】
コプロセッサ３１２もまたＣＰＵ３０２を支援する。コプロセッサ３１２は、限定はされないが、浮動小数点コプロセッサ、ＧＰＵ、ビデオ処理ユニット（ＶＰＵ）、ネットワーキングコプロセッサ、並びに関連する分野を含めて当業者に明らかであろうような他の種類のコプロセッサ及びプロセッサを備えていてよい。
【００３９】
ＧＰＵ３１０及びコプロセッサ３１２は、ＣＰＵ３０２及びシステムメモリとバス３１４を介して通信する。バス３１４は、周辺要素インタフェース(peripheral component interface)（ＰＣＩ）バス、アクセラレーテッドグラフィクスポート(accelerated graphics port)（ＡＧＰ）バス、ＰＣＩエクスプレス(PCI Express)（ＰＣＩＥ）バス、又は現在利用可能であり若しくは将来開発される別の種類のバスを含めてコンピュータシステムにおいて用いられる任意の種類のバスであってよい。
【００４０】
システムメモリ３０４に加えて、コンピューティングシステム３００はローカルメモリ３０６及びローカルメモリ３０８を更に含む。ローカルメモリ３０６はＧＰＵ３１０に結合されており、またバス３１４に結合されていてもよい。ローカルメモリ３０８はコプロセッサ３１２に結合されており、またバス３１４に結合されていてもよい。ローカルメモリ３０６及び３０８は、特定のデータ（例えば頻繁に用いられるデータ）への、そのデータがシステムメモリ３０４内に記憶されていたとした場合に可能であろうよりも高速なアクセスを提供するために、それぞれＧＰＵ３１０及びコプロセッサ３１２に利用可能である。
【００４１】
ある実施形態においては、ＧＰＵ３１０及びコプロセッサ３１２は、ＣＰＵ３０２と並列に命令をデコードし、そしてそれらを対象としている命令のみを実行する。別の実施形態においては、ＧＰＵ３１０及びコプロセッサ３１２を対象としている命令をＣＰＵ３０２がそれぞれのコマンドバッファへ送る。
【００４２】
図３には具体的に示されていないが、コンピューティングシステム３００は、ディスプレイデバイス（例えば陰極線管、液晶ディスプレイ、プラズマディスプレイ等）を含み又はディスプレイデバイスに接続されていてもよい。ディスプレイデバイスは、コンテンツをユーザに表示するために用いられる（例えば、コンピューティングシステム３００がコンピュータ、ビデオゲームコンソール又は携帯デバイスを備えている場合）。
【００４３】
III．例示的なコンピューティングシステムの追加的な詳細
上述したように、図３は本発明の実施形態の例示的なコンピューティングシステム３００を示している。図４は本発明の実施形態に従い例示的なコンピューティングシステム４００に含まれてよい追加的な要素を示している。
【００４４】
コンピューティングシステム４００は１つ以上の処理ユニット４０４を含む。処理ユニット４０４は汎用処理ユニット（例えば図３のＣＰＵ３０２）又は専用処理ユニット（例えば図３のＧＰＵ３１０）であってよい。処理ユニット４０４は通信基盤４０６（例えば通信バス（例えば図３のバス３１４）、クロスオーバーバー又はネットワーク）に接続される。
【００４５】
コンピューティングシステム４００はまた、通信基盤４０６からの（又は図示しないフレームバッファからの）グラフィクスデータ、テキストデータ及び他のデータをディスプレイユニット４３０（例えば液晶ディスプレイ）上での表示のために転送するディスプレイインタフェース４０２を含む。
【００４６】
コンピューティングシステム４００はまた、図３のシステムメモリ３０４等の主メモリ４０８、望ましくはランダムアクセスメモリ（ＲＡＭ）を含む。加えてコンピューティングシステム４００は、補助メモリ４１０を含んでいてもよい。補助メモリ４１０は例えば、ハードディスクドライブ４１２及び／又はリムーバブル記憶ドライブ４１４を含んでいてよく、フロッピー（登録商標）ディスクドライブ、磁気テープドライブ、光学ディスクドライブ等を代表する。リムーバブル記憶ドライブ４１４は周知の方法でリムーバブル記憶ユニット４１８から読み出し且つ／又はリムーバブル記憶ユニット４１８へ書き込みする。リムーバブル記憶ユニット４１８はフロッピー（登録商標）ディスク、磁気テープ、光学ディスク等を代表し、リムーバブル記憶ドライブ４１４によって読み出され且つ書き込まれる。理解されるであろうように、リムーバブル記憶ユニット４１８はコンピュータソフトウエア及び／又はデータが既に記憶されたコンピュータ可読記憶媒体を含む。
【００４７】
代替的な実装においては、補助メモリ４１０は、コンピュータプログラム又は他の命令がコンピュータシステム４００にロードされることを可能にするための他の同様のデバイスを含んでいてよい。そのようなデバイスは例えばリムーバブル記憶ユニット４２２及びインタフェース４２０を含み得る。そのような例は、プログラムカートリッジ及びカートリッジインタフェース（ビデオゲームデバイスにおいて見られるようなもの）、リムーバブルメモリチップ（例えば消去可能プログラム可能リードオンリメモリ（ＥＰＲＯＭ）又はプログラム可能リードオンリメモリ（ＰＲＯＭ））及び関連するソケット、並びにソフトウエア及びデータがリムーバブル記憶ユニット４２２からコンピューティングシステム４００へ転送されることを可能にする他のリムーバブル記憶ユニット４２２及びインタフェース４２０を含み得る。
【００４８】
コンピューティングシステム４００はまた通信インタフェース４２４を含んでいてよい。通信インタフェース４２４は、ソフトウエア及びデータがコンピューティングシステム４００と外部デバイスの間で転送されることを可能にする。通信インタフェース４２４の例は、モデム、ネットワークインタフェース（例えばイーサネット（登録商標）カード）、通信ポート、パーソナルコンピュータメモリカード国際協会(Personal Computer Memory Card International Association)（ＰＣＭＣＩＡ）スロット及びカード等を含み得る。通信インタフェース４２４を介して転送されるソフトウエア及びデータは、通信インタフェース４２４によって受信されることが可能な電子的信号、電磁気的信号、光学的信号又は他の信号であってよい信号４２８の形態にある。これらの信号は通信パス（例えばチャネル）４２６を介して通信インタフェース４２４へ供給される。このチャネル４２６は信号を伝え、そしてワイヤ若しくはケーブル、光ファイバ、電話線、携帯電話リンク、ラジオ周波数（ＲＦ）リンク又は他の通信チャネルを用いて実装され得る。
【００４９】
この文書では、「コンピュータ可読記憶媒体」の用語は、リムーバブル記憶ドライブ４１４、及びハードディスクドライブ４１２内に組み込まれるハードディスクを一般的には参照して用いられる。これらのコンピュータプログラム製品は、コンピューティングシステム４００にソフトウエアを提供する。
【００５０】
コンピュータプログラム（コンピュータ制御論理又は命令とも称される）は主メモリ４０８及び／又は補助メモリ４１０内に記憶される。コンピュータプログラムはまた、リムーバブル記憶ドライブ４１４、ハードドライブ４１２又は通信インタフェース４２４を用いてコンピューティングシステム４００内へロードされてよい。そのようなコンピュータプログラムは、実行されるときに、ここで論じられるような本発明の実施形態の特徴をコンピューティングシステム４００が行うことを可能にする。例えばコンピュータプログラムは、実行されるときに、本発明の実施形態に従いテセレーションシェーダを処理ユニット４０４の少なくとも１つが実行することを可能にする。そのようなテセレーションシェーダの実行の例が以下に説明される。
【００５１】
IV．例示的なＧＰＵ
図５は本発明の実施形態に従いテセレーションシェーダを実行する例示的なＧＰＵ３１０のブロック図である。図５の実施形態に示されるように、ＧＰＵ３１０は、コマンドバッファ５０２に接続され、また入力論理５０４、実行ユニット５０６及びキャッシュ５０８に結合される。
【００５２】
入力論理５０４は、グラフィクス処理タスク及び一般計算タスクに前処理を行う。入力論理５０４は、グラフィクス処理タスク及び／又は一般計算タスクに関連する全てのシェーダプログラムを識別し、そして利用可能になるはずの入力データ及び出力データに基づいて各シェーダプログラムが実行ユニット５０６においていつ着手され得るのかをスケジューリングする。例えば、特定のグラフィクス処理タスクは第１のシェーダプログラム及び第２のシェーダプログラムの実行を必要とするであろうし、ここで第２のシェーダプログラムは第１のシェーダプログラムによって生成されるデータに依存する。この例に従うと、入力論理５０４は、第１及び第２のシェーダプログラムを識別すると共に第１のシェーダプログラムが第２のシェーダプログラムよりも先に実行されるようにスケジューリングし、その結果、第２のシェーダプログラムのためのデータは、第２のシェーダプログラムが着手されるときに利用可能になるはずである。グラフィクス処理タスク及び一般計算タスクを前処理した後に、入力論理５０４はこれらのタスクを実行ユニット５０６へ発行する。
【００５３】
実行ユニット５０６は、複数の計算資源（例えば単一命令多重データ（ＳＩＭＤ）デバイス）を含む。実行ユニット５０６によって実行されるべきタスクは、複数のワークロードへと分割されてよく、ここでワークロードは異なる計算資源（例えばＳＩＭＤ）へ並列に発行されてよい。入力論理５０４は、実行ユニット５０６内の異なる計算資源（例えばＳＩＭＤ）によってどのワークロードが処理されているのかの経過を追って、複数のスレッドが並列に実行されることを可能にする。ある実施形態においては、例えば、実行ユニット５０６内でどの時点においても３０，０００スレッドが実行され得る。実行ユニット５０６の動作の結果は出力バッファ（例えばフレームバッファ）へ送られる。出力バッファは、ＧＰＵ３１０と同じチップ内に含まれていてよく、あるいはオフチップメモリ内に含まれていてよい。
【００５４】
キャッシュ５０８は実行ユニット５０６によって頻繁に用いられるデータを記憶する。シェーダプログラムを実行するために実行ユニット５０６によってデータが必要とされると、先ず要求がキャッシュ５０８へと作成される。キャッシュ５０８内でキャッシュヒットがある（即ち要求されたデータがキャッシュ５０８内にある）場合、データは実行ユニット５０６内へ転送される。キャッシュ５０８内でキャッシュミスがある（即ち要求されたデータがキャッシュ５０８内にない）場合、要求されたデータはオフチップメモリからリトリーブされる。ある実施形態においては、キャッシュ５０８は１つ以上のレベル１（Ｌ１）キャッシュ及び１つ以上のレベル２（Ｌ２）キャッシュを備え、ここでＬ１キャッシュは、Ｌ２キャッシュよりも小さい記憶容量を有しているが、Ｌ２キャッシュよりも高速なデータアクセスを提供する。
【００５５】
統合化シェーダモデルにおいては、ＧＰＵはシェーダのシーケンスを実行する。これらのシェーダを実行するために、ＧＰＵは複数のＳＩＭＤを含む。各ＳＩＭＤはそれ自身のローカルデータストア（ＬＤＳ）と関連付けられている。各ＬＤＳは限定されたメモリ（例えば３２キロバイト）を有する。ＧＰＵが実行するシェーダの特定のシーケンスは、ＧＰＵが結合されているＡＰＩによってディクテートされる。典型的なシーケンスにおいては、ＧＰＵは頂点シェーダ、ハルシェーダ、そして続いてテセレーションシェーダを実行する。頂点シェーダ及びハルシェーダの実行の間、ＳＩＭＤは複数の頂点を受信して処理することができ、そしてその結果をそれが関連付けられているＬＤＳ内へ書き込むことになる。
【００５６】
１つの問題は、テセレーションシェーダを実行するために用いられるデータは頂点シェーダ及びハルシェーダを実行したＳＩＭＤのＬＤＳ内にあるから、頂点の所与のセットに対して、テセレーションシェーダは頂点シェーダ及びハルシェーダを実行する同じＳＩＭＤによって実装されるべきであることである。ＧＰＵがテセレーションシェーダをより速く実行することを可能にし得る他の利用可能な計算資源（例えば他のＳＩＭＤ）をＧＰＵが有していることがあるにもかかわらず、他の利用可能な計算資源は、必要なデータへのアクセスをそれらが有していないという理由で、用いられることができない。
【００５７】
この問題に対処するために、本発明の実施形態に従うＧＰＵ３１０は、図６に示されるように、テセレーションシェーダに対してオフチップＬＤＳ６２２（オフチップメモリ６２０の）又はオンチップＬＤＳ（ＧＰＵ３１０の）を動的に用いる。図６を参照すると、ＧＰＵ３１０の各ＳＩＭＤ６１０に対してミラー配置されたオフチップＬＤＳ６２２がある。入力論理５０４は、コマンドプロセッサ６０２（ＧＰＵ３１０によって実行されるべきグラフィクス処理タスク及び一般計算タスクを受信する）及び頂点解析器６０４（各シェーダプログラムが実行ユニット５０６内でいつ着手され得るのかをスケジューリングする）を含む。ＧＰＵ３１０の実行ユニット５０６は複数のＳＩＭＤ６１０Ａ〜６１０Ｎを含む。各ＳＩＭＤは複数のオンチップＬＤＳ６１２Ａ〜６１２Ｎの１つと関連付けられている。ハルシェーダ（ＨＳ）スレッドグループにおけるパッチに対して、ＨＳデータは、ＳＩＭＤ６１０に関連付けられるオンチップＬＤＳ６１２（テセレーションレベルが低い場合、例えば１００未満の頂点を伴う）又はオフチップＬＤＳ６２２（テセレーションレベルが高い場合、例えば１００を超える頂点を伴う）のいずれかに書き込まれ得る。ＨＳの末尾のコードは、ＨＳデータがオンチップＬＤＳ６１２又はオフチップＬＤＳ６２２のどちらに書き込まれるのかを決定する。ある実施形態においては、各オフチップＬＤＳ６２２はクワッドバッファされ(quad-buffered)ることによって、同じＳＩＭＤがスレッドグループと同数の４回動作することを可能にしている。
【００５８】
V．テセレーションエンジン
ある実施形態においては、ＧＰＵ３１０はテセレーションエンジンを含む。テセレーションエンジンは、パッチの各エッジに対するテセレーション係数(tessellation factor)に基づいてパッチをテセレートする。２つ、４つ又は６つのテセレーション係数がパッチ毎に存在し得る。これらの係数に基づいて、テセレーションエンジンは、テセレーショントポロジに基づいてパッチを多数の点、線、又は三角形に分割する。
【００５９】
例えば図９Ａ〜Ｃは例示的なパッチを示している。図９Ａ〜Ｃの例においては、パッチは長方形として図示されているが、これらは三角形、線、又は別の幾何学的形状であってもよい。図９Ａのパッチに対しては、ｖ方向に沿ったテセレーション係数は６であり、結果として点（０，０）と点（０，１）の間には６つの線分がもたらされる。図９Ｂのパッチに対しては、ｖ方向に沿ったテセレーション係数は５であり、結果として点（０，０）と点（０，１）の間には５つの線分がもたらされる。図９Ｃのパッチに対しては、ｖ方向に沿ったテセレーション係数は４であり、結果として点（０，０）と点（０，１）の間には４つの線分がもたらされる。同様に、図９Ａ〜Ｃの各々におけるパッチに対しては、ｕ方向に沿ったテセレーション係数は６であり、結果として点（０，０）と点（１，０）の間には６つの線分がもたらされる。
【００６０】
テセレーションエンジンは、スレッドグループの形態にあるワークを受信する。各スレッドグループは、パッチの数、テセレーション係数をフェッチする(fetch)ために用いられるテセレーション係数メモリ内への開始アドレス、及び他の状態情報を定義する。テセレーションエンジンは、入力スレッドグループからの各パッチを処理し、各パッチに対して必要としているテセレーション係数の数を要求し、そして種々の状態データ（区分(partition)、トポロジ、軸、等）に基づいてパッチをテセレートする。テセレーションエンジンは頂点データ及びプリミティブデータを出力する。テセレーションエンジンから生じる頂点データはｕ，ｖ値を備えている。
【００６１】
図７は本発明の実施形態に従うテセレーションエンジンの機能ブロックを示している。図７を参照すると、テセレーションエンジンは、スレッド・パッチモジュール(thread-to-patch module)７０２、前処理モジュール７０４、テセレーションモジュール７０６及び接続性モジュール７０８を含む。これらの機能ブロックの各々が以下に更に詳細に説明される。
【００６２】
Ａ．スレッド・パッチモジュール７０２
スレッド・パッチモジュール７０２はスレッドグループをパッチへ変換する。各スレッドグループはハルシェーダ（例えば図２のハルシェーダ２０４）からの入力として受信される。この変換は、（i）幾つのテセレーション係数を各パッチが必要としているか、（ii）パッチのための各係数に対するテセレーション係数メモリ内へのアドレス、及び（iii）頂点キャッシュ（ＶＣ）からの要求テセレーション係数、の決定を含む。要求されたテセレーション係数はパッチ毎に一緒にバッファリングされる。パッチのための全てのテセレーション係数、及び状態情報は、スレッドグループにおける各パッチに対して前処理モジュール７０４へと送られる。スレッド・パッチモジュール７０２はまた、スレッドグループの末尾及びパケットの末尾を標識付けるためにフラグを送る。
【００６３】
テセレーション係数は、テセレーションエンジンによってＩＥＥＥ浮動小数点フォーマットで受信される。しかし、テセレートするために用いられる演算操作(math operations)は固定小数点で処理される。従って、ハードウエアを効率的にするために、唯一の浮動・固定変換器があり、そして値はそれらがＶＣから１つずつ到着するときに変換される。ユニットはまた、０．０と６４．０の間の値へのテセレート係数のクランプを行う。
【００６４】
Ｂ．前処理モジュール７０４
前処理モジュール７０４は１度に１つのパッチを受信し、そしてそのパッチをテセレートするために用いられる値を事前計算する。即ち、ある実施形態においては、所与のパッチに対して、テセレーションモジュール７０６は、幾つかの数を繰り返し用いて、そのパッチに対するテセレーション点のパラメトリック位置を計算する。これらの数は、パッチの所与のエッジに対するテセレーション係数に基づいている。テセレーション係数のセットはパッチ毎に同じであるはずなので、前処理モジュールは、繰り返し用いられる数を計算することができ、またそれらをテセレーションモジュール７０６へ提供することができる。
【００６５】
前処理モジュール７０４によって実装され得る疑似コードが以下に挙げられている。しかし、この疑似コードは例示のみを目的とし且つ限定を目的としていないことが理解されるべきである。以下の疑似コードにおいては、太字の係数は、前処理モジュール７０４によって事前計算され、そして次いでテセレーションモジュール７０６に提供される係数である。
【００６６】
Ｃ．テセレーションモジュール７０６
テセレーションモジュール７０６は、前処理モジュール７０４からパッチ情報を受信し、そしてパッチのテセレートされる点の全てを作成する。テセレーションモジュール７０６とは異なり、ＤＸ１１アルゴリズムは、パッチ内のあらゆる点を計算し、そしてそれをメモリ内に、接続性パス(pass)の間に使用されるように記憶する。しかし、単一のパッチは最大で４，２２５個の点を有し得るので、これはハードウエアに対して効率的ではない。この問題に対処するために、テセレーションモジュール７０６は、パッチの部分を逐次的にテセレートして、テセレーション点がプリミティブ内へ接続されるかどうかが決定される順序で接続性モジュール７０８に提供される一連のテセレーション点を作成する。このように、ＤＸ１１アルゴリズムとは異なり、テセレーションモジュール７０６からのテセレーション点は、接続性モジュール７０８へ提供されるのに先立ちメモリ内に記憶される必要がない。
【００６７】
ある実施形態においては、テセレーションモジュール７０６は、パッチのエッジを並列に処理してテセレーション点を作成する２つの演算ユニット(math unit)を含む。例えば図８は、テセレーションモジュール７０６によって実装されるパイプラインの機能を示している。図８に示される機能は、図９Ａ〜９Ｃの例示的なパッチを参照して以下に説明される。
【００６８】
図８を参照すると、テセレーションモジュール７０６はステージ８０２においてパッチデータを受信する。上述したように、テセレーションモジュール７０６は、接続性モジュール７０８が適切な順序で出力プリミティブを作成することができるように、外側エッジ及び内側エッジに対するテセレーション点を並列に作成する。その際、外側エッジ制御ブロック８０８は受信したパッチの外側エッジを識別し、また内側エッジ制御ブロック８０４は受信したパッチの内側エッジを識別する。例えば、図９Ａにおけるパッチは外側エッジ９０１及び内側エッジ９０２を含む。テセレーションモジュール７０６は外側エッジ９０１及び内側エッジ９０２で開始して、そして下から上へと点を作成する。例えば、ステージ８１０及び８１２においてデータを段階付け(staging)た後、外側点計算ブロック８２０は外側エッジ９０１に沿ったテセレーション点を計算し、また内側点計算ブロック８１４は内側エッジ９０２に沿ったテセレーション点を計算する。外側エッジ９０１に対するテセレーション点は次いで一時的に８２４において段階付けられ、また内側エッジ９０２のテセレーション点は一時的に８２２において段階付けられる。外側点調節ブロック８２８及び内側点調節ブロック８２６は、それぞれ外側エッジ９０１及び内側エッジ９０２のテセレーション点のスキュー(skewing)を調節する。スキューは、内側エッジ上の点及び外側エッジ上の点が同じｖ座標（エッジが垂直の場合）又は同じｕ座標（エッジが水平の場合）で位置合わせされていない場合に生じる。テセレーション点は次いで、外側点ＦＩＦＯ８３２及び内側点ＦＩＦＯ８３０内にそれぞれ記憶される。接続性モジュール７０８は次いで、次のサブセクションで更に詳細に説明されるように、これらのＦＩＦＯからテセレーション点をリトリーブする。
【００６９】
パッチの左側の２つのエッジに沿ってテセレーション点を計算した後、テセレーションモジュール７０６は、パス(path)９０４によって示されるように、２つの上側エッジ上のテセレーション点を計算し、それにリングの右側と最後に下側が続く。外側リングが完了したら、処理は次の内側リングに対して繰り返す。リング制御ブロック８０６は、次の内側リングへの移行の処理を制御する。
【００７０】
図９Ａを参照すると、次の内側リングに対しては、エッジ９０２が外側エッジであり、またエッジ９０３が内側エッジである。内側点直交ブロック８１６は、直交値、即ち全エッジにわたって同じままの値を計算する。例えばエッジ９０２に沿ってｖ値は変化するが、ｕ値は変化しない。従ってエッジ９０２に沿ってｖ値は正則値であり、またｕ値は直交値である。これに対して、図９Ａにおけるパッチの上外側エッジに沿ってｕ値は変化するが、ｖ値は変化しない。従って上外側エッジに沿ってｕ値は正則値であり、またｖ値は直交値である。その結果、エッジ９０２に沿って、例えば、内側点計算ブロック８１４はｖ値０．８３３、０．６６６、０．５、０．３３３及び０．１６７（下から上へ）を提供する一方で、内側点直交計算ブロック８１６は全エッジに対して１つのｕ値０．１６７を提供する（エッジ９０２に沿ったｕ値は一定のままであるから）。
【００７１】
次のリングの処理の間、正則点値（即ちエッジに沿って変化する値）は再計算され、そして記憶されない。このことは、性能になんら問題を生じさせないし、また記憶ユニットを除去することによってハードウエア面積を低減する。一方、直交値（即ちエッジに沿って一定のままの値）は、直交ＦＩＦＯ８１８内に内側エッジから一時的に記憶され、そして外側エッジに用いられる。次の内側リングの処理の間（即ちエッジ９０２が外側エッジである場合）、外側点計算ブロック８２０はエッジ９０２に沿ってテセレーション点に対する正則点値を再計算し、また直交点値は直交値ＦＩＦＯ８１８からリトリーブされる。
【００７２】
パッチの全てのテセレーション点の計算は、パッチ内の全てのリングが処理されて完了する。点作成のこの処理は、図９Ａに示されるように蛇又は蛇紋のパターン(snake or serpentine pattern)を形成し、そして点はそれらが接続される順序で作成されるので、点の記憶をなんら必要とせず、このことは接続性モジュール７０８に関して後で更に詳細に説明される。点データの各片は、実行ユニット５０６が新たな頂点データを作成するために用いられるｕ，ｖ座標として索引付けられる。作成される各新たなプリミティブもまた、パッチＩＤでタグ付けされる。
【００７３】
点が異なる様態で作成される２つの特別な場合があり、図９Ｂ及び９Ｃに示されている。これら特別な場合の両方とも、パッチの最後のリングの間に生じる。図９Ｂを参照すると、第１の特別な場合は、パッチが多角形で終わる場合に生じる。これは最後のリングが内側エッジを有していないことを意味する。この場合、テセレーションモジュール７０６は、上側エッジ及び右側エッジを外側エッジ演算ユニット（例えば図８の機能ブロック８０８、８１２、８２０、８２４及び８２８）内で処理し、また左側エッジ及び下側エッジを内側演算ユニット（例えば図８の機能ブロック８０４、８１０、８１４、８２２及び８２６）内で処理する。これにより、次いでパッチの中央における三角形のグループとして接続され得る点のストリームが作成される。
【００７４】
図９Ｃを参照すると、他の特別な場合は、パッチが中央における線で終わる場合に生じる。この場合、中央における点は内側エッジ演算ユニット（例えば図８の機能ブロック８０４、８１０、８１４、８２２及び８２６）によって処理される。図９Ｃに示されるように、左から右に線が処理され、次いで向きを変えて右から左に点が再作成される（最も右側の点は除く）。線の同じ点を再使用する三角形が線の上方及び線の下方にあるであろうから、こうするものである。ある実施形態においては、線が１４点の長さより短い場合には、接続性モジュール７０８における再使用バッファは、繰り返された点が１回だけ実行ユニット５０６へ送られることを確実にする。
【００７５】
上述した特別な場合の両方とも、ｖ次元がｕ次元よりも大きい場合にも生じ得る。これは多角形又は線が水平の代わりに垂直であることを意味する。これは異なるエッジを演算ユニットにおいて処理させる。
【００７６】
Ｄ．接続性モジュール７０８
接続性モジュール７０８はテセレートされた点のデータをテセレーションモジュール７０６から受信し、そしてトポロジ（点、線、又は三角形）に基づいてプリミティブを作成する。接続性モジュール７０８は、頂点データをストリップフォーム(strip form)で送り出し、そしてプリミティブに対する相対的索引(relative indices)を送る。重要なことには、接続性モジュール７０８は、パッチのどのテセレーション点が、テセレーションモジュール７０６がテセレーション点を作成する順序で接続されることになるのかを決定し、このことが（上述したように）、ＤＸ１１アルゴリズムにおけるようにテセレーション点をメモリ内に記憶する必要性を回避している。
【００７７】
例えば図１３は、接続性モジュール７０８が図９Ａのパッチに対するテセレーション点の接続性を決定する例示的な順序を示している。即ち、接続性モジュール７０８は、テセレーション点を２つの外側エッジに沿って下から上へと処理する。図１３を参照すると、ある実施形態においては、接続性モジュール７０８は、（０，１）で表される頂点から開始して、そして（０，０）で表される頂点へと進む。例えば、接続性モジュール７０８は、頂点（０，１）、頂点１３０２及び頂点１３０４を、図１３において「１」で表される第１のプリミティブ（例えば三角形）に関連付けられるものとして識別してよい。同様に、接続性モジュール７０８は、頂点１３０２、頂点１３０４及び頂点１３０６を、図１３において「２」で表される第２のプリミティブ（例えば三角形）に関連付けられるものとして識別してよい。つまり、接続性モジュール７０８は、テセレーションモジュール７０６がパッチに対してテセレーション点を提供するのと同じ順序でテセレーション点がプリミティブ内へと接続されるかどうかを決定する。
【００７８】
接続性モジュール７０８は、テセレーション係数情報に基づいてアクセスされるルックアップテーブルのセットによって、出力頂点（即ちテセレーション点）の接続性を決定する。例えば、図１１は３２個のルックアップテーブルのセットを示しており、接続性モジュール７０８はこれらのルックアップテーブルから選択して頂点が接続されるかどうかを決定する。図１１を参照すると、左列はＬＵＴの番号を含み、また右列はＬＵＴを含む。
【００７９】
接続性モジュール７０８と異なり、ＤＸ１１アルゴリズムは３２エントリＬＵＴのみを用い、これは３１で表されるＬＵＴとして図１１に示されている。ＤＸ１１アルゴリズムに従うと、三角形がいつ作成され得るのかを決定するために、この１つのＬＵＴがループスルーされる(looped through)。ＤＸ１１におけるように１つのテーブルのみを用いることは、１つのプリミティブを作成するために最大で３２クロックを必要とし得ることを意味する。性能要求はクロックあたり１つのプリミティブを生成することであるから、これはハードウエアにとって極めて非効率的である。本発明の実施形態によると、図１１に示されるように１つのＬＵＴが３２個の別個のテーブルへと分割される。３２個のテーブルの１つを選択することによって、選択されたテーブルがループスルーされ得るし、そしてプリミティブは単一クロックサイクル内で作成され得る。
【００８０】
図１０は頂点が接続されるかどうかを決定するために接続性モジュール７０８によって実装される例示的な方法１０００を示している。図１０を参照すると、方法１０００はステップ１００２で開始し、複数のルックアップテーブルからルックアップテーブルが選択される。ある実施形態においては、ルックアップテーブルは、ハルシェーダ２０４によって提供されるテセレーション係数に基づいて選択される。特に、テセレーション係数は２で除され、「ハーフテス係数(half tess factor)」と称される数がもたらされ、そしてハーフテス係数がＬＵＴを選択するために用いられる。例えばテセレーション係数が１０であるとすると、ハーフテス係数は５であるから、５で表される図１１のＬＵＴ（エントリ｛４，２，５，１，６，３｝を含む）が選択されることになる。
【００８１】
再び図１０の方法１０００を参照すると、ステップ１００４では、選択されたルックアップテーブルに基づいてテセレーション点がプリミティブ内へと接続される。上述したように、図１３は頂点がどのようにしてプリミティブ内へと接続され得るのかを示している。
【００８２】
接続性モジュール７０８はまた、テセレーション点データを効率的な方法で提供する再使用論理を含む。テセレーションエンジンの再使用論理とは異なり、ＤＸ１１は、パッチの座標（即ちメモリ内に記憶される（ｕ，ｖ）値）への索引に基づいて再使用を処理する。ＤＸ１１が用いるメモリ内の索引は縮退している(degenerate)であろうし、このことは、パッチの点がメモリ内で一意的に索引付けられていないことを理由として、ＤＸ１１がテセレーション点データを２回以上送るであろうことを意味している。具体的には、テセレーション係数の幾つかの値と共に、ＤＸ１１のアルゴリズムは、エッジ上の多重点に対して同じパッチ座標（即ち（ｕ，ｖ）値）を生成する。しかし、ＤＸ１１はこれらの点を一意的なもとのみなしてそれらの全てを出力として送ってしまう。
【００８３】
これに対して、本発明の実施形態のテセレーションエンジンは、メモリの索引よりはむしろ、パッチの実際の座標（即ち実際の（ｕ，ｖ）値）に基づいて再使用を処理する。本発明の実施形態により指定されるように実際の座標を用いることは、ＤＸ１１アルゴリズムに起因して縮退三角形が形成される場合に役に立つ。
【００８４】
本発明の実施形態によると、テセレーションエンジンは第１の点を送り、そして任意の後続の点が第１の点と同じ座標（即ち（ｕ，ｖ）値）を有しているかどうかを決定する。テセレーションエンジンは、第１の点の座標を索引バッファ（例えば「パラメータキャッシュ」）内の点の座標と比較することによって、この決定をなす。ある実施形態においては、索引バッファは最大で１４点を記憶する。後続の点が第１の点と同じ座標（即ち（ｕ，ｖ）値）を有している場合には、テセレーションエンジンは後続の点を送らない。これによりシェーダ処理が節約される。
【００８５】
例えば図１２は、本発明の実施形態に従い頂点を再使用するために接続性モジュール７０８によって実装される例示的な方法１２００を示している。方法１２００はステップ１２０２で開始し、プリミティブの頂点はそれらのそれぞれの位置に従って索引付けられ、それらの位置はパッチ内の（ｕ，ｖ）値によって指定される。
【００８６】
グラフィクスパイプライン内の後続の処理に対して頂点を送るのに先立ち、ステップ１２０４に示されるように、その頂点に関連付けられている索引がバッファ内にあるかどうかが先ず決定される。ある実施形態においては、バッファは１４要素幅である。索引がバッファ内にある場合には、頂点は既にグラフィクスパイプラインへと送られているので、ステップ１２０６に示されるように、頂点はグラフィクスパイプライン内の後続の処理へは送られない。
【００８７】
一方、ステップ１２０４において索引がバッファ内にないと判断される場合には、ステップ１２０８に示されるように、グラフィクスパイプライン内の後続の処理に対して頂点が送られる。ステップ１２１０では、頂点に対する索引がバッファ内に置かれ、そして最も古い索引が、先入れ先出しのやり方でバッファからフラッシュされる(flushed)。
【００８８】
VI．例示的なソフトウエア実装
本発明の実施形態の処理ユニットのハードウエア実装（例えばＣＰＵ３０２及びＧＰＵ３１０）に加えて、そのような処理ユニットはまた、例えばソフトウエア（例えばコンピュータ可読プログラムコード）を記憶するように構成されるコンピュータ可読媒体内に配置されるソフトウエアにおいて具現化されてもよい。プログラムコードは、（i）ここに開示されるシステムの機能及び技術（例えば図７、８、１０及び１２に示される機能）、（ii）ここに開示されるシステムの製造及び技術（例えばＣＰＵ３０２及び／又はＧＰＵ３１０の製造）又は（iii）ここに開示されるシステムの機能及び製造並びに技術の組み合わせ、の実施形態を含めて本発明の実施形態の実施可能性を生じさせる。
【００８９】
このことは、例えば、一般的なプログラミング言語（例えばＣ又はＣ＋＋）、ベリログ(Verilog)ＨＤＬ、ＶＨＤＬ、アルテラ(Altera)ＨＤＬ（ＡＨＤＬ）等を含むハードウエア記述言語(hardware description languages)（ＨＤＬ）、あるいは他の利用可能なプログラミング及び／又は回路図等（schematic）キャプチャツール(capture tools)（例えば回路キャプチャツール）の使用を通して達成され得る。プログラムコードは、半導体、磁気ディスク、又は光学ディスク（例えばＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ）を含む任意の既知のコンピュータ可読媒体内に配置され得る。従って、コードは、インターネット及びそれと同等のもの(the Internet and internets)を含む通信ネットワークを介して伝送され得る。上述したシステム及び技術によって達成される機能及び／又は提供される構造は、プログラムコードにおいて具現化されるコア（例えばＣＰＵコア及び／又はＧＰＵコア）内で表現することができ、また集積回路の生産の一部としてハードウエアに変換されてよいことが理解される。
【００９０】
VII．結論
概要及び要約の欄ではなく詳細な説明の欄が特許請求の範囲を解釈するために用いられることを意図されていることが理解されるべきである。概要及び要約の欄は、発明者によって検討されているような本発明の１つ以上であるが全てではない例示的な実施形態を記述することができ、従って、本発明及び添付の特許請求の範囲を限定することを意図されるものでは決してない。
【技術分野】
【０００１】
本発明は概してコンピューティングシステムにおいて行われるコンピューティング動作に向けられている。より特定的には、本発明はコンピューティング動作を行う処理ユニット（例えばグラフィクス処理ユニット（ＧＰＵ））及びそのアプリケーションに向けられている。
【背景技術】
【０００２】
ＧＰＵは、グラフィクス処理タスク等のデータ並列コンピューティングタスクを行うように特別に設計される複雑な集積回路である。ＧＰＵは、例えば、ビデオゲームアプリケーション等のエンドユーザアプリケーションによって要求されるグラフィクス処理タスクを実行することができる。
【０００３】
図１はエンドユーザアプリケーション１０２とＧＰＵ１０８の間に何層ものソフトウエアが存在し得ることを示している。エンドユーザアプリケーション１０２は、アプリケーションプログラミングインタフェース（ＡＰＩ）１０４と通信する。ＡＰＩ１０４は、ＧＰＵ１０８に依存するフォーマットでよりはむしろ標準的なフォーマットでエンドユーザアプリケーション１０２がグラフィクスデータ及びコマンドを出力することを可能にする。ＡＰＩ１０４はドライバ１０６と通信する。ドライバ１０６は、ＡＰＩ１０４から受信した標準コードを、ＧＰＵ１０８によって理解されるネイティブフォーマットの命令にトランスレートする。ドライバ１０６は典型的にはＧＰＵ１０８の製造業者によって書かれる。ＧＰＵ１０８は次いでドライバからの命令を実行する。
【０００４】
様々なＡＰＩが商業的に利用可能である。エンドユーザアプリケーションの大部分は、ワシントン、レドモンドのマイクロソフト社(Microsoft Corporation of Redmond, Washington)によって開発されたダイレクトＸ(DirectX)（登録商標）に適合する。エンドユーザアプリケーションのこの大部分に広がるためには、ＧＰＵはダイレクトＸ（登録商標）に適合すべきである。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ダイレクトＸの最新バージョンはダイレクトＸ１１（「ＤＸ１１」）として知られている。ＤＸ１１は、ＧＰＵがシェーダのシーケンスを実装している統合化シェーダモデルを用いる。例えば、図２はＤＸ１１によって指定されるシェーダ２００の例示的なシーケンスを示している。図２に示されるように、ＧＰＵは、頂点シェーダ(vertex shader)２０２、次いでハルシェーダ(hull shader)２０４、次いでテセレーションシェーダ(tessellation shader)２０６、そしてその後に１つ以上の追加シェーダ２０８を実行して結果データを提供する。統合化シェーダモデルにおいては、先に実行されたシェーダ（例えばハルシェーダ２０４）によって提供される中間結果は、ＧＰＵが後続のシェーダ（例えばテセレーションシェーダ２０６）を実行するために用いられ得る。残念なことに、ＤＸ１１は、ＧＰＵハードウエア視点からは最適ではないスキームを含んでいる。
【０００６】
従って、ＤＸ１１に適合するだけでなく、ＧＰＵハードウエア視点からも効率的に動作するシステム、装置及び方法が必要とされている。
【課題を解決するための手段】
【０００７】
本発明の実施形態は、上述の必要性を満たす。例えば、本発明の実施形態は、処理ユニット内に実装されるグラフィクス処理方法を提供する。このグラフィクス処理方法は、幾何学的形状の部分を逐次的にテセレートして幾何学的形状に対する一連のテセレーション点を提供することを含む。このグラフィクス処理方法は更に、テセレーション点の１つ以上のグループを一連のテセレーション点が提供される順序で１つ以上のプリミティブ内へと接続することを含む。
【０００８】
本発明の別の実施形態は、テセレーションモジュール及び接続性モジュールを含む処理ユニットを提供する。テセレーションモジュールは、幾何学的形状の部分を逐次的にテセレートして幾何学的形状に対する一連のテセレーション点を提供するように構成される。接続性モジュールは、テセレーション点の１つ以上のグループを一連のテセレーション点が提供される順序で１つ以上のプリミティブ内へと接続するように構成される。
【０００９】
本発明の更なる実施形態は、システムメモリと、処理ユニットと、システムメモリ及び処理ユニットに結合されるバスと、を含むコンピューティングシステムを提供する。処理ユニットは、テセレーションモジュール及び接続性モジュールを含む。テセレーションモジュールは、幾何学的形状の部分を逐次的にテセレートして幾何学的形状に対する一連のテセレーション点を提供するように構成される。接続性モジュールは、テセレーション点の１つ以上のグループを一連のテセレーション点が提供される順序で１つ以上のプリミティブ内へと接続するように構成される。
【００１０】
本発明の更なる特徴及び利点の他、本発明の種々の実施形態の構成及び動作は、添付の図面を参照して以下に詳細に説明される。尚、本発明はここに説明される特定の実施形態に限定されない。そのような実施形態は例示の目的のみのためにここに提示されている。追加的な実施形態はここに含まれる教示に基き関連分野を含めた当業者にとって明らかであろう。
【図面の簡単な説明】
【００１１】
ここに組み込まれ且つ出願書類の一部をなす添付の図面は本発明を示し、そして明細書と共に、本発明の原理を説明すること及び関連分野を含めた当業者が本発明を作りそして使用するのを可能にすることに更に役立つ。
【００１２】
【図１】図１はグラフィクスを処理するための例示的なワークフローを示すブロック図である。
【００１３】
【図２】図２は例示的な３次元グラフィクスＡＰＩのグラフィクスパイプラインに含まれる例示的なシェーダを示す図である。
【００１４】
【図３】図３は本発明の実施形態に従う例示的なコンピューティングシステムのブロック図である。
【００１５】
【図４】図４は本発明の実施形態に従う例示的なコンピューティングシステムに含まれる追加的な要素を示す図である。
【００１６】
【図５】図５は本発明の実施形態に従う例示的なＧＰＵのブロック図である。
【００１７】
【図６】図６は図５のＧＰＵの追加的な詳細のブロック図である。
【００１８】
【図７】図７は本発明の実施形態に従いテセレーションシェーダを実行するための処理ユニットの例示的な機能ブロックを示す図である。
【００１９】
【図８】図８は本発明の実施形態に従い図７のテセレーションモジュールによって実装される、テセレーション点を作成するための例示的な方法を示す図である。
【００２０】
【図９Ａ】図９Ａは本発明の実施形態に従いパッチのテセレーション点を作成するための例示的なシーケンスを示す図（その１）である。
【図９Ｂ】図９Ｂは本発明の実施形態に従いパッチのテセレーション点を作成するための例示的なシーケンスを示す図（その２）である。
【図９Ｃ】図９Ｃは本発明の実施形態に従いパッチのテセレーション点を作成するための例示的なシーケンスを示す図（その３）である。
【００２１】
【図１０】図１０は本発明の実施形態に従い図７の接続性モジュールによって実装される、テセレーション点をプリミティブ内へと接続するための例示的な方法を示す図である。
【００２２】
【図１１】図１１は本発明の実施形態に従い接続性を決定するために用いられる例示的なルックアップテーブル（ＬＵＴ）を示す図である。
【００２３】
【図１２】図１２は本発明の実施形態に従い図７の接続性モジュールによって実装される、プリミティブの頂点を再使用するための例示的な方法を示す図である。
【００２４】
【図１３】図１３は本発明の実施形態に従い図９Ａのテセレーション点がどのようにしてプリミティブ内へと接続され得るのかを示す図である。
【００２５】
本発明の特徴及び利益は、図面と共に以下に記述される詳細な説明からより明らかになり、図面において同様の参照番号は全体を通して対応する要素を識別する。図面において、同様の参照数字は一般的に同一の、機能的に類似の、及び／又は構造的に類似の要素を示す。ある要素が最初に現れる図面は対応する参照番号の一番左の単一又は複数の桁によって示される。
【発明を実施するための形態】
【００２６】
I．概説
本発明のある実施形態は、テセレーションエンジンを伴う処理ユニット及びそのアプリケーションを提供する。以下の詳細な説明において、「１つの実施形態」、「ある実施形態」、「例示的実施形態」等に対する言及は、説明される実施形態が特定の特徴、構造又は特性を含んでいてよいが、全ての実施形態が必ずしも当該特定の特徴、構造又は特性を含む必要がなくてよいことを示している。また、そのような表現は必ずしも同じ実施形態を参照しているとは限らない。更に、特定の特徴、構造又は特性がある実施形態に関連して説明されている場合には、明示的に説明されていようとなかろうと、他の実施形態に関連して当該特定の特徴、構造又は特性を具現化することは当業者の知識の範囲内にあることと言える。
【００２７】
図２に関して上述したように、典型的なグラフィクスパイプラインは複数のシェーダを含み、これらのシェーダはテセレーションシェーダ２０６を含む。テセレーションシェーダ２０６への入力は、パッチ(patch)、即ち幾何学的形状（例えば長方形、三角形、又は線）を含む。テセレーションシェーダ２０６の１つの目的は、パッチを複数の点へとテセレートする(tessellate)ことである。グラフィクスパイプラインの後続の段階の間、これらの点は更なる処理を被るであろう。例えば、これらの点はプリミティブ(primitives)（例えば三角形）内へと接続されることがある。本発明の実施形態に従う処理ユニットは、ハードウエア視点からテセレーションシェーダ２０６を効率的に実行するように構成されるテセレーションエンジンを含むことにより、従来の処理ユニットと比べて低減された面積のフットプリント(footprint)と共により良好な性能（例えばより高速な処理）を提供する。
【００２８】
例示のみを目的とし且つ限定を目的とせずに、本発明の実施形態はＧＰＵに関してここに説明されることになる。しかし、関連分野を含めた当業者であれば、本発明はテセレーションシェーダを実行する他の種類の処理ユニット、例えば中央処理ユニット及びコプロセッサ、にも適用され得ることを理解するであろう。これら他の種類のプロセッサは本発明の精神及び範囲内で検討される。
【００２９】
本発明の実施形態によると、ＧＰＵは、テセレーションシェーダの実行及びそのアプリケーションに対してオフチップメモリ及びオンチップメモリを動的に用いる。オフチップメモリはオフチップローカルデータシェア（ＬＤＳ）と称され、そしてオンチップメモリはオンチップＬＤＳと称される。テセレーションが低い場合（例えば１００未満の頂点が関与する場合）には、オンチップＬＤＳが用いられる。テセレーションが高い場合（例えば１００を超える頂点が関与する場合）には、オフチップＬＤＳが用いられる。ＧＰＵドライバは、レジスタ書き込み（例えば１ビット）を通して、オンチップＬＤＳ又はオフチップＬＤＳのどちらが用いられるのかを表示する。テセレーション出力に対してオンチップＬＤＳ又はオフチップＬＤＳのどちらを用いるかの決定は、動的になされる。
【００３０】
本発明の別の実施形態は、ＤＸ１１によって指定されるスキームに適合する一方でＤＸ１１によって指定されるスキームよりもハードウエア視点からは効率的な方法でＧＰＵがテセレーションのための点を生成することを可能にするテセレーションエンジンに向けられている。上述したように、テセレーションは、パッチ上、即ち幾何学的形状（例えば長方形、三角形、又は線）上で実行される。ＧＰＵのテセレーションエンジンは、パッチをテセレートして、接続性エンジン(connectivity engine)がテセレーション点を接続するように構成される順序でテセレーション点を提供するように構成される。対照的に、ＤＸ１１アルゴリズムは、全てのテセレーション点を作成すると共にテセレーション点をメモリ内に記憶し、次いで接続性処理の間にこれらのテセレーション点をメモリからリトリーブする（retrieves)。ＤＸ１１アルゴリズムとは異なり、本発明の実施形態のテセレーションエンジンは、テセレーション点をメモリ内に記憶する必要はなく、その理由は、テセレーションエンジンはそれらが接続性エンジンにおいて処理される順序で生成されるところにある。
【００３１】
ある実施形態においては、テセレーションエンジンは、テセレーション点を作成する２つの演算ユニット(math units)を含む。第１の演算ユニットはパッチの外側エッジに対する点を作成するように構成され、また第２の演算ユニットはそのパッチの内側エッジに対する点を作成するように構成される。各演算ユニットは出力ＦＩＦＯ及び入力ＦＩＦＯを含む。出力ＦＩＦＯは２つの読み出し点を有しており、２つの点がクロックサイクル毎に読み出されることを可能にしている。結果として、テセレーションエンジンの２つの演算ユニットは、単一クロックサイクル内でプリミティブ（例えば三角形）の点を作成することができる。数クロックサイクルの後、テセレーションエンジンは、蛇紋路(serpentine path)を辿ることによってパッチの全ての点を作成する。このようにして、パッチの点は後続の接続性処理に対して適切な方法によりオンザフライ(on the fly)で作成されるが、ＤＸ１１によって指定されるようにメモリがパッチの全ての点を記憶する必要はない。
【００３２】
本発明の更なる実施形態は、固有のテセレートされた点のデータ(unique tessellated-point data)のみを提供するＧＰＵ及びそのアプリケーションに向けられており、それにより処理資源を節約している。ある実施形態においては、ＧＰＵはテセレーションモジュール及び接続性モジュールを含む。テセレーションモジュールはテセレートされた点のデータを接続性モジュールへ提供する。接続性モジュールは、テセレートされた点のデータのトポロジ（例えば点、線、又は三角形）に基づいてプリミティブを作成する。接続性モジュールはデータをストリップフォーム(strip form)で送り出し、そしてプリミティブに対する相対的索引(relative indices)を送る。
【００３３】
本発明の更なる実施形態は、複数のルックアップテーブル（ＬＵＴ）からＬＵＴを選択してパッチのテセレーション点が接続されているかどうかを決定するテセレーションエンジン及びそのアプリケーションに向けられている。複数のＬＵＴから１つのＬＵＴを選択することによって、本発明の実施形態のテセレーションレーションエンジンは、クロックサイクル毎に１つのプリミティブを提供することができる。対照的に、ＤＸ１１によって指定される単一ＬＵＴを用いることは、プリミティブを提供するために最大で３２クロックサイクルを必要とすることがある。
【００３４】
本発明の実施形態に従う例示的なテセレーションエンジンの更なる詳細が以下に説明される。しかし、これらの詳細を提供するのに先立ちそのようなテセレーションエンジンが実装され得る例示的なシステムを説明することは有用である。
【００３５】
II．例示的なシステム
図３はある実施形態に従うコンピューティングシステム３００のブロック図である。コンピューティングシステム３００は、ＣＰＵ３０２、ＧＰＵ３１０を含み、そして随意的にコプロセッサ３１２を含んでいてよい。図３に示される実施形態においては、ＣＰＵ３０２及びＧＰＵ３１０は別個の集積回路（ＩＣ）又はパッケージに含まれている。しかし、他の実施形態においては、ＣＰＵ３０２及びＧＰＵ３１０、又はそれらの集合的な機能は、単一のＩＣ又はパッケージ内に含まれていてよい。
【００３６】
加えて、コンピューティングシステム３００はまた、ＣＰＵ３０２、ＧＰＵ３１０及びコプロセッサ３１２によってアクセスされてよいシステムメモリ３０４を含む。実施形態においては、コンピューティングシステム３００は、スーパーコンピュータ、デスクトップコンピュータ、ラップトップコンピュータ、ビデオゲームコンソール、埋め込みデバイス、携帯デバイス（例えば携帯電話、スマートフォン、ＭＰ３プレイヤ、カメラ、ＧＰＳデバイス等）、又はＧＰＵを含み若しくはＧＰＵを含むように構成される何らかの他のデバイスを備えていてよい。図３には具体的に示されていないが、コンピューティングシステム３００は、コンピューティングシステム３００のコンテンツ（例えばグラフィクス、ビデオ等）を表示するためのディスプレイデバイス（例えば陰極線管、液晶ディスプレイ、プラズマディスプレイ等）を含んでいてもよい。ディスプレイデバイスは、コンテンツをユーザに表示するために用いられる（例えば、コンピューティングシステム３００がコンピュータ、ビデオゲームコンソール又は携帯デバイスを備えている場合）。
【００３７】
ＧＰＵ３１０は、特定の特別の機能（例えばグラフィクス処理タスク及びデータ並列一般計算タスク）を、ＣＰＵ３０２がソフトウエアにおいてそれらを行い得るであろうよりも通常は高速に行うことによって、ＣＰＵ３０２を支援する。実施形態においては、ＧＰＵ３１０はチップセット及び／又はＣＰＵ３０２若しくは他のプロセッサ内に集積化されていてよい。ＧＰＵ３１０の追加的な詳細は後で提供される。
【００３８】
コプロセッサ３１２もまたＣＰＵ３０２を支援する。コプロセッサ３１２は、限定はされないが、浮動小数点コプロセッサ、ＧＰＵ、ビデオ処理ユニット（ＶＰＵ）、ネットワーキングコプロセッサ、並びに関連する分野を含めて当業者に明らかであろうような他の種類のコプロセッサ及びプロセッサを備えていてよい。
【００３９】
ＧＰＵ３１０及びコプロセッサ３１２は、ＣＰＵ３０２及びシステムメモリとバス３１４を介して通信する。バス３１４は、周辺要素インタフェース(peripheral component interface)（ＰＣＩ）バス、アクセラレーテッドグラフィクスポート(accelerated graphics port)（ＡＧＰ）バス、ＰＣＩエクスプレス(PCI Express)（ＰＣＩＥ）バス、又は現在利用可能であり若しくは将来開発される別の種類のバスを含めてコンピュータシステムにおいて用いられる任意の種類のバスであってよい。
【００４０】
システムメモリ３０４に加えて、コンピューティングシステム３００はローカルメモリ３０６及びローカルメモリ３０８を更に含む。ローカルメモリ３０６はＧＰＵ３１０に結合されており、またバス３１４に結合されていてもよい。ローカルメモリ３０８はコプロセッサ３１２に結合されており、またバス３１４に結合されていてもよい。ローカルメモリ３０６及び３０８は、特定のデータ（例えば頻繁に用いられるデータ）への、そのデータがシステムメモリ３０４内に記憶されていたとした場合に可能であろうよりも高速なアクセスを提供するために、それぞれＧＰＵ３１０及びコプロセッサ３１２に利用可能である。
【００４１】
ある実施形態においては、ＧＰＵ３１０及びコプロセッサ３１２は、ＣＰＵ３０２と並列に命令をデコードし、そしてそれらを対象としている命令のみを実行する。別の実施形態においては、ＧＰＵ３１０及びコプロセッサ３１２を対象としている命令をＣＰＵ３０２がそれぞれのコマンドバッファへ送る。
【００４２】
図３には具体的に示されていないが、コンピューティングシステム３００は、ディスプレイデバイス（例えば陰極線管、液晶ディスプレイ、プラズマディスプレイ等）を含み又はディスプレイデバイスに接続されていてもよい。ディスプレイデバイスは、コンテンツをユーザに表示するために用いられる（例えば、コンピューティングシステム３００がコンピュータ、ビデオゲームコンソール又は携帯デバイスを備えている場合）。
【００４３】
III．例示的なコンピューティングシステムの追加的な詳細
上述したように、図３は本発明の実施形態の例示的なコンピューティングシステム３００を示している。図４は本発明の実施形態に従い例示的なコンピューティングシステム４００に含まれてよい追加的な要素を示している。
【００４４】
コンピューティングシステム４００は１つ以上の処理ユニット４０４を含む。処理ユニット４０４は汎用処理ユニット（例えば図３のＣＰＵ３０２）又は専用処理ユニット（例えば図３のＧＰＵ３１０）であってよい。処理ユニット４０４は通信基盤４０６（例えば通信バス（例えば図３のバス３１４）、クロスオーバーバー又はネットワーク）に接続される。
【００４５】
コンピューティングシステム４００はまた、通信基盤４０６からの（又は図示しないフレームバッファからの）グラフィクスデータ、テキストデータ及び他のデータをディスプレイユニット４３０（例えば液晶ディスプレイ）上での表示のために転送するディスプレイインタフェース４０２を含む。
【００４６】
コンピューティングシステム４００はまた、図３のシステムメモリ３０４等の主メモリ４０８、望ましくはランダムアクセスメモリ（ＲＡＭ）を含む。加えてコンピューティングシステム４００は、補助メモリ４１０を含んでいてもよい。補助メモリ４１０は例えば、ハードディスクドライブ４１２及び／又はリムーバブル記憶ドライブ４１４を含んでいてよく、フロッピー（登録商標）ディスクドライブ、磁気テープドライブ、光学ディスクドライブ等を代表する。リムーバブル記憶ドライブ４１４は周知の方法でリムーバブル記憶ユニット４１８から読み出し且つ／又はリムーバブル記憶ユニット４１８へ書き込みする。リムーバブル記憶ユニット４１８はフロッピー（登録商標）ディスク、磁気テープ、光学ディスク等を代表し、リムーバブル記憶ドライブ４１４によって読み出され且つ書き込まれる。理解されるであろうように、リムーバブル記憶ユニット４１８はコンピュータソフトウエア及び／又はデータが既に記憶されたコンピュータ可読記憶媒体を含む。
【００４７】
代替的な実装においては、補助メモリ４１０は、コンピュータプログラム又は他の命令がコンピュータシステム４００にロードされることを可能にするための他の同様のデバイスを含んでいてよい。そのようなデバイスは例えばリムーバブル記憶ユニット４２２及びインタフェース４２０を含み得る。そのような例は、プログラムカートリッジ及びカートリッジインタフェース（ビデオゲームデバイスにおいて見られるようなもの）、リムーバブルメモリチップ（例えば消去可能プログラム可能リードオンリメモリ（ＥＰＲＯＭ）又はプログラム可能リードオンリメモリ（ＰＲＯＭ））及び関連するソケット、並びにソフトウエア及びデータがリムーバブル記憶ユニット４２２からコンピューティングシステム４００へ転送されることを可能にする他のリムーバブル記憶ユニット４２２及びインタフェース４２０を含み得る。
【００４８】
コンピューティングシステム４００はまた通信インタフェース４２４を含んでいてよい。通信インタフェース４２４は、ソフトウエア及びデータがコンピューティングシステム４００と外部デバイスの間で転送されることを可能にする。通信インタフェース４２４の例は、モデム、ネットワークインタフェース（例えばイーサネット（登録商標）カード）、通信ポート、パーソナルコンピュータメモリカード国際協会(Personal Computer Memory Card International Association)（ＰＣＭＣＩＡ）スロット及びカード等を含み得る。通信インタフェース４２４を介して転送されるソフトウエア及びデータは、通信インタフェース４２４によって受信されることが可能な電子的信号、電磁気的信号、光学的信号又は他の信号であってよい信号４２８の形態にある。これらの信号は通信パス（例えばチャネル）４２６を介して通信インタフェース４２４へ供給される。このチャネル４２６は信号を伝え、そしてワイヤ若しくはケーブル、光ファイバ、電話線、携帯電話リンク、ラジオ周波数（ＲＦ）リンク又は他の通信チャネルを用いて実装され得る。
【００４９】
この文書では、「コンピュータ可読記憶媒体」の用語は、リムーバブル記憶ドライブ４１４、及びハードディスクドライブ４１２内に組み込まれるハードディスクを一般的には参照して用いられる。これらのコンピュータプログラム製品は、コンピューティングシステム４００にソフトウエアを提供する。
【００５０】
コンピュータプログラム（コンピュータ制御論理又は命令とも称される）は主メモリ４０８及び／又は補助メモリ４１０内に記憶される。コンピュータプログラムはまた、リムーバブル記憶ドライブ４１４、ハードドライブ４１２又は通信インタフェース４２４を用いてコンピューティングシステム４００内へロードされてよい。そのようなコンピュータプログラムは、実行されるときに、ここで論じられるような本発明の実施形態の特徴をコンピューティングシステム４００が行うことを可能にする。例えばコンピュータプログラムは、実行されるときに、本発明の実施形態に従いテセレーションシェーダを処理ユニット４０４の少なくとも１つが実行することを可能にする。そのようなテセレーションシェーダの実行の例が以下に説明される。
【００５１】
IV．例示的なＧＰＵ
図５は本発明の実施形態に従いテセレーションシェーダを実行する例示的なＧＰＵ３１０のブロック図である。図５の実施形態に示されるように、ＧＰＵ３１０は、コマンドバッファ５０２に接続され、また入力論理５０４、実行ユニット５０６及びキャッシュ５０８に結合される。
【００５２】
入力論理５０４は、グラフィクス処理タスク及び一般計算タスクに前処理を行う。入力論理５０４は、グラフィクス処理タスク及び／又は一般計算タスクに関連する全てのシェーダプログラムを識別し、そして利用可能になるはずの入力データ及び出力データに基づいて各シェーダプログラムが実行ユニット５０６においていつ着手され得るのかをスケジューリングする。例えば、特定のグラフィクス処理タスクは第１のシェーダプログラム及び第２のシェーダプログラムの実行を必要とするであろうし、ここで第２のシェーダプログラムは第１のシェーダプログラムによって生成されるデータに依存する。この例に従うと、入力論理５０４は、第１及び第２のシェーダプログラムを識別すると共に第１のシェーダプログラムが第２のシェーダプログラムよりも先に実行されるようにスケジューリングし、その結果、第２のシェーダプログラムのためのデータは、第２のシェーダプログラムが着手されるときに利用可能になるはずである。グラフィクス処理タスク及び一般計算タスクを前処理した後に、入力論理５０４はこれらのタスクを実行ユニット５０６へ発行する。
【００５３】
実行ユニット５０６は、複数の計算資源（例えば単一命令多重データ（ＳＩＭＤ）デバイス）を含む。実行ユニット５０６によって実行されるべきタスクは、複数のワークロードへと分割されてよく、ここでワークロードは異なる計算資源（例えばＳＩＭＤ）へ並列に発行されてよい。入力論理５０４は、実行ユニット５０６内の異なる計算資源（例えばＳＩＭＤ）によってどのワークロードが処理されているのかの経過を追って、複数のスレッドが並列に実行されることを可能にする。ある実施形態においては、例えば、実行ユニット５０６内でどの時点においても３０，０００スレッドが実行され得る。実行ユニット５０６の動作の結果は出力バッファ（例えばフレームバッファ）へ送られる。出力バッファは、ＧＰＵ３１０と同じチップ内に含まれていてよく、あるいはオフチップメモリ内に含まれていてよい。
【００５４】
キャッシュ５０８は実行ユニット５０６によって頻繁に用いられるデータを記憶する。シェーダプログラムを実行するために実行ユニット５０６によってデータが必要とされると、先ず要求がキャッシュ５０８へと作成される。キャッシュ５０８内でキャッシュヒットがある（即ち要求されたデータがキャッシュ５０８内にある）場合、データは実行ユニット５０６内へ転送される。キャッシュ５０８内でキャッシュミスがある（即ち要求されたデータがキャッシュ５０８内にない）場合、要求されたデータはオフチップメモリからリトリーブされる。ある実施形態においては、キャッシュ５０８は１つ以上のレベル１（Ｌ１）キャッシュ及び１つ以上のレベル２（Ｌ２）キャッシュを備え、ここでＬ１キャッシュは、Ｌ２キャッシュよりも小さい記憶容量を有しているが、Ｌ２キャッシュよりも高速なデータアクセスを提供する。
【００５５】
統合化シェーダモデルにおいては、ＧＰＵはシェーダのシーケンスを実行する。これらのシェーダを実行するために、ＧＰＵは複数のＳＩＭＤを含む。各ＳＩＭＤはそれ自身のローカルデータストア（ＬＤＳ）と関連付けられている。各ＬＤＳは限定されたメモリ（例えば３２キロバイト）を有する。ＧＰＵが実行するシェーダの特定のシーケンスは、ＧＰＵが結合されているＡＰＩによってディクテートされる。典型的なシーケンスにおいては、ＧＰＵは頂点シェーダ、ハルシェーダ、そして続いてテセレーションシェーダを実行する。頂点シェーダ及びハルシェーダの実行の間、ＳＩＭＤは複数の頂点を受信して処理することができ、そしてその結果をそれが関連付けられているＬＤＳ内へ書き込むことになる。
【００５６】
１つの問題は、テセレーションシェーダを実行するために用いられるデータは頂点シェーダ及びハルシェーダを実行したＳＩＭＤのＬＤＳ内にあるから、頂点の所与のセットに対して、テセレーションシェーダは頂点シェーダ及びハルシェーダを実行する同じＳＩＭＤによって実装されるべきであることである。ＧＰＵがテセレーションシェーダをより速く実行することを可能にし得る他の利用可能な計算資源（例えば他のＳＩＭＤ）をＧＰＵが有していることがあるにもかかわらず、他の利用可能な計算資源は、必要なデータへのアクセスをそれらが有していないという理由で、用いられることができない。
【００５７】
この問題に対処するために、本発明の実施形態に従うＧＰＵ３１０は、図６に示されるように、テセレーションシェーダに対してオフチップＬＤＳ６２２（オフチップメモリ６２０の）又はオンチップＬＤＳ（ＧＰＵ３１０の）を動的に用いる。図６を参照すると、ＧＰＵ３１０の各ＳＩＭＤ６１０に対してミラー配置されたオフチップＬＤＳ６２２がある。入力論理５０４は、コマンドプロセッサ６０２（ＧＰＵ３１０によって実行されるべきグラフィクス処理タスク及び一般計算タスクを受信する）及び頂点解析器６０４（各シェーダプログラムが実行ユニット５０６内でいつ着手され得るのかをスケジューリングする）を含む。ＧＰＵ３１０の実行ユニット５０６は複数のＳＩＭＤ６１０Ａ〜６１０Ｎを含む。各ＳＩＭＤは複数のオンチップＬＤＳ６１２Ａ〜６１２Ｎの１つと関連付けられている。ハルシェーダ（ＨＳ）スレッドグループにおけるパッチに対して、ＨＳデータは、ＳＩＭＤ６１０に関連付けられるオンチップＬＤＳ６１２（テセレーションレベルが低い場合、例えば１００未満の頂点を伴う）又はオフチップＬＤＳ６２２（テセレーションレベルが高い場合、例えば１００を超える頂点を伴う）のいずれかに書き込まれ得る。ＨＳの末尾のコードは、ＨＳデータがオンチップＬＤＳ６１２又はオフチップＬＤＳ６２２のどちらに書き込まれるのかを決定する。ある実施形態においては、各オフチップＬＤＳ６２２はクワッドバッファされ(quad-buffered)ることによって、同じＳＩＭＤがスレッドグループと同数の４回動作することを可能にしている。
【００５８】
V．テセレーションエンジン
ある実施形態においては、ＧＰＵ３１０はテセレーションエンジンを含む。テセレーションエンジンは、パッチの各エッジに対するテセレーション係数(tessellation factor)に基づいてパッチをテセレートする。２つ、４つ又は６つのテセレーション係数がパッチ毎に存在し得る。これらの係数に基づいて、テセレーションエンジンは、テセレーショントポロジに基づいてパッチを多数の点、線、又は三角形に分割する。
【００５９】
例えば図９Ａ〜Ｃは例示的なパッチを示している。図９Ａ〜Ｃの例においては、パッチは長方形として図示されているが、これらは三角形、線、又は別の幾何学的形状であってもよい。図９Ａのパッチに対しては、ｖ方向に沿ったテセレーション係数は６であり、結果として点（０，０）と点（０，１）の間には６つの線分がもたらされる。図９Ｂのパッチに対しては、ｖ方向に沿ったテセレーション係数は５であり、結果として点（０，０）と点（０，１）の間には５つの線分がもたらされる。図９Ｃのパッチに対しては、ｖ方向に沿ったテセレーション係数は４であり、結果として点（０，０）と点（０，１）の間には４つの線分がもたらされる。同様に、図９Ａ〜Ｃの各々におけるパッチに対しては、ｕ方向に沿ったテセレーション係数は６であり、結果として点（０，０）と点（１，０）の間には６つの線分がもたらされる。
【００６０】
テセレーションエンジンは、スレッドグループの形態にあるワークを受信する。各スレッドグループは、パッチの数、テセレーション係数をフェッチする(fetch)ために用いられるテセレーション係数メモリ内への開始アドレス、及び他の状態情報を定義する。テセレーションエンジンは、入力スレッドグループからの各パッチを処理し、各パッチに対して必要としているテセレーション係数の数を要求し、そして種々の状態データ（区分(partition)、トポロジ、軸、等）に基づいてパッチをテセレートする。テセレーションエンジンは頂点データ及びプリミティブデータを出力する。テセレーションエンジンから生じる頂点データはｕ，ｖ値を備えている。
【００６１】
図７は本発明の実施形態に従うテセレーションエンジンの機能ブロックを示している。図７を参照すると、テセレーションエンジンは、スレッド・パッチモジュール(thread-to-patch module)７０２、前処理モジュール７０４、テセレーションモジュール７０６及び接続性モジュール７０８を含む。これらの機能ブロックの各々が以下に更に詳細に説明される。
【００６２】
Ａ．スレッド・パッチモジュール７０２
スレッド・パッチモジュール７０２はスレッドグループをパッチへ変換する。各スレッドグループはハルシェーダ（例えば図２のハルシェーダ２０４）からの入力として受信される。この変換は、（i）幾つのテセレーション係数を各パッチが必要としているか、（ii）パッチのための各係数に対するテセレーション係数メモリ内へのアドレス、及び（iii）頂点キャッシュ（ＶＣ）からの要求テセレーション係数、の決定を含む。要求されたテセレーション係数はパッチ毎に一緒にバッファリングされる。パッチのための全てのテセレーション係数、及び状態情報は、スレッドグループにおける各パッチに対して前処理モジュール７０４へと送られる。スレッド・パッチモジュール７０２はまた、スレッドグループの末尾及びパケットの末尾を標識付けるためにフラグを送る。
【００６３】
テセレーション係数は、テセレーションエンジンによってＩＥＥＥ浮動小数点フォーマットで受信される。しかし、テセレートするために用いられる演算操作(math operations)は固定小数点で処理される。従って、ハードウエアを効率的にするために、唯一の浮動・固定変換器があり、そして値はそれらがＶＣから１つずつ到着するときに変換される。ユニットはまた、０．０と６４．０の間の値へのテセレート係数のクランプを行う。
【００６４】
Ｂ．前処理モジュール７０４
前処理モジュール７０４は１度に１つのパッチを受信し、そしてそのパッチをテセレートするために用いられる値を事前計算する。即ち、ある実施形態においては、所与のパッチに対して、テセレーションモジュール７０６は、幾つかの数を繰り返し用いて、そのパッチに対するテセレーション点のパラメトリック位置を計算する。これらの数は、パッチの所与のエッジに対するテセレーション係数に基づいている。テセレーション係数のセットはパッチ毎に同じであるはずなので、前処理モジュールは、繰り返し用いられる数を計算することができ、またそれらをテセレーションモジュール７０６へ提供することができる。
【００６５】
前処理モジュール７０４によって実装され得る疑似コードが以下に挙げられている。しかし、この疑似コードは例示のみを目的とし且つ限定を目的としていないことが理解されるべきである。以下の疑似コードにおいては、太字の係数は、前処理モジュール７０４によって事前計算され、そして次いでテセレーションモジュール７０６に提供される係数である。
【００６６】
Ｃ．テセレーションモジュール７０６
テセレーションモジュール７０６は、前処理モジュール７０４からパッチ情報を受信し、そしてパッチのテセレートされる点の全てを作成する。テセレーションモジュール７０６とは異なり、ＤＸ１１アルゴリズムは、パッチ内のあらゆる点を計算し、そしてそれをメモリ内に、接続性パス(pass)の間に使用されるように記憶する。しかし、単一のパッチは最大で４，２２５個の点を有し得るので、これはハードウエアに対して効率的ではない。この問題に対処するために、テセレーションモジュール７０６は、パッチの部分を逐次的にテセレートして、テセレーション点がプリミティブ内へ接続されるかどうかが決定される順序で接続性モジュール７０８に提供される一連のテセレーション点を作成する。このように、ＤＸ１１アルゴリズムとは異なり、テセレーションモジュール７０６からのテセレーション点は、接続性モジュール７０８へ提供されるのに先立ちメモリ内に記憶される必要がない。
【００６７】
ある実施形態においては、テセレーションモジュール７０６は、パッチのエッジを並列に処理してテセレーション点を作成する２つの演算ユニット(math unit)を含む。例えば図８は、テセレーションモジュール７０６によって実装されるパイプラインの機能を示している。図８に示される機能は、図９Ａ〜９Ｃの例示的なパッチを参照して以下に説明される。
【００６８】
図８を参照すると、テセレーションモジュール７０６はステージ８０２においてパッチデータを受信する。上述したように、テセレーションモジュール７０６は、接続性モジュール７０８が適切な順序で出力プリミティブを作成することができるように、外側エッジ及び内側エッジに対するテセレーション点を並列に作成する。その際、外側エッジ制御ブロック８０８は受信したパッチの外側エッジを識別し、また内側エッジ制御ブロック８０４は受信したパッチの内側エッジを識別する。例えば、図９Ａにおけるパッチは外側エッジ９０１及び内側エッジ９０２を含む。テセレーションモジュール７０６は外側エッジ９０１及び内側エッジ９０２で開始して、そして下から上へと点を作成する。例えば、ステージ８１０及び８１２においてデータを段階付け(staging)た後、外側点計算ブロック８２０は外側エッジ９０１に沿ったテセレーション点を計算し、また内側点計算ブロック８１４は内側エッジ９０２に沿ったテセレーション点を計算する。外側エッジ９０１に対するテセレーション点は次いで一時的に８２４において段階付けられ、また内側エッジ９０２のテセレーション点は一時的に８２２において段階付けられる。外側点調節ブロック８２８及び内側点調節ブロック８２６は、それぞれ外側エッジ９０１及び内側エッジ９０２のテセレーション点のスキュー(skewing)を調節する。スキューは、内側エッジ上の点及び外側エッジ上の点が同じｖ座標（エッジが垂直の場合）又は同じｕ座標（エッジが水平の場合）で位置合わせされていない場合に生じる。テセレーション点は次いで、外側点ＦＩＦＯ８３２及び内側点ＦＩＦＯ８３０内にそれぞれ記憶される。接続性モジュール７０８は次いで、次のサブセクションで更に詳細に説明されるように、これらのＦＩＦＯからテセレーション点をリトリーブする。
【００６９】
パッチの左側の２つのエッジに沿ってテセレーション点を計算した後、テセレーションモジュール７０６は、パス(path)９０４によって示されるように、２つの上側エッジ上のテセレーション点を計算し、それにリングの右側と最後に下側が続く。外側リングが完了したら、処理は次の内側リングに対して繰り返す。リング制御ブロック８０６は、次の内側リングへの移行の処理を制御する。
【００７０】
図９Ａを参照すると、次の内側リングに対しては、エッジ９０２が外側エッジであり、またエッジ９０３が内側エッジである。内側点直交ブロック８１６は、直交値、即ち全エッジにわたって同じままの値を計算する。例えばエッジ９０２に沿ってｖ値は変化するが、ｕ値は変化しない。従ってエッジ９０２に沿ってｖ値は正則値であり、またｕ値は直交値である。これに対して、図９Ａにおけるパッチの上外側エッジに沿ってｕ値は変化するが、ｖ値は変化しない。従って上外側エッジに沿ってｕ値は正則値であり、またｖ値は直交値である。その結果、エッジ９０２に沿って、例えば、内側点計算ブロック８１４はｖ値０．８３３、０．６６６、０．５、０．３３３及び０．１６７（下から上へ）を提供する一方で、内側点直交計算ブロック８１６は全エッジに対して１つのｕ値０．１６７を提供する（エッジ９０２に沿ったｕ値は一定のままであるから）。
【００７１】
次のリングの処理の間、正則点値（即ちエッジに沿って変化する値）は再計算され、そして記憶されない。このことは、性能になんら問題を生じさせないし、また記憶ユニットを除去することによってハードウエア面積を低減する。一方、直交値（即ちエッジに沿って一定のままの値）は、直交ＦＩＦＯ８１８内に内側エッジから一時的に記憶され、そして外側エッジに用いられる。次の内側リングの処理の間（即ちエッジ９０２が外側エッジである場合）、外側点計算ブロック８２０はエッジ９０２に沿ってテセレーション点に対する正則点値を再計算し、また直交点値は直交値ＦＩＦＯ８１８からリトリーブされる。
【００７２】
パッチの全てのテセレーション点の計算は、パッチ内の全てのリングが処理されて完了する。点作成のこの処理は、図９Ａに示されるように蛇又は蛇紋のパターン(snake or serpentine pattern)を形成し、そして点はそれらが接続される順序で作成されるので、点の記憶をなんら必要とせず、このことは接続性モジュール７０８に関して後で更に詳細に説明される。点データの各片は、実行ユニット５０６が新たな頂点データを作成するために用いられるｕ，ｖ座標として索引付けられる。作成される各新たなプリミティブもまた、パッチＩＤでタグ付けされる。
【００７３】
点が異なる様態で作成される２つの特別な場合があり、図９Ｂ及び９Ｃに示されている。これら特別な場合の両方とも、パッチの最後のリングの間に生じる。図９Ｂを参照すると、第１の特別な場合は、パッチが多角形で終わる場合に生じる。これは最後のリングが内側エッジを有していないことを意味する。この場合、テセレーションモジュール７０６は、上側エッジ及び右側エッジを外側エッジ演算ユニット（例えば図８の機能ブロック８０８、８１２、８２０、８２４及び８２８）内で処理し、また左側エッジ及び下側エッジを内側演算ユニット（例えば図８の機能ブロック８０４、８１０、８１４、８２２及び８２６）内で処理する。これにより、次いでパッチの中央における三角形のグループとして接続され得る点のストリームが作成される。
【００７４】
図９Ｃを参照すると、他の特別な場合は、パッチが中央における線で終わる場合に生じる。この場合、中央における点は内側エッジ演算ユニット（例えば図８の機能ブロック８０４、８１０、８１４、８２２及び８２６）によって処理される。図９Ｃに示されるように、左から右に線が処理され、次いで向きを変えて右から左に点が再作成される（最も右側の点は除く）。線の同じ点を再使用する三角形が線の上方及び線の下方にあるであろうから、こうするものである。ある実施形態においては、線が１４点の長さより短い場合には、接続性モジュール７０８における再使用バッファは、繰り返された点が１回だけ実行ユニット５０６へ送られることを確実にする。
【００７５】
上述した特別な場合の両方とも、ｖ次元がｕ次元よりも大きい場合にも生じ得る。これは多角形又は線が水平の代わりに垂直であることを意味する。これは異なるエッジを演算ユニットにおいて処理させる。
【００７６】
Ｄ．接続性モジュール７０８
接続性モジュール７０８はテセレートされた点のデータをテセレーションモジュール７０６から受信し、そしてトポロジ（点、線、又は三角形）に基づいてプリミティブを作成する。接続性モジュール７０８は、頂点データをストリップフォーム(strip form)で送り出し、そしてプリミティブに対する相対的索引(relative indices)を送る。重要なことには、接続性モジュール７０８は、パッチのどのテセレーション点が、テセレーションモジュール７０６がテセレーション点を作成する順序で接続されることになるのかを決定し、このことが（上述したように）、ＤＸ１１アルゴリズムにおけるようにテセレーション点をメモリ内に記憶する必要性を回避している。
【００７７】
例えば図１３は、接続性モジュール７０８が図９Ａのパッチに対するテセレーション点の接続性を決定する例示的な順序を示している。即ち、接続性モジュール７０８は、テセレーション点を２つの外側エッジに沿って下から上へと処理する。図１３を参照すると、ある実施形態においては、接続性モジュール７０８は、（０，１）で表される頂点から開始して、そして（０，０）で表される頂点へと進む。例えば、接続性モジュール７０８は、頂点（０，１）、頂点１３０２及び頂点１３０４を、図１３において「１」で表される第１のプリミティブ（例えば三角形）に関連付けられるものとして識別してよい。同様に、接続性モジュール７０８は、頂点１３０２、頂点１３０４及び頂点１３０６を、図１３において「２」で表される第２のプリミティブ（例えば三角形）に関連付けられるものとして識別してよい。つまり、接続性モジュール７０８は、テセレーションモジュール７０６がパッチに対してテセレーション点を提供するのと同じ順序でテセレーション点がプリミティブ内へと接続されるかどうかを決定する。
【００７８】
接続性モジュール７０８は、テセレーション係数情報に基づいてアクセスされるルックアップテーブルのセットによって、出力頂点（即ちテセレーション点）の接続性を決定する。例えば、図１１は３２個のルックアップテーブルのセットを示しており、接続性モジュール７０８はこれらのルックアップテーブルから選択して頂点が接続されるかどうかを決定する。図１１を参照すると、左列はＬＵＴの番号を含み、また右列はＬＵＴを含む。
【００７９】
接続性モジュール７０８と異なり、ＤＸ１１アルゴリズムは３２エントリＬＵＴのみを用い、これは３１で表されるＬＵＴとして図１１に示されている。ＤＸ１１アルゴリズムに従うと、三角形がいつ作成され得るのかを決定するために、この１つのＬＵＴがループスルーされる(looped through)。ＤＸ１１におけるように１つのテーブルのみを用いることは、１つのプリミティブを作成するために最大で３２クロックを必要とし得ることを意味する。性能要求はクロックあたり１つのプリミティブを生成することであるから、これはハードウエアにとって極めて非効率的である。本発明の実施形態によると、図１１に示されるように１つのＬＵＴが３２個の別個のテーブルへと分割される。３２個のテーブルの１つを選択することによって、選択されたテーブルがループスルーされ得るし、そしてプリミティブは単一クロックサイクル内で作成され得る。
【００８０】
図１０は頂点が接続されるかどうかを決定するために接続性モジュール７０８によって実装される例示的な方法１０００を示している。図１０を参照すると、方法１０００はステップ１００２で開始し、複数のルックアップテーブルからルックアップテーブルが選択される。ある実施形態においては、ルックアップテーブルは、ハルシェーダ２０４によって提供されるテセレーション係数に基づいて選択される。特に、テセレーション係数は２で除され、「ハーフテス係数(half tess factor)」と称される数がもたらされ、そしてハーフテス係数がＬＵＴを選択するために用いられる。例えばテセレーション係数が１０であるとすると、ハーフテス係数は５であるから、５で表される図１１のＬＵＴ（エントリ｛４，２，５，１，６，３｝を含む）が選択されることになる。
【００８１】
再び図１０の方法１０００を参照すると、ステップ１００４では、選択されたルックアップテーブルに基づいてテセレーション点がプリミティブ内へと接続される。上述したように、図１３は頂点がどのようにしてプリミティブ内へと接続され得るのかを示している。
【００８２】
接続性モジュール７０８はまた、テセレーション点データを効率的な方法で提供する再使用論理を含む。テセレーションエンジンの再使用論理とは異なり、ＤＸ１１は、パッチの座標（即ちメモリ内に記憶される（ｕ，ｖ）値）への索引に基づいて再使用を処理する。ＤＸ１１が用いるメモリ内の索引は縮退している(degenerate)であろうし、このことは、パッチの点がメモリ内で一意的に索引付けられていないことを理由として、ＤＸ１１がテセレーション点データを２回以上送るであろうことを意味している。具体的には、テセレーション係数の幾つかの値と共に、ＤＸ１１のアルゴリズムは、エッジ上の多重点に対して同じパッチ座標（即ち（ｕ，ｖ）値）を生成する。しかし、ＤＸ１１はこれらの点を一意的なもとのみなしてそれらの全てを出力として送ってしまう。
【００８３】
これに対して、本発明の実施形態のテセレーションエンジンは、メモリの索引よりはむしろ、パッチの実際の座標（即ち実際の（ｕ，ｖ）値）に基づいて再使用を処理する。本発明の実施形態により指定されるように実際の座標を用いることは、ＤＸ１１アルゴリズムに起因して縮退三角形が形成される場合に役に立つ。
【００８４】
本発明の実施形態によると、テセレーションエンジンは第１の点を送り、そして任意の後続の点が第１の点と同じ座標（即ち（ｕ，ｖ）値）を有しているかどうかを決定する。テセレーションエンジンは、第１の点の座標を索引バッファ（例えば「パラメータキャッシュ」）内の点の座標と比較することによって、この決定をなす。ある実施形態においては、索引バッファは最大で１４点を記憶する。後続の点が第１の点と同じ座標（即ち（ｕ，ｖ）値）を有している場合には、テセレーションエンジンは後続の点を送らない。これによりシェーダ処理が節約される。
【００８５】
例えば図１２は、本発明の実施形態に従い頂点を再使用するために接続性モジュール７０８によって実装される例示的な方法１２００を示している。方法１２００はステップ１２０２で開始し、プリミティブの頂点はそれらのそれぞれの位置に従って索引付けられ、それらの位置はパッチ内の（ｕ，ｖ）値によって指定される。
【００８６】
グラフィクスパイプライン内の後続の処理に対して頂点を送るのに先立ち、ステップ１２０４に示されるように、その頂点に関連付けられている索引がバッファ内にあるかどうかが先ず決定される。ある実施形態においては、バッファは１４要素幅である。索引がバッファ内にある場合には、頂点は既にグラフィクスパイプラインへと送られているので、ステップ１２０６に示されるように、頂点はグラフィクスパイプライン内の後続の処理へは送られない。
【００８７】
一方、ステップ１２０４において索引がバッファ内にないと判断される場合には、ステップ１２０８に示されるように、グラフィクスパイプライン内の後続の処理に対して頂点が送られる。ステップ１２１０では、頂点に対する索引がバッファ内に置かれ、そして最も古い索引が、先入れ先出しのやり方でバッファからフラッシュされる(flushed)。
【００８８】
VI．例示的なソフトウエア実装
本発明の実施形態の処理ユニットのハードウエア実装（例えばＣＰＵ３０２及びＧＰＵ３１０）に加えて、そのような処理ユニットはまた、例えばソフトウエア（例えばコンピュータ可読プログラムコード）を記憶するように構成されるコンピュータ可読媒体内に配置されるソフトウエアにおいて具現化されてもよい。プログラムコードは、（i）ここに開示されるシステムの機能及び技術（例えば図７、８、１０及び１２に示される機能）、（ii）ここに開示されるシステムの製造及び技術（例えばＣＰＵ３０２及び／又はＧＰＵ３１０の製造）又は（iii）ここに開示されるシステムの機能及び製造並びに技術の組み合わせ、の実施形態を含めて本発明の実施形態の実施可能性を生じさせる。
【００８９】
このことは、例えば、一般的なプログラミング言語（例えばＣ又はＣ＋＋）、ベリログ(Verilog)ＨＤＬ、ＶＨＤＬ、アルテラ(Altera)ＨＤＬ（ＡＨＤＬ）等を含むハードウエア記述言語(hardware description languages)（ＨＤＬ）、あるいは他の利用可能なプログラミング及び／又は回路図等（schematic）キャプチャツール(capture tools)（例えば回路キャプチャツール）の使用を通して達成され得る。プログラムコードは、半導体、磁気ディスク、又は光学ディスク（例えばＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ）を含む任意の既知のコンピュータ可読媒体内に配置され得る。従って、コードは、インターネット及びそれと同等のもの(the Internet and internets)を含む通信ネットワークを介して伝送され得る。上述したシステム及び技術によって達成される機能及び／又は提供される構造は、プログラムコードにおいて具現化されるコア（例えばＣＰＵコア及び／又はＧＰＵコア）内で表現することができ、また集積回路の生産の一部としてハードウエアに変換されてよいことが理解される。
【００９０】
VII．結論
概要及び要約の欄ではなく詳細な説明の欄が特許請求の範囲を解釈するために用いられることを意図されていることが理解されるべきである。概要及び要約の欄は、発明者によって検討されているような本発明の１つ以上であるが全てではない例示的な実施形態を記述することができ、従って、本発明及び添付の特許請求の範囲を限定することを意図されるものでは決してない。
【特許請求の範囲】
【請求項１】
処理ユニットに実装されるグラフィクス処理方法であって、
幾何学的形状の部分を逐次的にテセレートして前記幾何学的形状に対する一連のテセレーション点を提供することと、
前記テセレーション点の１つ以上のグループを前記一連のテセレーション点が提供される順序で１つ以上のプリミティブ内へと接続することと、を備えるグラフィックス処理方法。
【請求項２】
前記逐次的にテセレートすることは、
前記幾何学的形状の外側エッジを第１の演算ユニット内でテセレートして前記一連のテセレーション点におけるテセレーション点の第１のサブセットを提供することと、
前記幾何学的形状の内側エッジを第２の演算ユニット内でテセレートして前記一連のテセレーション点におけるテセレーション点の第２のサブセットを提供することと、を備える請求項１のグラフィクス処理方法。
【請求項３】
前記接続することは、
前記テセレーション点をメモリ内に記憶することなしに、前記テセレーション点の１つ以上のグループを前記一連のテセレーション点が提供される順序で１つ以上のプリミティブ内へと接続することを備える請求項１のグラフィクス処理方法。
【請求項４】
前記接続することは、
テセレーション係数に基づいて複数のルックアップテーブルの１つを選択することと、
前記選択されたルックアップテーブルを用いて、前記１つ以上のプリミティブ内へと接続されるべき前記テセレーション点の前記１つ以上のグループを識別することと、を備える請求項１のグラフィクス処理方法。
【請求項５】
前記接続することは、
クロックサイクルあたり１つのプリミティブを提供することを備える請求項１のグラフィクス処理方法。
【請求項６】
前記１つ以上のプリミティブに基づいて結果データを生成することと、
前記結果データをテセレーション係数に応じてオンチップメモリ又はオフチップメモリのいずれかに書き込むことと、を更に備える請求項１のグラフィクス処理方法。
【請求項７】
前記書き込むことは、
前記テセレーション係数が予め定められたスレッショルドよりも小さい場合に前記結果データを前記オンチップメモリに書き込むことと、
前記テセレーション係数が前記予め定められたスレッショルドよりも大きい場合に前記結果データを前記オフチップメモリに書き込むことと、を備える請求項６のグラフィクス処理方法。
【請求項８】
前記幾何学的形状内の各それぞれの頂点の位置に基づいて前記１つ以上のプリミティブのそれぞれの頂点を索引付けることと、
頂点の当該索引に基づいて頂点を後続の処理に送るかどうかを決定することと、を更に備える請求項１のグラフィクス処理方法。
【請求項９】
幾何学的形状の部分を逐次的にテセレートして前記幾何学的形状に対する一連のテセレーション点を提供するように構成されるテセレーションモジュールと、
前記テセレーション点の１つ以上のグループを前記一連のテセレーション点が提供される順序で１つ以上のプリミティブ内へと接続するように構成される接続性モジュールと、を備える処理ユニット。
【請求項１０】
前記テセレーションモジュールは、
前記幾何学的形状の外側エッジをテセレートして前記一連のテセレーション点におけるテセレーション点の第１のサブセットを提供するように構成される第１の演算ユニットと、
前記幾何学的形状の内側エッジをテセレートして前記一連のテセレーション点におけるテセレーション点の第２のサブセットを提供するように構成される第２の演算ユニットと、を備える請求項９の処理ユニット。
【請求項１１】
前記一連のテセレーション点はメモリ内に記憶されない請求項９の処理ユニット。
【請求項１２】
前記接続性モジュールは、
テセレーション係数に基づいて複数のルックアップテーブルの１つを選択し、
前記選択されたルックアップテーブルを用いて、前記１つ以上のプリミティブ内へと接続されるべき前記テセレーション点の前記１つ以上のグループを識別するように更に構成される請求項９の処理ユニット。
【請求項１３】
前記接続性モジュールは、クロックサイクルあたり１つのプリミティブを提供するように構成される請求項９の処理ユニット。
【請求項１４】
前記処理ユニットは前記１つ以上のプリミティブに基づいて結果データを生成するように構成され、前記結果データはテセレーション係数に応じてオンチップメモリ又はオフチップメモリのいずれかに書き込まれる請求項９の処理ユニット。
【請求項１５】
前記テセレーション係数が予め定められたスレッショルドよりも小さい場合に前記結果データは前記オンチップメモリに書き込まれ、
前記テセレーション係数が前記予め定められたスレッショルドよりも大きい場合に前記結果データは前記オフチップメモリに書き込まれる請求項１４の処理ユニット。
【請求項１６】
前記接続性モジュールは、
前記幾何学的形状内の各それぞれの頂点の位置に基づいて前記１つ以上のプリミティブのそれぞれの頂点を索引付け、
頂点の当該索引に基づいて頂点を後続の処理に送るかどうかを決定するように更に構成される請求項９の処理ユニット。
【請求項１７】
システムメモリと、
前記システムメモリに結合される処理ユニットと、を備えるコンピューティングシステムであって、
前記処理ユニットは、
幾何学的形状の部分を逐次的にテセレートして前記幾何学的形状に対する一連のテセレーション点を提供するように構成されるテセレーションモジュールと、
前記テセレーション点の１つ以上のグループを前記一連のテセレーション点が提供される順序で１つ以上のプリミティブ内へと接続するように構成される接続性モジュールと、を備えるコンピューティングシステム。
【請求項１８】
前記テセレーションモジュールは、
前記幾何学的形状の外側エッジをテセレートして前記一連のテセレーション点におけるテセレーション点の第１のサブセットを提供するように構成される第１の演算ユニットと、
前記幾何学的形状の内側エッジをテセレートして前記一連のテセレーション点におけるテセレーション点の第２のサブセットを提供するように構成される第２の演算ユニットと、を備える請求項１７のコンピューティングシステム。
【請求項１９】
前記一連のテセレーション点は前記システムメモリ内に記憶されない請求項１７のコンピューティングシステム。
【請求項２０】
前記接続性モジュールは、
テセレーション係数に基づいて複数のルックアップテーブルの１つを選択し、
前記選択されたルックアップテーブルを用いて、前記１つ以上のプリミティブ内へと接続されるべき前記テセレーション点の前記１つ以上のグループを識別するように更に構成される請求項１７のコンピューティングシステム。
【請求項２１】
前記接続性モジュールは、クロックサイクルあたり１つのプリミティブを提供するように構成される請求項１７のコンピューティングシステム。
【請求項２２】
前記処理ユニットはローカルメモリを更に備え、
結果データはテセレーション係数に応じて前記ローカルメモリ又は前記システムメモリのいずれかに書き込まれる請求項１７のコンピューティングシステム。
【請求項２３】
前記テセレーション係数が予め定められたスレッショルドよりも小さい場合に前記結果データは前記ローカルメモリに書き込まれ、
前記テセレーション係数が前記予め定められたスレッショルドよりも大きい場合に前記結果データは前記オフチップメモリに書き込まれる請求項２２のコンピューティングシステム。
【請求項２４】
前記接続性モジュールは、
前記幾何学的形状内の各それぞれの頂点の位置に基づいて前記１つ以上のプリミティブのそれぞれの頂点を索引付け、
頂点の当該索引に基づいて頂点を後続の処理に送るかどうかを決定するように更に構成される請求項１７のコンピューティングシステム。
【請求項１】
処理ユニットに実装されるグラフィクス処理方法であって、
幾何学的形状の部分を逐次的にテセレートして前記幾何学的形状に対する一連のテセレーション点を提供することと、
前記テセレーション点の１つ以上のグループを前記一連のテセレーション点が提供される順序で１つ以上のプリミティブ内へと接続することと、を備えるグラフィックス処理方法。
【請求項２】
前記逐次的にテセレートすることは、
前記幾何学的形状の外側エッジを第１の演算ユニット内でテセレートして前記一連のテセレーション点におけるテセレーション点の第１のサブセットを提供することと、
前記幾何学的形状の内側エッジを第２の演算ユニット内でテセレートして前記一連のテセレーション点におけるテセレーション点の第２のサブセットを提供することと、を備える請求項１のグラフィクス処理方法。
【請求項３】
前記接続することは、
前記テセレーション点をメモリ内に記憶することなしに、前記テセレーション点の１つ以上のグループを前記一連のテセレーション点が提供される順序で１つ以上のプリミティブ内へと接続することを備える請求項１のグラフィクス処理方法。
【請求項４】
前記接続することは、
テセレーション係数に基づいて複数のルックアップテーブルの１つを選択することと、
前記選択されたルックアップテーブルを用いて、前記１つ以上のプリミティブ内へと接続されるべき前記テセレーション点の前記１つ以上のグループを識別することと、を備える請求項１のグラフィクス処理方法。
【請求項５】
前記接続することは、
クロックサイクルあたり１つのプリミティブを提供することを備える請求項１のグラフィクス処理方法。
【請求項６】
前記１つ以上のプリミティブに基づいて結果データを生成することと、
前記結果データをテセレーション係数に応じてオンチップメモリ又はオフチップメモリのいずれかに書き込むことと、を更に備える請求項１のグラフィクス処理方法。
【請求項７】
前記書き込むことは、
前記テセレーション係数が予め定められたスレッショルドよりも小さい場合に前記結果データを前記オンチップメモリに書き込むことと、
前記テセレーション係数が前記予め定められたスレッショルドよりも大きい場合に前記結果データを前記オフチップメモリに書き込むことと、を備える請求項６のグラフィクス処理方法。
【請求項８】
前記幾何学的形状内の各それぞれの頂点の位置に基づいて前記１つ以上のプリミティブのそれぞれの頂点を索引付けることと、
頂点の当該索引に基づいて頂点を後続の処理に送るかどうかを決定することと、を更に備える請求項１のグラフィクス処理方法。
【請求項９】
幾何学的形状の部分を逐次的にテセレートして前記幾何学的形状に対する一連のテセレーション点を提供するように構成されるテセレーションモジュールと、
前記テセレーション点の１つ以上のグループを前記一連のテセレーション点が提供される順序で１つ以上のプリミティブ内へと接続するように構成される接続性モジュールと、を備える処理ユニット。
【請求項１０】
前記テセレーションモジュールは、
前記幾何学的形状の外側エッジをテセレートして前記一連のテセレーション点におけるテセレーション点の第１のサブセットを提供するように構成される第１の演算ユニットと、
前記幾何学的形状の内側エッジをテセレートして前記一連のテセレーション点におけるテセレーション点の第２のサブセットを提供するように構成される第２の演算ユニットと、を備える請求項９の処理ユニット。
【請求項１１】
前記一連のテセレーション点はメモリ内に記憶されない請求項９の処理ユニット。
【請求項１２】
前記接続性モジュールは、
テセレーション係数に基づいて複数のルックアップテーブルの１つを選択し、
前記選択されたルックアップテーブルを用いて、前記１つ以上のプリミティブ内へと接続されるべき前記テセレーション点の前記１つ以上のグループを識別するように更に構成される請求項９の処理ユニット。
【請求項１３】
前記接続性モジュールは、クロックサイクルあたり１つのプリミティブを提供するように構成される請求項９の処理ユニット。
【請求項１４】
前記処理ユニットは前記１つ以上のプリミティブに基づいて結果データを生成するように構成され、前記結果データはテセレーション係数に応じてオンチップメモリ又はオフチップメモリのいずれかに書き込まれる請求項９の処理ユニット。
【請求項１５】
前記テセレーション係数が予め定められたスレッショルドよりも小さい場合に前記結果データは前記オンチップメモリに書き込まれ、
前記テセレーション係数が前記予め定められたスレッショルドよりも大きい場合に前記結果データは前記オフチップメモリに書き込まれる請求項１４の処理ユニット。
【請求項１６】
前記接続性モジュールは、
前記幾何学的形状内の各それぞれの頂点の位置に基づいて前記１つ以上のプリミティブのそれぞれの頂点を索引付け、
頂点の当該索引に基づいて頂点を後続の処理に送るかどうかを決定するように更に構成される請求項９の処理ユニット。
【請求項１７】
システムメモリと、
前記システムメモリに結合される処理ユニットと、を備えるコンピューティングシステムであって、
前記処理ユニットは、
幾何学的形状の部分を逐次的にテセレートして前記幾何学的形状に対する一連のテセレーション点を提供するように構成されるテセレーションモジュールと、
前記テセレーション点の１つ以上のグループを前記一連のテセレーション点が提供される順序で１つ以上のプリミティブ内へと接続するように構成される接続性モジュールと、を備えるコンピューティングシステム。
【請求項１８】
前記テセレーションモジュールは、
前記幾何学的形状の外側エッジをテセレートして前記一連のテセレーション点におけるテセレーション点の第１のサブセットを提供するように構成される第１の演算ユニットと、
前記幾何学的形状の内側エッジをテセレートして前記一連のテセレーション点におけるテセレーション点の第２のサブセットを提供するように構成される第２の演算ユニットと、を備える請求項１７のコンピューティングシステム。
【請求項１９】
前記一連のテセレーション点は前記システムメモリ内に記憶されない請求項１７のコンピューティングシステム。
【請求項２０】
前記接続性モジュールは、
テセレーション係数に基づいて複数のルックアップテーブルの１つを選択し、
前記選択されたルックアップテーブルを用いて、前記１つ以上のプリミティブ内へと接続されるべき前記テセレーション点の前記１つ以上のグループを識別するように更に構成される請求項１７のコンピューティングシステム。
【請求項２１】
前記接続性モジュールは、クロックサイクルあたり１つのプリミティブを提供するように構成される請求項１７のコンピューティングシステム。
【請求項２２】
前記処理ユニットはローカルメモリを更に備え、
結果データはテセレーション係数に応じて前記ローカルメモリ又は前記システムメモリのいずれかに書き込まれる請求項１７のコンピューティングシステム。
【請求項２３】
前記テセレーション係数が予め定められたスレッショルドよりも小さい場合に前記結果データは前記ローカルメモリに書き込まれ、
前記テセレーション係数が前記予め定められたスレッショルドよりも大きい場合に前記結果データは前記オフチップメモリに書き込まれる請求項２２のコンピューティングシステム。
【請求項２４】
前記接続性モジュールは、
前記幾何学的形状内の各それぞれの頂点の位置に基づいて前記１つ以上のプリミティブのそれぞれの頂点を索引付け、
頂点の当該索引に基づいて頂点を後続の処理に送るかどうかを決定するように更に構成される請求項１７のコンピューティングシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９Ａ】
【図９Ｂ】
【図９Ｃ】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９Ａ】
【図９Ｂ】
【図９Ｃ】
【図１０】
【図１１】
【図１２】
【図１３】
【公表番号】特表２０１３−５０４８１６（Ｐ２０１３−５０４８１６Ａ）
【公表日】平成２５年２月７日（２０１３．２．７）
【国際特許分類】
【出願番号】特願２０１２−５２８８９２（Ｐ２０１２−５２８８９２）
【出願日】平成２２年９月９日（２０１０．９．９）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０４８２４９
【国際公開番号】ＷＯ２０１１／０３１８４４
【国際公開日】平成２３年３月１７日（２０１１．３．１７）
【出願人】（５９１０１６１７２）アドバンスト・マイクロ・ディバイシズ・インコーポレイテッド (439)
【氏名又は名称原語表記】ＡＤＶＡＮＣＥＤ ＭＩＣＲＯ ＤＥＶＩＣＥＳ ＩＮＣＯＲＰＯＲＡＴＥＤ
【Ｆターム（参考）】
【公表日】平成２５年２月７日（２０１３．２．７）
【国際特許分類】
【出願日】平成２２年９月９日（２０１０．９．９）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０４８２４９
【国際公開番号】ＷＯ２０１１／０３１８４４
【国際公開日】平成２３年３月１７日（２０１１．３．１７）
【出願人】（５９１０１６１７２）アドバンスト・マイクロ・ディバイシズ・インコーポレイテッド (439)
【氏名又は名称原語表記】ＡＤＶＡＮＣＥＤ ＭＩＣＲＯ ＤＥＶＩＣＥＳ ＩＮＣＯＲＰＯＲＡＴＥＤ
【Ｆターム（参考）】
[ Back to top ]